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

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

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

${\displaystyle y=f(x)}$

${\displaystyle y+\Delta y=f(x+\Delta x)}$

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

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

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

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

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

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

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

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

${\displaystyle Ax=b}$,

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

${\displaystyle {\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).}$

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

${\displaystyle {\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}}}$

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

Тогда ${\displaystyle {\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)}$