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

Для применения метода простых итераций уравнение (4.1) предварительно представляют в виде (4.28):

. (4.28)

Очевидно, что корнем данного уравнения является абсцисса точки пересечения кривых и (смотрите рисунок 4).

Построение последовательности приближений к корню осуществляют по следующей схеме.

На отрезке выбирают нулевое приближение корня , и все последующие значения строят по правилу:

, , …, , …. (4.29)

Если последовательность, построенная по правилу (4.29), сходится к числу , то для непрерывной функции , переход к пределу в равенстве (4.30)

(4.30)

приводит к равенству

, (4.31)

что означает, что - корень уравнения (4.28).

Геометрически данный процесс выглядит следующим образом (смотрите рисунок 4).

Рисунок 4 – Геометрическая интерпретация метода простых итераций

Точке на графике функции соответствует точка , через точку проводим прямую до пересечения с прямой в точке , из точки опускаем перпендикуляр на ось ОХ, абсцисса точки пересечения данного перпендикуляра с осью ОХ – приближение . Нетрудно заметить, что .

Точке на графике функции соответствует точка , через точку проводим прямую до пересечения с прямой в точке , из точки опускаем перпендикуляр на ось ОХ, абсцисса точки пересечения данного перпендикуляра с осью ОХ – приближение . Нетрудно заметить, что .

Продолжая этот процесс, замечаем, что для получения n -го приближения необходимо через точку провести прямую до пересечения с прямой в точке , из точки опустить перпендикуляр на ось ОХ, абсцисса точки пересечения данного перпендикуляра с осью ОХ – приближение . Нетрудно заметить, что .

Таким образом, последовательные приближения к корню - абсциссы точек ломаной линии .

Очевидно, что поведение итерационного процесса, задаваемого, по правилу (4.29) зависит от свойств функции . На рисунке 5 представлена геометрическая иллюстрация поведения итерационного процесса в четырех простейших случаях взаимного расположения прямой y = x и кривой .

Рисунок 5

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

Нетрудно заметить, что для ситуаций а и б (модуль тангенса угла наклона кривой к оси абсцисс меньше единицы). А на рисунках в и г, - . Это дает возможность предположить, что сходимость метода простой итерации связана с выполнением условия ([3], стр. 99).

Справедливость этого предположения подтверждается следующей теоремой, с доказательством которой можно ознакомиться в [3], стр. 100.

Теорема. Если в некоторой s-окрестности корня функция дифференцируема и удовлетворяет неравенству

, (4.32)

где q - постоянная, удовлетворяющая условию , то независимо от выбора начального приближения из указанной s-окрестности корня итерационная последовательность, построенная по правилу (4.29), не выходит из этой окрестности, метод сходится со скоростью геометрической прогрессии и справедлива следующая оценка погрешности:

. (4.33)

Оценка (4.33) является априорной и на практике практически не используется, однако позволяет сделать вывод, что ([3], стр. 101):

· чем меньше q, тем выше скорость сходимости;

· чем меньше погрешность начального приближения, тем меньше итераций потребуется сделать для достижения заданной точности.

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

Теорема. Пусть функция определена и дифференцируема на отрезке . Тогда, если выполняются условия:

1) ;

2) ,

то уравнение (4.28) имеет и притом единственный на отрезке корень ; к этому корню сходится последовательность , определяемая по формулам (4.29), начиная с любого ; при этом для любого справедливы следующие оценки погрешности:

, (4.34)

. (4.35)

Доказательство данной теоремы имеется в [5], стр. 248 – 250.

Условие , является в данном случае не необходимым, а достаточным, и в [5], стр. 251 имеется и другой признак сходимости последовательности, построенной по правилу (4.49), к корню уравнения (4.28).

Теорема. Пусть на отрезке функция определена, дифференцируема и её производная удовлетворяет неравенству . Тогда, если величина r такова, что

, (4.36)

то на найдется единственный корень уравнения (4.28), и к нему сходится начатый с метод простых итераций (4.29) с оценками погрешности (4.34) и (4.35).

Оценку (4.34) используют в практических вычислениях в качестве критерия окончания вычислительного процесса. Если требуется вычислить корень с точностью , расчет ведется до тех пор, пока ([5], стр. 251):

. (4.37)

Как только условие (4.36) перестает выполняться, расчет прекращают и полагают .

Из (4.35) легко получается приблизительная оценка (4.38) для числа итераций ([5], стр. 251):

. (4.38)

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

Теорема. Если - корень уравнения (4.28) и , где , тогда последовательность , построенная по правилу (4.29), где в качестве взято любое число из отрезка , для которого не выходит за пределы отрезка , сходится к указанному значению . При этом:

a) если , то

; (4.39)

b) если , то

. (4.40)

Доказательство сходимости последовательности, построенной по правилу (4.29), при данных ограничениях на функцию и вывод формулы (4.40) для оценки погрешности можно найти в [7], стр. 391 – 393; вывод формулы (4.39) имеется в [12], стр. 177-181.

В [3], стр. 104 дополнительно отмечается, что:

1) если , то сходится к , монотонно возрастая при , и монотонно убывая при ;

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

Геометрическая иллюстрация данного факта представлена на рисунках 5а и 5б.

Используя оценки (4.39) и (4.40), можно находить приближенное значение корня уравнения (4.28) с заданной степенью точности .

В частности, при выполнении условий рассматриваемой теоремы для достижения требуемой точности расчет необходимо вести до тех пор, пока:

· , если ; (4.41)

· , если е . (4.42)

Как только данные неравенства перестанут выполняться, расчет прекращают и полагают .

Ключевой момент в методе итераций – приведение уравнения (4.1) к виду (4.28) так, чтобы выполнялось требование .

В тех случаях, когда простой перенос слагаемых не дает нужно результата, можно воспользоваться следующим искусственным приемом ([3], стр. 105).

Если производная на непрерывна и положительна, то исходное уравнение (4.1) представляют в виде:

, (4.43)

т.е. полагают

, (4.44)

где - некоторое положительное число.

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

Так как производная непрерывна и положительна, то она достигает на этом отрезке свои наименьшее и наибольшее значения, т.е. существуют положительные постоянные m и M, такие что

. (4.45)

В этом случае,

(4.46)

и, следовательно,

. (4.47)

Откуда следует, что для выполнения сходимости итерационного процесса достаточно выбрать . Если известными являются постоянные m и M, то лучший выбор значения параметра , если известна только одна постоянная M, то наилучший выбор - . В этом случае производная - неотрицательная и, следовательно, сходимость итерационной последовательности - монотонная.

Если производная на непрерывна и отрицательна, то обе части исходного уравнения (4.1) следует умножить на -1, что приведет к рассмотренному выше алгоритму.

Поиск по сайту: