АЛГОРИТМ 176

Решение трехдиагональной системы линейных алгебраических уравнений (с сохранением входных массивов) F4]

Процедури fridiag дает решение трехдиагональной системы линейных алгебраических уравнений: aiX2+biXi+di-0,

aiXi+i+biXi + CiXi.-i+di=0 для i=2, 3,..., n-l,

bnXn-CnXn-i + dn = Q.

Этот метод часто используется для решения разностных уравнений второго порядка.

Длина массивов а, Ь, с, d от I до п, причем с[1] = =й[п]-О, длина массива х от О до п, Ь{1]Ф0. procedure tridiag(a,b,c,d)order: (n) result: (x);

value n; integer n; array a,b,c,d,x; begin integer i; array g[0:n]; g[0]:=x[0]-.=0; for i:= 1 step 1 until n do begin g[0]:=b[i]+c[i]Xg[i--lI; gn]:=-a[il/g[0];

x[i]:(cli] X x[i-l]-l- d[i]) /g[0] end; .

for i:= n step -1 until 2 do xli-l]:=xraxg[i-l]+x[i-l] end tridiag; - . »

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

Алгоритм 176 отличается от алгоритма 17а только тем, что из списка значений процедуры tridiag были исключены массивы а, Ь, с, d, поскольку вызов их по значению не дает никаких .выгод и приводит лишь к затратам машинного времени.

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

Алгоритм 17а получен в результате сокращения и ординарной переработки алгоритма 17 (Sp rague С. F. кСАСМ», 1960, № 9).

С помощью транслятора ТА-1 решена система трех finneUHbix уравнений:

x,-f2x, -3 = 0, . 2x, + 2x,-f -6 = 0,

Получены правильные результаты: 1.00000000, 1.00000000, 2.00000000.

АЛГОРИТМ 186

Рациональная интерполяция с помощью непрерывных дробей [El]

Процедура confr (сокращение от слов continued - непрерывная - и fraction - дробь) данным т точкам {Хг, Уг) ставит В соотвстствис непрерывную дробь в форме

-- 1

Процедура приводит также эту непрерывную дробь к рациональной функции

bt-irbiX + ...+ bjgXe dc + diX-\- . .. + dugXe

где deg не больше чем т-м2 \{deg - сокращение от слова

degree - степень).

procedure confr (m,x,y) result: (a,b,d);

value m; integer m; array x,y,a,b,d; begin real r,s; integer i,j,k,ml; array p,qi[0:m-i-2]; for j:= 1 step 1 until m do begin r:=yffl; s:==xO]; for i:= 1 step 1 until j-1 do

г:==(8-хИ)/(г-аШ); a{j]: = r end j; p[0]: = l; qlO]: = a[ll; ml:=m-f-2; k: = l; mult: for i.: = -l step 1 until ml do рШ:= qW:-0; for i: = 2 step 1 until m do begin

forj==iH-2step -1 until 1 do begin r: = a[ilXq[j]-xli- 1}Xplj]+rfj-l];

P0]: = qtj!l;q{j]:=r end j;

r: a[i] Xqt0]-xli-1 ] Xp [0] ;p [0]:=q[0]; qCO]:=r end i;

if к=2 then go to fin;

for !:= 0 step 1 until ml do ЬШ: = яШ;

к:=2; p[0]:=0;

qCO]: = 1; go to mult; fin: for i:=3 0 stepl until ml do (5p]: = q[i] end confr;

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

Алгоритм 186 является стереотипным иереизданием алгоритма 18а.

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

Алгоритм 18а получен в результате исправления, сокращения, некоторой оптимизации и ординарной пере-раббтки алгоритма 18 (Floyd R. W. «САСМ», 1960, № 9).

Проведено контрольное решение на трансляторе ТА-1. Для пяти точек {х.и tji), указанных в табл. 7,

Таблица 7

определялась соответствующая непрерывная дробь в форме

X - X,

X - Xi

х - х.

а также соответствующая рациональная функция bo + bx + bjX-

Получены результаты, совпадающие с результатами ручного счета (табл. 8).