Номер состояния

Чувствительность функции к изменению аргумента

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

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

Задача с низким числом обусловленности называется хорошо обусловленной , в то время как задача с высоким числом обусловленности называется плохо обусловленной . В нематематических терминах плохо обусловленная задача — это задача, в которой при небольшом изменении входных данных ( независимых переменных ) происходит большое изменение ответа или зависимой переменной . Это означает, что правильное решение/ответ на уравнение становится трудно найти. Число обусловленности является свойством задачи. С задачей связано любое количество алгоритмов, которые можно использовать для решения задачи, то есть для вычисления решения. Некоторые алгоритмы обладают свойством, называемым устойчивостью к обратным результатам ; в общем случае можно ожидать, что устойчивый к обратным результатам алгоритм будет точно решать хорошо обусловленные задачи. Учебники по численному анализу дают формулы для чисел обусловленности задач и определяют известные устойчивые к обратным результатам алгоритмы.

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

Общее определение в контексте анализа ошибок

При наличии задачи и алгоритма с входными и выходными данными ошибка равна абсолютной ошибке , а относительная ошибка равна ${\displaystyle f}$ ${\displaystyle {\tilde {f}}}$ ${\displaystyle x}$ ${\displaystyle {\tilde {f}}(x),}$ ${\displaystyle \delta f(x):=f(x)-{\tilde {f}}(x),}$ ${\displaystyle \|\delta f(x)\|=\left\|f(x)-{\tilde {f}}(x)\right\|}$ ${\displaystyle \|\delta f(x)\|/\|f(x)\|=\left\|f(x)-{\tilde {f}}(x)\right\|/\|f(x)\|.}$

В этом контексте абсолютным числом условий проблемы является ^{[ необходимо разъяснение ]} ${\displaystyle f}$

${\displaystyle \lim _{\varepsilon \rightarrow 0^{+}}\,\sup _{\|\delta x\|\,\leq \,\varepsilon }{\frac {\|\delta f(x)\|}{\|\delta x\|}}}$

и относительное число состояний равно ^{[ необходимо разъяснение ]}

${\displaystyle \lim _{\varepsilon \rightarrow 0^{+}}\,\sup _{\|\delta x\|\,\leq \,\varepsilon }{\frac {\|\delta f(x)\|/\|f(x)\|}{\|\delta x\|/\|x\|}}.}$

Матрицы

Например, число условий, связанное с линейным уравнением Ax  =  b, дает границу того, насколько неточным будет решение x после аппроксимации. Обратите внимание, что это до того, как учитываются эффекты ошибки округления ; обусловленность является свойством матрицы , а не алгоритма или точности вычислений с плавающей точкой компьютера, используемого для решения соответствующей системы. В частности, следует думать о числе условий как о (очень грубо) скорости, с которой решение x будет изменяться по отношению к изменению b . Таким образом, если число условий велико, даже небольшая ошибка в b может вызвать большую ошибку в x . С другой стороны, если число условий мало, то ошибка в x не будет намного больше ошибки в b .

Число обусловленности определяется точнее как максимальное отношение относительной погрешности x к относительной погрешности b .

Пусть e будет ошибкой в ​​b . Предполагая, что A — невырожденная матрица, ошибка в решении A ⁻¹ b равна A ⁻¹ e . Отношение относительной ошибки в решении к относительной ошибке в b равно

${\displaystyle {\frac {\left\|A^{-1}e\right\|}{\left\|A^{-1}b\right\|}}/{\frac {\|e\|}{\|b\|}}={\frac {\left\|A^{-1}e\right\|}{\|e\|}}{\frac {\|b\|}{\left\|A^{-1}b\right\|}}.}$

Максимальное значение (для ненулевых b и e ) тогда представляется как произведение двух операторных норм следующим образом:

${\displaystyle {\begin{aligned}\max _{e,b\neq 0}\left\{{\frac {\left\|A^{-1}e\right\|}{\|e\|}}{\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right\}&=\max _{e\neq 0}\left\{{\frac {\left\|A^{-1}e\right\|}{\|e\|}}\right\}\,\max _{b\neq 0}\left\{{\frac {\|b\|}{\left\|A^{-1}b\right\|}}\right\}\\&=\max _{e\neq 0}\left\{{\frac {\left\|A^{-1}e\right\|}{\|e\|}}\right\}\,\max _{x\neq 0}\left\{{\frac {\|Ax\|}{\|x\|}}\right\}\\&=\left\|A^{-1}\right\|\,\|A\|.\end{aligned}}}$

То же самое определение используется для любой последовательной нормы , т.е. той, которая удовлетворяет

${\displaystyle \kappa (A)=\left\|A^{-1}\right\|\,\left\|A\right\|\geq \left\|A^{-1}A\right\|=1.}$

Когда число условий равно единице (что может произойти только в том случае, если A является скалярным кратным линейной изометрии ), то алгоритм решения может найти (в принципе, если алгоритм не вносит собственных ошибок) приближение решения, точность которого не хуже точности данных.

Однако это не означает, что алгоритм быстро сойдется к этому решению, а лишь то, что он не будет произвольно расходиться из-за неточности исходных данных (обратная ошибка), при условии, что прямая ошибка, вносимая алгоритмом, также не расходится из-за накапливающихся промежуточных ошибок округления. ^{[ необходимо разъяснение ]}

Число условий также может быть бесконечным, но это означает, что задача некорректно поставлена ​​(не имеет единственного, четко определенного решения для каждого выбора данных; то есть матрица необратима ) , и нельзя ожидать, что какой-либо алгоритм надежно найдет решение.

Определение числа обусловленности зависит от выбора нормы , что можно проиллюстрировать двумя примерами.

Если — матричная норма, индуцированная (векторной) евклидовой нормой (иногда называемой нормой L ² и обычно обозначаемой как ), то ${\displaystyle \|\cdot \|}$ ${\displaystyle \|\cdot \|_{2}}$

${\displaystyle \kappa (A)={\frac {\sigma _{\text{max}}(A)}{\sigma _{\text{min}}(A)}},}$

где и — максимальные и минимальные сингулярные значения соответственно . Следовательно: ${\displaystyle \sigma _{\text{max}}(A)}$ ${\displaystyle \sigma _{\text{min}}(A)}$ ${\displaystyle A}$

• Если — нормальное , то где и — максимальные и минимальные (по модулю) собственные значения соответственно . ${\displaystyle A}$ $${\displaystyle \kappa (A)={\frac {\left|\lambda _{\text{max}}(A)\right|}{\left|\lambda _{\text{min}}(A)\right|}},}$$ ${\displaystyle \lambda _{\text{max}}(A)}$ ${\displaystyle \lambda _{\text{min}}(A)}$ ${\displaystyle A}$
• Если унитарно , то ${\displaystyle A}$ ${\displaystyle \kappa (A)=1.}$

Число обусловленности относительно L2 так часто возникает в числовой линейной алгебре ^, что ему дали название — число обусловленности матрицы .

Если — матричная норма, индуцированная (векторной) нормой и являющаяся нижнетреугольной невырожденной (т.е. для всех ), то ${\displaystyle \|\cdot \|}$ ${\displaystyle L^{\infty }}$ ${\displaystyle A}$ ${\displaystyle a_{ii}\neq 0}$ ${\displaystyle i}$

${\displaystyle \kappa (A)\geq {\frac {\max _{i}{\big (}|a_{ii}|{\big )}}{\min _{i}{\big (}|a_{ii}|{\big )}}}}$

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

Число обусловленности, вычисленное с помощью этой нормы, как правило, больше числа обусловленности, вычисленного относительно евклидовой нормы , но его можно оценить проще (и часто это единственное практически вычислимое число обусловленности, когда решаемая задача включает нелинейную алгебру ^{[ необходимо разъяснение ]} , например, при аппроксимации иррациональных и трансцендентных функций или чисел численными методами).

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

Часто говорят, что матрица, которая не является обратимой, имеет число обусловленности, равное бесконечности. В качестве альтернативы, ее можно определить как , где — псевдообратная матрица Мура-Пенроуза . Для квадратных матриц это, к сожалению, делает число обусловленности прерывистым, но это полезное определение для прямоугольных матриц, которые никогда не являются обратимыми, но все еще используются для определения систем уравнений. ${\displaystyle \kappa (A)=\|A\|\|A^{\dagger }\|}$ ${\displaystyle A^{\dagger }}$

Нелинейный

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

Одна переменная

Число обусловленности дифференцируемой функции одной переменной как функции равно . Оцененное в точке , это равно ${\displaystyle f}$ ${\displaystyle \left|xf'/f\right|}$ ${\displaystyle x}$

${\displaystyle \left|{\frac {xf'(x)}{f(x)}}\right|=\left|{\frac {(\log f)'}{(\log x)'}}\right|.}$

Обратите внимание, что это абсолютное значение эластичности функции в экономике.

Наиболее элегантно это можно понимать как ( абсолютное значение ) отношение логарифмической производной , которая равна , и логарифмической производной , которая равна , что дает отношение . Это потому, что логарифмическая производная — это бесконечно малая скорость относительного изменения функции: это производная, масштабированная значением . Обратите внимание, что если функция имеет ноль в точке, ее число обусловленности в этой точке бесконечно, поскольку бесконечно малые изменения на входе могут изменить выход с нуля на положительный или отрицательный, что дает отношение с нулем в знаменателе, следовательно, бесконечное относительное изменение. ${\displaystyle f}$ ${\displaystyle (\log f)'=f'/f}$ ${\displaystyle x}$ ${\displaystyle (\log x)'=x'/x=1/x}$ ${\displaystyle xf'/f}$ ${\displaystyle f'}$ ${\displaystyle f}$

Более конкретно, при небольшом изменении относительное изменение равно , тогда как относительное изменение равно . Взяв соотношение, получаем ${\displaystyle \Delta x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle [(x+\Delta x)-x]/x=(\Delta x)/x}$ ${\displaystyle f(x)}$ ${\displaystyle [f(x+\Delta x)-f(x)]/f(x)}$

${\displaystyle {\frac {[f(x+\Delta x)-f(x)]/f(x)}{(\Delta x)/x}}={\frac {x}{f(x)}}{\frac {f(x+\Delta x)-f(x)}{(x+\Delta x)-x}}={\frac {x}{f(x)}}{\frac {f(x+\Delta x)-f(x)}{\Delta x}}.}$

Последний член представляет собой разностное отношение (наклон секущей линии ), а взятие предела дает производную.

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

Несколько переменных

Числа условий могут быть определены для любой функции, отображающей ее данные из некоторой области (например, -кортежа действительных чисел ) в некоторую кодомен (например, -кортежа действительных чисел ), где и область, и кодомен являются банаховыми пространствами . Они выражают, насколько чувствительна эта функция к небольшим изменениям (или небольшим ошибкам) ​​в ее аргументах. Это имеет решающее значение при оценке чувствительности и потенциальных трудностей точности многочисленных вычислительных задач, например, поиска корня полинома или вычисления собственных значений . ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle f(x)}$

Число обусловленности в точке (в частности, его относительное число обусловленности ^[4] ) затем определяется как максимальное отношение дробного изменения к любому дробному изменению в в пределе, где изменение становится бесконечно малым: ^[4] ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle x}$ ${\displaystyle \delta x}$ ${\displaystyle x}$

${\displaystyle \lim _{\varepsilon \to 0^{+}}\sup _{\|\delta x\|\leq \varepsilon }\left[\left.{\frac {\left\|f(x+\delta x)-f(x)\right\|}{\|f(x)\|}}\right/{\frac {\|\delta x\|}{\|x\|}}\right],}$

где — норма в домене/кодомене . ${\displaystyle \|\cdot \|}$ ${\displaystyle f}$

Если дифференцируемо, то это эквивалентно: ^[4] ${\displaystyle f}$

${\displaystyle {\frac {\|J(x)\|}{\|f(x)\|/\|x\|}},}$

где ⁠ ⁠ ${\displaystyle J(x)}$ обозначает матрицу Якоби частных производных от при , а — индуцированная норма на матрице. ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle \|J(x)\|}$

Смотрите также

• Численные методы для линейных наименьших квадратов
• Численная стабильность
• Матрица Гильберта
• Некорректно поставленная задача
• Единственное значение
• Матрица Вильсона

Ссылки

1. Белсли, Дэвид А.; Кух, Эдвин ; Уэлш, Рой Э. (1980). «Число условий». Регрессионная диагностика: выявление влиятельных данных и источников коллинеарности . Нью-Йорк: John Wiley & Sons. стр. 100–104. ISBN 0-471-05856-4.
2. Песаран, М. Хашем (2015). «Проблема мультиколлинеарности». Эконометрика временных рядов и панельных данных . Нью-Йорк: Oxford University Press. С. 67–72 [с. 70]. ISBN 978-0-19-875998-0.
3. Чейни; Кинкейд (2008). Численная математика и вычисления. стр. 321. ISBN 978-0-495-11475-8.
4. Trefethen, LN; Bau, D. (1997). Численная линейная алгебра. SIAM. ISBN 978-0-89871-361-9.

Дальнейшее чтение

• Деммел, Джеймс (1990). «Ближайшие дефектные матрицы и геометрия плохой обусловленности». В Коксе, МГ; Хаммарлинге, С. (ред.). Надежные численные вычисления . Оксфорд: Clarendon Press. стр. 35–55. ISBN 0-19-853564-3.

Внешние ссылки

• Число обусловленности матрицы в Институте целостных численных методов
• Функция библиотеки MATLAB для определения числа условий
• Число условий – Энциклопедия математики
• Кто придумал число обусловленности матрицы? Ник Хайэм