Главная Промышленная автоматика. с этими изменениями обе процедуры легко прошли через транслятор. Для сравнения каждая из них была проверена следующим образом. С довольно большим заданным значением eps процедура была применена для обращения сегмента матрицы Гильберта. После аварийного выхода к метке signal значение eps было разделено на 10, и сделано новое обращение к процедуре. Таким способом получили оценку наибольшего допустимого eps. После получения обращенной матрицы был вычислен тот ее элемент, который имел максимальную погрешность, найденную сравнением с точной матрицей, обращенной с помощью процедуры INVHILBERT (алгоритм 50). Относительная погрешность была получена делением на наибольший элемент точной обращенной матрицы. Этот процесс выполнен для сегментов матрицы Гильберта от 2-го до 15-го порядков. Для порядков свыше 9-го погрешности стали больше результатов. Для порядков ниже 9-го получены результаты, приведенные в табл. 5 (алгоритм 120). Таблица 5
Такие же результаты и отношение ошибок двух процедур получены для 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
Однако следует заметить, что вследствие автоматической сегментации программы по дорожкам барабана в системе GIER ALGOL время выполнения может кое-где отличаться от программы, в которой процедура используется по-другому. Вышеприведенные значения времени фактически относятся не к одной и той же программе. Замечание к подтверждению процедур обращения матриц К. Молер (Moler С. «САСМ», 1963, № 7) В предыдущем «Подтверждении» П. Наура (Naur Р. «САСМ», 1963, № 1) две процедуры обращения матриц были проверены обращением автоматически получаемых матриц Гильберта и сравнением результатов с теоретически обращенными матрицами. Как было показано в работе Дж. Вилкинсона [51], такая проверка является неудовлетворительной, вводящей в заблуждение. Здесь дополнительно рассматриваются возникающие трудности. Матрицы Гильберта даже низких порядков настолько плохо обусловлены, что малые погрешности, возникающие в результате усечения или округления их элементов при выравнивании машинного слова, вызывают большие изменения в соответствующих им обращенных матрицах. Поэтому результаты процедуры обращения должны сравниваться с истинными результатами обращения этих модифицированных исходных матриц, а не с результатами обращения неизмененных матриц Гильберта. Для большей определенности пусть Я„ обозначает матрицу пХп Гильберта, определяемую с помощью равенств (Я„)г,з=1/(г+/-1), где /,/=1, .... п. Пусть Я означает матрицу, составленную из нормализованных чисел с плавающей запятой и с мантиссой из b двоичных разрядов, получающейся усечением двоичного представления элементов Я„, т. е. где [х] - наибольшее целое, не превышающее х, а k - это целое, для которого 7г2(п)1,/<С Через Г„ и Т" обозначим истинные результаты обращения матриц Я„ и Н соответственно. В табл. 9 даются максимальные элементы матриц Т„ и Т" для нескольких значений п я Ь. Следует отметить, что разница между Г„ и Г* примерно того же порядка, что и «ошибки», найденные в «Подтверждении» П. Наура, где использовалась мантисса с 29 разрядами. Характерно, что отклонения, вызываемые усечением входных данных, часто так же велики, как погрешности численного обращения. Таблица 9
Можно использовать эти матрицы с соответствующими истинными обращениями Я* для проверки алгоритмов 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.0016 |