반복 알고리즘의 수렴 속도와 오차
개념적 접근
반복 알고리즘을 설계할 때 어떤 점근적 거동을 갖는지 이해하려면 오차 분석을 통해 수렴 속도와 수렴 차수를 파악하는 것이 중요하다. 예를 들어 1차원 문제에서 어떤 근사를 $x_n$이라 하고, 해를 $x$라 할 때, 반복에 따라 $x_n$이 $x$로 가까워지는 형식을 정량화하는 과정이 필요하다. 이러한 분석을 통해 알고리즘이 주어진 문제 설정에서 효율적이며 안정적으로 동작하는지 확인할 수 있다.
어떤 반복 공식을 $x_{n+1} = g(x_n)$로 표현할 수 있다고 할 때, 수렴 여부는 일반적으로 $x^$라는 고정점이 존재하고 $g'(x^)$의 절댓값이 1보다 작으면 지역적으로 수렴한다고 알려져 있다. 정확한 수렴 속도는 $|g'(x^)|$의 크기에 의해 결정되며, $|g'(x^)|$이 매우 작으면 빠른 수렴을 기대할 수 있으나, 1에 가까우면 수렴 속도가 떨어질 수 있다. 이런 정성적 설명을 보완하기 위해 오차를 정의하고 그 오차의 거동이 어떻게 변화하는지를 살펴보아야 한다.
반복 과정에서 관심을 두는 주요 요소는 $x_n$이 참해 $x$에 얼마나 가까운가를 나타내는 오차 $e_n = x_n - x$이다. 적절한 상황에서 $e_n$이 특정 비율로 감소하는 형식을 취하거나, 어떤 지수적 혹은 근사 형태로 감소한다면 우리는 이를 통해 알고리즘의 효율성을 평가할 수 있다.
오차 정의
오차를 정의할 때는 여러 방법을 사용할 수 있다. 반복 알고리즘에서는 구하고자 하는 해가 스칼라값이든 벡터값이든 공통적으로 절대 오차와 상대 오차를 정의한다. 어떤 해를 나타내는 스칼라 변수가 $x$일 경우, $x_n$과 $x$의 차이를
로 두는 것이 일반적이다. 만약 이 크기가 매우 작아져야 할 문제 상황이라면, $|e_n|$이 임계값 이하가 될 때 반복을 중단하기도 한다.
벡터 방정식을 풀어야 한다면 $\mathbf{x} \in \mathbb{R}^m$이라 하고 반복 근사치를 $\mathbf{x}_n$이라 할 때 오차 벡터 $\mathbf{e}_n = \mathbf{x}_n - \mathbf{x}$를 고려할 수 있다. 이 경우엔 벡터 크기를 정의하기 위해 주어진 노름(norm)을 사용한다. 예를 들어 2-노름을 사용하면
와 같은 형태가 될 것이다. 알고리즘의 안정성과 수렴 속도를 논하기 위해선 이 노름이 반복마다 어떻게 변화하는지, 즉 $|\mathbf{e}_n|$이 어떤 추세를 보이는지가 핵심이다.
수렴 속도와 수렴 차수
수렴 속도는 반복 알고리즘에서 $n$이 증가함에 따라 $e_n$이 어떻게 줄어드는가를 의미한다. 예를 들어 단순 고정점 반복 방법에서, $g$가 충분히 미분 가능하며 $x^$ 근방에서 $|g'(x^)| < 1$이면 국소 선형 수렴을 기대할 수 있다. 간단히 말해,
로 근사할 수 있다. 여기에서 $|g'(x^*)| < 1$이면 $|e_{n+1}|$가 $|e_n|$에 비례해서 감소하므로 이를 선형 수렴이라 하며, 그 비례상수를 수렴률 또는 수렴계수라고 부른다.
더 나아가 뉴턴 방법이나 이분법 등의 다른 알고리즘에서는 더 높은 차수의 수렴 속도가 나타난다. 대표적으로 뉴턴 방법의 경우 $x^$에서 $f'(x^) \neq 0$이고 $f''(x^*)$이 유한하면 이론적으로 이차 수렴(quadratic convergence)이 성립한다. 이는
와 같은 형태가 되어, $|e_n|$이 반복될 때마다 제곱으로 줄어든다. 여기서 상수 $C$는 문제에 따라 달라지며, 보통 $C = \tfrac{|f''(\xi)|}{2|f'(x^*)|}$ 같은 형태의 값으로 표현된다.
보다 일반적으로 $p$차 수렴을 갖는 반복식이라 하면
가 되는 경우를 가정한다. 만약 $p=1$이면 선형 수렴이고, $p=2$ 이상이면 초선형 혹은 이차 이상의 수렴 형태로 구분한다. 이 정의를 이용하면 알고리즘 간의 효율성을 비교할 수 있으며, 특정 문제에서 원하는 해를 얻기까지 필요한 반복 횟수를 예측하는 데 도움이 된다.
수렴 반경과 안정성
반복 알고리즘의 수렴 반경은 초기값이 참해로부터 일정 범위 안에 있을 때만 수렴한다는 의미에서 정의될 수 있다. 예를 들어 단순 고정점 반복에서 $|g'(x^)|<1$만으로는 국소 수렴(local convergence)을 보장하지만, 전역적으로는 어떤 초기값에서 시작해도 반드시 $x^$로 수렴한다고 말하기 어렵다. 따라서 알고리즘 활용 시에는 초기값 설정이 중요한 이슈가 되며, 이 과정을 안정적으로 설계하기 위해서는 대상 함수나 방정식의 구조적 특성을 파악하고 있어야 한다.
아울러 해가 여러 개 존재하는 문제의 경우, 특정 반복 알고리즘이 어떤 해를 향해 수렴할지 사전에 알기 어렵다. 이를 명시적으로 파악하기 위해서는 함수의 변분(derivative) 특성을 면밀히 분석하거나 다양한 초기값을 실험하여 주요 고정점들의 위치를 추정하기도 한다. 벡터 방정식 혹은 비선형 시스템에서도 유사한 논리가 확장 적용되며, 해당 시스템의 야코비 행렬을 바탕으로 수렴 조건과 안정성 여부를 살펴보게 된다.
반복 알고리즘 시각화
원활한 이해를 위해 간단한 반복 과정을 도식으로 표현할 수도 있다
이 도식에서는 단순 고정점 형태의 반복 과정을 개략적으로 나타낸다. 초기값을 설정하고, 반복식 $x_{n+1} = g(x_n)$을 통해 새 근사값을 계산한 뒤, 오차가 충분히 작아졌는지 혹은 반복 제한 횟수에 도달했는지 판정한다. 일반적인 비선형 방정식, 선형 시스템 반복 해법, 혹은 미분방정식 수치해석에서의 시간 전진법 등 다양한 맥락에서 이러한 반복 구조가 나타난다.
오차 전파와 민감도
반복 알고리즘이 진행되는 동안 $e_n = x_n - x$가 어떻게 줄어드는지에 대한 분석은, 실제 계산 환경에서 발생하는 반올림 오차나 입력 데이터의 근소한 변화에 의해 알고리즘의 결과값이 얼마나 영향을 받는가를 평가하는 데도 유용하다. 예를 들어 선형 시스템을 반복적 방법으로 풀 때, 시스템 행렬이나 우변 벡터가 조금만 변해도 반복 알고리즘의 최종 결과가 크게 달라질 가능성이 있으면 조건수가 매우 크다고 할 수 있다. 이런 상황에선 반복 횟수가 늘어남에 따라 반올림 오차가 누적될 위험이 커질 수 있다.
여기서 조건수(condition number)는 선형 시스템 $\mathbf{A}\mathbf{x}=\mathbf{b}$의 경우
와 같은 형식으로 정의된다. 이 값이 크면 $\mathbf{A}$가 조금만 변해도 $\mathbf{x}$가 많이 변한다. 반복 알고리즘에서 해석적으로는 $\mathbf{x}_n$이 참해 $\mathbf{x}$에 수렴하더라도, 실제로는 작은 수치 오차 때문에 특정 수준 이하로 오차가 줄지 않거나 오히려 오차가 증폭되는 현상이 나타날 수 있다.
사전적(a priori) 오차 추정과 사후적(a posteriori) 오차 추정
반복 알고리즘을 쓸 때, $n$번째 반복에서의 해 $\mathbf{x}_n$가 갖는 오차 $|\mathbf{x}_n - \mathbf{x}|$를 이론적으로 미리 추정하는 방법과, 실제로 구한 해를 바탕으로 오차 한계를 추론하는 방법이 있다. 전자를 사전적(a priori) 오차 추정이라 하고, 후자를 사후적(a posteriori) 오차 추정이라 한다.
사전적 오차 추정은 각 단계에서의 오차가 시스템이나 함수의 미분 계수 등으로부터 계산 가능한 식으로 표현되며, 이를 통해 필요한 반복 횟수나 초기값 설정에 대한 가이드를 얻을 수 있다. 예를 들어 뉴턴 방법의 사전적 오차 추정은 대개
과 같이 주어지며, $C$는 문제의 2계 미분이나 야코비 등에 의해 결정된다.
사후적 오차 추정은 실제로 얻은 근사해 $\mathbf{x}_n$을 가지고 계산하거나, 알고리즘 내에 추가 정보를 이용하여 현재 해가 얼마나 정밀한지 평가한다. 예를 들어 비선형 방정식 $f(x) = 0$을 뉴턴 방법으로 풀 때, 반복 과정에서 $|f(x_n)|$의 크기를 보고 현재 근사해가 정밀하게 $f(x)=0$에 근접했는지 가늠할 수 있다. 때로는 문제 구조나 알고리즘 특성을 이용해 추가 계산 없이도 간단히 오차 상계를 제시하기도 한다.
고차 미분이 0이 되는 경우
뉴턴 방법의 이차 수렴을 예로 들면 $f'(x^)$가 0이 아니어야 이차 수렴 계수가 성립한다. 만일 $f'(x^)=0$이지만 $f''(x^*) \neq 0$이면 통상적인 이차 수렴 이론이 그대로 적용되지 않고, 수렴 차수가 달라질 수 있다. 실제로 특정 차수 이상의 미분계수가 0이 될 경우, 알고리즘의 점근적 거동이 바뀌어서 예기치 않은 저차 수렴으로 떨어지거나 다른 형태의 초선형 수렴을 보일 수 있다. 그러므로 반복 알고리즘 적용 전에는 문제 함수 혹은 시스템의 기초적 특성을 가능한 한 파악해 두는 것이 중요하다.
또 다른 관점에서, 고정점 반복 $x_{n+1} = g(x_n)$을 분석할 때 $g'(x^)=1$이면 선형 수렴 속도가 1에 가까운 느린 형태가 될 수 있다. 하지만 $g''(x^)$ 등에 의해 $x^*$에서의 전개가 달라지면, 초선형 또는 준이차 형태의 수렴으로 진행되는 경우도 있다. 이런 상황은 각 문제마다 특수하게 설정된 함수 구조에 따라 달라지므로, 일반적인 수렴율 분석은 보통 1계 미분이 1보다 작다는 조건에서 가장 간단하게 이루어진다.
반복 과정에서의 반올림 오차와 안정성
컴퓨터로 반복 알고리즘을 실제 구현하면 부동소수점 연산에 의한 반올림 오차가 필수적으로 발생한다. 고정소수점 연산을 가정해도 오차가 생기는 원리는 유사하다. 반복 횟수를 거듭할수록 적은 양의 오차가 누적되면, 수렴에 유리한 방향으로는 크게 문제 되지 않을 수 있으나, 역으로 악영향을 주면 오차가 증폭되거나 발산할 수도 있다.
실제 수치 계산에서 반올림 오차는 보통 $x_n$의 크기나 연산 횟수에 비례해 누적될 수 있어, 원하는 오차 이하로 충분히 근사해가 줄어드는 상황에서는 반올림 오차와 같은 하한선에 의해 $|e_n|$의 감소가 멈추는 현상이 발생한다. 이를 수치적 안정성(numerical stability) 관점에서 해석하면, 알고리즘 자체가 본질적으로 발산하지 않고 $x^*$에 도달하려는 성질이 있어도, 기계 오차(machine epsilon) 수준 근처로 더 이상 수렴하기 어려워지는 것이다.
메모리와 실행 시간 관점
반복 알고리즘을 설계할 때는 오차를 줄이는 것뿐 아니라, 반복 횟수가 많아질 때 발생하는 실행 시간 증가와 메모리 사용량도 고려해야 한다. 예를 들어 대규모 선형 시스템을 반복 해법으로 풀 때, 각 반복에서 대형 행렬-벡터 곱을 수행해야 하면 계산 비용이 매우 커질 수 있다. 이런 이유로 특정 알고리즘은 초기 단계에서 사전적 오차 추정을 통해 필요한 반복 횟수를 예측하거나, 수렴이 어느 정도 임계값 이하로 내려가면 중단하는 방식으로 구현하기도 한다.
오차를 극도로 줄이는 대신에 적절한 선에서 해를 근사하고, 이후 문제 구조를 고려해 후처리 기법 등을 적용하는 것이 전체 연산 부담을 크게 낮출 수도 있다. 많은 응용 분야에서 해가 약간의 오차를 허용해도 충분히 유효한 결과를 낼 수 있기 때문에, 이와 같은 실제적 관점에서 수렴 속도와 오차를 균형 있게 다루는 전략을 구사하는 것이 실무에서는 중요하다.
간단한 예제 코드(Python)
비선형 방정식 $f(x) = 0$을 간단한 예제로 들어, 뉴턴 방법을 Python으로 구현해볼 수 있다
이 코드는 보편적인 뉴턴 방법을 구현한 형태다. $f'(x)=0$에 가까워지면 분모가 0에 근접하므로 반복을 멈추도록 했고, 반복마다 $|x_{n+1} - x_n|$이 $tol$ 이하로 줄어들면 더 이상 진행하지 않는다. 실제로는 $|f(x_n)|$가 충분히 작아지는지 확인해 반복을 멈추는 방식도 자주 쓰인다. 이처럼 구현 단계에서 수렴 판정과 수치적 안전장치(예컨대 $f'(x)$가 0에 가까운지 확인)를 함께 고려해야 반복 알고리즘이 안정적으로 동작한다.
가속 기법과 초선형 수렴
반복 알고리즘의 선형 수렴 속도가 충분하지 않을 때, 외부에서 추가적인 연산을 통해 수렴 속도를 개선하는 여러 기법이 존재한다. 이를 일반적으로 ‘가속 기법(acceleration technique)’이라 부른다. 고정점 반복 $x_{n+1} = g(x_n)$이 선형 수렴을 보일 경우, 오차가 줄어드는 비율이 느리다면 가속 기법을 적용해 초선형 이상의 빠른 수렴을 기대할 수 있다.
고전적인 가속 기법 중 하나로 Aitken의 $\Delta^2$ 과정이 있다. 어떤 반복 열 ${x_n}$이 선형적으로 수렴하고 있다고 가정해보자. 이때 $x_n, x_{n+1}, x_{n+2}$를 이용해 새로운 근사값 $x_n^*$를 정의하는 식을 구성할 수 있으며, 이 과정에서 오차 항의 선형 잔여분을 제거해 준다는 아이디어가 핵심이다. Aitken의 $\Delta^2$ 과정을 간단히 표현해 보면,
를 정의한 뒤,
로 새로운 근사값을 얻는다. 이 방법은 반복 열이 충분히 매끄러운 형태로 선형에 가깝게 수렴한다면, 초선형적인 수렴 가속을 달성할 가능성이 있다.
비슷한 개념으로 Steffensen 방법이 있는데, 이는 고정점 반복 $x_{n+1}=g(x_n)$을 자체적으로 뉴턴 방법 수준으로 가속하려는 시도다. 구체적으로,
과 같은 형태로, Aitken의 $\Delta^2$ 과정을 단일 함수 $g$에 직접 적용해 얻는다. 이 기법을 잘 적용하면 초선형 이상의 빠른 수렴을 얻을 수 있으나, 각 반복에서 $g(x_n)$와 $g(g(x_n))$를 모두 계산해야 하므로 연산 비용이 다소 증가한다. 따라서 가속 기법을 적용할 때는, 실제 계산 비용과 가속으로 인한 반복 횟수 감소가 어떻게 트레이드오프를 이루는지 함께 고려해야 한다.
선형 시스템 반복 해법과 스펙트럴 반경
비선형 방정식뿐만 아니라, 선형 시스템에서도 반복 알고리즘을 구성해 해를 구할 수 있다. 예컨대 Jacobi, Gauss-Seidel, SOR 등의 고전적 반복 해법은
와 같은 선형 사상 형태로 표현된다. 여기서 $\mathbf{M}$은 문제 행렬 $\mathbf{A}$를 적절히 분해해 얻는 변형 행렬이며, $\mathbf{c}$는 우변 벡터나 전 단계 근사값 등에 의해 정해지는 상수 벡터다. 선형 반복 과정에서 수렴 여부와 수렴 속도는 일반적으로 $\mathbf{M}$의 스펙트럴 반경(spectral radius), 즉 고유값의 절댓값 중 최댓값인
에 의해 결정된다. 보통
이면 $\mathbf{x}_n$이 참해로 수렴하며, $\rho(\mathbf{M})$가 1에 가까울수록 느리게, 0에 가까울수록 빠르게 수렴한다. 이론적으로 $\rho(\mathbf{M}) < 1$이면 지수적(선형) 수렴을 보이며, 실제 오차 감소 속도는 대개 $\rho(\mathbf{M})$의 크기에 따라 결정된다.
다만, 실제 계산에선 $\mathbf{M}$의 고유값 계산이나 적절한 분해를 수행하기가 쉽지 않을 수 있다. 크기가 매우 큰 희소행렬을 다뤄야 할 때, Krylov 서브스페이스 기법(GMRES, CG 등)을 이용해 반복 알고리즘을 설계하기도 한다. 이때도 기본적으로 반복 과정의 수렴 거동은 시스템 행렬의 분광 특성(고유값 분포)과 직접적인 연관이 있다.
사후적 오차 바운드와 잔차 기반 평가
선형 반복 해법에서 특정 근사값 $\mathbf{x}_n$이 주어지면, $|\mathbf{r}_n|$이라 불리는 잔차(residual) 벡터의 크기를 통해 오차를 가늠할 수 있다. 잔차는
으로 정의되며, 만약 $\mathbf{x}_n$이 참해라면 $\mathbf{r}_n$은 완전히 0이 된다. 수많은 반복 해법과 사후적 오차 추정 기법은 이 잔차의 크기를 직접 확인하거나, 이 잔차가 알고리즘 내부적으로 어떻게 변하는지를 추적하여 현재 근사값이 얼마나 정확한지를 평가한다. 예를 들어
와 같은 형태의 오차 상계를 이론적으로 유도하기도 한다(조건수 $\kappa(\mathbf{A})$가 들어가는 이유는 민감도와 관련되어 있다).
실제 구현에서 잔차를 직접 구해가며 반복을 진행하면, 원하는 정확도에 도달할 때까지만 반복할 수 있어 연산 시간을 효율적으로 분배할 수 있다. 또한 수렴이 부진하거나 잔차가 오히려 증가하는 추세를 보인다면, 알고리즘 선택이나 사전적(또는 사후적) 가속 기법 등을 재검토할 필요가 있다.
복잡한 구조의 비선형 시스템
비선형 방정식이 하나가 아니라 여러 개 연립된 경우, 혹은 고차원에서 정의된 비선형 시스템에 대해 뉴턴 방법과 같은 반복 알고리즘을 적용하려면 야코비 행렬(편미분 계수들로 구성된 행렬)을 계산하고, 이를 빠르게 풀 수 있는 선형 해법이 필수적으로 뒷받침되어야 한다. 고차원 문제에서는 야코비 행렬 자체를 구성하기도 쉽지 않으며, 이를 위한 해석적 도출이 불가능할 때는 수치 근사(차분) 방법을 통해 야코비을 구한다.
하지만 고차원 문제에서 야코비 계산이 매 반복마다 필요한 뉴턴 방법은 비용이 매우 클 수 있으므로, Broyden 방법이나 다른 준뉴턴(quasi-Newton) 기법들을 고려하기도 한다. 이런 경우 반복 당 단계에서 야코비을 명시적으로 다시 계산하지 않고, 이전 단계들의 정보를 통해 점진적으로 야코비 또는 그 역행렬을 추정한다. 이로 인해 이차 수렴률은 보장되지 않을 수 있으나, 전반적인 연산 비용이 크게 감소하므로 실제 문제 규모가 큰 경우 매우 유용하다.
이러한 비선형 시스템에서도 동일하게 수렴 속도와 오차 분석을 다룬다. 다만 고차원일수록 초기값 선택과 알고리즘 안정화가 한층 까다롭다. 특정 초평면이나 초곡면 근처에서 야코비이 퇴화(degenerate) 상태가 되면, 단순 뉴턴 방법이 원활히 작동하지 않고 수렴률이 저하되거나 발산할 수도 있다. 이 때문에 미리 문제의 구조적 특성(예: 희소성, 대칭성, 양의 정부호성 등)을 면밀히 파악하고, 이에 최적화된 반복 해법을 구현하는 것이 중요하다.
사전조건 기법(preconditioning)과 반복 개선(iterative refinement)
반복 알고리즘에서 수렴 속도를 높이거나, 안정적으로 해를 얻기 위한 대표적 아이디어 중 하나는 사전조건(preconditioning)이다. 특히 대규모 선형 시스템을 반복적인 방식으로 푸는 상황에서, 행렬의 조건수가 매우 크면 수렴이 느려질 뿐 아니라, 수치적 오차가 쉽게 증폭될 위험이 있다. 이때 사전조건 행렬 $\mathbf{P}$를 도입해
같은 새로운 시스템으로 바꾼 뒤, 이 시스템을 반복적으로 푼다. $\mathbf{P}$는 $\mathbf{A}$의 분광 특성을 개선해 $\mathbf{P}^{-1}\mathbf{A}$가 보다 작은 스펙트럴 반경을 갖거나, 적어도 조건수가 훨씬 감소하도록 설계한다. 이 과정에서 $\mathbf{P}$는 계산이 너무 복잡하지 않아야 하며, 실제 연산에서 효율적인 곱셈이나 역행렬 연산이 가능해야 한다.
사전조건 기법을 적용한 뒤에도 Jacobi, Gauss-Seidel 또는 Krylov 서브스페이스 방법(GMRES, CG 등)을 동일하게 쓸 수 있다. 주요한 차이는, 알고리즘 각 단계에서 $\mathbf{A}$ 대신 $\mathbf{P}^{-1}\mathbf{A}$를 이용하거나, 혹은 $\mathbf{M}=\mathbf{P}^{-1}\mathbf{A}$ 형태로 바꾼 다음 반복식을 구성한다는 점이다. 이로 인해 수렴 속도가 크게 개선되거나, 같은 반복 횟수라도 오차 감소 효율이 좋아지기도 한다.
반복 개선(iterative refinement)은 다른 관점에서 적용할 수 있는 기법으로, 선형 시스템을 직접 풀이(예: LU 분해)하여 얻은 근사해가 있을 때, 이 근사해를 다시 입력으로 하여 작은 보정 과정을 반복함으로써 해의 정확도를 높이는 방법이다. 구체적으로
라는 잔차를 계산한 뒤, 이 잔차에 대해서 다시 시스템
을 풀어 보정값 $\Delta \mathbf{x}n$을 얻고, $\mathbf{x}{n+1} = \mathbf{x}_n + \Delta \mathbf{x}_n$로 업데이트한다. 만약 초기에 $\mathbf{x}_0$가 충분히 좋은 근사해라면, 반복할수록 오차가 줄어들 가능성이 높다. 특히 고정소수점이나 단정밀도(single precision) 연산으로 최초 근사해를 구한 뒤, 잔차 계산과 보정은 배정밀도(double precision)로 진행해 수렴 정확도를 높이는 혼합 정밀도(mixed precision) 기법도 현대 대규모 계산에서 자주 사용된다.
Krylov 서브스페이스 기법과 수렴 속도
현대적 반복 해법의 핵심 중 하나인 Krylov 서브스페이스 기법은 선형 시스템
을 풀기 위해, $\mathbf{r}_0 = \mathbf{b} - \mathbf{A}\mathbf{x}_0$로부터 시작하여
에 속하는 벡터로 근사해를 찾으려는 아이디어에 기반한다. 대표적으로 GMRES(Generalized Minimal Residual)나 CG(Conjugate Gradient) 방법 등이 널리 쓰이며, 대규모 희소행렬 문제에서 빠른 수렴과 적은 메모리 사용이 장점이다.
CG는 $\mathbf{A}$가 대칭 양의 정부호(symmetric positive definite)라는 조건에서 사용 가능하며, 각 반복 단계에서 직교 조건과 잔차 최소화를 동시에 달성하도록 알고리즘을 구성해 매우 효율적으로 작동한다. GMRES는 $\mathbf{A}$가 일반 정방행렬일 때 적용 가능하며, 반복마다 오차를 최소화하도록 근사해를 구하되, 정규직교화 과정에서 메모리 사용량이 증가한다는 단점도 있다.
이러한 Krylov 서브스페이스 기법에서도 수렴 속도는 스펙트럼(고유값 분포)과 깊은 관련이 있다. 적절한 사전조건 행렬을 이용해 고유값들이 좁은 구간에 모이도록 만들면, 반복 횟수가 크게 줄어드는 효과가 발생한다. 다만 실제로 좋은 사전조건 행렬을 찾기 위해서는 문제 구조를 이해해야 하고, 사전조건을 구성하는 과정에서도 추가 계산이 필요하다. 결국 전체 계산 시간을 최소화하기 위해 사전조건 비용과 반복 횟수 감소 효과 간의 균형점을 찾아야 한다.
불안정 모드(unstable mode)의 영향
반복 알고리즘에서 특정 근사해가 잘 수렴해 가다가도, 어떤 시점에서 미세한 수치 오차가 증폭되어 오차가 갑자기 커질 수 있다. 이를 불안정 모드(unstable mode)라고 부르기도 한다. 이는 알고리즘 내부에서 $(\mathbf{I} - \mathbf{M})$ 혹은 $(\mathbf{I} - \mathbf{A}^{-1}\mathbf{P})$ 형태의 연산자가 정밀도 한계나 특정 취소오차 때문에 매우 민감하게 반응하기 때문일 수 있다.
실제로 $\rho(\mathbf{M}) < 1$이라 할지라도, 근사치가 어떤 경계 영역에서 매우 작은 방향 벡터 성분에 대해 오류가 증폭되는 모드가 존재하면, 이로 인해 반복 과정에서 수렴이 지연되거나(오차가 잠시 증가) 최종적으로 정밀도를 떨어뜨릴 수도 있다. 이 문제를 완화하기 위해선 고른 방향으로 오차를 감소시키는 형태의 알고리즘을 설계하거나, 사전조건을 통해 $\mathbf{A}$의 고유치 분포를 균등하게 만들어야 한다. 때론 단순히 배정밀도 계산을 채택하는 것도 효과가 있다.
알고리즘 선택과 문제 특성
비선형 혹은 선형 반복 알고리즘을 실제 문제에 적용하려면, 먼저 문제 특성을 면밀히 살펴야 한다. 예를 들어
$\mathbf{A}$가 대칭 양의 정부호인지
야코비이나 미분계수를 명시적으로 구할 수 있는지
대규모 희소 행렬인지, 혹은 밀집 행렬인지
조건수가 매우 큰지, 복수의 해가 존재하는지
초기값에 따라 다른 해에 수렴할 가능성이 있는지
계산 환경(메모리, CPU, GPU 등)이 어떤 구조인지
등을 종합적으로 고려해야 한다. 문제에 적합한 반복 알고리즘과 사전조건, 가속 기법 등을 선택해야 최적의 성능과 안정성을 확보할 수 있다. 게다가 실제 응용 분야에서는 일정 수준의 오차를 허용하기도 하고, 추가적으로 물리적 또는 공학적 제약이 있어 해가 완전히 정확하지 않아도 되는 경우가 많다. 따라서 반복 알고리즘의 오차, 수렴 속도, 연산 비용을 균형있게 보며 적용하는 것이 중요하다.
Last updated