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

Заключение. Процедура итерации оканчивается точно или выполняет одну дополнительную итерацию в каждом случае. Если процедура equilibrate изменяет исходные данные, то итерация сходится К решению для измененной матрицы. Если матрица плохо обусловлена, как в вышеприведенном случае, то применение процедуры equilibrate может стать нерациональным. На практике замена процедуры equilibrate процедурой в машинном коде, не округляющей исходные данные, является, вероятно, наилучшим методом решения.

Процедура eguUidrate

-Me итерации,-

. . 1 .1--

тцедура crout 1 1

10 20 30 fO Порядок матрицы л

Рис. 2.

Распределение затрачиваемого времени между различными фазами алгоритма показано на рис. 2 (см. [61]).

Замечание к алгоритму 135

Л- Мейснер (М е i s s п е г L. Р. «САСМ», 1965, № 2)

1- В опубликованном алгоритме замечена следующая ошибка: процедура ipl формирует сумму произведений А{1,р\у,А{р,11\- Однако во второй строке от конца процедуры crout делается попытка использовать ipl для образования суммы произведений Л [А,р] ХЛ[р,/].

Возможный путь исправления этого состоит в добавлении процедуры ipla, которая идентична процедуре ipl, но такой, что k написано вместо i, а ; - вместо k. Поскольку процедура используется часто, делать поправку таким способом неразумно. Лучше было бы модифицировать процедуру crout так, чтобы использовалась более общая процедура inner product*.

2. Следующее сказано в связи со ссылкой на этот алгоритм в «Замечании» Ротенберга (см. [7i, 81]).

При использовании алгоритма 135 для вычисления определителя было бы хорошо задавать т (число правых частей) равным единице вместо нуля и задавать любые ненулевые правые части, например 1,0, О, ... . Это вызовет определение обусловленности и, возможно, выход к метке signallZb, когда определитель теряет смысл **.

* См. алгоритм 436, процедура scalar. (Прим. ред.) ** См., например, [11, с. 77]. {Прим. ред.)



АЛГОРИТМ 1366

Расширение группы [Z]

Процедура enlargegroup {enlargement -расширение, group -труп-па) объединяет ©лемент g с группой gg из п элементов для образования новой группы. Логическая переменная abel должна иметь значение true, если группа, которой принадлежат gg и g, абелева.

В процедуре enlargegroup используются две нелокализованные процедуры multiply (умножать) и equal (равны), которые должны быть описаны в программе, использующей процедуру enlargegroup. После выполнения оператора multiply {gg[i], gg[j], gg[k]) элемент gglk] становится равным произведению элемента gg[i] на gg[}]- Значения указателя логической функции equal {gg[i], gg[j]) есть true тогда и только тогда, когда элементы gg[i] и gg\j] тождественны.

После выхода из процедуры enlargegroup расширенная группа запоминается в g, а п становится равным числу элементов в новой, подгруппе gg. Массив g-g- остается неизменным, если g уже содержится в gg. Возможно, что g и элементы gg будут массивами, и тело процедуры на практике нужно будет существенно изменить

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

О расширении групп см., например, работу А. Г. Куроша [10].

procedure enlargegroup (g,abel) dataresult: (gg,n);

value abel,g; real g; integer n; Boolean abel; array gg; begin integer i,j,k;

for i:=l step 1 until n do

if equal (gg[i],g) then go to final; n:=n+l; gg[n]:=g; for i:=n step 1 until n do for j:=l step 1 until n do

begin multiply (gg [i] ,gg[j] ,gg [n-Ы ]); for k:=l step 1 until n do

if equal(gg[k],gg[n-M]) then go to notnewl; n:=n-f-l; notnewl: if abel then go to next;

multiply (gg [j ] ,gg [i] ,gg [n -Ы ]); for k:=l step 1 until n do

if equal (gg [k] ,gg [n -f-1 ]) then go to next; n:=n-M; next: end J; final: end enlargegroup;

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

Алгоритм 1366 получен в результате исправления и сокращения -записи алгоритма 136а. В алгоритме 136а была исправлена одна ошибка (содержавшаяся и в алгоритме 136), заключающаяся в том, что формальный параметр g, используемый в теле процедуры как простая переменная, был специфицирован как массив.

Алгоритм 1366 был транслирован в системе ТА-1М на машине М-220, и с его помощью были правильно решены следующие две задачи.



1. Абелева подгруппа g=(0,5) расширялась до абелевой группы, состоящей из всех десяти однозначных чисел, по отношению к операции сложения по модулю десять. При этом задавались параметры g-g-= (0,5,0,0,0,0,0,0,0,0), п=2, abeltrue, а тагсже

Boolean procedure equal (а,Ь);

value a,b; integer a,b; equal:=a=b

и • . •

procedure multiply (a,b,c);

value a,b; integer a,b,c; begin c:=a-f-b;

if clO then c:=c-c-blOXlO

Для g=l, 2 и 6 были соответственно получены gg= (0,5,1,6,2,7,3,8,4,9), gg= (0,5,2,7,4,9,6,1,8,3), gg= (0,5,6,1,2,7,8,3,4,9): Bo всех случаях выходное значение п=10.- В начале ведущей программы массив gg был описан как integer array gg[l:ll].

Следует заметить, что в общем случае размерность массива gg должна быть на единицу больше, чем- предполагаемое количество элементов в расширенной группе.

2. В условии предыдущей задачи был заменен только оператор с:=а + Ь в теле процедуры multiply на оператор с:=2Ха-\-Ь. В результате этой замены по отношению к операции, определяемой этой новой процедурой multiply, обе группы стали неабелевыми. Поэтому параметр abet задавался как false, остальные параметры (т. е. п, gg и equal) оставались прежними. В результате для g"=l, 7 и 4 были соответственно получены

(0,5,1,2,7,3,4,9,6,8), gg=(0,5,7,4,9,l,8,3,2,6), gg= (0.5.4,8,3,2,6,1,9,7).

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

Алгоритм 136а получен в результате ординарной переработки алгоритма 136 (W el 1 s М. «САСМ», 1962, №. 11).

АЛГОРИТМ 1376

Свертывание оператора цикла с экономией времени (рекурсивная процедура) [02]

Процедура forsl (сокращение от for statement - оператор цикла) заменяет собой (свертывает) «п-слойный» оператор цикла, подоператором которого является обращение к процедуре р (известно, что любой оператор цикла может быть приведен к такому виду). Два массива i и и дают значение параметра цикла и его верхней границы соответственно для каждого уровня. Размерность массивов i,u[l:n].

procedure forsl (n,p,u,i);

value n; integer n; integer array i,u; procedure p; begin integer j;

if n=0 then p else





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