Метод простых итераций
Материал из MachineLearning.
Строка 4: | Строка 4: | ||
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций. | Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций. | ||
== Метод простых итераций в общем виде == | == Метод простых итераций в общем виде == | ||
- | Заменим исходное уравнение <tex>f(x)=0</tex> на эквивалентное <tex>g(x)=x</tex>,и будем строить итерации по правилу <tex>x_{n+1} = g(x_n)</tex>. Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение <tex>x_0</tex>. Выясним условия сходимости метода. | + | Заменим исходное уравнение <tex>f(x)=0</tex> на эквивалентное <tex>g(x)=x</tex>,и будем строить итерации по правилу <tex>x_{n+1} = g(x_n)</tex>. Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение <tex>x_0</tex>. Выясним условия сходимости метода и выбор начального приближения. |
===Сходимость метода простых итераций=== | ===Сходимость метода простых итераций=== | ||
Метод сходится, если при <tex>k \to \infty </tex> последовательность {<tex>x_n</tex>} имеет предел.<br> | Метод сходится, если при <tex>k \to \infty </tex> последовательность {<tex>x_n</tex>} имеет предел.<br> | ||
Строка 66: | Строка 66: | ||
Это двухшаговый метод, и для начала вычислений необходимо задать 2 приближения <tex>x_0,x_1</tex>. | Это двухшаговый метод, и для начала вычислений необходимо задать 2 приближения <tex>x_0,x_1</tex>. | ||
== Программная реализация == | == Программная реализация == | ||
+ | Все методы были реализованы на языке C++. Доступ к методам осуществяется через класс | ||
+ | PowerIterationMethod | ||
+ | пример кода: | ||
+ | PowerIterationMethod::PowerIterationParams *params = new PowerIterationMethod::PowerIterationParams (f1,s1,0,0,0,1000); | ||
+ | PowerIterationMethod *method = new PowerIterationMethod (params); | ||
+ | method->simpleIteration (); | ||
+ | printf ("%f\n",method->getResult ()); | ||
+ | printf ("%f",method->getEps ()); | ||
+ | |||
== Числовые примеры == | == Числовые примеры == | ||
== Заключение == | == Заключение == |
Версия 15:40, 24 ноября 2008
Содержание |
Постановка задачи
Пусть есть функция .
Требуется найти корень этой функции: такой при котором
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций.
Метод простых итераций в общем виде
Заменим исходное уравнение на эквивалентное
,и будем строить итерации по правилу
. Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение
. Выясним условия сходимости метода и выбор начального приближения.
Сходимость метода простых итераций
Метод сходится, если при последовательность {
} имеет предел.
Обозначим окресность точки
радиуса
, то есть
.
Теорема. Если липшиц-непрерывна с константой
на
, то есть выполняется
при этом если также выполнено
где - точное решение.
Из оценки видно, что метод линеен.
Пусть непрерывно дифференцируема на
, тогда из теоремы вытекают следующие утверждения:
Следствие 1. Если для
, выполнено
, и
, тогда уравнение
имеет единственное решение на
и метод простой итерации сходится к решению.
Следствие 2. Если уравнение имеет решение
,
непрерывно дифференцируема на
и
. Тогда существует
такое, что на
уравнение не имеет других решений и метод простой итерации сходится к решению при
Метод релаксации
Так как для сходимости метода очень важен выбор функции , ее обычно берут вида
. Где
не меняет знака на отрезке, на котором ищется корень функции.
Положим и рассмотрим метод в этом случае.
Тогда получим метод 'релаксации':
для которого , и метод сходится при условии
Пусть в некоторой окресности корня выполняются условия
Тогда метод релаксации сходится при
Выбор параметра
Оценим погрешность метода релаксации
Применяя теорему о среднем получаем
Отсюда
Следовательно
Таким образом задача сводится к нахождению минимума функции
Из рассмотрения графика функции видно, что точка минимума определяется
и равна
Ускорение сходимости
Как следует из Теоремы, метод простых итераций линеен, то есть
Воспользуемся этим для оценки погрешности на каждой итерации. Запомним 3 последние итерации и выпишем их оценки:
Где нам известны (вычисленны по какому то линейному алгоритму),а
найдем из системы. Получим:
Метод ускорения сходимости заключается в том, что после вычисления 3 приближений по линейно сходящемуся алгоритму, вычисляется новое приближение по уточняющему правилу (1).
Применительно к методу релаксации имеем:
Следовательно
Можно показать, что данный метод имеет уже квадратичную скорость сходимости.
Метод Вегстейна
Метод Вегстейна, вообще говоря, является модификацией метода секущих, однако его можно назвать и улучшенным методом простой итерации, преобразовав вычислительню формулу
к виду
Это двухшаговый метод, и для начала вычислений необходимо задать 2 приближения .
Программная реализация
Все методы были реализованы на языке C++. Доступ к методам осуществяется через класс
PowerIterationMethod
пример кода:
PowerIterationMethod::PowerIterationParams *params = new PowerIterationMethod::PowerIterationParams (f1,s1,0,0,0,1000);
PowerIterationMethod *method = new PowerIterationMethod (params); method->simpleIteration (); printf ("%f\n",method->getResult ()); printf ("%f",method->getEps ());
Числовые примеры
Заключение
Ссылки
Список литературы
- А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 1989.
- Н.Н.Калиткин. Численные методы. Москва «Наука», 1978.