Назад Метод половинного деления
Наверх: Приближённое нахождение корней уравнений
Вперед: Метод секущих

Untitled Document

Ядерное оружие | Графика | Математика | Физика | Заказать диплом | Информатика | ТКМ | Электротехника | Атомная энергетика | Лекции

Метод простых итераций

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

Заметим, что такое преобразование можно вести разными способами, и при этом будут получаться разные функции $ {\varphi}(x)$ в правой части уравнения. Уравнение $ f(x)=0$ эквивалентно уравнению $ x=x+{\lambda}(x)f(x)$ при любой функции $ {\lambda}(x)\ne0$. Таким образом, можно взять $ {\varphi}(x)=x+{\lambda}(x)f(x)$ и при этом выбрать функцию (или постоянную) $ {\lambda}\ne0$ так, чтобы функция $ {\varphi}(x)$ удовлетворяла тем свойствам, которые понадобятся нам для обеспечения нахождения корня уравнения.

Для нахождения корня уравнения $ x={\varphi}(x)$ выберем какое-либо начальное приближение $ x_0$ (расположенное, по возможности, близко к корню $ x^*$). Далее будем вычислять последующие приближения

$\displaystyle x_1,x_2,\dots,x_i,x_{i+1},\dots$

по формулам

$\displaystyle x_1={\varphi}(x_0);x_2={\varphi}(x_1);\dots;x_{i+1}={\varphi}(x_i);\dots\quad,$

то есть используя каждое вычисленное приближение к корню в качестве аргумента функции $ {\varphi}(x)$ в очередном вычислении. Такие вычисления по одной и той же формуле $ x_{i+1}={\varphi}(x_i)$, когда полученное на предыдущем шаге значение используется на последующем шаге, называются итерациями. Итерациями называют часто и сами значения $ x_i$, полученные в этом процессе (то есть, в нашем случае, последовательные приближения к корню).

Заметим: тот факт, что $ x^*$ -- корень уравнения $ x={\varphi}(x)$, означает, что $ x^*$ есть абсцисса точки пересечения графика $ y={\varphi}(x)$ с прямой $ y=x$. Если же при каком-либо $ x_0$ вычислено значение $ x_1={\varphi}(x)$ и взято в качестве нового аргумента функции, то это означает, что через точку графика $ (x_0;{\varphi}(x_0))$ проводится горизонталь до прямой $ y=x$, а оттуда опускается перпендикуляр на ось $ Ox$. Там и будет находиться новый аргумент $ x_1$.

Рис.9.3.Точка $ x^*$ -- решение уравнения $ x={\varphi}(x)$. Построение точки $ x_1$ по точке $ x_0$


Проследим, как изменяются последовательные приближения $ x_i$ при различных вариантах взаимного расположения графика $ y={\varphi}(x)$ и прямой $ y=x$.

1). График $ y={\varphi}(x)$ расположен, по крайней мере в некоторой окрестности корня, включающей начальное приближение $ x_0$, в некотором угле со сторонами, имеющими наклон менее $ \frac{\pi}{4}$ к горизонтали (то есть стороны угла -- прямые $ y=f(x^*)\pm k(x-x^*)$, где $ 0<k<1$):

 

Рис.9.4.График пересекает прямую $ y=x$ под малым углом: варианты расположения


Если предположить вдобавок, что функция $ {\varphi}(x)$ имеет производную $ {\varphi}'(x)$, то этот случай соответствует тому, что выполнено неравенство $ \vert{\varphi}'(x)\vert<1$, при $ x$, близких к корню $ x^*$. Проследим в этом случае за поведением последовательных приближений $ x_0,x_1,\dots.$

Рис.9.5.Сходящиеся к корню приближения в случае $ \vert{\varphi}(x)\vert<1$: два варианта


Мы видим, что каждое следующее приближение $ x_{i+1}$ будет в этом случае расположено ближе к корню $ x^*$, чем предыдущее приближение $ x_i$. При этом, если график при $ x<x^*$ лежит ниже горизонтали $ y={\varphi}(x^*)$, а при $ x>x^*$ -- выше её (что, в случае наличия производной, верно, если $ 0<{\varphi}'(x)<1$), то приближения $ x_i$ ведут себя монотонно: если $ x_0<x^*$, то последовательность $ \{x_i\}$ монотонно возрастает и стремится к $ x^*$, а если $ x_0>x^*$, то монотонно убывает и также стремится к $ x^*$. Если же график функции $ {\varphi}(x)$ лежит выше горизонтали $ y={\varphi}(x^*)$ при $ x<x^*$ и ниже её при $ x>x^*$ (это так, если $ -1<{\varphi}'(x)<0$), то последовательные приближения $ x_i$ ведут себя иначе: они "скачут" вокруг корня $ x^*$, с каждым скачком приближаясь к нему, но так же стремятся к $ x^*$ при $ i\to\infty$.

Заметим, что если функция $ {\varphi}(x)$ не монотонна в окрестности точки $ x^*$, то последовательные приближения могут вести себя нерегулярно (то есть не монотонно и не оказываясь попеременно то левее, то правее корня, а делая скачки относительно корня при произвольных номерах (см. следующий чертёж):

Рис.9.6.В случае немонотонной функции $ {\varphi}$ сходящиеся итерации могут вести себя нерегулярно


2). График $ y={\varphi}(x)$ расположен, по крайней мере в некоторой окрестности корня, вне некоторого угла со сторонами, имеющими наклон более $ \frac{\pi}{4}$ к горизонтали (то есть стороны угла -- прямые $ y=f(x^*)\pm k(x-x^*)$, где $ k>1$):

Рис.9.7.График пересекает прямую $ y=x$ под большим углом: варианты расположения


Если функция $ {\varphi}(x)$ имеет производную $ {\varphi}'(x)$, то в этом случае при $ x$, близких к корню $ x^*$, выполнено неравенство $ \vert{\varphi}'(x)\vert>1$.

Рис.9.8.Числа $ x_0,x_1,x_2,\dots$ расходятся в случае $ \vert{\varphi}(x)\vert>1$: два варианта


Каждая следующая итерация $ x_{i+1}$ будет в этом случае расположена дальше от корня $ x^*$, чем предыдущая, $ x_i$. При этом, в зависимости от того, пересекает ли график прямую $ y=x$ "снизу вверх" или "сверху вниз" (см. рис.), последовательность $ \{x_i\}$ монотонно удаляется от корня $ x^*$ или же итерации удаляются от $ x^*$, оказываясь попеременно то справа, то слева от корня.

Ещё одно замечание: если не выполнено ни условие $ {\vert{\varphi}'(x)\vert<1}$, ни условие $ {\vert{\varphi}'(x)\vert>1}$, то итерации $ x_1,x_2,x_3,\dots$ могут зацикливаться. На чертеже ниже приведён пример зацикливания, когда уравнение имеет вид $ x=2x^*-x$.

Рис.9.9.Пример зацикливания итераций


Мы видим, что для сходимости итераций к корню, вообще говоря, не обязательно наличие производной у функции $ {\varphi}(x)$. Однако метод итераций гораздо удобнее формулировать в терминах, связанных со значениями производной. Именно так мы и сформулируем наши наблюдения в виде теоремы.

        Теорема 9.3   Если функция $ {\varphi}(x)$ имеет производную в некоторой окрестности $ E$ корня $ x^*$ уравнения $ x={\varphi}(x)$, причём $ \vert{\varphi}'(x)\vert\leqslant {\gamma}<1$ при $ x\in E$, то последовательность итераций $ x_{i+1}={\varphi}(x_i)$, полученных при $ i=1,2,3,\dots$, начиная с $ x_0\in E$, сходится к корню $ x^*$.

При этом скорость сходимости задаётся неравенствами

$\displaystyle \vert x_i-x^*\vert\leqslant {\gamma}^i\vert x_0-x^*\vert,\quad i=1,2,3,\dots,$

$\displaystyle \vert x_{i+1}-x_i\vert\leqslant 4{\delta}{\gamma}^i,$

где $ 2{\delta}$ -- длина окрестности $ E$, а точность $ i$-го приближения -- оценкой

$\displaystyle \vert x_i-x^*\vert\leqslant 2{\delta}{\gamma}^i.$

        Доказательство.     Пусть $ x_0\in E$. По формуле конечных приращений, применённой к отрезку между точками $ x_0$ и $ x^*$, получаем

$\displaystyle {\varphi}(x_0)-{\varphi}(x^*)={\varphi}'(c_0)(x_0-x^*),$

где $ c_0$ лежит между $ x_0$ и $ x^*$. Значит,

$\displaystyle \vert{\varphi}(x_0)-{\varphi}(x^*)\vert\leqslant {\gamma}\vert x_0-x^*\vert,$

то есть

$\displaystyle \vert x_1-x^*\vert\leqslant {\gamma}\vert x_0-x^*\vert$

(напомним, что $ {\varphi}(x_0)=x_1$ и $ {\varphi}(x^*)=x^*$). Повторяя рассуждения для точек $ x_1,x_2,\dots,x_{i-1},x_i$ вместо $ x_0$, получаем:

$\displaystyle \vert x_2-x^*\vert=\vert{\varphi}(x_1)-{\varphi}(x^*)\vert\leqslant {\gamma}\vert x_1-x^*\vert\leqslant {\gamma}^2\vert x_0-x^*\vert;$   
$\displaystyle \vert x_3-x^*\vert=\vert{\varphi}(x_2)-{\varphi}(x^*)\vert\leqslant {\gamma}\vert x_2-x^*\vert\leqslant {\gamma}^3\vert x_0-x^*\vert;$   
$\displaystyle \dots$   
$\displaystyle \vert x_i-x^*\vert=\vert{\varphi}(x_{i-1})-{\varphi}(x^*)\vert\leqslant {\gamma}\vert x_{i-1}-x^*\vert\leqslant {\gamma}^i\vert x_0-x^*\vert;$   
$\displaystyle \vert x_{i+1}-x^*\vert=\vert{\varphi}(x_i)-{\varphi}(x^*)\vert\leqslant {\gamma}\vert x_i-x^*\vert\leqslant {\gamma}^{i+1}\vert x_0-x^*\vert;$   
$\displaystyle \dots$   

Так как $ 0<{\gamma}<1$, последовательность $ {\gamma}^i\vert x_0-x^*\vert$ стремится к 0 при $ i\to\infty$. Значит, $ x_i\to x^*$ при $ i\to\infty$.

Неравенство $ \vert x_i-x^*\vert\leqslant 2{\delta}{\gamma}^i$ очевидно, поскольку из того, что $ x_0$ и $ x^*$ лежат в окрестности $ E$ длины $ 2{\delta}$, следует, что $ \vert x_0-x^*\vert\leqslant 2{\delta}$.

Поскольку

$\displaystyle \vert x_{i+1}-x_i\vert\leqslant \vert x_{i+1}-x^*\vert+\vert x_i-x^*\vert,$

мы имеем

$\displaystyle \vert x_{i+1}-x_i\vert\leqslant {\gamma}^{i+1}\vert x_0-x^*\vert+... ...mma}+1)\vert x_0-x^*\vert< {\gamma}^i\cdot2\cdot2{\delta}=4{\delta}{\gamma}^i,$

так как $ {\gamma}+1<2$ и $ \vert x_0-x^*\vert\leqslant 2{\delta}.$     

        Определение 9.1   Доказанные оценки показывают, что скорость сходимости итераций к корню не меньше, чем у геометрической прогрессии со знаменателем $ {\gamma}$, где $ {\gamma}$ -- величина, ограничивающая сверху абсолютную величину производной. Тем самым, чем меньше $ {\gamma}>0$, тем быстрее сходятся итерации. Наиболее быстро они будут сходиться, если график $ y={\varphi}(x)$ пересекает прямую $ y=x$, имея горизонтальную касательную, то есть при $ {\varphi}(x^*)=0$ (и, разумеется, при выборе начального приближения $ x_0$ достаточно близко к корню $ x^*$, так чтобы на отрезке между $ x_0$ и $ x^*$ производная мало отличалась от 0).

Рис.9.10.Быстрая сходимость итераций при горизонтальной касательной к графику


    

Выше мы отмечали, что привести уравнение $ f(x)=0$ к виду $ x={\varphi}(x)$ можно, выбирая $ {\varphi}(x)$ в виде $ {\varphi}(x)=x-{\lambda}(x)f(x)$, где $ {\lambda}(x)\ne0$ -- произвольная функция. При различных способах выбора $ {\lambda}(x)$ получаются разные модификации метода итераций, которые имеют отличающиеся свойства: разную скорость сходимости (но не меньшую той, что гарантирована теоремой) и разную потребность в вычислении значений функции $ f$ или $ {\varphi}$, а также их производных.

Отметим самые употребительные из этих методов.
Наверх: Приближённое нахождение корней уравнений

Физика лабы
Элементарная математика Кратные интегралы Математический анализ грузовые японские иркутск
Векторный анализ Аналитическая геометрия Пределы функции Изучение функции Куплю Акции
Конспекты по математике Комплексные числа Дифференциальные уравнения омоложение Элос
Определенные интегралы Лекции по высшей математике Исследование функций Вычисление объема с помощью интегралов Алгеброические структуры