§ 4. Итерационные методы решения алгебраических и трансцендентных уравнений

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

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

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

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

и затем строят последовательность с помощью соотношения

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

Ниже мы исследуем ряд стационарных и нестационарных методов.

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

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

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

т. е. оператор А сближает элементы.

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

имеет, одно и только одно решение. Решение этого уравнения может быть получено как предел последовательности

где — произвольный элемент из

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

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

Но

Таким образом,

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

Из полноты пространства следует существование элемента к которому сходится последовательность т. е.

Далее, так как

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

Для доказательства единственности допустим, что существуют два неподвижных элемента х и у, т. е.

Но оператор осуществляет сжатое отображение, поэтому

что невозможно, так как

Приведем еще одну теорему, которая уточняет доказанный выше принцип сжатых отображений.

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

и

где — некоторое фиксированное положительное число, меньшее единицы. Тогда в существует одно и только одно решение уравнения (6), которое может быть получено как предел последовательности (7), где -произвольный элемент из

Эта теорема непосредственно следует из принципа сжатых отображений, так как если то

т. е. Это означает, что оператор осуществляет отображение в себя. Из (5) следует, что это отображение, сжатое. Совокупность всех элементов с тем же самым понятием расстояния р(х, у) можно рассматривать как полное метрическое пространство, так как если любая фундаментальная последовательность элементов из то она сходится в т. е. существует элемент такой, что

Но отсюда т. е. Теперь уже утверждение теоремы прямо следует из принципа сжатых отображений.

Рассмотрим применение этого принципа к исследованию сходимости итерационного метода решения уравнения

при некоторых ограничениях на функцию

Предположим, что уравнение (3) имеет корень круге функция удовлетворяет условию Липшица

для любых точек

Теорема. Каково бы ни было последовательность

сходится к а, если только в круге удовлетворяет условию Липшица с константой причем скорость сходимости характеризуется неравенством

Доказательство. Совокупность точек круга если определить расстояние между точками х и у соотношением образует полное метрическое пространство. Если то также принадлежит ибо

Отображение, определяемое функцией есть сжатое отображение в себя, так как для любых

Поэтому по принципу сжатых отображений в существует одна и только одна неподвижная точка, но эта точка Эту точку можно получить как предел последовательности

при любом

Используя условие Липшица (8), имеем:

т. е.

Таким образом, сходится к а со скоростью геометрической прогрессии со знаменателем К.

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

Теорема. Если функция в некотором круге удовлетворяет условию Липшица (8) с константой и в точке имеет место неравенство

то в уравнение (3) имеет единственный корень который может быть найден как предел последовательности

где любая точка из круга

Доказательство. Пусть Тогда

т. е. функция осуществляет отображение в себя. Это — сжатое отображение, так как для любых

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

Мы требовали от функции выполнения условия Липшица с константой в некоторой окрестности корня уравнения (3). Чаще всего функция имеет производные, и условие Липшица с константой будет иметь место, если в некоторой окрестности корня функция имеет производную по модулю меньшую некоторого числа, меньшего единицы, т. е.

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

Введем понятие порядка итерации (4) для решения уравнения (3). Будем говорить, что итерация (4) имеет порядок если

Если имеет в окрестности корня непрерывных производных, то по формуле Тейлора

В случае итерации порядка имеем:

откуда

Обозначая через максимум модуля в некоторой фиксированной окрестности корня получим неравенство

из которого следует:

Таким образом, если то

что дает очень быструю сходимость к а.

Для случая, когда действительная функция переменного действительный корень уравнения (3), метод итерации (4) имеет хорошую геометрическую интерпретацию.

Рис. 6.

Рис. 7.

На рис. 6 и 7 изображена геометрическая картина метода итераций (4) для случаев, когда

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