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

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

Версия от 08:22, 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$ .
Итерации будем строить по правилу $g(x_n)=x_{n+1}$
Для сходимости метода очень важен выбор функции $g(x)$ , поэтому ее обычно берут вида $g(x)=x+s(x)f(x).$
Где $s(x)$ не меняет знака на отрезке, на котором ищется корень функции.
Таким образом метод простой итерации - это одношаговый итерационны процесс.

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

Метод сходится, если при $k \to \infty$ последовательность { $x_n$ } имеет предел.

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

Положим $s(x) = c = const$ b и рассмотрим метод в этом случае.
Тогда получим $f(x_n) = \frac{x_{n+1}-x_{n}}{c}$ .
Обозначим $U_r(a) = \{x:|x-a|<r\}$ , то есть окрестность с радисом $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)$ .