Ошибки округления , [1] также называется ошибка округления , [2] представляют собой разность между результатом полученного по заданному алгоритму с использованием точного арифметическим и результат получает тем же самый алгоритм с использованием конечной точности, округленная арифметики. [3] Ошибки округления возникают из-за неточности в представлении действительных чисел и выполняемых с ними арифметических операций. Это форма ошибки квантования . [4] При использовании приближенных уравнений или алгоритмов, особенно при использовании конечного числа цифр для представления действительных чисел (которые теоретически имеют бесконечное количество цифр), одна из целейчисленный анализ предназначен для оценки ошибок вычислений. [5] Ошибки вычислений, также называемые числовыми ошибками , включают как ошибки усечения, так и ошибки округления.
Когда выполняется последовательность вычислений с входом, включающим любую ошибку округления, ошибки могут накапливаться, иногда доминируя в вычислении. В плохо подготовленных задачах может накапливаться значительная ошибка. [6]
Короче говоря, есть два основных аспекта ошибок округления, связанных с численными расчетами: [7]
- Цифровые компьютеры имеют ограничения по величине и точности их способности представлять числа.
- Некоторые численные операции очень чувствительны к ошибкам округления. Это может быть связано как с математическими соображениями, так и с тем, как компьютеры выполняют арифметические операции.
Ошибка представления
Ошибка, возникающая при попытке представить число с помощью конечной строки цифр, является формой ошибки округления, называемой ошибкой представления . [8] Вот несколько примеров ошибок представления в десятичных представлениях:
Обозначение | Представление | Приближение | Ошибка |
---|---|---|---|
1/7 | 0. 142 857 | 0,142 857 | 0,000 000 142 857 |
пер. 2 | 0,693 147 180 559 945 309 41 ... | 0,693 147 | 0,000 000 180 559 945 309 41 ... |
журнал 10 2 | 0,301 029 995 663 981 195 21 ... | 0,3010 | 0,000 029 995 663 981 195 21 ... |
3 √ 2 | 1,259 921 049 894 873 164 76 ... | 1,25992 | 0,000 001 049 894 873 164 76 ... |
√ 2 | 1,414 213 562 373 095 048 80 ... | 1,41421 | 0,000 003 562 373 095 048 80 ... |
е | 2,718 281 828 459 045 235 36 ... | 2,718 281 828 459 045 | 0,000 000 000 000 000 235 36 ... |
π | 3,141 592 653 589 793 238 46 ... | 3,141 592 653 589 793 | 0,000 000 000 000 000 238 46 ... |
Увеличение числа цифр, разрешенных в представлении, снижает величину возможных ошибок округления, но любое представление, ограниченное конечным числом цифр, все равно вызовет некоторую степень ошибки округления для несчетного количества действительных чисел. Дополнительные цифры, используемые на промежуточных этапах вычислений, называются защитными цифрами . [9]
Многократное округление может привести к накоплению ошибок. [10] Например, если 9,945309 округляется до двух десятичных знаков (9,95), а затем снова округляется до одного десятичного знака (10,0), общая ошибка составляет 0,054691. Округление 9,945309 до одного десятичного знака (9,9) за один шаг приводит к меньшей ошибке (0,045309). Обычно это происходит при выполнении арифметических операций (см. « Потеря значимости» ).
Система счисления с плавающей запятой
По сравнению с системой счисления с фиксированной запятой, система счисления с плавающей запятой более эффективна при представлении действительных чисел, поэтому она широко используется в современных компьютерах. Пока реальные цифры бесконечны и непрерывны, система счисления с плавающей запятой конечно и дискретно. Таким образом, ошибка представления, которая приводит к ошибке округления, возникает в системе счисления с плавающей запятой.
Обозначение системы счисления с плавающей запятой
Система счисления с плавающей запятой характеризуется целые числа:
- : основание или основание
- : точность
- : диапазон экспоненты, где это нижняя граница и это верхняя граница
- Любой имеет следующий вид:
- где целое число такое, что для , а также целое число такое, что .
Нормализованная система с плавающей запятой
- Система счисления с плавающей запятой нормализуется, если первая цифра всегда отличен от нуля, если число не равно нулю. [3] Поскольку мантиссамантисса ненулевого числа в нормированной системе удовлетворяет . Таким образом, нормализованная форма ненулевого числа с плавающей запятой IEEE : где . В двоичном формате первая цифра всегдапоэтому он не записывается и называется неявным битом. Это дает дополнительный бит точности, так что ошибка округления, вызванная ошибкой представления, уменьшается.
- Поскольку система счисления с плавающей запятой является конечным и дискретным, он не может представлять все действительные числа, что означает, что бесконечные действительные числа могут быть аппроксимированы только некоторыми конечными числами с помощью правил округления . Приближение заданного действительного числа с плавающей запятой от можно обозначить.
- Общее количество нормализованных чисел с плавающей запятой равно
- , где
- считает выбор знака, положительный или отрицательный
- считает выбор первой цифры
- считает оставшуюся мантиссу
- считает выбор показателей
- считает тот случай, когда число .
- , где
Стандарт IEEE
В стандарте IEEE база двоичная, т.е., и используется нормализация. Стандарт IEEE хранит знак, показатель степени и мантиссу в отдельных полях слова с плавающей запятой, каждое из которых имеет фиксированную ширину (количество бит). Два наиболее часто используемых уровня точности для чисел с плавающей запятой - это одинарная точность и двойная точность.
Точность | Знак (биты) | Экспонента (биты) | Мантисса (биты) |
---|---|---|---|
Одинокий | 1 | 8 | 23 |
Двойной | 1 | 11 | 52 |
Машина эпсилон
Машинный эпсилон может использоваться для измерения уровня ошибки округления в системе счисления с плавающей запятой. Вот два разных определения. [3]
- Машинный эпсилон, обозначаемый , - максимально возможная абсолютная относительная ошибка представления ненулевого действительного числа в системе счисления с плавающей запятой.
- Машинный эпсилон, обозначаемый , это наименьшее число такой, что . Таким образом, в любое время .
Ошибка округления при разных правилах округления
Существует два распространенных правила округления: округление за отрезком и округление до ближайшего. Стандарт IEEE использует округление до ближайшего.
- По очереди : Основание- расширение усекается после цифра.
- Это правило округления смещено, потому что оно всегда приближает результат к нулю.
- Округление до ближайшего : устанавливается равным ближайшему числу с плавающей запятой к . При равенстве используется число с плавающей запятой, последняя сохраненная цифра которого четная.
- Для стандарта IEEE, где базовый является , это означает, что когда есть ничья, она округляется так, чтобы последняя цифра была равна .
- Это правило округления более точное, но более затратное с точки зрения вычислений.
- Округление таким образом, чтобы последняя сохраненная цифра была даже при равенстве, гарантирует, что она не округляется систематически в большую или меньшую сторону. Это сделано для того, чтобы избежать возможности нежелательного медленного отклонения в длинных вычислениях просто из-за смещения округления.
- В следующем примере показан уровень ошибки округления в соответствии с двумя правилами округления. [3] Правило округления, округление до ближайшего, в целом приводит к меньшей ошибке округления.
Икс | По очереди | Ошибка округления | Округление до ближайшего | Ошибка округления |
---|---|---|---|---|
1,649 | 1.6 | 0,049 | 1.6 | 0,049 |
1,650 | 1.6 | 0,050 | 1,7 | 0,050 |
1,651 | 1.6 | 0,051 | 1,7 | -0,049 |
1,699 | 1.6 | 0,099 | 1,7 | -0,001 |
1,749 | 1,7 | 0,049 | 1,7 | 0,049 |
1,750 | 1,7 | 0,050 | 1,8 | -0,050 |
Расчет ошибки округления в стандарте IEEE
Предположим, что используется округление до ближайшего и двойная точность IEEE.
- Пример: десятичное число может быть преобразован в
Поскольку бит справа от двоичной точки - это и за ним следуют другие ненулевые биты, правило округления до ближайшего требует округления, то есть добавления немного к немного. Таким образом, нормализованное представление с плавающей запятой в стандарте IEEE является
- .
- Теперь ошибку округления можно вычислить при представлении с участием .
Это представление получается путем отбрасывания бесконечного хвоста
из правого хвоста, а затем добавил на этапе округления.
- потом .
- Таким образом, ошибка округления равна .
Измерение ошибки округления с помощью машинного эпсилон
Машина эпсилон может использоваться для измерения уровня ошибки округления при использовании двух вышеупомянутых правил округления. Ниже приведены формулы и соответствующие доказательства. [3] Здесь используется первое определение машинного эпсилон.
Теорема
- По очереди:
- Округление до ближайшего:
Доказательство
Позволять где , и разреши быть представлением с плавающей запятой . Поскольку используется последовательное нарезание,* Чтобы определить максимум этой величины, необходимо найти максимум числителя и минимум знаменателя. С (нормализованная система), минимальное значение знаменателя равно . Числитель ограничен сверху величиной. Таким образом,. Следовательно,для порезки. Доказательство для округления до ближайшего аналогично.
- Обратите внимание, что первое определение машинного эпсилон не совсем эквивалентно второму определению при использовании правила округления до ближайшего, но оно эквивалентно для последовательного перехода.
Ошибка округления, вызванная арифметикой с плавающей запятой
Даже если некоторые числа могут быть представлены точно числами с плавающей запятой и такие числа называются машинными числами , выполнение арифметических операций с плавающей запятой может привести к ошибке округления в окончательном результате.
Добавление
Машинное сложение состоит из выравнивания десятичных знаков двух добавляемых чисел, их сложения и последующего сохранения результата как числа с плавающей запятой. Само сложение может быть выполнено с более высокой точностью, но результат должен быть округлен до указанной точности, что может привести к ошибке округления. [3]
Например, добавив к в IEEE двойной точности следующим образом:
- Это сохранено как поскольку в стандарте IEEE используется округление до ближайшего. Следовательно, равно в IEEE двойной точности и ошибка округления .
Из этого примера видно, что при сложении большого числа и малого числа может возникнуть ошибка округления, поскольку сдвиг десятичных знаков в мантиссах для согласования показателей степени может вызвать потерю некоторых цифр.
Умножение
В общем, продукт -цифровые мантиссы содержат до цифр, поэтому результат может не соответствовать мантиссе. [3] Таким образом, в результат будет включена ошибка округления.
- Например, рассмотрим нормализованную систему счисления с плавающей запятой с основанием и цифры мантиссы не более . потом а также . Обратите внимание, что но так как там самое большее цифры мантиссы. Ошибка округления будет.
Разделение
В общем, частное -цифровые мантиссы могут содержать более -цифры. [3] Таким образом, в результат будет включена ошибка округления.
- Например, если приведенная выше нормализованная система счисления с плавающей запятой все еще используется, то но . Итак, хвост отрезан.
Субтрактивная отмена
Вычитание двух почти равных чисел называется вычитанием . [3]
- Когда начальные цифры отменяются, результат может быть слишком маленьким для точного представления, и он будет представлен просто как .
- Например, пусть и здесь используется второе определение машинного эпсилон. Какое решение?
Известно, что а также почти равные числа, и . Однако в системе счисления с плавающей запятой. Хотя достаточно большой, чтобы быть представленным, оба экземпляра были округлены, давая .
- Например, пусть и здесь используется второе определение машинного эпсилон. Какое решение?
- Даже с несколько большим , в типичных случаях результат по-прежнему существенно ненадежен. Нет особой веры в точность значения, потому что наибольшая неопределенность в любом числе с плавающей запятой - это цифры в крайнем правом углу.
- Например, . Результат ясно представима, но в это мало веры.
Накопление ошибки округления
Ошибки могут увеличиваться или накапливаться, когда последовательность вычислений применяется к начальному входу с ошибкой округления из-за неточного представления.
Нестабильные алгоритмы
Алгоритм или численный процесс называется стабильным, если небольшие изменения на входе вызывают только небольшие изменения на выходе, и называется нестабильным, если производятся большие изменения на выходе. [11]
Последовательность вычислений обычно происходит при запуске какого-либо алгоритма. Количество ошибок в результате зависит от стабильности алгоритма . Ошибка округления будет увеличиваться нестабильными алгоритмами.
Например, для с участием дано. Легко показать, что. Предполагать это наше начальное значение и имеет небольшую ошибку представления , что означает, что начальный вход в этот алгоритм вместо . Затем алгоритм выполняет следующую последовательность вычислений.
Ошибка округления увеличивается в последующих вычислениях, поэтому этот алгоритм нестабилен.
Плохо обусловленные проблемы
Даже если используется стабильный алгоритм, решение проблемы может быть неточным из-за накопления ошибок округления, когда сама проблема плохо обусловлена .
Число обусловленности проблемы - это отношение относительного изменения решения к относительному изменению входных данных. [3] Проблема хорошо обусловлена, если небольшие относительные изменения входных данных приводят к небольшим относительным изменениям в решении. В противном случае проблема плохо обусловлена . [3] Другими словами, проблема является плохо обусловленной, если ее число условий «намного больше», чем.
Число обусловленности вводится как мера ошибок округления, которые могут возникнуть при решении плохо обусловленных задач. [7]
Например, полиномы более высокого порядка имеют тенденцию быть очень плохо обусловленными , то есть они имеют тенденцию быть очень чувствительными к ошибке округления. [7]
В 1901 году Карл Рунге опубликовал исследование об опасностях полиномиальной интерполяции высокого порядка. Он посмотрел на следующую простую на вид функцию:
которая теперь называется функцией Рунге . Он взял равноудаленные точки данных из этой функции на интервале. Затем он использовал интерполяционные полиномы возрастающего порядка и обнаружил, что по мере того, как он брал больше точек, полиномы и исходная кривая значительно отличались, как показано на Рисунке «Сравнение1» и Рисунке «Сравнение 2». Дальше ситуация сильно ухудшилась по мере увеличения приказа. Как показано на Рисунке «Сравнение 2», посадка стала еще хуже, особенно на концах интервала.
Нажмите на рисунки, чтобы увидеть полное описание.
Пример из реального мира: отказ ракеты Patriot из-за увеличения ошибки округления
25 февраля 1991 года, во время войны в Персидском заливе, американская ракетная батарея Patriot в Дхаране, Саудовская Аравия, не смогла перехватить приближающуюся иракскую ракету Scud. Скад врезался в казармы американской армии и убил 28 солдат. В отчете Главного бухгалтерского управления, озаглавленном «Противоракетная оборона Patriot: программная проблема, приведшая к отказу системы в Дахране, Саудовская Аравия», сообщается о причине сбоя: неточный расчет времени с момента загрузки из-за компьютерных арифметических ошибок. В частности, время в десятых долях секунды, измеренное внутренними часами системы, было умножено на 10, чтобы получить время в секундах. Этот расчет был выполнен с использованием 24-битного регистра с фиксированной запятой. В частности, значение 1/10, которое имеет неограниченное двоичное расширение, было прервано на 24 бита после точки счисления. Небольшая ошибка прерывания, умноженная на большое число, дающее время в десятых долях секунды, привела к значительной ошибке. Действительно, батарея Patriot проработала около 100 часов, и простой расчет показывает, что результирующая временная ошибка из-за увеличенной ошибки прерывания составила около 0,34 секунды. (Число 1/10 равно. Другими словами, двоичное разложение 1/10 равно. Теперь 24-битный регистр в Патриоте хранится вместо вводя ошибку двоичный, или около десятичный. Умножая на количество десятых долей секунды в часов дает ). Скад едет примерно1676 метров в секунду, то есть за это время проходит более полукилометра. Этого было достаточно, чтобы приближающийся Скад находился за пределами «ворот дальности», которые отслеживал Патриот. По иронии судьбы, тот факт, что вычисление плохого времени было улучшено в некоторых частях кода, но не во всех, способствовал возникновению проблемы, поскольку это означало, что неточности не отменялись. [12]
Смотрите также
- Точность (арифметика)
- Усечение
- Округление
- Потеря значимости
- Плавающая запятая
- Алгоритм суммирования Кахана
- Машина эпсилон
- Полином Уилкинсона
Рекомендации
- ↑ Butt, Rizwan (2009), Введение в численный анализ с использованием MATLAB , Jones & Bartlett Learning, стр. 11–18, ISBN 978-0-76377376-2
- ^ Уеберхубер, Кристоф В. (1997), Численные вычисления 1: методы, программное обеспечение и анализ , Springer, стр. 139–146, ISBN. 978-3-54062058-7
- ^ Б с д е е г ч я J K Форрестер, Дик (2018). Math / Comp241 Численные методы (конспекты лекций) . Колледж Дикинсона .
- ^ Аксой, Пелин; ДеНардис, Лаура (2007), Информационные технологии в теории , Cengage Learning, стр. 134, ISBN 978-1-42390140-2
- ^ Ральстон, Энтони; Рабиновиц, Филип (2012), Первый курс численного анализа , Dover Books on Mathematics (2-е изд.), Courier Dover Publications, стр. 2–4, ISBN 978-0-48614029-2
- ^ Чапман, Стивен (2012), Программирование MATLAB с приложениями для инженеров , Cengage Learning, стр. 454, ISBN 978-1-28540279-6
- ^ а б в Чапра, Стивен (2012). Прикладные численные методы с MATLAB для инженеров и ученых (3-е изд.). ISBN компании McGraw-Hill Companies, Inc. 9780073401102.
- ^ Лапланте, Филип А. (2000). Словарь компьютерных наук, инженерии и технологий . CRC Press . п. 420. ISBN 978-0-84932691-2.
- ^ Хайэм, Николас Джон (2002). Точность и устойчивость численных алгоритмов (2-е изд.). Общество промышленной и прикладной математики (SIAM). С. 43–44. ISBN 978-0-89871521-7.
- ^ Волков Е.А. (1990). Численные методы . Тейлор и Фрэнсис . п. 24. ISBN 978-1-56032011-1.
- ^ Коллинз, Чарльз (2005). «Состояние и стабильность» (PDF) . Департамент математики Университета Теннесси . Проверено 28 октября 2018 .
- ^ Арнольд, Дуглас. "Неудача ракеты" Патриот " . Проверено 29 октября 2018 .
дальнейшее чтение
- Мэтт Паркер (2021). Humble Pi: Когда математика идет не так в реальном мире . Книги Риверхеда. ISBN 978-0593084694.
Внешние ссылки
- Ошибка округления в MathWorld.
- Гольдберг, Дэвид (март 1991). «Что должен знать каждый компьютерный ученый об арифметике с плавающей точкой» (PDF) . ACM Computing Surveys . 23 (1): 5–48. DOI : 10.1145 / 103162.103163 . Проверено 20 января 2016 .( [1] , [2] )
- 20 известных программных катастроф