Дж. Деммель - Вычислительная линейная алгебра, страница 6

Например, при сложении интервалов а = [ан а ] и 6 = (60 6„] числа а~ + 6| и 24 Глава 1. Введение а„+ 6„округляются соответственно вниз и вверх до ближайших чисел с плавающей точкой сс и с„. Это гарантирует, что интервал с = [сс, с„) содержит в себе сумму любых двух чисел, взятых из а и 6. К сожалению, если, по наивности, кто-то просто возьмет свою программу и заменит в ней все переменные и операции с плавающей точкой интервальными переменными и операциями, то, скорей всего, интервалы, генерируемые модифицированной программой, будут быстро расширяться (возможно даже получение интервала ( — оо, +оо)) и скоро не будут давать никакой полезной информации.

(Простым примером может служить многократное повторение оператора х = х — х, где х — интервал; вместо х = 0 мы получим систему интервалов, в которой при каждом вычитании длина х„— хс интервала х удваивается.) Можно все же так модифицировать старые алгоритмы или сконструировать новые, чтобы получать разумные гарантированные оценки для ошибки (4, 140, 162, 190]. Однако алгоритмы такого рода нередко оказываются в несколько раз более медленными, чем алгоритмы, рассматриваемые в этой книге. Оценки ошибок, которые мы даем, в отличие от интервальных границ, не гарантированы в строгом математическом смысле, но они достаточно достоверны почти во всех ситуациях. (Позже мы обсудим этот вопрос более подробно.) Интервальная арифметика далее в этой книге обсуждаться не будет.

1.6. Еще раз о вычислении многочлена Применим модель округлений (1.1) к анализу вычисления многочлена по пра- вилу Горнера. Напомним основную программу: Р=из Еог Е = сŠ— 1 сЕовсп со 0 р=х р+сн епсЕ Еог Теперь мы пометим индексами промежуточные результаты так, чтобы каж- дому соответствовал единственный символ (в частности, ро — это конечный результат): Рз=аз Еог г' = сŠ— 1 сносна Ео 0 р; = х рс+д + а, епсЕ Еог Далее, для каждой операции с плавающей точкой введем множитель (1+ бс), учитывающий округление: рс= аз Еог г' = сŠ— 1 с)овса 1о 0 р, = ((х рсес)(1+бс) +ас)(1+6), где /Б),/6( < е епс1 Еог -=Ы[ с-1 (1+6,') П(1+61)(1+6,') псх*+ Е=о з-1 П(1+ 61)(1+ 6,'.) у=о азх В результате, получим следующую формулу для вычисленного значения мно- гочлена: 1.6. ЕвГе рвз о вычислении многочлена Это громоздкое выражение типично, если в анализе пытаются проследить за распространением внутри алгоритма канской погрешности округления.

Мы упростим его, используя следующие верхние и нижние оценки: (1+ Б~) (1+ б~) < (1+ е)1 <, = 1+ 1е+ 0(е~), 1 — уе (1+1) (1+61) > (1 — е)' > 1 — уе. Эти оценки верны, если уе < 1. В типичном случае мы исходим из (разумного) допущения, что уе « 1 (для 1ЕЕЕ-арифметики обычной точности это все равно, что»' « 10~), и используем приближения 1 — уе < (1+61) (1+61) < 1+ус.

Это позволяет написать е ро = ~~ '(1+ А)а;х', где ф;~ < 2«(е в=о л ~ а;х' '=о Итак, вычисленное значение ро для р(х) есть точное значение слабо возмущенного многочлена с коэффициентами а,. Это означает, что вычисление многочлена р(х) есть «обратно устойчивый» процесс. «Обратная ошибка», измеряемая как максимальное относительное изменение коэффициентов р(х), ограничена величиной 2Ж. Используя оценку для обратной ошибки, оценим погрешность в вычисленном значении многочлена: д л (1+ 4)а«х' — ~ а;х' а=о .=о ~У;а;х' < ~е2Н(а« . х'! !ро — р (х) ~ а=о < 2(Хе~~ /а; х'!.

з=о 2.;= ! *'! 1Е!=. «**! может служить относительным числом обусловленности для задачи вычисления многочлена. Заметим, что величина 2, ~а;х'~ ограничивает сверху наибольшее значение многочлена, которое могло бы получиться, не будь взаимного уничтожения при сложении чисел с различными знаками.

Наша оценка есть произведение этой величины и числа 2«(е. Аналогичные результаты дает анализ вычисления скалярного произведения и многих других выражений, схожих с многочленами. Если положить 4 = е з1яп(а;х'), то видно, что полученная нами оценка погрешности, с точностью до умеренного множителя 24, достижима.

Отсюда следует, что дробь Глава 1. Введение Ценой удвоения числа операций найденная оценка для погрешности легко может быть вычислена: р = аз, Ьр = )аз) Гог ь = д — 1 с)оьчп Со О р=х р+аь Ьр = )х) . Ьр+ )аь! епь1 Еог еггог )ьоипс) = Ьр = 2д в Ьр Таким образом, подлинное значение многочлена находится в интервале [р — Ьр,р + Ьр], а гарантированное число верных десятичных знаков равно — 1ойьоо Уй)).

Для обсуждавшегося выше многочлена (х — 2) границы его значений изображены в верхней части рис. 1.3. 1Читатель может спросить, не теряет ли граница для погрешности своей справедливости вследствие округлений, произведенных при ее вычислении. Оказывается, что в данном случае округления не создают проблем; в качестве упражнения предлагаем читателю самому убедиться в этом.) Нижняя часть рис.

1.3 есть график функции — 1ойьо )-и), т.е. нижней границы для числа верных десятичных знаков. График свидетельствует, что мы должны встретиться с затруднениями при попытке вычислить р(х) с высокой точностью, если р(х) близко к нулю. Что же особенного в случае р 1х) = О? Дело в том, что произвольно малая ошибка в, сделанная при вычислении р (х) = О, имеет следствием бесконечную относительную ошибку е = о.

Иными словао ми, наша гРаница длЯ относительной погРешности 2дв 2, о )аьхь)/) 2.'ь о аьхь~ бесконечна. Определение 1.1. Задача, число обусловленноспьи которой бесконечно, назы- вается некорректной. В противном случае задача гьазььвается корректной.ь Существует простая геометрическая интерпретация числа обусловленности: оно показывает, насколько далек р (х) от многочлена, для которого задача вычисления значения в точке х некорректна.

Определение 1.2. Пусть р(з) = 2т,". „аьвь и ь)(х) = ~, о Ь,з'. Относительным расстоянием ь1ьр, ь)) от р до ь) называется наимеььььиее число ьх, удовлетворяющее неравенствам ~аь — Ьь! < ьь(р,ь)) )аь) для О < ь < ь1. (Если все аь ~ О, то мозьсььо просто полооьсить ьььр,ь)) = тахо<с<з)яь;-ь~.) Заметим, что если аь = О, то для того, чтобы число ьь1р, ь)) было конечно, Ь, также должно быть нулем. Это определение до некоторой степени нестандартно, поскольку включает в число некорректных задачи, ращения которых изменяются непрерывно (но при этом недифференцнруемым образом). Примерами таких задач могут служить вычисление кратных корней многочленов и вычисление кратных собственных значений матриц Ьразд.

4.3). Корректную задачу можно еще описать как задачу, для которой число верных знаков вычисленного решения, с точностью до заранее фиксированного числа последних разрядов, всегда совпадает с числом разрядов арифметики, используемой для вычислений; если это не так, мы имеем некорректную задачу. Например, при вычислении кратных корней многочлена обычно теряется воловика (или даже более того) точности арифметики. 27 1.6. Еще раз о вычислении многочлена х10е ! 0.8 0.6 0.4 0.2 -1 1.85 1.9 1.95 2 2.05 2.1 16 14 12 10 0 -2 -1 0 1 2 3 4 6 6 Рис.

1.3. График границ погрешности для значений многочлена р = (в — 2)е, вычисленных по правилу Горнера. 28 Глава 1. Введение Теорема 1.2. Предположим, что многочлен р(г) = ~ г а,г' не равен тоже дественно нулю. Тогда ш1п(д(р, д) для многочленов д, таких, что у(х) = О) = ! Е,"= *'! Е,"=, !щ*Ч Друг ми словами, относительное расстояние от р до ближайшего многочлена д, число обусловленносгпи которого в елочке х бесконечно (т.е. д(х) = 0), обратно числу обусловленности многочлена р (х). Доказательство. Положим д(г) = 2 Ь;гг = 2 (1 + е,)а;г', тогда сг(р,ч) = шах; ~е;!.

Из равенствами(х) = 0 выводим ~р (х)! = (д(х) — р (х)( = ! ~,; о е,агх1 < )е,а,х'( < шах, )е;) 2 'г (агх'(, откУда, в свою очеРедь, следУет, что д(Р, д) = шах )е,! > (р(х)(/2 г )агх'). Многочлен д, находящийся на требуемом расстоянии от р, получается при выборе — р (х) е, = . з18п(а,хг). П )агх'~ Это простое взаимно-обратное соотношение между числом обусловленности и расстоянием до ближайшей некорректной задачи очень типично для численного анализа, и позже мы встретим его снова.

В начале этой главы было сказано, что канонические формы матриц будут использоваться как вспомогательное средство при решении линейно- алгебраических задач. Например, знание точной жордановой канонической формы делает вычисление точных собственных значений тривиальным. Существует аналогичная каноническая форма для многочленов, облегчаюшая вычисление их значений с высокой точностью; она имеет вид р(х) = аз Пг (х— г;). Иными словами, в представлении многочлена ис1юльзуются его старший коэффициент аз и корни гы ..,, г„.

Вычисление значения р (х) проводится посредством очевидного алгоритма р = ае (ог г = 1 $о д р=р. (х — г;) епй Еог Нетрудно показать, что вычисленное значение р удовлетворяет соотношению р = р(х) (1+ 6), где ~6~ < 2де, т.е. значение р(х) всегда находится с высокой относительной точностью. Однако для этого нужно знать корни многочлена! 1.7, Векторные и матричные нормы Нормы используются для измерения погрешностей в матричных вычислениях, поэтому нужно уметь обращаться с ними и уметь вычислять их. Отсутствующие в этом параграфе доказательства предлагаются в качестве задач в конце главы.