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

 

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

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

                                                     (6.1)

Говорят, что система имеет трех диагональную структуру. Рассмотрим ее векторно матричное представление:

 

.

 

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

 

,                                                        (6.2)

di, li - некоторые числа. При этом уравнение преобразуется в уравнение, содержащее две переменных. Уменьшив в (6.2) индекс на единицу и полученное выражение , подставим в уравнение (6.1) получим:

откуда

.

Последнее равенство совпадает с равенством (6.2), если выполняются рекуррентные соотношения:

.                                                  (6.3)

Так как , то процесс вычисления di, li можно начать со значений

                                                               (6.4)

и продолжаться по формулам (6.3) последовательно при i = 1,2,…, n.При i = n ,в силу dn = 0, получим dn = 0. Следовательно, полагая в (6.3) i = n, будем иметь

                                                         (6.5)

(где dn-1, ln-1 - известны на предыдущем шаге). Далее по формулам (6.3) при последовательно находим xn-1, xn-2,…, x1 при i = n -1, n - 2,…,1.

Таким образом, решение СЛАУ (6.1) сводится к вычислению так называемых прогоночных коэффициентов по формулам (6.3), (6.4) (прямая прогонка). Затем получаются значения неизвестных по формулам (6.2) - обратная прогонка. Описанный метод решения системы (6.1) называется методом прогонки.

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

Прогонку называют корректной, если знаменатели прогоночных коэффициентов (6.3) не обращаются в ноль, и устойчивой, если |di| < 1при всех i = 1,2,…, n.

Имеет место теорема:

Теорема 6.1. Пусть коэффициенты bi и di, i = 2,3,…, n-1, в СЛАУ (6.1) отличны от нуля и пусть

 | ci |>|bi| + |di|; i = 1,2,…, n.                                                (6.3)

Тогда прогонка корректна и устойчива (т.е. ci + bidi-1 ¹ 0, li li li |di| < 1).

Алгоритм решения СЛАУ методом прогонки.

Ввод: трехдиагональная A[i,j] порядка n, матрица B[i].

Вывод: матрицу x[i] решения системы.

D[1]:= - A[1,2]/ A[1,1]; L[1]:= - B[1]/ A[1,1];

Цикл по i: = 2, …,n выполнять D[i]:= - A[i,i+1]/ (A[i,i]+ D[i-1]* A[i,i-1]); L[i]:= (B[i]- A[i,i-1]*L[i-1])/ (A[i,i]+ D[i-1]* A[i,i-1]); конец цикла по i;

X[n]:= L[n];

Цикл по i: = n-1,…,1 выполнять X[i]:= D[i1]*X[i+1]+L[i]; конец цикла по i;

Конец.

Ручное вычисление. При ручном вычислении результаты удобно записывать в таблицу. Числа di, li вычисляются сверху вниз по формулам (6.4), (6.3) (прямой ход). Неизвестные xi - по формулам (6.5), (6.2) (обратный ход).

 

i - уравнение

bi

ci

di

ri

di

li

xi

1

2

n

b1=0

b2

bn

c1

c2

cn

d1

d2

dn=0

r1

r2

rn

d1

d2

dn

l1

l2

ln

x1

x2

xn

 

Пример. Методом прогонки решить систему

 

.

 

i - уравнение

bi

ci

di

ri

di

li

xi

1

2

3

 -

-2,3

5,1

1,2

7,2

11,2

2,3

5,4

-

6,1

8,6

8,2

-1,917

0,465

0

5,083

1,734

-0,047

1,910

1,655

-0,047

 

Ответ: (1,91; 1,65; -0,05)