Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 75
Текст из файла (страница 75)
Правило округления гласит: 1ц9 в (в+ в)~ < Ювевт )и(Э в (и — в)~ < бвви, )и Э в — (и х в)~ < Ь„в„~и О в — (и / в)~ < Ь„р„,. Эти неравенства применимы как к нормализованным, так и к ненормализованным величинам; основное различие между двумя типами анализа ошибок состоит в том, что порядок результата каждой из операций (соотношения (48)-(50)) опречеляется по-другому. Отношения -с,, >- и ж, определенные выше в настоящем разделе, сохраняют смысл и для ненормализованных чиатал. В качестве примера использования зтих отношений докажем приближенный закон ассоциативности для сложения ненорма- лизованных величин по аналогии с (39): (цЕв)Ешжиф(ваш) (е) (52) для подходящим образом выбранного с.
Имеем )(и ш в) 9 ш — (и + в + ш) ) < ) (ц ш в) 9 ш - ((н ш в) + ш) ) + )и Ю в — (и+ в)) < 4[вщюэв+ Ьшзи < 25(мыми)вв Аналогичная формула справедлива н для )в б (в Е ш) — (ц + в + ш) !. Но поскольку е~ве~1в = шах(е„,е„,е )+ (О, 1 или 2), то б<„в,овм < Ьзб„е „щ ).
Следовательно, (52) верно при е > Ьз в + 6 г. С точки зрения закона ассоциативности сложение ненормализованных величин яе вызывает столько ошибок, как сложение нормали- зованных. Следует подчеркнуть, что арифметика ненормализованных величин ни в коей мере не может служить панацеей; иногда указываемая при таком способе выпол- вени» вычислений точность болыпе действительной (напрнмер, сложение большого числа малых приблизительно одинаковых по абсолютной величине чисел или нахо- ждение х" для болыпого а). Существует еще больше примеров, когда в такой ариф- метике дается невысокая точность, в то время как при выполнении операций нвд нормализованными величинами в действительности получались бы гораздо более точные результаты.
Существует важная причина, цо которой ни один прямой метод анализа ошибок "по одной операции" не может считаться удовлетворительным, а именно: операнды обычно ие являются независимыми. Это означает, что ошибки имеют тенденцию к компенсации или усилению одна другой необычным образом. Предположим, например, что х приблизительно равно 1/2 и что у этого значения есть приближение у = х+й с абсолютной ошибкой э. Чтобы вычислить произведение х(1 — х), можно найти у(1 — у); если х = -' + с, то получим у(1 — у) = х(1 — х)— 2сд — бз.
Таким образом, абсолютная ошибка существенно уменьшилась — перед ней появился коэффициент 2с + б! Это всего лишь один из случаев, когда умножение приближенных значений операндов, не являющихся независимыми, может привести к довапьно точному результату. Более очевидный пример — вычисление х Ох, которое может быть выполнено с абсолютной точностью независимо от того, насколько ошибочным было приближение х, которое испачьзуетсн в качестве операнда, Дополнительная информация, которую предоставляет арифметика ненормализованных величии, часто может быть более важна, чем информация, потерянная при выполнении обширных вычислений в таком формате, но, как обычно, необходимо соблюдать осторожность при ее использовании.
Примеры правильного использования арифметики ненормализованных величин проанализированы Р. Л. Эшенхерстом (К. 1.. АэЬепЬпгэг) и Н. Метрополнсом (Х. Меггоройэ) в сборнике Согпрпгегэ п Согпрпбп8, АММ, 81апйЬс Мепюпа1 Рарегэ 10 (РеЬгпагу, 1965), 47-59, Н. Метрополисом в журнале Хишег. МагЛ. 7 (1965), 104 — 112, и Р. Л. Эшенхерстом в сборнике Еггаг 1п 01811а( Сошр~ГаНоп 2, ебйеб Ьу 1.
В. Ва11 ( чеэг гоНс: '1э11еу, 1965), 3 — 37. Надлежащие методы вычисления стандартных математических функций с представлением как входных, так и выходных данных в ненормализованной форме были описаны Р. Л, Эшенхерстом в,(АСМ 11 (1964), 168-187. Расширение ненормализованной арифметики, которое предусматривает сохранение информации о том. что определенные операнды известны точно, проанализировано Н. Метрополисом в 1ЕЕЕ Тгапк С-22 (1973), 573 — 576. С. Арифметика интервалов. Другой подход к проблеме оценки погрешности связан с так называемой арифметикой интервалов или диапазонов, которая предусматривает учет в процессе выполнения вычислений строгих границ--верхней и нижней — для каждого числа.
Так, например, если известно, что ип < и < и~ и пе < э < иы в записи в форме интервалов это будет иметь вид и = ]пэ .. и1], и = (ээ .. сз]. Сумма и З э есть (пэ тр пэ .. п1 А э1], где ~у означает нижнюю сумму в формате с плавающей точкой, т. е. наибольшее представимое в данном формате число, меньшее или равное действительному значению суммы, а й определяется аналогично (см.
упр. 4,2.1-13). Далее, и ~Э и = ]пп '6' щ ..щ Й ео]; если иэ и эо положительны, то и З э = ]по 1щ эо, п1 гь в1], и З е = ]по ~у э, п1 Ь эо]. Например, число Авогадро и постоянная Планка в обозначениях арифметики интервалов будут иметь такой вид: Х = ((24, +.60221331),. (24, +.60221403)], Ь = (( — 26, +.66260715) ..
( — 26, +.66260795)1. Сумма и произведение этих величин будут выражены следующим образом: Аг Ь Ь = ((24, +.60221331) .. (24, +.60221404)1, Аг З Ь = ((-2, +.39903084) .. (-2, +.39903181)1. Если попытаться выполнить деление на (во .. в!), причем цв < 0 < в!, весьма вероятно возникновение деления на нуль. Поскольку самой философией арифметики интервалов предусматривается строгая оценка ошибки вычислений, в этом случае обязательно должно формироваться сообщение об ошибке деления на нуль. Однако переполнение и потеря значимости не рассматриваются как фатальные ошибки, если поддерживаются специальные соглашения, которые более подробно рассматриваются в упр.
24. Вычисления с использованием арифметики интервалов лишь вдвое больше по объему, чем те же вычисления в обычном формате. В то же время данный метод обеспечивает надежную оценку ошибки. Учитывая сложность математического анализа ошибок, такую цену можно признать вполне приемлемой. Поскольку в процессе вычислений промежуточные значения часто зависят одно от другого, полученные с помощью арифметики интервалов оценки результатов часто слишком пессимистичны; если вы собираетесь использовать ее, измените итерационные численные методы решения привычных задач.
Хотя перспективы эффективного использования арифметики интервалов выглядят довольно хорошо, нужно приложить определенные усилия, направленные иа расширение ее функциональных возможностей и, насколько зто возможно, обеспечение "дружественности" по отношению к пользователю. Ю. История н библиография. В классическом трактате о методах вычислений в десятичной системе счисления Ъерзпэ гГАг!1Лшбг!9ие (РаНэ: Со1!и, 1894), принадлежащем перу Жии~я Таннерн (Лц!ез Таппегу), утверждается, что положительные числа должны округляться в сторону большего, если первый отбрасываемый разряд равен или больше 5.
Поскольку ровно половина десятичных цифр равна нли больше 5, это, как ему казалось, будет приводить к округлению в большую сторону в среднем ровно в половине случаев, так что в результате ошибки (округления,— Прим. ред.) компенсируются. Идея округлять до четного в неоднозначных случаях впервые, кажется, была упомянута Джеймсом Б. Скврборо (Зашев В. БсагЬогоцй!~) в первом издании его пионерской книги 7тцшег!са) МагЬетаг!са/ Ала!ув!э (Ва1г!шоге: ЛоЬпэ НорЫпэ Ргеш, 1930), 2; во втором издании (1950 г.) он развил ранние примечания по этому поводу, утверждая, что "для любого думающего человека должно быть очевидным, что, когда отбрасывается 5, предыдущий разряд дачжен бытЬ увеличен на 1 только в половцне случаев"; как средство достижения этого он рекомендовал округлять до четного.
Впервые анализ арифметических операций в формате с плавающей точкой был выполнен Ф. Л. Бауэром (Г..1,. Ваиег) и К. Замельсоном (К. Ваше!эоп), Яе!гасйг!В 85г апйев.апс!1е МагЬ. цпг! РЬувй 4 (1953), 312-316. Следующая публикация появилась лишь пятью годами позже; 3. Ч'. Сагг Ш, САСМ 2, 5 (Мау, 1959), 10-15. (См. также Р. С. Г!эсЬег, Ргос. АСМ г!ас. Меег!пй 13 (1958), Рарег 39.) В книге Л, Н. ТИЫпвоп, Яоиле3пй Еггогз ш А!8еЬгаус Ргосеэмл (Епй!ежооб С!!(7э: Ргепйсе-На11, 1963) показано, как применять методы анализа ошибок отдельных арифметических операций к анализу ошибок в задачах с большим числом вычислений (см. также его монографию ТЬе А!8еЬгшс Е(йепга!ие РгоЫет (ОхГогп: С!агепбоп Ргеээ, 1965)).
Обзор других ранних работ, касающихся точности вычислений в формате с плавающей точкой, приведен в двух важных статьях, которые можно настоятельно рекомендовать для дальнейшей проработки: ЪЧ. М. КаЬап, Ргос. 1Г!Р Сопйгеш (1971), 2, 12 14-1239, и Н. Р. Вгепс, 1ЕЕЕ Ьзов. С-22 (1973), 601-607. В обеих статьях содержатся весьма полезная теоретическая часть и демонстрация ее приложения на практике. Ввезенные в этом разделе отношения м,, ь., ж имеют аналогию с идеями, сформу лированным в работе А. Уап %!)пйаагбеп, В1Т 6 (1966), 66-81. Приведенные выше теоремы А и В навеяны некоторыми работами в этой области Оле Меллера (О!е Мойег), В1Т 5 (1965), 37-50, 251-255.
Теорема С взята из работы Т. 1. ВеИсег, Уишег. Май. 18 (1971), 224-242. Расширение н уточнение всех трех теорем опубликовано в работе 8. Рйппашпъы, В1Т 14 (1974), 167 — 202. У. М. Кахан (%. М. КаЬап) сформулировал теорему 1) в неопубликованных заметках: полное ее доказательство и комментарии приведены в работе 1. Г. Не!яег, О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
