Текущая версия страницы пока
не проверялась опытными участниками и может значительно отличаться от
версии , проверенной 11 мая 2019 года; проверки требуют
13 правок .
Текущая версия страницы пока
не проверялась опытными участниками и может значительно отличаться от
версии , проверенной 11 мая 2019 года; проверки требуют
13 правок .
Метод итерации или метод простой итерации — численный метод решения системы линейных алгебраических уравнений . Суть метода заключается в нахождении по приближённому значению величины следующего приближения, являющегося более точным.
Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (в результате итерационного процесса). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня.
Пусть дана СЛАУ вида:
A
x
=
B
{\displaystyle Ax=B}
, где
A
=
[
a
11
⋯
a
1
n
⋮
⋱
⋮
a
n
1
⋯
a
n
n
]
,
x
=
[
x
1
⋮
x
n
]
,
B
=
[
b
1
⋮
b
n
]
{\displaystyle A={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\cdots &a_{nn}\end{bmatrix}},\ x={\begin{bmatrix}x_{1}\\\vdots \\x_{n}\end{bmatrix}},\ B={\begin{bmatrix}b_{1}\\\vdots \\b_{n}\end{bmatrix}}}
Предполагается, что
a
i
i
≠
0
,
i
=
1
,
n
¯
{\displaystyle a_{ii}\neq 0,\ i={\overline {1,n}}}
. Выразим
x
1
{\displaystyle x_{1}}
через первое уравнение,
x
2
{\displaystyle x_{2}}
— через второе и т. д.[1] :
{
x
1
=
b
1
a
11
−
a
12
a
11
x
2
−
⋯
−
a
1
n
a
11
x
n
⋮
x
n
=
b
n
a
n
n
−
a
n
1
a
n
n
x
1
−
a
n
2
a
n
n
x
2
−
⋯
−
a
n
,
n
−
1
a
n
n
x
n
−
1
{\displaystyle \left\{{\begin{array}{c}x_{1}={\dfrac {b_{1}}{a_{11}}}-{\dfrac {a_{12}}{a_{11}}}x_{2}-\cdots -{\dfrac {a_{1n}}{a_{11}}}x_{n}\\\vdots \\x_{n}={\dfrac {b_{n}}{a_{nn}}}-{\dfrac {a_{n1}}{a_{nn}}}x_{1}-{\dfrac {a_{n2}}{a_{nn}}}x_{2}-\cdots -{\dfrac {a_{n,n-1}}{a_{nn}}}x_{n-1}\end{array}}\right.}
Пусть
α
i
j
=
{
−
a
i
j
a
i
i
,
i
≠
j
,
0
,
i
=
j
,
{\displaystyle \alpha _{ij}=\left\lbrace {\begin{array}{cc}-{\dfrac {a_{ij}}{a_{ii}}},&i\neq j,\\0,&i=j,\end{array}}\right.}
β
i
=
b
i
a
i
i
,
{\displaystyle \beta _{i}={\frac {b_{i}}{a_{ii}}},}
для
i
,
j
=
1
,
n
¯
{\displaystyle i,j={\overline {1,n}}}
и пусть
α
=
[
α
11
⋯
α
1
n
⋮
⋱
⋮
α
n
1
⋯
α
n
n
]
,
β
=
[
β
1
⋮
β
n
]
{\displaystyle \alpha ={\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}},\ \beta ={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}}
Тогда исходная система преобразуется к виду
x
=
β
+
α
x
{\displaystyle x=\beta +\alpha x}
.
За нулевое приближение примем столбец свободных членов:
[
x
1
(
0
)
⋮
x
n
(
0
)
]
=
[
β
1
⋮
β
n
]
{\displaystyle {\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}}
Тогда
[
x
1
(
1
)
⋮
x
n
(
1
)
]
=
[
β
1
⋮
β
n
]
+
[
α
11
⋯
α
1
n
⋮
⋱
⋮
α
n
1
⋯
α
n
n
]
[
x
1
(
0
)
⋮
x
n
(
0
)
]
{\displaystyle {\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}}
— первое приближение,
[
x
1
(
2
)
⋮
x
n
(
2
)
]
=
[
β
1
⋮
β
n
]
+
[
α
11
⋯
α
1
n
⋮
⋱
⋮
α
n
1
⋯
α
n
n
]
[
x
1
(
1
)
⋮
x
n
(
1
)
]
{\displaystyle {\begin{bmatrix}x_{1}^{(2)}\\\vdots \\x_{n}^{(2)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix}}}
— второе приближение и т.д.
Общая формула итерационного процесса имеет вид
x
(
k
)
=
β
+
α
x
(
k
−
1
)
,
k
=
1
,
2
,
…
{\displaystyle x^{(k)}=\beta +\alpha x^{(k-1)},\ k=1,2,\dots }
За решение исходной системы принимается
x
∗
=
lim
k
→
∞
x
(
k
)
{\displaystyle x^{*}=\lim _{k\to \infty }x^{(k)}}
.
Необходимое и достаточное условие сходимости:
ρ
(
α
)
<
1
{\displaystyle \rho (\alpha )<1}
, где —
ρ
(
α
)
{\displaystyle \rho (\alpha )}
спектральный радиус
α
{\displaystyle \alpha }
[2] .
Достаточное условие сходимости:
‖
α
‖
<
1
{\displaystyle \Vert \alpha \Vert <1}
[2] .
В частности при выборе нормы , подчинённой векторной
‖
x
‖
∞
=
max
1
≤
i
≤
n
|
x
i
|
{\displaystyle \|x\|_{\infty }=\max \limits _{1\leq i\leq n}|x_{i}|}
условие сходимости приобретает вид
max
j
=
1
n
|
α
i
j
|
<
1
{\displaystyle \max _{j=1}^{n}\vert \alpha _{ij}\vert <1}
(где
i
=
1
,
2
,
…
,
n
{\displaystyle i=1,2,\dots ,n}
).
При выборе нормы
‖
x
‖
1
=
∑
i
=
1
n
|
x
i
|
{\displaystyle \|x\|_{1}=\sum _{i=1}^{n}|x_{i}|}
условие приобретает вид
∑
i
=
1
i
≠
j
n
|
α
i
j
|
<
1
{\displaystyle \sum _{i=1 \atop i\neq j}^{n}\vert \alpha _{ij}\vert <1}
(где
j
=
1
,
2
,
…
,
n
{\displaystyle j=1,2,\dots ,n}
), что называют условием диагонального преобладания исходной матрицы
A
{\displaystyle A}
.
Пусть
x
{\displaystyle x}
— вектор точного решения. Тогда можно получить следующие оценки погрешности приближённого решения
x
(
k
)
{\displaystyle x^{(k)}}
на
k
{\displaystyle k}
-м шаге алгоритма[3] :
‖
x
−
x
(
k
)
‖
≤
|
|
α
|
|
k
|
|
x
(
0
)
|
|
+
‖
α
‖
k
1
−
‖
α
‖
‖
β
‖
.
{\displaystyle \Vert x-x^{(k)}\Vert \leq ||\alpha ||^{k}||x^{(0)}||+{\frac {\Vert \alpha \Vert ^{k}}{1-\Vert \alpha \Vert }}\Vert \beta \Vert .}
‖
x
−
x
(
k
)
‖
≤
‖
α
‖
1
−
‖
α
‖
‖
x
(
k
)
−
x
(
k
−
1
)
‖
.
{\displaystyle \Vert x-x^{(k)}\Vert \leq {\frac {\Vert \alpha \Vert }{1-\Vert \alpha \Vert }}\Vert x^{(k)}-x^{(k-1)}\Vert .}
Прямые методы Итерационные методы Общее