при дополнительных условпях

оэ со

п =1 п= I

(276)

которым удовлетворяет, например, последовательность а„ = (1/л). Доказано [47], что Хп-х при п->-со с вероятностью единица. Использование в фор-и!уле (27а) знака производной не означает, что надо вычислять эту производную: достаточно лишь определить ее знак по разности двух значений функции.

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

5. Метод Ньютона. Он называется также методом касательных или методом линеаризации. Если л;„ есть некоторое приближение к корню X, а f{x) имеет непрерывную производную, то уравнение (22) можно преобразовать следующим образом:

О = / (x) = / {х„ -f (X - х„)) = / (Хп) -f (х - х„) Г {%).

Приближенно заменяя / () на значение в известной точке х„, получим такой итерационный процесс:

= Х„

(28)

Геометрически этот процесс означает замену на каждой итерации графика y = f{x) касательной к нему (рис. 28).

Метод Ньютона можно рассматривать как частный случай метода простых итераций, если положить ф(л;) = = - [/ {х)1Г {х)]. Тогда ф {X) = {ffin. Если X есть р-кратный корень уравнения (22), то вблизи него f{x) fa{x - x)P; отсюда нетрудно получить ф(х) = (р-1) 7, т. е. Ойгф(л)<1 р=1 и ф (х) = 0. Используя результаты

Рис. 28.

Для простого корня п. 4, можно сформулировать следующие условия сходимости итераций (28). Если нулевое приближение выбрано достаточно близко к корню, ньютоновские итерации сходятся; скорость сходимости велика для простого корня и соответствует скорости геометрической прогрессии для кратного корня. При произвольном нулевом приближении итерации сходятся, если всюду " < (Z); в противном случае сходимость будет не при любом нулевом приближении, а только в некоторой окрестности корня.

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

условие сходимости итераций. Пусть /" (х) 5= О справа от корня на отрезке [х, а]; если х выбрано также справа от корня на этом отрезке, то итерации (28) сходятся, причем монотонно. То же будет, если f" (х) =sc О слева от корня на отрезке [Ь, х], и на этом же отрезке выбрано нулевое приближение. Таким образом, итерации сходятся к корню с той стороны, с которой f (х) /" (х) 0.

Оценим скорость сходимости вблизи простого корня. По определению простых итераций, х - х„ = ф (х) - ф (a;„ i). Разлагая правую часть по формуле Тейлора и учитывая равенство ф (х) = О, получим

Хп-х = 1/2 -xf ф" (?), I е (х„ 1, X),

(29)

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

6 верных знаков, а {п-\-\)-я

Таблица 16 Дл:) еее;л;2 -4 = 0

Примерно 12 знаков. Это иллюстрирует быструю сходимость вблизи корня. Разумеется, вдали от корня подобные соображения неприменимы.

Если вычисляется корень высокой кратности, то f (х) в знаменатеде формулы (28) становится малой вблизи корня. Чтобы не было потери точности, отношение / {x)/f (х) надо вычислять достаточно аккуратно. К остальным погрешностям расчета метод Ньютона хорошо устойчив.

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

Пример. Рассмотрим решение уравнения f{x) = x - a = 0. Тогда общая формула метода Ньютона (28) принимает вид

1 / а\

ХпЛ-

Мы получили вторую формулу (25), которая, как отмечалось раньше, позволяет очень быстро находить квадратный корень с помощью только сложения и деления. Для иллюстрации в таблице 16 приведен ход итераций при извлечении квадратного корня из а = 4. Видно, что сходимость очень быстрая; несмотря на неважное нулевое приближение, уже третья итерация дает точность 0,005%. Попутно можно заметить, что вблизи корня итерации сходятся с одной стороны, т. е. монотонно, хотя первая итерация дает переброс на другую сторону корня.

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

(fix) = (f" {х)= ... =tf>P-(х) = 0, (f<P<(x)Q. (30)

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

.(х„,х). (31а)

Xni - X = ф {Хп) - ф (х) -i- (ДГ„ - Х)Р фР (I), I I

Если 1 ф* {х) 1 Мр, то отсюда следует

\х-х\(Мр1р\)(р"- IP-Xa-xf. (316)

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

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

7. Метод секущих *) [48]. В методе Ньютона требуется вычислять производную функции, что не всегда удобно. Можно заменить производную первой разделенной разностью, найденной по двум последним итерациям, т. е. заменить касательную секущей. Тогда вместо процесса (28) получим

(Xn-Xn-l)f(Xn)

(32)

j:j Хг X, Xa Рис. 29.

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

Эти, казалось бы, небольшие изменения сильно влияют на характер итераций. Например, сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня. Скорость сходимости также изменяете. Иллюстрацией служит приведенный в таблице 16 расчет по методу секущих; для удобства сравнения с методом Ньютона первые два

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