규범 별 조건 번호 대 구성 요소 별 조건 번호
나는 수치 선형 대수 수업에 대한 강의 노트를 훑어보고 있는데,이 장에는 내가 잘 이해하지 못하는 조건 번호를 다루는 몇 가지 사항이 있습니다.
두 가지 유형의 조건 번호가 도입되며 첫 번째는
$\kappa_{1}({f(\boldsymbol{x})} ; \boldsymbol{x})=\frac{\|\boldsymbol{J}(\boldsymbol{x})\|}{\|\boldsymbol{f}(\boldsymbol{x})\| /\|\boldsymbol{x}\|}$
두 번째는
$\kappa_{2}(f(\boldsymbol{x}) ; \boldsymbol{x}) =\frac{\left|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right||\boldsymbol{x}|}{|f(\boldsymbol{x})|}$ .
첫 번째 질문은 두 가지의 차이점이 무엇입니까? 첫 번째 조건이 "비관적"결과를 제공 할 때 두 번째 조건 번호를 사용할 수 있다고 말하지만 이것은 나에게 매우 임의적 인 것 같습니다.
그런 다음 무한대 노름이 사용되고 출력이 사용되는 경우 두 번째 조건 번호가 첫 번째 조건 번호에 의해 제한 될 수 있음이 도출됩니다. $f$스칼라로 간주됩니다. 유도를 위해 그들은 다음 방정식을 사용했습니다.
$\kappa_{1, \infty}(f ; \boldsymbol{x})=\frac{\left\|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right\|_{\infty}\|\boldsymbol{x}\|_{\infty}}{|f(\boldsymbol{x})|}$.
Jacobian 행렬의 전치가 사용되었고 $J^T$ 다음과 같이 쓸 수있는 행 벡터입니다. $\left\|\boldsymbol{J}^{\mathrm{T}}(\boldsymbol{x})\right\|_{\infty}=\|\boldsymbol{J}(\boldsymbol{x})\|_{1}=\sum_{i=1}^{m}\left|[\boldsymbol{J}(\boldsymbol{x})]_{i}\right|$. 나는 우리가 왜 전치를 사용하는지 이해하지 못했습니다.$J$. 똑같이 할 수 있습니까?$x$ 아니면 거기에서 무한대 규범을 취해야합니까?
답변
두 조건 번호에 대한 정의가 서로 일치하지 않는 것 같습니다. 약간의 고집은 다른 저자가 Jacobian을 다르게 정의한다는 것입니다. 일부 사용 (A)$J_{ij} = \partial f_i / \partial x_j$ 기타 사용 (B) $J_{ij} = \partial f_j / \partial x_i$. 첫 번째 정의로 우리는$f(x+\Delta x) = f(x) + J(x) \Delta x + O(\|\Delta x\|^2)$ 그리고 두 번째로 우리는 $f(x+\Delta x) = f(x) + J^\top(x) \Delta x + O(\|\Delta x\|^2)$. 첫 번째 정의는 Jacobian의 정의 (A)를 사용하는 것으로 보이며 두 번째 정의는 제품에 대한 정의 (B)를 사용해야합니다.$|J^\top(x)||x|$잘 정의되어야합니다. 표준이$\|\cdot\|$ 전치 불변 $\|A\| = \|A^\top\|$어떤 정의를 사용하든 상관 없습니다. 서로 다른 저자들 사이에는 충분한 표기법 일관성이있어서 여기서 무슨 일이 일어나고 있는지 정확히 밝히기가 어렵습니다. 나는 인기있는 숫자 선형 대수 책 (Golub과 Van Loan, Trefethen과 Bau, Demmel, Higham)을 확인했고이 특정 정의를 사용하여 다른 어떤 책도 찾을 수 없었습니다. 이 정의 세트로 다른 소스를 찾을 수 있다면 나 (또는 다른 사람)가 더 도움을 줄 수 있습니다.
이제 주요 질문에 대해 말씀 드리겠습니다. 선형 연립 방정식의 대각선 시스템을 풀고 싶다고 가정합니다.
\ begin {equation} \ underbrace {\ begin {bmatrix} a & 0 \\ 0 & b \ end {bmatrix}} _ {= A} \ begin {bmatrix} x \\ y \ end {bmatrix} = \ begin { bmatrix} 1 \\ 1 \ end {bmatrix}. \ end {등식}
이것은 기능에 해당합니다 $f(a,b) = (a^{-1},b^{-1})$ Jacobian과 함께
$$ J(a,b) = -\begin{bmatrix} a^{-2} & 0 \\ 0 & b^{-2} \end{bmatrix} $$
표준이있는 $\|J(a,b)\| = \max(a^{-2},b^{-2})$ 연산자에서 $\infty$-표준. 앞으로 나아가 자$a > b > 0$ 그래서 $\|J(a,b)\| = b^{-2}$. 첫 번째 조건 번호는
$$ \kappa_1(f(a,b);(a,b)) = \frac{\|J(a,b)\|}{\|f(a,b)\|/\|(a,b)\|} = \frac{b^{-2}}{b^{-1}/ a} = \frac{a}{b}. $$
따라서 $a\gg b$,이 문제는 매우 상태가 좋지 않습니다. 이제 구성 요소 별 조건 번호를 살펴 보겠습니다.
$$ \kappa_2(f(a,b);(a,b)) = \frac{\begin{bmatrix} a^{-2} & 0 \\ 0 & b^{-2} \end{bmatrix}\begin{bmatrix}a\\ b\end{bmatrix}}{\begin{bmatrix} a^{-1} \\ b^{-1}\end{bmatrix}} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}. $$
나는 벡터의 요소 별 나눗셈을 사용하여 주어진이 정의를 보지 못했고, 나는 표준 성분 별 조건 번호가이 "벡터 조건 번호"의 표준이 될 것이라고 믿습니다. (예 :$\infty$-표준, $\kappa_2(f(a,b);(a,b)) = 1$.) 구성 요소 별 조건 번호를 사용하면 문제가 완벽하게 조건화 된 것처럼 보입니다! 여기서 무슨 일이 일어나고 있습니까?
표준 바닐라 표준 기준 조건 번호는 $f(x+\Delta x)$ 과 $f(x)$ 사이의 상대적인 오류와 비교할 $x$ 과 $x+\Delta x$. 구체적으로 특별히,
$$ \mbox{relative error in $에프$} \le \kappa \cdot (\mbox{relative error in $엑스$}) + \mbox{higher order terms}. $$
우리가 말하면 $(a+\Delta a, b+\Delta b)$ 상대 오류가 있습니다. $10^{-6}$ 에 $\infty$-실제 값과 비교되는 표준 $(a,b)$ 이것은 오류가 $\Delta a$ 과 $\Delta b$ 각 구성 요소에서 $10^{-6}\|(a,b)\| = 10^{-6}a$. 참고$a$ 이상 $10^6b$, 이것은 오류를 의미합니다. $\Delta b$ 보다 클 수 있습니다. $b$그 자체! 하지만 실제로 평가할 때$f$, $a^{-1}$ 훨씬 작습니다 $b^{-1}$ 그러나 $b$ 큰 오류에 의해 교란되었습니다 $\Delta b$ 따라서 상대 오류 $f$ (대부분의 상대적 오류에 의해 $b^{-1}$매우 높습니다. 실제로, 규범 별 상대 오차를 고려하면 벡터의 작은 구성 요소의 상대 오차가 매우 커질 수 있으며 다음과 같은 경우 이러한 큰 구성 요소 별 오류가 증폭 될 수 있습니다.$f$ 입력의 작은 항목에 따라 다릅니다.
많은 실제 설정에서 모든 구성 요소에 작은 상대 오차가있는 입력 벡터가 있습니다. 예를 들어 오류가$\Delta a$ 과 $\Delta b$ 임의의 실수를 근사한 결과 $a$ 과 $b$ 부동 소수점 숫자로, 우리는 $|\Delta a| \le \epsilon |a|$ 과 $|\Delta b| \le \epsilon |b|$ 작은 상수 $\epsilon$. 따라서, 마지막의 경우이 최악의 시나리오는 불가능하지만 우리는 경우 등 그 사용 기준을 증명 할 수있는 방법이 없습니다 만 가정이,$\|(\Delta a, \Delta b)\| \le \epsilon \|(a,b)\|$, 표시 할 방법이 없습니다. $\Delta b$ 상대적으로 작다 $b$. 구성 요소 별 조건 번호는 정확히이를 수행합니다. 이를 통해 입력의 작은 구성 요소 별 섭동과 관련된 문제의 조건을 측정 할 수 있으므로 입력 벡터에서 작은 값의 상대 오차를 훨씬 더 잘 제어 할 수 있습니다.
하루가 끝날 무렵, "첫 번째 조건이 '비관적'결과를 제공 할 때 두 번째 조건 번호를 사용할 수 있습니다."라는 줄을 말해야합니다. 구성 요소 별 조건이 언제 성공할지 여부를 명확하게 보여줄 포괄적 인 휴리스틱이 없기 때문입니다. 실질적으로 더 나은 오류 경계를 제공하지 않습니다. 그러나 내가 제시 한 예제가 어떻게 규범 적 컨디셔닝이 문제에 대해 오해의 소지가있는 비관적 오류 경계를 제공 할 수 있는지, 그리고 구성 요소 별 컨디셔닝이 더 현실적인 경계를 제공 할 수 있는지에 대한 예시가되기를 바랍니다.
표현 $\kappa_2$ 말이되지 않는 한 $f(x)$스칼라입니다. 주어진 표현$\kappa_1$ 과 $\kappa_2$ 정의가 아니라 정리입니다.
이 답변에서는 표준 상대 조건 번호와 구성 요소 상대 조건 번호를 엄격하게 정의합니다. 이것은 그들의 차이점을 명확히해야합니다.
허락하다 $\Omega \subseteq \mathbb{R}^n$ 공개 세트가 되십시오. $f : \Omega \rightarrow \mathbb{R}^m$ 그리고하자 $x \in \Omega$. 만약$x \not = 0$ 그리고 만약 $f(x) \not = 0$, 표준 상대 조건 번호 $\kappa_f^{nr}$다음과 같이 정의됩니다. 먼저 보조 함수 \ begin {equation} \ kappa_f ^ {nr} (x, \ delta) = \ sup \ left \ {\ frac {\ | f (x) -f (y) \ |} {\ | f (x) \ |} \ big / \ frac {\ | xy \ |} {\ | x \ |} \ : : \ : 0 <\ | xy \ | <\ 델타 \ | x \ | \권리 \}. \ end {equation} 여기서$\delta > 0$ 다음과 같은 숫자입니다. $$ \{ y \in \mathbb{R}^n \: : \: \|x\| < \delta \|x\|) \subseteq \Omega. $$ 기능이 $\delta \rightarrow \kappa_f^{nr}(x,\delta)$음수가 아니고 감소하지 않습니다. 그 한계는$$ \underset{\delta \rightarrow 0_.}{\lim} \kappa_f^{nr}(x,\delta) $$존재합니다. 이를 통해 표준 상대 조건 번호 를 정의 할 수 있습니다.$\kappa_f^{nr}$ 다음과 같이 $$ \kappa_f^{nr}(x) = \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{nr}(x,\delta).$$
표준 상대 조건 번호는 달성 할 수있는 표준 상대 오류에 엄격한 한계를 부과합니다. 만약$y \in \Omega$ 만족하다 $\|x-y\| \leq \delta \|x\|$, 다음 $$ \frac{\|f(x)-f(y)\|}{\|f(x)\|} = \left(\frac{\|f(x)-f(y)\|}{\|f(x)\|} \big/ \frac{\|x-y\|}{\|x\|}\right) \frac{\|x-y\|}{\|x\|} \leq \kappa_f^{nr}(x,\delta) \frac{\|x-y\|}{\|x\|} $$ 또한 $\delta$ 충분히 작 으면 $$ \kappa_f^{nr}(x,\delta) \approx \kappa_f^{nr}(x) $$좋은 근사치입니다. 다음보다 작은 표준 상대 오차를 기대할 수 없습니다.$$ \frac{\|f(x)-f(y)\|}{\|f(x)\|} \approx \kappa_f^{nr}(x,\delta) \frac{\|x-y\|}{\|x\|}. $$이 정의에서 다음과 같은 결과를 증명할 수 있습니다. 만약$f : \Omega \rightarrow \mathbb{R}^m$이다 도 지점에서 미분$x \in \Omega$, 다음 $$ \kappa_f^{nr}(x) = \frac{\|Df(x)\|\|x\|}{\|f(x)\|} $$ 어디 $Df(x) \in \mathbb{R}^{m \times n}$ 야 코비 행렬 $f$ 그 시점에 $x$. 명확하게 말하면$A = Df(x)$ 야 코비 행렬 $f$ ...에서 $x$, 다음 $a_{ij} = \frac{\partial f_i}{\partial x_j}(x)$.
이제 구성 요소 별 상대 조건 번호를 정의하기 위해 먼저 구성 요소 별 상대 오류를 정의합니다. 허락하다$x \in \mathbb{R}^n$ 목표 값을 표시하고 $y \in \mathbb{R}^n$근사치를 나타냅니다. 그런 다음 구성 요소 별 상대 오차는 \ begin {equation} \ rho (x, y) = \ max \ left \ {\ frac {| x_j-y_j |} {| x_j |} \ : : \ : j = 1, 2, \ dotsc, n \ right \}, \ end {equation} 여기서 우리는 \ begin {equation} \ frac {a} {b} = \ begin {cases} 0 & a = 0 을 포함하도록 분수의 일반적인 정의를 확장합니다. \ wedge b = 0, \\ \ infty & a> 0 \ wedge b = 0. \ end {cases} \ end {equation} 이제$x \in \Omega$ 그런 점이 $x_j \not = 0$ 모든 $j$ 과 $f_i(x) \not = 0$ 모든 $i$. 보조 기능을 정의하는 것으로 시작합니다.$\kappa_f^{cr}$ 주어진 $$ \kappa_f^{cr}(x,\delta) = \sup \left\{ \frac{\rho(f(x),f(y))}{\rho(x,y)} \: : \: 0 < \rho(x,y) < \delta \right\}. $$ 분명하다 $\delta \rightarrow \kappa_f^{cr}(x,\delta)$음이 아니고 감소하지 않는 함수입니다. 그 한계는$$ \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{cr}(x,\delta) $$존재하고 음이 아닙니다. 이를 통해 컴포넌트 별 상대 조건 수를 정의 할 수 있습니다.$f$ 다음과 같이 $$ \kappa_f^{cr}(x) = \underset{\delta \rightarrow 0_+}{\lim} \kappa_f^{cr}(x,\delta). $$구성 요소 별 상대 조건 번호는 달성 할 수있는 구성 요소 별 정확도에 엄격한 제한을 부과합니다. 만약$y \in \Omega$ 그런 $0 < \rho(x,y) < \delta$, 다음 $$ \rho(f(x),f(y)) = \left(\frac{\rho(f(x),f(y))}{\rho(x,y)}\right) \rho(x,y)\leq \kappa_f^{cr}(x,\delta) \rho(x,y). $$ 또한 $\delta$ 충분히 작 으면 $$ \kappa_f^{cr}(x,\delta) \approx \kappa_f{cr}(x) $$좋은 근사치입니다. 다음보다 작은 구성 요소 별 상대 오차를 기대할 수 없습니다.$$ \rho(f(x),f(y)) \approx \kappa_f^{cr}(x,\delta) \rho(x,y). $$정의에서 다음과 같은 결과를 증명할 수 있습니다. 만약$f$인 도 에서 미분$x \in \Omega$, 다음 $$ \kappa_f^{cr}(x) = \left \|\frac{|Df(x)||x|}{|f(x)|} \right\|_\infty. $$여기가 오른쪽에있는 부서가 있다는 사실에 감사하는 것이 중요합니다 componentwise 때를$f$ 벡터 함수입니다.
두 개의 조건 번호가 민감도를 측정한다는 것은 분명합니다. $f$입력 에 작은 변화가 있지만 "작은"의 다른 정의에 의존합니다. 만약$f$ 또한 스칼라 함수입니다. 즉, $m = 1$, 그러면 우리는 $$ \kappa_f^{cr}(x) = \left \|\frac{|Df(x)||x|}{|f(x)|} \right\|_\infty = \frac{\||Df(x)||x|\|_\infty}{|f(x)|} \leq \frac{\||Df(x)|\|_\infty\||x|\|_\infty}{\|f(x)\|_\infty} = \frac{\|Df(x)\|_\infty\|x\|_\infty}{\|f(x)\|_\infty} =\kappa_f^{nr}(x). $$이 경우 표준 상대 조건 번호가 항상 성분 별 조건 번호보다 큽니다. 그러나 나는 단순히 그들이 "작은"의 다른 정의를 사용하기 때문에 표준 상대 조건 번호가 구성 요소 별 조건 번호보다 더 비관적이라고 말하는 것은 약간 오해의 소지가 있다고 생각합니다.
문제가되는 기능의 영역과 공동 영역을 항상 명확하게 설명하면 많은 혼란을 피할 수 있습니다. 사실 함수는 실제로 트리플입니다. $(f,U,V)$ 도메인으로 구성 $U$, 공동 도메인 $V$ 그리고 규칙 $f$ 도메인의 정확한 요소에 할당하기 위해 $U$ 공동 도메인에 정확히 하나의 요소 $V$. 불행히도 확립 된 표기법은 규칙에만 초점을 맞추는 경향이 있습니다. $f$.
여기에 사용 된 구성 요소 별 상대 조건 번호의 정의는 Gohberg 및 Koltracht, SIAM J. Matrix Anal의 논문 "혼합, 구성 요소 및 구조화 된 조건 번호"에서 추출되었습니다. Appl., 14 (3), 페이지 688–704, 1993.