Метод простых итераций
Материал из MachineLearning.
Строка 15: | Строка 15: | ||
Тогда получим <tex>f(x_n) = \frac{x_{n+1}-x_{n}}{c}</tex>. <br> | Тогда получим <tex>f(x_n) = \frac{x_{n+1}-x_{n}}{c}</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> | + | |
Версия 08:22, 24 ноября 2008
Содержание |
Постановка задачи
Пусть есть функция .
Требуется найти корень этой функции, то есть при котором
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций и его обобщения.
Метод простых итераций в общем виде
Заменеим исходное уравнение на эквивалентное .
Итерации будем строить по правилу
Для сходимости метода очень важен выбор функции , поэтому ее обычно берут вида
Где не меняет знака на отрезке, на котором ищется корень функции.
Таким образом метод простой итерации - это одношаговый итерационны процесс.
Сходимость метода простых итераций
Метод сходится, если при последовательность {} имеет предел.
Метод релаксации
Положим b и рассмотрим метод в этом случае.
Тогда получим .
Обозначим , то есть окрестность с радисом .
Теорема.Если Липшиц непрерывна с константой на , то есть выполняется . При этом если также выполнено , то уравнение имеет решение на и метод простой итерации сходится к решению при любом выборе начального приближжения .
Числовые примеры
Рекомендации программисту
Заключение
Ссылки
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 1989.
- Н.Н.Калиткин. Численные методы. Москва «Наука», 1978.