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

(2.92)

С целью упрощения формы записи полных структурных чисел будем применять операцию переноса нижних индексов в соответ­ствии со следующими правилами:

(2.93)

Определим обратную алгебраическую производную полного струк­турного числа.

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

по элементу α называется полное структурное числоопре-

деленное как

(2.94)

Это означает, что обратную производнуюсоставляют лишь

те столбцы числа A , которые не содержат элемента α.

Пример.

Очевидно, если то

(2.95)

Заметим, что для обратной производной суммы, произведения и частного полных структурных чисел справедливы следующие соотношения:

(2.96)

Легко доказать, что между действиями над структурными числами и действиями над полными структурными числами имеют место следующие соотношения:

(2.97)

Выражение называется дефектом суммы струк-

турных чисел А и В. Если

(если то пересечениезапишем в виде

),

т. е.

то говорим, что сумма чисел А и В не обладает дефектом суммы, т. е.

(2.98)

где

(2.99)

— столбцы произведения имеющие по крайней

мере два идентичных элемента

kі — число идентичных столбцов aі в произведении

Полное структурное число D в выражении (2.98) называется дефектом произведения структурных чисел А и В. Заметим, что

(2.100)

при условии

(2.101)

где k — натуральное число.

Если то произведение структурных чисел А и В не

обладает дефектом, т. е.

Легко заметить, что произведение структурных чисел А1,: A2, . . ., Ag блоков блок-графа не имеет дефекта, т. е.

(2.102)

так как эти числа не имеют общих элементов.

Модуль 7.

Введение в интервальную алгебру

Введение

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

Основная идея интервального анализа чрезвычайно проста. Вещественное число представляется в памяти ЭВМ не одним, а двумя машинными числами — оценкой снизу и оценкой сверху, образующими интервальное число. Арифметические операции над этими числами выполняются так, что если [а1, a2] = [b1, b2] ° [с1, с2], b [b1, b2], с [с1, с2], то b ° с1 [а1, a2], где ° {+, —, ×. /}. Таким образом, интервальный анализ дает возмож­ность автоматически учитывать погрешности в задании исход­ных данных и погрешности, вызываемые машинными округле­ниями. Это создает основу для аккуратного учета погрешностей, вызываемых используемым приближенным методом вычислений.

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

Такой пересмотр и делается в настоящей работе, которая базируется на книге Г. Алефельда, Ю. Херцберга «Введение в интервальые вычисления». При этом Г. Алефельд, Ю. Херцберг не ограничиваются только описанием различных алгоритмов, но и проводят их сравнение как по достигаемой точности, так и по вычислительной сложности. Большая часть излагаемого материала посвящена за­дачам линейной алгебры, что неудивительно ввиду той базис­ной роли, которую играет линейная алгебра в численных мето­дах. Вместе с тем вне рамок настоящей работы остались многие другие важные для приложений разделы математики, в которых интер­вальный анализ успешно применяется, например, обыкновенные дифференциальные уравнения.

Это объясняется, прежде всего, содержанием раздела математики, который рассматривается в настоящей книге, а именно, - «Дискретная математика. Алгебры »

Интервальный анализ вышел за рамки чисто теорети­ческого исследования и достаточно широко применяется на практике с помощью соответствующего программного обеспече­ния. В приложениях В и С приведены программы для интер­вальных вычислений на Алголе 60. За про­шедшее время, с одной стороны, появились реализации интервальной арифметики на более мощных языках. С другой стороны, был разработан стандарт ANSI/IEEE на машинное представление чисел и правила выполнения операций над ними. Этот стандарт реализован как программно, так и аппаратно в микропроцессорах. Это в значительной степени облегчает программную реализацию интер­вальных вычислений, которые становятся ненамного более мед­ленными, чем традиционные.

Следует обратить внимание на терминологию, ко­торая еще полностьюне устоялась ни в мире, ни на русском языке, что надо иметь в виду при чтении работ других авторов. На интервальные числа можно смотреть двояко: как на способ задания вещест­венных чисел, которые мы знаем лишь с некоторой погреш­ностью, и как на самостоятельные объекты Это различие почти нигде не ощущается, пожалуй, его единственное проявление — это определение равенства интервалов. При первом подходе равенство [а1, a2] = [b1, b2] выполняется тогда и только тогда, когда а1 =а2=b1= b2, при втором, принятом в этой книге, оно справедливо тогда и только тогда, когда а1 = b1 и а2 = b2.

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

Вещественная интервальная арифметика

7.1. Основные понятия и определения

В этом и последующих модулях поле вещественных чисел бу­дет обозначаться через, а строчные буквы а, b, с, ..., х, у, z будут использоваться для обозначения его элементов. Подмно­жество А множества , такое что

будет называться замкнутым вещественным интервалом, или просто интервалом, если это не сможет вызвать недоразумения. Впоследствии в некоторых случаях, чтобы избежать путаницы, мы будем обозначать границы интервала А через