WikiSort.ru - Не сортированное

Общий алгоритм последовательных приближений

1. Уравнение ${\displaystyle f(x)=0}$ преобразуется к уравнению с тем же корнем вида ${\displaystyle x=\varphi (x)}$ , где ${\displaystyle \varphi (x)}$  — сжимающее отображение.
2. Задаётся начальное приближение и точность ${\displaystyle x_{0},\quad \varepsilon ,\quad i=0}$
3. Вычисляется очередная итерация ${\displaystyle x_{i+1}=\varphi (x_{i})}$
   • Если ${\displaystyle ||x_{i+1}-x_{i}||>\varepsilon }$ , то ${\displaystyle i=i+1}$ и возврат к шагу 3.
   • Иначе ${\displaystyle x=x_{i+1}}$ и остановка.

Применительно к общему случаю операторных уравнений этот метод называется методом последовательных приближений или методом простой итерации. Однако уравнение ${\displaystyle f(x)=0}$ можно преобразовывать к сжимающему отображению ${\displaystyle x=\varphi (x)}$ , имеющему тот же корень, разными способами. Это порождает ряд частных методов, имеющих как линейную, так и более высокие скорости сходимости.

Применительно к СЛАУ

Рассмотрим систему:

${\displaystyle \left\{{\begin{array}{ccc}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\end{array}}\right.}$

Для неё итерационное вычисление будет выглядеть так:

${\displaystyle \left({\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i+1}=\left({\begin{array}{cccc}a_{11}+1&a_{12}&\ldots &a_{1n}\\a_{21}&a_{22}+1&\ldots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\ldots &a_{nn}+1\end{array}}\right)\left({\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i}-\left({\begin{array}{c}b_{1}\\b_{2}\\\vdots \\b_{n}\end{array}}\right)}$

Метод будет сходится с линейной скоростью, если ${\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}$

Двойные вертикальные черты означают некоторую норму матрицы.

Одномерный случай

Оптимизация преобразования исходного уравнения ${\displaystyle f(x)=0}$ в сжимающее отображение ${\displaystyle x=\varphi (x)}$ позволяет получить метод с квадратичной скоростью сходимости.

Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации ${\displaystyle x^{*}}$ выполнялось ${\displaystyle \varphi '(x^{*})=0}$ . Будем искать решение данного уравнения в виде ${\displaystyle \varphi (x)=x+\alpha (x)f(x)}$ , тогда:

${\displaystyle \varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{*})=0}$

Воспользуемся тем, что ${\displaystyle f(x)=0}$ , и получим окончательную формулу для ${\displaystyle \alpha (x)}$ :

${\displaystyle \alpha (x)=-{\frac {1}{f'(x)}}}$

С учётом этого сжимающая функция примет вид:

${\displaystyle \varphi (x)=x-{\frac {f(x)}{f'(x)}}}$

Тогда алгоритм нахождения численного решения уравнения ${\displaystyle f(x)=0}$ сводится к итерационной процедуре вычисления:

${\displaystyle x_{i+1}=x_{i}-{\frac {f(x_{i})}{f'(x_{i})}}}$

Многомерный случай

Обобщим полученный результат на многомерный случай.

Выбирая некоторое начальное приближение ${\textstyle {\vec {x}}^{[0]}}$ , находят последовательные приближения ${\displaystyle {\vec {x}}^{[j+1]}}$ путём решения систем уравнений:

${\displaystyle f_{i}+\sum _{k=1}^{n}{\frac {\partial f_{i}}{\partial x_{k}}}(x_{k}^{[j+1]}-x_{k}^{[j]})=0,\quad i=1,2,\ldots ,n}$ ,

где ${\displaystyle x^{[j]}=\left(x_{1}^{[j]}\ldots x_{k}^{[j]}\ldots x_{n}^{[j]}\right),\quad j=0,1,2,\ldots }$ .