Номер условия

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

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

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

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

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

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

В этом контексте абсолютное число обусловленности проблемы $f$ является

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

и относительный номер состояния

$\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 равно

${\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 ) тогда рассматривается как произведение двух норм оператора следующим образом:

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

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

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

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

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

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

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

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

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

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

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

Число обусловленности по отношению к L ² возникает так часто в числовой линейной алгебре , что ему дают имя — число обусловленности матрицы .

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

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

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

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

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

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

Нелинейный

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

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

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

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

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

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

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

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

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

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

Имя	Символ	Номер условия
Сложение/вычитание	$x+a$	$\left|{\frac {x}{x+a}}\right|$
Скалярное умножение	$ax$	$1$
Разделение	$1/x$	$1$
Полиномиальный	$x^{n}$	$|n|$
Экспоненциальная функция	$e^{x}$	$|x|$
натурального логарифма Функция	$\ln(x)$	$\left|{\frac {1}{\ln(x)}}\right|$
Синусоидальная функция	$\sin(x)$	$|x\cot(x)|$
Функция косинуса	$\cos(x)$	$|x\tan(x)|$
Функция касательной	$\tan(x)$	$|x(\tan(x)+\cot(x))|$
Обратная функция синуса	$\arcsin(x)$	${\frac {x}{{\sqrt {1-x^{2}}}\arcsin(x)}}$
Обратная функция косинуса	$\arccos(x)$	${\frac {|x|}{{\sqrt {1-x^{2}}}\arccos(x)}}$
Функция обратного тангенса	$\arctan(x)$	${\frac {x}{(1+x^{2})\arctan(x)}}$

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

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

Число условий $f$ в какой-то момент $x$ (в частности, его относительный номер состояния ) затем определяется как максимальное соотношение дробного изменения $f(x)$ любому дробному изменению $x$, в пределе, когда изменение $\delta x$ в $x$ становится бесконечно малым:

$\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],$

где $\|\cdot \|$ является нормой в домене/кодомене $f$.

Если $f$ дифференцируемо, это эквивалентно:

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

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

См. также

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

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

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

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

• Число обусловленности матрицы в Институте целостных численных методов
• Библиотечная функция MATLAB для определения номера условия
• Номер условия - Математическая энциклопедия
• Кто изобрел матричное число состояния? Ник Хайэм