AOP_Tom2 (1021737), страница 73
Текст из файла (страница 73)
(24) и .ч е (с) тогда и только тогда, когда и е (е) иые (е) вше (е) тогда и только тогда, когда тогда и только тогда, когда тогда и только тогда, когда Эти определения подходят как для нормализованных чисел, так и для ненормализованных. Согласно этим определениям для любой данной пары значений и и е может выполняться в точности одно из соотношений и и Ч е (определенно меньше), и е (приблизительно равно) или и м е (определенно болыпе). Отношение и а е несколько более сильное, чем и е, и его можно читать так: "и, по существу, где е — число, которое должно быть выбрано заранее.
Соотношение (20) позволяет другим способом выразить то, что числа х„+1 и х„приблизительно равны: н наше обсуждение показывает, что прн анализе вычислений над числами с плавающей точкой отношение "приблизительного равенства" бьшо бы более полезно, чем традиционное отношение равенства, если только первое отношение удастся определить надлежащим образом. Другими словами, тот факт, что строгое равенство величин в формате с плавающей точкой играет очень небольшую роль, приводит к необходимости ввода новой операции сравнения величин с плавающей точкой, назначение которой — упростить оценку относительных значений двух таких величин. Представляются подходящими следующие определения для чисел с плавающей точкой и = (е„, у„) и е = (е„, ~„) по основанию Ь с избытком в: и то же самое неравенство выполняется, если поменять местами (и З в) З ш и и З (в З иь).
Следовательно, в соответствии с (34) справедливо соотношение (иЗв)Зю иЗ(вЗиь) (с) (30) для с > 2са/(1 — т се) . Например, при Ь = 10 и р = 8 можно взять с = 0.00000021. Соотношения ч, —, ~- и м полезны для численных алгоритмов, и поэтому разумно включить в состав системного программного обеспечения компьютера программы для сравнения чисел с плавающей точкой наряду с программами для вьнюлнения над ними арифметических действий. Теперь вновь перейдем к вопросу о нахождении точных соотношений, которым удовлетворяют операции над числами с плавающей точкой.
Интересно отметить, что сложение и вычитание таких величии не полностью выпадают из поля зрения аксиоматики, так как они удовлетворяют нетривиальным тождествам, сформулированным в следующих теоремах. Теорема А. Пусть и я в — нормализованные числа с плавающей точкой. Тогда ((и Е в) Е и) + ((и Е в) Е ((и Е в) В и) ) = и вь в (40) при условия, что не происходит переполнения нли исчезновения порядка.
и =(ивьв)ь~в в' = (ивов) Ви; (41) ив = (и йь в) ьв в', в" = (и вь в) ьв и'. Интуитивно ясно, что и' и и" должны быть приближениями к и, а в' и в" — приближениями к в. Теорема А утверждает, что и 9 в = и' + в ' = и" + Ь . Этп более сильное утверждение, нежели тождество ивьв=и Вв =ив Яв', являющееся следствием округления (42). (42) (43) Доказагпельство. Будем говорить, что ь является остагььочиьоьь членам х (по модулю Ь'), еьли г = х (по модулю Ь'). /1) < 16'. (44) Таким образом, х — гоппг)(х) всегда равно остаточному члену х.
Доказательство теоремы А в значительной мере основывается на гледуюгцих простых умозаключениях, доказанных в упр. 11. Лемма Т. Есльг 1 есть остаточный член числа в формате с плавающей точкой х, тохсьь =х — а $ Пусть ю = и йь в. Теорема А становится тривиальной, когда вь = О. Умножив все переменные на подходящие степени Ь, можно, не теряя общности, предположить, что еи = р.
Тогда и+ в = иь + гь где г есть остаточный член и + в (по модулю 1). Далее, и' = гоипй(ю — в) = гоипг1(и — г) = и — г — г, где 1 есть остаточный член и — г (по модулю 6') и е = е„— р. Это довольно громоздкое тождество можно переписать в следующем более простом виде. Положим Если е < О, то С = и — т ги — в (по модулю Ь'). Следовательно, С есть остаточный член — е и еп = гоипб(и — и') = гоппд(в+ С) = в+ С, что доказывает (40). Если е > О, то ~и — т~ > Ь" — з, а поскольку (т( < -', имеем )и( > Ьг — 1. Из этого следует, что и есть целое число, твк что т — -остаточный член в (по модулю 1). Если и' = и, то С = — т является остаточным членом — е. В противном случае соотношение гоцпп(и — т) ф и влечет за собой ~и( = Ьг — 1, (т( = -', ~и'~ = Ьг, С = т; опять же, С вЂ” остаточный член — е.
1 Теорема А выявляет некое свойство регулярности операции сложения в формате с плавающей точкой, но она не представляется уж очень полезным результатом. Следующая теорема гораздо более существенна. Теорема В. В предположениях теоремы А п прн условие (41) справедливо тождество и + е = (и 9 е) + Ци О и ) 9 (в б е )) . (45) Даказапзельстпео, Рассматривая каждый нз случаев, возникших при доказательстве теоремы А, мы неизменно обнаруживаем, что и В и' = и — и', е В е" = е — вп и (а — и') Ж (в — вп) = (и — и') + (е — е"). Значит, (45) следует из теоремы А, Если учесть принятые в предыдущем доказательстве обозначении, эти соотношения окажутсн эквивалентными следующим: гоппс1(С+ т) = С+ т, гоипй(С) = С, гоипб(т) = т.
(46) В упр. 12 рассматривается теорема дли особого случая, когда ~е„— е„) > р. Иначе и+в имеет не более 2р значащих разрядов, и можно легко показать, что гоцпб(т) = т. Если теперь е > О, доказательство теоремы А показывает, что С = — т или С = т = х —. 1 Если е < О, имеем С + т = и и С = — е (по модулю Ь'); этого достаточно для доказательства того, что С + т и С при округлении не изменяются (округлнютсн до "самих себя" ), обеспечивая выполнение неравенств е„> е и е„> е.
Но либо е„< О, либо е„< О будут противоречить нашей гипотезе о том, что (е„— е„) < р, поскольку ее = р. 1 Теорема В дает в яаном виде формулу для получения разности между и + е и и Ю е в терминах величии, которые можно вычислить, непосредственно используя пвть арифметических операций в формате с плавающей точкой.
Если основание системы счисления Ь равно 2 или 3, можно улучшить этот результат и получить точные значения корректирующих членов, используя всего две арифметические операции в формате с плавающей точкой и одно сравнение абсолютных величин в формате с фиксированной точкой. Теорема С. Есле Ь < 3 и (и( > (е(, то (47) и + в = (и В в) + (и 9 (и Я е)) е в. Доказательства. Следуя соглашеиинм, принятым при доказательстве предыдущих теорем, желательно показать, что е В в' = т. Достаточно показать, что в' = ги — и, поскольку из (46) затем последует е В в' = гоппд(в — в') = гоцпб(и + в — ю) = гоппд(т) = т.
Фактически нужно доказать (47) для любых Ь < 3 и е„> е„. Если е„> р, то т есть остаточный член е (по модулю 1). Значит, в' = ш 9 и = в 8 т = е — т = ш — и что и следовало доказать. Если е„ < р, должно оказаться, что е„ = р — 1 и ю — и кратно 6 '.
Таким образом, результат будет совпадать с окрутленным значением, если его абсолютная величина меньше, чем Ье '+Ь л. Поскольку Ь < 3, мы, конечно же, получим (ле — и! < (ю — и — е(+ (е( < — '+(Ь" ' — Ь ') < Ь" 1+Ь '. Таким образолб доказательство завершено. $ В доказательствах теорем А, В и С нет ссылок на точное определение округления (х) в подозрительных случаях, когда х равно точно половине интервала между последовательными числами в формате с плавающей точкой. Как бы не разрешилась данная ситуация, это не отразится на истинности использованных в процессе доказательств.
Не существует правила округления на все случаи жизни. Например, обычно желательно иметь специальное правило для округления прибыли, облагаемой налогом. Но для большинства расчетов наилучшим следует считать предлагаемый в алгоритме 4.2.1Х вариант, который "настаивает" на том, чтобы наименее значимый разряд был всегда четным (или всегда нечетным) в случаях, допускающих неоднозначность трактовки правил округления. Реализовать аппаратно такое правило— отнюдь не тривиальная задача. Однако существуют весьма серьезные практические соображения в пользу ее решения, поскольку такие неоднозначные ситуации часто возникают совершенно неожиданно и двойственное решение приводит к существенно отрицательным результатам.
Например, рассмотрим действия в десятичной системе и будем считать, что остаток 5 всегда округляется в большую сторону. Тогда, .если и = 1.0000000 и е = 0.55555555, получим и ~Э е = 1.5555556. Если в формате с плавающей точкой из этого результата вычесть е, то получится и' = 1.0000001. Сложение и вычитание е из и' дает 1.0000002, а в следующий раз получим 1.0000003 и т. д. Таким образом, результат будет постоянно увеличиваться, хоти складывается и вычитается одно н то же число. Это явление, называемое дрейфом, не возникнет, если использовать стабилизирующее правило округления, базирующееся на приоритете наименее значимого разряда. Теорема Р.
(((и Ве) Эе) Юе) бе = (иВе) Ое. Например, если и = 1.2345679 и е = — 0.23456785, то и Ю е = 1.0000000, (ише) Ое = 1,2345678, ((ибо) Яе) Юе = 0.99999995, (((ибо) Ве) Ве) Ее = 1.2345678. Доказательство для любых и и е, как иам кажется, потребует еще более скрупулезного анализа частных случаев, чем в теоремах, рассмотренных вьш|е (см. ссылки на литературу, которые приведены ниже).
1 Теорема )У справедлива и в отношении "округленных до четного", и в отношении "округленных до нечетного", и возникает вопрос, какой же из вариантов выбрать. Когда основание системы счисления 6 нечетно, подозрительных случаев возникнуть не лложет, кроме как при делении в формате с плавающей точкой, а здесь округление, в общем-то, не имеет значения. Если же основание системы счисления чешно, есть смысл придерживаться следующего правила: "Округлять до четного, если Ь~2 нечетно, и округлять до нечетного, если Ь~2 четно".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
