Ошибка аппроксимации относится к разнице между точным значением и его приближением. Это расхождение можно количественно оценить двумя способами: как абсолютную ошибку , которая измеряет численную разницу, и как относительную ошибку , которая выражает абсолютную ошибку по отношению к истинному значению. Понимая оба типа ошибок, мы можем лучше оценить точность наших оценок и измерений.
Ошибки аппроксимации могут возникать из-за различных факторов, часто вытекающих из ограничений измерительных инструментов или точности вычислений. Например, если лист бумаги измеряет ровно 4,53 см, но ваша линейка отмечает только ближайшие 0,1 см, вы запишите это как 4,5 см. Аналогично, в вычислениях ограничения точности машин означают, что числа иногда округляются, что приводит к небольшим расхождениям . Эти ошибки, хотя часто и незначительны, могут повлиять на точность вычислений, особенно если они накапливаются в течение нескольких этапов.
В математической области численного анализа численная устойчивость алгоритма указывает на степень, в которой ошибки на входе алгоритма приведут к большим ошибкам на выходе; численно устойчивые алгоритмы не приводят к значительным ошибкам на выходе, когда входные данные неправильно сформированы, и наоборот. [ 1]
При некотором значении v мы говорим, что v approx приближает v с абсолютной погрешностью ε >0, если [2] [3]
где вертикальные черты обозначают абсолютное значение .
Мы говорим, что v approx приближает v с относительной погрешностью η >0, если
.
Если v ≠ 0, то
Процентная погрешность (выражение относительной погрешности) равна [3]
Граница погрешности — это верхний предел относительного или абсолютного размера погрешности аппроксимации. [4]
Например, если точное значение равно 50, а мы округляем его до 49,9, абсолютная погрешность составляет 0,1. Относительная погрешность, рассчитанная как 0,1/50, равна 0,002 или 0,2%.
В практическом сценарии рассмотрим измерение жидкости в стакане объемом 6 мл . Если показание показывает 5 мл , но правильное значение — 6 мл, процентная погрешность составляет 61≈16,7% . Этот вид погрешности показывает, как даже небольшие расхождения могут привести к значительным процентным погрешностям, особенно при меньших измерениях!
Относительная погрешность часто используется для сравнения приближений чисел, сильно различающихся по размеру; например, приближение числа 1000 с абсолютной погрешностью 3 в большинстве случаев намного хуже, чем приближение числа 1 000 000 с абсолютной погрешностью 3; в первом случае относительная погрешность составляет 0,003, тогда как во втором — всего 0,000003.
Следует помнить о двух важных аспектах относительной погрешности. Во-первых, относительная погрешность становится неопределенной, когда точное значение равно нулю, поскольку это поместило бы ноль в знаменатель. Во-вторых, относительная погрешность имеет смысл только тогда, когда значения измеряются по шкале отношений — той, которая имеет истинный ноль. Это связано с тем, что относительная погрешность чувствительна к единицам измерения. Например, измерение температуры с абсолютной погрешностью 1°C и истинным значением 2°C имеет относительную погрешность 0,5. Однако по шкале Кельвина та же самая погрешность в 1 К с истинным значением 275,15 К (эквивалентно 2°C) приводит к гораздо меньшей относительной погрешности 0,00363.
Утверждения об относительных ошибках чувствительны к сложению констант, но не к умножению на константы. Для абсолютных ошибок верно обратное: чувствительны к умножению на константы, но не к сложению констант. [5] : 34
Мы говорим, что действительное значение v полиномиально вычислимо с абсолютной ошибкой по входным данным, если для каждого рационального числа ε > 0 можно вычислить рациональное число v approx , которое аппроксимирует v с абсолютной ошибкой ε за время, полиномиальное по размеру входных данных и размеру кодирования ε (которое равно O(log(1/ ε )). Аналогично, v полиномиально вычислимо с относительной ошибкой , если для каждого рационального числа η > 0 можно вычислить рациональное число v approx , которое аппроксимирует v с относительной ошибкой η за время, полиномиальное по размеру входных данных и размеру кодирования η .
Если v полиномиально вычислимо с относительной ошибкой (некоторым алгоритмом, называемым REL), то оно также полиномиально вычислимо с абсолютной ошибкой. Доказательство . Пусть ε >0 будет желаемой абсолютной ошибкой. Сначала используем REL с относительной ошибкой η= 1/2; найдем рациональное число r 1 такое, что | v - r 1 | ≤ | v |/2, и, следовательно, |v| ≤ 2 | r 1 |. Если r 1 =0, то v =0, и мы закончили. Поскольку REL является полиномом, длина кодирования r 1 является полиномом на входе. Теперь снова запустим REL с относительной ошибкой η=ε/ (2 |r 1 |). Это дает рациональное число r 2 , которое удовлетворяет | v - r 2 | ≤ ε|v | / (2 r 1 ) ≤ ε , поэтому оно имеет абсолютную ошибку ε, как и требовалось. [5] : 34
Обратная импликация обычно неверна. Но если предположить, что некоторая положительная нижняя граница |v| может быть вычислена за полиномиальное время, например, | v | > b > 0, и v полиномиально вычислима с абсолютной ошибкой (неким алгоритмом, называемым ABS), то она также полиномиально вычислима с относительной ошибкой, поскольку мы можем просто вызвать ABS с абсолютной ошибкой ε = η b.
Алгоритм, который для каждого рационального числа η >0 вычисляет рациональное число v , приблизительно приближающее v с относительной погрешностью η , за время, полиномиальное от размера входных данных и 1/ η (а не log(1/ η )), называется FPTAS .
В большинстве индикаторных приборов точность гарантируется до определенного процента от полной шкалы показаний. Пределы этих отклонений от указанных значений известны как предельные погрешности или гарантированные погрешности. [6]
Определения можно распространить на случай, когда и являются n -мерными векторами , заменив абсолютное значение на n -норму . [7]
