Численные методы линейной алгебры Учебное пособие. Ширапов Д.Ш. - 29 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

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

Рубрика: 

Доказательство
Доказательство следует из того, что если
1S < , то и µ
p
<1. Следовательно, по теореме
3.4 стационарный итерационный процесс сходится.
3.5. Вариационно-итерационные методы
В параграфе 3.4 рассматривались такие итерационные методы решения СЛАУ
Ax=b, (3.40)
в которых для задания итерационных параметров требовалось знание границы собственных
значений матрицы А. Что делать, если такой информации нет? В таком случае можно при-
менять методы, не использующие знания о границах собственных значений матрицы А.
Ниже описываются итерационные методы вида
В
1k
)k()1k(
xx
+
+
τ
−
+ Ax
(k)
=b, k=0, 1, 2,…
в которых параметры
τ
k+1
выбираются из других условий.
3.5.1. Метод минимальных невязок
Рассмотрим явную схему метода минимальных невязок [8, 9] заданную формулой с сим-
метричной положительно определенной матрицей А.
1k
)k()1k(
xx
+
+
τ
−
+ Ax
(k)
=b, k=0, 1, 2,… (3.41)
Для невязки R
(k)
= Ax
(k)
-b из (3.41) получим
1k
)k()1k(
RR
+
+
τ
−
+ AR
(k)
=0, k=0, 1, 2,…
R
(k+1)
=R
(k)
-τ
k+1
AR
(k)
.
Параметр
τ
k+1
выбираем из условия минимума невязки R
(k+1)
по норме
+τ−=τ−=
++
+
)AR,R(2RARRR
)k()k(
1k
2
)k(
2
)k(
1k
)k(
2
)1k(
2
)k(2
1k
AR
+
τ+
=ϕ(τ
k+1
).
Дальше вычислим производную от функции
ϕ(τ
k+1
) по параметру τ
k+1
и приравняем нулю
ϕ
’
(τ
k+1
)= -2(R
(k)
,AR
(k)
)+2τ
k+1
2
)k(
AR
=0
или
2
)k(
)k()k(
1k
AR
)R,AR(
=τ
+
, k=0, 1, 2,… (3.42)
При этом значении параметра
τ
k+1
вторая производная ϕ
”
(τ
k+1
)>0, следовательно, достига-
ется
2
1)(k
τ
Rmin
1k
+
+
.
В этом методе переход от k-ой итерации к (k+1)-ой осуществляется следующим обра-
зом. По найденному значению x
(k)
вычисляется вектор невязки R
(k)
= Ax
(k)
-b и по формуле
(3.42) находится параметр
τ
k+1
. Затем по формуле (3.41) вычисляется вектор x
(k+1)
.
Метод минимальных невязок (3.41), (3.42) сходится с той же скоростью, что и метод
простой итерации с оптимальным параметром
τ . 
                                      Доказательство
    Доказательство следует из того, что если S < 1 , то и µp<1. Следовательно, по теореме
3.4 стационарный итерационный процесс сходится.

                                               3.5. Вариационно-итерационные методы

   В параграфе 3.4 рассматривались такие итерационные методы решения СЛАУ
                   Ax=b,                                         (3.40)
в которых для задания итерационных параметров требовалось знание границы собственных
значений матрицы А. Что делать, если такой информации нет? В таком случае можно при-
менять методы, не использующие знания о границах собственных значений матрицы А.
   Ниже описываются итерационные методы вида
                                                         x ( k +1) − x ( k )
                                                     В                       + Ax(k)=b,          k=0, 1, 2,…
                                                                τ k +1
в которых параметры τk+1 выбираются из других условий.

                                                    3.5.1. Метод минимальных невязок

   Рассмотрим явную схему метода минимальных невязок [8, 9] заданную формулой с сим-
метричной положительно определенной матрицей А.
                                    x ( k +1) − x ( k )
                                                        + Ax(k)=b,           k=0, 1, 2,…                                 (3.41)
                                           τ k +1
Для невязки R(k)= Ax(k)-b из (3.41) получим
                                                       R ( k +1) − R ( k )
                                                                           + AR(k)=0,           k=0, 1, 2,…
                                                              τ k +1
                                                R(k+1)=R(k)-τk+1AR(k) .
Параметр τk+1              выбираем из условия минимума невязки R(k+1) по норме

                           2                                  2              2                                                 2
               R ( k +1)       = R ( k ) − τ k +1 AR ( k )        = R (k )       − 2τ k +1 (R ( k ) , AR ( k ) ) + + τ2k +1 AR ( k ) =ϕ(τk+1).


Дальше вычислим производную от функции ϕ(τk+1) по параметру τk+1 и приравняем нулю
                                                                                                              2
                                                    ϕ’(τk+1)= -2(R(k),AR(k))+2τk+1 AR ( k ) =0
или
                                               (AR ( k ) , R ( k ) )
                                    τ k +1 =                  2
                                                                       , k=0, 1, 2,…                                     (3.42)
                                                   AR ( k )


При этом значении параметра τk+1 вторая производная ϕ”(τk+1)>0, следовательно, достига-
                           2
ется min R (k +1) .
      τ k +1

    В этом методе переход от k-ой итерации к (k+1)-ой осуществляется следующим обра-
зом. По найденному значению x(k) вычисляется вектор невязки R(k)= Ax(k)-b и по формуле
(3.42) находится параметр τk+1. Затем по формуле (3.41) вычисляется вектор x(k+1).
    Метод минимальных невязок (3.41), (3.42) сходится с той же скоростью, что и метод
простой итерации с оптимальным параметром τ .

Страницы