4. Трёхдиагональные матрицы и метод прогонки

Матрицы Хессенберга – квадратные матрицы H [10], которые являются обобщением треугольных матриц. У верхней матрицы Хессенберга элементы, лежащие ниже первой нижней диагонали, нулевые. В нижней матрице Хессенберга нулевыми являются элементы выше первой верхней диагонали. Соответственно, нижняя матрица при транспонировании обращается в верхнюю, и наоборот.

Матрицы, которые одновременно удовлетворяют свойствам и нижних, и верхних матрицам Хессенберга, называются трёхдиагоальными, так как ненулевые элементы лежат только на главной, первой нижней и первой верхней диагоналях. Такие матрицы имеют следующий вид:

где при .

[11] Определитель такой матрицы рассчитывается с помощью рекуррентного соотношения

с начальными значениями и . Это позволяет вычислять определитель за линейное время, когда для матрицы общего вида вычисления оцениваются как .

Наиболее часто такие матрицы используются при решении дифференциальных уравнений. А так как сфера применения последних очень широка (включает в себя приближение функций, физические задачи

Для трёхдиагональных матриц используется не алгоритм Гаусса, а его модификация – метод прогонки. Если в алгоритме Гаусса исключение переменных производится из всех уравнений, лежащих ниже рассматриваемого, то в методе прогонки изменения затронут только одну строку (лежащую ниже рассматриваемой). Отметим, что вычисления также имеют линейную сложность.

Алгоритм сводится к вычислению прогоночных коэффициентов – рекуррентно вычисляемых по строкам коэффициентов для выражения одной переменной строки через другую. Таким образом,

где , а – прогоночные коэффициенты.

Вывод

В данном разделе приведено описание алгоритма Гаусса и его модификаций. Это необходимо для того, чтобы определить основные идеи перехода от классических алгоритмов к тропическим (они выделены в разделе 3) и сформулировать схожие мысли для аналога метода прогонки – алгоритма решения системы линейных уравнений с трёхдиагональной матрицей. Так как данные матрицы широко применяются при решении задач физики и приближения функций, попытка перехода к тропической системе может упросить вычислительные процессы.

2. Сравнение алгоритмов гаусса и григорьева

Приведённый в данном разделе материал является исследовательским, не опирается на какие-либо источники и состоит из предположений.

3.1 Сравнение шагов алгоритма Гаусса и алгоритма Григорьева

Проведём аналогии между шагами алгоритмов, чтобы показать их схожесть.

Так как тропическое умножение – это классическое сложение, определим тропическое деление как вычитание. Анализируемые строки для алгоритма Григорьева – это строки от 1 до m, где m – мощность множества J.

Сравнение алгоритмов приведено в таблице 3.1.

Таблица 3.1 – Сравнение шагов алгоритмов Гаусса и Григорьева
Алгоритм Гаусса (в терминах классической математики)	Алгоритм Григорьева (в терминах тропической математики)
Выбираем строки, в которых надо «избавиться» от переменных. Обозначим их как множество I. Рассматриваемую строку назовём i.	Выделяем столбцы, которые должны быть изменены. Это множество J. Число строк для анализа равно мощности J.
Для каждой строки из I находим коэффициент, домножение на который при суммировании со строкой i «исключит» переменную. Обозначим множество таких коэффициентов как K.	Находим одну константу для J, добавление которой к элементам J позволит увеличить число минимумов хотя бы в одной строке. Обозначим её const.
Каждый из K равен частному коэффициентов строки i и соответствующей строки из I при исключаемой переменной.	Для вычисления const сначала находят тропическую сумму тропических произведений переменных из столбцов J с их коэффициентами. Затем то же самое для не принадлежащих J столбцов. Тропически делим первую и вторую суммы соответствующих строк, тропически суммируем результаты для всех анализируемых строк.
Заменяем строки из I их линейными комбинациями с соответствующими коэффициентами из K и строкой i.	Тропически умножаем столбцы из J на const.
Повторяем шаги, приводя матрицу к верхне-треугольному виду: все элементы, лежащие ниже главной диагонали, должны обнулиться.	Повторяем шаги, приводя матрицу к виду, напоминающему верхне-треугольный: все минимумы всех срок должны лежать ниже главной диагонали.
Решение СЛУ получается с помощью обратного хода алгоритма Гаусса. Действия повторяются в обратном порядке.	Решение ТСЛУ получается через вычитание первой строки исходной матрицы из первой строки полученной.