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

Материал из MachineLearning.

Версия от 11:28, 24 ноября 2008; Zadonskiyd (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Постановка задачи
2 Метод простых итераций в общем виде
- 2.1 Сходимость метода простых итераций
3 Метод релаксации
- 3.1 Выбор параметра
- 3.2 Ускорение сходимости
4 Метод Вегстейна
5 Числовые примеры
6 Рекомендации программисту
7 Заключение
8 Ссылки
9 Список литературы

Постановка задачи

Пусть есть функция $y = f(x)$ .
Требуется найти корень этой функции, то есть $x$ при котором $f(x)=0$
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций.

Метод простых итераций в общем виде

Заменеим исходное уравнение $f(x)=0$ на эквивалентное $g(x)=x$ ,и будем строить итерации по правилу $x_{n+1} = g(x_n)$ . Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение $x_0$ . Выясним условия сходимости метода.

Сходимость метода простых итераций

Метод сходится, если при $k \to \infty$ последовательность { $x_n$ } имеет предел.
Обозначим $U_r(a)$ окресность точки $a$ радиуса $r$ , то есть $U_r(a) = \{x:|x-a|<r\}$ .
Теорема. Если $g(x)$ липшиц-непрерывна с константой $q \in (0,1)$ на $U_r(a)$ , то есть выполняется

$|g(x'')-g(x')|<q|x''-x'|$ ,

при этом если также выполнено

$|g(a)-a|<(1-q)r$ ,то уравнение $x = g(x)$ имеет единственное решение на $U_r(a)$ и метод простой итерации сходится к решению при любом выборе начального приближения $x_1 \in U_r(a)$ .Так же справедлива оценка: $|x_k-x_*|<q^k|x_0-x_*|$ ,

где $x_*$ - точное решение.

Из оценки видно, что метод линеен. Пусть $g(x)$ непрерывно дифференцируема на $U_r(a)$ , тогда из теоремы вытекают следующие утверждения:
Следствие 1. Если $|g'(x)| \le q < 1$ для $x \in U_r(a)$ , выполнено $|g(a)-a|<(1-q)r$ , и $x_0 \in U_r(a)$ , тогда уравнение $x = g(x)$ имеет единственное решение на $U_r(a)$ и метод простой итерации сходится к решению.

Следствие 2. Если уравнение $x = g(x)$ имеет решение $x_*$ , $g(x)$ непрерывно дифференцируема на $U_r(x_*)$ и $|g'(x_*)|<1$ . Тогда существует $\eps > 0$ такое, что на $U_{\eps}(x_*)$ уравнение не имеет других решений и метод простой итерации сходится к решению при $x_0 \in U_{\eps}(x_*)$

Метод релаксации

Так как для сходимости метода очень важен выбор функции $g(x)$ , ее обычно берут вида $g(x)=x+s(x)f(x)$ . Где $s(x)$ не меняет знака на отрезке, на котором ищется корень функции.
Положим $s(x) = c = const$ и рассмотрим метод в этом случае.
Тогда получим метод 'релаксации':