Ошибка округления
В вычислениях ошибка округления , [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). Это может произойти, например, когда программное обеспечение выполняет арифметические действия в 80-битном формате x86 с плавающей запятой , а затем округляет результат до IEEE 754binary64 с плавающей запятой .
Система счисления с плавающей запятой
[ редактировать ]По сравнению с системой счисления с фиксированной запятой , система счисления с плавающей запятой более эффективна для представления действительных чисел, поэтому она широко используется в современных компьютерах. Хотя реальные цифры бесконечны и непрерывны, система счисления с плавающей запятой конечно и дискретно. Таким образом, в системе счисления с плавающей запятой возникает ошибка представления, приводящая к ошибке округления.
Обозначение системы счисления с плавающей запятой
[ редактировать ]Система счисления с плавающей запятой характеризуется целые числа:
- : основание или основание
- : точность
- : диапазон экспоненты, где является нижней границей и это верхняя граница
Любой имеет следующую форму: где целое число такое, что для , и целое число такое, что .
Нормализованная система с плавающими числами
[ редактировать ]- Система счисления с плавающей запятой нормализуется, если первая цифра всегда ненулевое значение, если число не равно нулю. [3] Поскольку мантисса , значение ненулевого числа в нормализованной системе удовлетворяет . Таким образом, нормализованная форма ненулевого числа IEEE с плавающей запятой имеет вид где . В двоичной системе первая цифра всегда равна поэтому он не записывается и называется неявным битом. Это дает дополнительную точность и уменьшает ошибку округления, вызванную ошибкой представления.
- Поскольку система счисления с плавающей запятой конечен и дискретен, он не может представлять все действительные числа, что означает, что бесконечные действительные числа могут быть аппроксимированы только некоторыми конечными числами с помощью правил округления . Приближение данного действительного числа с плавающей запятой к можно обозначить.
- Общее количество нормализованных чисел с плавающей запятой равно где
- учитывается выбор знака, будь то положительный или отрицательный
- считает выбор первой цифры
- считает оставшиеся значащие цифры
- считает выбор показателей
- учитывается случай, когда число .
- Общее количество нормализованных чисел с плавающей запятой равно где
стандарт IEEE
[ редактировать ]В стандарте IEEE база двоичная, т.е. , и используется нормализация. Стандарт IEEE хранит знак, показатель степени и мантиссу в отдельных полях слова с плавающей запятой, каждое из которых имеет фиксированную ширину (количество битов). Двумя наиболее часто используемыми уровнями точности для чисел с плавающей запятой являются одинарная точность и двойная точность.
Точность | Знак (биты) | Экспонента (биты) | Поле завершающего мантиссы (биты) |
---|---|---|---|
Одинокий | 1 | 8 | 23 |
Двойной | 1 | 11 | 52 |
Машина эпсилон
[ редактировать ]Машинный эпсилон можно использовать для измерения уровня ошибки округления в системе счисления с плавающей запятой. Вот два разных определения. [3]
- Машинный эпсилон, обозначаемый , — максимально возможная абсолютная относительная ошибка представления ненулевого действительного числа. в системе счисления с плавающей запятой.
- Машинный эпсилон, обозначаемый , это наименьшее число такой, что . Таким образом, в любое время .
Ошибка округления при разных правилах округления
[ редактировать ]Существует два общих правила округления: по частям и округление до ближайшего. Стандарт IEEE использует округление до ближайшего.
- По частям : основание- расширение усекается после -я цифра.
- Это правило округления является предвзятым, поскольку оно всегда приближает результат к нулю.
- Округление до ближайшего : устанавливается как ближайшее число с плавающей запятой . В случае равенства используется число с плавающей запятой, последняя сохраненная цифра которого четная (также последняя цифра в двоичной форме равна 0).
- Для стандарта IEEE, где базовый является , это означает, что при ничьей она округляется так, чтобы последняя цифра была равна .
- Это правило округления более точное, но требует больше вычислительных затрат.
- Округление таким образом, чтобы последняя сохраненная цифра была четной, в случае равенства гарантирует, что она не будет систематически округляться в большую или меньшую сторону. Это делается для того, чтобы избежать возможности нежелательного медленного дрейфа в длительных вычислениях просто из-за смещенного округления.
- Следующий пример иллюстрирует уровень ошибки округления при двух правилах округления. [3] Правило округления, округление до ближайшего, в целом приводит к меньшей ошибке округления.
х | Раунд за отбивной | Ошибка округления | Округление до ближайшего | Ошибка округления |
---|---|---|---|---|
1.649 | 1.6 | 0.049 | 1.6 | 0.049 |
1.650 | 1.6 | 0.050 | 1.6 | 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.
- Пример: десятичное число можно переставить в
Поскольку 53-й бит справа от двоичной точки равен 1, а за ним следуют другие ненулевые биты, правило округления до ближайшего требует округления в большую сторону, то есть добавления 1 бита к 52-му биту. Таким образом, нормализованное представление с плавающей запятой в стандарте IEEE 9.4 имеет вид
- Теперь ошибку округления можно рассчитать при представлении с .
Это представление получается путем отбрасывания бесконечного хвоста. из правого хвоста, а затем добавил на этапе округления.
- Затем .
- Таким образом, ошибка округления равна .
Измерение ошибки округления с использованием машинного эпсилона
[ редактировать ]Машина Эпсилон может использоваться для измерения уровня ошибки округления при использовании двух приведенных выше правил округления. Ниже приведены формулы и соответствующие доказательства. [3] Здесь используется первое определение машинного эпсилона.
Теорема
[ редактировать ]- По кругу:
- Округление до ближайшего:
Доказательство
[ редактировать ]Позволять где , и пусть быть представлением с плавающей запятой . Поскольку используется порубочная обработка, это Для того чтобы определить максимум этой величины, необходимо найти максимум числителя и минимум знаменателя. С (нормированная система), минимальное значение знаменателя равно . Числитель ограничен сверху . Таким образом, . Поэтому, для круга за отбивной.Доказательство округления до ближайшего аналогично.
- Обратите внимание, что первое определение машинного эпсилона не совсем эквивалентно второму определению при использовании правила округления до ближайшего, но оно эквивалентно для округления за кусочком.
Ошибка округления, вызванная арифметикой с плавающей запятой
[ редактировать ]Даже если некоторые числа могут быть точно представлены числами с плавающей запятой и такие числа называются машинными числами , выполнение арифметических операций с плавающей запятой может привести к ошибке округления в конечном результате.
Добавление
[ редактировать ]Машинное сложение состоит из выравнивания десятичных точек двух суммируемых чисел, их сложения и последующего сохранения результата в виде числа с плавающей запятой. Само сложение можно выполнить с более высокой точностью, но результат необходимо округлить до заданной точности, что может привести к ошибке округления. [3]
- Например, добавив к в двойной точности IEEE следующим образом:
Это сохраняется как поскольку в стандарте IEEE используется округление до ближайшего. Поэтому, равно в двойной точности IEEE и ошибка округления равна .
Этот пример показывает, что ошибка округления может возникнуть при сложении большого и малого числа. Смещение десятичных знаков в значащих числах для обеспечения совпадения показателей степени приводит к потере некоторых менее значащих цифр. Утрату точности можно охарактеризовать как поглощение . [11]
Обратите внимание, что сложение двух чисел с плавающей запятой может привести к ошибке округления, если их сумма на порядок больше, чем сумма большего из двух.
- Например, рассмотрим нормализованную систему счисления с плавающей запятой с основанием и точность . Затем и . Обратите внимание, что но . Имеется ошибка округления .
Ошибка такого рода может возникать наряду с ошибкой поглощения в одной операции.
Умножение
[ редактировать ]Как правило, произведение двух мантисс p-цифр содержит до 2p цифр, поэтому результат может не поместиться в мантиссу. [3] Таким образом, в результат будет включена ошибка округления.
- Например, рассмотрим нормализованную систему счисления с плавающей запятой с основанием и значащие цифры не более . Затем и . Обратите внимание, что но так как там максимум значащие цифры. Ошибка округления будет .
Разделение
[ редактировать ]В общем, частное 2p-значных чисел может содержать более p-цифр. Таким образом, в результате будет присутствовать ошибка округления.
- Например, если приведенная выше нормализованная система счисления с плавающей запятой все еще используется, то но . Итак, хвост отрезан.
Вычитание
[ редактировать ]Поглощение также применимо к вычитанию.
- Например, вычитание от в двойной точности IEEE следующим образом: Это сохраняется как поскольку в стандарте IEEE используется округление до ближайшего. Поэтому, равно в двойной точности IEEE и ошибка округления равна .
Вычитание двух почти равных чисел называется вычитающим сокращением . [3] Когда первые цифры удалены, результат может быть слишком мал, чтобы его можно было представить точно, и он будет просто представлен как .
- Например, пусть и здесь используется второе определение машинного эпсилона. Каково решение ?
Известно, что и это почти равные числа, и . Однако в системе счисления с плавающей запятой . Хотя достаточно велик, чтобы его можно было представить, оба экземпляра были округлены, давая .
Даже с несколько большим , в типичных случаях результат по-прежнему существенно ненадежен. В точность значения не особо верят, поскольку наибольшую неопределенность в любом числе с плавающей запятой представляют цифры в крайнем правом углу.
- Например, . Результат ясно представимо, но веры в него мало.
Это тесно связано с явлением катастрофического сокращения , в котором эти два числа, как известно, являются приближениями.
Накопление ошибки округления
[ редактировать ]Ошибки могут увеличиваться или накапливаться, если к исходным входным данным применяется последовательность вычислений с ошибкой округления из-за неточного представления.
Нестабильные алгоритмы
[ редактировать ]Алгоритм или численный процесс называется стабильным, если небольшие изменения входных данных приводят лишь к небольшим изменениям выходных данных, и нестабильным, если производятся большие изменения выходных данных. [12] Например, вычисление использование «очевидного» метода вблизи неустойчиво из-за большой ошибки, возникающей при вычитании двух одинаковых величин, тогда как эквивалентное выражение является стабильным. [12]
Плохо обусловленные проблемы
[ редактировать ]Даже если используется стабильный алгоритм, решение задачи все равно может быть неточным из-за накопления ошибки округления, когда сама задача плохо обусловлена .
Число обусловленности задачи — это отношение относительного изменения решения к относительному изменению входных данных. [3] Задача считается хорошо обусловленной , если небольшие относительные изменения входных данных приводят к небольшим относительным изменениям в решении. В противном случае проблема плохо обусловлена . [3] Другими словами, задача является плохо обусловленной, если число ее условий «намного больше» 1.
Число обусловленности вводится как мера ошибок округления, которые могут возникнуть при решении плохо обусловленных задач. [7]
См. также
[ редактировать ]- Точность (арифметика)
- Усечение
- Округление
- Потеря значимости
- Плавающая точка
- Алгоритм суммирования Кахана
- Машина эпсилон
- Значимые цифры
- Полином Уилкинсона
Ссылки
[ редактировать ]- ^ Батт, Ризван (2009), Введение в численный анализ с использованием MATLAB , Jones & Bartlett Learning, стр. 11–18, ISBN 978-0-76377376-2
- ^ Юберхубер, Кристоф В. (1997), Численные вычисления 1: методы, программное обеспечение и анализ , Springer, стр. 139–146, ISBN 978-3-54062058-7
- ^ Jump up to: а б с д и ж г час я дж Форрестер, Дик (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
- ^ Jump up to: а б Чапра, Стивен (2012). Прикладные численные методы с MATLAB для инженеров и ученых (3-е изд.). МакГроу-Хилл . ISBN 9780073401102 .
- ^ Лапланте, Филип А. (2000). Словарь по информатике, технике и технологиям . ЦРК Пресс . п. 420. ИСБН 978-0-84932691-2 .
- ^ Хайэм, Николас Джон (2002). Точность и устойчивость численных алгоритмов (2-е изд.). Общество промышленной и прикладной математики (SIAM). стр. 43–44. ISBN 978-0-89871521-7 .
- ^ Волков, Е.А. (1990). Численные методы . Тейлор и Фрэнсис . п. 24. ISBN 978-1-56032011-1 .
- ^ Биран, Адриан Б.; Брейнер, Моше (2010). «5». Что должен знать каждый инженер о MATLAB и Simulink . Бока-Ратон , Флорида : CRC Press . стр. 193–194. ISBN 978-1-4398-1023-1 .
- ^ Jump up to: а б Коллинз, Чарльз (2005). «Состояние и стабильность» (PDF) . Кафедра математики в Университете Теннесси . Проверено 28 октября 2018 г.
Дальнейшее чтение
[ редактировать ]- Мэтт Паркер (2021). Скромный Пи: когда математика в реальном мире идет не так . Книги Риверхеда. ISBN 978-0593084694 .
Внешние ссылки
[ редактировать ]- Ошибка округления в MathWorld.
- Гольдберг, Дэвид (март 1991 г.). «Что должен знать каждый ученый-компьютерщик об арифметике с плавающей запятой» (PDF) . Обзоры вычислительной техники ACM . 23 (1): 5–48. дои : 10.1145/103162.103163 . S2CID 222008826 . Проверено 20 января 2016 г. ( [1] , [2] )
- 20 известных катастроф программного обеспечения