Главная Промышленная автоматика.

Алгоритм 1016 не nj6 лику ется здесь, потому что соответствующий алгоритм 101 (Kiviat Р. I. «САСА1», 1962, № 6) не был подтвержден ни в журнале «САСМ», ни в расчетах авторов выпуска.

Свидетеньсгв© и аиг©риту Ю26 [G6]

Алгоритм 1026 не публикуется здесь, потому что соответствующие алгоритмы 102а и 102 («САСМ», 1962, № 6) следует считать устаревшими согласно нижеследующему «Замечанию к алгоритмам 87, 102, 130 и 202». Р. Орд-Смита.

-Замечания к алгоритмам 87, 102, 130 и 202

Р. Орд-Смит (Ord-Smith R. J. «САСМ», 1967, № 7)

Сравпенне опубликованных алгоритмов, предназначенных для образования последовательных перестановок в лексикографическом порядке, показывает, что алгоритм 202 наиболее эффективен. Однако, поскольку он более чем в два раза медленнее алгоритма 115 (Trotter Н. С. «САСМ», 1962, № 8), го еще остается простор для усовершенствований. Теоретически «наилучший» лексикографический алгоритм должен быть примерно в полтора раза медленнее, чем алгоритм 115. [См. алгоритм 308 (Ord-Smith R. J. «САСМ», 1967 № 7), который -В два раза быстрее алгоритма 202.]

Алгоритм 87 очень медленный.

Алгоритм 102 заметно улзчшен.

Алгоритм 130 не, имеет опубликованных подтверлдений. Мы обнаружили, что для некоторых форм преобразуемого вектора алгоритм 130 может дать неверные результаты согласно следующему соображению*. При выполнении оператора A[f]:-r в строке перед меткой «shell» переменная f может еще и не иметь значения. Пере.менная f имеет значение, если и только если логическое выражение В[/г] >0 Д < <Б[т] имеет значение true по крайней мере для одного из соответствующих значений k. В частности, если взять матрицу с элементами A[i]=l, то для любого i вышеуказанное логическое выражение при первом обращении к процедуре бдет иметь значение false.

Алгоритм 202 является самым лучшим и самым быстрым из ранее опубликованных алгоритмов.

Сравнительные данные этих алгоритмов сведены в табл. 1. В этой таблице tn - время, затрачиваемое для получения всех п! перестано-

* К алгоритму 130а это замечание не относится. {Прим. ред.)



вок. времена масштабированы относительно 4 алгоритма 202, которое принято за 100.

Проверка делалась на вычислительной машине ICT 1905. Для алгоритма 202 на этой машине 8=100 с. Переменная имеет обычное значение, т. е. rn=tnl (ntn-i).

Т а б л II ц а 1

Алгорита

102 130 202

15.5

1.03

1.08

1.10

12-4

l.CO

1 .СО

1.00

Алгоритм 1036 НС публикзется здесь, пото.му что соответствующие алгоритмы 103 и 103а следует считать устаре:вшими, так как позднее для вычисления интегралов по Симпсону был опубликован более совершенный алгоритм 182а.

Процедура т21 симметричнзЮ ленточную матрицу

аЩ Ь[1] с[1]

Ь [Г] а [2] Ь [2] с [2]

с [1] Ъ [2] а [3] с [2]

Ъ\п- 2\ с [ft - 2] Ъ {п - 2\ а\п-\\ Ъп - !] с{п - 1\ Ь [ft - 1] aiftj

представленнзю массивами а, Ь, с, приводит путем ортогональных преобразований к якобиевой трехдиагональной форме, которая представляется массивами а, Ъ. Этот метод описан в работе X. Рутисхаузе-ра [101]. Заметим, что описания массивов а, Ь, с должны быть заданы с границами индексов от 1 до п. Процедура inform тоже должна быть описана. Она может служить для использования вращения Якоби,



выполняющегося внутри процедуры т21, и для других целей. Процедура inform должна выполнять вращение Якоби аа=иХааХи, где

d S -S d

d к s помещаются в точках пересечения строк и столбцов с номерами / и и - транспонированная матрица и [1, с. 36-42].

procedure m21(n, с, inform) dataresult:(a,b);

value n; integer n; array a,b,c; procedure inform; begin real p,g,d,s; integer k,j;

b[nj: = cfn]:.= c[n-1]:=0;

for k:=2 step 1 until n-1 do begin

for j:.= k step 2 until n-1 do begin

if k=j then

begin p: = sqrt(b[k-l]f2+o[k-l]f2); if p=Q then go to exit; d:==b[k-}]/p; s:=-c[k-l]/p; b[k-l]:=p; c[k-1]:=0 end k=j else

begin p: = sqrt(c[j-2]f2+gf2); if p-0 then go to exit; d: = c[j-2]/p; s:=-g/p; c[j-2]:==p;

p: = dXb[j-l]-sXc[j-l]; c[j-l]: = sXb[j-l]+dXc[j-l]; b[j-l]:=p end кФу,

g:=2Xb[j]XdXs; p:=a[j]XdXd-g+a[j + l]XsXs; b[j]:=(a[j]-a[j + l])XdXs+b[j]X(dXd-a j + l]:=a[j]XsXs+g+a[j + l]XdXd; a[j]:=p;

p:=dXc[j]-sXb[j + l]; b[j + l]:=sXc[j]+dXb[j + l];

-sXs);

сП]:=Р; g:=-sXc[j + cn + l]:=dXc[j + l]; inform (n,j,d,s) end j;

exit: end к endm21;





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

0.0034