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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

при малых

где  — норма или метрика соответственно в пространстве аргументов или значений.

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

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

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

Число обусловленности для линейных уравнений[править | править код]

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

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

,

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

Тогда число обусловленности характеризует, насколько велика будет погрешность решения при произвольных ненулевых b и e.

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

.

Если оператор не ограничен, то числом обусловленности оператора обычно считают .

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

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

Пример[править | править код]

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


Решением является пара чисел

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

Некоторые теоремы, связанные с числом обусловленности[править | править код]

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

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

 — «основное» уравнение.
 — «близкое» к нему.

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

Пусть операторы также ограничены, и .

Пусть  — решение уравнения (1),  — решение уравнения (2).

Тогда

Примечания[править | править код]

  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.
  3. Cheney; Kincaid. Numerical Mathematics and Computing (неопр.). — 2007. — ISBN 978-0-495-11475-8.