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

подтверждение к алгоритму 122

П. Наур (Naur Р. «САСМ», 1964, № 3)

В алгоритм 122 необходимо внести следующие исправления...* После этих исправлений алгоритм работал удовлетворительно

в системе GIER ALGOL. Он был опробован в качестве теста с матри*

цей Хансена, имеющей элементы

HBH[j,i]=HBH[i,j]=n+l-j, где j>i

(ср. «Подтверждение к алгоритму 85», «САСМ», 1963, № 8).

Для контроля !было сделано обратное преобразование полученной матрицы с с использованием вычисленной матрицы и. Определялось наибольшее отклонение любого элемента от его исходного значения.

Для сравнения можно пользоваться цифрами, полученными после применения алгоритмов, данных в работе Вилкиясона («Numerische Mathematik», 1962, 4, с. 354-376). В алгоритмах Вилкинсона для при-, ведения к трехдиагональной форме используется метод Хаусхольдера. Следует заметить, что отклонения, приведенные в . нижеследующей табл. И для метода Хаусхольдера, относятся к окончательным результатам получения собственных значений и векторов, а не только к ре еультатам приведения к трехдиагональной форме, и включают, следовательно, погрешности гораздо более длинной цепочки вычислений, чем той, которая дается в алгоритме 122. Однако в обоих случаях время относится только к процессу приведения к трехдиагональной форме.

Таблица 11

Характеристики алгоритма

«=5

п=15

Максимальное отклонение

для алгоритма 122

1.4,0-7

7.0,0-7

2.4,0-6

для алгоритма Хаусхольдера Время вычисления в системе GIER ALGOL, с

1.4,0-7

1.3.0-6

для алгоритма 122

для алгоритма Хаусхольдера

Эти цифры ясно показывают превосходство метода Хаусхольдера. А так как метод Хаусхольдера в форме, данной Вилкинсоном, использует еще и гораздо меньше ячеек памяти для переменных, то алгО ритм 122 не может быть рекомендован.

Свидетельство к алгоритму 1236 [S15]

Алгоритм 1236 не публикуется здесь, потому что соответствующие алгоритмы 123 («САСМ», 1962, № 9) и 123а считаются устаревшими по причинам, указанным в нижеследующих «Замечаниях к алгоритмам 123, 180, 181, 209, 226, 272 и 304» И. Хилла и С. Джойса. Интеграл вероятности можно вычислять с помощью более совершенных алгоритмов 209а и 304 («САСМ», 1967, № 6).

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



Замечания к алгоритмам 123, 180, 181, 209, 226, 272 и 304

И. Хилл, С. Джойс (Hill I. D., Joyce S. А. «САСМ», 1967, № 6)

Эти алгоритмы были проверены .на машине ICT Atlas с использованием транслятора Atlas ALGOL. Были сделаны следующие изменения и получены следующие результаты.

Алгоритм 123*

1. Было вставлено value х;

2. flfcs(7)10-10 было заменено на V-T-V.

Оба эти улучшения были предложены в «Подтверждении к алгоритму 123» Г. Тачера (Thacher Н. С. Jr. «САСМ», 1963, № 6).

3. Метки 1 п 2 были заменены метками L1 и L2; .соответственно были исправлены операторы перехода.

4. Константа была удлинена до 1.12837916710.

5. В качестве первого оператора процедуры был добавлен оператор х:=0.70710б781187Хх, так чтобы вместо интеграла вероятности получался интеграл ошибок.

Во .всех проверенных точках результаты имели точность 10 десятичных цифр, кроме случая х=1.0, где точность ограничивалась только двумя десятичными цифрами, как это уже было отмечено Д. Ибет-соном в его «Замечании к алгоритму 123» (Ibbetson D. «САСМ», 1963, № 10). Представляется, что не существует простого способа преодоления этого затруднения [см. «Замечание .к алгоритму 123» С. Бар-тона и Дж. Вагнера (Barton S. Р., Wagner J. F. «САСМ», 1964, № 3)], и вряд ли стоит искать такой способ, поскольку этот алгоритм работает медленнее, чем алгоритм 304, не давая при этом большей точности.

Алгоритм 180**

1. Оператор Т:=-0.56418958/x/exp(и) был заменен оператором Т:--0.564189583548Xexp(-и)/х. Последний выполняется быстрее и обладает тем преимуществом, что при очень больших значениях г не происходит переполнения, а получается машинный нуль.

2. Был добавлен такой же оператор, как и в п. 5 предыдущих замечаний к алгоритму 123.

3. for т:=т+1 было заменено на for т:-т + 2, так как т + 1 - опечатка, приводящая к неверным результатам.

Максимальная .погрешность, замеченная в результатах, была равна двум единицам .в 11-й десятичной цифре.

Алгоритм 181***

1. Была сделана замена такая же, как и в п. 1 замечаний к алгоритму 180 (за исключением знака минус).

2. Тот же, что и п. 2 замечаний к алгоритму 180.

* Первая и третья модификации были уже внесены в алгоритм 123а при его составлении авторами выпуска «Алгоритмы (101-150)» (Прим. ред.)

** Первая и третья поправки были уже внесены в алгоритм 180а при его составлении. (Прим. ред.)

*** Первая и третья поправки были уже внесены в алгоритм 181а при его составлении. (Прим. ред.)



3. т было описано как real, вместо integer, что является альтернативой к поправке, предложенной в «Подтверждении к алгоритму 181» И. Клаузена и Л. Хансона (Clausen I., Hansson L. «САСМ», 1964, № 12).

Точность результатов этого алгоритма составила для х8 девять значащих цифр, но для д;;=10 и х=20 - только восемь значащих цифр.

Алгоритм 209

Не было сделано никаких изменений. Результаты были правильными в семи десятичных цифрах.

Алгоритм 226

•m/(480Xsqrt(2X3.14159265)) было заменено на тХО.000831129750836.

2. fori:=l step 1 until 2Xn do было заменено на m:=2Xn; for i:=l step 1 until m do •

3. -(iXb/n)f2/8 было заменено на -(ixb/п)f2x0.125.

4. if i=2Xn-1 было заменено на if i-m-1.

5. b/(6XnXsqrt(2X3.14159265)) было заменено на"

b/(l 5.0397696478 Xn). Контрольные решения для m=7 и m=ll дали результаты, указанные в табл. 12.

Таблица 12

Число правильных значащих ввФр

Число правильных десятичных цифр

m=ll

-0.5

-1.0

-1.5

-2.0

-2.5

-3.0

-4.0

-6.0

-8.0

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

Алгоритм 272

Константа 0.99999999 была удлинена до 0.9999999999. В большинстве проверенных точек точность результатов была восемь десятичных цифр, но при x=0.8 точность была только пять десятичных цифр.

Алгоритм 304

Не было сделано никаких изменений. В табл. 13 приведены погрешности в 11-й значащей цифре, обнаруженные в результатах решения.





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