Главная страница  Алгоритмы 

[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] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]

трансляторов, использующих стандартный сокращенный вариант языка АЛГОЛ-60 [19], и должна быть для вих исключена из процедуры crout. real procedure scalar (u,v) index: (к) start: (s) finish: (f);

value s,f; real u,v; integer k,s,f; begin real h;

h:=0;

for k:= s step 1 until f do h:=h+uXv; scalar: = h end scalar;

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

Алгоритм 436 .получен из алгоритма 43а путем внесения в него .модификаций, предложенных И. А. Григорье-выМ в нижеследующем «Подтверждении к алгоритму

Алгоритм 436 был транслирован на машине М-220 в системе ТА-1М и на машине Б,ЭСМ-6 в системе БЭСМ-АЛГОЛ, и с его помощью были повторены расчеты Г. Тачера, указа.нные в его «Подтверждении к алгоритму 43» (см. ниже). Поскольку транслятор ТА-1М .работает на сокращенном языке АЛГОЛ-60, то перед трансляцией в алгоритм были внесены изменения, заменяющие обращение к процедуре scalar на операторы цикла, как это указано в нижеследующем «Свидетельстве к алгоритму 43а». В результате трансляции на М-220 было получено значение у-(0.15929113, 0.14691773, 0-М257480, 0.0Ш840711), отличающееся от приведенного Г. Тачером не больше чем на 7X10-.

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

Алгоритм 43а получен в результате сокращений и ординарной переработки алгоритма 43 (Thacher Н. С. «САСМ», 1961, № 4).

В случае использования транслятора .па уровне стандартного сокращенного варианта языка АЛГОЛ-60 (IFIP SUBSET) процедуру scalar нужно исключить из процедуры crout. Например, оператор

а [i,k]: = а [i,k]-scalar (а [i,p] ,а[р,к] ,р, 1 ,к- 1); можно заменить операторами: s:=0;

for р:= 1 step 1 until k-l do s:=s + a[i,p]XaIp,k]; a[i,k]: = a[i,k]-s;



Процедура crout была проверена в системе -TA-l с исходными данными, указанными в нижеследующем ;10дтверждении Г. Тачера. Получены результаты, совпадающие с точностью до 8 значащих цифр с результатами Г. Тачера.

Подтверждение к алгоритму 43 Г. Тачер (Th а с her Н. С. «САСМ», 1961, № 4)

Процедура crout была ва1пролрамми)рована вручную для вычислительной машины LGP-30, использующей интерпретирующую систему (модифицированную 24.2) с 28-разрядной 1мант1Иссой и -плавающей запятой. Программа .была .проверена для системы линейных уравнений

дала

12.1719

27.3941

1.9827

7.3757

6.6355

8.1163

23.3385

9.8397

4.9474

6.1304.

3.0706

13.5434

15.5973

7.5172

4.6921

3.0581

3.1510

6.9841

13.1984

2.5393

дала следующие результаты: 12.171900 27.394100 0.25226957 6.632702Г 0.25124262 -0.56260107 0.66680633 " 0.76468695" 6.6354999 3.0181653 2.570202© -0.082780734

1.9827000 15.097125 14.979620

7.3756999 5.6565352 14.527683

-0.20207132 -1.3606142

0.15929120

, pivot =

0.14691771

. У =

0.11257482

0.060840712

det = - 1645,4499.

[ Все элем.енты матрицы АЬ - у были по величине, меньше чем 10"". Такие же результаты были получены : тем же вектором Ь, по при repeat=ir-\ie.. С тем же век-гором b .и последней строкой .матрицы А, замененной

на (19.1927 33.4409 -25.1298 -5.2eiil) *, т. е. Ai„j==

,,=;Л1,з + 2Л2,з-ЗЛз,,-, получены результаты:

к, de/=0.10924352 X10-"

f i/=. (0.29214425X108, -0.12131172X10», 0.72411923 X XIO -0.51018392X10).

* Эта .строка исправлена в соответствии t нижеследующим («Подтверждением» К. Доминго и Ф. Родригец-Гила. (Прим. ред.)



Неудачное решение с такой необычной матрицей объяс, няется ошибками округления либо при вводе данных либо лри вычислении.

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

Д. Доминго, Ф. Родригец-Гил (D о m i п g о С, R о d г i g U е Z-G i 1 F. «САСМ», 1963, № 8)

Процедура crout была запрограммирована и провере-на на машине IBM-1620. Было использовано два типа подпрограмм scalar. Первая из них для HOBbmeHHH точности находит скалярное произведение, пользуясь операциями с фиксированной запятой и 32-раз1рядным сумматором. Вторая нользуется обычной плавающей запятой и 8 значащими цифрами. При использовании единиц в качестве правых частей был обращен сегмент 6X6 матрицы ГИлъбертт~Обра"ш:етаая матрица была обращена снова.

Максимальная раз1ница между полученными результатами и исходным сегментом матрицы Гильберта была:

прииспользованиипроцедуры scalar с фиксированной запятой максимальное отклонение 8.2426X10~*

значение определителя 4.7737088X10-"

при использовании процедуры scalar

с плавающей запятой максимальное отклонение 3.014016X10"

значение определителя 4.4950721X10-"

В алгоритме 43 обнаружены две опечатки... *.

Предыдущее .подтверждение этого алгоритма («САСМ», 1961, № 4) было вновь проверено с теми же результатами. В подтверждении обнаружены две ошибки: строка, которой следует заменить последнюю строку матрицы А для получения вырожденной матрицы, должна иметь вид

19.1927 33.4409 -26.1298 -5.2811.

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

И. В. Григорьев, Москва, май 1970

Алгоритм 43а был использова.н нами во Многих задачах на. машине БЭСМ-6 в системе БЭСМ-АЛГОЛ и всегда давал правильные результаты.

* Указываются две опечатки и одно сокращение алгоритма 43, учтенное пря составлении алгоритма 43а. {Прим. ред.)




[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] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]

0.0179