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

А
выражается через элементы мат­
рицы 
А
следующим образом:
\\А\\с=
шах 2 К | -
/=1
Докажем это утверждение. Для любого вектора 
х
справедливо неравенство
Ах ||с = шах
», е.
2
ач xi
SI max 
| 
х 
- | max 2 \ a,, | =
IS /S"! 
1
IS'S'7! 
I_x
=
max
2
K /l II* lb 
l iS'S”i .
l=i
шах 
2 K /l II*Нс-
' 
1 
»
(7)
i=i
91

---

Ч т о б ы
з а в е р ш и т ь
д о к а з а т е л ь с т в о , 
д о с т а т о ч н о
п о с т р о и т ь
в е к т о р
= (* J , 
.............* т ) Г > д л я к о т о р о г о в ы п о л н я е т с я р а в е н с т в о
I! 
Ахо
 11с = ( "lax S I 
aii
U II*0 lie
/=1
J
П у с т ь ф у н к ц и я
in
Фг =
2
I 
аи
I’ 
i =
1
.
2
,
/=1
д о с т и г а е т м а к с и м у м а п р и
i=kt
т . e .
m 
in
ш а х
V | A y | =
2
I « * / I-
l- 1
 
.
/=1
 
1=1
Р а с с м о т р и м в е к т о р
Xo,
и м е ю щ и й к о о р д и н а т ы
x„ _ l
 
!■ 
е с л и а Л/. > 0 ,
1
 
I — 1, е с л и
akl-
< 0 .
О ч е в и д н о , ч т о ll-^oll с = 1- О ц е н и м с н и з у в ы р а ж е н и е д л я 1 И * о ||с . И м е е м
1 
Аха
||с = ш а х
l^i^m
m
m
2
ачх)
>
2
аыА
i=i
1=1
*0 =
(
8
)
О)
(Ю)
Д а л е е , и с х о д я и з о п р е д е л е н и я ( 1 0 ) в е к т о р а
xq
,
п о л у ч и м
и, с л е д о в а т е л ь н о ,
т
2
V i
i
=
i
т
т
2
% - * ° = 2
/= 
1
/= 
1
т
т
и 
Ахо
Не >
2
I 
aki
I = тах 
2
I ai
/ 1
•
■
l^i

/=1
/=1
П о с л е д н е е р а в е н с т в о с п р а в е д л и в о в с и л у ( 9 ) . Т е м с а м ы м н а ш л и в е к т о р
xQt
д л я к о т о р о г о
т
l Axo\\>
m a x
Y
К / I Их ° Нс
1
.
/=1
П о с к о л ь к у д л я к а ж д о г о в е к т о р а
х
с п р а в е д л и в о п р о т и в о п о л о ж н о е н е р а в е н ­
с т в о ( 7 ) , з а к л ю ч а е м , ч т о д л я
ха
с п р а в е д л и в о р а в е н с т в о ( 8 ) .
3. 
Теорема о сходимости итерационного метода. Справедлива 
Т е о р е м а 1. 
Итерационный метод
(3) 
сходится при любом
начальном приближении тогда и только тогда, когда все собствен­
ные значения матрицы S = E
—т
В~1А по модулю меньше единицы.
Д о к а з а т е л ь с т в о . Представим уравнение (4) для погреш­
ности ц„=хп—
х
в виде (5) — (
6
). Докажем сначала необходимость 
условий теоремы 
1. 
Предположим, что матрица 
5
имеет 
собствен­
ное число 
s,
для которого | s | > l , и покажем, что в этом случае 
можно так подобрать начальное приближение 
х0,
чтобы погреш­
ность 
vn = xn—х
неограниченно возрастала при /г-*-оо. Пусть р — 
собственный вектор матрицы 
S,
отвечающий собственному числу
92

---

s, | s | > l . Возьмем в качестве начального приближения вектор 
*0
= х+|х, так что начальная погрешность и
0
= р,. Тогда из уравне­
ния (5) получим
ц„ 
= S nv0
= s"u
0
= S"|X
и ||и„||'= |s|"||p||->oo при 
п-*-о
о. Если | s | = 1, то ЦиГ1|| = ||[х||т^О при 
П
—>-оо.
Доказательство достаточности условий теоремы 
1
проведем 
сначала в предположении, что матрица S имеет 
т
линейно неза­
висимых собственных векторов. Пусть 
sk, k = \ ,
2, ..... m,— собст­
венные числа матрицы S и 
6= 1, 2, 
т
,— отвечающие им 
линейно независимые собственные векторы. Разложим начальную 
погрешность 
va = x0—х
по векторам р*:
Тогда получим
vo
— 
2
k—i
т
y„ = S”y
0
=
2
ckSn
kVk.
k=i
В любой норме справедлива оценка
1
М ^ р
п2
1
^
11
! п* II. 
(П)
Й
=1
где р = max | s* | —спектральный радиус матрицы S. Из оценки
(
1 1
) в силу предположения теоремы 
1
о том, что р <
1
, и следует 
сходимость метода.
4. 
Продолжение доказательства. В общем случае, когда систе­
ма собственных векторов матрицы S не является полной, доказа­
тельство достаточности условий теоремы 
1
проводится с помощью 
приведения S к жордановой форме. Напомним (см. [12], стр. 147), 
что для любой квадратной матрицы S порядка 
т
существует невы­
рожденная матрица 
Р
такая, что матрица 
5 = P~lSP
имеет жорда- 
нову каноническую форму
г *
0 
. . . 0 '
5 =
0
S ,  . . . 0
0
0 . •
где 
Sk
либо собственное число матрицы S, либо жорданова клетка, 
т. е. матрица вида
г®*
1
0 0
. . 
0
-1
0
sk
1 0
. . 
0
Sk =
0 0 0 0
. . 
1
Lo
0 0 0
.
Sk
J
a 
sk
— собственные числа матрицы S.
93

---

Помимо обычной жордановой формы нам потребуется еще так 
называемая модифицированная жорданова форма матрицы S. 
Она строится следующим образом.
Применим к матрице 
S
преобразование подобия 
D~lSD
с диа­
гональной матрицей Z) = diag[l, е, 
ет“']> где е — любое поло­
жительное число. Нетрудно убедиться, что матрица
S = D-
имеет ту же блочно-диагональную структуру, что и матрица 
S,
однако жордановы клетки имеют теперь следующий вид:
Г 5/0
е
0
0 .
. о -
0
ч
£
0 .
. 0
& =
0
0
0
0 .
. Б
L o
0
0
0 .
S* J
Матрицы S и S связаны равенством
S = Q-
1
SQ, 
Q = PD.
(
12
)
Матрица S имеет в каждой строке не более двух отличных от нуля 
элементов, поэтому
|] 5 ||с ^ р (5) + е, 
(13)
где p(S) — спектральный радиус матрицы S, т. е.
p(S) = max |
Sk\.
l
Напомним, что согласно (10) из § 
6
гл. 1 подчиненная норма 
матрицы удовлетворяет неравенству
IIS ||> p(S ). 
(И )
Покажем теперь, что можно найти такую норму вектора, для 
которой подчиненная норма матрицы станет сколь угодно близкой 
к ее спектральному радиусу. Точнее, справедливо следующее 
утверждение.
Л е м м а 1. 
Д л я любого
е > 0
существует норма
||-||, 
вектора
такая, что для подчиненной нормы матрицы справедливо неравен'
ство
||iS ||.^p (S )+ e. 
(15)
Д о к а з а т е л ь с т в о . Воспользуемся преобразованием (12) и 
определим норму вектора ||-|
1
* равенством
11г/||.= [IQ~'«/llc
для любого вектора г/еЯ . Для подчиненной нормы 
имеем
Sy
II
! ^ «*= sup
Уго
|| 
У
WQ-'SyWc
sup---------- .
уфо
II
Q 1У
11с
матрицы S
94

---

Обозначая 
Q~ly = x
и учитывая (12), (13), получим отсюда
И
 
Q~lSQx ||с
sup-----------
II 
х
11
с
tS x  ||с
sup------
^ 0
I* He
= IS ||c ^ p (5) + e,
что и требовалось.
Завершим доказательство теоремы 1. Из уравнения (5) полу­
чим
vn = S nv0, 
п =
0 , 1 , . . .
(16)
Пусть ||-Ц* — норма, для которой выполнено неравенство (15). 
По условию теоремы p ( S ) d , поэтому существует е > 0 такое, что 
||5 ||.^ p ( S ) + е ^ <
7
< 1. Из (16) получим оценку
|ил|.^ ||5 |П к 1 1 ^ < р |К 1 .. 
(17)
из которой следует, что ||и
„||,-»-0
при любых начальных приближе­
ниях.
§ 4. Оценки скорости сходимости 
стационарных итерационных методов
1
. 
Скорость сходимости итерационного метода. При практиче­
ском использовании итерационных методов важен не только сам 
факт сходимости, но и скорость, с которой приближенное решение 
сходится к точному. Так как при численном решении всегда осу­
ществляется конечное число итераций, необходимо знать, во сколь­
ко раз уменьшается начальная погрешность после проведения за­
данного числа итераций. Ответить на эти вопросы позволяет ана­
лиз оценок погрешности итерационного метода.
В предыдущем параграфе при доказательстве теоремы 1 была 
получена оценка (17), которую можно переписать в виде
\\хп—
x l ld ^ l U n —-VIU, 
п =
0
, 
1
, . . . ,
(
1
)
где <
7
g
(0, 1). Если для погрешности итерационного метода выпол­
няются оценки вида (
1
), то говорят, что метод сходится со ско­
ростью геометрической прогрессии со знаменателем 
q.
Используя оценку (1), можно определить число итераций, до­
статочное для того, чтобы начальная погрешность уменьшилась в 
заданное число раз. Действительно, зададим произвольное е > 0
и потребуем, чтобы 
qn
т. е. чтобы
п > п 0
(s) = | - (1/е) . 
(
2
)
Ь (1/9)
Тогда из (1) получим, что
\\хп—
х||,С е||*о—*
11
'.,
т. е. после проведения п
0
(е) итераций начальная погрешность 
||*о—*11. уменьшилась в е
-1
раз. Целая часть числа п
0
(е) называ­
ется 
минимальным числом итераций, необходимым для получения
заданной точности
е.
0S

---

Выражение 1п(1/у), находящееся в знаменателе числа га
0
(е), 
называется 
скоростью сходимости итерационного метода.
Ско­
рость сходимости целиком определяется свойствами матрицы пе­
рехода 5 и не зависит ни от номера итерации 
п,
ни от выбора на­
чального приближения 
Ха,
ни от задаваемой точности е. Качество 
различных итерационных методов сравнивают обычно по их скоро­
сти сходимости: чем выше скорость сходимости, тем лучше метод.