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

Данная процедура в действительности обращает не только положительно определенные симметричные матрицы (как это сказано у Дж. Кафри в описании алгоритма 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].

Алгоритм проверен с исходными данными

, 6 =

И получен правильный результат

Подтверждение к алгоритму 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.0018