Главная страница  Алгоритмы 

[0] [1] [2] [ 3 ] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]

ex[i\=\, если uO, ul стали по модулю меньше epsl;

ex[i]=Q, если поправки corp, corq {cor - начальные буквы слова correction - поправка) становятся по модулю меньше eps2;

ехЩ =3, если отношения cor pip, corqjq становятся меньше eps3;

ел:[1] =4, если число итераций становится равным max.

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

Входные массивы х, у, nat и ех должны иметь размерность [1 : {п+\).-й\.

procedure bairstow(n,a,eps0,epsl,eps2,eps3,max)

result: (num,x,y,nat,ex);

value eps0,epsl,eps2,eps3,n,max;

real eps0,epsl,eps2,eps3; integer n,max,num;

array a,x,y; integer array nat.ex; begin real p,q,corp,corq,uO,ul,vO,vl,wO,wl,det,s,t;

integer i,j,k,m,n2,r; array b,c[0:n + l];

for i:= 0 step 1 until n do b[i]: = a[i];

bl[n+l]:=0; n2:=(n + l)2;

г:=2Хп2;

for ra:= 1 step 1 until n2 do begin p: = q:=0; for k: = 1 step 1 until max do labl: begin

for i:= 0 step 1 until r do cli]:=b};i]; for i:- г-2,r-4 do for j:=0 step 1 until i do begin o[j +1]:=cl. +1]-pХоЦ];

clj+2]:-:c[j+2-qXcfj] end

uO: = a[r]; ul: = clr-1]; vO:-=cfr-2]; vl: = ctr-3]; wO:==-qXvl; wl:=vO-pXvl; det:=vOXwl-wOXvl; Sf abs (det) <epsO then begin p: = p + l; q:=q-i-l;

go to labl end;

corp:= (vOXul-uOXvl)/det; corq:= (uOXwl-wOXul)/det;



р: = р+согр; q: = q+corq; if(abs (uO) <epsl) д (abs(ul) <epsl)then

begin ex[m]: = l; go to lab2 end; If (abs(corp) <eps2) Д (abs(corq) <eps2) then

begin e4m]:=2; go to lab2 end; И (abs(corp)<eps3Xabs(p))Д (abs(corq*) <eps3Xabs(q)) then begin exlml:=3; go to lab2 end

end k; exfm]:-4; lab2: s:=-p/2; t:=sxs-q; if tO then

begin natlml: = 1; t: = sqrt (t); xrm]: = s--t; уГт]:=8-t \ end else

begin nat[ml:=-1; x[ni]:=s; y[m]:=sqrt(-t) end;

Tf ex[m]=4 then go to out; r:=r-2;

for j:=0 step 1 until r do begin bO +1]:=bQ + Ibp Xb[j];

brj+2]:=b[i+2]-qXbin] end; !f r<l then but: begin num:=m; go to fin end;

If r<3 then begin m:=m + l; ex[m]: = l; рГ=зЬ[1]/Ь[01; q:=bl2]/b[0]; go to lab2 end end m; fin: end bairstow;

Свидетельство к алгоритму 36

Алгоритм 36 получен в результате следующих усовершенствований в алгоритме За.

1. Условие [24, с. 10, Ш-я стр. сверху], if (abs(corp/p)<eps3) Д (abs (corq/q) < eps3) then было заменено эквивалентным ему условием if (аь8(согр)<ер83ХаЬ8(р))Д (abs(corq) <eps3Xabs(q)) then



поскольку, как выяонилось, при решении на машине М-220 второго из примеров Дж. Вандерграфта (см. ниже «Подтверждение к алгоритму 3») в этом условии возникает деление на нуль.

2. В заголовке процедуры bairstow был добавлен список значений.

3. Оператор n2:=entier{{n+\)l2)\ был заменен для краткости оператором п2:={п+\) -i-Q,.

4. В пояснительном тексте к алгоритму было добавлено указание размерностей входных массивов х, у, nat, ex.

Алгоритм 36 был транслирован в системе ТА-1М для машины М-220, и при eps0=epsl=eps2=eps3=l0- и тал:=.10 000 было повторено решение всех примеров, приведенных в «Подтверждениях» Г. Тачера, Дж. Вандерграфта и Дж. Херндона. Полученные результаты с точностью до одной единицы последней значащей цифры совпали с результатами, приведенными в вышеупомянутых «Подтверждениях». Вопреки утверждению Дж. Херндона (см. ниже его «Подтверждение») о неприменимости этого метода к уравнению х-16=0 было получено правильное решение х={2, 0), у-(-2, 2), nat= (1, -1) даже и для этого примера.

Свидетельство к алгоритму За

Алгоритм За получен в результате перевода с языка АЛГОЛ-58, исправления, сшфащения и ординарной переработки алгоритма 3 (G г а и А. А. «САСМ», 1960, № 2).

После переработки алгоритма были проведены контрольные решения на трансляторе для двух уравнений. Для уравнения

л:-2x5+Sjc++6x2-6л:+8=О получены результаты:

X = 0.500000000 ± 0.866025381, х=- 1.00000000 d= l.OOOOOOOOi, х= 1.50000000 ±1.3228757i. Для уравнения

хб-14x4+49x2-36= (х2-1) (х2-4)i(x2-9) = О - результаты

х= ±11.00000000, х= ±2.00000000, х= ±3.00000000.




[0] [1] [2] [ 3 ] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]

0.0297