AOP_Tom2 (1021737), страница 72
Текст из файла (страница 72)
С другой стороны, ситуации довольно парадоксальная и ее нужно правильно воспринимать, поскольку "плохое" сложение и вычитание всегда выполняется с великолепной точностью! (См. упр. 25,) Одним из следствий возможной ненадежности сложения в формате с плавающей точкой является нарушение закона ассоциативности: (и ч с) Ю и у-' и Ю (с Я и) для многих и, и, ю.
Например: (11111113. 9 — 11111111.) б 7.5111111 = 2.0000000 е 7.о111111 = 9.5111111; 11111113. Ю (- 11111111. Ю 7.5111111) = 11111113. Ю вЂ 111111. = 10 000000. (Все примеры в этом разделе приводятся в восьмиразрядном десятичном'формате с плавающей точкой с представлением порядков посредством прямого указания места расположения десятичной точки.
Напомним, что, как и в разделе 4.2.1, символы 9, б, З, З используются для обозначения операций в формате с плавающей точкой, соответствующих точным операциям +, —, х, /.) В свете возможного невыполнения закона ассоциативности приведенное в начале этой главы замечание госпожи Ла Туш (ьа ТопсЬе), если его отнести к арифметике в формате с плавающей точкой, несет в себе большу'ю долю здравого смысла.
Математические обозначения наподобие "а1+аэ+аэв и "2,", аь" по самому своему сугцеству основаны на предположении об ассоциативности, так что программист должен быть особенно бдителен на сей счет, задаваясь постоянно вопросом, не предполагается ли неявно справедливость закона ассоциативности. А. Аксиоматический подход.
Хотя закон ассоциативности и не выполняется, закон коммутативностн пЯи=иЮн (2) (3) (4) (5) (б) -(и 61 и) = -и 9 -и; и б и = О тогда и только тогда, когда и 6) О = и. Из этих законов можно получить и другие тождества, например (см. упр. 1) и б и = — (и 9 и). (7) Тождества (2) — (6) легко выводятся из алгоритмов, описанных в разделе 4.2.1. Следующее правило менее очевидно: если н<и, то ишш<иЮш. (8) Вместо того чтобы попьпаться доказать это правило, анализируя алгоритм 4.2.1А, вернемся к основным принципам„на которых этот алгоритм базируется. (Доказа- тельство с помощью алгоритма отнюдь не всегда проще и легче формулируется, чем привычное нам математическое доказательство.) Идея состоит в том, что операции в формате с плавающей точкой должны удовлетворять следующим равенствам: о Я и = гоним(и + и), и Ю и = гоппд(и — и), (О) и З и = гоппд(н х и), и З и = гоппсЦн / и), где гоппд(х) означает наиболее близкое приближение в формате с плавающей точкой к х, как определено в алгоритме 4.2.
1 э'. Имеем гошЫ( — х) = -гонов(х), (1О) х < р влечет гоппб(т) < гоппп(у). (11) должен выполняться; последний может служить серьезным концептуальным подспорьем при программировании и анализе программ. Это соображение подсказывает нам, что следует искать наиболее существенные законы, которым удовлетворяют операции ~Э, 8, З и О. Далее, вполне резонным представляется слелующее соображение: программы арифметических операций в формате, с плавающей точкой следует составлять таким образом, чтобы сохранить действие как можно большего числа обычных математических законов.
Если сохраняется действие большего числа аксиом, то легче разрабатывать хорошие программы, к тому же обеспечивая их переносимость с одной модели компьютера на другую. Рассмотрим теперь другие основные законы, которые сохраняются для нормализованных операций с плавающей точкой, описанных в предыдущем разделе. Прежде всего, имеем Из этих фундаментальных соотношений свойства (2)-(8) следуют немедленно. Теперь можно выписать еще несколько тождеств, вытекающих из указанных выше соотношений: иЗе=еЗи, ( — и)Зе= — (иЗе), 1Зе=и; и З е = 0 тогда и только тогда, когда и = 0 или е = 0; ( — и) З е = и З ( — е) = — (и З е); ОЗе=О, иЗ1=и, иЗи=1.
Еглии < е ию > О, тоиЗю < еЗюи иЗю <еЗю; также юЗи > юЗе, если е > и > О. Если и Ф е = и+ е, то (и 9 е) Ю е = и; если и З е = и х е ф О, то (и З е) З е = и. Как видно, несмотря на природную "неточность" операций в формате с плавающей точкой, им присуща значительная регулярность, если все как следует продумать. Все же в приведенном вьппе наборе тождеств, разумеется, бросается в глаза отсутствие нескольких известных законов алгебры; закон ассоциативности для умножения в формате с плавающей точкой выполняется не вполне точно, как будет видно из упр. 3.
Что же касается закона дистрибутивности, связывающего операции З и З, то он может нарушаться, и при этом довольно значительно. Пусть, например, и = 20000.000, е = — 6.0000000 и ю = 6.0000003: тогда (и З е) Я (и З ю) = — 120000.00 Ю 120000 01 = .010000000 и З (е й ю) = 20000.000 З .00000030000000 = .0060000000. Гаким образом, и З (е З ю) ф (и З е) Ю (и З ю). (12) С другой стороны, действительно справедливо 6 З (е З ю) = (6 З е) З (6 З ю), когда 6 есть основание системы счисления, поскольку (13) гоип6(6х) = 6 гоив6(х). (Строго говоря, в тождествах и неравенствах, которые рассматриваются в атом разделе, неявно подразумевается, что потеря значимости или переполнение порядка не возникает.
Функция округления гоппд(х) не определена, когда ~х~ слишком малб или слишком велико, и равенства, подобные (13), имеют место только в случае, когда обе части определены.) Другой впечатляющий пример наруп|ения законов традиционной алгебры при работе с числами в формате с плавающей точкой — невыполнение фундаментального неравенства Коши (те+ . +хз)(у~+.. -ьу)>(ху + .+х у ) Как это может произойти, продемонстрировано в упр.
7, причем в совершенно ординарном случае, когда и = 2, хг = хе = 1. Программисты-новички имеют привычку использовать для программы вычисления среднего квадратичного отклонения для ряда наблюдений формулу из справочника (14) ц часто при выполнении программы "нарываются" на попытку извлечения ква- дратного корпя из отрицательного числа! Значительно лучший метод вычисления среднего значения и стандартного отклонения с учетом свойств операций в формате с плавающей точкой состоит в использовании рекуррентных формул М1 = хы Мь = Мь-, Ю (хь В Мз-1) З)з, (15) 5) =О, Яь = Яь 6 й4(хз ВРМз — з) З(хз В(Мз) (1б) 2 ( 2 (, = 99„9( -19. $Г . В.
Р. 12221 6, тв 1 4 (1962), 419-420.) При использовании этого метода о„никогда не может быть отрицательным и можно избежать множества других серьезных проблем, возникающих прн слишком доверчивом отношении к накоплению сумм, как показано в упр, 1б.
(О методах суммирования, обеспечивающих даже более высокую гарантированную точность, речь идет также в упр. 19,) Даже если алгебраические законы выполняются не вполне строго, можно использовать описанные методы для определения того, насколько точно выполняется тот или ивой закон. Когда Ь' ' < х < Ь', имеем гоип61(х) = х+ р(х), где )р(х)! < зЬ' г. Следовательно, гоип61(х) = х(1 + б(х)), где относительная ошибка ограничена независимо от х: ~б(х)! = ~~( )1 < 1~( )~ < г < 1Ьз — з (18) ц ЬВ з + )ЗР(х)! Ь -з + 154 — з Это неравенство можно использовать в качестве простого инструмента для оценки относительной погрешности вычислений, выполняемых с нормализованными числа- ми в формате с плавающей точкой, поскольку и В и = (и + и) (1+ б(и + и)) и т, д.
В качестве примера типичной процедуры оценки ошибки рассмотрим закон ассоциативности умножения, Как показано в упр. 3, (и З и) З и2, вообще говоря, не равно и З (и З и9), но ситуация в данном случае намного лучше, чем в случае применения закона ассоциативности сложения (1) и закона дистрибутивности (12). На самом деле, имеем (и З и) З и9 = ((ии)(1+ бз)) З и9 = иии9(1+ б1)(1+ бг), и З (и З и2) = и З ((ии9)(1 + бз)) = ииш(1 + бз)(1 + б4) для некоторых бы бг, бз, бз при условии, что не происходит переполнения или исчезновения порядка, причем )б ) < 1~6з з для каждого у. Следовательно, (и З и) З и2 (1+ бз)(1+ бг) и З (и 3 ю) (1+ бзК1+ б4) где 14 <2Ь Г(1 гЬ ) ' (19) В анализе точности очень часто появляется число Ь' г, которому дано специальное наименование — один и)р, что означает одну единицу в последнем разряде дробной части (Пп11 ш 1)эе Еазз Р!асе).
Операции с числами в формате с плавающей точкой дают результат с точностью до половины и1р, и вычисление иии9 посредством двух умножений в формате с плавающей точкой имеет точность около одного и1р (если отбросить члены второго порядка). Следовательно, закон ассоциативности для умножения справедлив вплоть до двух и!р относительной ошибки. Таким образом, показано, что (иЗе)Зю приблизительно равно иЗ(еЗю), за исключением тех случаев, когда происходит исчезновение или переполнение порядка.
Этв интуитивная идея "приблизительного равенства" заслуживает более подробного изучения; можно ли дать более точную формулировку этого утверждения? Программист, использующий арифметические операции в формате с плавающей точкой, почти никогда не испытывает желания проверить, не выполняется ли точное равенство двух вычисленных значений, так как равенство является крайне маловероятным. Например, если используется рекуррентное соотношение х„+1 — — у(х„), о котором известно из литературы, что х„стремится к некоторому пределу при и -+ ос, то, скорее всего, будет ошибкой продолжать вычислении, пока для некоторого и не выполннтся равенство хв Ы вЂ” — х„, так как последовательность х„может ввиду округления промежуточных результатов оказаться периодической с большим периодом. Разумно продолжать вычисления лишь до тех пор, пока для некоторого подходящим образом выбранного б не станет справедливым неравенство !хь ы — х„~ < д; но так как порядок величины х„заранее неизвестен„еще лучше— дождаться выполнения неравенства (20) (хе+1 — хв( ( с(хп(, е — и > с п1ах(Ь'" т, Ь'" т); (21) (е — и~ < еп1ах(Ь'" ~,Ь'" т); (22) и — е ь вшах(Ь~" 4,Ьг" т); (23) (е — и! (аш!п(Ь'" ',Ь*" ').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
