Подразделы

Другие разделы

Дата и время

09/04/2025 22:03:38

Авторизация

Численные алгоритмы

Вычислительная математика Классификация ошибок вычислений Алгоритмы численного интегрирования Алгоритмы для решения нелинейных уравнений Алгоритмы для поиска экстремума

Классификация ошибок вычислений

Значения стандартных функций (например, $e^x$ ) вычисляются путем аппроксимации бесконечного ряда Тейлора конечной суммой его первых элементов:

$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%.

Многие численные алгоритмы выполняют для типичных входных данных тысячи или даже миллионы арифметических операций, и распространение ошибок округления в них становится основным вопросом как с теоретической, так и с практической точек зрения. Для некоторых алгоритмов распространение ошибок округления идет с нарастанием. Это крайне нежелательное свойство численного алгоритма называется нестабильностью.