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

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

Содержание

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

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

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

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

Заменим исходное уравнение $f(x)=0$ на эквивалентное $g(x)=x$ ,и будем строить итерации по правилу $x_{n+1} = g(x_n)$ . Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение $x_0$ . Выясним условия сходимости метода и выбор начального приближения.

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

Метод сходится, если при $k \to \infty$ последовательность { $x_n$ } имеет предел.
Обозначим $U_r(a)$ окресность точки $a$ радиуса $r$ , то есть $U_r(a) = \{x:|x-a|<r\}$ .
Теорема 1. Если $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_0 \in U_r(a)$ .Так же справедлива оценка: $|x_k-x_*|<q^k|x_0-x_*|$ ,

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

Из оценки видно, что метод линеен. Пусть $g(x)$ непрерывно дифференцируема на $U_r(a)$ , тогда из теоремы вытекают следующие утверждения:
Следствие 1. Если $|g'(x)| \le q < 1$ для $x \in U_r(a)$ , выполнено $|g(a)-a|<(1-q)r$ , и $x_0 \in U_r(a)$ , тогда уравнение $x = g(x)$ имеет единственное решение на $U_r(a)$ и метод простой итерации сходится к решению.

Следствие 2. Если уравнение $x = g(x)$ имеет решение $x_*$ , $g(x)$ непрерывно дифференцируема на $U_r(x_*)$ и $|g'(x_*)|<1$ . Тогда существует $\eps > 0$ такое, что на $U_{\eps}(x_*)$ уравнение не имеет других решений и метод простой итерации сходится к решению при $x_0 \in U_{\eps}(x_*)$

Геометрическая интерпретация

Рассмотрим график функции $y = g(x)$ . Это озночает, что решение уравнения $f(x) = 0$ и $x=g(x)$ - это точка пересечения $g(x)$ с прямой $y = x$ :

И следующая итерация $x_{x+1} = g(x_n)$ - это координата $x$ пересечения горизонтальной прямой точки $(x_n g(x_n))$ с прямой $y = x$ .

Из рисунка наглядно видно требование сходимости $|g'(x)|<1$ . Чем ближе производная $g'(x)$ к $0$ , тем быстрее сходится алгоритм. В зависимости от знака производной вблизи решения приближения могут строится по разному. Если $g'(x)<0$ , то каждое следующее приближение строится с другой стороны от корня:

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

Так как для сходимости метода очень важен выбор функции $g(x)$ , ее обычно берут вида $g(x)=x+s(x)f(x)$ $(1)$ .

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

$f(x_n) = \frac{x_{n+1}-x_{n}}{c}$ ,

для которого $g'(x) = 1+cf'(x)$ , и метод сходится при условии

$-2<cf'(x_*)<0$ ,

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

$f'(x)<0, 0<m_1<|f'(x)|<M_1$ ,

Тогда метод релаксации сходится при $c \in (0,\frac{2}{M_1}).$

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

Оценим погрешность метода релаксации $z_k=x_k-x_*$

$f(x_*+z_n) = \frac{z_{n+1}-z_{n}}{c}$ ,

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

$f'(x_*+{\theta}z_n)z_n = \frac{z_{n+1}-z_{n}}{c}$ ,

Отсюда

$|z_{n+1}|\le|1+cf'(x_*+{\theta}z_n)||z_n|\le max|1+cf'(x_*+oz_n)||z_n|$ ,

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

$|z_{n+1}|\le max\{|1-cM_1|,|1-cm_1|\}|z_n|$ ,

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

$F(c) = max\{|1-cM_1|,|1-cm_1|\}$ ,

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

$|1-cM_1| = |1-cm_1|$ при $c\ne 0$ ,

и равна

$c = \frac{2}{M_1+m_1}$

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

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

$x_n-x_* \approx aq^n$

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

$x_{k}-x_{*} \approx aq^{k}$ $x_{k+1}-x_{*} \approx aq^{k+1}$ $x_{k+2}-x_{*} \approx aq^{k+2}$

Где $x_{k},x_{k+1},x_{k+2}$ нам известны (вычисленны по какому то линейному алгоритму),а $a,q,x_*$ найдем из системы. Получим:

$x_{*} \approx x_{k+2} - \frac{(x_{k+2}-x_{k+1})^2}{x_{k+2}-2x_{k+1}+x_{k}}$ $(2)$

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

$x_{*} \approx x_{k+2} - \frac{(x_{k+2}-x_{k+1})^2}{x_{k+2}-2x_{k+1}+x_{k}}$
$\frac{x_{n+1}-x_{n}}{c} = f(x_n)$

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

$x_{*} \approx x_{k} - c\frac{f^2(x_k)}{f(x_k)-f(x_k-cf(x_k))}$

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

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

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

$x_k = x_{k-1} - \frac{f(x_{k-1})(x_{k-1}-x_{k-2})}{f(x_{k-1})-f(x_{k-2})}$

к виду

$x_{k}=x_{k-1} - \frac{x_{k-1}-g(x_{k-1})}{(1-\frac{g(x_{k-1})-g(x_{k-2)}}{x_{k-1}-x_{k-2}})}$

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

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

Все методы были реализованы на языке 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 ());

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

Ошибкой будем считать $\eps = f(x_k)-f(x_*) = f(x_k)$ и проверим скорость сходимости методов относительно друг друга.
$f(x) = -(\log(x)-\cos(x))$ $\eps = 10^{-5}$
Начальное приближение $x_0 = 1$
1. Метод простой итерации с $s(x) = 1$ .
Сходимость за 28 шагов.
2. Метод простой итерации с $s(x) = \sin x$ .
Сходимость за 21 шаг.
3. Ускоренный метод простой итерации.
Сходимость за 3 шага.
4. Метод Вегстейна.
Сходимость за 3 шага.

$f(x) = -(\frac{1}{2}+x^2-\cos x)$ Корень $x_* \approx 0.58$
$\eps = 10^{-5}$
Начальное приближение $x_0 = 1$
1. Метод простой итерации с $s(x) = 1$ .
Сходимость за 23 шагов.
2. Метод простой итерации с $s(x) = \sin x$ .
Сходимость за 5 шаг.
3. Ускоренный метод простой итерации.
Сходимость за 4 шага.
4. Метод Вегстейна.
Сходимость за 4 шага.

$f(x) = -(\frac{1}{2}+x^2-\cos x)$ Корень $x_* \approx 0.58$
$\eps = 10^{-8}$
Начальное приближение $x_0 = 0.4$
1. Метод простой итерации с $s(x) = 1$ .
Сходимость за 43 шагов.
2. Метод простой итерации с $s(x) = \sin x$ .
Сходимость за 7 шагов.
3. Ускоренный метод простой итерации.
Сходимость за 5 шагов.
4. Метод Вегстейна.
Сходимость за 7 шагов.