Обусловленность задач

2.2. Обусловленность задач#

Рассмотрим простую вычислительную задачу. Необходимо вычислить значение функции

\[f(x) = x + 1.\]

Поскольку вычисления осуществляются в числах с плавающей точкой, то в реальности получится вычислить не \(f(x)\), а \(y(x)\) следующего вида

\[y(x) = \float(x) + 1 = (x + \delta x) + 1,\]

единица при этом представима точно.

Теперь рассмотрим относительную ошибку вычисления \(f(x)\)

\[\frac{|f(x) - y(x)|}{|f(x)|} = \frac{|(x + 1) - (x + \delta x + 1)|}{|x+1|} = \frac{|\delta x|}{|x+1|}.\]

Отсюда видно, что относительная ошибка возрастает, если значение \(x\) близко к \(-1\).

Подобные ошибки являются следствием конечной точности используемых чисел \(x \to \float(x)\). Если вычисления ведутся в таких числах, то этих ошибок не избежать независимо от используемого алгоритма. Поэтому, ещё до его написания можно оценить области входных данных, на которых алгоритм даёт большие ошибки.

Кроме того, в случае Float64, несмотря на точность в 16 десятичных знаков, не все они репрезентативны в конечном результате.

Таким образом, задачам (и алгоритмам) можно сопоставить их чувствительность к входным данным. У некоторых задач теоретически сильная чувствительность (большая обусловленность), что в паре с вычислительной погрешностью приводит к ошибкам в расчётах. Для оценки чувствительности вводится число обусловленности.

2.2.1. Число обусловленности#

… скалярных функций

Определение 2.5 (Число обусловленности скалярной функции)

Относительным числом обусловленности называют предел отношения относительного изменения значения функции к относительному изменению значения аргумента.

(2.4)#\[\kappa_f(x) = \lim_{\delta x \to 0} \frac{ \dfrac{ |f(x+\delta x)-f(x)| }{|f(x)|} }{ \dfrac{|\delta x|}{|x|} }.\]

В случае дифференциируемой функции \(f\) из (2.4) получаем

(2.5)#\[\kappa_f(x) = \left| \frac{x f'(x)}{f(x)}\right|.\]

Число обусловленности сложной функции \(h(x) = f(g(x))\) имеет вид

\[\kappa_h(x) = \kappa_f(g(x))\cdot\kappa_g(x),\]

что показывает, как могут распространяться ошибки в алгоритмах.

Пример 2.6

Сложение \(\text{add}(x) = x + c\) порождает ошибки из-за конечной точности

\[ \kappa_\text{add}(x) = \left|\frac{(x)(1)}{x+c}\right| = \left|\frac{x}{x+c}\right| \]

около точек \(x \approx -c\).

Умножение \(\text{mul}(x) = cx\) не порождает новых, но «протаскивает» существующие

\[ \kappa_\text{mul}(x) = \left| \frac{(x)(c)}{cx} \right| = 1. \]

А вот, скажем, извлечение корня \(\text{sqrt}(x) = \sqrt x\)

\[ \kappa_\text{sqrt}(x) = \left| \frac{(x)(1/(2\sqrt x))}{\sqrt x} \right| = \frac{1}{2} \]

теоретически должно уменьшать ошибку в вычислениях, однако, на практике \(\text{sqrt}(x)\) реализован программно, и при его вычислении происходят операции, порождающие ошибки. Либо, в конечном итоге, произойдёт ошибка округления входных данных. Поэтому, на практике меньшее единицы число обусловленности \(\kappa_f < 1\) можно «округлять» до единицы.

2.2.2. Оценка ошибок#

Из определения числа обусловленности (2.4) следует, что при малом \(\delta x\)

(2.6)#\[\frac{ |f(x+\delta x) - f(x)| }{|f(x)|} \approx \kappa_f(x) \frac{|\delta x|}{|x|}.\]

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

Например, в случае \(\kappa_f \approx 10^d\) можно ожидать, что \(d\) десятичных знаков (мантиссы) потеряны при вычислении \(f(x)\) из \(x\). Таким образом, если \(\kappa_f\approx 1/\macheps\), то вычислить \(f\) в числах с точностью \(\macheps\) не получится.

Определение 2.7 (Плохая обусловленность задачи)

Если задача имеет большое число обусловленности при некотором \(x\), то говорят, что задача плохо обусловлена при этом \(x\). В таких случаях ошибка в получаемом ответе уже превышает ошибку округления.

Демонстрация 2.8

Вычисление детерминанта является плохо обусловленной задачей для почти сингулярных матриц. Рассмотрим пример

\[\begin{split}A(x) = \begin{bmatrix} 1 + x & 2 \\ 4 & 5 \end{bmatrix}, \quad \det(A(x)) = 5x - 3, \quad \kappa_\det(x) = \left|\frac{x}{x - 0.6}\right|.\end{split}\]

Эта матрица сингулярна при \(x^* = 0.6\), а число обусловленности возрастает при \(x^* \).

using LinearAlgebra: det;
x = 0.601;
@show A = [1.0 + x 2.0; 4.0 5.0];  # 1.601 представимо точно
@show det(A);

A = [1.0 + x 2.0; 4.0 5.0] = [1.601 2.0; 4.0 5.0]
det(A) = 

0.004999999999999893

По цифрам в мантиссе видно, что детерминант вычислен с ошибкой (точное значение \(0.005\)). Посмотрим на относительную ошибку вычислений err

err = abs(det(A) - 0.005) / 0.005

2.1337098754514727e-14

Число обусловленности в точке \(x=0.601\) равняется \(\kappa_\det = 601\). Если теперь возмутить входные данные \(x\) на погрешность, вносимую \(\float(x)\), т.е. на машинную точность \(\delta x = \) eps(x) вблизи \(x\), получим

@show err_estimate = 601.0 * (eps(x) / x);

err_estimate = 601.0 * (eps(x) / x) = 1.1102230246251565e-13

Видно, что ошибка вычислений err совпадает с оценкой ошибки err_estimate по выражению (2.6).

Содержание