Главная Промышленная автоматика.
Алгоритм, модифицированный указанным способом, дал результаты, приведенные в столбцах 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 |