Метод итераций

Пусть дано уравнение

. (1.4)

Умножим обе части уравнения на некоторую функцию ², и прибавимк обеим частям уравнения. Получим тождественное уравнение

. (1.5)

Обозначим

. (1.6)

Следовательно, от уравнения (1.4) мы переходим к тождественному уравнению (1.7)³:

. (1.7)

Выберем каким-нибудь образом грубое приближенное значение корня (например, один из концов отрезка). Назовем егоначальным приближением. Подставимв правую часть нового уравнения (1.7) и вычислим очередное приближение. Далее подставимв правую часть уравнения (1.7) и вычислим. Будем повторять данный процесс. В результате получим последовательность значений:

, где . (1.8)

Если данная последовательность сходится, т.е. у нее существует предел , то, перейдя к пределу, получими. Следовательно,- корень уравнения. Т.к. на компьютерах практически невозможно проводить бесконечно большое количество операций (т.к. это потребует бесконечно большого количества машинных часов), то точное значение корня вычислить, в общем случае, нельзя. Но приближенное значение корня можно вычислить с любой требуемой точностью.

Как определить, сколько раз необходимо выполнить итерационную формулу , и с какой точностью будет найден приближенный корень? На практике задают погрешность Eps (обычноEps=0.001) и говорят, что требуемая точность достигнута при выполнении одного из условий:или. Данные условия окончания счета принято называтькритериями сходимости. Иногда в качестве критерия пытаются использовать выполнение определенного заранее заданного количества итераций⁴. Но указанный третий подход на практике является неверным и может быть использован только в качестве защиты от зацикливания программы при неверных исходных параметрах.

Теоретическим обоснованием метода итераций служит следующая теорема.

Теорема. Пусть функцияопределена и дифференцируема на отрезке, причем все ее значения. Тогда, если существует рациональное числоq, такое чтодля, то 1) Процесс итерациидлясходится независимо от начального значения. 2) Предельное значениеявляется единственным корнем уравнения.

Примечание. На практике обычно берут константу и используют итерационный процесс. Следовательно,и метод итераций сходится при условии.

Пример. Решить уравнение.

Берем const . Получаем.

Далее, .

Согласно условиям теоремы и примечания имеем .

Т.к. для любого отрезка, содержащего корень уравнения , данное условие выполняться не будет (невозможно подобрать constc), то теоретически метод итераций для этого примера сходиться не будет при любом начальном приближении. Однако на практике возможно подобрать коэффициенты метода итераций для его сходимости. Например, прииметод не сходится. Прииметод сходится при погрешностиEps=0.0001 и уже не сходится приEps=0.00001.

Пример. Решить уравнение.

В качестве отрезка с корнем возьмем .

Берем const c. Получаем.

Далее, .

Согласно условиям теоремы и примечания имеем .

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

Пример. Ниже приведен фрагмент программы, реализующий метод итераций. Для реализации последовательности приближений используется цикл с постусловиемRepeat ... Until. Считается, что все нужные переменные и функцияF(x) ранее определены и им заданы нужные значения.

{Задаем начальное приближение}

Xn:=X0;

{Начинаем цикл с постусловием}

Repeat

{Вычисляем очередное приближение}

Xn1:=Xn-C*F(Xn);

{Очередное приближение становится предыдущим}

Xn:=Xn1;

{Проверяем критерий сходимости - конец цикла}

Until Abs(F(Xn1))<Eps;

{Выводим приближенное значение корня Xn1 на экран}

Для оценки погрешности приближенного значения корня можно использовать следующее неравенство

. (1.9)