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

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

Из сборников задач и учебников по математике мы привыкли анализировать задачи по критерию «имеет ли задача решение». Однако, даже задачи с однозначным решением могут быть сильно чувствительны к входным данным. Зачастую решение таких задач (в их исходной постановке) лишено практического смысла. В связи с этим, прежде чем приступать к задаче, следует проверить, является ли она корректной.

Первые критерии корректности задачи предписываются Жаку Адамару (1865-1963). Мы разрешим себе вольность в их пересказе, не вдаваясь в формализацию.

  1. Решение задачи существует для любых допустимых входных данных.

  2. Решение задачи единственно и содержится в области допустимых решений.

  3. Решение задачи непрерывно меняется с непрерывным изменением входных данных.

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

Задачи с высокой чувствительностью к входным данным называют плохо обусловленными. А чтобы измерить «обусловленность» задачи, используют число обусловленности.

2.2.1. Обусловленность#

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

\[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.2. Число обусловленности#

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

Определение 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.3. Оценка ошибок#

Из определения числа обусловленности (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\) не получится. Так, в случае чисел Float64 расчёты теряют смысл (все цифры в ответе ложные) при \(\kappa_f > 10^{16}\).

Определение 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).

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

2.2.4. Как решают плохо обусловленные задачи?#

Чтобы решать плохо обусловленные задачи, есть два пути.

  1. Сменить класс используемых чисел на числа с большей точностью (меньшей \(\macheps\)).

  2. Использовать те же числа, но решать (строго говоря) другую, регуляризованную задачу.

Первый путь хорош тем, что задача остаётся исходной, но уже не является плохо обусловленной. Практическим недостатком является потеря быстродействия, поскольку арифметика требуемого класса чисел может быть медленной. Сделать её по-настоящему быстрой можно только на уровне аппаратной поддержки, что может быть дорого или недоступно.

На втором пути применяются методы регуляризации, с некоторыми из них вы можете ознакомится по работам Андрея Николаевича Тихонова (1906-1993). Методы регуляризации, как правило, подменяют исходную задачу очень похожей, но с низкой чувствительностью к входным данным и допустимой на практике ошибкой в решении.

Содержание