AOP_Tom2 (1021737), страница 76
Текст из файла (страница 76)
9. [М22) Докажите утверждение (33) и объясните, почему его нельзя усилить до и«в («а + «э). ь 10. [М25] (У. М. Казан (%'. М. КаЬап).) На некотором компьютере неправильно выполняется округление при арифмет«гческих операциях иад числами в формате с плавающей точкой, и фактически программа умножения принимает ва внимание только первые р значащих разрядов 2р-разрядиого произведения 7'„,7' . (Таким образом, если 1„1„< 116, из-за последующей нормализации наименее значимый разряд в и З е всегда оказывается равным нулю.) Покажите, что это приводит к утрате монотонности умножении, т.
е. что существуют такие положительные нормализованные числа с плавающей точкой и, е и ю, что на этол«компьютере и < е, но и З ю > е З «е. 11. [М20] Докажите лемму Т. 12. [М24] Докажите теорему В и (46), если [е„— е ] > р. ь 13. [М25] Некоторые языки программировш«ия (и даже некоторые компьютеры) оперируют только числами в формате с плавающей точкой, не выделяя в отдельную группу точные операции иад целыми числами. Кали желательны и операции нвд целыми числами, можно, естественно, представить их в формате с плавающей точкой.
Тогда, если операции арифметики с плавающей точкой удовлетворяют базовым соотношениям (9), можно считать, что все операции выполняются точно в том смысле, что, если операнды представлены р значащими разрядами, точными будут р значащих разрядов.
Далее, до тех пор, пока можно быть уверенным, что числа не слишком велики, можно складывать> вычитать и умножать целые числа и считать при этом, что округление не сказывается на точности. Но предположим, чта программисту необходимо определить, является ли т точно кратным и, когда т и и ф 0 оба целые. Далее предположим, что в нашем распоряжении илсеется подпрограмма для вычисления величины гавай(в шод 1) = в ( 0в) 1 для любого заданного числа в в формате с плавающей точкой, как в уяр. 4.2.1-15.
В качестве подходящего способа определения, является ли гп кратным и, можно было бы проверить выполнение соотношения (т З н) (.1?е) 1 = О, подразумевая наличие указанной выше подпрограммы. Но, возможно, в некоторых случаях эта проверка не даст адекватного результата нз-за ошибок округления при выполнении вычислений в формате с плавающей точкой. Отыщите подходящие условия, которые нужно наложить на диапазон значений целых чисел и ~ 0 и т, такие, чта т является кратным я тогда и только тогда, когда (т З и) (~мв,с 1 = О.
Другими словами, покажите, что, если т и и не слишком велики, эта проверка дает верный результат. 14. [М87[ Найдите подходящее значение е, такое, что (и З и) З си» в З (и З со) (е), если выполняется ненормализованное умножегше. (Этим обобщается соотношение (39), поскольку ненормализованное умножение нормализованных операндов в, и и си в точности повторяет результат нормализованного умножения.) ь 15. [МЕ4] (Г.
Бьерк (Н. В)аг)с).) Действительна ли вычисленная средняя точка интервала всегда находится между крайними точками? (Другими словами, действительно ли из в < и следует, что и < (в З и) З 2 < и?) 16. [М68[ (а) Чему равно ( .. ((хс З хв) СО хз) З Ю х ) при использовании восьмиразряднога представления в формате с плавающей точкой, если и = 10 и хв = 1.1111111 для любых А? (Ь) Что произойдет, если использовать выражение (14) для вычисления стацолртного отклонения на множестве этих конкретных чисел хз? Что произойдет, если вместо этого выражения использовать формулы (15) и (16)? (с) Докажите, что Яв > 0 в (16) при любых хс,..., хы 17.
[68[ Разработайте подпрограмму ЕСИр для 611, сравнивающую число в формате с плавающей тачкой и, которое находится по адресу АСС, с числом в формате с плавающей точкой и, которое находится в регистре А н устанавливает в индикаторе сравнения значение ьЕЕЕ, ЕООАЬ нли ОЕЕАТЕЕ соответственно результату в М и, и и или в ь. и (е), Здесь е хранится по адресу ЕР31ЬОИ в виде неотрицательного значения с разделяющей точкой, фиксированной слева от старшего разряда слова.
Предполагается, что входные значения нормализованы. 16. [М40[ Существует ли в арифметике ненормализованных чисел подходящее значение е, такое, чФа в З (и З си) (в З и) йс (к З си) (е)? ь 19. [М80[ (У. М. Квхвн.) Проанализируйте следующие процедуры суммирования хс,..., х„в формате с плавающей точкой: во = со = 0; уз = хаЕсв м вв =вз-свуы се =(во Евв,)Еуы где1<А <а. Будем считать, что относительная ошибка в этих операциях определяется по формулам ув = (хз — сс с)(1+ Оь), вс = (вв с+ уз)(1+аз), се = ((зе — вз с)(1+Те) — ув)(1+ Аз), где [Ов[,[оз[,[ТАЬ[дв~ < е.
Докажите, что в = 2 в с(1+8в)хы где [8в[ < 2е+О(иез). [Теорема С утверждает, что, если Ь = 2 и [вв с[ > [уз[, имеем точное равенстно вв с+уз = вв — сы Но в данном упражнении желательно получить оценку, которая справедлива дооссе в тном случае, когда регультпагл операции в формате с плавающей гаечкой округлен не очень аккураглн, прн единственном предположении, что каждая операция дает ограниченную относительную ошибку,] 20.
[25] (С. Линненмаа (Я, т" тпла!пшаа).) Найдите все и и щ для которых [и] > ]о], а соотношение (47) не выполняется. 21. (Мдд] (Т. Дж. Деккер (Т. 5. Ве)т)гег).) Теорема С показывает, как выполнить "точное" гложение чисел в формате с плавающей точкой.
Покажите„как выполнить "тпо тнае" умноаюение чисел в формате с плавающей точкой: выразите произведение ие в форме ю+ ю, где в и ю вычислены на основе заданных чисел я формате с плавающей точкой и н о с использованием только операций Щ, 9 и Э. 22. [МЮО] Может лн возникнуть дрейф при умножении и/илн делении в формате с плавающей точкой? Рассмотрите последовательность хо = и, хгл+т = хг Зк, хге+г = хгчэт Зе при заданных и и е ф О. Каково значение наибольшего индекса Ь, при котором возможно выполнение условия хг ф хг+г? ° 23.
[Мдд] Докажите или опровергните следующее утверждение: для всех чисел и в формате с плавающей точкой справедливо равенство и Ю (и (]чье) 1) = [и]. 24. [М27] Рассмотрим множестэо всех интервалов [щ ., и„], где ит и и, есть либо отличные от нуля числа в формате с плавающей точкой, либо специальные символы +О, — О, +ос, — оо. Каждый интерэал должен иметь щ < и„и щ = и, допускается только при условии, что щ конечно и отлично от нуля. Интервал [щ .. и„] вмещает все числа х в формате с плавающей точкой, такие, что и~ < х < и,, причем, мы полагаем, что — со < -х < — 0 < +О < +х < +со для всех возможных х.
(Таким образом, (1..2] означает 1 < х < 2; (+0..1] означает 0 < х < 1; [ — 0 .. 1] означает О < х < 1; ( — 0 .. +0] представляет единственное значение 0 [ — со .. +со] вмещает все,) Покажите, как определить соответствующие арифметические операции на всех этих интерэалах, не принимая эо внимание индикаторов переполнения или потери значимости, кроме как прн делении на число из интервала, содержащего нуль.
ь 25. [! 5] Когда речь заходит о точности выполнения арифметических операций в формате с плавающей точкой, ошибки зачастую приписываются лотказам", которые возникают при вычитании близких по значению величин. Но, если и и и почти равны, разность и Ю е получается безо всяких ошибок. Что же тогда подразумевается под "отказами"? 26.
(М21] Дано: и, и', к и о' — положительные числа в формате с плавающей точкой, причем и и (т) и и и' (е). Предполагая использование нормализованной арифметики, докажите, что сущестэует малое значение е', такое, что и 9 о и' Ю и (е ). 27. [Мд?] (У. М, Кахан.) Докажите, что 1 З (1 З (1 З и)) = 1 Зи для любых и ф О. 25. [аду] (Г. Дж. Диамоттд (Н. С. О!атпопд).) Предположим, 7(х) есть жестко возрастающая функции на некотором интервале (хо .. х,], и пусть д(х) — обратная ей функция. (например, 1 н д могут быть "ехр" и ")и" или "еап" и "агсгап",) если х — число в формате с плавающей точкой, такое, что хе < х < хт, то пусть 7(х) = тоипд(1(х)) и, если у — другое число, такое, что /(ха) < у < 7(хт), пусть д(у) = гоипд(д(у)).
Далее, пусть Ь(х) = д(т" (х)), если только оно определено. Хотя Ь(х) и не всегда равно х из-за округления, можно рассчитывать, что Ь(х) очень близко к х. Докажите, что если точность Ьг как минимум равна 3 и если 1' — жестко вогнутая или жестко выпуклая (т. е. 1 '(х) имеет тот же знак для всех х, принадлежащих интервалу [хе хт]), то многократное применение Ь будет устлойчивмм в том смысле, что Ь(Ь(Ь(х))) = Ь(Ь(х)) лля всех х, таких, что обе части этого равенства определены.
Другими словами, ие должно быть никакого "дрейфа", если подпрограмма правильно запрограммирована. ь 29. [М25) Приведите пример, чтобы показать, что Ье > 3 есть необходимое условие для предыдущего упражнения. ь 30. [МЯО) (У. М. Кахан.) Пусть у(х) = 1+я+ + хю~ = (1 — хшт)/(1 — х) для х < 1 и "усть д(у) = 1((5 — у )(3+ 3.45у )) при 0 < у < 1. Вычислите д(у) на разных карманньсх калькуляторах лля у = 10 ~, 10 ~, 10 ~, 10 ~ и объясните, почему все результаты> которые при этом получены, различны. (Поскольку в большинстве современных калькуляторов округление выполняется неправильно, результаты лсогут стать лля вас большим сюрпризолс.
Обратите внимание, что д(с) = 107 — 10491.35с~ + 659749.9625е~ — 30141386.26625с~ + 0(с"),) 31. [М25[ (У. Кулиш (11. Кп!1асЬ).) При вычислении полинома 2у~ + 9хэ — у лля х = 408855776 и у = 708158977 с использованием стандартного пакета подпрограмм арифметики с плавающей точкой с двойной точностью (53 бит) получен результат ш -3.7 х 10 ш Вычисление по альтернативной формуле 2у~ + (Зх — у~)(Зх~+ у ) дает +1 0 х 10сх Правильньсй ответ, однако,— — точно 1.0. Объясните, как строить аналогичные примеры нестабильности вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
