Ошибка аппроксимации

Ошибка аппроксимации значения данных — это несоответствие между точным значением и некоторым приближением к нему. Эта ошибка может быть выражена как абсолютная ошибка (числовая величина расхождения) или как относительная ошибка (абсолютная ошибка, деленная на значение данных).

Ошибка аппроксимации может возникнуть по разным причинам, в том числе из-за точности вычислительной машины или ошибки измерения (например, длина листа бумаги составляет 4,53 см, но линейка позволяет оценить ее только с точностью до 0,1 см, поэтому вы измеряете это 4,5 см).

В математической области численного анализа численная стабильность алгоритма ; указывает на степень, в которой ошибки на входных данных алгоритма приведут к большим ошибкам на выходе численно стабильные алгоритмы не дают значительной ошибки в выводе, когда входные данные имеют неверный формат, и наоборот. ^[1]

Формальное определение

Учитывая некоторое значение v , мы говорим, что v _{приближенно} приближает v с абсолютной ошибкой ε >0, если ^[2]^[3]

|v-v_{\text{approx}}|\leq \varepsilon

где вертикальные полосы обозначают абсолютное значение .

Мы говорим, что v _{приближенно} приближает v с относительной ошибкой η > 0, если

$|v-v_{\text{approx}}|\leq \eta \cdot v$ .

Если v ≠ 0, то

\eta ={\frac {\epsilon }{|v|}}=\left|{\frac {v-v_{\text{approx}}}{v}}\right|=\left|1-{\frac {v_{\text{approx}}}{v}}\right|

.

Процентная ошибка (выражение относительной ошибки) равна ^[3]

\delta =100\%\times \eta =100\%\times \left|{\frac {v-v_{\text{approx}}}{v}}\right|.

Граница ошибки — это верхний предел относительного или абсолютного размера ошибки аппроксимации. ^[4]

Примеры

Например, если точное значение равно 50, а приближение — 49,9, то абсолютная ошибка равна 0,1, а относительная ошибка — 0,1/50 = 0,002 = 0,2%. В качестве практического примера: при измерении стакана емкостью 6 мл полученное значение составило 5 мл. Правильное показание составляет 6 мл, это означает, что процентная ошибка в этой конкретной ситуации составляет, округленно, 16,7%.

Относительная ошибка часто используется для сравнения приближений чисел сильно различающегося размера; например, приближение числа 1000 с абсолютной ошибкой 3 в большинстве приложений намного хуже, чем приближение числа 1000000 с абсолютной ошибкой 3; в первом случае относительная ошибка равна 0,003, а во втором — всего 0,000003.

Следует иметь в виду две особенности относительной ошибки. Во-первых, относительная ошибка не определена, когда истинное значение равно нулю, как оно указано в знаменателе (см. ниже). Во-вторых, относительная ошибка имеет смысл только при измерении по шкале отношений (т. е. шкале, которая имеет истинный значимый ноль), в противном случае она чувствительна к единицам измерения. Например, если абсолютная ошибка измерения температуры , выраженная в шкале Цельсия , составляет 1 °С, а истинное значение составляет 2 °С, относительная ошибка равна 0,5. Но если сделать то же самое приближение с использованием шкалы Кельвина , абсолютная ошибка в 1 К с тем же истинным значением 275,15 К = 2 °C дает относительную ошибку 3,63 × 10. ⁻³.

Сравнение

Утверждения об относительных ошибках чувствительны к сложению констант, но не к умножению на константы. Для абсолютных ошибок верно обратное: они чувствительны к умножению на константы, но не к сложению констант. ^[5]^: 34

Полиномиальная аппроксимация действительных чисел

Мы говорим, что действительное значение v является полиномиально вычислимым с абсолютной ошибкой на входных данных, если для каждого рационального числа ε > 0 можно вычислить рациональное число v _{приблизительно} , которое аппроксимирует v с абсолютной ошибкой ε , за время, полиномиальное по размеру. входных данных и размер кодирования ε (который равен O(log(1/ ε )). Аналогично, v полиномиально вычислимо с относительной ошибкой , если для каждого рационального числа η > 0 можно вычислить рациональное число v _{приближение} , которое аппроксимирует v с относительной ошибкой η , за полиномиальное время от размера входных данных и размера кодирования η .

Если v полиномиально вычислимо с относительной ошибкой (с помощью некоторого алгоритма под названием REL), то оно также полиномиально вычислимо с абсолютной ошибкой. Доказательство . Пусть ε >0 — искомая абсолютная ошибка. Сначала используйте REL с относительной ошибкой η= 1/2; найдите рациональное число r ₁ такое, что | в - р ₁ | ≤ | v |/2 и, следовательно, |v| ≤ 2 | р ₁ |. Если r ₁ =0, то v =0 и все готово. Поскольку REL является полиномиальным, длина кодирования r ₁ является полиномиальной на входе. Теперь снова запустите REL с относительной ошибкой η=ε/ (2 |r ₁ |). Это дает рациональное число r _2, удовлетворяющее условию | в - р ₂ | ≤ ε|v | / (2 r ₁ ) ≤ ε , поэтому он имеет абсолютную ошибку ε, как и хотелось. ^[5]^: 34

Обратный вывод обычно неверен. Но если предположить, что некоторая положительная нижняя граница |v| можно вычислить за полиномиальное время, например | в | > b > 0, и v полиномиально вычислимо с абсолютной ошибкой (с помощью некоторого алгоритма, называемого ABS), то оно также полиномиально вычислимо с относительной ошибкой, поскольку мы можем просто вызвать ABS с абсолютной ошибкой ε = η b.

Алгоритм, который для каждого рационального числа η рациональное число v _{> 0 вычисляет} , аппроксимирующее v с относительной ошибкой η , за время, полиномиальное от размера входных данных и 1/ η (а не log(1/ η )), называется ФПТАС .

Инструменты

В большинстве показывающих приборов точность гарантирована до определенного процента от полной шкалы. Пределы этих отклонений от заданных значений известны как предельные погрешности или гарантийные погрешности. ^[6]

Обобщения

Определения можно распространить на случай, когда $v$ и $v_{\text{approx}}$ являются n -мерными векторами путем замены абсолютного значения на n -норму . ^[7]

См. также

Ссылки

^ Вайсштейн, Эрик В. «Численная стабильность» . mathworld.wolfram.com . Проверено 11 июня 2023 г.
^ Вайсштейн, Эрик В. «Абсолютная ошибка» . mathworld.wolfram.com . Проверено 11 июня 2023 г.
^ Перейти обратно: ^а ^б «Абсолютная и относительная ошибка | Исчисление II» . Courses.lumenlearning.com . Проверено 11 июня 2023 г.
^ «Приближение и границы ошибок» . www.math.wpi.edu . Проверено 11 июня 2023 г.
^ Перейти обратно: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419
^ Хелфрик, Альберт Д. (2005) Современные электронные приборы и методы измерения . п. 16. ISBN 81-297-0731-4
^ Голуб, Гена ; Чарльз Ф. Ван Лоан (1996). Матричные вычисления – третье издание . Балтимор: Издательство Университета Джона Хопкинса. п. 53. ИСБН 0-8018-5413-Х .

Внешние ссылки

Вайсштейн, Эрик В. «Процентная ошибка» . Математический мир .

[1] Вайсштейн, Эрик В. «Численная стабильность» . mathworld.wolfram.com . Проверено 11 июня 2023 г.

[2] Вайсштейн, Эрик В. «Абсолютная ошибка» . mathworld.wolfram.com . Проверено 11 июня 2023 г.

[:0-3] Перейти обратно: ^а ^б «Абсолютная и относительная ошибка | Исчисление II» . Courses.lumenlearning.com . Проверено 11 июня 2023 г.

[4] «Приближение и границы ошибок» . www.math.wpi.edu . Проверено 11 июня 2023 г.

[:02-5] Перейти обратно: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

[6] Хелфрик, Альберт Д. (2005) Современные электронные приборы и методы измерения . п. 16. ISBN 81-297-0731-4

[GOLUB_MAT_COMP2.2.3-7] Голуб, Гена ; Чарльз Ф. Ван Лоан (1996). Матричные вычисления – третье издание . Балтимор: Издательство Университета Джона Хопкинса. п. 53. ИСБН 0-8018-5413-Х .

[1]

[2]

[3]

[4]

[5]

[6]

[7]