с помощью этой процедуры й транслятора решено У1равнение x=f(x)=x-2. Результаты решения даны в табл. 10. (Описание метода см. в [18, с. 171-175].)

Таблица 10

Замечания к алгоритмам 2, 3, 15, 25 и 26

Дж. Г. Вилкинсон (Wilkinson J. Н. «САСМ», 1961,

№ 3)

Алгоритмы 2, 3, 15, 25 и 26 были посвящены вычислению корней произвольных функций последовательной линейной или квадратичной интерполяцией. Главным лимитирующим фактором в достижении точности с помощью таких процедур является обусловленность метода вычисления функции в окрестности корней. Под этим понимается условие, которое должно определять отклонение, допустимое для относительной ошибки. Если метод вычисления хорошо обусловлен, то может быть удовлетворен почти точный Критерий сходимости, даже если функция имеет кратные .корни.

Например, в АСЕ алгоритм нахождения вещественных квадратных корней (подобный алгоритму 25) использовался для отыскания корней трехдиагональной матрицы Г, у которой tii=ai, ti+ij-bi+i, ti4+i = Ci+i. В качестве экстремального случая были взяты а1=а2=аз=Й4=А!5= =0, «6=7=8=09=0:10=1, Gii=2, fet = l, Сг=0, так что функция, подлежащая вычислению, былал;(л;-1){х-2). Несмотря на кратность корней, ответ, полученный на машине с плавающей запятой и 46-разрядной мантиссой, имел погрешность не более 2-. При использовании линейной интерполяции вместо квадратич1Ной в той же задаче были получены результаты с такой же точностью. Поэтому использованный метод решения, т. е. двучленное рекуррентное соотношение между ведущими главными MHHopaiMH, является очень хорошо обусловленным методом решения. Зная это, я мог с уверенностью

нрийяь погрешность равной 2-. Если бы та же самйя функция вычислялась путем ее полного разложения g степенной ряд, то могла получиться погрешность 2-, а кратные корни могли получиться с гораздо более низкой точностью.

Для отыскания нулевых корней необходимо иметь абсолютную погрешность для \xr+i-Хг\ такой же малой, как и относительную погрешность. Нежелательно, чтобы требовалась цредварнтельная проба на нулевые корни. Преимущество алгоритмов отыскания корней таким методом состоит в том, что поскольку мы не связаны проблемой вычисления производной, то имеем большую свободу выбора для вычисления самой функции. Эта свобода нарушается, когда мы строим алгоритм так, что он отыскивает корни уравнения x-f{x), так как в этом случае истинная функция х-tg (х) произвольно разделена на две части. Формальное преимущество употребления такой формулировки незначительно. Поэтому в «Подтверждении к алгоритму 2» (июнь, I960) была сделана попытка вычисления корней уравнения x-tgx. Если бы использовалась функция -x+tgXB общем алгоритме отыскания корня, то щанный метод решения мог бы быть, например, таким:

» cos

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

I (sin -)-(cosy-1) ~ "- --1 +(cos-r)

И тогда решение хорошо обусловлено в окрестности л;=0. Что же касается числа необходимых приближений, то ограничение числом 10 (см. «Подтверждение к алгоритму 2») скорее всего чрезмерно мало. Например, црямое вычисление х-1 хорошо обусловлено, но если начать со значений х-2 и х=1.5, то для нахождения корня х=1 потребуется большое число итераций. Точно так же Очень большое число итераций необходимо для метода Ньютона с начальным приближением х-2. Если время вычисления производной примерно то же самое, что и Для вычисления функции (часто оно намного больше),

to Лйней-иая интерполяция обычно быстрее, а кваДраТйЧ. ная интерполяция намного быстрее, чем .метод Ньютона.

Во всех алгоритмах, включая алгоритм Берстоу, по-лезно иметь (некоторый критерий, который ограничивал бы допустимое изменение независимой переменной от данного значения к следующему (здесь Дж. Вилкинсон ссылается иа свою работу [3i, с. 150-180]. - Прим. ред). Этот критерий встречается в некоторой мере в алгоритме 25 в условии S4 в виде abs{fprt)<abs{x2XlO), но здесь ограничение наложено на допустимое приращение значения функции от одного щага к следующему. Алгоритмы 3 и 25 имеют допустимые попрешности в величине функции и в величине остатков rl и г2 соответственно. Эти погрешности трудно определить, так как величины остатков могут получить очень малые значения и тогда, когда принимать значение х в качестве корня нежелательно.

В алгоритме 3 полезно вернуться к исходному полиному и к итерации с каждым из вычисленных множителей. Это исключает потерю точности, которая могла бы возникнуть, если бы множители не находились в возрастающем порядке. По-видимому, именно такой случай имел место в «Подтверждении к алгоритму 3», когда делалась попытка вычислить корни полинома

х+7х+Ъх+Ы+Зх+2=0.

Однако в АСЕ все корни этого полинома были найдены точно, сходимость при условии требования обычной точности была очень быстрая, но корни .при этом отыскивались в возрастающем порядке. Поэтому ссылка на плохую сходимость вызывает недоумение. В АСЕ сходимость была хорошей для всех выбранных начальных приближений к величинам р и q. Когда начальные приближения брались такими, что первыми были найдены вещественный корень х=-6.3509936103 и ложный (побочный) корень, остальные два квадратичных Множителя оказались низкой точности, хотя, разумеется, они были исправлены путем итерации в исходном полиноме. Когда же любой из двух других множителей отыскивался первым, то все множители были совершенно точ- ными даже без итерации в исходном полиноме.