Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 72
Текст из файла (страница 72)
Если точное вещественное число х в компьютере представляется посредством приближения х = т(1 + е), то величина г = (х — х)/х называется относительной ошибкой приближения. Грубо говоря, при выполнении вычислений в формате с плавающей точкой операции умножения и деления пе слишком увеличивают относительную ошибку, но вычитание почти равных величин (и сложение и 9 е, где н почти равно -е) может увеличить ее значительно. Итак, общее эмпирическое правило таково: существенной потери точности можно ожидать от сложения и вычитания указанного вида, но не от умножения и деления.
С другой стороны, ситуация довольно парадоксальная и ее нужно правильно воспринимать„поскольку "плохое" сложение и вычитание всегда выполняется с великолепной точностью! (См. упр. 25.) Одним из следствий возможной ненадежности сложения в формате с плавающей точкой является нарушение закона ассоциативности: (и9е) 9 ну Ф и 9(е9Ф) для многих м,е,ю. Например: (11111113. 9 -11111111.) 9 7.5111111 = 2.0000000 9 7.5111111 = 0.5111111; 11111Г13 9 (-1111Ш1.
9 7.5111111) и 11111113. 9 -11111103. ~ 10.000000. (Все примеры в этом разделе приводятся в восьмиразрядном десятичном'формате с плавающей точкой с представлением порядков посредством прямого указания места расположения десятичной точки. Напомним, что, как и в разделе 4.2,1, символы 9, 9, З, З используются для обозначения операций в формате с плавающей точкой, соответствующих точным операциям +, —, х, /.) В свете возможного невыполнения законе ассоциативности приведенное в начале этой главы замечание госпожи Ла Туш (1 а ТопсЬе), если его отнести и арифметике в формате с плавающей точкой, несет в себе большую долю здравого смысла.
Х1атематические обозначения наподобие "а1 + от+ аз" и "~ ь, аь" по самому своему существу основаны иа предположении об ассоциативности, так что программист должен быть особенно бдителен иа сей счет, задаваясь постоянно вопросом, ие предполагается ли неявно справедливость закона ассоциативности. А. Аксиоматический подход. Хотя заков ассоциативности и ие выполняется, закон коммугативиости мшо=юшя (2) (3) (4) (б) (6) иЯо=иЮ-о; -(иЮо) = -пЬ-с; и 9 с = 0 тогда и только тогда„когда и~О = и.
Из этих законов можно получить и другие тождества, например (см. упр, 1) и Ес = -(е Е и). (у) Тождества (2)-(6) легко вьпюдятся из алгоритмов, описанных в разливе 4.2.1. Следующее правило менее очевидно: если и < в, то иЮю < гфи>. (8) Вместо того чтобы попытаться доказать это правило, анализируя алгоритм 4,2.1А, вернемся к основным принципам, на которых этот алгоритм базируется. (Доказа- тельство с помощью алгоритма отнюдь ие всегда проще и легче формулируется, чем привычное иам математическое доказательство.) Идея состоит в том, что операции в формате с плавающей точкой должны удовлетворять следующим равенствам: и Ю о = гоопд(п + и), и сЭ о = гоипд(и — о), (9) и З е = гоппд(и х о), и З е = гоопд(п / о), где гоппд(х) означает наиболее близкое приближение в формате с плававшей точкой к х, как определено в алгоритме 4.2.11ч.
Имеем гоипд(-х) = -гоопд(х), (10) х < у влечет гоопд(к) < гоопд(д). (11) должен выполняться; последний может служить серьезным концептуальным подспорьем при программировании и анализе программ. Это соображение подсказывает иам, что следует искать наиболее существенные законы, которым удовлетворяют операции 6~, В, З и З.
Далее, вполне резонным представляется следующее соображение: программы арифметических операций в формате с плавающей точкой следует составлять таким образом, чтобы сохранить действие как можно бдльшего числа обычных математических законов. Если сохраняется действие большего числа аксиом, то легче разрабатывать хорошие программы, к тому же обеспечивая их переносимость с одной модели компьютера на другую, Рассмотрим теперь другие основные законы, которые сохраняются для нормализованных операций с плавающей точкой, описанных в предыдущем разделе. Прежде всего, имеем Из этих фуцдаментальных соотношений свойства (2)-(8) следуют немедленио.
Теперь можно выписать еще несколько тождеств, вытекающих из указанных выше соотношений: иЗе =еЗи, (-и) Зе = -(иЗе), 1З» =е; иЗ» = 0 тогда и только тогда, когда и = О или е =0; (-) =. (-.)=-(.З ); ОЗе=О, иЗ1=и, иЗи=1. Если и < е и в > О, то и З ю < е З ю и и З»е < е З ю; также ю З и > ю З е, если е > и > О. Если и З е = и+ е, то (и Ю е) В е = и; если и З е = и х» 1~ О, то (и З е) З е = и. Как видно, несмотря на природную "неточность" операций в формате с плавающей точкой, им присуща значительиая регулярность, если все как следует продумать.
Все же в приведенном выше наборе тождеств, разумеется, бросается в глаза отсутствие нескольких известных законов алгебры; закон ассоциативности для умножения в формате с плавающей точкой выполняется не вполне точно, квк будет видно из упр. 3. Что же касается закона дистрибутивиости, связывающего операции З и Ф, то он может нарушаться, и при этом довольно значительно. Пусть, например, и = 20000.000, е = -6.0000000 и ю = 6.0000003; тогда (и З е) В (и З ю) = -120000.00 В 120000,01 = .010000000 и З (е ~Э ю) = 20000.000 З .00000030000000 = .0060000000. Таким образом, иЗ(ерш) ~ (и Зе) Е(е.з ~с).
(12) С другой стороны, действителько справедливо Ь З (е Ф и) = (Ь З е) 6Э (Ь З ю), когда Ь есть основание системы счисления, поскольку гопак(Ьх) = Ь гоипс)(х). (Строго говоря, в тождествах и неравенствах, которые рассматриваются в этом разделе, неявно подразумевается, что потеря значимости или переполнение порядка не возникает. Функция округления гоипй(х) не определеиа, когда ~х) слишком мвлб или слишком велико, и равенства, подобкые (13), имеют место только в случае, когда обе части определены.) Другой впечатляющий пример нарушения законов традиционной алгебры при работе с числами в формате с плавающей точкой — невыполнение фундаментального неравенства Коши (х2+...+Х~~)(У2+...+Р2)>(ж у +,, +х д )2 Как это может произойти, продемонстрировано в упр.
7, причем в совершенно ординарном случае, когда и = 2, х~ = эт = 1. Программисты-новички имеют привычку использовать для программы вычисления средиего квадратичного отклонения для ряда наблюдений формулу из справочника (14) ц часто при выполнении программы "нарываются" на попытку извлечения квадратного корня из отрицательного числа! Значительно лучший метод вычисления среднего значения и стандартного отклонения с учетом свойств операций в формате с плавающей точкой состоит в использовании рекуррентных формул М» — -хы М»=М»»З(х»ЭМ»»)ЗЬ, (1б) Я» = О, 5» = 5»» 9 (х» Э М»») З (х» б М») (10) ц,2<а~, ж -„~3.7ь — 'ц. ~с .в.Р.аь» т ) 4(1а~, 419-420,) При использовании этого метода Я„никогда не может быть отрицательным н можно избежать множества других серьезных проблем, возникающих при слишком доверчивом отношении к накоплению сумм, как показано в упр.
16. (О методах суммирования, обеспечиваю»цих даже более высокую гарантированную точность, речь идет также в упр. 19.) Дюкс если алгебраические законы выполняются не вполне строго, можно использовать описанные методы для определения того, насколько точно выполняется тот или иной закон. Когда Ь' ' < х < Ь', имеем гоппб(х) = к+ р(х), где )р(х)( < 1Ь' ". Следовательно, гоипб(х) = х(1+ б(х)), (17) где относительная ошибка ограничена независимо от»п )б(х)) = — « ~ < 1Ь' г.
(18) — Ь -» + )р(я)/ — Ье-» + 1Ь вЂ” в Это неравенство мвкно использовать в качестве простого инструмента для оценки относительной погрешности вычислений, выполняемых с нормализованными числами в формате с плавающей точкой, поскольку и З г = (и + и) (1 + б(и + е)) и т. д. В качестве примера типичной процедуры оценки ошибки рассмотрим закон ассоциативности умножения. Как показано в упр.
3, (и З е) З ю, вообще говоря, не равно и З (с З»с), но ситуация в данном случае намного лучше, чем в случае применения закона ассоциативности сложения (1) и закона дистрибутивности (12). На самом деле, имеем (иЗе) Зю = ((ис)(1+б»)) З»с = исю(1+б»)(1+бз) и З (е З ю) = к З ((»чв) (1 + бз)) = всю(1 + бз) (1 + б») для некоторых бм бт, 'бз, б» при условии, что не происходит переполнения или исчезновения порядка, причем ~б».) < -'Ь' ~ для каждого у.
Следовательно, (и Зе) Зи~ (1+б»)(1+бз) и З (и З ю) (1+ бз)(1+ б») где )б) < 2Ь' г/(1- 1Ь' г), (19) В анализе точности очень часто появляется число Ь' ", которому дано специальное наименование — один и)р, что означает одну единицу в последнем разряде дробной части ((1п11 ш »1»е Еав» Р1асе). Операции с числами в формате с плавающей точкой дают результат с точностью до половины п1р, и вычисление иею посредством двух умножекий в формате с плавающей точкой имеет точность около одного п1р (если отбросить члены второго порядка). Следовательно, закон ассоциативности для умножения справедлив вплоть до двух ц1р относительной ошибки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
