📂알고리즘

수치적 알고리즘에서의 조건수와 호조건, 악조건

정의

조건수 ¹

주어진 입력^input으로써의 문제^problem $a$ 에 대해, 알고리즘이 계산 결과로써 해^solution $w$ 를 출력^output한다고 하자. 데이터와 해는 놈 $\left\| \cdot \right\|$ 에 대해 크기를 잴 수 있으며, $\hat{a}$ 는 어떤 $\varepsilon > 0$ 에 대해 $\left| \hat{a} - a \right| \le \varepsilon \left| a \right|$ 를 만족하는 $a$ 의 근사값^{approximation}이라고 하자. $\hat{a}$ 에 대한 해가 $\hat{w}$ 이라고 할 때, 다음과 같이 상대오차와 $\varepsilon$ 의 비에 리미트 슈프리멈을 취한 값을 조건수^{condition number} $\kappa = \kappa (a)$ 라 한다. $$ \kappa(a) = \limsup_{\varepsilon \to 0} \left\{ \frac{\left\| \hat{w} - w \right\|}{\varepsilon \left\| w \right\|} : \left\| \hat{a} - a \right\| \le \varepsilon \left\| a \right\| \right\} $$

호조건과 악조건

조건수 $\kappa$ 가 크다면 악조건^{ill-conditioned}이라고 하고, 크지 않으면 호조건^{well-conditioned}이라 한다.

설명

엄밀한 의미에서 조건수는 쉽게 말해 데이터가 참값에 가까워짐에 따라서 오차도 잘 줄어가는지에 대한 척도라 할 수 있다. 조건수가 크다는 것은 입력의 오차 $\varepsilon$ 이 줄어드는 것에 비해 오차가 별로 줄어들지 않는다는 의미가 된다.

한편 수학도라면 그래서 조건수가 크다 작냐는 기준이 무엇이냐가 궁금할텐데, 정의에서 명시하지 않은 것에서 알 수 있다시피서 굳이 구체적인 수치를 기준을 제시하거나 하지는 않고 문제마다 다르게 생각해야한다. 어떤 임계점이 있어서 아슬아슬하게 악조건이라든가 하는 걸 다루는 일은 없으며, 악조건이면 아예 확실한 악조건을 다루는 것이 일반적이기 때문이다. 통계학에서는 15를 기준으로 삼기도 하지만, 역시 널리 쓰지는 건 아니다.

같이보기

• 수치행렬대수에서의 조건수