i Подтверждение к алгоритму 3

Дж. С. Вандертрафт (VandergraftJ. S. «САСМ», 1961, № 2)

Процедура bairstow была запрограммирована для •вычислительной машины Burroughs 220 с использованием

* Указываются две поправки, учтенные в алгоритме За. (Прим. ред).

** В нижеследующие уравнения внесены исправления, указанные в «Подтверждении к алгоритму 3» Вандерграфта. (Прим. ред.)

*** Для уравнений нечетного порядка вводятся ложные нулевые вещественные корни. (Прим. Г. Тачера).

**** См. «Замечание к алгоритмам 2, 3, 15, 25 и 26», следующее за описанием алгоритма 266. (Прим. ред.)

Г. Тачер (Thacher Н. С. «САСМ», 1960, № 6)

Процедура bairstow была запрограммирована для вычислительной машины Royal-Precision LGP-30, использующей систему иетерпретации плавающей запятой с 28 значащими разрядами.

Было йайдено необходимым- .внести следующие небольшие поправки... *.

После этих поправок программа прошла хорошо для следующих уравнений **:

х-гх + 20x2 + 44д,- + x = -0.97063897 ± 1.0058076i, + 54 =0, X = 4- 2.4706390 ± 4.€405330i;

х« -2x5 -1- 2х + х + х= 0.50000000 ± 0.86602539i, + 6x2 -бх +i 8 = 0, X = -1.0000000 ± il.OOOOOOOi,

X = 1.6000000 ± 1.3228756i;

x - 8x3 1.6x2 + х.= 0.00000005***, - 0.99999999, + 7х + Г,5 = 0, X = 3.0000000, 0.99999999,

X = - .2.0000000 ± .1.0000000/.

Для уравнения х+7х+Ъх-\-х+х+2= сходимость была плохой, и полная точность не была получена ****. Но для уравнения 2x+3x{-&x+bx+7x-\=i =.0 с обратными корнями сходимость была хорошая.

языка Burroughs-ALGOL. Перевод с языка АЛГОЛ был сделан вручную на основе iHipHHUHna «оператор к оператору». Описание integer должно включать в себя переменные п, k, т, nat, ex *. Кроме того, были включены поправки, указанные в подтверждении Г. Тачера.

Тщательным подбором входных параметров были проверены все ветви программы и получены хорошие результаты. Были решены следующие полиномиальные уравнения:

хб-14x4+49x2-36=0,

jt= ±1.0000000, х= ±1.9999999, х= ±3.0000001;

л:8-30x8+273x4-820x2+676=0,

х= ±11.0000000, х= ±2.0000000, х= ±2.9999999, х= ±4.0000001.

В подтверждении Г. Тачера были обнаружены некоторые небольшие ошибки. Свободный член первого полиномиального уравнения должен быть 54, а не 43, вторая пара корней этого уравнения должна быть +2. 470639± ±4.640533Ог, а вторая пара корней второго уравнения должна -быть -1.0±г.

Подтверждение к алгоритму 3 Дж. Херндон (Herndon J. «САСМ», 1961, № 4)

Процедура bairstow была переведена на язык БАЛГОЛ и провфена на машине Burroughs 220. Были учтены поправки, предложенные Г. Тачером. Результаты были верными для всех уравнений, к которым примени этот метод. Одним из уравнений, которое дало неверные результаты, является x-16=0. Для 12 контрольных уравнений,- одно из которых х«-2х5+,2х4+л:8+6л;2-6х+8=0, получены результаты с семью значащими цифрами.

* По-видимому, Дж. Вандерграфт имел в виду спецификации integer. [Прим. ред.)

Нахождение корней непрерывной функции методом деления интервала пополам [С 5]

Процедура bisec вычисляет функцию на концах вещественного интервала с выходом на метку signal, если нет перемены знака. В противном случае она находит корень методом деления интервала пополам с вычислением функции в середине интервала. Процедура заканчивает работу, если значение функции оказалось меньше лроизвольно заданного eps или если два последовательно найденных приближения корня отличаются меньше чем на epsl. Величину eps следует выбирать .примерно равной погрешности в вычислении функции (иначе .машинное время будет тратиться впустую), а .величину epsl -примерно равной требуемой точности. При этом epsl не должно быть меньше, чем две единицы последнего разряда .машинного слова, иначе возникнет зацикливание вследствие оиругления при делении пополам. Хотя этот метод нулевого порядка и, следовательно, относится к самым медленным методам, он применим к любой непрерывной функции. Тот факт, что эта процедура не соде)р-жит никакой проверки дифференцируемости, делает ее "«надежной рабочей лошадкой» среди .программ отыскания вещественных корней, которые предварительно были вьщелены. Произвольные переменные а и b являются (предположительно) .концами интервала, внутри которого имеется нечетное число корней вещественной функции / [16, с. 72].

procedure bisec(a,b,eps,epsl,f,signal)result: (х);

value a,b; real a,b,eps,epsl,x: real procedure f;

label signal; begin real y,z;

procedure fun(y); real y;

begin y:==f(x);

if abs(y) :<eps then go to fin

end; x: = a;fun(y); x:=b; fun(z);

if sign(y) =sign(z) then go to signal; iter: x: == a/2 -i- b/2; fun (y); .v

if sign (y) = sign (z) then b:=x else a:=x;

if abs(a-b)epsl then go to iter; fin: end bisec: