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

с этими изменениями обе процедуры легко прошли через транслятор. Для сравнения каждая из них была проверена следующим образом. С довольно большим заданным значением eps процедура была применена для обращения сегмента матрицы Гильберта. После аварийного выхода к метке signal значение eps было разделено на 10, и сделано новое обращение к процедуре. Таким способом получили оценку наибольшего допустимого eps. После получения обращенной матрицы был вычислен тот ее элемент, который имел максимальную погрешность, найденную сравнением с точной матрицей, обращенной с помощью процедуры INVHILBERT (алгоритм 50). Относительная погрешность была получена делением на наибольший элемент точной обращенной матрицы.

Этот процесс выполнен для сегментов матрицы Гильберта от 2-го до 15-го порядков. Для порядков свыше 9-го погрешности стали больше результатов. Для порядков ниже 9-го получены результаты, приведенные в табл. 5 (алгоритм 120).

Таблица 5

Порядок

Определитель

Максимальная ошибка

Относительная

Индексы

Ошибка

максимальная ошибка

2 3 4 5

10-2 10- 10-* 10- = 10- 10-

10-10

8.ЗЗЗЗЗЗЗ10-2 4.6296284i„-4 1.6534314,0-7 3-7490001,„-12 5.360I875i„-18 4.8485529,0-25 1.5221000,0-33

[2,2] [2,2 3,3 4,4 5,5 [5.5 [6,6

2.98,0-8

5.01,0-5

3.06,0-2

1.38,о1

5.78,оЗ

3.70,о5

3.33,о9

2.48,0-9 2.61,0-7 4.72,0-6 7.72,0-5 1.31,0-3 2.77,0-3 7.84,0-1

Такие же результаты и отношение ошибок двух процедур получены для gjr (см. табл. 6).

Таблица 6

Порядок

Максимальдая ошибка

Индексы

Ошибка

Относительная максимальная ошибка

Отношение ошибок алгоритма 120 к алгоритму gjr

10-2 10- 10-* 10-« 10- 10-« 10-10

2,1 2,2 4,3 4,4 5,5 5.5 7,7

2.98,0-8

2.86,0-6

1.07,0-4

2.48

4.05,оЗ

4.32,о6

5.55,о7

2.48,0-9 1.49,0-8 1.65,0-8 1.39,0-5 9.18,0-4 3.24,0-2 1.31,0-2

1.0 18.0 290.0

0.086 60.0

Хотя превосходство алгоритма gjr, который производит поиск главного элемента как по столбцам, так и по строкам, над алгоритмом 120, который производит поиск только в очередном столбце, хорошо показано в последней колонке табл. 6, результат для п=7 является странным и должен быть подтвержден еще где-нибудь.

В качестве дополнительных тестов обеих процедур были использованы матрицы, полученные с помощью алгоритма 52 (см. «Подтверждение» выше). Снова погрешность обращения находилась сравнением



с известным результатом обращения. Срав-нение двух процедур было сделано для порядков 2, ..., 23 и показало удивительно малую разницу в точности. Типичный результат приводится в табл. 7.

Таблица 7

Порядок

Местонахождение и величина максимальной сш1-.6ки

Алгоритм 120

Ивдексы

Ошибка

Алгоритм qjr

Индексы

Ошибка

Отношение ошибок алгоритма 120 к алгоритму

5 10 15 20

[5,5] 10,10 15,15 20,20

3.76,„-6 2.12„-5 6.81,„-5

[5.5] 10,10

15,15 20,20

8 •94,0-8 3.52,0-6 1.78,0-5 6.71,0-5

1.00 1.07 1.19 1.02

Относительные ошибки в величинах определителей, вычисляемых алгоритмом 120, возрастают по п медленно, достигая 2.3io-7 для п=24.

Типичные значения времени выполнения (в секундах) приведены в табл. 8.

Таблица 8

Порядок

Алгоритм 120

Алгоритм д{г

Однако следует заметить, что вследствие автоматической сегментации программы по дорожкам барабана в системе GIER ALGOL время выполнения может кое-где отличаться от программы, в которой процедура используется по-другому. Вышеприведенные значения времени фактически относятся не к одной и той же программе.

Замечание к подтверждению процедур обращения матриц

К. Молер (Moler С. «САСМ», 1963, № 7)

В предыдущем «Подтверждении» П. Наура (Naur Р. «САСМ», 1963, № 1) две процедуры обращения матриц были проверены обращением автоматически получаемых матриц Гильберта и сравнением результатов с теоретически обращенными матрицами. Как было показано в работе Дж. Вилкинсона [51], такая проверка является неудовлетворительной, вводящей в заблуждение. Здесь дополнительно рассматриваются возникающие трудности.

Матрицы Гильберта даже низких порядков настолько плохо обусловлены, что малые погрешности, возникающие в результате усечения или округления их элементов при выравнивании машинного слова, вызывают большие изменения в соответствующих им обращенных матрицах. Поэтому результаты процедуры обращения должны сравниваться с истинными результатами обращения этих модифицированных исходных матриц, а не с результатами обращения неизмененных матриц Гильберта.



Для большей определенности пусть Я„ обозначает матрицу пХп Гильберта, определяемую с помощью равенств

(Я„)г,з=1/(г+/-1), где /,/=1, .... п.

Пусть Я означает матрицу, составленную из нормализованных чисел

с плавающей запятой и с мантиссой из b двоичных разрядов, получающейся усечением двоичного представления элементов Я„, т. е.

где [х] - наибольшее целое, не превышающее х, а k - это целое, для которого 7г2(п)1,/<С Через Г„ и Т" обозначим истинные результаты обращения матриц Я„ и Н соответственно.

В табл. 9 даются максимальные элементы матриц Т„ и Т" для нескольких значений п я Ь. Следует отметить, что разница между Г„ и Г*

примерно того же порядка, что и «ошибки», найденные в «Подтверждении» П. Наура, где использовалась мантисса с 29 разрядами. Характерно, что отклонения, вызываемые усечением входных данных, часто так же велики, как погрешности численного обращения.

Таблица 9

,,29,

,(36,

4 5 6 7 8 10

6480.224 179273.60 4492480.8 1985.829„5 58864.37, „5

6480.046 179246.94 4434355.1 1340.502,„5 27268.01, „5

6480.015. 179207.51 4414530.4 1347.137,„5 54260.62, „5-1

6480.000 179200.08 4410074.9 1334.385,„5 42527.95, „5 -5.07,12

6480 179200 4410000 1334.025,о5 42499.42,„5 3.48,„12

Можно использовать эти матрицы с соответствующими истинными обращениями Я* для проверки алгоритмов 120 и g]r. Алгоритм 120 является программой частичного вращения, т. е. на каждом шаге преобразования в одном столбце отыскивается главный элемент с максимальным абсолютным значением. Алгоритм g]r использует полное вращение, т. е. на каждом шаге главный элемент отыскивается по всей непреобразованной матрице. Кроме того, были сделаны две модификации алгоритма gjr, позволяющие вызывать частичное вращение и отсутствие вращения соответственно. Четыре программы были проверены на машине IBM 7090 с использованием языка SUBALGOL (Stanford - Burroughs ALGOL) и ФОРТРАН. Для машины IBM 7090 было взято k=27, так что результаты сравнивались с Т- . Максимальные ошибки приведены в табл. 10. Для п8 погрешности превышают результаты. В табл. 10 дается также максимальный элемент матрицы j.(27) -сравнения с фактическими ошибками. Матрицы ошибок являются разностями между Р и результатами процедур.





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