Задачи с диагональными матрицами. Метод прогонки.
П
р
и
м
е
р с
и
с
т
е
м
ы л
и
н
е
й
н
ы
х у
р
а
в
н
е
н
и
й – р
а
з
н
о
с
т
н
ы
й (
з
а
м
е
н
я
е
т
д
и
ф
ф
е
р
е
н
ц
и
а
л
ь
н
ы
й
2
о
г
о
п
о
р
я
д
к
а

п
е
р
а
т
о
р
н
ад
и
с
к
р
е
т
н
о
м
м
н
о
ж
е
с
т
в
ет
о
ч
е
к
.
D
x
=
F
0
n
+
1

1

2

i1

i

i+
1

n
1

n

_
_
_
_

c
d
1
,n
в
н
у
т
р
е
н
н
и
ет
о
ч
к
и
:a
ix
i?1?b
ix
i?
ix
i?
1?
i i?
x
x
c
x
d
л
е
в
а
я
г
р
а
н
и
ц
а
: a
0
0?b
0
1?
0
2?
0

п
р
а
в
а
я
г
р
а
н
и
ц
а
:

}
a x ?b x?
cx ?
d
n
?
!n
?1

n
?
1n

n
?
!n
?
1

г
р
а
н
и
ч
н
ы
еу
с
л
о
в
и
я

n
?
1

И
м
е
е
м
д
в
ес
и
с
т
е
м
ы
:

a
x
x
c
x
d
0
0?b
0
1?
0
2?
0

м

с
к
л
ю
ч
и
т
ьx
0

{ax?bx?cx?
d
10

{
м

с
к
л
ю
ч
и
т
ь
x
n
+
1

11

12

1

a
x
x
c
x
d
n
n
?1?b
n
n?
n
n
?
1?
n
a
x
x
c
x
d
n
?
1
n
?1?b
n
?
1
n?
n
?
1
n
?
1?
n
?
1

~ ~ ~
?b
x
c
x
d
1
1?
1
2?
1
? ?
?
?
?
~
~
~
a
x
?
b
x
?
d
nn
?1
nn
n

У
б
р
а
в
з
н
а
к

~

п
о
л
у
ч
и
м
с
и
с
т
е
м
у
в
и
д
а
:

?
b
c
0
.....
0
?
?
d
1
1
1
?
?
a
?
b
c
.....
0
d
?
?
22
2
2
?
?
0
a
?
b
.....
0
d
3
3
3
?
?

н
о
р
м
а
л
ь
н
а
я
с
и
с
т
е
м
а
м
е
т
о
д
а
п
р
о
г
о
н
к
и
.....
.....
.....
.....
.....
?
?
.....
?
?
0
.....
a
?
b
c
(
1
)
d
n
?
1n
?
1
n
?
1
n
?
1
?
?
?
?
d
.....
.....
0
a
?
b
?
n
nn
?

Т
а
к
к
а
к
в
м
а
т
р
и
ц
е
н
о
р
м
а
л
ь
н
о
й
с
и
с
т
е
м
ы
м
н
о
г
о
н
у
л
е
в
ы
х
э
л
е
м
е
н
т
о
в
,
н
е
т
с
м
ы
с
л
а
и
с
п
о
л
ь
з
о
в
а
т
ь
а
л
г
о
р
и
т
м
м
е
т
о
д
а
Г
а
у
с
с
а
.
Н
а
д
о
е
г
о
и
з
м
е
н
и
т
ь
П
о
м
е
т
о
д
у
Г
а
у
с
с
а
м
а
т
р
и
ц
а
п
р
и
в
о
д
и
т
с
я
к
в
е
р
х
н
е
й
т
р
е
у
г
о
л
ь
н
о
й
ф
о
р
м
е
,
к
о
т
о
р
а
я
д
л
я
н
о
р
м
а
л
ь
н
о
й
с
и
с
т
е
м
ы
(
1
)
п
р
и
м
е
т
в
и
д
:
x
x
0
.
0
?
?
?
?
0
x
x
.
0
?
?
?
?
.
.
.
.
.
?
?
0
.
.
x
x
?
?
?
?
0
.
.
0
x
?
?

П
оэтому для обратного хода метода Гаусса будет верно рекуррентное
соотнош
ение:
b
xn ? n ; xi ?
P
Q
i?
n? 1,1
i?
1x
i?
1?
i?
1
ann
где P
рогоночныекоэффициенты
i?
1 –п
i?
1, Q

di
?ai xi?1 ? bi xi ?ci xi?1 ?
?
P
i xi ?Q
i
?xi?1 ?

di
? aiP
ix
i ?a
iQ
i ?b
ix
i ?c
ix
i?
1?

xi(aiP
di ? aiQ
i ?b
i )?
i ?c
ix
i?
1
ci
aiQ
i ? di
xi ?
xi?1 ?
bi ? aiP
bi ? aiP
i
i
P
i?
1

Q
i?
1

Дляграничныхточек(верхнихдвухстрок):

c1
d1
? b1x1 ?c1x2 ?
d1 ? x1 ?b x2 ?? b
1
1
P
Q
2
2
Н
ахождение P
ойход;
i –прям
i ,Q
Реализацияф-л(2)–обратныйход.

(2a)

D f: М е т о д п р о г о н к и н а з ы в а е т с я к о р р е к т н ы м , е с л и д л я л ю б о г о i (b i ? a i P i ) ? 0 .
У т в : М е т о д п р о г о н к и у с т о й ч и в , е с л и д л я л ю б о г о i |P i | < 1 ( п о г р е ш н о с т ь п р и о б р а т н о м
х о д е н е в о зр а с та е т).
И з (2 а ) с л е д у е т в и д м а тр и ц ы :
c1
0
?
? ? b1
?
a 2 P2 ? b2 c 2
?
? 0
? ?
?
?
?
?
0
0 a n Pn ? bn
? 0
? 0
?
?
?
?

0
?
?
0
?
?
?
?
c n ? Р а с п и ш е м |А | ч е р е з а л г е б р а и ч е с к и е д о п о л н е н и я :
a n ? b n ??

n? 2

| A |? ? b 1 ?? ( a i P i ? b i ) ??( ? b n ) ?( a n ? 1 P n ? 1 ? b n ? 1 ) ? a n c n ? ?
i?2

?
? n?1
a
c
n
n
? ? b 1 ? ??
? b n ?? ? ( a i P i ? b i ) ?
? i?2
? a n ? 1Pn ? 1 ? b n ? 1
-P n
n

? ? b 1 ?? ( a i P i ? b i )
i?2

Итерационные методы решения систем линейных уравнений: метод
простой итерации, метод Зейделя. Условие сходимости и оценка
погрешности. Обращение матрицы.

x ? x ? DAx ? Db
Ax ?b

Метод простой итерации

?
x ?Bx ? c

x

решение

:

? xn? ? x
n? ?

x n ?1 ?Bx n ? c
Существует три этапа построения итерационной процедуры:
1. Построение итерационного цикла;
2. Оценка сходимости итерационного цикла;
3. Оптимизация итерационного цикла (максимальная скорость сходимости)
Df

x

( k ?1)

?

x

A = const

(k ) n

(k )

?A x ?

x

( k ? 1)

- итерационный метод n-ого порядка сходимости

k - номер итерации
n – порядок сходимости

еорема (достаточное условие сходимости метода простой итерации)

сли

B ? 1 ,то система

x ? Bx ? c

имеет единственное решение, и итерации сходятся к решению со
скоростью геометрической прогрессии.
Доказательство: 1) x * ? x* ? Bx * ?c
решение

x * ? B ? x * ? c ? x * ??1 ? B ? ? c ? x * ?(1 ? B ) ? 1 ? c

?

B ?1

Докажем единственность решения: пусть x1, x2 - решения

x1 ? x 2 ? x 2 ? x1 ??x ? решение
x1 ? B ? x1 ? c ??
? ? x1 ? x 2 ? B ? x1 ? x 2 ? x1 ? x 2
x 2 ? B ? x 2 ? c ??
(см. свойства нормы)

2) x * - решение ? x* ? Bx * ?c

x n ?1 ? x* ?r n ?1
(r

невязка)
Ч. т. д.

x n ?1 ?B ?x n ? c
? B ?( x n ? x*) ? B ?r n ? B n ?1 ?r0 ? r n ?1 ? B n ?1 ? r0 ? 0

Оценка погрешности
Если

B ?x ? B ? x и B ? 1 , то

x
Доказательство:

A( x ( k ) ? x*) ? Ax ( k ) ? b

Для

( k ?1)

B

? x* ?
? x ( k ) ? x ( k ? 1)
1? B

Ax ?b

?D

D : x * ? Bx* ?c ? E ? B ?DA

c ?Db

x ( k ?1) ?Bx ( k ) ? c ? c ?x ( k ?1) ? Bx ( k )
( E ? B)( x ( k ) ? x*) ?( E ? B) x ( k ) ? Bx ( k ) ? x ( k ?1) ?x ( k ) ? x ( k ?1) ?Bx ( k ? 1) ? c ? Bx ( k ) ? c ?B( x ( k ? 1) ? x ( k ) )
( E ? B)( x ( k ) ? x*) ? ( x ( k ) ? x*) ? B ?( x ( k ) ? x*) ? x ( k ) ? x * ? B ?( x ( k ) ? x*) ??
?
(k )
(k )
(k )
??
? x ? x * ? B ? x ? x * ?(1 ? B ) ? x ? x *
??
?
?
( k ? 1)
(k )
( k ? 1)
(k )
B ?( x ? x ) ? B ? x ? x
??
? (1 ? B ) ? x ( k ) ? x * ? B ? x ( k ? 1) ? x ( k )

Ч. т. д.

Есть достаточное условие сходимости итерационного цикла, но нет необходимого.
( ? - собственные значения матрицы B)
Теорема (необходимое и достаточное условие сходимости метода простой итерации)
Существует и единственно решение
для любых

x * ( Ax* ?b)

и

x ( 0 ) тогда и только тогда, когда для любых

?x ? :
(k )

x ( k ?1) ? Bx ( k ) ? c
i ?i ? 1 и Bx ??i x.

(Это правило справедливо для вычислений без ошибок округления.)
Пример простого итерационного цикла:

Ax ?b
n

aii xi ?bi ?

?a

ij

?x j

j ?i

aii x

( k ?1)
i

n

?bi ?

(k )
a
?
x
? ij j
j ?i

i ?1, n

x

( k ?1)
i

bi
? ?
aii

n

aij

?a
j ?i

?x (jk ) ?

x ( k ?1) ? B ?x ( k ) ? c

ii

В B нули на главной диагонали.

B ?1 ?

Из

B

c

?1 ?

n

aij

?a
j ?i

ii

n

? 1 ? a ii ? ? aij
j ?i

n

a ii ? ? aij

- условие преобладания диагональных элементов

j ?i

( k ?1)

В методе простой итерации x
не используются до завершения итерационного
цикла, хотя являются лучшими приближениями, что неэкономично. От этого недостатка
свободен метод Зейделя (Гаусса-Зейделя).
( k ?1)
ii i

a x

?bi ?

i? 1

?a x
j ?1

i

( k ?1)
ij j

?a x
j ?1

( k ?1)
ij j

n

n

?

(k )
a
x
? ij j

j ?i ?1

? ? aij x (jk ) ?bi ? Bx ( k ?1) ? Cx ( k ) ?b ? x ( k ?1) ?? B ? 1Cx ( k ) ? B ? 1b
j ?i ?1

B – нижняя треугольная матрица
С – верхняя треугольная матрица с нулями на главной диагонали
Необходимое и достаточное условие сходимости:
для любых i

?i ? 1 ?i : (? B ? 1C ) x ??i x

Можно уйти от нахождения обратной матрицы:

? B ? 1C ? ?E ?0 - характеристическое уравнение
(у этих уравнений общие
?)
? B ? 1C ? ?E ? ? B ? 1 ?C ? B? ?0
корни

a11 ?

a12

?

a 21
?

a 22 ? ?
? ?

a n1

an2

a1n
a2n
?0
?

? a nn ?

?i ? 1

Геометрическая интерпретация метода Зейделя
n=2

1)

?? a11 x1* ? a12 x 2* ?b1
?
?? a 21 x1* ? a 22 x 2* ?b2

X2

уравнения прямых (плоскостей в n-мерном пространстве)
Метод Зейделя

L2

?? a11 x1( k ?1) ?b1 ? a12 x 2( k )
?
?? a 22 x 2( k ?1) ?b2 ? a 21 x1( k ?1)

(k)

(k+1)
L1

( x1( k ) , x 2( k ) ) ? ( x1( k ?1) , x 2( k ) ) ? ( x1( k ?1) , x 2( k ?1) )

X1
2)

Метод Зейделя
X2
(k+1)

?? a 22 x 2( k ?1) ?b2 ? a 21 x 2( k )
?
?? a11 x1( k ?1) ?b1 ? a12 x 2( k ?1)

(k)

X1

( x1( k ) , x 2( k ) ) ? ( x1( k ?1) , x 2( k ) ) ? ( x1( k ?1) , x 2( k ?1) )

Сходимость метода может изменить характер при перестановке уравнений.
Возможно и “зацикливание” метода.
Теорема
Если А – вещественная, симметричная, положительно определённая (т. е. все главные
миноры неотрицательны) матрица, то метод Зейделя сходится.
Доказательство:

( f , h) ? ?? ( x) f ( x)h( x)dx

- скалярное произведение векторов f и h

X

Часто ? ( x ) ?1

f (x) - комплексно сопряжённое

x * - решение
~
x - приближенное решение
Введём функцию F(y)

F ( y ) ?( A( ~
x ? x*), ~
x ? x*) ? ( Ax*, x*) ?( A~
x, ~
x ? x*) ? ( Ax*, ~
x ? x*) ? ( Ax*, x*) ?
?( A~
x, ~
x ) ? ( A~
x , x*) ? ( Ax*, ~
x ) ? ( Ax*, x*) ? ( Ax*, x*) ?( A~
x, ~
x ) ? ( A~
x , x*) ? ( Ax*, ~
x)
Так как матрица симметрична

F ( y ) ?( A~
x, ~
x ) ? 2( Ax*, ~
x ) ?( A~
x, ~
x ) ? 2(b, ~
x)

Так как матрица положительно определённая , то

( A( ~
x ? x*), ~
x ? x*) ? 0 при

~
~
x ? x * ? существует единственное x такое, что
~
x ?x *
и
F ( ~x ) ? F ( x*) ?min F ( x)
X

Способ нахождения min функции

F ( x1 , ? , x n ) - метод покоординатного спуска:

?F
?F
x1( 0) ? xn( 0) ? x1(1) , x2( 0) ,? xn( 0) :
?0 (min F ) ? x1(1) , x2(1) , x3( 0) ,? xn(0) :
?0 ? ?
? ? ? ? ? ? ? ?x1
?
?
?
?
?
?
?
?
?
X1
?x2
x (1 )

x( 2 )

?n
?
?F
?
?
? ( Ax, x) ?
(2? bi xi ) ?2? ? akj x j ? bk ? ?0
?xk ?xk
?xk i
? j ?1
?
n

(? akj x j ? bk )

- система уравнений метода Зейделя

j ?1

Если

x ( m ) ? x *, то существует ml

?F ( m )
( x ) ?0
? xm

такое, что

l ?1, L

l ?1, L - некоторый набор уравнений

( x j ) ?x (k )

Выберем минимальный номер k такой, что
покоординатного спуска. Тогда

x( k )

?F
?0, и уточним x k по методу
?x k

x ( k ?1)

? ? ? ? ? ??
? ? ? ? ? ? ?
(k )
( k ?1)
F ( x ,? x ? , x ) ? F ( x1 ,? xl ? , x n )
? ? 1 ? ? ? l ? ? ??n
? ? ? ? ? ? ? ??
F (k )

F ( k ?1)

F ( k ) ? F ( k ?1)
И хоть одно неравенство строгое (для минимального k). Следовательно, метод сходится.
Ч. т. д.

( x1( 0) ,? xk( 0? )1 , xk( 0) ,? xn( 0) ) ? ( x1(1) ,? xk(1?)1 , xk(1) ,? xn(1) )
x1(1) , ? xk(1?)1

xk(1)

- не уточняются

-F

xk(1) , ? xn(1)

- F не увеличивается (но может уменьшиться)

Оценка скорости сходимости – см. Бахвалов и др. “Численные методы”

Общая схема итерационного процесса

U , H - матрицы

?k

- итерационный параметр

x ( k ?1) ? x ( k )
Ax ?b ? Ux ?Ux ? ?H ( Ax ? b) ? U k
? HAx ( k ) ?Hb
?k
Df Если U k ?U и ? k ?? , то итерационный процесс стационарный.
Df Если U ? E , то итерационный процесс неявный.
Если U ?E , то итерационный процесс (итерационная схема) явный.
Df

? ??
U ? D ? ?L
D - диагональная матрица

- релаксационные методы

?

- параметр релаксации

L

- нижняя треугольная матрица с нулями на главной диагонали

? >1 – методы верхней релаксации
?
Нахождение обратной матрицы

? ?11 ?12 ? ?
?
?
?1
A ?? ? 22 ? 21 ? ?
? ? ? ??
?
?

A? 1 A ?E ?

? n
? ? ? ij a ji ?? ij
? j ?1
? i ?1, n
?

? a11
?
A ?? a22
??
?

a12 ? ?
?
a21 ? ?
? ? ??

Система линейных уравнений






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