Начало
Учебные материалы
Численные алгоритмы
Вычислительная математика Классификация ошибок вычислений Алгоритмы численного интегрирования Алгоритмы для решения нелинейных уравнений Алгоритмы для поиска экстремума
Классификация ошибок вычислений
аппроксимации бесконечного ряда Тейлора конечной суммой его первых элементов:
`e^x ~~ 1 +x + x^2/{2!} + ... + x^n /{n!}`.
Ошибка, которое дает такое приближение, называется *ошибкой усечения* (ошибкой метода).
Одной из важных задач в численных методах является оценка величины ошибки усечения, для этого разработан соответствующей
математический инструментарий. Например, для приближения `e^x` имеем:
`|e^x -( 1 +x + x^2/{2!} + ... + x^n /{n!})| <= (max_{t in [0,x]} e^t)/{(n+1)!} |x|^(n+1)`.
--
Например, если мы хотим вычислить `e^{1//2}` и гарантировать ошибку усечения не выше `10^{-4}`:
`(max_{t in [0,1//2]} e^t)/{(n+1)!} |1/2|^(n+1)<=e^{1//2}/{(n+1)! 2^(n+1)}<=2^{-n}/{(n+1)!} <= 10^{-4}`,
Откуда получаем `n=5`.
--
Второй тип ошибки, именуемой *ошибкой округления*, вызван
ограниченной точностью, с которой действительные числа могут быть
представлены в компьютере. Действительные числа представляются как
`+-0.b_1 b_2...b_p *2^N`, где `b_i in {0,1}` -- разряд числа.
Точность представления числа с плавающей точкой зависит от количества
значащих цифр `p` в представлении. Большинство
компьютеров позволяют использовать два или три уровня точности:
одинарную точность (6-7 значащих десятичных цифр),
двойную точность (14-15 значащих десятичных цифр)
и расширенную точность (18-19 значащих десятичных цифр).
--
Как и в случае любого типа приближений, важно различать *абсолютную
ошибку* и *относительную ошибку* представления
числа `alpha^{**}` его приближением `alpha`:
`"Абсолютная ошибка" = |alpha-alpha^{**}|`
`"Относительная ошибка" = {|alpha-alpha^{**}|}/{|alpha^{**}|}`
Относительная ошибка не определена при `alpha^{**}=0`.
--
Очень большие и очень маленькие числа не могут быть представлены в
арифметике с плавающей точкой из-за явлений, называющихся соответственно
*переполнением* (overflow) и *исчезновение порядка* (underflow).
Иногда таких проблем можно избежать, просто внеся небольшие изменения в порядок вычисления выражения,
заменяя выражение эквивалентным или вычисляя логарифм выражения вместо его значения.
--
Кроме неточностей представления чисел арифметические
операции, выполняемые компьютером, также не всегда точны. В частности,
вычитание двух близких чисел с плавающей точкой может привести к резкому росту
относительной ошибки. Это явление носит название *потери значащих разрядов*.
Если разность с пониженной точностью будет использована в качестве
делителя, то эта ошибка будет распространяться и будет получен неверный ответ.
--
Рассмотрим уравнение `x^2 - 10^5 х + 1 = 0`.
Его истинными корнями до одиннадцатой значащей цифры являются
`x_1^{**} = 99999.999990` и `x_2^{**} = 0.000010000000001`.
Если мы выполним все вычисления с
использованием одинарной точности (7 значащих цифр), то получим
`D = 0.1000000*10^{11}`,
`sqrt{D}=0.1000000*10^{6}`,
`x_1=0.1000000*10^{6}`, `x_2 = 0.0000000`.
В то время как относительная ошибка приближения `x_1` к `x_1^{**}` очень мала (`<10^{-10}`), для
второго корня она составляет 100%.
--
Многие численные алгоритмы выполняют для типичных входных
данных тысячи или даже миллионы арифметических операций, и распространение
ошибок округления в них становится основным вопросом как с теоретической,
так и с практической точек зрения. Для некоторых алгоритмов распространение
ошибок округления идет с нарастанием. Это крайне нежелательное свойство
численного алгоритма называется *нестабильностью*.
Некоторые задачи демонстрируют настолько высокую степень чувствительности к изменениям
входных данных, что невозможно разработать стабильный алгоритм для их решения.
Такие задачи называются *плохо обусловленными*.
