Метод прогонки

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

         К матрицам, которые не редко встречаются в задачах физики и техники и допускают такое ускорение расчета; относятся ленточные (а), ящичные (в), квазитреугольные (д),  почти треугольные (е) и многие другие. Можно сказать, что при обходе нулевых элементов решение системы с почти треугольной матрицей требует даже выбор главного элемента. Но обычно в этом нет необходимости, поскольку подобные физические задачи приводят, как правило, к хорошим обусловленным матрицам с большими элементами на главной диагонали, для которых ошибки округления в методе Гаусса не велики.

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

                                                 (1)

Формула (1) называется разностным уравнением второго порядка, или трехточечным уравнением. В этом случае прямой ход (без выбора главного элемента) сводится к исключению элементов ai. получается треугольная система, содержащая в каждом уравнении только два неизвестных, xi и xi+1. поэтому формулы обратного имеют следующий вид:

         (2)

Уменьшим в формуле (2) индекс на единицу и подставим в уравнение (3):

Выражая отсюда xi через  xi+1 получим

                (3)

Чтобы это выражение совпало с (2), надо, чтобы стоящие в его правой части дроби были равны соответственно ξi+1  и ηi+1. Отсюда получим запись формул прямого хода

(4)

Попутно можно найти определитель трехдиоганальной матрицы

                          (5)

Вычисления по формулам прогонки (4)-(3) требует всего 3п ячеек памяти и 9п арифметических действий, т.е. они гораздо экономнее общих формул метода исключения.

         В формулах прямого и обратного хода начало счета «замаскировано»: для начала (развязки) расчета формально требуется задать величины ξ1, η1 и xn=1 , которые неизвестны. Однако перед этими величинами в формулах стоят множители ai или ξn+1 ~сп, равные нулю.

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

(6)

(причем хотя бы для одного i имеет место неравенство), то в формулах прямого хода (3) не возникает деления на нуль, и тем самым исходная система (1) имеет единственное решение. Для этого предположим, что |ξi|<1 при некотором значении индекса. Тогда легко проверяется цепочка неравенств

|ξi+1|=|ci|/|bi-aiξi|≤|ci|/(|bi|-|ai||ξi|)≤|ci|/(|ci|+|ai|-|ai|×|ξi|)<1

поскольку можно положить ξ1=0, отсюда по индукции следует |ξi|<1; значит, , что и требовалось доказать. При выполнении условия (20) формулы прогонки не только безопасны, но и устойчивы относительно ошибок округления и позволяют успешно решать системы уравнений с несколькими сотнями неизвестных.

         Условие (3) является достаточным, но не необходимым условием устойчивости прогонки. Конечно, можно построить примеры неустойчивости при несоблюдении этого условия. Но в практических расчетах для хорошо обусловленных систем типа (1) прогонка часто оказывается достаточно устойчивой даже при нарушении условия преобладания диагональных элементов.

         Заметим, что к линейным системам с трехдиогональной матрицей обычно приводят трехточечные разностные схемы для дифференциальных уравнений второго порядка.