Число обусловленности

Оглавление

В предыдущей лекции мы отметили, что при работе с арифметикой с плавающей запятой имеется три основных источника ошибок:

Округления вещественного числа до числа с плавающей запятой имеет относительную погрешность равную половине машинной точности.
Каждая операция над числами, имеющими точное представление с плавающей запятой, имеет погрешность равную машинной точности. Если операция над числами допускает округление в нужную сторону, то погрешность может быть равна половине машинной погрешности.
Погрешность входных данных может увеличиться или уменьшиться в результате выполнения операции даже в точной арифметике.

Первые два вида погрешности ограничены стандартом IEEE 754. Мы остановимся на третьем виде погрешности.

Ранее мы видели, что при возведении числа с некоторой данной малой относительной погрешностью в степень $a$ , относительная погрешность умножается на $a$ . Примененный нами способ оценки погрешности относительно сложен, однако можно вывести более простую формулу. Пусть нам дано $x=x_0(1+\delta x)$ приближенно равное $x_0$ с относительной погрешностью $\delta x$ . Вычислим значение $y=f(x)$ функции $f$ на аргументе $x$ . Предположим, что $f$ вычисляет точно, однако результат будет иметь погрешность, так как аргумент дан приближенно. Пусть точное значение результата $y_0=f(x_0)$ , тогда $y=y_0(1+\delta y)$ , где $\delta y$ - погрешность результата. Считая погрешность $\delta x$ малой, а функцию $f$ дифференцируемой, оценим искомую погрешность следующим образом:

$\delta y=(y-y_0)/y_0=(f(x_0(1+\delta x))-f(x_0))/f(x_0)=f'(x_0)x_0\delta x/f(x_0),$

где $f’(x_0)$ обозначает производную функцию в точке $x_0$ . Как мы видим, погрешность $\delta y$ результата пропорциональна погрешности аргумента $\delta x$ , если погрешность $\delta x$ мала. Коэффициент пропорциональности $k(f,x_0)$ называют числом обусловленности.

$k(f,x_0)=|x_0f'(x_0)/f(x_0)|.$

Мы вычислили число обусловленности для относительной погрешности аргумента и результата, однако можно вычислить и другие числа обусловленности. Например, найдем число обусловленности для абсолютной погрешности аргумента и результата. Пусть дан аргумент $x=x_0+\Delta x$ с абсолютной погрешностью $\Delta x$ . Результат вычислений функции $y=f(x_0)+\Delta y=f(x)$ имеет некую абсолютную погрешность $\Delta y$ . Тогда $\Delta y=f(x_0)-f(x_0+\Delta x)=f’(x_0)\Delta x$ , т.е. погрешность результата снова пропорциональна погрешности аргумента. Коэффициент пропорциональности называют числом обусловленности для абсолютных ошибок аргумента и результата, и мы видим, что оно равно модулю производной в точке.

При работе с числами с плавающей запятой мы интересуемся относительными погрешностями, поэтому будем обсуждать только число обусловленности для относительных погрешностей без дополнительных уточнений. Выше мы показали, что число обусловленности зависит от величины числа, с которым производятся операции, т.е. для функции есть область, где вычисления проводить безопасно, но при некоторых значениях аргумента результату нельзя доверять, причем библиотека работы с числами с плавающей запятой не даст вам никаких предупреждений. Число обусловленности $k$ равное или меньшее единицы как правило на устраивает, так как в этом случае точность результата равна или выше точности аргумента. Если $k$ больше единицы, то точность результат падает при вычислениях. Обычно выделяют хорошо обусловленные задачи с малыми числами обусловленности, и плохо обусловленные задачи, для которых числа обусловленности велики. Точные значения $k$ отделяющие разделяющие хорошо и плохо обусловленные задачи условно. Лучше воспринимать число обусловленности как меру числа знаков, которые становятся ошибочными после вычислений. Например, если число обусловленности равно $1000$ , то после вычисления функции число верных знаков в десятичной записи уменьшается на три. Значения $k$ , для которых решение задачи имеет смысл, зависит от точности исходных данных, числа применений функции, желаемой точности результат и т.п.

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

Вычислим числа обусловленности для элементарных функций.

$k(x^a)=x(x^a)'/(x^a)=xax^{a-1}/x^a=a.$

Результат для степенной функции совпал с полученным ранее результатом, в частности точность результата одна для всех чисел. Можно отметить, что вычисление обратного $1/x$ в точной арифметике может быть выполнено без потери точности.

Погрешность вычислений показательной функции увеличивается с ростом аргумента. Случай $a=1$ (постоянная функция) показывает, что погрешность результата может быть много меньше погрешности аргумента.

$k(a^x)=x(a^x)'/(a^x)=x(ln a)a^x/a^x=x\ln a.$

Рассмотрим погрешность вычисления тригонометрических функций:

$$k(\sin x)=	x(\sin x)’/(\sin x)	=	x\,\mathrm{ctg}\,x	,$$
$$k(\cos x)=	x(\cos x)’/(\cos x)	=	x\,\mathrm{ctg}\,x	,$$
$$k(\mathrm{tg}\,x)=	x(\mathrm{tg}\,x)’/(\mathrm{tg}\,x)	=	x/\sin x/\cos x	,$$
$$k(\mathrm{ctg}\, x)=	x(\mathrm{ctg}\,x)’/(\mathrm{ctg},x)	=	x/\sin x/\cos x	,$$
$$k(\mathrm{arctg}\, x)=	x(\mathrm{arctg}\, x)’/(\mathrm{arctg}\,x)	=	x/(1+x^2)/\mathrm{arctg}\,x	.$$

Результат вычисления тригонометрической функции может иметь бесконечно большую погрешность, если значение функции обращается в нуль. Ясно что это общий факт: исходя из определения относительной погрешности видно, что относительная погрешность стремится к бесконечности, если точное значение стремится к нулю.

Выше мы рассмотрели функции одного аргумента, однако арифметические операции зависят от двух аргументов. Понятие числа обусловленности можно перенести на случай нескольких аргументов, однако в этом случает нужно уточнить, что именно подразумевается под точностью аргумента, так как каждый аргумент может иметь свою точность. В качестве примера рассмотрим точность вычисления умножения. Пусть $x=x_0(1+\delta x)$ и $y=y_0(1+\delta y)$ даны приближенно, тогда их произведение равно

$xy=x_0y_0(1+\delta x)(1+\delta y)=x_0y_0(1+\delta x+\delta y+\delta x\cdot\delta y),$

где слагаемым $\delta x\cdot\delta y$ можно пренебречь, так как оно меньшего порядка, чем $\delta x$ и $\delta y$ . Из полученной формулы мы заключаем, что относительная погрешность произведения равна сумме погрешностей аргументов $\delta x+\delta y$ . Можно сказать, что погрешность результата пропорциональна некой функии от погрешностей аргументов, в математике эта функци называется нормой. В случае одной переменной роль нормы играл модуль числа, в случае нескольких переменных функция определена неоднозначно, например, можно рассмотреть $L^1$ норму $|(\delta x,\delta y)|=|\delta x|+|\delta y|$ или $L^\infty$ норму $\max(|\delta x|,|\delta y|)$ . Числа обусловленности для разных норм могут различаться, например, для $L^1$ нормы число обусловленности равно $1$ , а для $L^\infty$ нормы число обусловленности равно $2$ .

$|\delta x+\delta y|\leq|\delta x|+|\delta y|\leq 2\max(|\delta x|,|\delta y|).$

Оценим теперь относительную погрушность операции вычитания для тех же чисел $x$ и $y$ :

$|(x-y)-(x_0-y_0)|/|x_0-y_0|=|x_0\delta x-y_0\delta y|/|x_0-y_0|\leq |\delta x|\cdot|x_0|/|x_0-y_0|+|\delta y|\cdot|y_0|/|x_0-y_0| \leq\max(|\delta x|,|\delta y|)\cdot(|x_0|+|y_0|)/|x_0-y_0|.$

Неравенство выше показывает, что число обусловленности для вычитания в $L^\infty$ норме равно

$k(x_0,y_0)=(|x_0|+|y_0|)/|x_0-y_0|.$

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

Так как вычитание отличается от сложения только знаками аргументов, а мы не делали никаких предположений на знаки, то приведенная выше оценка также работает для сложения, но нужно изменить знак $y_0$ , тем самым получаем число обусловленности для сложения.

$k(x_0,y_0)=(|x_0|+|y_0|)/|x_0+y_0|.$

Легко видеть, что если оба аргумента положительны, то число обусловленности равно $1$ , т.е. при сложении положительных аргументов точность не изменяется. Отсюда можно предположить, что положительные числа можно складывать не задумываясь о точности, однако это не так. В качестве примера рассмотрим сумму числа $1$ и $10^n$ чисел $10^{-n}$ в арифметике с плавающей запятой. Сумма этих чисел должна быть равна $2$ , однако при сложеннии $1$ и $10^{-n}$ результат равен $1$ , если второе число меньше машинной точности, т.е. начиная суммирование с $1$ мы получаем в арифметике с плавающей запятой суммы равную $1$ . Однако, если начать суммирование с меньших слагаемых, то точность будет выше.

Вопросы для закрепления

Какова погрешность вычисления $1/pi$ в арифметике с плавающей запятой? Учтите погрешность округления $pi$ до числа с плавающей запятой, погрешность выполнения операция деления над числами с плавающей запятой и изменении погрешности при вычислении обратного.
Сравните точность вычисления $a/b$ и $a(1/b)$ .
Какой способ вычислений предпочтительнее: $\ln(a/b)$ или $\ln(a)-\ln(b)$ ?
Как согласуется существование эффекта катастрофического сокращения и требование стандарта IEEE 754, предписывающее операции вычитания возвращать результат с погрешностью, не превосходящей машинной точности?

Литература

Numerical recipes. The art of scientific computing. 1256 pp. Cambridge University Press (2007).