Главная > Математика > Вычислительные методы для инженеров
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

1. Описание метода.

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

Это преобразование (приведение уравнения к виду, удобному для итерации) можно выполнить различными способами; некоторые из них будут указаны ниже. Функцию далее будем называть итерационной функцией.

Выберем каким-либо образом приближенное значение корня и подставим его в правую часть уравнения (4.15). Получим значение Подставляя теперь в правую часть уравнения (4.15), имеем Продолжая этот процесс неограниченно, получим последовательность приближений к корню, вычисляемых по формуле

Очевидно, что метод простой итерации — одношаговый (см. § 4.1).

Если существует предел построенной последовательности то, переходя к пределу в равенстве (4.16) и предполагая функцию непрерывной, получим равенство

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

2. Геометрическая иллюстрация.

Из рис. 4.6 видно, что корень х уравнения (4.15) является абсциссой точки пересечения графиков двух функций: Возьмем некоторое начальное приближение которому отвечает расположенная на кривой точка с координатами (напомним, что Соединим точку отрезком прямой с лежащей на прямой точкой с координатами Проведем теперь через точку прямую до пересечения с кривой в точке с координатами Продолжая этот процесс далее, получаем ломаную линию для которой абсциссы точек представляют собой последовательные приближения к решению х.

3. Сходимость метода.

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

Рис. 4.6

Рис. 4.7

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

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

Теорема 4.2. Пусть в некоторой -окрестности корня х функция дифференцируема и удовлетворяет неравенству

где постоянная.

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

Вычитая из равенства (4.16) равенство (4.17) и используя формулу конечных приращений Лагранжа, получим

Здесь где некоторая точка, расположенная между Если то в силу условия (4.18). Тогда на основании равенства (4.20) получаем

Это означает, что метод простой итерации обладает линейной скоростью сходимости и поэтому доказательство теоремы завершается применением леммы 4.1.

Оценка погрешности (4.19) является априорной. Она показывает, что метод простой итерации сходится со скоростью геометрической прогрессии, знаменатель которой равен Чем меньше тем выше сокрость сходимости. Видна и роль правильного выбора начального приближения: чем меньше погрешность начального приближения, тем меньше итераций потребуется сделать для достижения заданной точности

Неравенство (4.19), как правило, не используется для практической оценки погрешности. Одна из причин этого состоит в том, что значение х, входящее в правую часть оценки, неизвестно. Кроме того,

использование неравенства (4.19) приводит к существенно завышенной оценке погрешности.

4. Критерий окончания.

Выведем апостериорную оценку погрешности, пригодную для практического применения.

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

В силу равенства (4.20) имеем

Отсюда

Взяв модуль от левой и правой частей этого равенства и воспользовавшись неравенством получим требуемое соотношение (4.21).

Если величина известна, то неравенство (4.21) дает эффективный метод контроля погрешности и можно сформулировать следующий критерий окончания итерационного процесса. Вычисления следует вести до выполнения неравенства или равносильного ему неравенства

Если это условие выполнено, то можно считать, что является приближением к х с точностью

Пример 4.5. Используем метод простой итерации для вычисления положительного корня х уравнения с точностью Результат примера 4.4 дает для корня отрезок локализации .

Преобразуем уравнение к виду (4.15), где Заметим, что Так как на то производная монотонно убывает и . Следовательно, условие сходимости (4.18) выполнено. Возьмем и будем вести итерации до выполнения критерия (4.23). В табл. 4.3 соответствующие приближения приведены с 10 знаками мантиссы.

Таблица 4.3 (см. скан)

Критерий окончания выполняется при После округления значения до четырех значащих цифр получим

Замечание. Часто в практике вычислений вместо критерия (4.23) используется привлекательный своей простотой критерий

В случае использование критерия (4.24) оправдано. Действительно, здесь и поэтому выполнение неравенства (4.24) влечет за собой выполнение неравенства (4.23).

Рис. 4.8

В то же время в случае использование критерия (4.24) может привести к преждевременному прекращению итераций. Дело в том, что когда величина близка к единице, итерационный процесс сходится медленно и расстояние между двумя последовательными приближениями не характеризует расстояния от до решения х (рис. 4.8).

Пример 4.6. Пусть метод простой итерации используется для решения уравнения Здесь и, следовательно, условие (4.18) сходимости метода выполнено. Для вычислений по формуле (4.16) используем -разрядную десятичную ЭВМ. Возьмем Тогда и, если доверять критерию (4.24), то следовало бы считать, что решение получено с точностью Продолжая

вычисления, получим Дальнейшие итерации теряют смысл. Сколько же верных знаков найдено? Сравнение с точным значением решения показывает, что верными в приближении являются только две значащие цифры. Использование критерия (4.24) в данном случае категорически недопустимо. В дальнейшем мы еще вернемся к обсуждению этого примера.

Использование критерия (4.23) предполагает знание величины входящей в условие (4.18). Однако далеко не всегда эта величина известна, либо может быть легко вычислена. В тех же случаях, когда удается оценить эта оценка оказывается довольно грубой.

Исключим из критерия окончания итераций величину Заметим, что в малой окрестности корня величина производной практически постоянна: Поэтому в равенстве (4.22) величину можно приближенно заменить на Далее в силу равенства

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

5. Дополнительные сведения о характере сходимости.

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

Теорема 4.4. Пусть отрезок локализации корня уравнения (4.15). Предположим, что на этом отрезке функция непрерывно дифференцируема, а ее производная знакопостоянна и удовлетворяет неравенству (4.18) при Пусть

произвольное начальное приближение и в случае выполнено дополнительное условие (первое приближение не выходит за пределы отрезка локализации).

Тогда итерационная последовательность не выходит за пределы отрезка метод простой итерации сходится и верны оценки погрешности (4.19), (4.21).

Кроме того, справедливы следующие свойства:

1°. Если на то сходится к х, монотонно возрастая в случае а и монотонно убывая в случае

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

и справедлив критерий (4.24) окончания итерационного процесса.

Мы не будем приводить здесь полное доказательство теоремы. Оно основано на использовании равенства (4.20), установленного при доказательстве теоремы 4.2. Докажем только справедливость свойств 1° и 2°.

Если то знаки величин совпадают, в то время как Следовательно, последовательность монотонно приближается к х с той стороны, где лежит Если же то из равенства (4.20) следует, что знаки величин различны. Это подтверждает колебательный характер сходимости.

Замечание. Монотонный и колебательный характер сходимости итерационной последовательности, указанные в теореме 4.4, иллюстрируют соответственно рис. 4.7, а и 4.7, б.

6. Приведение уравнения к виду, удобному для итераций.

Ключевой момент в применении метода простой итерации — эквивалентное преобразование уравнения (4.1) к виду (4.15). Конечно, такое преобразование имеет смысл только тогда, когда оказывается выполненным условие (4.18) при Укажем один из простых способов такого преобразования.

Предположим, что производная на отрезке непрерывна и положительна. Тогда существуют положительные постоянные и такие, что Приведем уравнение (4.1) к виду

где . В этом случае итерационная функция имеет вид Как выбрать а, чтобы выполнялось условие (4.18), причем было бы по возможности минимальным?

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

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

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

Пример 4.7. Для решения задачи, поставленной в примере 4.5, можно воспользоваться преобразованием уравнения (4.4) к виду (4.26). Будем считать известным, что . Так как на отрезке локализации выполнено условие то перепишем уравнение в виде Тогда и для оценки Выберем в уравнении (4-26) возьмем и будем вести итерации по формуле Выбранному а соответствует и поэтому сходимость должна быть более быстрой, чем в примере 4.6. Действительно, уже первая итерация дает и так как то итерации следует прекратить и считать

<< Предыдущий параграф Следующий параграф >>
Оглавление