Дж. Деммель - Вычислительная линейная алгебра, страница 5
Описание файла
PDF-файл из архива "Дж. Деммель - Вычислительная линейная алгебра", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
1ЕЕЕ-арифметика предусматривает также символы хоо и ХаХ (Ной а Ыишбег — НеЧисло). Символы хоо генерируются при переполнении и в дальнейшем ведут себя в соответствии со следующими арифметическими правилами: х/хсо = 0 для всякого числа с плавающей точкой х; х/О = хоо для всякого ненулевого числа с плавающей точкой х; +со + со = +оо, и т.д. Любая операция, результат которой, конечный или бесконечный, не определен корректно, генерирует символ Ха1ч. Примерами могут служить оо — со, —, о, ч/ — Т, 1ч'аХ О х, и т.п. В каждом из следующих случаев — арифметическая операция некорректна и порождает ХаХ; произошло переполнение; встретилось деление на нуль, вследствие чего генерируется хоо; получен машинный нуль,— выставляется индикатор особого случал (ехсерйоп Яая).
В дальнейшем состояние индикатора может быть проверено программой пользователя. Эти особенности арифметики позволяют разрабатывать более надежные программы (поскольку программа может обнаружить и исправить особые случаи вместо того, чтобы просто 1.5. Арифметика с плавающей точкой 3 э(3-3 ) порог порог машин- 3 НОГО НУЛЯ 33л О в эв .333 .134 переполнения 339 3 субнормвльнме нормализованные числа положительные числе нормализованные отрицательныечиола прекратить свое исполнение) и, вместе с тем, более быстрые (поскольку можно отказаться от «паранондального» стиля программирования с множеством тестов и ветвей, предназначенных для обхода возможных, хоть н маловероятных особых случаев).
Подходящие примеры можно найти в вопросе 1.19, комментариях, сопровождающих лемму 5.3, и в статье [81]. Наиболее дорогостоящей из известных ошибок, вызванных неправильной обработкой особого случая арифметики с плавающей точкой, является крушение ракеты Ариан 5 Европейского космического агентства, произошедшее 4 июня 1996 г. Подробности можно узнать по ттГЧГ%-адресу НОМЕ/аг)апе5гер.
ЬЬш1. Хотя почти все современные компьютеры используют 1ЕЕЕ-арнфметику или правильное округление, все же имеются исключения. Наиболее важными из ннх являются машины, производимые фирмой Сгау КевеагсЬГ. Однако будущие поколения компьютеров Сгау будут, вполне возможно, работать на основе 1ЕЕЕ-арифметикиз. Поскольку различия между значениями 11(а О Ь), вычисленными на компьютере Сгау и на 1ЕЕЕ-машине, обычно касаются лишь 14-го десятичного разряда нли и того меньше, читатель вправе спросить, так ли уж онн важ- 2 Мы включаем э эту линию машины типа 1ЧЕС ЯХ-4; эта машина имеет специальный режим, э котором ее арифметика совпадает с арифметикой компьютеров Сгэу. Мы исключаем иэ этой линии машины Сгэу ТЗВ и Стау ТЗЕ, представляющие собой параллельные компьютеры, собранные иэ процессоров ВЕС А1рЬа; арифметика последних почти не отличается от 1ЕЕЕ-арифметики (разве что машинные нули, лля достижения большей скорости, интерпретируются кэк точный нуль).
2 В 1996 г. фирма Сгэу ВеэеатсЬ была приобретена компанией зййсоп СтэрЬкэ. Рис. 1.2. Вещественная числовая прямая, на которой числа с плавающей точкой отмечены сплошными штрихами. Размер показанной области соответствует 1ЕЕЕ- арифметике обычной точности, однако для мантисс, в целях иллюстрации, принято 3-битовое представление. Таким образом, между двумя соседними степенями 2 содержится только 2 — 1 = 7 чисел с плавающей точкой, а не 2 — 1. Расстояние 2 22 между соседними штрихами остается постоянным между степенями 2 и увеличивается/уменьшается вдвое при переходе через такую степень.
Точечными штрихами указаны числа +2'22 и — 2'22; оба они на одну единицу последнего разряда больше (по абсолютной величине) Гюрога переполнения (т.е. наибольшего числа с плавающей точкой) 2'22 - (2 — 2 22). Рисунок симметричен относительно нуля; +О и -О различны как битовые строки 1ЕЕЕ-арифметики, но считаются численно равными. Деление на нуль является единственной операцией, которая дает разные результаты, а именно +оо и — со, для нулевых аргументов, снабженных различными знаками. Глава 1.
Введение ны. В самом деле, большинство алгоритмов вычислительной линейной алгебры нечувствительны к деталям способа округления. Однако оказывается, что некоторые алгоритмы проще реализуемы нли более надежны, если округление производится правильно. Вот два примера. Если на компьютере Сгау С90 вычесть единицу из ближайшего к ней меньшего числа с плавающей точкой, то будет получено значение — 2 «т, вдвое большее (по абсолютной величине) правильного значения — 2 4».
Между тем, для корректности алгоритма разделяй-и-властвуй существенно, чтобы даже очень малые разности вычислялись с высокой относительной точностью. Этот алгоритм в настоящее время является наиболее быстрым методом вычисления собственных значений и собственных векторов симметричной матрицы. Требуется весьма нетривиальная модификация алгоритма для того, чтобы обеспечить его корректность на машинах Сгау (см. разд. 5.3.3).
Ошибка на машине Сгау возможна и при вычислении функции агссоз(х/~/х~+ у~), поскольку вследствие чрезмерного округления аргумент арккосинуса может оказаться ббльшим 1. Это исключено в 1ЕЕЕ-арифметике (см. вопрос 1.17). Чтобы наш анализ погрешностей был пригоден для Сгау С90 и других компьютеров Сгау, мы можем заменить исходную модель моделью, описываемой уравнениями Я(а х Ь) = а(1 + 6») х Ь(1 + Ьз), Я(а * Ь) = (а * Ь)(1 + дз) и Я(а/Ь) = (а/Ь)(1+Бе), где )б;( < е, а е лишь небольшим множителем отличается от максимальной относительной ошибки представления. Вкратце можно сказать, что правильное округление и другие характеристики 1ЕЕЕ-арифметики предназначены для того, чтобы сохранить в силе как можно больше математических соотношений, используемых при выводе формул.
Конструировать алгоритмы проще, зная, что (за исключением переполнений и машинных нулей) величина Я(а — Ь) вычисляется с малой относительной ошибкой (в противном случае, может неправильно работать процедура разделяй-и-властвуй) и что — 1 < с»вЂ” а Я(х/~/х~ + уз) < 1 (иначе произойдет отказ при вычислении агссоз(с)). Имеется и ряд других математических соотношений, используемых (нередко неосознанно) при разработке алгоритмов.
По поводу дополнительных сведений об 1ЕЕЕ-арифметике и ее связях с численным анализом см. [159, 158, 81]. Учитывая существование различных арифметик с плавающей точкой, спрашивается, как же писать переносимые программы, зависящие от арифметики? Например, итерационные алгоритмы, которые мы рассматриваем в последних главах книги, часто включают в себя циклы типа следующего: повторить модифицировать значение е пока «е не станет пренебрежимо мало по сравнению с /» Здесь е > 0 есть некоторая мера ошибки, а / > 0 —. константа сравнения (пример можно найти в разд. 4.4.5). Под «пренебрежимой малостью» мы понимаем выполнение неравенства е < с е /, где с > 1 — умеренная константа, выбираемая из компромисса между требованиями точности и скорости сходимости. Поскольку в неравенство входит машинно-зависимая константа е, то в прошлом его проверка часто заменялась по видимости машинно-независимым тестом 1.5.
Арифметика с плавающей точкой 23 чверно ли, что в+ с( = с(?» Идея такого теста состоит в том, что если е < сгу или, возможно, е чуть меньше, чем требуется этим неравенством, то добавление е к с1 и последующее округление снова дают с(. Однако на некоторых компьютерах и при использовании некоторых трансляторов (см. по этому поводу следующий абзац) данный тест может потребовать от е гораздо большей малости, чем необходимо, или даже оказаться невыполнимым.
Поэтому наилучший тест все же использует в явным образом. Выясняется, что, проявляя достаточную осмотрительность, можно вычислить в машинно-независимым способом. Это делают, например, подпрограммы пакета ЬАРАСК в!агпсЬ (для обычной точности) и Й1ашсЬ (для двойной точности). Эти программы, кроме того, вычисляют или оценивают порог переполнения (без переполнения!), порог машинного нуля и другие параметры. В вопросе 1.19 обсуждается пример переносимой программы„которая использует эти машинные параметры явно. Иногда бывает нужна более высокая точность, чем та, которую обеспечивают 1ЕЕЕ-стандарты обычной и двойной точности.
Например, повышенная точность используется алгоритмом итерационного уточнения, методом, применяемым для улучшения точности вычисленного решения системы Ах = 6 (см. равд. 2.5.1). Поэтому в 1ЕЕЕ-арифметике определена еще одна, более высокая точность, называемая расширенной двойной. К примеру, все арифметические операции процессора 1псе1 Реп1шга (как и его предшественников, вплоть до 1п1е1 8086/8087) выполняются в регистрах расширенной двойной точности; эти регистры имеют длину 80 бит, из которых 64 используются для представления мантиссы и 15 для представления показателя. К сожалению, не все языки и трансляторы позволяют пользователю объявлять переменные расширенной двойной точности и оперировать с ними. На уровне архитектуры лишь немногие компьютеры имеют какие-либо иные возможности помимо расширенной двойной арифметики.
Однако существует несколько способов программного моделирования более точной арифметики. На машинах ПЕС Нах и ПЕС А!рЬа, 8пп Брагс и 1ВМ НЯ6000 некоторые трансляторы позволяют пользователю объявлять переменные учетверенной »пенности (нвзываемые также переменными дваоюди двойной точности или переменными типа геа!»16) и проводить вычисления с ними. Поскольку такая арифметика моделируется посредством меньшей разрядности, работать она может в несколько раз медленнее, чем арифметика двойной точности.
Обычная точность компьютеров Сгау эквивалентна, в смысле разрядности, 1ЕЕЕ-арифметике двойной точности, которая имеет примерно вдвое меньше разрядов, чем Сгау-арифметика двойной точности. Последняя моделируется программно и работает относительно медленно. Отметим еще, что существуют алгоритмы и пакеты для моделирования очень высокой разрядности; они могут использовать целочисленную арифметику (20, 21] или основную арифметику с плавающей точкой ]204, 218] (см.
по этому поводу вопрос 1.18). Наконец, упомянем интервальную арифметику как стиль вычислений, автоматически генерирующий гарантированные границы для ошибки. Каждая переменная в интервальном вычислении представляется парой чисел с плавающей точкой, из которых одно является нижней границей, а другое — верхней. В процессе вычислений округления производятся таким образом, чтобы гарантировать правильность пересчитываемых нижних и верхних границ.