Форсайт Дж., Малькольм М., Моулер К. - Машинные методы математических вычислений (1040536), страница 5
Текст из файла (страница 5)
Поскольку она используется очень часто, важно иметь возможкость вычислять е"' машинной программой для любого числа с плавающей точкой х. Существует множество методов, на которых она может быть основана, и большинство вычисли- КХ ПРИМЕР ОШИБОК ОКРУГЛЕНИЯ тельных систем научного предназначения имеет подобную программу. Но предположим, что на нашей машине такой программы нет, и спросим себя, как бы мы ее составили.
Эта ситуация может возникнуть для более сложной трансцендентной функции либо на новой вычислительной машине. Вспомним, что для любого действительного (или даже комплексного) значения х число е" может быть представлено как сумма сходящегося бесконечного ряда хБ хБ а"=1+х+ — + — '+.... 2! 31 Попробуем воспользоваться зтим рядом для вычисления е'. Предположим, что наша плавающая система характеризуется параметрами 5=10 и 1=5.
Применим ряд для х= — 5.5. Вот числа, которые мы получим: 4-4л = 1.0000 — 5.5000 + ! 5.125 -27.730 +ЗВ.129 -4!.942 +За.446 -залов +20 76 — 12.692 + 6.9ВОЗ вЂ” 3.4902 + !.5997 + 0.0026363 Мы ограничиваемся при суммировании 25 членами, поскольку последующие слагаемые уже не меняют сумму. Удовлетворительный ли ответ получен? Истинный результат е-"= — -0.00408577, так что вычисление посредством ряда привело к ответу„не имеющему верных цифр. Что же было неправильно? Заметим, что некоторые члены, и следовательно промежуточные суммы, на несколько порядков больше конечного ответа.
При атом такие слагаемые, как 38.129, уже содержат ошибку округления, почти равную по величине окончательному результату. Кроме того, четыре старших (т. е. наиболее значимых) разряда каждого нз восьми членов, превышающих 10 по модулю, были потеряны. Этн восемь членов следовало бы брать с десятью значащими цифрами, чтобы Я. ВЫЧИСЛЕНИЯ С ПЛАВАЮЩЕЙ ТОЧКОЙ 25 получить шесть значащих цифр в ответе.
Более того, потребо-. валась бы еще одиннадцатая цифра, чтобы можно было надеяться получить верную шестую цифру вычисляемой суммы. Это явление иногда называется катастрофической потерей верных знаков; оно часто встречается в плохо продуманных вычислениях. Важно, однако, понимать, что такая потеря знаков пе является причиной ошибки в ответе„она попросту увеличивает ошибки, уже присутствующие в слагаемых '). Хотя иной раз возможно удерживать в вычислениях большее число значащих цифр с целью избежать катастрофической потери знаков, это всегда обходится дорого как по времени исполнения, так и по памяти, и зачастую требует специальных программных средств. Для рассматриваемой задачи есть гораздо лучшее лекарство: именно, вычислить сумму для х=5.5 и затем взять обратное число: ! — в ° в св в ! + 5 .
5+ ! 5. ! 25+ .. = 0.0040865 (в нашей пятизначной десятичной арифметике). При таком способе вычисления ошибка снижается до 0.007ив. Один из важных выводов, следующих из этого примера,— это то, что даже короткая последовательность вычислений может быть связана с серьезными ошибками округления.
Заметьте, насколько хуже была бы задача, если бы мы хотели вычислить е" для х= †1. Реальные машинные алгоритмы для вычисления е" начинаются с разложения х на действительную н дробную части х=т+7, т — целое, 0(~(!. Далее, используя свойства показательной функции, получаем е" = — е '"т = — е" . [ет), или ') е» = есс ч-П~! = [е~ ч-П~1м Каждая нз величин, взятых в квадратные скобки, предпола-: гает вычисление ел для у из интервала 0(у(1. Сграничение у1 на такой малый интервал облегчает вычисление .'т.
Затем результат может быть умножен на ем (которое вычисляется просто~~ или возведен в степень т. [ ') Авторы имеют в виду относитсльнос увеличение ошибки.— Прил. перев.! и) Это прсдставлспис прнмснястся при отрнпатсльном т.— Прия . перев.[ »ХЬ НЕУСТОЙЧИВОСТЪ НЕКОТОРЫХ АЛГОРИТМОВ 99 2.4. Неустойчивость некоторых алгоритмов Задача вычисления е-' ', обсуждавшаяся в предыдущем параграфе, показывает, как плохо продуманный алгоритм может привести к неудовлетворительному результату даже для вполне хорошо поставленной задачи.
Трудность была преодолена посредством изменения алгоритма. Для некоторых задач «хорошие» ответы нельзя получить никаким алгоритмом„потому что задача чувствительна к малым ошибкам, допущенным при представлении данных и в арифметике. Два примера таких задач приведены в 9 2.5.
Важно различать эти два класса ловушек, поскольку неустойчивые алгоритмы и чувствительные задачи встречаются почти во всех областях вычислительной математики. Однако если вы знаете их симптомы, то диагностировать эти задачи уже довольно просто. В этом параграфе мы обсудим более наглядный пример неустойчивого алгоритма. Предположим, что мы хотим вычислить интегралы ! Е = ~ х»е«-««!х и 1 2 и е Интегрируя по частям, получим ! ! ! х»ех-! !!х хие«-! ~ ) пх««е«! ««х» о о нли Е,=! — пЕ„„и=2, где Е,=1/е. Пусть )1=!О н 1=б; мы можем использовать это ре- куррентное соотношение для вычисления приближений к де- вяти первым значениям Е„: Е, 0.367879, Е, ж 0.264242, Е, ж 0.207274, .Е, 0.170904, Е, ж 0.145480, Е, 0.127120, Е, ж 0.110160, Ев — 0 118720, Е, — 0.0684800. Хотя подынтегральное выражение х'е" " положительно на всем интервале (О,!), вычисленное нами значение для Е, отрицательно.
Что вызвало столь большую ошибку? Заметим, что единстееиная ошибка округления, сделанная в приведенных вычисле- з, вычисления с плавающий точкои ниях,— это ошибка в Е„когда 1/е округляется до шести зна. чащих цифр '). Поскольку рекуррентная формула, полученная интегрированием по частям, точна для действительной арифметики, ошибка в Е, всецело обязана ошибке округления, сделанной в Е,. Чтобы понять, как онтибка в Е„ примерно равная 4.412х 10-', становится столь большой, заметим, что она умножается на — 2 при вычислении Е„ затем ошибка в Е, умножается на — 3 при вычислении Е„н т.
д. Таким образом, ошибка в Е, есть в точности ошибка в Е„помноженная на ( — 2)( — 3)... ... ( — 9)=9! или примерно 9! х 4.412 х 10-'ж0.1601. Это огромное увеличение ошибки, содержащейся в исходных данных задачи, есть результат выбранного алгоритма. Подлинное значение Е, (с тремя значащими цифрами) есть — 0.06848+ +0.1601=0,0916. Как можно было бы избрать другой алгоритм, который не имеет подобной неустойчивости? Если мы перепишем рекуррентное соотношение в виде ! — Е„ то теперь на каждом шаге вычисления ошибка в Е„умножается на множитель 1/и. Таким образом, если мы начнем со значения для некоторого Е„при п))1 и будем вычислять в обратном направлении, то любая начальная ошибка или промежуточные ошибки округлений будут уменыцаться на каждом шаге.
Это и называется устойчивадс алгоритмом. Чтобы найти начальное значение, заметим, что хи+1! ! Е = х"г"-"Дх( х" с( == — ~ =- —. 1 = +~ +,. в о Итак, Е„стремится к нулю, когда л стремится к оо. Например, есин мы аппрокснмируем нулем число Е„и возьмем этот нуль стартовым значением, то сделаем начальную ошибку, не превосходящую 1/2!.
Эта ошибка умножается на 1/20 при вычислении Емм так что ошибка в Е„не превосходит (1/20) м (!/2!)ж ж0.0024. Ко времени вычисления Е„начальная ошибка уменьшится до величины, меньшей 4х 10 ', что в свою очередь меньше единственной ошибки округления. Проводя эти вычисления, получаем з) Имеется в виду, что последующие значения для Ев,..., Ев получены округлеиием результатов, вычислеииык точно по содержащему ошибку округлеиия заачеиию для Еь.— Оуимв перев, 2.К ЧУВСТВРРТЕЛЬНОСТЪ НСКОТОРЬРХ ЗАДАЧ з! Когда мы дойдем до Е,,„на-Ральная ошибка в Е„уже совершенно подавлена устойчивостью алгорРРтма и вычисленные значения от Е„до Е, точны во всех шести значащих цифрах, с точностью до возможной ошибки округления в последней цифре. 2.5.
Чувствнтепьность некоторык задач ' Мы покажем теперь, что некоторыс вычислительные задачи поразительно чувствительны к изменению данных. Этот аспект численного анализа не зависит от плавающей системы или выбранного алгоритма. Задача нахождения корней полинома является стандартной вычислительной задачей; зачастую она крайне чувствительна к изменению данных. Например, рассмотрим квадратичный полипом с почти кратными корнями вроде (х — 2)о=--10 '. Корни этого уравнения суть 2~!О-". Однако изменение свооодпого члена на 1О " может вызвать изменение в корнях, равное 10 '.
Этот тип неустойчивости еще более выражен у полиномов более высокой степени. Однако неустойчивость можно наблюдать не только у полиномов с почти кратными корнями. Следующий пример принад'лежит Уилкинсоиу (1963). Пусть р(х) =-(х — 1)(х — 2)... (х — 19)(х — 20) — — хо' — 2!Ох" +.... Корни п(х) суть 1, 2, ..., 19, 20 и хорошо разделены. Этот пример возник на фоне плавающей системы с параметрами (3=-2, 1=-.30. Чтобы ввести тот или иной коэффициент в вычислительную машину, его необходимо округлить до 30-значного двоичного числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
