Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 73
Текст из файла (страница 73)
Таким образом, показано, что (изе) зю приблизительно равно иЗ(евою), за исключением тех случаев, когда происходит исчезновение илн переполнение порядка, Эта интуитивная идея "приблизительного равенства" заслуживает более подробного изучения; можно ли дать более точную формулировку этого утверждения? Программист, использующий арифметические операции в формате с плавающей точкой, почти никогда не испытывает желания проверить, не выполняется ли точное равенство двух вычисленных значений, так как равенство является крайне маловероятным. Например, если используется рекуррентное соотношение х„~1 = Дх„), о котором известно из литературы, что х„стремится к некоторому пределу при и -+ оо, то, скорее всего, будет ошибкой продолжать вычисления, пока для некоторого и не выполнится равенство х„+1 — — х„, так как последовательность х„может ввиду округления промежуточных результатов оказаться периодической с большим периодом.
Разумно продолжать вычисления липть до тех пор, пока для некоторого подходящим образом выбранного д не станет справедливым неравенство )х„.~1 — х„~ < о; но так как порядок величины х„заранее неизвестен, еще лучше— дождаться выполнения неравенства (2Р) !Хв.~.1 хв) < с!ха(, ~ — и > (ь'" ',ь'" '); )е — и( < с шах(Ь'" ', Ь'" в); и — е > вшах(Ь'" в,Ь'" в); )е — и) < а шт(ь'" в, Ь'" в) (21) (22) (23) (24) и»е (с) и е (с) и~ е (с) име (с) тогда и только тогда, когда тогда и только тогда, когда тогда и только тогда, когда тогда н только тогда, когда Эти определения подходят как для нормализованных чисел, так и для ненормализованных, Согласно этим определениям для любой данной пары значений и и е может вьгполняться в точности одно из соотношений и и» е (определенно меньше), и е (приблизительно равно) илн и м е (определенно больше).
Отношение и м е несколько более сильное, чем и е, и его можно читать так: "и, по существу, где с — число, которое должно быть выбрано заранее. Соотношение (20) позволяет другим способом выразить то, что числа х +1 и х„приблизительно равны; и наше обсуждение цоквзывает, что при анализе вычислений над числами с плавающей точкой отношение "приблизительного равенства" было бы более полезно, чем традиционное отношение равенства, если только первое отношение удастся определить надлежащим образом. Другими словами, тот факт, что строгое равенство величин в формате с плавающей точкой играет очень небольшую роль, приводит к необходимости ввода новой операции сравнения величин с илаваюеэвй точкой, назначение которой — упростить оценку относительных значений двух таких величин.
Представляются подходящими следующие определения для чисел с плавающей точной и = (с„, ~„) и е = (е„, у„) по основанию Ь с избытком в: и то же самое неравенство выполняется, если поменять местами (и З е) З ы и и З (е З ы). Следовательно, в соответствии с (34) справедливо соотношение (иЗв)ЗымиЗ(еЗв) (е) (39) для е > 2еоП1 — 1еа)~.
Например, при Ь = 10 и р = 8 можно взять е = 0.00000021. Соотношения -ч,, ь. и м полезны для численных алгоритмов, и позтому разумно включить в состав системного программного обеспечения компьютера программы для сравнения чисел с плавающей точкой наряду с программами для выполнения над ними арифметических действий. Теперь вновь перейдем к вопросу о нахождении пючимх соотношений, которым удовлетворяют операции над числами с плавающей точкой. Интересно отметить, что сложение и вычитание таких величин ие полностью выпадают нз паля зрения аксиоматики, так как они удовлетворяют нетривиальным тождествам, сформулированным в следующих теоремах. Теорема А.
Пусть и я е — нормаллзованные числа с плавающей точкой. 2Ъгда ((и й в) Э и) + ((и Э е) Э ((и б е) Э и) ) = и З в (40) прп условии, что не происходит переполнения нли исчезновения порядка. Это доюльно громоздкое тождество можно переписать в следующем бочее простом виде. Положим (41) и" = (ибв) Эв', ев =(ибо) Эй.
Интуитивно ясно, что и' н и" должны быть приближениями к и, а в' и еа — приближениями к е. Теорема А утверждает, что и б е = и'+ еп = и" + Ь'. (42) Это более сильное утверждение, нежели тождество и З в = й З еа = и" 9 е', (43) являющееся следствием округления (42). Докаааглельсгпао. Будем говорить, что г является осшаточнмм членом х (цо мо- дулю Ь'), если 8%х (по модулю Ь'), )Ф! С 1тЬ', (44) Таким образом,х — гоцпб(х) всегда равно остаточному члену х.
Доказательство теоремы А в значительной мере основывается на следующих простых умозаключениях, доказанных в упр. 11. Лемма Т. Если 1 есть остаточный член числа в формате с плавающей точкой х, тохЭ$=я-г. 1 Пусть ю = и Ю е. Теорема А становится тривиальной, когда ы = О. Умножив все переменные на подходящие степени Ь, можно, не теряя общности, предположить, что е = р. Тогда и+ е = и+ г, где г есть остаточный член и+ е (по модулю 1). Далее, и' = гоцци(ю — е) = гоцпб(и — г) = и — г — 1, где 1 есть остаточный член и — г (по модулю Ь') и е = ев - р.
Если е < О, то 1 ьэ и -г эз -в (по модулю Ь'). Следовательно, т есть остаточный член -е и е" = гоипб(то — и') = гоипт((о+1) = и+1, что доказывает (40). Если е > О, то )и-г) > Ьг-1э, а поскольку(г) < эт, имеем )и) > Ь" — 1. Из этого следует, что исеть целое число, так что г — остаточный член е (по модущю 1). Если и' = и, то 1 = -г является остаточным членом -о. В противном случае соотношение гонит((и-г) ф и влечет за собой (и) = Ь" — 1, )г) = 1~, )и') = Ь", 1 = г; опять же, 1 — остаточный член -е. $ Теорема А выявляет некое свойство регулярности операции сложения в формате с плавающей точкой, но она не представляется уж очень полезным результатом.
Следующая теорема гораздо более существенна. Теорема Б. В предположениях теоремы А и ори условии (41) справедливо тожде. ство + =(+ )+((. ")е( ")), (45) Докаэатиельстео. Рассматривая каждый из случаев, возникших при доказательстве теоремы А, мы неизменно обнаружяваем, что и ст и' = и — и', е От ео = о — е" и (и — и') йт (е — ьо) = (и — и') + (е — о"). Значит., (45) следует из теоремы А.
Если учесть принятые в предыдущем доказательстве обозначения, эти соотношения окажутся эквивалентными следующим: готтпс)(1+ г) = $ + г, гонит)(т) = Г, гоипд(г) = г. (46) В упр. 12 рассматривается теорема для особого случая, когда )е„— е„) > р. Иначе и+о имеет не более 2р значащих разрядов, и можно легко показать, что гоши1(г) = г.
Если теперь е > О, доказательство теоремы А показывает, что 1 = -г или т = г = х-т. Если е < О, имеем т + г гв и и т тя -о (по модулю Ь'); этого достаточно для доказательства того, что 1+ г и 1 при округлении не изменяются (округляются до "самих себя"), обеспечивая выполнение неравенств е„> е и е„, > е.
Но либо е„< О, либо е, < 0 будут противоречить нашей гипотезе о том, что )е„— ет! < р, поскольку е„, = р. 3 Теорема В дает в явном виде формулу длл получения раэиостви между и+ е и идее в терминах величин, которые можно вычислить, непосредственно используя пять арифметических операций в формате с плавающей точкой. Если основание системы счисления Ь равно 2 или 3, можно улучшить этот результат и получить точные значения корректирующих членов, используя всего две арифметические операции в формате с плавающей точкой и одно сравнение абсолютных величин в формате с фиксированной точкой. Теорема С.
Если Ь < 3 и )и) > )е), то + = ( ) + (. (. )) ' Докаэашелъствво. Следуя соглашениям, принятым при доказательстве предыдущих теорем, желательно показать, что о О е' = г. Достаточно показать, что е' = ю — и, поскольку из (46) затем последует е О е' = гоипд(е — е') = гонит((и+ о — ит) = гоипт((г) = г. Фактически нужно доказать (47) для любых Ь < 3 и е„> е„.
Если е„> р, то г есть остаточный член е (по модулю 1). Значит, е' = мети = еЭг = е — г = ит — и, что и следовало доказать. Если е, < р, должно оказаться, что с„ = р — 1 и в — и кратно 6 1. Таким образом, результат будет совпадать с округленным значением, если его абсолютная величина меньше, чем Ь' '+6 '. Поскольку 6 < 3, мы, коиечио же, получим )ю-и( < (ю — и — е(+(е( < -'+(Ь" '-Ь 1) с Ьг '+Ь '. Таким образом„ доказательство завершено. ! В доказательствах теорем А, В и С нет ссылок на точное определение округления (з) в подозрительных случаях, когда я равно точно половине интервала между последовательными числами в формате с плавающей точкой. Как бы не разрешилась данная ситуация, зто не отразится на истинности использованных в процессе доказательств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
