Краткий курс вычислительной математики. Денисова Э.В - 56 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

1.4 Метод прогонки
Он является модификацией метода Гаусса для частного случая разреженных систем — системы уравнений с
трехдиагональной матрицей. Такие системы получаются при моделировании некоторых инженерных задач, а
также при численном решении краевых задач для дифференциальных уравнений.
Запишем систему уравнений в виде
11 12 1
21 22 23 2
32 33 34 3
12 11 1 1
1
,
,
,
.................................
,
.
n
nn nn nn n
n nn n
bx cx d
ax bx cx d
ax bx cx d
ax bx cx d
ax bx d
−− −− − −
−
+=
++ =
++ =
+ +=
+=
(4.13)
На главной диагонали матрицы этой системы стоят элементы b
1,
b
2
, ..., b
n
, над ней — элементы с
1,
с
2
, ..., с
n-1
под ней — элементы а
2
, а
3
, ..., а
n
. (при этом обычно все коэффициенты b
i
не равны нулю.
Метод прогонки состоит из двух этапов — прямой прогонки (аналога прямого хода метода Гаусса) и
обратной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в вычислении
прогоночных коэффициентов A
i,
В
i,
с помощью которых каждое неизвестное x
i
выражается через x
i+1
:
1
, 1,2,..., 1.
i ii i
x Ax B i n
+
= += −
(4.14)
Из первого уравнения системы (5.13) найдем
11
12
11
.
cd
xx
bb
=−+
(4.15)
С другой стороны, по формуле (5.14) x
1
=A
1
x
2
+ B
1
. Приравнивая коэффициенты в обоих выражениях для х
1
получаем
11
11
11
,.
cd
AB
bb
=−=
Подставим во второе уравнение системы (5.13) вместо x
1
его выражение через x
2
по формуле (5.14)
2 12 1 22 23 2
() .a Ax B bx c x d++ + =
Выразим отсюда x
2
через
x
3
:
23 2 2 1
2
21 2
,
cx d aB
x
aA b
− +−
=
+
(4.16)
или
2 23 2
2 2 21
2 2 2 21 2
22
,
, ,.
x Ax B
c d aB
A B e aA b
ee
= +
−
=−= =+
Аналогично можно вычислить прогоночные коэффициенты для любого номера i:
1
1
,,
, 2,3,..., 1.
i i in
ii
ii
i ii i
c d aB
AB
ee
e aA b i n
−
−
−
=−=
= += −
Обратная прогонка состоит в последовательном вычислении неизвестных х
i
. Сначала нужно найти х
n
. Для
этого воспользуемся выражением (4.14) при i=n-1 и последним уравнением системы (4.13). Запишем их:
Отсюда, исключая x
n-1
, находим
1
1
.
n nn
n
n nn
d aB
x
b aA
−
−
−
=
+
Далее, используя формулы (5.14) и вычисленные ранее по формулам (5.15), (5.16) прогоночные
коэффициенты, последовательно вычисляем все неизвестные x
n-1
, x
n-2
, …, x
1
Алгоритм решения системы
линейных уравнений вида (5.13) методом прогонки представлен на рисунке 5.3.
55

Страницы