A
x
=
b
{\displaystyle Ax=b}
приводим к виду, удобному для итерации:
x
=
B
x
+
c
{\displaystyle x=Bx+c}
{
x
1
=
b
11
x
1
+
.
.
.
+
b
1
m
x
m
+
c
1
…
x
m
=
b
m
1
x
1
+
.
.
.
+
b
m
m
x
m
+
c
m
{\displaystyle {\begin{cases}x_{1}=b_{11}x_{1}+...+b_{1m}x_{m}+c_{1}\\\dots \\x_{m}=b_{m1}x_{1}+...+b_{mm}x_{m}+c_{m}\end{cases}}}
Самый простой метод: из
i
{\displaystyle i}
-го уравнения выражаем
x
i
{\displaystyle x_{i}}
. Возможно только если диагональные элементы матрицы
A
{\displaystyle A}
ненулевые. Иногда приводят к виду
x
=
x
−
τ
(
A
x
−
b
)
{\displaystyle x=x-\tau (Ax-b)}
, где
τ
{\displaystyle \tau }
- специально выбираемый числовой параметр.
Описание: Выбираем начальное приближение
x
(
0
)
=
(
x
1
(
0
)
,
x
2
(
0
)
,
.
.
.
,
x
m
(
0
)
)
T
{\displaystyle x^{(0)}=(x_{1}^{(0)},x_{2}^{(0)},...,x_{m}^{(0)})^{T}}
x
(
1
)
=
B
x
(
0
)
+
c
x
(
k
+
1
)
=
B
x
(
k
)
+
c
,
k
=
0
,
1
,
2
,
.
.
.
{\displaystyle x^{(1)}=Bx^{(0)}+c\quad x^{(k+1)}=Bx^{(k)}+c,k=0,1,2,...}
Если система
x
=
B
x
+
c
{\displaystyle x=Bx+c}
получена по вышеописанному (самому простому) методу, то МПИ называется методом Якоби.
Теорема. Пусть выполнено условие
‖
B
‖
<
1
{\displaystyle \|B\|<1}
, тогда
∃
!
{\displaystyle \exists !}
решение
x
¯
{\displaystyle {\overline {x}}}
системы
x
=
B
x
+
c
{\displaystyle x=Bx+c}
при
∀
{\displaystyle \forall }
начальном приближении
x
(
0
)
{\displaystyle x^{(0)}}
МПИ сходится и справедлива оценка погрешности
‖
x
(
n
)
−
x
¯
‖
≤
‖
B
‖
n
‖
x
(
0
)
−
x
¯
‖
{\displaystyle \|x^{(n)}-{\overline {x}}\|\leq \|B\|^{n}\|x^{(0)}-{\overline {x}}\|}
Замечание. При
‖
B
‖
=
‖
B
‖
1
{\displaystyle \|B\|=\|B\|_{1}}
получаем:
∑
i
=
1
,
i
≠
j
m
|
a
i
j
|
<
|
a
j
j
|
j
=
1
,
m
¯
{\displaystyle \sum _{i=1,i\neq j}^{m}|a_{ij}|<|a_{jj}|\quad j={\overline {1,m}}}
.
Апостериорная оценка погрешности:
Если
‖
B
‖
<
1
{\displaystyle \|B\|<1}
, то справедлива апостериорная оценка:
‖
x
(
n
)
−
x
¯
‖
≤
‖
B
‖
1
−
‖
B
‖
‖
x
(
n
)
−
x
(
n
−
1
)
‖
{\displaystyle \|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B\|}{1-\|B\|}}\|x^{(n)}-x^{(n-1)}\|}
Доказательство.
x
(
n
)
−
x
¯
=
B
(
x
(
n
−
1
)
−
x
(
n
)
)
+
B
(
x
(
n
)
−
x
¯
)
⇒
‖
x
(
n
)
−
x
¯
‖
=
‖
B
‖
‖
x
(
n
−
1
)
−
x
(
n
)
‖
+
‖
B
‖
‖
x
(
n
)
−
x
¯
‖
⇒
‖
x
(
n
)
−
x
¯
‖
≤
‖
B
‖
1
−
‖
B
‖
‖
x
(
n
)
−
x
(
n
−
1
)
‖
{\displaystyle x^{(n)}-{\overline {x}}=B(x^{(n-1)}-x^{(n)})+B(x^{(n)}-{\overline {x}})\Rightarrow \|x^{(n)}-{\overline {x}}\|=\|B\|\|x^{(n-1)}-x^{(n)}\|+\|B\|\|x^{(n)}-{\overline {x}}\|\Rightarrow \|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B\|}{1-\|B\|}}\|x^{(n)}-x^{(n-1)}\|}
Критерий окончания итерационного процесса:
‖
x
(
n
)
−
x
(
n
−
1
)
‖
<
ε
1
{\displaystyle \|x^{(n)}-x^{(n-1)}\|<\varepsilon _{1}}
, где
ε
1
=
1
−
‖
B
‖
‖
B
‖
ε
{\displaystyle \varepsilon _{1}={\frac {1-\|B\|}{\|B\|}}\varepsilon }
.
Если
A
{\displaystyle A}
- симметричная, положительно определенная матрица, то
A
x
=
b
{\displaystyle Ax=b}
, часто приводят к виду
x
=
x
−
τ
(
A
x
−
b
)
{\displaystyle x=x-\tau (Ax-b)}
x
(
k
+
1
)
=
x
(
k
)
−
τ
(
A
x
(
k
)
−
b
)
{\displaystyle x^{(k+1)}=x^{(k)}-\tau (Ax^{(k)}-b)}
- здесь
B
=
E
−
τ
A
{\displaystyle B=E-\tau A}
. Параметр
τ
>
0
{\displaystyle \tau >0}
выбирают так, чтобы по возможности сделать минимальной
‖
b
‖
2
=
max
1
≤
j
≤
m
λ
j
(
B
T
B
)
{\displaystyle \|b\|_{2}=\max {1\leq j\leq m}{\sqrt {\lambda _{j}(B^{T}B)}}}
.
‖
B
‖
2
<
1
{\displaystyle \|B\|_{2}<1}
если
τ
∈
(
0
,
2
λ
m
a
x
)
{\displaystyle \tau \in (0,{\frac {2}{\lambda _{max}}})}
. Оптимально
τ
=
2
λ
m
i
n
+
λ
m
a
x
{\displaystyle \tau ={\frac {2}{\lambda _{min}+\lambda _{max}}}}
Тогда
‖
B
‖
2
=
λ
m
a
x
−
λ
m
i
n
λ
m
a
x
+
λ
m
i
n
{\displaystyle \|B\|_{2}={\frac {\lambda _{max}-\lambda _{min}}{\lambda _{max}+\lambda _{min}}}}
. Если известны не сами
λ
m
i
n
{\displaystyle \lambda _{min}}
и
λ
m
a
x
{\displaystyle \lambda _{max}}
, а их оценки
0
<
μ
≤
λ
m
i
n
≤
λ
m
a
x
≤
M
{\displaystyle 0<\mu \leq \lambda _{min}\leq \lambda _{max}\leq M}
или
λ
m
a
x
≤
M
⇒
τ
=
2
μ
+
M
{\displaystyle \lambda _{max}\leq M\Rightarrow \tau ={\frac {2}{\mu +M}}}
или
τ
<
2
M
(
τ
=
1
M
)
{\displaystyle \tau <{\frac {2}{M}}\quad (\tau ={\frac {1}{M}})}
.
В случае
λ
m
i
n
≤
λ
m
a
x
{\displaystyle \lambda _{min}\leq \lambda _{max}}
то
∀
τ
∈
(
0
,
2
λ
m
a
x
)
:
‖
B
‖
2
=
1
{\displaystyle \forall \tau \in (0,{\frac {2}{\lambda _{max}}}):\|B\|_{2}=1}
метод сходится медленно.
Метод Зейделя - модификация метода Якоби[ править ]
x
1
=
b
12
x
2
+
b
13
x
3
+
.
.
.
+
b
1
,
m
−
1
x
m
−
1
+
b
1
m
x
m
+
c
1
x
2
=
b
21
x
1
+
b
23
x
3
+
.
.
.
+
b
2
,
m
−
1
x
m
−
1
+
b
2
m
x
m
+
c
2
x
3
=
b
31
x
1
+
b
32
x
2
+
.
.
.
+
b
3
,
m
−
1
x
m
−
1
+
b
3
m
x
m
+
c
3
…
x
m
=
b
m
1
x
1
+
b
m
2
x
2
+
b
m
3
x
3
+
.
.
.
+
b
m
,
m
−
1
x
m
−
1
+
c
m
,
{\displaystyle {\begin{matrix}&x_{1}=\qquad \quad b_{12}x_{2}+b_{13}x_{3}+...+b_{1,m-1}x_{m-1}+b_{1m}x_{m}+c_{1}\\&x_{2}=b_{21}x_{1}+\qquad \quad b_{23}x_{3}+...+b_{2,m-1}x_{m-1}+b_{2m}x_{m}+c_{2}\\&x_{3}=b_{31}x_{1}+b_{32}x_{2}\qquad \quad +...+b_{3,m-1}x_{m-1}+b_{3m}x_{m}+c_{3}\\&\dots \\&x_{m}=b_{m1}x_{1}+b_{m2}x_{2}+b_{m3}x_{3}+...+b_{m,m-1}x_{m-1}\qquad \quad +c_{m}\\\end{matrix}}\qquad {\text{,}}}
где
b
i
j
=
−
a
i
j
a
i
i
{\displaystyle b_{ij}=-{\frac {a_{ij}}{a_{ii}}}}
,
c
i
=
b
i
a
i
j
{\displaystyle c_{i}={\frac {b_{i}}{a_{ij}}}}
,
i
,
j
=
1
,
2
,
…
,
m
,
j
≠
i
{\displaystyle i,j=1,2,\dots ,m,j\not =i}
Метод Зейделя:
x
1
=
b
12
x
2
+
b
13
x
3
+
.
.
.
+
b
1
m
x
m
+
c
1
x
2
=
b
21
x
1
+
b
23
x
3
+
.
.
.
+
b
2
m
x
m
+
c
2
x
3
=
b
31
x
1
+
b
32
x
2
+
.
.
.
+
b
3
m
x
m
+
c
3
…
x
m
=
b
m
1
x
1
+
b
m
2
x
2
+
b
m
3
x
3
+
.
.
.
+
+
c
m
{\displaystyle {\begin{matrix}&x_{1}=\qquad \quad b_{12}x_{2}+b_{13}x_{3}+...+b_{1m}x_{m}+c_{1}\\&x_{2}=b_{21}x_{1}+\qquad \quad b_{23}x_{3}+...+b_{2m}x_{m}+c_{2}\\&x_{3}=b_{31}x_{1}+b_{32}x_{2}\qquad \quad +...+b_{3m}x_{m}+c_{3}\\&\dots \\&x_{m}=b_{m1}x_{1}+b_{m2}x_{2}+b_{m3}x_{3}+...+\qquad \quad +c_{m}\\\end{matrix}}}
Введем:
B
1
=
(
0
0
…
0
b
21
0
…
0
…
b
m
1
b
m
2
…
0
)
,
B
2
=
(
0
b
12
…
b
1
m
0
0
…
b
2
m
…
0
0
…
0
)
{\displaystyle B_{1}={\begin{pmatrix}0&0&\dots &0\\b_{21}&0&\dots &0\\\dots \\b_{m1}&b_{m2}&\dots &0\end{pmatrix}},B_{2}={\begin{pmatrix}0&b_{12}&\dots &b_{1m}\\0&0&\dots &b_{2m}\\\dots \\0&0&\dots &0\end{pmatrix}}}
- верхняя и нижняя треугольные матрицы.
x
(
k
+
1
)
=
B
1
x
(
k
+
1
)
+
B
2
x
(
k
)
+
c
B
=
B
1
+
B
2
⇒
x
¯
{\displaystyle x^{(k+1)}=B_{1}x^{(k+1)}+B_{2}x^{(k)}+c\qquad B=B_{1}+B_{2}\Rightarrow {\overline {x}}}
удовлетворяет:
x
¯
=
B
1
x
¯
+
B
2
x
¯
+
c
{\displaystyle {\overline {x}}=B_{1}{\overline {x}}+B_{2}{\overline {x}}+c}
Теорема. Пусть
‖
B
‖
<
1
{\displaystyle \|B\|<1}
, где
‖
B
‖
{\displaystyle \|B\|}
- одна из норм
‖
B
‖
∞
,
‖
B
‖
1
{\displaystyle \|B\|_{\infty },\|B\|_{1}}
. Тогда
∀
x
(
0
)
{\displaystyle \forall x^{(0)}}
метод Зейделя сходится со скоростью геометрической прогресии с
q
≤
‖
B
‖
{\displaystyle q\leq \|B\|}
. (без доказательства)
Теорема. Пусть выполнено условие
‖
B
1
‖
+
‖
B
2
‖
<
1
{\displaystyle \|B_{1}\|+\|B_{2}\|<1}
. Тогда
∀
x
(
0
)
{\displaystyle \forall x^{(0)}}
метод Зейделя сходится и верна оценка погрешности:
‖
x
(
n
)
−
x
¯
‖
≤
q
n
‖
x
(
0
)
−
x
¯
‖
{\displaystyle \|x^{(n)}-{\overline {x}}\|\leq q^{n}\|x^{(0)}-{\overline {x}}\|}
, где
q
=
‖
B
2
‖
1
−
‖
B
1
‖
<
1
{\displaystyle q={\frac {\|B_{2}\|}{1-\|B_{1}\|}}<1}
Теорема.
A
{\displaystyle A}
- симметричная положительно определенная матрица. Тогда
∀
x
(
0
)
{\displaystyle \forall x^{(0)}}
метод Зейделя сходится со скоростью геометрической прогресии (без доказательства)
Апостериорная оценка: Если
‖
B
‖
<
1
{\displaystyle \|B\|<1}
, то
‖
x
(
n
)
−
x
¯
‖
≤
‖
B
2
‖
1
−
‖
B
‖
‖
x
(
n
)
−
x
(
n
−
1
)
‖
,
n
≥
1
{\displaystyle \|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B_{2}\|}{1-\|B\|}}\|x^{(n)}-x^{(n-1)}\|,n\geq 1}
.
Возьмем
k
=
n
−
1
⇒
{\displaystyle k=n-1\Rightarrow }
x
(
n
)
−
x
¯
=
B
(
x
(
n
)
−
x
¯
)
+
B
2
(
x
(
n
−
1
)
−
x
(
n
)
)
{\displaystyle x^{(n)}-{\overline {x}}=B(x^{(n)}-{\overline {x}})+B_{2}(x^{(n-1)}-x^{(n)})}
‖
x
(
n
)
−
x
¯
‖
=
‖
B
‖
‖
x
(
n
)
−
x
¯
‖
+
‖
B
2
‖
‖
x
(
n
−
1
)
−
x
(
n
)
‖
⇒
‖
x
(
n
)
−
x
¯
‖
≤
‖
B
2
‖
1
−
‖
B
‖
{\displaystyle \|x^{(n)}-{\overline {x}}\|=\|B\|\|x^{(n)}-{\overline {x}}\|+\|B_{2}\|\|x^{(n-1)}-x^{(n)}\|\Rightarrow \|x^{(n)}-{\overline {x}}\|\leq {\frac {\|B_{2}\|}{1-\|B\|}}}
Для данного
ε
{\displaystyle \varepsilon }
критерий окончания:
‖
x
(
n
)
−
x
(
n
−
1
)
‖
≤
ε
2
{\displaystyle \|x^{(n)}-x^{(n-1)}\|\leq \varepsilon _{2}}
, где
ε
2
=
1
−
‖
B
‖
‖
B
2
‖
ε
{\displaystyle \varepsilon _{2}={\frac {1-\|B\|}{\|B_{2}\|}}\varepsilon }
Геометрическая интерпретация метода Зейделя
m
=
2
:
{\displaystyle m=2:}
{
a
11
x
1
+
a
12
x
2
=
b
1
a
21
x
1
+
a
22
x
2
=
b
2
{\displaystyle {\begin{cases}a_{11}x_{1}+a_{12}x_{2}=b_{1}&\\a_{21}x_{1}+a_{22}x_{2}=b_{2}&\end{cases}}}
Расчетные формулы:
x
1
(
k
+
1
)
=
b
12
x
2
(
k
)
+
c
1
b
12
=
−
a
12
a
11
c
1
=
b
1
a
11
x
2
(
k
+
1
)
=
b
21
x
1
(
k
)
+
c
2
b
21
=
−
a
21
a
22
c
2
=
b
2
a
22
{\displaystyle {\begin{matrix}x_{1}^{(k+1)}=b_{12}x_{2}^{(k)}+c_{1}&\qquad b_{12}=-{\frac {a_{12}}{a_{11}}}&\qquad c_{1}={\frac {b_{1}}{a_{11}}}\\x_{2}^{(k+1)}=b_{21}x_{1}^{(k)}+c_{2}&\qquad b_{21}=-{\frac {a_{21}}{a_{22}}}&\qquad c_{2}={\frac {b_{2}}{a_{22}}}\end{matrix}}}
Метод Якоби
Замечание. Метод Якоби ориентирован на системы с матрицами, близкими к диагональным, а метод Зейделя - на матрицы, близкие к нижним треугольным.
После вычисления
i
{\displaystyle i}
-ой компоненты по методу Зейделя (
(
k
+
1
)
{\displaystyle (k+1)}
-го приближения)
x
~
i
(
k
+
1
)
=
b
i
1
x
1
(
k
+
1
)
+
b
i
1
x
2
(
k
+
1
)
+
.
.
.
+
b
i
,
i
−
1
x
i
−
1
(
k
+
1
)
+
b
i
,
i
+
1
x
i
+
1
(
k
+
1
)
+
.
.
.
+
b
i
,
m
x
m
(
k
+
1
)
+
C
{\displaystyle {\tilde {x}}_{i}^{(k+1)}=b_{i1}x_{1}^{(k+1)}+b_{i1}x_{2}^{(k+1)}+...+b_{i,i-1}x_{i-1}^{(k+1)}+b_{i,i+1}x_{i+1}^{(k+1)}+...+b_{i,m}x_{m}^{(k+1)}+C}
Производится дополнительно смещение этой компоненты на величину
(
ω
−
1
)
(
x
~
i
(
k
+
1
)
−
x
i
(
k
)
)
{\displaystyle (\omega -1)({\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)})}
, где
ω
{\displaystyle \omega }
- параметр релаксации. То есть
i
{\displaystyle i}
-я компонента
(
k
+
1
)
{\displaystyle (k+1)}
-го приближения вычисляется по формуле:
x
i
(
k
+
1
)
=
x
~
i
(
k
+
1
)
+
(
ω
−
1
)
(
x
~
i
(
k
+
1
)
−
x
i
(
k
)
)
=
ω
x
~
i
(
k
+
1
)
+
(
1
−
ω
)
x
i
(
k
)
{\displaystyle x_{i}^{(k+1)}={\tilde {x}}_{i}^{(k+1)}+(\omega -1)({\tilde {x}}_{i}^{(k+1)}-x_{i}^{(k)})=\omega {\tilde {x}}_{i}^{(k+1)}+(1-\omega )x_{i}^{(k)}}
Компактная формула:
x
(
k
+
1
)
=
(
1
−
ω
)
x
(
k
)
+
ω
B
1
x
(
k
+
1
)
+
ω
B
2
x
(
k
)
+
ω
c
{\displaystyle x^{(k+1)}=(1-\omega )x^{(k)}+\omega B_{1}x^{(k+1)}+\omega B_{2}x^{(k)}+\omega c}
При
ω
=
1
{\displaystyle \omega =1}
получаем метод Зейделя. Если
ω
>
1
{\displaystyle \omega >1}
- метод последовательной верхней релаксации. Если
ω
<
1
{\displaystyle \omega <1}
- метод последовательной нижней релаксации.
Если
A
{\displaystyle A}
- симметричная и положительно определенная матрица, то
∀
ω
:
(
0
<
ω
<
2
)
{\displaystyle \forall \omega :(0<\omega <2)}
метод релаксации сходится.
Иногда можно выбрать
ω
>
1
{\displaystyle \omega >1}
так, чтобы метод сходился существенно быстрее, чем метод Якоби и Зейделя. Выбор параметра - зачастую экспериментально.