Метод последовательных приближений

Ме́тод после́довательных приближе́ний (метод повторных подстановок, метод простой итерации), один из общих методов приближённого решения уравнений. В ряде случаев хорошая сходимость построенных этим методом приближений позволяет применять его в практике вычислений.

Пусть ${\displaystyle E}$ – некоторое множество, на котором задан оператор ${\displaystyle A}$, отображающий ${\displaystyle E}$ в себя. Требуется найти неподвижную точку этого оператора, т. е. решение уравнения

${\displaystyle Ax=x,\,\,x\in E.}$ (1)

Пусть это уравнение имеет решение ${\displaystyle x_{*}}$ и указано какое-либо его начальное приближение ${\displaystyle x_{0}\in E}$. С помощью рекуррентного соотношения

${\displaystyle x_{n+1}=Ax_{n},\quad n=0,1,2,\ldots ,}$ (2)

определяется последовательность ${\displaystyle \{x_{n}\}_{n=0}^{\infty }}$. Построение этой последовательности и исследование вопроса о её сходимости обычно называют методом последовательных приближений.

Для исследования сходимости последовательности (2), а также для доказательства существования решения уравнения (1) широко применяется сформулированный ниже принцип сжимающих отображений.

Если ${\displaystyle E}$ – полное метрическое пространство с метрикой ${\displaystyle \rho }$ и для всех ${\displaystyle x}$, ${\displaystyle y\in E}$

${\displaystyle \rho (Ax,Ay)\leqslant \alpha \rho (x,y),\quad 0<\alpha ={\text{const}}<1}$,

то уравнение (1) имеет единственное решение, которое является пределом последовательных приближений (2) при любом начальном приближении ${\displaystyle x_{0}}$. Для приближения ${\displaystyle x_{n}}$ верна следующая оценка его близости к решению ${\displaystyle x_{*}}$:

${\displaystyle \rho (x_{n},x_{*})\leqslant {\dfrac {\alpha ^{n}}{1-\alpha }}\rho (Ax_{0},x_{0})}$.

Пусть, например, ${\displaystyle E=\mathbb {R} ^{n}}$ – ${\displaystyle n}$-мерное пространство и оператор ${\displaystyle A}$ в (1) имеет вид ${\displaystyle Ax=Bx+c}$, где ${\displaystyle B=}$
${\displaystyle midb_{ik}}$
${\displaystyle mid}$ – квадратная матрица ${\displaystyle n}$-го порядка, ${\displaystyle c=(c_{1},\ldots ,c_{n})}$ – заданный, а ${\displaystyle x=(x_{1},\ldots ,x_{n})}$ – искомый векторы в ${\displaystyle \mathbb {R} ^{n}}$. Если в этом пространстве метрика определена формулой ${\displaystyle \rho (x,y)=\max \limits _{1\leqslant i\leqslant n}\mid x_{i}-y_{i}\mid }$ и элементы матрицы ${\displaystyle B}$ удовлетворяют условию ${\displaystyle \sum _{k=1}^{n}\mid b_{ik}\mid <1}$ для всех ${\displaystyle i=1,\ldots ,n}$, то из принципа сжимающих отображений следует, что система алгебраических уравнений (1) имеет в ${\displaystyle \mathbb {R} ^{n}}$ единственное решение, которое можно вычислить со сколь угодно высокой точностью, исходя из произвольного вектора ${\displaystyle x_{0}=(x_{1}^{(0)},\ldots ,x_{n}^{(0)})}$.