|
А
выражается через элементы мат
рицы
А
следующим образом:
\\А\\с=
шах 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 и не зависит ни от номера итерации
п,
ни от выбора на
чального приближения
Ха,
ни от задаваемой точности е. Качество
различных итерационных методов сравнивают обычно по их скоро
сти сходимости: чем выше скорость сходимости, тем лучше метод.
Do'stlaringiz bilan baham: |
