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

[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]

Единственный способ противостоять природе - основательно познать ее.

Джон Локк (1693)

2.1. ВВЕДЕНИЕ В ТЕОРИЮ ОШИБОК ВЫЧИСЛЕНИЙ

2.1.1. ИЗМЕРЕНИЕ ОШИБКИ

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

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

Принимая во внимание только абсолютную ошибку, далеко ие всегда можно правильно оценить качество приближения. Например, если х=2 и х=1, абсолютная ошибка равна 1, н в данном случае ее, по-видимому, следует считать «большой», так как приведенные значения вряд ли можно назвать близкими. Однако, если д:=10", а i=10"-t-l, ту же - единичную - абсолютную ошибку мы скорее всего сочтем «малой» и решим так потому, что разность между хи х мала по сравнению с х. Эти рассуждения приводят к понятию от«о-сительной ошибки, которая определена как

\х\

если X отличается от нуля, и не определена в противном случае; таким образом, при вычислении относительной ошибки учитывается модуль точного значения величины. В приведенных примерах относительные ошибки равны 0.5 и 10"" соответственно, так что вторая из них действительно «мала».

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

жения величиной

-1+RT

которая объединяет в себе черты абсолютной и относительной ошибок. Она близка к первой при UI<1 и мало отличается от второй при \xi\.

2.1.2, ПРЕДСТАВЛЕНИЕ ЧИСЛА В МАШИНЕ

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

Общепринятый способ записи числовой информации состоит в представлении ее упорядоченной последовательностью цифр. Этот принцип используется и в известной всем десятичной системе счисления. Мы изображаем вещественное число цепочкой символов, которая начинается со знака плюса или минуса п продолжается списком цифр из набора О, 1.....9, возможно разделенных на две

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

В точности на тех же идеях строятся и способы записи чисел в ЭВМ. При этом электронные устройства памяти можно представ-.чять себе как цепочки элементов, у каждого из которых есть только два состояния - «включен» и «выключен». Эти состояния интерпретируются как значения двоичного числа, которое может быть либо нулем, либо единицей и за которым закрепилось название «бит». А коль скоро всякая информация превращается в ЭВМ в цепочки битов, то и основания машинных систем счисления обычно бывают степенями числа 2; три наиболее распространенных основания - 2 (бинарная арифметика), 8 (восьмеричная арифметика с цифрами О, 1, . . ., 7) и 16 (шестнадцатеричная арифметика с цифрами О, 1 , 9, А, . . ., F).

Обычно для хранения одного числа в памяти машины выделяется поле, достаточное для записи фиксированного количества цифр. Его принято называть слоаол. Интерпретация цифр в пределах слова определяется специальными правилами - форматами записи. Два из них мы сейчас рассмотрим.

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

ОСНОВЫ



разрядов, выделяемых для хранения целой и дробной частей числа. Если, например, под запись целых чисел отводятся слова с четырьмя десятичными разрядами, то целые от О до 9999 будут представлены в машине фактически так же, как они обычно записываются. Разница лишь в том. что в машинном представлении нули в старших разрядах не отбрасываются (т. е. число 20 будет представлено цепочкой 0020).

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

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

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

х=пф.

(2.1)

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

1/р<т<1.

Поскольку порядок е по определению есть целое со знаком, его естественно хранить в каком-нибудь подходящем формате с фиксированной запятой. Что же касается мантиссы, то для представления ее знака выделяют специальный бит, а модуль мантиссы хранят •в виде строки из г цифр т,, mj. Шг, . .., т, где 0<т,<Р-1. которая интерпретируется как запись дроби

p-(m,P--l-m,P-+...+mO.

Если мантисса т нормализована, в этой записи njiO. В нормализованном представлении максимум величины т равен 1-р~, что соответствует т=р-I, 1=1, ... , т; минимальное значение jmi равно р- и получается при mi=l, ma=...=m,=0.

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

Рассмотрим теперь два примера, иллюстрирующие сказанное. Начнем с гипотетической машины, которая оперирует десятичной арифметикой и нмеет 8-разрядные слова, причем эти разряды используются следующим образом; левый («первый») разряд отведен под запись знака мантиссы т; следующие два разряда содержат порядок со смещением на 50, так что диапазоном его значений будут числа от -50 до наконец, в последних пяти разрядах хранится модуль нормализованной мантиссы. В этой машине число I-.12345X X 10~з будет записано так, как показано на рис. 2а.

I » I г I

IW/fllJvK

Рнс. 2а. Десятичное слово с записью числа -0.12345X10-.

Более сложный пример взят из жизни и относится к машинам серии IBM 360/370 с шестнадцатернчной арифметикой. Для записи чисел ординарной точности в представлении с плавающей запятой в этих машинах отаодягся слова, состоящий из 32 битов, группируемых в четыре в-битовых байта или в восемь шестиадцатеричных разрядов. Первый бит слова содержит знак мантиссы (О означает плюс, 1 - минус). Следующие семь битов (остаток первого байта) содержат порядок со смещением иа 64. Б байтах со второго по четвертый хранится модуль нормализованной мантиссы.

1 в

" 1

смещенный трядон

глантиссл

Рис. 2Ь. Шестнадцатеричное слово с записью числа -42/4096.

Рассмотрим представление числа -42/4096=-16-(2/16+ -1-10/256). Истинный порядок в данном случае равен -1, а его смещенным значением будет 63. Модуль нормализованной мантиссы равен .2А (основание 16). Таким образом, запись числа в машине будет выглядеть так, как показано на рис. 2Ь.

2.1.3. ОШИБКИ ОКРУГЛЕНИЯ

Множества чисел, которые можно записать словом заданной длины в форматах с фиксированной и плавающей запятой, конечны. Если слово некоторой машины содержит т разрядов по основа-



нию р, ТО в ней можно оперировать не более чем (3 различными числами. Эти чисел формируют так называемое представимое множество машины. Все иные, не попавшие в это множество числа не могут быть представлены в ней точно, и запись любого из них в память будет сопровождаться некоторой ошибкой. Такие ошибки обыч-1Ю называют ошибками округления или ошибками представ.гения.

Некоторые числа непредставимы в машине стандартным способом из-за того, что нх величины лежат за границами диапазона значений, которые можно хранить в машинном слове. Эти границы определяются следующим образом. Если «•„ах есть максимальный разрешенный порядок, то значение максимального модуля числа, представкмого в формате с плавающей запятой, равно /=рта« (1 - -Р"). Если г„,„ есть минимальный разрешенный порядок, то наименьший модуль числа, представимого в нормализованном виде, равен A=p*"in~*. Попытка записать число, по модулю превосходящее К, приведет к переполнению, а число, по модулю меньшее, чем к,- к антипереполнению.

Помимо рассмотренных есть и другие числа, которые нельзя представить в машине (без ошибки) обычным путем. Это - числа, имеющие в представлении (2.1) мантиссу с более чем т значащими цифрами. Например, число л=3.14159... не может быть представлено точно никаким конечным набором цнфр. Заметим, что, кроме всего прочего, возможность представления конкретного числа определяется и тем, каково основание р. Так, число 1/10 представимо в одноразрядной десятичной арифметике н не представимо никаким конечным набором цнфр в арифметиках с основаниями 2, 8 н 16.

Коль скоро задано непредставимое в формате с плавающей запятой число х, которое тем не менее не приводит нн к переполнению, ни к антнпереполнеиию, возникает вопрос о выборе представимого числа X, аппроксимирующего х наилучшим образом; прн этом X обычно обозначают через 11{х). Поскольку х заведомо лежит между двумя представимыми числами, минимизация ошибки округления в данном случае сводится к выбору в качестве х ближайшего представкмого «соседа» числа х. Этот выбор, если он единствен, определяется следующим правилом: оставьте /л, без изменения, если модуль отбрасываемой части мантиссь! составляет менее половины значения единицы в последнем сохраняемом разряде (т. е. менее "аР"), а в противном случае добавьте единицу к т, (и, если потребуется, заново нормализуйте мантиссу). Прн такой схеме округления в машине с десятичной арифметикой и шестнразрядной мантиссой числа 3.14159265... и -20.98999 будут преобразованы в 3.14159 и -20.9900 соответственно.

Теперь осталось определить, как будет округляться непредставимое число, лежащее в точности посередине между двумя представимыми. Есть несколько способов автоматически разрешить данную неоднозначность. Например, часто используется правило

округления до ближайшего четного. В соответствии с ним непредставимое число округляется до того из ближайших представимых. чей последний разряд четен. При этом числа .98435 п .98445 будут округлены в десятичной машине с четырехразрядной арифметикой до одного и того же числа .9844.

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

m-m<4P--

а так как относительная ошибка приближения х в рассматриваемом случае равна

1-х\ \m-m\ \х\ ]т] •

нз предыдущего неравенства видно, что величину этой ошибки можно оценить по формуле

(2.2)

Здесь учтено, что 1/р<т<1. Фигурирующее в полученной оценке (2.2) число Р играет в анализе погрешностей вычислений с плавающей запятой важную роль. Его принято называть относительней точностью машины (или просто машинной точностью). Впредь в этой книге оно будет обозначаться через е,,-

В некоторых машинах для приближения непредставимых чисел используются к другие схемы округления, например правило усечения, в соответствии с которым все цифры мантиссы m после младшей сохраняемой просто отбрасываются независимо от нх «номиналов». Тогда в десятичной машине с четырехразрядно!"! арифметикой все числа между .98340 и .983499...9 будут округлены до .9834. При этом относительную ошибку можно оценить аналогичной (2.2) формулой вида

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

2.1.4. ОШИБКИ ПРИ ВЫПОЛНЕНИИ АРИФМЕТИЧРХКИХ ОПЕРАЦИЯ

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



[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.0015