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

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

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

<math>y=f(x)</math>

<math>y+\Delta y=f(x+\Delta x)</math>

<math>\mu(f):=\max_x \frac{\varepsilon_y}{\varepsilon_x} = \max_x \frac{\|\Delta y\| / \|y\|}{\|\Delta x\| / \|x\|}</math> при малых <math>\Delta x</math>Шаблон:Уточнить

где <math>\|\cdot\|</math> — норма или метрика соответственно в пространстве аргументов или значений.Шаблон:Уточнить

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

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

Как правило, если число обусловленности <math>\mu(f) = 10^{k}</math>, то вы можете потерять до k цифр точности сверх того, что будет потеряно для числового значения из-за потери точности из арифметических методов. <ref name="Numerical Mathematics and Computing, by Cheney and Kincaid">Шаблон:Книга</ref> Однако число обусловленности не дает точного значения максимальной погрешности, которая может возникнуть в алгоритме. Обычно это просто ограничивает его оценкой (чье вычисленное значение зависит от выбора нормы для измерения погрешности).

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

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

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

<math>Ax = b</math>,

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

<math> \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) .</math>

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

<math>\begin{align}

\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{align}</math>

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

<math>\mu(A) = ||A||\cdot||A^{-1}||</math>.

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

Пусть <math>u^*</math> — решение уравнения (1), <math>u^* + \Delta u</math> — решение уравнения (2).

Тогда <math> \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)</math>