Ускорение сходимости итерационных процессов по Эйткену (? 2 -процесс).

X ( k ?1) ?CX ( k ) ? F
Пусть, для простоты
X ?- точное решение.
n

X ( 0 ) ? X ? ?? ? i ei
i ?1

если C ?1 , то итерации сходятся медленно.
( С имеет размерность n x n )

1 ? ?1 ? C ? ? ?2 ?... ? ?n

?

?

X ( k ) ? X ? ?C k X ( 0 ) ? X ? .

?C k (слева умножаем!);
(

ei

- собственные вектора)

k
k
?
?
? e?
?
e
?
?
Используем утверждение:

?

X

(k )

n

?

? X ? ? ?ki? i ei ? X 1( k ) ? X 1? ,..., X n( k ) ? X n?
?

i ?1

?

- вектор ошибки.

k
k
? ? ? ? ?k e
?
?
?
?
?
?
?
?
?
e
?
(k )
?
k
k
2
2
2
l
n
n
nl
2
? ?? ? e ? O ?? ? ?
X e ? X e ??1?1 e1l ?1 ? ?? ??
? ... ? ?? ??
1 1 1l
?? ?
? ?1 ? ?1 ? e1l
?1 ? ?1 ? e1l ?
?
?
?
?? 1 ? ??
k

? ?2 ?
?? ?? - стремится к 0 приk ? ?
? ?1 ?

k

? ?n ?
?? ?? - стремится к 0 при k ? ?
? ?1 ?

X L( K ) ? X L( K ? 1)

?1 , ?1 , e1l - неизвестные l ?1, n
? X l( k ? 1) ? X ? ??1?1( k ? 2 )e1l
? ( k ? 1)
(k )
( k ? 2)
( k ? 1) 2
( k ? 1) 2
? ? X l ? X ? ??1?1k ? 1e1l
?
?
X
?
X
?
(
X
)
?
X
?
(k )
(k )
l
l
l
l
X ?U l ? ( k )
? X l ? 2 ( k ? 2)
?
( k ? 1)
( k ? 2)
? (k )
?
k
Xl ? 2Xl
? Xl
? Xl
? X l ? X ??1?1 e1l

?U ?

(k )
l
l ?1, n

- эту последовательность строим!

l ?1, n

От ? 2 - название процесса.
Скорость сходимости определяется |?2|, т.е. процесс сходится
быстрее, чем базовый итерационный.

Решение плохо обусловленных систем.

C ( A)
???
число обусл. системы

?

A

?1

x

?b

?

?1

A ?A
? ? ? ??

, C(A)>>1

число обусл. матрицы

Погрешность данных (A и B) сильно влияет на результат.
Существует множество способов решения плохо обусловленных систем (см.
спец. литературу, например Крылов В.И., Бобков В.В., Монастырный П.И.
“Начала теории вычислительных методов” 3-и книги, Минск, Наука и техника,
1982, 1983, 1984 г.г.)

?
?
Один из них: Ax ?b ? ? ?(Ax - b)(Ax - b)dx ? ?( Ax * ? b, Ax * ? b) ?0
?x
? для точного решения x*
Доп. условие – min отклонение
решения от некоторого заданного x0,
т.е.

( x ? x0 , x ? x0 ) ? min

( Ax ? b, Ax ? b) ?0
при учёте погрешности A и B
(при реальных, не точных
значениях A и B и точном x*)

Следовательно возникает новая, регуляризованная задача:

( Ax ? b, Ax ? b) ? ? ( x ? x0 , x ? x0 ) ? F ( x) ? min , ? ? 0
- этот переход сделать самостоятельно

( x, A* Ax) ? 2( x, A*b) ? (b, b) ? ? ? ( x, x) ? 2( x, x0 ) ? ( x0 , x0 )? ?F ( x,? ) ? min,
A*-сопряжённая матрица:aik* ?aki , “?“-комплексное сопряжение
Утв.(без доказательства): для Ax=b в гильбертовом пространстве,
где А - линейный, самосопряжённый, положительно определённый оператор,

F ( x) ? ( Ax, x) ? 2( x, b) ?min
? ? ? ? ? ??

при x=x* , где x* - решение Ax=b.

энергентич еский функционал

F ( x, ? ) ?min
( A * A ? ?E ) x ? A * b ? ? x 0

Из этого утверждения следует, что
если х есть решение уравнения

Следовательно, x=x(?) -параметрическое решение.

Имеем две проблемы:
•x0-? – выбор из доп. информации, в противном случае x0?0
•?=0 Ax=b
?>>0 x(?) не близко к x* => min ? определяется из условия
*

C ( A A ? ?E ) ?1
? ? ?? ? ??
хорошее число обусловлен ности

На практике условие оптимального ?:

Ax(? ) ? b ? ?b ? ?A ?x(? )
? ? ? ??
невязка

где ?b и ?A – известные погрешности.

Рассмотрим частный случай: A=AT,
m

x * ? ? c i ei

=>

i ?1

(b, ei )
ci ?
?i

~
b ?b ? ?b

Иногда заранее известно,
что

Для больших |?i|:

m

(b, ei ) ? (?b, ei )
~
x ??
ei
?i
i ?1
(?b, ei )
Слагаемое
-искажает решение
?i
при малых ?

?ci ?0 : ?i ?0 . Такие сi надо выделить.

~
(b , ei )
x(? ) ??
?ei
?i
i? 1
m

1
1
?
?
?
? i ?i ? ? ? i (? i ? ? )

~
~
b , ei
b , ei
??
?i ? ?
?i

? ?

?1… ?m?0 - собственные значения, |?i|>|?i+1|
e1…em-собственные векторы

i

~
( A ? ?E ) x ?b ?b ? ?b

Для |?i|
Таким образом видна необходимость решения 2-ой задачи
линейной алгебры.

Ax=?x ?i=? – собственные значения (числа)
хi=? – собственные векторы
Здесь используется метод вращения
Проблемы:
-полная (найти все ?i и xi)
-частичная (найти некоторые ?i и xi, например max(min) |?i|)
-обобщённая (Ax=B?x)
-общая (aij=aij(?))
Все {?i}-спектр матрицы A, r = max|?i| - спектральный радиус
Ax=?x (A-?E)x=0 => существует решение, отличное от нуля, тогда и только тогда,
когда: det( A ? ?E ) ?0 -характеристическое уравнение

Поиск собственных значений и векторов итерационным методом вращения
Якоби (1804-1851г.г.) - 1846г.
Существует и множество других методов.
Рассмотрим частную задачу поиска собственных значений и собственных векторов
действительной симметричной матрицы (комплексной эрмитовой). (Существует прямой
метод вращения, который можно применять для неэрмитовых матриц.)
В качестве примера рассмотрим матрицу квадратичной формы:
n

n

??a

ik

xi x k ?b

i ?1 k ?1

В 3-х мерном пространстве это уравнение поверхности второго порядка.
Приведение этой формы к каноническому виду, когда

a~ik ?0, i ? k

и есть суть метода. Каждый шаг метода - поворот осей координат на некоторый угол.
T

? ? H AH

Имеет место преобразование координат вида
, где столбцы матрицы H- собственные векторы.

Здесь число неизвестных превосходит число уравнений, поэтому необходимы
последовательные приближения.

Алгоритм: 1. поиск

a kp ?max aij , i ? j

2. поворот осей координат в плоскости xkxp для обнуления образа элемента akp:
Условие поворота:

A
(R)

( R ?1)

?H

T (R)

(R)

A H

( R)

?H

T (R)

B (R)

B ( R ) - отличаются столбцы R и P

A и
A ( R ?1) и B ( R ) - отличаются строки k и P

H- матрица ортогонального преобразования вида:
?1 0 .
?
?0 1 .
?. . .
?
k ?0 . .
?0 . .
p?
?. . .
?
?0 . .

k
.
.
.
cos ?
sin ?
.
.

p
.
.
.
? sin ?
cos ?
.
.

.
.
.
.
.
.
.

0?
?
0?
.?
?
0?
0 ??
.?
?
1?

? a11
?
? a 21
? .
?
? a k1
?
? .
? a p1
?
? .
?a
? n1

=

a12
a 22
.
ak 2
.
a p2
.
an2

? a11
?
? a 21
? .
?
? a k1
? .
?
? a p1
?
? .
?a
? n1

...
...
.
...
.
...
.
...

a1k
a2k
.
a kk
.
a pk
.
a nk

a12
a 22
.
ak 2
.
a p2
.
an2

...
...
.
...
.
...
.
...

...
...
.
...
.
...
.
...

a1 p
a2 p
.
a pp
.
a pp
.
a np

...
...
.
...
.
...
.
...

a1n ?
??1
a2n ? ?
?0
?
. ?
? .
a kn ? ?
??0
. ??
.
?
a pn ?
??0
. ??
?.
?
a nn ? ?
?0

a1k cos ? ? a1 p sin ?
a 2 k cos ? ? a 2 p sin ?
.
a kk cos ? ? a kp sin ?
.
a pk cos ? ? a pp sin ?
.
a nk cos ? ? a np sin ?

k
0 ...
0
1 ...
0
. .
.
0 ... cos ?
. .
.

p
...
0
...
0
.
.
... ? sin ?
.
.

0 ... sin ?
. .
.
0 ...
0

...
.
...

...
...
.
...
.
...
.
...

cos ?
.
0

...
...
.
=...
.

0?
?
0?
.?
?
0?
. ??
... 0 ?
?
. .?
... 1 ??

? a1k sin ? ? a1 p cos ?
? a 2 k sin ? ? a 2 p cos ?
.
? a kk sin ? ? a kp cos ?
.
? a pk sin ? ? a pp cos ?
.
? a nk sin ? ? a np cos ?

...
...
.
...
.
...
.
...

a1n ?
?
a2n ?
. ?
?
a kn ?
?B
?
. ?
a pn ?
?
. ?
a nn ??

a11
?
?
a 21
?
?
.
?
? a cos ? ? a sin ?
p1
? k1
T
H ?B ??
.
?
? ? a sin ? ? a cos ?
p1
? k1
?
.
?
?
a n1
?

a12
a 22
.
a k 2 cos ? ? a p 2 sin ?
.
? a k 2 sin ? ? a p 2 cos ?
.
an2

...
...
.

a1k cos ? ? a1 p sin ?
a 2 k cos ? ? a 2 p sin ?
.
( a kk cos ? ? a pp sin ? ) cos ? ?

...
...
.

? a1k sin ? ? a1 p cos ?
? a 2 k sin ? ? a 2 p cos ?
.
(? a kk sin ? ? a kp cos ? ) cos ? ?

...
...
.

a1n
a 2n
.

?
?
?
?
?
...
...
... a kn cos ? ? a pn sin ? ?
?
? (a pk cos ? ? a pp sin ? ) sin ?
? (? a pk sin ? ? a pp cos ? ) sin ?
?
.
.
.
.
.
.
?
? (a kk cos ? ? a kp sin ? ) sin ? ?
? ( ? a kk sin ? ? a kp cos ? ) sin ? ?
...
...
... ? a kn sin ? ? a pn cos ? ?
?
? (a pk cos ? ? a pp sin ? ) cos ?
? (? a pk sin ? ? a pp cos ? ) cos ?
?
.
.
.
.
.
.
?
?
...
a nk cos ? ? a np sin ?
...
? a nk sin ? ? a np cos ?
...
a nn
?

a~kp ?? a kk cos? sin ? ? a kp cos 2 ? ? a pk sin 2 ? ? a pp cos? sin ? ?cos? sin ? (a pp ? a kk ) ? a kp (cos 2 ? ? sin 2 ? )
a~ pk ?? a kk cos? sin ? ? a kp sin 2 ? ? a pk cos 2 ? ? a pp cos? sin ? ?cos? sin ? (a pp ? a kk ) ? a kp (cos 2 ? ? sin 2 ? )

a pp ? a kk
2

?sin 2? ? a kp cos 2? ?a~kp ?0 tg 2? ?

2a kp
1
? ? arctg
2
a kk ? a pp
t ( A)
сферическая норма матрицы

2a kp
a kk ? a pp

, k
3) Критерий окончания счёта(один из…):

1
t ( A? l ? ) ? ?
n(n ? 1)

Собственные значения – элементы на главной диагонали итоговой матрицы А.
4) Собственные векторы есть столбцы матрицы:

H

( L)

L

?? H
l ?1

(l )

Свойства преобразования, используемые для контроля расчетов:
1) treck A = treck A(l)
(l )
(l )
a
?
a
при i?j - симметрия матрицы A(l)
ji
2) ij

К обоснованию метода вращений:
Df. А и В - подобные матрицы, если существует невырожден ная матрица C : B ?C ? 1 AC .
Теорема : Подобные матрицы имют одинаковые спектры(набор ? ).
Док - во : C ? 1 AC ? ?E ? C ? 1 AC ? ?C ? 1 EC ? C ? 1 ?A ? ?E ?C ? A ? ?E
Утв. trB = trA.
Доказать самостоятельно!
Интересный метод для поиска собственных значений - метод л локаль й интерполяции

B=AHkl: B и A- отличия в k и l столбцах:
bik=aik?+?il?
bil=-aik?*+ail?
bij=aij

j?k,l

i=1?n

C =HklB: C и B - отличия от в k и l строках:
C k ?bk ? ? bl ? * C l ?? bk ? ? bl ?
C ji ?b ji
j?k,l
i=1?n
i

i

i

i

i

i

? C kl ?a kl (? 2 ? ? 2 ) ? (all ? a kk )??
? ?
2
2
?
?
?
?1
?
Сkl=0 из условия min недиагональной части






Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.