Метод прогонки для решения систем линейных уравнений с трехдиагональной матрицей

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

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

• • Приведение трехдиагональной матрицы к верхней треугольной (прямой ход). В случае трехдиагональной матрицы это означает приведение к двухдиагональной, т. е. приведение исходной системы к системе, содержащей по два неизвестных в каждом уравнении, кроме последнего, в котором содержится только одно неизвестное.
• • Запись обратного хода в виде x_i = Р, _{+ t}x_{( + х} + Q_{(+ v} так как преобразованная матрица — двухдиагональная.
• • Вывод рекуррентного соотношения для P_{i + 1} и^ _{+ 1} через P_t

и Q_i и получение соотношения для Р_г и Q₂ (Р_х = = 0).

• Осуществление обратного хода метода прогонки и определение всех неизвестных.

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

Запись (1.6) представляет собой так называемый КАНОНИЧЕСКИЙ ВИД СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДА ПРОГОНКИ. При этом матрица системы (1.6) имеет вид.

Прямой ход метода прогонки сводится к исключению неизвестного x_t _ _г в каждом уравнении системы. Получаемая в результате прямого хода система содержит в каждом уравнении только два неизвестных х_{ и x_{t +}, и матрица ее — верхняя треугольная с двумя диагоналями. Запишем i-ю строку преобразованной двухдиагональной матрицы в виде.

Если система (1.6) приведена к виду (1.7), то обратный ход метода Гаусса очевиден. Однако использование общих алгоритмов прямого и обратного хода нецелесообразно. Построим эффективную вычислительную схему, которая и составляет суть метода прогонки. Для этого, уменьшив в (1.7) индекс на единицу, запишем

Подставляя x_t _ _: в систему (1.6), получим соотношение.

из которого нетрудно получить.

Сравнивая это соотношение с (1.7), можем записать рекуррентные соотношения.

для вычисления так называемых ПРОГОНОЧНЫХ КОЭФФИЦИЕНТОВ.

Подчеркнем, что последующие значения прогоночных коэффициентов Р._f j, Q, * ! вычисляются только по известным коэффициентам системы (1.6) и известным предыдущим значениям прогоночных коэффициентов P_r Q_t.

Для начала прямого хода метода прогонки необходимо задать начальные (стартовые) значения прогоночных коэффициентов, например P_v Q_r Отметим, что, вообще говоря, начальные значения коэффициентов P_v в рассмотренной схеме вычислений не требуются, так как значения коэффициентов Р₂, Q₂ вычисляются только через коэффициенты первого уравнения системы (1.6): при i = 1 из (1.6) получаем соотношение -ЬуХу + с_гх_г — d_v Сравнивая это выражение с (1.7) при i = 1, получаем Р₂ = с₁/Ь₁; Q₂ = -djb_v а значение в обратном ходе вычисляем по соотношению Ху — Р₂х₂ + Q₂. Использование P_v Qj в качестве начальных значений целесообразно по двум причинам: сохраняется однородность вычислительного алгоритма для всех i = 2, 3, … п; упрощается обсуждение и доказательство условия корректности и устойчивости метода прогонки. Из того обстоятельства, что коэффициенты Р₂, Q₂ не зависят от P_lt Qj (в соотношениях (1.8) при i = 1 коэффициенты Pj, Qj умножаются на а_х = 0), следует, что можно задать любые значения для прогоночных коэффициентов Рj, Qj. Далее будет ясно, почему удобно положить P_i = Q₁ ~ 0. Для начала обратного хода метода прогонки необходимо для вычисления x_i = Р, ₊ jX_{t +} j + Q_{(+ 1} задать значение х_{п + г} Так как с_п — 0, то из первого соотношения (1.8) вытекает, что _t, = 0 и, следовательно, можно задать любое значение для x_{n + v} Обычно полагают х_{п +д} = 0, и тогда x_n = Q_{n х г}

Метод прогонки устойчив, если [Pj < 1. Метод прогонки корректен, если dr — a_jP_i * 0.

Отметим, что при устойчивости метода прогонки ошибки округления не возрастают, а подавляются. Пусть jc_jf x_{i + г} — вычисленные с погрешностями значения решения. Пусть при этом коэффициенты P_{i +} I, Q_t i-i вычисляются точно. Тогда по (1.7).

Из этой формулы при P_{i +} < 1 следует, что в данном случае по грешность не возрастает.

Достаточным условием корректности метода прогонки и устойчивости его к погрешностям является условие преобладания диагональных коэффициентов:

В самом деле, если хотя бы для одного значения i выполняется строгое неравенство ]Р,| < 1, то можно записать цепочку неравенств:

Выло показано, что можно положить |Pj| = 0 и тогда, во-первых, для всех i выполняется |Р₍| < 1, что обеспечивает затухание погрешности, и, во-вторых, для всех i выполняется условие |dr — aPj > |cj > 0 и, таким образом, не возникает ситуации деления на нуль. Так как условие |{г) > |а₍| + jcj является только достаточным, то невыполнение его не означает нарушения корректности и устойчивости.

Для реализации метода требуется примерно 8л операций, из которых Зл составляют операции типа умножения и 5л — операции типа сложения. При численном решении дифференциальных уравнений используются различные варианты метода прогонки: метод встречных прогонок, потоковая прогонка, матричная прогонка для систем векторных уравнений. Отметим, что.

Метод прогонки обобщается на случай, при котором в системе (1.6) a_r 6_{j (} c_j — квадратные матрицы размерности тх т, a x_jt d_t — векторы размерности т. Тогда соотношения (1.7) и (1.8) метода прогонки, в которых все действия совершаются уже над матрицами, а не над скалярами, сохраняются, а [Ь_; — а, Р₄]^-1 в (1.8) является соответствующей обратной матрицей.

Условие устойчивости матричной прогонки выглядит как fdet P. f < 1, а условие корректности и устойчивости имеет вид.

det (В^С.) + det (В.¹ А) < 1.