📂알고리즘

수치적 알고리즘에서의 안정성

정의 ¹

상대오차와 가까움

1. 주어진 부동소수점 체계에서 작동하는 알고리즘이 데이터 $a$ 를 입력받아서 계산된 해^{computed solution} $\bar{w}$ 를 출력한다고 하자. 이 때, 정확한 해^{exact solution} $w$ 에 대해 $\left| w - \bar{w} \right| / \left| w \right|$ 을 상대오차^{relative error}라 한다.
2. 머신입실론 $\epsilon$ 에 대해, 상대오차가 다음과 같이 그리 크지 않은 상수 $c$ 와 $\epsilon$ 의 곱인 $c \epsilon$ 보다 작거나 같으면 $\bar{w}$ 는 $w$ 에 가깝다^close고 한다.
   $$ {\frac{ \left| w - \bar{w} \right| }{ \left| w \right| }} \le c \epsilon $$

전방안정성

3. 계산된 해가 정확한 해에 가깝다면, 알고리즘이 전방안정적^{forward stable}이라고 한다.

후방안정성

4. 데이터 $a$ 의 계산된 해 $\bar{w}$ 가, $a$ 에 가까운 $\tilde{a}$ 에 대한 정확한 해라면, 알고리즘이 후방안정적^{backward stable}이라고 한다.

수치행렬대수에서의 후방안정성

5. 어떤 행렬의 클래스를 $\mathcal{A}$ 라 하자. 각각의 $A \in \mathcal{A}$ 와 벡터 $\mathbf{b}$ 에 대한 선형시스템 $A \mathbf{x} = \mathbf{b}$ 을 풀기위한 수치적 알고리즘은, $\bar{A} \in \mathcal{A}$ 와 $\bar{\mathbf{b}}$ 가 $A \in \mathcal{A}$ 와 $\mathbf{b}$ 에 가깝다고 할 때 $A \mathbf{x} = \mathbf{b}$ 의 계산된 해인 $\bar{\mathbf{x}}$ 가 $\bar{A} \bar{\mathbf{x}} = \bar{\mathbf{b}}$ 를 만족하면 후방안정적이라 한다.

설명

소위 $\tilde{a}$ 는 살짝 섭동이 가해졌다^{slightly perturbed}고 하며, 알고리즘이 후방안정적이라는 말은 곧 데이터에 약간의 변화가 있어도 안정적으로 해를 구할 수 있다는 의미가 된다. 이 설명이 조금 어렵다면 차라리 수치행렬대수의 후방안정성으로 이해하는 게 좋은데, $\bar{\mathbf{x}}$ 는 $A$ 와 $\mathbf{b}$ 에서 계산되었음에도 불구하고 $\bar{A} \bar{\mathbf{x}} = \bar{\mathbf{b}}$ 의 정확한 해가 되고 있다. 여기서 후방^backward라는 표현은 단순히 해가 비슷하냐가 아니라, 뒤로 돌아가서 원래 문제의 해로써 제대로 기능하는지까지 고려했다는 의미가 된다.

보편적인 후방안정성과 수치선형대수의 후방안정성에서 다른 점은 $A \in \mathcal{A}$ 와 같이 행렬의 클래스를 생각한다는 것이다. 말은 좀 어렵지만 수치행렬대수적인 알고리즘이 가역행렬에 대한 것인지, 정부호행렬에 대한 것인지 등에 대한 조건은 일관되게 지켜줘야한다는 정도로만 받아들이면 된다. 이렇게 클래스에 대한 제한을 두지 않으면 애초에 알고리즘이 요구하는 조건을 어겨놓고서 후방안정적이지 않다고 우길 수 있다.