Главная  Методы условной оптимизации 

[0] [1] [2] [ 3 ] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

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

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

регистр г- регистр R

±

Рис. 2с. Операнды машинного сложения и вычитания.

Регистр R нмеет спсцнатьный разряд переполнения, отмеченный на рис. 2с жирной точкой. Ои необходим иа случай появления (в результате сложения или вычитания мантисс) значащей цифры перед десятичной запятой. Если это произойдет, регистр R должен быть нормализован сдвигом вправо. Если же разряд перетюлнения ие понадобился и первые после десятичной запятой разряды получились нулевыми, для нормализации R нужен сдвиг влево.

Ошибка при сложении и вычисленнн появляется из-за того, что мантисса, записанная в регистр R, вообще говоря, будет содержать более, чем т, значащих цифр, и соответственно ее придется округлять. Кроме того, в некоторых машинах прн сдвиге г, вправо сохраняются не все разряды г, которые младше самого младшего разряда г,. В данном случае прн нормализации R сдвигом влево может возникнуть дополнительная потеря точности.

Вычисленный результат операции с плавающей запятой удовлетворяет соотношению

ft(a op Ь)=(а op Ь){1+ц).

Здесь а и Ь - два представнмых числа, ор - одна из операции «+», «-», «X» нли «-;-», а 1) - величина, зависящая от о, Ь, машинной точности к способа реализации в машине арнфметнкн с плавающей запятой.

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

2.1.5. ОШИБКИ КОЛШЕНСАЦИИ

Среди арифметических операций есть такие, которые могут приводить к появлению относительных ошибок, превышающих величину машинной точности во много раз. Это - вычисления разностей почти совпадающих округ.теиных чисел. Связанные с ними ошибки принято называть ошибками компенсации.

Рассмотрим два числа Xi и х, чьи представления в формате с плавающей запятой равны x,"Xt(\+ei) и Хг=Х2(1--Е8) соответствеино, а е„ Ej ограничены по модулю сверху относигельной машинной точностью. Точную разность х, и х, можно записать следующим образом;

Дх, {\+г,)~х, (1 -1-е.) = (Х.-Х,) (1 (2.3)

где величина ii будет относительным уклонением значения Ах от точного значения разности исходных чисел.

Если XiXj, мы говорим о полной компенсации. В противном случае из (2.3) получается выражение для i] вида

Соответственно для относительной ошибки приближения Дх справедлива такая оценка сверху:

I , 1 Е,х1-ег I 1 е, {Xi-x,)+Xi (е, - е.)

11=-гт:=й---Ы=\ ,„5,

Из (2.5) видно, что, когда модуль U,-Xsl мал по сравнению с Ixil (т. е. число xi «примерно равно» х,), относительная ошибка в Ах может быть много больше машинной точности г. Прн этом она окажется большой не из-за того, что вычитание х, нз х, выполнено не точно (ведь Дх есть точная разность между х, и xj, а потому, что сами величины .v, и Ха получены округлением xj, Ха и включают соответствующие ошибки; заметим, что если е, и е, равны нулю, то \\ также будет нулем. Когда Xi н х взаимно близки, нх старшие разряды во время вычитания взаимно уничтожаются, и потому младшие разряды, отброшенные прн округлении х, и Хг до х, и Xj. приобретают вес. Таким образом, компенсация в данном случае «вскрывает предыдущие огрехи». Если же х, и Xs существенно различны, оценка сверху для ошибки компенсации при вычитании оказывается величиной того же порядка, что и оценки ошибок других операций с плавающей запятой, т. е. здесь она никакого особого значения иметь не будет.

В качестве примера рассмотрим вычисление разности величин

Xi= .2946796847, х.= .2946782596 (2.6)



иа машине, в которой мантисса представления числа с плавающей запятой содержит шесть десятичных цифр (Ej,=IO-). При корректном округлении значения xt и х, будут равны .294680 и .294678 соответственно, и их разность (вычисленная без ошибки) равна .2х x 10"». В то же время разность между точньши значениями Xi к х, равна .14251x 10"", откуда следует, что Ах имеет относительную ошибку компенсации г) =.40341. Из (2.5) видно, что верхняя граница относительной ошибки компенсации снижается при уменьшении Е,и; если вычитание х, из Xi выполнить на машине с восьмиразрядной мантиссой, то относительная ошибка компенсации будет равна .357x10-».

Не зная точных значений Xi, х, н не имея возможности делать точных арифметических вычислений, истинного значения ошибки (2.4) не определить. Поэтому приходится пользоваться прикндоч-ными значениями, которые получаются оцениванием правой части неравенства (2.5). Их мы и будем называть ошибками компенсации, причем речь, разумеется, идет о вычислимых оценках. Методы расчета таких оценок обсуждаются в гл. 8.

2.1.6. ТОЧНОСТЬ ПРИ ПОСЛЕДОВАТЕЛЬНЫХ ВЫЧИСЛЕНИЯХ

В данном разделе вводится терминология, используемая при анализе точности величин, получающихся в результате длинных цепочек вычислений с привлечением других расчетных или тпме-ряемых значений.

Обозначим через / точное значение искомой величины; это - значение, которое было бы получено, если бы все промежуточные вычисления выполнялись точно и с точными значениями всех привлекаемых данных. Пусть далее fHf) - реальный конечный результат вычислений. Тогда, если

то 1а в соответствии с приведенным ранее определением (см. разд. 2.1.1) есть абсолютная ошибка приближения (/). Мы будем использовать термин абсолютная точность (или уровень шума) для обозначения положительного числа £д, которое является верхней границей для абсолютной ошибки, т. е. оЮа. При ненулевом зиа-ченин / качество приближения ЦЦ) иногда удается выразить в терминах относительной точности, так как погрешности расчетов в рамках арифметики с плавающей запятой н в обычных методах вычисления стандартных функций изначально проявляются именно как относнтельные.Так, например, для большинства машин расчетное значение \/х будет содержать ошибку, не превосходящую единицы в младшем разряде мантиссы его представлеикя в формате с плавающей запятой. Введя относительную ошибку, мы можем записать (/) в виде

(/)=/(Ц-6).

При этом относительной точностью будем называть положительное число Ев, для которого 6Кен.

Связь между ошибками 6 и о очевидна н выражается равенством 6/1 = 1а1. Оно выполнено iro определению, т. е. справедливо вне зависимости от того, что представляет собой величина /. К сожалению, сказать то же самое о вычислимых границах Ед, е„ нельзя. Правда, абсолютная и относительная точности нередко удовлетворяют соотношению ед~еи1/. Если / - стандартная функция, то обычно енЕм и ё.1=е„/, но в общем случае связь между ё„ и Ед оказывается значительно более сложной, особенно прн малых /.

2.1.7. АН.1ЛИЗ ОШИБОК ДЛЯ АЛГОРИТМОВ

Когда какая-то вычислительная задача решается на ЭВМ, результат представляет собой набор представимых чисел, как правило, генерируемых последовательностью операций в арифметике с плавающей запятой. Эти операции связаны с ошибками, и потому ответ будет приближенным даже в том случае, если используемый алгоритм теоретически является точным. Разные алгоритмы реагируют на условность машинной арифметики по-разному, и в данном разделе мы рассмотрим вопрос о том, как можно классифицировать нх по отношению к этой реакции.

В идеале всегда хочется иметь гарантию «близости» численного решения к точному, т. е. располагать удовлетворительной оценкой вида

Us-si К 6,

(2.Л

где S - точное решение, s - численное, II -11 - разумная мера уклонения. Исходя нз этого, хорошим следовало бы считать такой алгоритм, который всегда обеспечивает соблюдение неравенства (2.7) с достаточно малым 6. Однако при данном подходе к оценке качества алгоритмов, именуемом прямым анализом ошибок, большинство из них пришлось бы признать плохими.

Дело в том. что многим задачам присуще свойство плохой обус-AOR.wHHOcmu. Это - внутреннее свойство, и определяется оно вне какой-либо привязки к дефектам машинной арифметики. Плохо обусловленная задача характерна тем, что малое возмущение ее параметров может привести к большому возмущению точного решения (соответствующие примеры даны в разд. 2.2.4). В силу этого обстоятельства прямой анализ ошибок для таких задач всегда дает пессимистичные оценки.

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



Гл. 2. Основы

шение, которое будет сильно отличаться от настоящего. Соответственно величина 6 в (2.7) с необходимостью окажется большой, т. е. с точки зрения прямого анализа ошибок этот алгоритм плох.

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

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

2.2. Введение в вычислите.1ьную линейную алгебру

(2.8)

где Д зависит от машинной точности и от задачи Р.

В отличке от прямого анализа ошибок обратный анализ показывает, что для большинства общепризнанных алгоритмов величина Д «мала» независимо от Р. Такне алгоритмы принято называть численно устойчивыми, так как ошибки выполняемых в соответствии с ними вычислений приводят к небольшому уклонению от исходной задачи. Заметим, кстати, что Д может быть ненулевой уже в силу необходимости аппроксимации изначальных данных задачи предста-внмыми числами.

Замечания и избранная библиография к разделу 2.1

Впервые роль ошибок округления в алгебраических процедурах была проанализирована Уилкнисоном (1963). Тому, кто хочет поподробнее ознакомиться со способами реализации арифметики с плавающей запятой иа современных машинах, рекомендуем работу Кахана (1973). Хорошим универсальным пособием по численному анализу является книга Дальквиста и Бьёрка (1974).

2.2. ВВЕДЕНИЕ В ВЫЧИСЛИТЕЛЬНУЮ ЛИНЕЙНУЮ АЛГЕБРУ

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

2.2.1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

2.2.1.1. Скаляры. Одиночные количественные характеристики и результаты измерений обычно формализуются понятием «скаляр» или «вещественное число». Вещественные числа обладают мно-

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

Впредь скаляры, как правило, будут обозначаться малыми греческими буквами: а, р. 6 и т. д.

2.2.1.2. Векторы. Фор-мально вектор может быть определен как упорядоченный набор скашров, причем и значения чисел в этом наборе, и их порядок существенны. Подобно тому как вещественное число служит мерой отдельного свойства какого-либо объекта (скажем, высоты стола), векторы используются для описания упорядоченных совокупностей свойств. Предположим, к примеру, что высота стола рассматривается как его первая характеристика, длина - как вторая, а ширина - как третья. Тогда стол, имеющий 3 фута высоты, 3-5 фута длины и 2 фута ширины, может быть описан вектором

/3.0N

стол =

3.5 2.0

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

Количество скалярных числовых величин, образующих вектор, называют размерностью вектора, а сами числа - его компонентами. Последние, как правило, нумеруются индексом, пробегающим значения от 1 до п, где п - размерность вектора.

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

Два вектора считаются одинаковыми, если их соответственные компоненты равны. Это определение предполагает, что проверяемые на совпадение векторы имеют одинаковую размерность.

Иногда удобно использовать представления вектора как строки, т. е. горизонтального списка чисел. Если вектор-столбец х задан в виде



[0] [1] [2] [ 3 ] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.001