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

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

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

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

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

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

Если матричная норма, индуцированная (векторной) евклидовой нормой ( ^иногда называемой нормой L2 и обычно обозначаемой как ), то ${\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 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\|}},}$

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

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

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

Рекомендации

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

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

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

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

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