Одной из целей этого метода состоит в нахождении приближенных решений уравнений. Одним из таких методов является метод простой итерации.
Метод простой итерации
Метод простой итерации - один из самых простейших численных методов для решения уравнений.
Идея метода простой итерации.
Пусть нам необходимо решить уравнение $f\left(x\right)=0$.
Вначале для его решения приведем его к эквивалентному уравнению вида
Рассмотрим пример такого приведения:
Привести уравнение ${arcsin \left(2x+1\right)\ }-x^2=0$ к виду $x=\varphi (x)$.
Решение.
Здесь есть три способа такого преобразования:
-
1 способ:
\[{arcsin \left(2x+1\right)\ }=x^2\] \[sin({arcsin \left(2x+1\right)\ })=sin(x^2)\] \[2x+1=sinx^2\] \[x=\frac{sinx^2-1}{2}\] -
2 способ:
\[{x=x+arcsin \left(2x+1\right)\ }-x^2\] -
3 способ:
\[{arcsin \left(2x+1\right)\ }=x^2\] \[x=\sqrt{{arcsin \left(2x+1\right)\ }}\]
После этого каким-либо образом выбирается начальное приближение $x_0$, вычисляется значение $\varphi (x_0)$ и находится уточненное значение $x_1=\varphi (x_0)$. Следующее уточненное значение будет находиться как $x_2=\varphi (x_1)$ и т.д. Каждый такой шаг называется шагом итерации.
Сформулируем и докажем следующую теорему:
Функция $\varphi (x)$ определена и дифференцируема на отрезке $[a,b]$ и $\varphi (x)\in [a,b]$. Тогда, если \textbar ${\varphi }'\left(x\right)|
-
Процесс итерации $x_n=\varphi (x_{n-1})$ сходится независимо от начального положения $x_0$;
-
${\mathop{lim}_{n\to \infty } x_n\ }=X$ -- единственный корень уравнения $x=\varphi (x)$ на отрезке $[a,b]$.
Доказательство.
-
\item Так как $X=\varphi (x)$ и $x_n=\varphi (x_{n-1})$, то
\[x_n-X=\varphi \left(x_{n-1}\right)-\varphi \left(x\right)=\left(\varphi \left(x_{n-1}\right)-\varphi \left(x\right)\right)\frac{x_{n-1}-x}{x_{n-1}-x}=\] \[=\frac{\varphi \left(x_{n-1}\right)-\varphi \left(x\right)}{x_{n-1}-x}\cdot x_{n-1}-x\]По теореме о среднем, получаем
\[\frac{\varphi \left(x_{n-1}\right)-\varphi \left(x\right)}{x_{n-1}-x}=\varphi '(C)\]То есть
\[x_n-X={\varphi }'\left(C\right)\cdot (x_{n-1}-x)\]Пусть $M=max |{\varphi }'\left(x\right)|$, тогда $|x_n-X|\le M|x_{n-1}-x|$. Также$|x_{n-1}-X|\le M|x_{n-2}-x|$. Но тогда получим
\[\left|x_n-X\right|\le M\left|x_{n-1}-x\right|\le M^2\left|x_{n-2}-x\right|и\ т.д.\]То есть получим, что
\[\left|x_n-X\right|\le M^n\left|x_0-x\right|\]Следовательно, для того чтобы метод сходился нужно, чтобы $M=max |{\varphi }'\left(x\right)|$ было меньше единицы, значит $\left|{\varphi }'\left(x\right)\right|
-
Рассмотрим $x_n=\varphi (x_{n-1})$ и $x_{n+1}=\varphi (x_n)$.
\[x_{n+1}-x_n=\varphi \left(x_n\right)-\varphi (x_{n-1})\]По теореме о среднем $x_{n+1}-x_n=f'\left(x_n\right)(x_n-x_{n-1})$.
Так как $\left|{\varphi }'\left(x\right)\right|\le q
Рассмотрим теперь $f\left(x\right)=x-\varphi \left(x\right)$, $f^{'\left(x\right)}=1-{\varphi }^{'\left(x\right)}\ge 1-q$. Значит, $\left|x_n-\varphi \left(x_n\right)\right|=\left|f\left(x_n\right)-f\left(X\right)\right|=\left|x_n-X\right|\left|f'\left(x_n\right)\right|\ge \left(1-q\right)|x_n-X|$. Следовательно, $|x_n-X|\le \frac{\left|x_n-\varphi \left(x_n\right)\right|}{1-q}\le \frac{|x_{n+1}-x_n|}{1-q}$.
Из двух полученных неравенств, имеем
\[|x_n-X|\le \frac{q}{1-q}|x_n-x_{n-1}|\]Пусть $|x_n-X|\le \varepsilon $, тогда $x_0,x_1,\dots ,x_n$ нужно вычислять до тех пор, пока не выполнится неравенство $|x_n-x_{n-1}|\le \frac{\varepsilon (1-q)}{q}$, тогда получим, что $X=x_n\pm \varepsilon $. Отсюда следует, что $X$ корень уравнения $x=\varphi (x)$, то есть $X=\varphi (X)$.
Предположим, что это уравнение имеет еще один корень $X'=\varphi \left(X'\right)$. Отсюда $X'-X=\varphi \left(X'\right)-\varphi \left(X\right)$, тогда $\left(X'-X\right)\left|1-{\varphi }'\left(C\right)\right|=0$. Значит $X'=X$.
Теорема доказана.
Из теоремы будет вытекать погрешность метода простой итерации. Она определяется следующей формулой:
Также из нее можно выделить критерий окончания метода простой итерации. Он говорит, что процесс итерации необходимо продолжать до выполнения следующего неравенства:
Рассмотрим теперь на примере использование метода простой итерации.
Решить уравнение $sinx-x^2=0$ с точностью до $\varepsilon =0,001$.
Решение.
Вначале приведем уравнение к виду $x=\varphi (x)$.
\[sinx=x^2\] \[x=\frac{sinx}{x}\]Очевидно, что корень уравнения находит на отрезке $\left[\frac{\pi }{6},\frac{\pi }{3}\right]$.
Найдем $\varphi (x)$:
\[{\varphi }'\left(x\right)=\frac{xcosx-sinx}{x^2}\]Она возрастает на отрезке $\left[\frac{\pi }{6},\frac{\pi }{3}\right]$, следовательно принимает максимальное значение, при $x=\frac{\pi }{3}$. $\left|{\varphi }'\left(x\right)\right|\le \left|{\varphi }'\left(\frac{\pi }{3}\right)\right|\approx 0,312$.
Условие выполняется, $q \[|x_n-x_{n-1}|\le \varepsilon \]
Это неравенство выполнится на 5 шаге.
Приведем таблицу промежуточных решений, взяв за $x_0$ единицу:
Ответ: приближенное значение с заданной точностью -- $0,8765$.
