Введение
Математическая концепция
Ошибка приближения в значении данных — это разница между точным значением и его приближением. Эта ошибка может быть выражена как абсолютная ошибка (величина этой разницы) или как относительная ошибка (абсолютная ошибка, делённая на значение данных). Ошибка приближения может возникать по различным причинам, включая точность вычислительного устройства или погрешность измерения (например, длина листа бумаги составляет 4,53 см, но линейка позволяет оценить её только с точностью до 0,1 см, поэтому измерение даёт 4,5 см). В области математического анализа, известной как численное, численная устойчивость алгоритма показывает, насколько ошибки во входных данных могут привести к большим ошибкам в результате; численно устойчивые алгоритмы не приводят к существенным ошибкам в результате, даже если входные данные неточны, и наоборот.
Примеры
Например, если точное значение равно 50, а приближение равно 49,9, то абсолютная погрешность равна 0,1, а относительная погрешность равна 0,1/50 = 0,002 = 0,2%. В качестве практического примера, при измерении 6 мл стакана было получено значение 5 мл. Поскольку правильное значение равно 6 мл, процентная погрешность в данной конкретной ситуации, округленно, составляет 16,7%. Относительная погрешность часто используется для сравнения приближений чисел сильно различающихся по величине; например, приближение числа 1000 с абсолютной погрешностью 3 в большинстве случаев намного хуже, чем приближение числа 1 000 000 с абсолютной погрешностью 3; в первом случае относительная погрешность составляет 0,003, а во втором – всего 0,000003. Следует учитывать две особенности относительной погрешности. Во-первых, относительная погрешность не определена, когда истинное значение равно нулю, поскольку оно находится в знаменателе (см. ниже). Во-вторых, относительная погрешность имеет смысл только при измерении по шкале отношений (то есть шкале, имеющей истинный, значимый ноль), иначе она чувствительна к единицам измерения. Например, если абсолютная погрешность измерения температуры в шкале Цельсия составляет 1 °C, а истинное значение равно 2 °C, то относительная погрешность составляет 0,5. Но если то же самое приближение выполнено в шкале Кельвина, абсолютная погрешность 1 К при том же истинном значении 275,15 К = 2 °C дает относительную погрешность 3,63.
Сравнение
Заявления об относительных ошибках чувствительны к добавлению констант, но не к умножению на константы. Для абсолютных ошибок верно обратное: они чувствительны к умножению на константы, но не к добавлению констант.
Приближение в полиномиальном времени действительных чисел
Мы говорим, что вещественное значение v является полиномиально вычислимым с абсолютной ошибкой от входных данных, если для каждого рационального числа ε>0 возможно вычислить рациональное число vapprox, которое приближает v с абсолютной ошибкой ε, за время, полиномиальное от размера входных данных и размера кодирования ε (который равен O(log(1/ε))). Аналогично, v является полиномиально вычислимым с относительной ошибкой, если для каждого рационального числа η>0 возможно вычислить рациональное число vapprox, которое приближает v с относительной ошибкой η, за время, полиномиальное от размера входных данных и размера кодирования η. Если v полиномиально вычислимо с относительной ошибкой (с помощью некоторого алгоритма, называемого REL), то оно также полиномиально вычислимо с абсолютной ошибкой. Доказательство. Пусть ε>0 – желаемая абсолютная погрешность. Сначала используйте REL с относительной погрешностью η=1/2; найдите рациональное число r1 такое, что |v - r1| ≤ |v|/2, и, следовательно, |v| ≤ 2|r1|. Если r1=0, то v=0 и мы закончили. Поскольку REL является полиномиальным, длина кодирования r1 полиномиальна от размера входных данных. Теперь запустите REL снова с относительной ошибкой η=ε/(2|r1|). Это даст рациональное число r2, которое удовлетворяет |v - r2| ≤ ε|v| / (2|r1|) ≤ ε, то есть имеет абсолютную погрешность ε, как и требовалось.
Обобщения
Определения могут быть расширены на случай, когда и являются n-мерными векторами, заменяя абсолютную величину на n-норму.