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

В области численного анализа число обусловленности функции по отношению к аргументу измеряет, насколько может измениться значение функции при небольшом изменении аргумента. Данный параметр отражает, насколько чувствительна функция к изменениям или ошибкам на входе и насколько ошибка на выходе является результатом ошибки на входе. Очень часто решается обратная задача — зная $f(x)=y$, найти $x$, для которой должно использоваться число обусловленности (локальной) обратной задачи. В линейной регрессии число обусловленности может использоваться в качестве диагностики для мультиколлинеарности.

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

$y=f(x)$

$y+\Delta y=f(x+\Delta x)$

$\mu (f):=\max _{x}{\frac {\varepsilon _{y}}{\varepsilon _{x}}}=\max _{x}{\frac {\|\Delta y\|/\|y\|}{\|\Delta x\|/\|x\|}}$ при малых $\Delta x$^{[уточнить]}

где $\|\cdot \|$ — норма или метрика соответственно в пространстве аргументов или значений.^{[уточнить]}

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

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

Как правило, если число обусловленности $\mu (f)=10^{k}$, то вы можете потерять до k цифр точности сверх того, что будет потеряно для числового значения из-за потери точности из арифметических методов. Однако число обусловленности не дает точного значения максимальной погрешности, которая может возникнуть в алгоритме. Обычно это просто ограничивает его оценкой (чье вычисленное значение зависит от выбора нормы для измерения погрешности).

Число обусловленности для линейных уравнений

Пусть задан ограниченный обратимый линейный оператор $A$.

Рассмотрим линейное уравнение

$Ax=b$,

где $A$ — линейный оператор, $b$ — вектор, $x$ — искомый вектор (переменная уравнения). Допустим, уравнение решается с погрешностью на входных данных $b\pm \Delta b$. Отношение относительных ошибок аргумента $b$ и решения $A^{-1}b$ равно

${\frac {\frac {\left\|A^{-1}\Delta b\right\|}{\left\|A^{-1}b\right\|}}{\frac {\|\Delta b\|}{\|b\|}}}=\left({\frac {\left\|A^{-1}\Delta b\right\|}{\|\Delta b\|}}\right)\cdot \left({\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right).$

Тогда число обусловленности $\mu (A)$ характеризует, насколько велика будет погрешность решения при произвольных ненулевых $b$ и $\Delta b$.

${\begin{aligned}\mu (A)=\max _{\Delta b,b\neq 0}\left\{\left({\frac {\left\|A^{-1}\Delta b\right\|}{\|\Delta b\|}}\right)\cdot \left({\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right)\right\}&=\max _{\Delta b\neq 0}\left\{{\frac {\left\|A^{-1}\Delta b\right\|}{\|\Delta b\|}}\right\}\cdot \max _{b\neq 0}\left\{{\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right\}\\&=\max _{\Delta b\neq 0}\left\{{\frac {\left\|A^{-1}\Delta b\right\|}{\|\Delta b\|}}\right\}\cdot \max _{x\neq 0}\left\{{\frac {\|Ax\|}{\|x\|}}\right\}\\&=\left\|A^{-1}\right\|\cdot \|A\|\end{aligned}}$

Такое же определение дается для любой операторной нормы (то есть определение зависит от выбора нормы):

$\mu (A)=||A||\cdot ||A^{-1}||$.

Если оператор $A^{-1}$ не ограничен, то числом обусловленности оператора $A$ обычно считают $\mu (A)=+\infty$.

С числом обусловленности связано множество утверждений и оценок теории вычислительной математики.

Если число обусловленности оператора $A$ мало́, то оператор называется хорошо обусловленным. Если же число обусловленности велико, то оператор называется плохо обусловленным. Таким образом, чем меньше $\mu (A)$, тем «лучше», то есть тем меньше погрешности решения будут относительно погрешностей в условии. Учитывая, что $\mu (A)\geqslant 1$, то наилучшим числом обусловленности является 1.

Пример

Дана система двух линейных уравнений: $\left\{{\begin{matrix}u+10v=11\\100u+1001v=1101\end{matrix}}\right.$

Решением является пара чисел $(1;1).$

«Возмутим» правую часть первого уравнения на 0,01 (вместо 11 напишем 11,01) и получим новую, «возмущённую» систему, решением которой является пара чисел $(11,\!01;0)$, сильно отличающаяся от решения невозмущённой системы. Здесь изменение значения одного параметра меньше чем на $0,\!1\%$ привело к относительно сильному возмущению решения.

Некоторые теоремы, связанные с числом обусловленности

Оценка относительной погрешности при замене уравнения близким

Рассмотрим два линейных уравнения:

$Au=f\qquad \qquad \qquad \qquad \ (1)$ — «основное» уравнение.

$(A+\Delta A)u=f+\Delta f\qquad (2)$ — «близкое» к нему.

Пусть $A$ — линейный ограниченный обратимый оператор, действующий из полного пространства $U$.

Пусть операторы $A^{-1},\Delta A$ также ограничены, и $||A^{-1}||\cdot ||\Delta A||<1$.

Пусть $u^{*}$ — решение уравнения (1), $u^{*}+\Delta u$ — решение уравнения (2).

Тогда ${\frac {||\Delta u||}{||u^{*}||}}\leqslant {\frac {\mu (A)}{1-\mu (A){\frac {||\Delta A||}{||A||}}}}\left({\frac {||\Delta A||}{||A||}}+{\frac {||\Delta f||}{||f||}}\right)$