Метод простых итераций
Материал из MachineLearning.
| Строка 11: | Строка 11: | ||
===Сходимость метода простых итераций=== | ===Сходимость метода простых итераций=== | ||
Метод сходится, если при <tex>k \to \infty </tex> последовательность {<tex>x_n</tex>} имеет предел.<br> | Метод сходится, если при <tex>k \to \infty </tex> последовательность {<tex>x_n</tex>} имеет предел.<br> | ||
| - | |||
| - | |||
| - | |||
Обозначим <tex>U_r(a) = \{x:|x-a|<r\}</tex>, то есть окрестность с радисом <tex>r</tex>.<br> | Обозначим <tex>U_r(a) = \{x:|x-a|<r\}</tex>, то есть окрестность с радисом <tex>r</tex>.<br> | ||
'''Теорема.'''Если <tex>g(x)</tex> Липшиц непрерывна с константой <tex>q \in (0,1)</tex> на <tex>U_r(a)</tex>, то есть выполняется <tex>|g(x'')-g(x')|<q|x''-x'|</tex>. При этом если также выполнено <tex>|g(a)-a|<(1-q)r</tex>, то уравнение <tex>x = g(x)</tex> имеет решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению при любом выборе начального приближжения <tex>x_1 \in U_r(a)</tex>.<br> | '''Теорема.'''Если <tex>g(x)</tex> Липшиц непрерывна с константой <tex>q \in (0,1)</tex> на <tex>U_r(a)</tex>, то есть выполняется <tex>|g(x'')-g(x')|<q|x''-x'|</tex>. При этом если также выполнено <tex>|g(a)-a|<(1-q)r</tex>, то уравнение <tex>x = g(x)</tex> имеет решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению при любом выборе начального приближжения <tex>x_1 \in U_r(a)</tex>.<br> | ||
| + | ===Метод релаксации=== | ||
| + | Положим <tex>s(x) = c = const </tex> b и рассмотрим метод в этом случае.<br> | ||
| + | Тогда получим <tex>f(x_n) = \frac{x_{n+1}-x_{n}}{c}</tex>. <br> | ||
== Числовые примеры == | == Числовые примеры == | ||
Версия 08:23, 24 ноября 2008
Содержание |
Постановка задачи
Пусть есть функция .
Требуется найти корень этой функции, то есть при котором
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций и его обобщения.
Метод простых итераций в общем виде
Заменеим исходное уравнение на эквивалентное
.
Итерации будем строить по правилу
Для сходимости метода очень важен выбор функции , поэтому ее обычно берут вида
Где не меняет знака на отрезке, на котором ищется корень функции.
Таким образом метод простой итерации - это одношаговый итерационны процесс.
Сходимость метода простых итераций
Метод сходится, если при последовательность {
} имеет предел.
Обозначим , то есть окрестность с радисом
.
Теорема.Если Липшиц непрерывна с константой
на
, то есть выполняется
. При этом если также выполнено
, то уравнение
имеет решение на
и метод простой итерации сходится к решению при любом выборе начального приближжения
.
Метод релаксации
Положим b и рассмотрим метод в этом случае.
Тогда получим .
Числовые примеры
Рекомендации программисту
Заключение
Ссылки
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 1989.
- Н.Н.Калиткин. Численные методы. Москва «Наука», 1978.
