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

Метод простых итераций основан на замене исходного уравнения эквивалентным уравнением:

. (2.7)

Пусть известно начальное приближение к корню х = х₀. Подставив его в правую часть уравнения (2.7), получим новое приближение , затем аналогичным образом получим и т. д.:

. (2.8)

Не при всех условиях итерационный процесс сходится к корню уравнения х. Рассмотрим этот процесс подробнее. На рис.2.6 приведена графическая интерпретация одностороннего сходящегося и расходящегося процесса. На рис.2.7 изображены двухсторонний сходящийся и расходящийся процессы. Расходящийся процесс характеризуется быстрым нарастанием значений аргумента и функции и аварийным завершением соответствующей программы.

При двухстороннем процессе возможно зацикливание, то есть бесконечное повторение одних и тех же значений функции и аргумента. Зацикливание отделяет расходящийся процесс от сходящегося.

Из графиков видно, что как при одностороннем, так и при двухстороннем процессе сходимость к корню определяется наклоном кривой вблизи корня. Чем меньше наклон, тем лучше сходимость. Как известно, тангенс угла наклона кривой равен производной кривой в данной точке.

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

Для того чтобы итерационный процесс был сходящимся, необходимо в окрестности корня выполнение следующего неравенства:

. (2.9)

Переход от уравнения (2.1) к уравнению (2.7) можно осуществить различными способами в зависимости от вида функции f(x). При таком переходе необходимо построить функцию так, чтобы выполнялось условие сходимости (2.9).

Рассмотрим один из общих алгоритмов перехода от уравнения (2.1) к уравнению (2.7).

Умножим левую и правую части уравнения (2.1) на произвольную константу b и добавим к обеим частям неизвестное х. При этом корни исходного уравнения не изменятся:

(2.10)

Введем обозначение и перейдем от соотношения (2.10) к уравнению (2.8).

. (2.11)

Произвольный выбор константы b позволит обеспечить выполнение условия сходимости (2.9). Критерием окончания итерационного процесса будет условие (2.2). На рис.2.8 приведена графическая интерпретация метода простых итераций при описанном способе представления (масштабы по осям X и Y различны).

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

Программная реализация метода простых итераций выполнена в виде процедуры-подпрограммы Iteras (ПРОГРАММА 2.1).

Вся процедура практически состоит из одного цикла Repeat... Until, реализующего формулу (2.11) с учетом условия прекращения итерационного процесса (формула (2.2)).

В процедуру встроена защита от зацикливания путем подсчета числа циклов с помощью переменной Niter. На практических занятиях необходимо убедиться путем прогона программы в том, как сказывается выбор коэффициента b и начального приближения на процессе поиска корня. При изменении коэффициента b характер итерационного процесса для исследуемой функции меняется. Он становится сначала двухсторонним, а потом зацикливается (рис.2.9). Масштабы по осям X и Y различны. Еще большее значение модуля b приводит к расходящемуся процессу.

Сравнение методов приближенного решения уравнений

Сравнение описанных выше методов численного решения уравнений проводилось с помощью программы, позволяющей на экране ПЭВМ наблюдать процесс нахождения корня в графическом виде. Процедуры, входящие в данную программу и реализующие сравниваемые методы, приведены ниже (ПРОГРАММА 2.1).

Рис. 2.3-2.5, 2.8, 2.9 являются копиями экрана ПЭВМ при окончании итерационного процесса.

В качестве исследуемой функции во всех случаях было взято квадратное уравнение x²-x-6 = 0, имеющее аналитическое решение х₁ = -2 и х₂ = 3. Погрешность и начальные приближения принимались для всех методов равными. Результаты поиска корня х= 3, представленные на рисунках, таковы. Наиболее медленно сходится метод дихотомии - 22 итерации, самый быстрый - метод простых итераций при b = -0.2 - 5 итераций. Здесь нет противоречия с утверждением, что метод Ньютона является самым быстрым.

Производная исследуемой функции в точке х = 3 равна -0.2, то есть расчет в данном случае велся практически методом Ньютона с величиной производной в точке корня уравнения. При изменении коэффициента b скорость сходимости падает и постепенно сходящийся процесс сначала зацикливается, потом становится расходящимся.