ЧМ-Лекция 03 (Лекции (презентации))

Задачи с диагональными матрицами. Метод прогонки.
П
р
и
м
е
р с
и
с
т
е
м
ы л
и
н
е
й
н
ы
х у
р
а
в
н
е
н
и
й – р
а
з
н
о
с
т
н
ы
й (
з
а
м
е
н
я
е
т
д
и
ф
ф
е
р
е
н
ц
и
а
л
ь
н
ы
й
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
( k 1)

b1  a12 x 2( k )
a11 x1

( k 1)
( k 1)

a
x

b

a
x
 22 2
2
21 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 – методы верхней релаксации
 <1 – методы нижней релаксации
 =1 – методы полной релаксации (метод Зейделя)
Итерационные методы эффективны для диагональных матриц или нерегулярных
матриц (много нулей).
Неудобны для одинаковых матриц А и разных b ( Ax b).
Оценка числа итераций – см. Кошелева “Численные методы и алгоритмы решения задач
ракетной техники”, изд. МАИ.

Нахождение обратной матрицы
 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  
  
Система линейных уравнений