дипломы,диссертации,курсовые,контрольные,рефераты,отчеты на заказ
Деструктор Точечные изображения как объекты Геометрическая оптика Фотоэлектрический эффект Ядерные реакции Волновые свойства Квантовая механика Электромагнитное поле Задачник по ядерной физике Квантовая физика Электростатика Математика MATLAB Компьютерная математика Maple Лекции по математике учебник Outlook На главную Числовые ряды

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

Каждая следующая итерация $ 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}$, а также их производных.

Отметим самые употребительные из этих методов.


Объектно-ориентированный подход CorelDRAW Установка параметров цвета в цифровом виде Искусство Западная Европа Трехмерное объектно-ориентированное программное обеспечение CAD Эффект Комптона Волновые свойства электронов Геометрическая оптика Фотоэлектрический эффект Строение атомных ядер Волновые свойства микрочастиц Математические пакеты Моделирование и расчет электронных схем Конструкционные материалы Релятивистская механика Справочник по физикеПрикладная математика Архитектурное проектирование ArchiCAD Строительное и ландшафтного проектирования Planix Home 3D Architect Функции преобразования ;