Главная Промышленная автоматика. Данная процедура в действительности обращает не только положительно определенные симметричные матрицы (как это сказано у Дж. Кафри в описании алгоритма 66. - Прим. ред.). По-видимому, требуется только ограничение, чтобы ведущие миноры матрицы были не нулевыми. Переменная а[1,1] последовательно принимает значения отношения (г-Ы)-го к г-му ведущему минору матрицы, и если о.но становится равным нулю, то переменная р не может быть вычислена. Следующая матрица, в которой последовательными значениями а[\,\] были +2, -2, -1, -0.6, -Ь5, дала результаты, верные с точностью до единицы пятой значащей цифры: 2-3 1-1 4 3 2 -4 3 -2 1-4-3 2 4 -1 3 2-2 -3 4-2 4-3 2 Подтверждение к алгоритму 66 Дж. Кафри (С af f геу J. «САСМ», 1962, № 6) Эта процедура была транслирована с помощью системы BALCOM в Стенфордском университете при использовании 8-разрядной арифметики с плавающей запятой. Опечатка, указанная Ранделом и Брой-деном («САСМ», 1962, № 1), была исправлена, и в качестве теста использовался тот же пример (матрица Вильсона 4X4). Результат обращения 68.0000 -41.0000 -17.0000 10.0000 25.0000 10.0000 -6.0000 5.0000 -3.0000 2.0000 Полезно также отметить, что определитель матрицы может быть получен как результат последовательного перемножения значений главных элементов. Таким образом, если U (равный gJ1,1] ) является главным элементом матрицы порядка п, то определитель = J г. Для вышеприведенного примера определитель равен единице. Замечание Рандела и Бройдена относительно кажущегося ограничения этой процедуры случаями положительной определенности является правильным. Иначе говоря, любая невырожденная вещественная симметричная матрица (положительная, отрицательная или неопределенного знака) может быть обращена с помощью этого алгоритма. Следовательно, первоначальный вариант процедуры должен быть дополнен оператором if р=0 then go to signal. Второй пример Рандела и Бройдена (матрица пятого порядка) был-также использован в жачестве теста со следующими результатами: -0.0000 0.9999 0.0000 0.0000 0.9999 1.5333 -0.7333 -0.1333 0.7999 -0.8666 -1.0666 -0.5999 -1.4666 -0.1999 0.2000 Определитель равен -14.999999. При попытке обратить обращенный сегмент 4X4 матрицы Гильберта, как предложено Ранделом («САСМ», 1962, № 1, с. 50), получены следующие результаты: 0.9999 0.4999 0.3333 0.2499 0.3333 0.2499 0.1999 0.1999 0.1666 0.1428 Определитель равен 6048020.6. АЛГОРИТМ 676 Умножение уплотненной симметричной матрицы на прямоугольную [F1] Процедура cram [cram - уплотнение, втискивание (в память) умножает симметричную матрицу е[1:п,1:п] на прямоугольную Ь[\:п,\:г\ в предположении, что во входном одномерном массиве а[1:ях (п+1)/2 построчно записана верхняя треугольная часть (включая главную диагональ) матрицы е. Результат помещается на место матрицы Ъ. В процессе выполнения процедуры cram значения элементов присваиваются элементам a[mi+f\, где mi={2n-г) (г-(1)/2. Из последнего соотношения можно найти, что mi+i=mi+n-i. Это позволяет вычислять значения т рекурсивно, имея mi=0. Такое уплотнение симметричной матрицы может быть полезно, например, тогда, когда она не помещается целиком в свободную часть памяти машины. procedure cram(a,n,r) dataresult: (b); value n,r; integer n,r; array a,b; begin real s; integer i,j,k,m; array v[l:n]; for ]: = 1 step 1 until т do begin for i:=:l step 1 until n do begin s:=0; m:==i-n; for k: = 1 step I until n do begin m:=m-f (if ki then n-M-к else 1); s: = s-i-a[m]xb[k,j] end k; v[i]:=s end i; for i:=l step 1 until n do b.[i,j]:=v[il end] . end cram; Свидетельство к алгоритму 676 Алгоритм 676 получен в результате модификации алгоритма 67а, имевшей целью его упрощение и состоявшей в следующем. 1. Из заголовка процедуры был исключен параметр р. В соответствии с этим был вычеркнут оператор р:=п+\, а 1-я строка на 41 с. [6] была заменена на begin m: = m-b (if ki then п-Ы-к else 1); 2. Был .вычеркнут второй оператор тела процедуры, обеспечивавший ввод массива а, пОСкольку такой ввод только сужал область применимости процедуры. Вследствие такого исключения стал ненужным и первый оператор тела прОцедуры k:=nx (п-Ь1)/2; ПоСле этих модификаций алгоритм был транслирован в системе ТА-1М для М-220 с примером, приведенным в «Свидетельстве к алгоритму 67а» и дал правильный результат. Массив а при этом задавался в виде G= (О, 4, 10, 8, 18, 40). Свидетельство к алгоритму 67а Алгоритм 67а получен в результате исправления, сокращения, модификации и ординарной переработки алгоритма 67 (Caffrey J. «САСМ», 1961, № 7). Модификация состояла в исключении массива с (для экономии памяти) и замене процедуры ввода READ процедурой inreal, рекомендованной журналом «САСМ» в разделе «Алгоритмы» в мае 1964 г. [2, Приложение 1]. Алгоритм проверен с исходными данными
И получен правильный результат Подтверждение к алгоритму 67 А. П. Релф (ReИ А. Р. «САСМ», 1962, № 6) Процедура cram была транслирована при помощи DEUCE-ALGOL транслятора со следующими исправлениями ... * Сзидетельстзо к алгоритму 686 [А1] Алгоритм 686 не публикуется здесь, потому что соответствующий алгоритм 68 «Пополнение одного числа другим» (R i с е Н. G. «САСМ», 1961, № 8) является примитивным, назначение его неясно и полезность его представляется сомнительной. * Указываются две опечатки в алгоритме 67 и предлагается изменить оператор ввода. (Прим. ред.) 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 42 43 0.0024 |