Методическое пособие для практических и лабораторных работ по курсу «Численные методы»

140
Лекция 6. Метод прогонки решений СЛАУ с трехдиагональной матрицей.
Устойчивость.
Корректность.
Варианты метода прогонки. Возможность распараллеливания расчетов.
6.1. Метод прогонки решения систем линейных алгебраических
уравнений с трехдиагональной матрицей

Метод прогонки был предложен в начале 50-х годов прошлого века независимо несколькими авторами, в том числе российскими учеными
И. М. Гельфандом, О. В. Локуциевским, В. С. Владимировым, А. С.
Кронродом.
Определение 1. Матрица называется ленточной, если ее элементы
ij
a удовлетворяют условиям
0
=
ij
a
при
j
i
l
−
<
и
m
i
j
>
−
для некоторых неотрицательных чисел l , m .
Если
0
=
m
, то матрица называется левой ленточной матрицей. Если
0
=
l
, то матрица называется правой ленточной матрицей. Величина
1
+
+
m
l
называется шириной ленточной матрицы. Если
1
=
=
m
l
, то матрица называется трехдиагональной.
Рассмотрим систему линейных алгебраических уравнений
b
x
A
r r
=
с трехдиагональной матрицей A . Вводя новые обозначения систему перепишем в виде
1 1
1 0
ν
+
=
y
k
y
,
(
6.1)
i
i
i
i
i
i
i
F
y
B
y
C
y
A
−
=
+
−
+
−
1 1
,
1
,...,
2
,
1
−
=
N
i
,
(
6.2)
2 1
2
ν
+
=
−
N
N
y
k
y
,
(
6.3) где
2 1
2 1
,
,
,
,
,
,
,
ν
ν
k
k
F
B
C
A
i
i
i
i
– заданные числа,
i
y – неизвестные,
N
i
,...,
1
,
0
=
Метод прогонки заключается в следующем. Предполагается, что справедливы рекуррентные соотношения
1 1
1
+
+
+
+
=
i
i
i
i
y
y
β
α
,
1
,...,
2
,
1
,
0
−
=
N
i
,
(
6.4) где коэффициенты
1 1
,
+
+
i
i
β
α
, которые называют
прогоночными
коэффициентами, пока не определены.

141
Для определения
i
α
,
i
β
поступаем следующим образом: выражение
i
i
i
i
y
y
β
α
+
=
−
1
подставляем в (6.2), получаем:
i
i
i
i
i
i
i
i
i
F
y
B
A
y
C
A
−
=
+
+
−
+
1
)
(
β
α

Заменяя здесь
i
y согласно (6.4), имеем
i
i
i
i
i
i
i
i
i
i
i
i
i
F
C
A
A
y
B
C
A
−
=
−
+
+
+
−
+
+
+
1 1
1
)
(
]
)
[(
β
α
β
α
α
(
6.5)
Потребуем, чтобы равенство (6.5) выполнялось при любом
1
+
i
y . Это будет иметь место, если
0
)
(
1
=
+
−
+
i
i
i
i
i
B
C
A
α
α
,
0
)
(
1
=
+
−
+
+
F
C
A
A
i
i
i
i
i
i
β
α
β
(
6.6)

Из (6.6) получаем рекуррентные соотношения для вычисления
i
α
и
i
β
:
i
i
i
i
i
A
C
B
α
α
−
=
+
1
,
1
,...,
2
,
1
−
=
N
i
,
(6.7)
i
i
i
i
i
i
i
A
C
F
A
α
β
β
−
+
=
+
1
,
1
,...,
2
,
1
−
=
N
i
(6.8)

Чтобы организовать счет по формулам (6.7), (6.8), надо знать
1
α
и
1
β
Из (6.1) и (6.4) имеем:
1 1
1 0
β
α
+
=
y
y
,
1 1
1 0
ν
+
=
y
k
y
. Отсюда
1 1
k
=
α
,
1 1
ν
β =
(
6.9)

Уравнения для вычисления прогоночных коэффициентов найдены.
Чтобы организовать счет для вычисления
i
y , надо знать
N
y . Согласно (6.3) и
(6.4)
N
N
N
N
y
y
β
α
+
=
−
1
,
2 1
2
ν
+
=
−
N
N
y
k
y
, отсюда
2 2
2 1
k
k
y
N
N
N
α
β
ν
−
+
=
(
6.10)

Выражения (6.4), (6.7)-(6.10) называют прогоночными формулами.
Коэффициенты
i
α
и
i
β
вычисляют («гонят») слева направо, а
i
y
−
справа налево, поэтому изложенный метод называют методом правой прогонки.

142
Отметим, что при выводе всех формул мы предполагали, что соответствующие знаменатели отличны от нуля. Сейчас покажем, когда это условие выполнено. Предварительно введем определения.
Определение 2. Прогонка называется корректной, если знаменатели в прогоночных формулах не обращаются в нуль.
Определение 3. Прогонка устойчива, если
1
≤
i
α
, для всех
N
i
,...,
1
,
0
=
Лемма. (достаточное условие корректности и устойчивости правой
прогонки). Правая прогонка устойчива и корректна, если:

0
≠
j
A
,
0
≠
j
B
,
j
j
j
B
A
C
+
≥
,
1
,...,
1
−
=
N
j
,
1 1
≤
k
,
1 2
<
k
.

Доказательство. Сначала по индукции докажем, что все
1
≤
i
α
Согласно (6.9) и условия леммы
1 1
1
≤
=
+
k
j
α
. Предположим, что для некоторого номера j
1
≤
j
α
и докажем, что
1 1
≤
+
j
α
. Предварительно рассмотрим выражение
j
j
j
A
C
α
−
Имеем
0
>
≥
−
≥
−
≥
−
≥
−
j
j
j
j
j
j
j
j
j
j
j
j
B
A
C
A
C
A
C
A
C
α
α
α

Поэтому
1 1
≤
−
=
+
j
j
j
j
j
A
C
B
α
α

Тем самым устойчивость доказана. Попутно мы доказали, что знаменатели в формулах (6.7) и (6.8) отличны от нуля. Осталось доказать, что знаменатель в формуле (6.10) отличен от нуля. Действительно
0 1
1 1
1 2
2 2
2
>
−
≥
−
≥
−
≥
−
k
k
k
k
N
N
N
α
α
α
. Корректность доказана. Лемма доказана.
Ранее мы назвали устойчивым метод, в котором не нарастает вычислительная погрешность. Покажем, что данное здесь определение устойчивости прогонки не противоречит данному ранее определению устойчивого метода. Пусть
1
≤
i
α
для всех номеров i . Пусть из-за ошибок округлений реальные вычисления идут по формулам
1 1
1
+
+
+
+
=
i
i
i
i
y
y
β
α
,
)
1
(
,...,
1
,
0
−
=
N
i
(
6.11)

143
Вычислительную погрешность мы внесли в приближенные значения
i
y
. Вычитая (6.11) из (6.4), получаем
1 1
1 1
1 1
1 1
)
(
+
+
+
+
+
+
+
+
−
≤
−
≤
−
==
−
i
i
i
i
i
i
i
i
i
i
y
y
y
y
y
y
y
y
α
α
, т.е.
1
+
∆
≤
∆
i
i
y
y
, а т.к. в правой прогонке предыдущие значения
i
y вычисляются через последующие
1
+
i
y , то последнее неравенство и означает, что вычислительная погрешность не нарастает и прогонка устойчива, согласно данного ранее определения устойчивого метода.
Аналогично выводятся формулы левой прогонки:
1 1
1
+
+
+
+
=
i
i
i
i
y
y
ζ
ξ
,
1
,...,
2
,
1
,
0
−
=
N
i
,
(
6.12)
i
i
i
i
i
B
C
A
1
+
−
=
ξ
ξ
,
i
i
i
i
i
i
i
B
C
F
B
1 1
+
+
−
+
=
ξ
ζ
ζ
,
1
,...,
2
,
1
−
=
N
i
,
(
6.13)
2
k
N
=
ξ
,
2
ν
ζ =
N
,
1 1
1 1
1 0
1
ξ
ζ
ν
k
k
y
−
+
=
(
6.14)

В левой прогонке коэффициенты «гонят» назад, а неизвестные
−
вперед.
Замечание. Нетрудно показать, что прогонка для своей реализации требует порядка
)
(N
O
операций, поэтому прогонка эффективна и
экономична. Стоит отметить, что прогонка – это тот же метод исключения
Гаусса, реализованный специальным образом в случае, когда матрица A – трехдиагональная.
Иногда оказывается удобным комбинировать правую и левую прогонки, получая так называемый метод встречных прогонок. Этот метод целесообразно применять, если надо найти только одно неизвестное, например
m
y (
)
0
N
m
≤
≤
или группу идущих подряд неизвестных.
Получим формулы метода встречных прогонок. Пусть
N
m
≤
≤
1
и по приведенным ранее формулам найдены
m
m
β
β
β
α
α
α
...,
,
,
,
,...,
,
2 1
2 1
и
m
N
N
m
N
N
ζ
ζ
ζ
ξ
ξ
ξ
...,
,
,
,
...,
,
,
1 1
−
−
. Выпишем формулы (6.4) и (6.12) для обратного хода правой и левой прогонок для
1
−
=
m
i
. Получаем систему
m
m
m
m
y
y
β
α
+
=
−
1
,
m
m
m
m
y
y
ζ
ξ
+
=
−
1
, из которой найдем
m
y :

144
m
m
m
m
m
m
y
α
ξ
β
ξ
ζ
−
+
=
1

Используя найденное
m
y , по формулам (6.4) для
0
,...,
2
,
1
−
−
=
m
m
i
найдем последовательно
0 2
1
...,
,
,
y
y
y
m
m
−
−
, а по формулам (6.12) – остальные
N
m
m
y
y
y
...,
,
,
2 1
+
+
Рассмотрим следующую систему
i
i
i
i
i
i
i
f
y
b
y
c
y
a
−
=
+
−
+
−
1 1
,
,
2
,
1
,
0
±
±
=
i
,
(
6.15) коэффициенты и правая часть которой периодичны с периодом N :
N
i
i
a
a
+
=
,
N
i
i
b
b
+
=
,
N
i
i
c
c
+
=
,
N
i
i
f
f
+
=
(
6.16)
К системам (6.15), (6.16) приходят при численном отыскании периодических решений обыкновенных дифференциальных уравнений второго порядка, а также при приближенном решении уравнений в частных производных в цилиндрических и сферических координатах.
При выполнении условий (6.16) решение системы (6.15), если оно существует, тоже будет периодическим с периодом
N
, т.е.
N
i
i
y
y
+
=
(
6.17)
Поэтому достаточно найти решение
i
y , например, при
1
...,
,
1
,
0
−
=
N
i
В этом случае задачу (6.15) – (6.17) удобней записать так:
0 1
0 0
0 1
0
f
y
b
y
c
y
a
N
−
=
+
−
−
,
0
=
i
,
i
i
i
i
i
i
i
f
y
b
y
c
y
a
−
=
+
−
+
−
1 1
,
1 1
−
≤
≤
N
i
,
0
y
y
N
=
(
6.18)
Для нахождения решения системы (6.18) построен вариант метода прогонки, который называется методом циклической прогонки. Подробно останавливаться на расчетных формулах этого метода не будем, отсылая читателя к соответствующей литературе [19,22]. Отметим также, что разработаны метод немонотонной прогонки – аналог метода Гаусса с выбором главного элемента для систем с трехдиагональной матрицей, метод

145
прогонки для систем с пятидиагональной матрицей, метод матричной прогонки [19].
Рассмотрим частный случай исходной задачи (6.1) – (6.3)
1 1
f
y
=
,
i
i
i
i
i
i
i
f
y
b
y
c
y
a
=
+
−
+
−
1 1
,
1 2
−
≤
≤
N
i
,
N
N
f
y
=
,
(
6.19) здесь для удобства нумерацию неизвестных ведем с единицы и немного изменили обозначения правых частей уравнений.
Теорема 1. Пусть в (6.19)

0
>
i
a
,
0
>
i
b
,
ε
+
+
>
i
i
i
b
a
c
,
0
>
ε
.
(
6.20)

Тогда







≤
i
i
n
i
f
f
f
y
max
1
,
,
max
1
ε

(
6.21)

Доказательство. Заметим, что если
i
y есть решение задачи (6.19), то
(
i
y
−
) является решением задачи
1 1
)
(
f
y
−
=
−
,
i
i
i
i
i
i
i
f
y
b
y
c
y
a
−
=
−
+
−
−
−
+
−
)
(
)
(
)
(
1 1
,
1 2
−
≤
≤
N
i
,
N
N
f
y
−
=
−
)
(
(
6.22)
Поэтому, если для решения задачи (6.19) установлена оценка






≤
i
i
N
i
f
f
f
y
max
1
,
,
max
1
ε
,
(
6.23) то для решения задачи (6.22) будет справедлива оценка






−
−
−
≤
−
i
i
N
i
f
f
f
y
max
1
,
,
max
1
ε
(
6.24)
Оценки (6.23) и (6.24) дают оценку (6.21). Следовательно, все сводится к установлению справедливости (6.23). Пусть
m
y – наибольшее из
N
y
y ,...,
1

146
Если
0
<
m
y
, то (6.23) очевидно. Столь же очевидно (6.23) и при
1
=
m
,
N
m
=
. Остается рассмотреть случай
0
≥
m
y
и
1
≠
m
,
N
m
≠
. Но тогда
m
m
m
m
m
m
m
m
m
m
m
m
y
y
c
b
a
y
b
y
c
y
a
f
ε
−
≤
−
+
≤
+
−
=
+
−
)
(
1 1
, что и доказывает (6.23).
Теорема доказана.
Отметим следующее. Если в (6.19)
0
=
i
f
,
N
i
,...,
1
=
и выполнены условия диагонального преобладания (6.20), то в силу (6.21)
0
=
i
y
,
N
i
,...,
1
=
С другой стороны, поскольку однородная (
0
=
i
f
) задача (6.19), (6.20) имеет только нулевое решение, неоднородная (
0
≠
i
f
) задача (6.19), (6.20) разрешима и решение ее единственно. Следовательно, определитель системы линейных алгебраических уравнений (6.19) при условиях (6.20) отличен от нуля.
Пусть
i
f в задаче (6.19) заданы с некоторой погрешностью
i
f
∆
. Тем самым решение задачи (6.19) определяется с некоторой погрешностью
i
y
∆
Очевидно (в силу линейности), что
1 1
f
y
∆
=
∆
,
i
i
i
i
i
i
i
f
y
b
y
c
y
a
∆
=
∆
+
∆
−
∆
+
−
1 1
,
1 2
−
≤
≤
N
i
,
N
N
f
y
∆
=
∆
(
6.25)
Если выполнены условия (6.20), то из (6.25) вытекает, что






∆
∆
∆
≤
∆
i
i
N
i
f
f
f
y
max
1
,
,
max
1
ε
(
6.26)
Следовательно, если для задачи (6.19) справедлива оценка (6.26), то естественно говорить об устойчивости решения задачи (6.19) по правой
части.
В заключение рассмотрим алгоритм решения задачи (6.1) – (6.3), основанный на принципе суперпозиции. Для упрощения изложения рассмотрим частный случай этой задачи, а именно задачу (6.19).
1 1
f
y
=
,
i
i
i
i
i
i
i
i
f
y
b
y
c
y
a
Ly
=
+
−
=
+
−
1 1
,
1 2
−
≤
≤
N
i
,
N
N
f
y
=
(
6.27)
Теорема 2. Пусть задача (6.27) однозначно разрешима. Пусть
i
u ,
i
v
и
i
w есть решения задач

147 0
=
i
Lu
,
1 1
=
u
,
0
=
N
u
;
0
=
i
Lv
,
0 1
=
v
,
1
=
N
v
;
i
i
f
Lw
=
,
0 1
=
w
,
0
=
N
w
;
(
6.28)

Тогда решение задачи (6.27) дается формулой

i
i
N
i
i
w
v
f
u
f
y
+
+
=
1

(
6.29)
Доказательство. Из (6.29) следует, что
i
i
i
N
i
i
f
Lw
Lv
f
Lu
f
Ly
=
+
+
=
1
Кроме того
1 1
1 1
1
f
w
v
f
u
f
y
i
N
=
+
+
=
,
N
N
N
N
N
N
f
w
v
f
u
f
y
=
+
+
=
1
Теорема доказана.
В этой теореме применительно к задаче (6.27) сформулирован известный принцип суперпозиции: общее решение линейной неоднородной
(
0
≠
i
f
) задачи есть сумма общего решения однородной (
0
=
i
f
) задачи и частного решения неоднородной задачи.
Замечание. Для эффективного использования многопроцессорных вычислительных систем требуются алгоритмы, допускающие распараллеливание. Как отмечено в книге [12] в основу параллельных алгоритмов метода прогонки может быть положен принцип суперпозиции
(6.28), (6.29). Действительно, каждая задача в (6.28) может решаться независимо от других задач, одновременно с ними, каждая – на своем процессоре. Точно так же и определение
i
y из (6.29) может производиться одновременно на нескольких процессорах для различных значений i .

148
Лекция 7. Итерационные методы.
Стационарные.
Нестационарные. Теоремы сходимости. Метод Якоби. Метод
Гаусса-Зейделя. Каноническая форма итерационных методов.
Сходимость.

Скачать 1.29 Mb.

Поделитесь с Вашими друзьями: