Магнитогорский Государственный Технический Университет имени Г.И.Носова
Кафедра математики
Реферат
Тема: Метод прогонки решения систем с трехдиагональными

матрицами коэффициентов
Выполнил:      студент группы ЭА-04-2

Романенко Н.А.
Проверил:        Королева В.В.
Магнитогорск 2004


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

Рассмотрим наиболее простой случай ленточных систем, к которым, как увидим впоследствии, сводится решение задач сплайн-интерполяции функций, дискретизации краевых задач для дифференциальных уравнений методами конечных разностей, конечных элементов и др. А именно, будем искать решение такой системы, каждое уравнение которой связывает три “соседних” неизвестных:
                            b_ix_i
-1
+
c_ix_i
+
d_ix_i
=
r_i
                                       
         (1)
где i=1,2,...,n; b
₁
=0, d_n
=0. Такие уравнения называются трехточечными разностными уравнениями второго порядка. Система (1) имеет трёхдиагональную структуру, что хорошо видно из следующего, эквивалентного (1), векторно-матричного представления:
                                              

                                   c₁  d₁ 0  0  ...  0   0   0                   x₁                    r₁

                                   b₂  c₂ d₂ 0  ...  0   0   0                   x₂                    r₂ 

                                   0  b₃  c₃  d₃ ...  0   0   0                   x₃                             r₃         

                                   .   .   .    .    ...   .   .   .            *       ...          =        ...    

                                   0  0  0  0    ...  b_n-1
c_n-1
d_n-1                   x_n-1                            
r_n-1

                                   0  0  0  0    ...  0   b_n   
c_n                        
x_n                            
 
 r_n

            Как и в решении СЛАУ методом Гаусса, цель избавится от ненулевых элементов в поддиаганальной части матрицы системы, предположим, что существуют такие наборы чисел δ_i
и λ
_i
(
i
=1,2,...,n
), при которых
                                      x_i=
δ
_i
x_i+1+
λ
_i
                                                                 (2)
т.е. трехточечное уравнение второго порядка (1) преобразуется в двухточечное уравнение первого порядка (2). Уменьшим в связи (2) индекс на единицу и полученое выражение x_i
-1
= δ
_i
-1
x_i
+ λ
_i
-1
подставим в данное уравнение (1):
                                      b_iδ_i-1 x_i+ b_i λ_i-1
+ c_ix_i+ d_ix_i+1= r_i      

откуда

                                      x_i= -((d_i /( c_i+ b_iδ_i-1)) x_i-1+(r_i - b_i λ_i-1)/( c_i - b_i δ_i-1)).
Последнее равенство имеет вид (2) и будет точно с ним совпадать, иначе говоря, представление (2) будет иметь место, если при всех i
=1,2,…,
n
выполняются рекуррентные соотношения
                                     δ_i = - d_i /( c_i+ b_iδ_i-1) ,   λ _i=(r_i - b_i λ_i-1)/( c_i - b_i δ_i-1)           (3)
Легко видеть, что, в силу условия b
₁
=0, процесс вычисления δ_i
, λ_i
 может быть начат со значений

        

                                      δ₁ = - d₁/ c₁ ,         λ₁
=

r₁/
c₁
и продолжен далее по формулам (3) последовательно при i
=2,3,...,
n, причем при i
=
n
, в силу d_n
=0, получим δ_n
=0.Следовательно, полагая в (2) i
=
n,будем иметь
                                      x_n = λ_n
= (r_n – b_n λ_n-1)/( c_n – b_n δ_n-1)
(где λ_n
-1
, δ
_n
-1
– уже известные с предыдущего шага числа). Далее по формулам (2) последовательно находятся x_n
-1
, x_n
-2 ,…, x
₁ при i
=
n
-1,
n
-2,...,1 соответственно.

         Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки, сводится к вычислениям по трём простым формулам: нахождение так называемых прогоночных коэффициентов δ_i
, λ_i
  по формулам (3) при i
=1,2,…,
n
(прямая прогонка) и затем неизвестных x_i по формуле (2) при i
=
n
-1,
n
-2,...,1 (обратная прогонка).

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

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

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

        

Пусть коэффициенты
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) для систем с трехдиагональными матрицами (левая прогонка, встречная прогонка, немонотонная, циклическая, ортогональная прогонки и т.д.), так и для более сложных систем с матрицами ленточной структуры или блочно-матричной структуры (например, матричная прогонка).


Список используемой литературы
В.М. Вержбитский «Численные методы. Линейная алгебра и нелинейные уравнения», Москава «Высшая школа 2000».