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

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

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

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

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

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

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

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

${\ Displaystyle \ lim _ {\ varepsilon \ rightarrow 0} \ sup _ {\ | \ delta x \ | \ leq \ varepsilon} {\ frac {\ | \ delta f \ |} {\ | \ 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 является скалярным кратным линейной изометрии ), тогда алгоритм решения может найти (в принципе, то есть, если алгоритм не вносит собственных ошибок) аппроксимацию решения. чья точность не хуже, чем у данных.

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

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

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

Если это норма определена в квадрате суммируемых пространства последовательностей л ² (которое совпадает с обычным расстоянием в стандартном евклидовом пространстве и, как правило , как отмечено ), то${\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.}$

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

Если - норма, определенная в пространстве последовательностей ℓ ∞ всех ограниченных последовательностей (которая соответствует максимуму расстояний, измеренных на проекциях в базовые подпространства и обычно обозначается как ), и является нижнетреугольной невырожденной (т. Е. ), То${\displaystyle \|\cdot \|}$ ${\displaystyle \|\cdot \|_{\infty }}$${\displaystyle A}$${\displaystyle \forall i,a_{ii}\neq 0}$

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

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

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

Нелинейный [ править ]

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

Одна переменная [ править ]

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

${\displaystyle \left|{\frac {xf'(x)}{f(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}$

Более непосредственно, учитывая небольшое изменение в , относительное изменение IS , в то время как относительное изменение является . Принимая соотношение доходности${\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 x+a}$	${\displaystyle \left|{\frac {x}{x+a}}\right|}$
Скалярное умножение	${\displaystyle ax}$	${\displaystyle 1}$
Разделение	${\displaystyle 1/x}$	${\displaystyle 1}$
Полиномиальный	${\displaystyle x^{n}}$	${\displaystyle |n|}$
Экспоненциальная функция	${\displaystyle e^{x}}$	${\displaystyle |x|}$
Функция натурального логарифма	${\displaystyle \ln(x)}$	${\displaystyle \left|{\frac {1}{\ln(x)}}\right|}$
Функция синуса	${\displaystyle \sin(x)}$	${\displaystyle |x\cot(x)|}$
Функция косинуса	${\displaystyle \cos(x)}$	${\displaystyle |x\tan(x)|}$
Касательная функция	${\displaystyle \tan(x)}$	${\displaystyle |x(\tan(x)+\cot(x))|}$
Обратная функция синуса	${\displaystyle \arcsin(x)}$	${\displaystyle {\frac {x}{{\sqrt {1-x^{2}}}\arcsin(x)}}}$
Функция обратного косинуса	${\displaystyle \arccos(x)}$	${\displaystyle {\frac {|x|}{{\sqrt {1-x^{2}}}\arccos(x)}}}$
Функция обратной тангенса	${\displaystyle \arctan(x)}$	${\displaystyle {\frac {x}{(1+x^{2})\arctan(x)}}}$

Несколько переменных [ править ]

Числа условий могут быть определены для любой функции, отображающей свои данные из некоторой области (например, -набора действительных чисел ) в некоторый codomain (например, -набор действительных чисел ), где и домен, и codomain являются банаховыми пространствами . Они показывают, насколько чувствительна эта функция к небольшим изменениям (или небольшим ошибкам) ​​в своих аргументах. Это имеет решающее значение при оценке чувствительности и потенциальных трудностей с точностью при решении многочисленных вычислительных задач, например, при нахождении полиномиального корня или вычислении собственных значений .${\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)\|}$

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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