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

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

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

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 цифр точности сверх того, что будет потеряно для числового значения из-за потери точности из арифметических методов. [3] Однако число обусловленности не дает точного значения максимальной погрешности, которая может возникнуть в алгоритме. Обычно это просто ограничивает его оценкой (чье вычисленное значение зависит от выбора нормы для измерения погрешности).

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

Пусть задан ограниченный обратимый линейный оператор $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 и e.

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

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

«Возмутим» правую часть первого уравнения на 0,01 (вместо 11 напишем 11,01) и получим новую, «возмущённую» систему, решением которой является пара чисел {11,01; 0,00}, сильно отличающаяся от решения невозмущённой системы. Здесь изменение значения одного параметра меньше чем на $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)

Примечания

Belsley, David A.; Kuh, Edwin; Welsch, Roy E. The Condition Number // Regression Diagnostics: Identifying Influential Data and Sources of Collinearity (англ.). — New York: John Wiley & Sons, 1980. — P. 100—104. — ISBN 0-471-05856-4.
Pesaran, M. Hashem The Multicollinearity Problem // Time Series and Panel Data Econometrics (англ.). — New York: Oxford University Press, 2015. — P. 67—72 [p. 70]. — ISBN 978-0-19-875998-0.
Cheney; Kincaid. Numerical Mathematics and Computing (неопр.). — 2007. — ISBN 978-0-495-11475-8.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Belsley, David A.; Kuh, Edwin; Welsch, Roy E. The Condition Number // Regression Diagnostics: Identifying Influential Data and Sources of Collinearity (англ.). — New York: John Wiley & Sons, 1980. — P. 100—104. — ISBN 0-471-05856-4.

[2] Pesaran, M. Hashem The Multicollinearity Problem // Time Series and Panel Data Econometrics (англ.). — New York: Oxford University Press, 2015. — P. 67—72 [p. 70]. — ISBN 978-0-19-875998-0.

[Numerical_Mathematics_and_Computing,_by_Cheney_and_Kincaid-3] Cheney; Kincaid. Numerical Mathematics and Computing (неопр.). — 2007. — ISBN 978-0-495-11475-8.