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

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

Содержание 1 Постановка задачи 2 Метод простых итераций в общем виде 2.1 Сходимость метода простых итераций 3 Метод релаксации 3.1 Выбор параметра 3.2 Ускорение сходимости 4 Метод Вегстейна 5 Программная реализация 6 Примеры тестирования алгоритмов 7 Заключение 8 Ссылки 9 Список литературы

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

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

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

Заменим исходное уравнение на эквивалентное ,и будем строить итерации по правилу . Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение . Выясним условия сходимости метода и выбор начального приближения.

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

Метод сходится, если при последовательность {} имеет предел.
Обозначим окресность точки радиуса , то есть .
Теорема 1. Если липшиц-непрерывна с константой на , то есть выполняется

,

при этом если также выполнено

,то уравнение имеет единственное решение на и метод простой итерации сходится к решению при любом выборе начального приближения .Так же справедлива оценка: ,

где - точное решение.

Из оценки видно, что метод линеен. Пусть непрерывно дифференцируема на , тогда из теоремы вытекают следующие утверждения:
Следствие 1. Если для , выполнено , и , тогда уравнение имеет единственное решение на и метод простой итерации сходится к решению.

Следствие 2. Если уравнение имеет решение , непрерывно дифференцируема на и . Тогда существует такое, что на уравнение не имеет других решений и метод простой итерации сходится к решению при

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

Так как для сходимости метода очень важен выбор функции , ее обычно берут вида .

Где не меняет знака на отрезке, на котором ищется корень функции.
Положим и рассмотрим метод в этом случае.
Тогда получим метод 'релаксации':

,

для которого , и метод сходится при условии

,

Пусть в некоторой окресности корня выполняются условия

,

Тогда метод релаксации сходится при

Выбор параметра

Оценим погрешность метода релаксации

,

Применяя теорему о среднем получаем

,

Отсюда

,

Следовательно

,

Таким образом задача сводится к нахождению минимума функции

,

Из рассмотрения графика функции видно, что точка минимума определяется

при ,

и равна

Ускорение сходимости

Как следует из Теоремы 1, метод простых итераций линеен, то есть

Воспользуемся этим для оценки погрешности на каждой итерации. Запомним 3 последние итерации и выпишем их оценки:

Где нам известны (вычисленны по какому то линейному алгоритму),а найдем из системы. Получим:

Метод ускорения сходимости заключается в том, что после вычисления 3 приближений по линейно сходящемуся алгоритму, вычисляется новое приближение по уточняющему правилу (2).
Применительно к методу релаксации имеем:

Следовательно

Можно показать, что данный метод имеет уже квадратичную скорость сходимости.

Метод Вегстейна

Метод Вегстейна, вообще говоря, является модификацией метода секущих, однако его можно назвать и улучшенным методом простой итерации, преобразовав вычислительню формулу

к виду

Это двухшаговый метод, и для начала вычислений необходимо задать 2 приближения .

Программная реализация

Все методы были реализованы на языке C++. Доступ к методам осуществяется через класс

PowerIterationMethod

пример кода:

PowerIterationMethod::PowerIterationParams *params = 
        new PowerIterationMethod::PowerIterationParams (
        f1   // Исходная функция
       ,s1   // Функция s(x) в формусле (1) или константа в методе релаксации
       ,1    // Начальное приближение
       ,0    // Второе приближение для метода Вегстейна
       ,0    // Допустимая погрешность решения
       ,1000 // Максимальное количество итераций
       );
PowerIterationMethod *method = new PowerIterationMethod (params);
method->simpleIteration (); // Вычисление по методу простой итерации
printf ("%f\n",method->getResult ());
printf ("%f",method->getEps ());

Примеры тестирования алгоритмов

Заключение

Ссылки

• Практикум ММП ВМК, 4й курс, осень 2008

Список литературы

• А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 1989.
• Н.Н.Калиткин. Численные методы. Москва «Наука», 1978.