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}
