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

UptoLike

ВУЗ: 

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

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

Рубрика: 

1.4 Метод прогонки
Он является модификацией метода Гаусса для частного случая разреженных систем — системы уравнений с
трехдиагональной матрицей. Такие системы получаются при моделировании некоторых инженерных задач, а
также при численном решении краевых задач для дифференциальных уравнений.
Запишем систему уравнений в виде
11 12 1
21 2 2 23 2
32 33 34 3
12 11 1 1
1
,
,
,
.................................
,
.
n
nn nn nn n
nnnn
bx cx d
ax bx cx d
ax bx cx d
ax bx cx d
ax bx d
−− −− − −
−
+=
++ =
++ =
++=
+=
(5.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.
iii i
xAx Bi n
+
=
+= −
(5.14)
Из первого уравнения системы (5.13) найдем
11
12
11
.
cd
xx
bb
=− +
(5.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)
212 1 22 23 2
() .aAx B bx cx d
+
++=
Выразим отсюда x
2
через
x
3
:
23 2 2 1
2
21 2
,
cx d aB
x
aA b
−
+−
=
+
(5.16)
или
2232
2221
22 2212
22
,
,,.
xAxB
cdaB
A
BeaAb
ee
=+
−
=− = = +
Аналогично можно вычислить прогоночные коэффициенты для любого номера i:
1
1
,,
, 2,3,..., 1.
iiin
ii
ii
iii i
cdaB
AB
ee
eaA bi n
−
−
−
=− =
=
+= −
Обратная прогонка состоит в последовательном вычислении неизвестных х
i
. Сначала нужно найти х
n
. Для
этого воспользуемся выражением (5.14) при i=n-1 и последним уравнением системы (5.13). Запишем их:
11 1
1
,
.
nnnn
nn nn n
x
Ax B
ax bx d
−
−−
−
+
+=
Отсюда, исключая x
n-1
, находим
1
1
.
nnn
n
nnn
daB
x
baA
−
−
−
=
+
Далее, используя формулы (5.14) и вычисленные ранее по формулам (5.15), (5.16) прогоночные
коэффициенты, последовательно вычисляем все неизвестные x
n-1
, x
n-2
, …, x
1
Алгоритм решения системы
линейных уравнений вида (5.13) методом прогонки представлен на рисунке 5.3.

Страницы