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

Метод Гаусса с процедурой выбора главного элемента считается одним из лучших для решения систем линейных уравнений с плотно заполненной матрицей общего вида. Однако часто при решении прикладных задач возникает необходимость решать системы уравнений с матрицей, содержащей большое количество нулевых элементов. В этом случае можно так организовать расчеты, чтобы не включать в них эти нулевые элементы. Метод прогонки является наиболее известным и эффективным методом решения СЛАУ с ленточной матрицей, в которой ненулевые элементы группируются вблизи главной диагонали. Такие системы возникают при численном решении дифференциальных уравнений в частных производных, интерполировании сплайнами и моделировании некоторых физических и экономических процессов. Метод прогонки можно рассматривать как частный случай метода Гаусса, так как в нем также можно выделить прямой ход, на котором из уравнений исключаются переменные и обратный ход, позволяющий вычислить решение системы. При этом процедуру выбора главного элемента в этом методе применять нельзя, так как перестановка строк или столбцов может разрушить специфическую структуру матрицы системы.

Рассмотрим систему уравнений с трехдиагональной матрицей.

(11.10)

Такие системы принято записывать в каноническом виде

(11.11)

Определение. Формула (11.11) называется разностным уравнением второго порядка, или трехточечным уравнением.

Выразим из первого уравнения системы (11.10) переменную x ₁, а из последнего - переменную x _n, предполагая, что b ₁ ≠ 0, b _n ≠0,

(11.12)

Определение. Соотношения (11.12) называются краевыми условиями для разностного уравнения (11.11).

Подставляя первое краевое условие во второе уравнение в (11.10), исключим из него переменную x ₁. Получим уравнение

, или

, (11.13)

где

Найденное выражение (11.13) для x ₂ подставим в следующее уравнение в (11.10) и получим уравнение, связывающее переменные x ₃ и x ₄ и т.д.

Предполагая, что мы уже выразили в (i –1)–ом уравнении x _i-1 через x_i

, (11.14)

и подставляя выражение для x _i-1 (11.14) в i- е уравнение

,

получим следующую формулу обратного хода

, (11.15)

где коэффициенты задаются рекуррентными формулами прямого хода

(11.16)

Расчет по формулам (11.16) начинается при значении i =2, при этом необходимые значения краевых коэффициентов вычисляются по формулам (11.12).

Для начала расчета по формуле обратного хода (11.15) необходимо вычислить значение x _n. Подставим во второе краевое условие (11.12) выражение для x _n-1, полученное из формулы (11.15) при i = n- 1

(11.17)

где заданные в (11.12) краевые коэффициенты, а вычислены по формуле прямого хода (16). Из уравнения (11.17) найдем значение x _n

(11.18)

Таким образом, для нахождения решения сначала по формулам (11.16) вычисляем все коэффициенты , затем по формулам (11.18), (11.15) в обратном порядке вычисляем значения неизвестных.

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

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

(11.19)

(причем неравенство имеет место хотя бы для одного i), то в формулах прямого хода (16) и формуле (18) не возникает деления на нуль и система имеет единственное решение. Условие (19) является достаточным условием существования единственного решения системы (10). Однако в практических расчетах метод прогонки оказывается достаточно устойчивым и в случаях нарушения данного условия.