Одной из целей этого метода состоит в нахождении приближенных решений уравнений. Одним из таких методов является метод простой итерации.
Метод простой итерации
Метод простой итерации - один из самых простейших численных методов для решения уравнений.
Идея метода простой итерации.
Пусть нам необходимо решить уравнение f(x)=0.
Вначале для его решения приведем его к эквивалентному уравнению вида
Рассмотрим пример такого приведения:
Привести уравнение arcsin(2x+1) −x2=0 к виду x=φ(x).
Решение.
Здесь есть три способа такого преобразования:
-
1 способ:
arcsin(2x+1) =x2sin(arcsin(2x+1) )=sin(x2)2x+1=sinx2x=sinx2−12 -
2 способ:
x=x+arcsin(2x+1) −x2 -
3 способ:
arcsin(2x+1) =x2x=√arcsin(2x+1)
После этого каким-либо образом выбирается начальное приближение x0, вычисляется значение φ(x0) и находится уточненное значение x1=φ(x0). Следующее уточненное значение будет находиться как x2=φ(x1) и т.д. Каждый такой шаг называется шагом итерации.
Сформулируем и докажем следующую теорему:
Функция φ(x) определена и дифференцируема на отрезке [a,b] и φ(x)∈[a,b]. Тогда, если \textbar ${\varphi }'\left(x\right)|
-
Процесс итерации xn=φ(xn−1) сходится независимо от начального положения x0;
-
limn→∞xn =X -- единственный корень уравнения x=φ(x) на отрезке [a,b].
Доказательство.
-
\item Так как X=φ(x) и xn=φ(xn−1), то
xn−X=φ(xn−1)−φ(x)=(φ(xn−1)−φ(x))xn−1−xxn−1−x==φ(xn−1)−φ(x)xn−1−x⋅xn−1−xПо теореме о среднем, получаем
φ(xn−1)−φ(x)xn−1−x=φ′(C)То есть
xn−X=φ′(C)⋅(xn−1−x)Пусть M=max|φ′(x)|, тогда |xn−X|≤M|xn−1−x|. Также|xn−1−X|≤M|xn−2−x|. Но тогда получим
|xn−X|≤M|xn−1−x|≤M2|xn−2−x|и т.д.То есть получим, что
|xn−X|≤Mn|x0−x|Следовательно, для того чтобы метод сходился нужно, чтобы M=max|φ′(x)| было меньше единицы, значит $\left|{\varphi }'\left(x\right)\right|
-
Рассмотрим xn=φ(xn−1) и xn+1=φ(xn).
xn+1−xn=φ(xn)−φ(xn−1)По теореме о среднем xn+1−xn=f′(xn)(xn−xn−1).
Так как $\left|{\varphi }'\left(x\right)\right|\le q
Рассмотрим теперь f(x)=x−φ(x), f′(x)=1−φ′(x)≥1−q. Значит, |xn−φ(xn)|=|f(xn)−f(X)|=|xn−X||f′(xn)|≥(1−q)|xn−X|. Следовательно, |xn−X|≤|xn−φ(xn)|1−q≤|xn+1−xn|1−q.
Из двух полученных неравенств, имеем
|xn−X|≤q1−q|xn−xn−1|Пусть |xn−X|≤ε, тогда x0,x1,…,xn нужно вычислять до тех пор, пока не выполнится неравенство |xn−xn−1|≤ε(1−q)q, тогда получим, что X=xn±ε. Отсюда следует, что X корень уравнения x=φ(x), то есть X=φ(X).
Предположим, что это уравнение имеет еще один корень X′=φ(X′). Отсюда X′−X=φ(X′)−φ(X), тогда (X′−X)|1−φ′(C)|=0. Значит X′=X.
Теорема доказана.
Из теоремы будет вытекать погрешность метода простой итерации. Она определяется следующей формулой:
Также из нее можно выделить критерий окончания метода простой итерации. Он говорит, что процесс итерации необходимо продолжать до выполнения следующего неравенства:
Рассмотрим теперь на примере использование метода простой итерации.
Решить уравнение sinx−x2=0 с точностью до ε=0,001.
Решение.
Вначале приведем уравнение к виду x=φ(x).
sinx=x2Очевидно, что корень уравнения находит на отрезке [π6,π3].
Найдем φ(x):
φ′(x)=xcosx−sinxx2Она возрастает на отрезке [π6,π3], следовательно принимает максимальное значение, при x=π3. |φ′(x)|≤|φ′(π3)|≈0,312.
Условие выполняется, $q |xn−xn−1|≤ε
Это неравенство выполнится на 5 шаге.
Приведем таблицу промежуточных решений, взяв за x0 единицу:
Ответ: приближенное значение с заданной точностью -- 0,8765.
