5. Прогонка.

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

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

Можно показать, что при обходе нулевых элементов решение системы с почти треугольной матрицей требует всего действий, а с ленточной — даже , где — ширина ленты, т. е. выигрыш во времени счета очень велик.

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

Рис. 25.

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

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

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

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

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

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

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

(13)

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

В формулах прямого и обратного хода начало счета «замаскировано»: для начала (развязки) расчета формально требуется задать величины которые неизвестны. Однако перед этими величинами в формулах стоят множители или равные нулю. Это позволяет начать вычисления, полагая, например,

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

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

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

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

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