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

Алгоритл!

первоначальный

модифицированный

хЯ 1 ф

1000

1046

-2092

91002

1002

Не определено

Не определено

-103

47009

2209423

1222234

-289

Нет решения

Нет решения

Алгоритм, модифицированный указанным способом, дал результаты, приведенные в столбцах 6 и 7 табл. 20. Время вычисления на машине В-5000 было равно примерно 40 мс.

АЛГОРИТМ 1406

Упрощенное обращение матрицы [F1]

Процедура invertlAQ {invert - обращать) обращает матрицу а[\:п, с помощью ряда элементарных операций. Хотя метод не

очень хорош для плохо обусловленных матриц, простота алгоритма и тот факт, что обращение производится на месте исходной матрицы а, делает его иногда полезным. При опасности возникновения больших погрешностей (при ai,ieps>0) осуществляется выход к метке-параметру out.

procedure invertUO (n,eps,out) dataresult: (a);

value n.eps; real eps; integer n; array a; label out; begin real q; integer i,j,k; ;

for i:=l step 1 until n do begin

if abs (a [i,!]) eps then go to out;

q:=l/a[i,i]; a[i,i]:=l; ;

for k: = l step 1 until n do a[i,k]: = a[i,k] Xq; for ]:=1 step 1 until n do

if i=7j then ,

begin q: = a[j,i]; a[j,!]5=0;

for k:=l step 1 until n do . ,

a[i,k]:=a[j,k]-qxa[i,k] end j end i end invertl40;

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

Алгоритм 1406 является стереотипным переизданием алгоритма 140а. Хотя в нижеследующем «Подтверждении к алгоритму 140» Р. Георг рекомендует обращать матрицы с помощью других алгоритмов, публикация алгоритма 1406 в данном выпуске представляется оправданной, поскольку этот алгоритм, очевидно, будет выполняться



быстрее, чем алгоритмы, содержащие процесс вращения. В ряде .случаев этот факт может оказаться более существенным, чем ограниченность области применимости.

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

Алгоритм 140а получен в результате модификации и ординарной переработки алгоритма 140 (In germ an P. Z. «САСМ», 1962, № И). Модификация имела цель сократить время выполнения процедуры и заключалась в замене в первом из операторов цикла по k операции деления на операцию умножения.

Алгоритм транслирован с матрицей Вильсона для eps-lQr-

5 7 6 5 7 10 8 7

6 8 10 9 5 7 9 10

С точностью до единицы последней (девятой) значащей цифры получен правильный результат

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

Р. Георг (Georg R. «САСМ», 1963, № 8)

Алгоритм 140 был проверен на машине LGP-30 с использованием языка SCALP и транслятора Вычислительного центра Дартмутского колледжа и показал себя синтаксически правильным.

Это ,п:ействительно простая процедура. Она так проста потому, что автор исключил весьма нужный поиск наибольшего элемента и ряд перестановок. В результате эта процедура не сможет обратить многие невырожденные матрицы. Эта процедура может обратить те матрицы, всеведущие диагональные подматрицы которых будут иметь ненулевые определители.

Лучше обходиться без этого алгоритма, а пользоваться алгоритмом, который применяет процесс вращения (например, таким, как алгоритм 120).

АЛГОРИТМ 1416

4 Метод Уаршала [Н]

Процедура findpath (find -поиск, path - путь) является реализацией в АЛГОЛе метода Уаршала, описанного в работе [181]. Некоторые характеристики задачи использованы для повышения эффективности.



procedure findpath(a,n);

value n; integer n; Boolean array a; begin integer i,j,k;

for ]:=! step 1 until n do for i:=l step 1 until n do if a[i,j] A ij then

for k:=l step 1 until n do a[i,k]:=a[i,k] Va[j,k]

end findpath;

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

Алгоритм 1416 является стереотипным переизданием алгоритма 141а, не отличающегося, в свою очередь, от алгоритма 144 (Ingerm an P. Z. «САСМ», 1962, № 11).

Вследствие элементарности процедуры findpath контрольное решение на машине не проводилось.

Свидетельство к алгоритму 1426 [G2]

Алгоритм 1426 не публикуется здесь потому, что соответствующий алгоритм 142 (Hafley W. L., Lewis J. S. «САСМ», 1962, № 12) ©одержит ряд ошибок и неясностей. Например, было обнаружено следующее:

1) в 8-й строке после метки «inversion:» встречается странный заголовок цикла:

for i3:=i2 step 1 until n while 1311 do

2) в 16-й строке после метки «coeff:» используется else, которому нет соответствующего then;

3) во 2-й строке после метки «initial:» в выражении пХ (n-f-1)/2 опущен знак умножения;

4) имеются и другие ошибки, такие «ак пропуск символа «;»,. использование круглых скобок вместо индексных и т. д.

Модификация алгоритма 142, выполненная Фаянсом О. Г., опубликована в сборнике «Программы и алгоритмы» ЦЭМИ вып. 29 за 1969 г. под названием «Треугольная регрессия».

АЛГОРИТМ 1436

Сортировка с помощью графа [Ml]

Процедура treesortl отсортировывает k наименьших элементов п-компонентного массива unsort в -компонентный массив sort (эти два массива могут совпадать). Число вспомогательных ячеек памяти равно примерно 2Xn--Ax]g(«).

Значение параметра inf (сокращение от infinity - бесконечность) должно быть больше любого элемента массива unsort.

procedure treesortl (unsort,n,k,inf) result: (sort);

value n,k,inf; real inf; integer n,k; array sort,unsort; begin integer i,j; array ml[l:2Xn-1]; integer array ш2[1:2Хп-1];





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.0016