Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ЧИСЛЕННЫЕ МЕТОДЫ
Посмотреть оригинал

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

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

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

  • • Приведение трехдиагональной матрицы к верхней треугольной (прямой ход). В случае трехдиагональной матрицы это означает приведение к двухдиагональной, т. е. приведение исходной системы к системе, содержащей по два неизвестных в каждом уравнении, кроме последнего, в котором содержится только одно неизвестное.
  • • Запись обратного хода в виде xi = Р, + tx( + х + Q( + v так как преобразованная матрица — двухдиагональная.
  • • Вывод рекуррентного соотношения для Pi + 1 и^ + 1 через Pt

и Qi и получение соотношения для Рг и Q2х = = 0).

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

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

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

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

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

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

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

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

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

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

Для начала прямого хода метода прогонки необходимо задать начальные (стартовые) значения прогоночных коэффициентов, например Pv Qr Отметим, что, вообще говоря, начальные значения коэффициентов Pv в рассмотренной схеме вычислений не требуются, так как значения коэффициентов Р2, Q2 вычисляются только через коэффициенты первого уравнения системы (1.6): при i = 1 из (1.6) получаем соотношение -ЬуХу + сгхг - dv Сравнивая это выражение с (1.7) при i = 1, получаем Р2 = с11; Q2 = -djbv а значение в обратном ходе вычисляем по соотношению Ху - Р2х2 + Q2. Использование Pv Qj в качестве начальных значений целесообразно по двум причинам: сохраняется однородность вычислительного алгоритма для всех i = 2, 3, .... п; упрощается обсуждение и доказательство условия корректности и устойчивости метода прогонки. Из того обстоятельства, что коэффициенты Р2, Q2 не зависят от Plt Qj (в соотношениях (1.8) при i = 1 коэффициенты Pj, Qj умножаются на ах = 0), следует, что можно задать любые значения для прогоночных коэффициентов Рj, Qj. Далее будет ясно, почему удобно положить Pi = Q1 ~ 0. Для начала обратного хода метода прогонки необходимо для вычисления xi = Р, + jXt + j + Q( + 1 задать значение хп + г Так как сп - 0, то из первого соотношения (1.8) вытекает, что t, = 0 и, следовательно, можно задать любое значение для xn + v Обычно полагают хп +д = 0, и тогда xn = Qn х г

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

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

Из этой формулы при Pi + < 1 следует, что в данном случае по

грешность не возрастает.

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

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

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

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

Метод прогонки обобщается на случай, при котором в системе (1.6) ar 6j( cj — квадратные матрицы размерности тх т, a xjt dt векторы размерности т. Тогда соотношения (1.7) и (1.8) метода прогонки, в которых все действия совершаются уже над матрицами, а не над скалярами, сохраняются, а [Ь; - а,Р4]-1 в (1.8) является соответствующей обратной матрицей.

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

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

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы