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

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

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

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

Содержание

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

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

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

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

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

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

Метод сходится, если при $k \to \infty$ последовательность { $x_n$ } имеет предел.
Обозначим $U_r(a)$ окресность точки $a$ радиуса $r<tex>, то есть <tex>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)$ .

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

Так как для сходимости метода очень важен выбор функции $g(x)$ , ее обычно берут вида $g(x)=x+s(x)f(x)$ . Где $s(x)$ не меняет знака на отрезке, на котором ищется корень функции.
Положим $s(x) = c = const$ b и рассмотрим метод в этом случае.
Тогда получим $f(x_n) = \frac{x_{n+1}-x_{n}}{c}$ .