수치행렬대수에서의 조건수가 상대오차의 상한에 비례함을 증명
정의 1
주어진 행렬 $A \in \mathbb{R}^{m \times n}$ 에 대해, 조건수 $\kappa (A)$ 를 다음과 같이 정의한다. $$ \kappa(A) = \left\| A \right\| \left\| A^{\dagger} \right\| = {\frac{ \sigma_{1} }{ \sigma_{r} }} $$ 여기서 $\left\| \cdot \right\|$ 는 프로베니우스 놈, $A^{\dagger}$ 는 $A$ 의 유사역행렬이다. $\sigma_{k}$ 는 $A$ 의 $k$ 번째로 큰 특이값으로, $r \le \min (m, n)$ 은 $A$ 의 랭크다. $\kappa (A)$ 가 크면 $A$ 가 악조건 행렬ill-conditioned matrix, 작으면 호조건 행렬well-conditioned matrix이라고 한다.
정리
선형시스템 $A \mathbf{x} = \mathbf{b}$ 을 푸는 알고리즘의 상대오차 상한은 조건수에 비례한다. $$ \frac{\left\| \bar{\mathbf{x}} - \mathbf{x} \right\|}{\left\| \mathbf{x} \right\|} \le \varepsilon c \kappa(A) $$ 여기서 $\varepsilon > 0$ 은 충분히 작은 상수, 더 구체적으로는 머신입실론 $\epsilon$ 이라 보아도 무방하다. $c = c(A, \mathbf{b})$ 는 $A$ 와 $\mathbf{b}$ 의해 결정된다.
설명
언뜻 보면 일반적인 조건수와 수치행렬대수에서의 조건수는 전혀 다른 정의를 가진 것처럼 보인다. 행렬에 대한 조건수가 왜 저렇게 정의되는지는 다음의 증명을 살펴봐야 이해가 된다.
증명 2
$$ A \mathbf{x} = \mathbf{b} $$ $A \in \mathbb{R}^{m \times n}$ 와 $\mathbf{b} \in \mathbb{R}^{m}$ 에 대해 위와 같은 선형시스템을 푸는 알고리즘이 있다고 할 때, $m = n$ 이고 $A$ 가 가역행렬이 아닌 이상 최소제곱법을 쓰게 되는 것이고, $A$ 와 $\mathbf{b}$ 각각에 약간의 섭동perturbation $\varepsilon F$ 와 $\varepsilon \mathbf{f}$ 가 가해진다고 두어야 한다. $$ \left( A + \varepsilon F \right) \mathbf{x} = \mathbf{b} + \varepsilon \mathbf{f} $$ 이 때의 해는 $\varepsilon$ 에 종속되어 $\mathbf{x} = \mathbf{x}(\varepsilon)$ 라 둘 수 있고, $\mathbf{x} (0) = \mathbf{x}$ 다. $\mathbf{x}(\varepsilon)$ 는 $\varepsilon = 0$ 의 근방에서 미분가능하고, 이에 대한 테일러전개는 다음과 같다. $$ \mathbf{x}(\varepsilon) = \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) $$ 여기서 $\mathbf{x} ' (0)$ 는 $\varepsilon$ 에 대한 미분으로써 구할 수 있다. $$ \begin{align*} \left( A + \varepsilon F \right) \mathbf{x} \left( \varepsilon \right) =& \mathbf{b} + \varepsilon \mathbf{f} \\ \implies A \mathbf{x} ' \left( \varepsilon \right) + F \mathbf{x} \left( \varepsilon \right) + \varepsilon F \mathbf{x} ' \left( \varepsilon \right) =& \mathbf{f} \\ \implies A \mathbf{x} ' \left( 0 \right) + F \mathbf{x} \left( 0 \right) =& \mathbf{f} \\ \implies \mathbf{x} ' \left( 0 \right) =& A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \left( 0 \right) \right] \end{align*} $$ 이를 상대오차에 대해 나타내려 해보면, 놈의 삼각부등식 $|a-b| \le |a| + |b|$ 에 의해 다음의 부등식을 얻는다. $$ \begin{align*} \mathbf{x}(\varepsilon) =& \mathbf{x} + \varepsilon \mathbf{x} ' (0) + O \left( \varepsilon^2 \right) \\ \implies \mathbf{x}(\varepsilon) - \mathbf{x} =& \varepsilon A^{\dagger} \left[ \mathbf{f} - F \mathbf{x} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \end{align*} $$
일반화된 코시-슈바르츠 부등식: $$ \left\| \mathbf{x} \right\| \left\| \mathbf{y} \right\| \ge \left< \mathbf{x} , \mathbf{y} \right> $$
일반화된 코시-슈바르츠 부등식에 의해 다음의 보조부등식을 얻는다. $$ \begin{align*} \left\| \mathbf{b} \right\| \le& \left\| A \right\| \left\| \mathbf{x} \right\| \\ \implies {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} \le & {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} \end{align*} $$ 따라서 $\mathbf{x}$ 에 대한 상대오차는 다음과 같다. $$ \begin{align*} {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \left| \varepsilon \right| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{x} \right\| }} + \left\| F \right\| \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| \left\| A \right\| }{ \left\| \mathbf{b} \right\| }} + \left\| A \right\| {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \\ \implies {\frac{ \left\| \mathbf{x}(\varepsilon) - \mathbf{x} \right\| }{ \left\| \mathbf{x} \right\| }} \le & \varepsilon \left\| A \right\| \left\| A^{\dagger} \right\| \left[ {\frac{ \left\| \mathbf{f} \right\| }{ \left\| \mathbf{b} \right\| }} + {\frac{ \left\| F \right\| }{ \left\| A \right\| }} \right] + O \left( \varepsilon^2 \right) \end{align*} $$ 여기서 $\left\| F \right\| / \left\| A \right\|$ 와 $\left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$ 는 그 자체가 각각 $A$ 와 $\mathbf{b}$ 에 대한 상대오차로, $c = \left\| F \right\| / \left\| A \right\| + \left\| \mathbf{f} \right\| / \left\| \mathbf{b} \right\|$ 라 두고 충분히 작은 $\varepsilon$ 에 대해 $O \left( \varepsilon^2 \right)$ 를 무시하면 원하던 결과를 얻는다.
■