Численные методы. Корнюшин П.Н. - 56 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

56
Точность итерационного метода (2) характеризуется величиной погрешности z
k
=y
k
-u, т.е.
разностью между решением y
k
уравнения (2) и точным решением u исходной системы линейных
алгебраических уравнений. Подстановка y
k
=z
k
+u в (2) приводит к однородному уравнению для
погрешности:
,...1,0,0
1
1
==+
−
+
+
kAz
zz
B
k
k
kk
τ
, z
0=
y
0
-u. (5)
Говорят, что итерационный метод сходится в H
D
, если
,0lim =
∞→
D
k
k
z где .:,0,),(
*
HHDDDzDzz
D
→>==
Обычно задают некоторую относительную погрешность
ε
>0, с которой надо найти
приближенное решение y
k
, и прекращают вычисления, как только выполняется условие
.
0
DD
n
uyuy −≤−
ε
(6)
Если n=n(
ε
) – наименьшее из чисел, для которых (6) выполняется, то общее число
арифметических действий, затрачиваемых для нахождения приближенного решения уравнения
(1), равно Q
n
(
ε
)=n(
ε
)q
0
, где q
0
– число действий, затрачиваемых для нахождения одной итерации,
т.е. для решения уравнения (4). Задача состоит в минимизации Q
n
(
ε
) путем выбора B и параметров
{}
.
k
τ
3.5.3.2. Метод простой итерации
Для решения системы уравнений (1) может быть использован метод простой итерации
,,...,2,1,
1
)()()()(
1
Nifyayy
N
j
ij
kij
i
k
i
k
=
−−=
∑
=
+
τ
(7)
где
τ
>0 - итерационный параметр. Запишем (7) в операторной форме:
,...,1,0,
1
==+
−
+
kfAy
yy
k
kk
τ
для всех y
0
∈
H. (8)
Сравнение (8) с (3) показывает, что метод простой итерации задается явной одношаговой
схемой с постоянным параметром
.
τ
τ
≡
k
Существуют и другие варианты метода простой итерации, например, такой:
.
1
1
)()()(
1
−=
∑
=
≠
+
N
ij
ij
kij
ii
i
k
j
fya
a
y
Подставляя сюда
∑∑
==
−=−=
≠
N
j
i
k
i
k
i
kii
j
kij
N
j
j
kij
DyAyyayaya
ij
1
)()()()(
1
)(
,)()(
где D=(a
ii
δ
ij
) – диагональная матрица, получаем
,
1
1
)()()()(
1
−−=
∑
=
+
N
ij
kij
ii
i
k
i
k
j
fya
a
yy
или, в каноническом виде,
.1,...,1,0,
1
===+
−
+
τ
τ
kfAy
yy
D
k
kk
Хотя формально эта схема является неявной (B=D
≠
E), однако D=(a
ii
δ
ij
) – диагональная
матрица и потому y
k+1
определяется по явным формулам.
3.5.3.3. Метод Зейделя 
                                                                               56


       Точность итерационного метода (2) характеризуется величиной погрешности zk=yk-u, т.е.
разностью между решением yk уравнения (2) и точным решением u исходной системы линейных
алгебраических уравнений. Подстановка yk=zk+u в (2) приводит к однородному уравнению для
погрешности:
                                      z k +1 − z k
                                 B                        + Az k = 0, k = 0,1,... , z0=y0-u.                     (5)
                                           τ k +1
          Говорят, что итерационный метод сходится в HD, если
                     lim z k D = 0, где z  = ( Dz, z ) , D = D * > 0, D : H → H .
                     k →∞                                             D

      Обычно задают некоторую относительную погрешность ε>0, с которой надо найти
приближенное решение yk, и прекращают вычисления, как только выполняется условие
                              yn − u D ≤ ε y0 − u D .      (6)
         Если n=n(ε) – наименьшее из чисел, для которых (6) выполняется, то общее число
арифметических действий, затрачиваемых для нахождения приближенного решения уравнения
(1), равно Qn(ε)=n(ε)q0, где q0 – число действий, затрачиваемых для нахождения одной итерации,
т.е. для решения уравнения (4). Задача состоит в минимизации Qn(ε) путем выбора B и параметров
{τ k }.

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

          Для решения системы уравнений (1) может быть использован метод простой итерации
                                                      N                         
                            y k( i+)1 = y k(i ) − τ  ∑ aij y k( j ) − f ( i ) , i = 1,2,..., N ,                   (7)
                                                      j =1                      
          где τ>0 - итерационный параметр. Запишем (7) в операторной форме:
                        y k +1 − y k
                                                + Ay k = f , k = 0,1,..., для всех y0 ∈ H.                             (8)
                                 τ
       Сравнение (8) с (3) показывает, что метод простой итерации задается явной одношаговой
схемой с постоянным параметром τ k ≡ τ .
       Существуют и другие варианты метода простой итерации, например, такой:
                                                                                                   
                                                                      1  N                    (i ) 
                                                        y k( i+)1 =          ∑ ij k
                                                                      aii  j =1
                                                                                  a y ( j)
                                                                                           − f      .
                                                                            j ≠i                    
          Подставляя сюда
                               N                         N

                              ∑a
                               j =1
                                      ij   y   ( j)
                                               k      =∑ aij y k( j ) − aii y k( i ) = ( Ay k ) ( i ) − ( Dy k ) ( i ) ,
                                                         j =1
                               j ≠i


          где D=(aiiδij) – диагональная матрица, получаем
                                                                                                        
                                                                           1  N                    (i ) 
                                                 y k( i+)1 = y k(i ) −            ∑ ij k
                                                                           aii  j =1
                                                                                       a y ( j)
                                                                                                − f      ,
                                                                                                         
или, в каноническом виде,
                                                  y k +1 − y k
                                           D                          + Ay k = f , k = 0,1,...,τ = 1.
                                                         τ
      Хотя формально эта схема является неявной (B=D ≠ E), однако D=(aiiδij) – диагональная
матрица и потому yk+1 определяется по явным формулам.


                                                          3.5.3.3. Метод Зейделя

Страницы