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

      Будем называть прогонку корректной, если знаменатели прогоночных коэффициентов (3) не обращаются в нуль, и устойчивой, если |δ_i|<1 при всех i€{1,2,...,n }.

      Приведем  простые достаточные условия корректности и устойчивости прогонки, которые во многих приложениях метода автоматически выполняются. 

4. Теорема о корректности и устойчивости прогонки

    Пусть коэффициенты b_i и d_i  уравнения (1) при i=2,3,...,n-1 отличны от нуля и пусть

                  |c_i|>|b_i|+|d_i|  i=1,2,…,n.    (4) 

    Тогда прогонка (3), (2) корректна и устойчива (т.е. с_i+b_iδ_i-1≠0, |δ_i|<1). 

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

    При i=1, в силу (4), имеем: 

|c₁|>|d₁|≥0 

- неравенство нулю первой пары прогоночных коэффициентов, а так же 

                        |δ₁|=|- d₁/ c₁|<1     

    Предположим, что знаменатель (i-1)-x прогоночных коэффициентов не равен нулю и что |δ_i-1|<1. Тогда, используя свойства модулей, условия теоремы и индукционные предположения, получаем: 

            |с_i+b_iδ_i-1|≥|c_i| - |b_iδ_i-1|>|b_i|+|d_i| - |bi|*|δi_-1|= |d_i|+|bi|(1 - | δ_i-1|)> |d_i|>0

а с учетом этого 

                        |δ_i|=|- d_i/ с_i+b_iδ_i-1|=|δ_i|/| с_i+b_iδ_i-1|<|δ_i|/|δ_i|=1     

Следовательно, с_i+b_iδ_i-1 ≠0 и |δ_i|<1 при всех i€{1,2,...,n }, т.е. имеет место утверждаемая в данных условиях корректность и устойчивость прогонки. Теорема доказана.

      Пусть А – матрица коэффициентов  данной системы (1), удовлетворяющих  условиям теоремы, и пусть  

      δ₁= - d₁/ c₁  ,  δ_i=|- d_i/ c_i+b_iδ_i-1    (i=2,3,...,n-1),   δ_n=0

    - прогоночные коэффициенты, определяемые  первой из формул (3), а 

                        ∆_i= с_i+b_iδ_i-1  (i=2,3,...,n)

    - знаменатели этих коэффициентов  (отличные от нуля согласно  утверждению теоремы). Непосредственной  проверкой легко убедится, что  имеет место представление A=LU, где  
 

   c₁  0 0  0  ...  0   0  0              

                  b₂ ∆₂ 0  0  ...  0   0   0                  

               L= 0  b₃ ∆₃ 0  ...  0  0   0                  

                  …………………………      

                  0 0 0 0    ...  b_n-1 ∆_n-1 0              

                  0   0 0   0    ...  0   b_n  ∆_n                      

                        1  -δ₁ 0   0  ...  0    0    0              

                  0   1  δ₂  0  ... 0    0    0                  

               U= 0  0   1   δ₃  ...  0    0    0                  

                  …………………………      

                  0   0   0   0  ... 0   1  -δ_n-1      

                  0   0 0   0  ...  0   0     1                    
 

      Единственное  в силу утверждение теоремы LU-разложения матриц. Как видим, LU-разложение трехдиагональной матрицы А может быть выполнено очень простым алгоритмом, вычисляющем ∆_i δ_i при возрастающих значениях i. При необходимости попутно может быть вычислен

                                                _n

      det A = c₁ ∏ ∆_i .

                       ⁱ⁼² 

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

      5. Решение системы методом прогонки. Код, реализующий метод прогонки

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

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

Поделив первую строку матрицы, приведенной  выше, на -b₁ очевидно, что:

и можно вывести  формулу для прямого хода:

    Затем необходимо выполнить обратный ход - найти вектор X, из последней строки преобразованной матрицы следует, что x_n= Q_n.

В тоже время остальные элементы вектора считаются по формуле:

    Следует заметить, что метод устойчив если(следует из диагонального преобладания матрицы А):

и корректен, если(иначе формулы прямого хода не имеют смысла):

    Ниже  представлен код, реализующий метод  прогонки, принимает трехдиагональную матрицу a размерности N*N, и вектор правых частей b размерности N, результат возвращается в b:

void sweep(double a[N][N],double b[N])

{

int i;

double znam;

b[0]/=a[0][0];//Q₁

a[0][1]/=-a[0][0];//P₁

for(i=1;i < N-1;i++)

{

  znam=-a[i][i]-a[i][i-1]*a[i-1][i]; //общий знаменатель для формул нахождения Pi, Qi

  a[i][i+1]/=znam; //P_i

  b[i]=(a[i][i-1]*b[i-1]-b[i])/znam; //Q_i

}

//строка ниже для вычисления Q_N

b[N-1]=(a[N-1][N-2]*b[N-2]-b[N-1])/(-a[N-1][N-1]-a[N-1][N-2]*a[N-2][N-1]);

 

//обратный ход

 for(i=N-2;i > -1;i--)

{

  b[i]+=b[i+1]*a[i][i+1];

}

return;

}

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

Преобразуем первое уравнение системы к виду , где ,

Подставим полученное выражение во второе уравнение  системы и преобразуем его  к виду и т.д. На i-ом шаге уравнение преобразуется к виду , где , . На m-ом шаге подстановка в последнее уравнение выражения дает возможность определить значение :

. Значения остальных неизвестных  находятся по формулам: , i = m-1, m-2, ..., 1.

Пример 4. Решение системы уравнений методом прогонки.

Прямой  ход прогонки. Вычислим прогоночные коэффициенты:

, ,

,   

, ,

,

Обратный  ход прогонки. Находим значения неизвестных:

, , ,

Ответ:       .

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

    6. Трёхдиагональная матрица (матрица Якоби)

    Трёхдиагональной  матрицей или матрицей Якоби называют матрицу следующего вида:

.

    Системы линейных алгебраических уравнений с такими матрицами встречаются при решении многих задач математики и физики. Краевые условия x₁ и x_n, которые берутся из контекста задачи, задают первую и последнюю строки. Так краевое условие первого рода F(x = x₁) = F₁ определит первую строку в виде C₁ = 1, B₁ = 0, а условие второго рода dF / dx(x = x₁) = F₁ будет соответствовать значениям C₁ = − 1, B₁ = 1.

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

Для решения  систем вида или, что то же самое,

                                                                  (1)

используется  метод прогонки, основанный на предположении, что искомые неизвестные связаны рекуррентным соотношением:

     , где                     (2)

Используя это  соотношение, выразим x_i-1 и x_i через x_i+1 и подставим в уравнение (1):

,

где F_i — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать

Отсюда следует:

Из первого  уравнения получим:

    После нахождения прогоночных коэффициентов  α и β, используя уравнение (2), получим решение системы. При этом,

     

    Другим  способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим  происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению

                    (1')

c надиагональной  матрицей

.

    Вычисления  проводятся в два этапа. На первом этапе вычисляются компоненты матрицы  и вектора , начиная с     до    

      

и