Дискретно-непрерывная математика (стр. 80 )

Посмотрим теперь на алгоритмы, описанные в терминах ве­щественных чисел. К их числу можно отнести, скажем, схему Горнера или метод Гаусса. Если такой алгоритм реализуется на компьютере, т. е. с использованием машинной арифметики, то даже исходные данные в общем случае не могут быть пред­ставлены точно. Возникающие при этом трудности преодоле­ваются применением машинной интервальной арифметики. Ис­ходные данные просто заключаются в интервалы, имеющие своими границами машинные числа. Если теперь представить себе, что алгоритм будет выполняться без учета погрешностей округления, то, как показано в микромодуле 24, ширина реализующего ин­тервала станет, вообще говоря, возрастать в большей степени, чем это обусловлено исходными данными. При наличии по­грешностей округления описанное свойство проявляется еще сильнее.

Обсудим следующий вопрос: на какой рост точности результата можно рассчитывать, если перейти от алгоритма, использующего машинную интервальную арифме­тику с t1 цифрами в мантиссе, к алгоритму, использующему t2-значную арифметику, где t2>t1? Предполагается, что при таком переходе диапазон возможных значений порядка остается неизменным. Таким образом, все числа, представимые с t1 циф­рами, столь же точно записываются с t2 цифрами.

Пусть и

Чтобы гарантировать единственность представления х, мы пред­полагаем, что не существует v0 такого, что при v ≤ v0 все av равны b — 1. Будем также считать, что число х не представимо в t1-значной системе с плавающей точкой. (Если бы последнее допущение отсутствовало, то следующее рассуждение было бы совершенно излишним.) Пусть, кроме того, интервальное округ­ление (8) осуществляется через оптимальное округление гра­ниц. В соответствии с (8) при х > 0 получаем

где

Очевидно, что ширина ↕ х есть

Точно такой же результат получается для ширины ↕ х при х < 0. В дальнейшем зависимость результата от длины мантиссы бу­дет отражаться с помощью записи fl1(x) (соответственно fl2(x)). Следовательно, под fl мы будем понимать интервальное округ­ление вещественного числа (а впоследствии и вещественного ин­тервала). Предыдущее равенство теперь может быть переписано в виде

Аналогично, для мантиссы длины t2 = t1 +l получаем

Неравенство выполняется как строгое в случае, когда х пред­ставляется точно с t2-разрядной мантиссой. Как следствие

(14)

Из предположений, сформулированных для интервальных округлений, следует, что для двух машинных интервалов А и В

(см. определение 1). С помощьювычисляются

границы точного значения результата, причем

и

Следовательно, можно записать

(15а)

Оценкой ширины результата служит

(15b)

Эта оценка показывает, что когда используется мантисса фик­сированной длины, то рост шириныопределяется величиной |А *В|. Пусть мы знаем, что х принадлежит интервалу X из I(R). Естественно выбрать некоторое х из X в качестве приближен­ного значения х. Оценим абсолютную и относительную погреш­ность такого приближения:

(16)

и если то

). (17)

Теорема 4. Пусть А, В, С и D — машинные интервалы, причем

(18)

и

(19)

Предположим, что * — одна из арифметических операций над вещественными интервалами и Тогда границы для (соответственнооказываются в bl раз меньше, чем границы для (соответственно

Доказательство. Используя (15b), (10 п.7.2), (12 п.7.2), неравенство

а также первую строку из (19), сразу же получаем

На основе (18) и (19) аналогичным способом доказывается, что

(20)

Из (18) и теоремы 2 следует включение

Оно справедливо, поскольку мы предположили, что интерваль­ное округление задано через оптимальные округления границ. Таким образом,

(21)

Из (15b), (20) и неравенствавытекает

Это доказывает утверждение теоремы для верхних границ абсо­лютной погрешности. Для верхних границ относительной по­грешности требуемый результат получается непосредственно из (21).

Простое, но важное следствие из теоремы 4 содержит

Теорема 5. Допустим, что справедливы все приведенные выше предположения, касающиеся машинной интервальной арифме­тики. Кроме того, имеется заданный в поле вещественных чисел алгоритм, который выполняется в машинной интервальной арифмеmике с мантиссой длины t1. Если затем этот алгоритм выпол­нить в арифметике с мантиссой длины t2, где то границы абсолютной и относительной погрешностей умень­шатся в bl раз. (Под алгоритмом здесь понимается однозначно определенная последовательность арифметических операций вме­сте с конкретными входными данными.)

Доказательство. Из (14) следует, что в нашем случае интер­вальное округление входных данных удовлетворяет важному предположению (19) теоремы 4. Свойства интервальной ариф­метики обеспечивают справедливость (18). Окончательно дока­зательство получаем из теоремы 4 применением полной индук­ции. Теорема 5 указывает способ получения результата с наперед заданной абсолютной или относительной точностью. Пусть, на­пример, d1 — наибольшая ширина, которую имеют результирую­щие интервалы, вычисленные с помощью t1-значной мантиссы, а е — требуемая абсолютная точность. Если то цель достигнута. В противном случае число цифр в мантиссе увели­чивается на l, где l удовлетворяет неравенству

(Такой выбор не гарантирует, что абсолютная погрешность уменьшится в bl раз. В соответствии с теоремой 5 эта оценка верна лишь для верхней границы абсолютной погрешности.)

Факты, обсужденные и доказанные в теореме 5, были изу­чены Румпом; он же проиллюстрировал их числовыми примерами. Один из этих примеров — решение системы уравне­ний, задаваемой матрицей Гильберта размерности 7×7, причем в правой части каждого уравнения стоит 1. Результаты приме­нения к этой системе алгоритма Гаусса, реализованного в ма­шинной интервальной арифметике с 15, 20, 25, 30 и 35 циф­рами в мантиссе, воспроизведены в табл. 1.

Таблица 1

Верхняя граница ρ (Xi) относительной погрешности в алгоритме Гаусса

означает здесь, что интервал Хi содержит 0.

Следует иметь в виду, что в ней дана лишь верхняя граница ρ(Xi) относительной погрешности для каждой компоненты вектора результата.

Pассмотрим следующую задачу. Пусть имеются машинные интервалы (т. е. вещественные интервалы, границами которых служат машинные числа)