Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 5
Текст из файла (страница 5)
Число а, не представимое в ЭВМ точно, подвергается округлению, т. е. оно заменяется близким ему числом а, прел ставимым в ЭВМ точно. Точность представления чисел в ЭВМ с плавающей запятой характеризуется относительной погрешностью ~а — аИа~. Величина относительной погрешности зависит от способа округления. Простейшим, но не самым точным способом округления является отбрасывание всех разрядов мантиссы числа а, которые выходят за пределы разрядной сетки.
Найдем границу относительной погрешности при таком способе округления. Пусть дли записи мантиссы в ЭВМ отводится т двоичных разрядов. Предположим, что надо записать число, представленное в виде бесконечной двоичной дроби Итак, относительная точность в ЭВМ с плавающей запятой определяется числом разрядов г, отводимых для записи мантиссы. Можно считать, что точное число а и отвечающее ему округленное число а связаны равенством а=а(1+ в), (6) где /е~ (2 '. Число 2 ' называют иногда машинным эпсилоном. Оно характеризует относительную точность представления чисел в ЭВМ.
Для ЭВМ БЭСМ-6 имеем (=40, 2 '=10 ", т. е. относительная точность представления чисел составляет 12 десятичных знаков. Соотношение (6) справедливо лишь в случае ~ а()Мь где М,— машинный нуль. Если же число а мало, а именно ~!а'!(М„то полагается а=О, что соответствует е= — 1 в формуле (6).
3. Накопление погрешностей округления. В процессе проведения вычислений погрешности округления могут накапливаться, так как выполнение каждой из четырех арифметических операций вносит некоторую погрешность. Будем в дальнейшем обозначать округленное в системе с плавающей запятой число, соответствующее точному числу х, через П(х) (от английского 1!оаПпд — плавающий). Считается, что выполнение каждой арифметической операции вносит относительную погрешность не большую, чем 2 '. Это предположение можно записать в виде П (авЬ) =ааЬ(1+в), (7) где звездочка означает любую из операций +, †, Х,:, и (е~ (2-', Если результат выполнения арифметической операции является машинным нулем, то в формуле (7) надо положить е= — 1.
Может показаться, что предположение (7) не обосновано, так как согласно (б) каждое из чисел о и Ь записывается с относительной погрешностью 2-', следовательно, погрешность результата может достигнуть 2-'+'. Однако ЭВМ обладает возможностью проводить промежуточные вычисленяя с двойной точностью, т. е. с мантиссой, содержащей 2г разрядов, причем округлению до г разрядов подвергается лишь окончательный результат. Это обстоятельство позволнет добяться выполнения соотношения (7). Для оценки влияния погрешностей округления на результат того или иного вычислительного алгоритма очень часто используется предположение о том, что результат вычислений, искаженный погрешностями округления, совпадает с результатом точного выполнения этого же алгоритма, но с иными входными данными. Рассмотрим, например, процесс вычисления суммы я=у~+ Уз+ Уз трех положительных чисел.
Пусть сначала находится сумма у,+у, Тогда согласно (7) получим г1=П(У1+Уз)=(У~+Уз) (1+е1), (в,~ ~(2 Затем в результате сложения г, и у, получим число з=П (а~+уз) = (а~+уз) (1+ез), где 1е,~ (2 '. Таким образом, вместо точного значении суммы г получаем приближенное значение 2=(у,+у,) (1+е,) (1+е»)+у»(1+е.). Отсюда видно, что результат выполнения алгоритма (8), искаженный погрешностями округления, совпадает с результатом точного выполнения того же алгоритма (8), примененного к другим исходным данным у =(1+е») (1+ а») у, »=1, 2, у,= (1+е,)у,. »» г» = ~»„' уь »гх (9) Тогда вычисления организуются обычно следующим образом. Задается начальное значение г,=О и затем последовательно, начиная с 1=1, находятся числа гь связанные рекуррентным соотношением г»=г»»+у„1=1, 2, ..., и, г,=б.
(10) Для вычисления произведения »» г»» = П Уу достаточно задать начальное значение г,=1 и воспользоваться ре- куррентными соотношениями г»=у»г» „1=1, 2, ..., и, г,=1. (12) Уравнения (10) и (11) являются частными случаями линейного разностного уравнения первого порядка г,=У»г»-»+»Рь 1=1, 2, ..., и, (13) где йь»р» — заданные числа, г, — искомые числа. Для уравнения (13) рассматривается задача с начальными условиями или задача Коши, которая состоит в отыскании всех гь 1=1,2,..., и, при за- 20 На этом же примере видно, что результирующая погрешность зависит от порядка выполнения операций, так что вычисление суммы (8) в обратном порядке (у,+у,)+у, может привести к другому Результату. Приведенный пример имеет чисто иллюстративное значение, так как число слагаемых в сумме (8) невелико, а погрешности е» малы.
Практический интерес представляют оценки результирующей погрешности в зависимости от числа выполненных арифметических действий и. Однако прежде чем перейти к получению таких оценок, необходимо познакомиться с методами решения разностных уравнений. 4. Разностные уравнения первого порядка. Предположим, что надо вычислить сумму данном начальном значении г,. Ясно, что решение задачи Коши для разностного уравнения (13) существует и единственно.
Коэффициенты «//, правые части «р/ и искомое решение г/ уравнения (13) можно рассматривать как функции целочисленного аргумента /, т. е. ///=«/(/), «р/=«р(/), г/=г(/). Нам потребуется прежде всего записать решение уравнения (13) в явном виде. Подставляя в (13) вместо г,, выражение и/ « ///-«г/-ъ+ щ-н получим / «//«// — « /-2+ ц~/+«/ЯЗ- « ° Теперь можно подставить сюда выражение для г, „затем — для г;, и т. д, В результате получим формулу, в которой г/ выражается через г/ „«р/ «+„«р/ ы„..., «р/, Эта формула имеет вид / г/=(///г/ /+ 'Я (//,/ «~рм 1=1,2,...,/ — 1,!, /=1,2,...,п, л=/-/+« (14) где Я // = (15) «//«//са «//-/««. 1 < 1 ~ /. Строго доказать формулу (14) можно нндукцией по числу / прн каждом фиксированном 1. Нам потребуется формула (!4) при 1-!, т.
е. г/=/г//г +~к~~ «г/,/-««ры /=1,2,,п, (16) (20) 2! где согласно (15) 1, й=), /е/,/-а = о/а/ «... о,+„0<й</ — 1. В частности, если (13) является уравнением с постоянными коэффициентами, т. е. «)/=«/ для всех !, то из (16) получим / г/=«)/ге+~ ///««/м /=1,2, ...,л. (18) я « Явную формулу (16) можно использовать для получения различных оценок решения г/ через начальные данные г„заданные коэффициенты «// и правые части фя Л е м м а 1.
Если для некоторого «/) 0 выполнены неравенства ~ «// ~ = «/, /=1, 2,..., п, (19) то для решения уравнения (13) справедливы оценки / 1г/(<д/!ге~+ 'Я д'-'!Чъ1 /=1 2 и. Доказательство. Из (!7) и (19) получаем, что )(~кт,( ~у~-', й=б, 1,..., 1. Отсюда и из (16) следуют оценки (20). 3 а меча н ие. Оценки (20) неулучшаемы в том смысле, что для уравнения (13) с постоянными коэффициентами и положительными гм ~рй, и=1, 2, ..., Х, неравенства (20) выполняются согласно (18) со знаком равенства. 5. Оценки погрешностей округления. Приведем примеры оценок погрешностей округления, возникающих в результате выполнения вычислительных алгоритмов.
Нас будет интересовать в основном зависимость результирующей погрешности от числа арифметиче- ских действий п и от величины е=2 ', определяемой разрядностью ЭВМ. Пр имер 1. Вычисление произведения "=Пу )=1 п вещественных чисел проводится по формуле 1=1, 2,..., п, го=1. (21) Предположим, что в результате округления вместо точного зна- чения гт, получено приближенное значение г,, Тогда согласно (7) вместо уэгэ, получим величину 1! (узгт,) =у,гт, (1+ ез), где 1е;~(е=2-', Таким обРазом, вместо гт полУчаем г; = (1+ е;) уэгт,„ т.
е. приближенное значение гт удовлетворяет рекуррентному соот- ношению (22) гэ=уэгт „1=1, 2, ..., п, г,=1, где у;=ут(1+е,). Результирующая погрешность равна й й г. — г. = 11 у) — Г) (1+ е)) у;, !=т поэтому относительная погрешность есть й ", "=' — П('+'). й )=т Для оценки относительной погрешности заметим, что (1+е,) (1+в, 1=1, 2,..., п, е=2-', поэтому с точностью до величин второго порядка малости относи- тельно е можно считать, что (23) 22 ! г„— г„ " (пе=п2 г При выводе оценки (23) предполагалось, что е=2-', т.
е, при перемножении не возникает чисел, меньших машинного нуля или больших машинной бесконечности. Однако может оказаться, что на каком-то этапе вычислений в качестве промежуточного результата будет получен либо машинный нуль М„либо машинная бесконечность М . Поскольку оба указанных случая приводят к неверному окончательному результату, необходимо видоизменить вычислительный алгоритм. Оказывается, что здесь существенным является порядок действий. Пусть, например, М,=2 ' и М =2' при некотором р>0. Предположим, что надо перемножить пять чисел у,=2"', у,=2"', У,=2"", У,=2 "', у,=2 "". Каждое из этих чисел и их произведение 2'" принадлежат допустимому диапазону чисел (М„М ), Однако произведение у,у,у,=2'"'>М, поэтому при указанном порядке действий дальнейшее выполнение алгоритма становится невозможным.
Если проводить вычисление в пор~дне узу!узу!у!, то получим у,у,=2-'гп(М„следовательно, 1!(У,у,)=0 и все произведение окажется равным нулю, т. е. получим неверный результат. В данном примере к верному результату приводит вычисление произведения в порядке У!у!у!Угу!. В случае произвольного числа и сомножителей можно предложить следуюшнй алгоритм вычисления пронзвсдення (см. [6[). Предположим, что [у
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
