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

удовлетворяет соотношению

В соответствии с (21 п.7.2) получаем

Пусть теперь

Тогда

С учетом (9 п.7.2), (14 п.7.2) и приведенного выше включения имеем

Исходя из (10 п.7.2), (12 п.7.2), (3 п.7.2) и (20 п.7.2), получаем

Посколькуиз (21 п.7.2) следует, что

Определение 6 п.7.2 и соотношения (4 п.7.2), (5 п.7.2) дают неравенство

На основе приведенных выше неравенств получаем

И наконец, после применения теоремы 5 к выражению h(X— z) оказывается, что

При выполнении некоторых условий дифференцируемости для аналитических выражений можно определить общие условия, при которых соотношение (4) справедливо. При этом теоремы 4 и 6 получаются как част­ные случаи. У Херцбергера можно найти простую интерполяционную формулу, вычисляющую множество значений для семейства многочленов с заданными коэффициентами Им используется тот вытекающий из теоремы 2 факт, что интервальное оценивание позволяет точно вычислить множество значений функции, когда все переменные и параметры входят в аналитическое выражение лишь по одному разу.

Корнелиус и Лонер предложили выражение f(X), для которого q(W(f, X), При s = 1, 2, 3 f(X) вычисляется с по­мощью весьма простого алгоритма.

Микромодуль 25

Машинная и комплексная интервальная арифметика

7.3. Машинная интервальная арифметика

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

Здесь т — мантисса, b — основание степени, е — порядок. Как правило, для внутримашинного представления выбирается осно­вание b, равное 2, а мантисса нормализуется, т. е. ее абсолют­ное значение помещается в интервал [1/2, 1). Целое е при­надлежит интервалу

Множество машинных чисел описанного типа обозначим че­рез RM, и всюду далее будем предполагать, что оно симметрично относительно нуля, т. е. RM = — RM. Для аппроксимации веще­ственных чисел, лежащих в интервале можно с успехом использовать машинные числа Аппроксимация достигается применением отображения

(1)

Это отображение называется округлением, если выполнено свой­ство

(2)

Округление, которое отображает RM в RM так, что

(3)

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

Особый интерес представляют так называемые направлен­ные округления. Если для округления ↓ справедлива импли­кация

(4)

то говорят об округлении вниз. Аналогично,

(5)

определяет округление вверх. Техника выполнения этих округ­лений для различных способов представления чисел неодно­кратно освещалась в литературе. Подобно тому как вещественные числа прибли­жаются с помощью машинных, можно вещественные интервалы приближать машинными интервалами. В этом случае интервал X из І(R), для которого справедливо соотношение заменяется соответствующим машинным интервалом из множества

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

причем

(6)

и

(7)

Если рассмотреть переход от интервала из І(R) к его машинному представлению то окажется, что (7) означает, что необходимо осуществить этот переход путем округления каждой из границ X. Из (6) следует, что границы должны быть округлены направленно. Таким образом, округ­ление интервала X состоит в нахождении ↕ X по правилу

(8)

Проведенное обсуждение показывает, что для того, чтобы округ­лить интервал, достаточно иметь ↓ — направленное округление вниз. С другой стороны, ↑ и ↓ не обязательно должны быть связаны соотношением (5).

Если над двумя машинными числами х и у из Rm произво­дится машинная операция *, гдето ее резуль­татом оказывается новое число z из Rm. Проигнорировав воз­можность выхода за пределы допустимого диапазона (переполнение и антипереполнение), можно, используя соответствую­щее округление fl, представить z в виде

(9)

Таким же образом мы можем определить результат машинной операции над интервалами.

Определение 1. Пусть —интервальное округление. Тогда результат операции *, выполненной над А и В с применением ↕ есть

(10)

Теперь мы покажем, что основные свойства интервальной арифметики при использовании этого определения сохраняются.

Теорема 2. Для машинных интервальных операций, задаваемых определением 1, справедливо следующее утверждение:

(11)

Доказательство теоремы 2 следует непосредственно из свойства интервальных округлений (7).

Утверждение (11) отражает не что иное, как свойство мо­нотонности включения (9 п.7.1) применительно к машинным интер­вальным операциям.

Очередная теорема представляет интерес с точки зрения оценки погрешностей округлений.

Теорема 3. Пусть ↕ — интервальное округление, сводящееся с помощью (8) к направленным округлениям ↓ и ↑, и пусть Тогда

(12)

Если имеется округление fl, применение которого приводит к выполнению неравенства

то для х, у, z из Rm справедливо

(13)

Доказательство свойств (12) и (13) мы опускаем, поскольку оно элементарно и следует непосредственно из соответствующих определений.

Интервальное оценивание аналитического выражения функ­ции, проведенное с использованием операций из определения 1, дает интервалы, объемлющие значения оценивающей функции. Среди этих интервалов находятся и оценки множества значений функции. Более того, при выполнении подобных вычислений со­храняется свойство монотонности включения.

На практике машинные интервальные операции реализуются с помощью соответствующих программно-аппаратных средств Эти средства могут служить поддержкой языка программиро­вания высокого уровня. Один из вариантов реализации — набор подпро­грамм, написанных, скажем, на Алголе. Рассмотрим вкратце последнюю возможность. В большинстве случаев, в частности у Криста, такой набор содержит средство, с помощью ко­торого выполняется округление ↓. Это средство может быть, на­пример, оформлено в виде процедуры-функции LOW; через нее определяются стандартные операции интервальной арифме­тики — ADD, SUB, MUL и DIV, а также элементарные функции. На деталях реализации подобных подпрограмм мы остановимся в приложении В.