А. А. Самарский, А. В. Гулин

2. 
Запись разностного уравнения Пуассона в виде системы век­
торных уравнений. 
Пусть в прямоугольнике
G =
(0< х а< 4 , а = 1, 2}
с границей Г требуется найти решение уравнения Пуассона
д2и
дх\
д'2и
дх\
(
2
)
удовлетворяющее условию Дирихле
и(хи х2) = ц (х и х2),
если (х„ хг) е Г .
(3)
Введем прямоугольную сетку
Gh
=
{хц
=
{x'i \
4 я)},
где 
x[l> = ihlt x{f = jh2, i =
0, 1, . . . .
N lt j —
0, 1, . . . ,
Nt, ht
ЛГ, = /„
h2N2 — l2
и заменим задачу (2), (3) разностной схемой 
^ £ - 1 , /
^ У ц
+ P i'- ц , /
| 
V i, f
- 1 
^ £ / " Е ^ £ , / + 1
+
К
— — 
fit
i
‘1 
“2
i = l , 2 ......
N i -
1, / = 1 , 2 ........
N2-
1,
i/о/ 
Ро/, 
UXxi
P^V,/» 
i
 
1 , 2 ,
. . . , 
1
,
У in
== pro, 
yiNi
 == 
Р£Л/г, 
i
;= 
1 , 2 , . . . ,
N,
 
1
.
(4)
(5)
Р азн остн ая схем а (4 ), (5) представляет собой систем у линей­
ных алгебраических уравнений, в которой неизвестными являются 
значения 
yih i = l ,
2, . . . .
—1, / = 1 , 2, . . . ,
Nt-~-
1. Число неиз­
вестных равно числу уравнений, т. е. (Л\—1) 
(N2
—1). Запишем 
систему (4), (5) в векторном виде (1).
412

---

При решении системы (4), (5) матричную прогонку можно про­
водить как по индексу 
1
, так и по индексу /. Покажем, например, 
как подготовить систему (4), (5) к виду (1), удобному для приме­
нения прогонки по индексу i. Перепишем систему (4) в виде
Ус-и 
( 2Ус/ 
(/и -
1
- 2У ц + У
[.,-+1
 
У и и ! 
f
А? 
{
 
а
; 
А* 
)
+
А* 
Л/’
i = l , 2, 
. . . , N - 1 ,
/ = 1, 2, 
. . . , N
2—1
и учтем граничные условия
У
 to == 
У to
, 
У
 i'.v, — p.(V,, 
t = 1 , 2 , . . . , 
1 •
Тогда получим систему уравнений
Ус-
1.1 
/ 2Уп 
- 2i/a +
Ун \ 
У т л
 
г 
ftp
a
; 
I, Л2
, 
Л2 
j 
h\ 
Ы 
h\ ’
«/£_!,/ 
(2 у „
У с, i- i ~ %Уц
+
Уи + 1 \
, 
Уи
 
1
, /
,
“ ч —
------------------- ч ---------------- ) +
ч --------------
/ = 2,3, . .., 
2,
Ус-i.N ^i 
У 
i . Nr-г — ty j.N r-i
а
;
+
Ус+l.Nr
А?
Pi.v,
где i = l , 2, . . . ,
j
V,—1. Далее, обозначим через £ а единичную матри­
цу порядка 
— 1 и через Л2— следующую трехдиагональную ма­
трицу того же порядка
2
1
0 0 •••
1 —2
1 0 •••
•
0
1 —2 0
(
6
)
Ясно, что Л2 представляет собой матрицу оператора второй раз­
ностной производной по направлению 
хг-
Введем для i = 1 , 2 , . . . ,
N
,— 1 векторы
Ус
—
(t/iii 
Усг>
 • ■ 
•» 
yc,Nt-i)T
■>
Fc =
 |7ii + 
, 
f
i
2
» /
1 3
, • ■
 ■
 , /;. 
v
2-
2
, А.
л
/ , - 1
 + 
—
■
(7)
(
8
)
Тогда предыдущую систему уравнений можно записать в вектор­
ном виде
—
Е аУс-1
—
(
—
—
Л 2 ^
yi
-1—
—Eztji+i
=
Fi,
h\ 
U
 
)  
(9 )
i = l , 2, . . . ,
N t— \.
Эту систему уравнений следует дополнить граничными условиями
Уа
 — Ро, 
У if ,
 — Рлт,
413

---

где
P'
0
— (poi, Рог. • • • )
I^O'Nj-i)7,
p.v,— ( P
n
,
i
P
jv
,2
• • • Pjf|,rr2- i ) T- 
Таким образом, разностная схема (4), (5) записывается в век­
торном виде (1), где 
В0
и 
— нулевые 
матрицы, 
A {= B i = h^2E2y
Ci — 2И?Ей
—Л2, 
i = l ,
2, 
. . . ,
Ni—
1.
Может оказаться, что 
N2^>MU
т. е. что число точек сетки по 
направлению х2 гораздо больше числа точек по направлению я, 
(например в случае, когда прямоугольник 
G
сильно растянут в 
направлении 
х2).
Тогда выгоднее пользоваться прогонкой по ин­
дексу /, так как при этом соответствующие матричные коэффициен­
ты будут иметь порядок А,— 1 гораздо меньший, чем 
N 2
—1. Соот­
ветствующая система векторных уравнений имеет вид
~ ~
Е
1
У
1
-
1
—
( ~~ Ei
—
АЛ 
у ,
+ 4 -
Е м +1
= —
F I,
hl
V 
hl 
j
hi
j Г=
1 I 2,. . 
N
2
1 , 
Уд
== P
q
, 
У
jVj == P
j
V
h
где 
E
t— единичная матрица порядка 
—1, Ad— матрица, анало­
гичная (6) и имеющая порядок А,—1,
УI = (У\Ь Уги
•••» 
yNi-i,i)T,
Ро = (Рю> Р
20
» • • • > Рл\—
1
,о)Г|
p,v2 = (PlAf,P
2
jVj . . . Рл',-
1
,Л'г)Г.
3. Алгоритм матричной прогонки. Пусть задана система урав­
нений (1). Формулы матричной прогонки можно получить так же, 
как и формулы обычной прогонки (см. п. 7 § 4 ч. I), однако при 
их выводе надо учитывать, что коэффициенты уравнения (1) непе­
рестановочны. Будем искать решение системы (1) в виде
£/i=ai+1Pi+i + Pi+i, 
i = 0, 1, . . . .
N —
1, 
(10)
где a i+,— квадратные матрицы того же порядка 
М,
что и порядок 
матриц 
A
j, 
Ви Ci,
а р,+1— вектор размерности 
М.
Подставляя у; =
= a i+1(/i+I-t-pi+i и 
y i - i = a iyi + $i=aia,i+lyi+i+
(аф,+1 + Р0 в уравнение
Aiyi-i— Ciyi+Biyi+i= —Fi,
получаем, что это уравнение будет выполнено, если потребовать
(Ада,— С;) a i+1 +
Bi+i
= 0,
(/4;CC;--
Ci)
Pi+1 = --- (AiPi+fj) .
Отсюда приходим к следующим рекуррентным соотношениям 
для определения матриц cci+1 и векторов jii+1:
ai
+1
=
(Ci —
A a £)-1 
В,,
(11)
Pi+i =
(Ci
— 
Aicci)
1 (.4;Pi -j- 
F;).
(12)
Здесь ( = 1 , 2, . . . ,
N
—1. Начальные значения 
a,i
и p, задаются в 
соответствии с уравнением
СоУоА~ ВцУ i = — F ц.
414

---

(1 3 )
которое можно переписать в виде
Уо = Са Вау 1
-|- С0 
F0.
Сопоставляя (13) с уравнением (10) при t = 0, получаем
(14)
После того как все коэффициенты а„ j}f найдены, векторы 
y it
i = N
— 1, (V—2, 
1, 0, определяются последовательно из урав­
нения (10), начиная с 
Для начала счета надо знать вектор 
yN,
который определяется из системы двух уравнений
АкУп
- i 
CNy N
=
F N, Ун-i = {Х,хУн
+
$
n
-
Отсюда получаем
Ук=={Ся A
n

n
)
 _1 (-Лифвг +
Fн) •
 
(15)
Объединяя формулы (10) — (12), (14), (15), приходим к следую­
щему алгоритму матричной прогонки для системы (1):
ai+1 —
 (Ct — Д а £)_1В£) t = 1, 2, . . . , 
N
 — 1, 
а ^ С ^ В ^ ,
 
(16)
IW =
(Ct
-
Atat)-1
 (Л£р£ +
Ft),
i = l , 2,
. . N,
P1=C 71F0, 
(17)
y i= a ,+it/i+i + Pi+i, 
i = N
—1, 
N
—2, . . . , 1,0, 
Уп=$
w+i- 
(18)
При реализации метода матричной прогонки приходится запо­
минать все матрицы оя, 
i = l , 2, . . . ,
N
—1, что ведет в случае 
матриц больших размеров к необходимости использования внеш­
ней памяти ЭВМ и тем самым к увеличению времени счета.
Кроме того, реализация формул (16) сама по себе требует боль­
шого числа действий. В каждой точке 
i
приходится один раз обра­
тить матрицу и сделать два умножения матриц порядка 
М,
что 
требует О (АН) арифметических действий. Следовательно, для вы­
числения всех коэффициентов со, i = l , 2, . . . ,
N
—1, требуется 
0 ( M 3N)
действий. Для модельной задачи, когда 
M = N = h ~ \
число 
действий становится величиной О (Л-4). По указанным причинам 
(большой объем памяти и значительное число арифметических дей­
ствий) матричную прогонку сравнительно редко применяют для 
решения задач математической физики. Однако в тех случаях, 
когда матрицы 
А и Ви Ct
невысокого порядка (небольшое число то­
чек по направлению 
х2),
необходимый объем памяти и число дей­
ствий резко сокращаются и метод можно рекомендовать для прак­
тического использования.
4. Устойчивость матричной прогонки. Так же, как и в случае 
обычной прогонки, возникает вопрос о численной устойчивости ме­
тода матричной прогонки. Получим здесь достаточные условия 
устойчивости в виде требований, предъявляемых к матрицам 
А {, Bit
Си
i= 0 , 1, . . . ,
N.
Пусть в системе (1) 
yt
и / \ — векторы размерности 
М, A it Ви Ct
— 
квадратные матрицы порядка 
М
(векторы и матрицы могут быть 
как вещественными, так и комплексными). Будем рассматривать
415

---

матрицы 
Аи Ви Ci
как линейные операторы, действующие в М-мер- 
ном линейном пространстве 
Н
(вещественном или комплексном). 
Предположим, что в 
Н
определены нормы вектора [Ml и подчинен­
ная ей норма матрицы. При доказательстве устойчивости прогонки 
нам потребуется следующее известное утверждение.
Л е м м а 1. 
Если для данной матрицы А существует константа
Ч>0 
такая, что для любого х ^ Н выполнено неравенство
\\А х\\^\\х\\,
т > 0 , 
(19)
то матрица А имеет обратную, причем
Д о к а з а т е л ь с т в о . Покажем сначала, что все собственные 
числа матрицы 
А
отличны от нуля и, следовательно, существует 
А~‘.
Пусть Я — любое собственное число матрицы 
А
и 
z
— отвечаю­
щий ему собственный вектор, т. е. 
Az="kz.
Согласно условию (19) 
имеем
WAz\\=\K\\\z\\^\\z\\,
т. е. |Я| ^ у > 0 , и тем самым Я=Д0.
Таким образом, матрица 
А
имеет обратную. Пусть 
у ^ Н —
лю­
бой вектор. Обозначая 
х = А ~ 'у ,
получим из условия (19), что 
Следовательно, ||Л-‘|| 
что и требовалось.
Метод прогонки (16) — (18) будем называть устойчивым, если 
матрицы С,—Л,а, имеют обратные и ||а ,||^ 1 , 1= 1, 2, . . . ,
N.
Из устойчивости прогонки следует однозначная разрешимость 
системы (1). Действительно, в этом случае, исходя из рекуррентных 
формул (18), можно представить решение задачи (1) в явной фор­
ме в виде конечной суммы с коэффициентами, зависящими от он,
Условия H aill^l обеспечивают численную устойчивость счета по 
формуле (18). Нарушение этих условий не всегда приводит к силь­
ному накоплению погрешности. Однако подробный анализ вычис­
лительной погрешности метода прогонки выходит за рамки данной 
книги.
Сформулируем теперь теорему об устойчивости матричной про­
гонки.
Т е о р е м а 1. 
Пусть А{,
В,— 
ненулевые матрицы,
1 = 1, 
2, . . .
. . . ,
1
V—
1