수치해석 (Numerical Analysis)

수치해석은 수학 문제의 근사적인 수치 해법을 연구하는 분야입니다. 해석적으로 풀기 어렵거나 불가능한 문제를 컴퓨터를 이용하여 근사적으로 풀 수 있습니다. 이 분야는 공학, 과학, 금융 등 실질적으로 모든 응용 수학 분야의 기반이 됩니다.

이런 곳에 쓰여요

선수 지식: 미적분학, 선형대수학

난이도: ★★★★☆ (대학교)

부동소수점 표현

컴퓨터는 실수를 유한한 비트로 표현하기 때문에, 모든 실수를 정확하게 나타낼 수 없습니다. 이 한계가 수치 계산의 근본적인 오차 원인이 됩니다.

IEEE 754 표준

IEEE 754는 부동소수점 수의 표현과 연산을 정의하는 국제 표준입니다. 부동소수점 수는 다음과 같이 표현됩니다.

여기서 $s$는 부호 비트, $m$은 가수(mantissa/significand), $e$는 지수(exponent)입니다.

기계 엡실론 (Machine Epsilon)

기계 엡실론 $\epsilon_{\text{mach}}$은 $1 + \epsilon > 1$을 만족하는 가장 작은 부동소수점 수입니다. 이는 부동소수점 산술의 상대 정밀도를 나타냅니다.

여기서 $t$는 가수 비트 수(숨겨진 비트 포함)입니다.

임의의 실수 $x$를 부동소수점 수 $\text{fl}(x)$로 표현할 때, 반올림에 의한 상대 오차는 다음을 만족합니다.

유효숫자 (Significant Digits)

근사값 $\hat{x}$가 참값 $x$에 대해 $t$자리 유효숫자를 갖는다는 것은 다음을 의미합니다.

오차 분석

오차의 종류

절대오차와 상대오차

참값 $x$에 대한 근사값 $\hat{x}$의 오차를 두 가지로 측정합니다.

• 절대 오차 (Absolute Error): $E_{\text{abs}} = |x - \hat{x}|$
• 상대 오차 (Relative Error): $E_{\text{rel}} = \dfrac{|x - \hat{x}|}{|x|}$ (단, $x \neq 0$)

전방 오차와 후방 오차

문제를 함수 $f$로, 알고리즘의 계산 결과를 $\hat{y}$라 하면:

• 전방 오차 (Forward Error): 계산된 답과 정확한 답의 차이 $$\Delta y = |\hat{y} - f(x)|$$
• 후방 오차 (Backward Error): 계산된 답이 정확한 답이 되도록 하는 입력의 섭동 $$\Delta x = \min\{|\delta x| : f(x + \delta x) = \hat{y}\}$$

알고리즘이 후방 안정(backward stable)하다는 것은, 계산된 결과가 약간 섭동된 입력에 대한 정확한 답이라는 의미입니다. 즉, 후방 오차가 기계 엡실론 수준으로 작습니다.

조건수 (Condition Number)

문제의 조건수는 입력의 작은 변화가 출력에 얼마나 큰 영향을 미치는지를 나타내는 척도입니다.

함수의 조건수: 함수 $f$에서 $x$에서의 (상대) 조건수는

행렬의 조건수: 행렬 $A$의 조건수는

여기서 $\|\cdot\|$는 적절한 행렬 노름입니다. $\kappa(A) \geq 1$이며:

• $\kappa(A) \approx 1$: 양조건(Well-conditioned) — 입력 변화에 안정적
• $\kappa(A) \gg 1$: 악조건(Ill-conditioned) — 작은 입력 변화가 큰 출력 변화를 유발

선형 시스템에서의 의미: $A\mathbf{x} = \mathbf{b}$를 풀 때, 입력 $\mathbf{b}$에 상대적 섭동 $\frac{\|\delta \mathbf{b}\|}{\|\mathbf{b}\|}$가 있으면 해의 상대적 섭동은 다음으로 한정됩니다.

비선형 방정식의 근

$f(x) = 0$의 근을 수치적으로 찾는 방법들입니다. 각 방법의 수렴 속도, 장단점, 실패 조건을 비교하여 이해하는 것이 중요합니다.

이분법 (Bisection Method)

원리: 중간값 정리에 기반합니다. $f$가 $[a, b]$에서 연속이고 $f(a) \cdot f(b) < 0$이면, $(a, b)$ 안에 적어도 하나의 근이 존재합니다.

알고리즘:

1. 중점 $c = \dfrac{a + b}{2}$ 계산
2. $f(c) = 0$이면 $c$가 근, 종료
3. $f(a) \cdot f(c) < 0$이면 $b \leftarrow c$, 아니면 $a \leftarrow c$
4. $|b - a| < \varepsilon$ (허용 오차)이 될 때까지 반복

수렴 분석: $n$번 반복 후 구간 길이는 $\dfrac{b - a}{2^n}$이므로, 오차 한계는

허용 오차 $\varepsilon$ 이내로 수렴하는 데 필요한 반복 횟수:

수렴 차수는 선형(1차)이며, 매 반복마다 정확도가 약 1비트씩 늘어납니다.

뉴턴법 (Newton's Method)

유도: $f(x)$를 현재 근사값 $x_n$ 근처에서 1차 테일러 전개하면

$f(x) = 0$으로 놓고 $x$에 대해 풀면 다음 반복 공식을 얻습니다.

기하학적 해석: $(x_n, f(x_n))$에서의 접선이 $x$축과 만나는 점을 다음 근사값으로 사용합니다.

수렴 정리: $f(x^*) = 0$, $f'(x^*) \neq 0$ (단근), $f''$가 연속이면, 충분히 $x^*$에 가까운 초기값에서 뉴턴법은 이차 수렴합니다.

예시: $f(x) = x^2 - 2$ ($\sqrt{2}$ 구하기)에서 $x_0 = 1$로 시작하면

이차 수렴의 위력: 4번 반복만에 12자리 정확도를 달성합니다.

실패 조건:

• $f'(x_n) = 0$: 접선이 수평 — 다음 반복을 계산할 수 없음
• $f'(x_n) \approx 0$: 다음 반복값이 매우 멀어져 발산 가능
• 중근: $f'(x^*) = 0$이면 수렴 차수가 선형으로 감소. 이 경우 수정 뉴턴법 $x_{n+1} = x_n - m\frac{f(x_n)}{f'(x_n)}$ (근의 중복도 $m$) 사용
• 순환: 초기값에 따라 주기적으로 반복하며 수렴하지 않을 수 있음

세컨트법 (Secant Method)

뉴턴법에서 도함수 $f'(x_n)$을 차분으로 근사합니다.

이를 대입하면 반복 공식을 얻습니다.

초기값 2개 $(x_0, x_1)$이 필요하며, 매 반복에서 함수 평가 1회만 수행합니다 (뉴턴법은 $f$와 $f'$ 2회).

수렴 차수: 초수렴(superlinear)이며, 수렴 차수는 황금비 $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$입니다.

고정점 반복법 (Fixed-Point Iteration)

$f(x) = 0$을 $x = g(x)$ 형태로 변환한 뒤, 반복 $x_{n+1} = g(x_n)$을 수행합니다.

수렴 정리 (바나흐 고정점 정리): $g: [a,b] \to [a,b]$이 연속이고, 어떤 상수 $L < 1$에 대해 모든 $x, y \in [a,b]$에서

를 만족하면 ($g$가 축소 사상), $g$는 유일한 고정점 $x^*$를 가지며 임의의 $x_0 \in [a,b]$에서 반복이 수렴합니다.

오차 한계:

수렴 속도: $g'(x^*) \neq 0$이면 선형 수렴, $g'(x^*) = 0$이면 이차 이상의 수렴.

근 찾기 방법 비교

4가지 방법 직접 비교 — $x^3 - x - 2 = 0$

동일한 방정식 $f(x) = x^3 - x - 2 = 0$의 근 $x^* \approx 1.52138$을 4가지 방법으로 구한 결과를 비교합니다.

보간법

보간법(Interpolation)은 주어진 데이터 점 $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$을 모두 정확히 지나는 함수를 구성하는 방법입니다.

라그랑주 보간 (Lagrange Interpolation)

$n+1$개의 점을 지나는 최대 $n$차 다항식을 라그랑주 기저 다항식으로 표현합니다.

각 $L_i(x)$는 $L_i(x_i) = 1$이고 $j \neq i$일 때 $L_i(x_j) = 0$을 만족하므로, $P_n(x_i) = y_i$가 자동으로 성립합니다.

보간 오차: $f$가 $[a,b]$에서 $n+1$번 미분 가능하면

여기서 $\xi$는 $x$와 보간 노드를 포함하는 구간 안의 어떤 점입니다.

뉴턴 보간 (Newton's Divided Difference)

분할차분(Divided Difference)을 이용하여 점진적으로 구성할 수 있는 형태입니다.

분할차분의 정의:

장점: 새로운 데이터 점이 추가되면 기존 계수를 유지하고 항만 추가하면 되므로 효율적입니다. 계산 복잡도는 $O(n^2)$입니다.

에르미트 보간 (Hermite Interpolation)

에르미트 보간은 데이터 점에서 함수값뿐만 아니라 도함수 값까지 일치하는 다항식을 구성합니다.

$n+1$개의 점에서 함수값과 1차 도함수가 주어지면, $2n+1$차 다항식 $H_{2n+1}(x)$를 구합니다.

오차:

스플라인 보간 (Spline Interpolation)

고차 다항식 보간은 노드 사이에서 심하게 진동할 수 있습니다 (룽게 현상). 스플라인 보간은 구간별로 저차 다항식을 이어 붙여 이 문제를 해결합니다.

자연 3차 스플라인 (Natural Cubic Spline): 각 구간 $[x_i, x_{i+1}]$에서 3차 다항식 $S_i(x)$를 사용하되 다음 조건을 만족합니다.

• 보간 조건: $S_i(x_i) = y_i$, $S_i(x_{i+1}) = y_{i+1}$
• 매끄러움: 내부 노드에서 $S_i'(x_{i+1}) = S_{i+1}'(x_{i+1})$, $S_i''(x_{i+1}) = S_{i+1}''(x_{i+1})$
• 경계 조건 (자연 스플라인): $S''(x_0) = 0$, $S''(x_n) = 0$

$h_i = x_{i+1} - x_i$로 놓고 $M_i = S''(x_i)$라 하면, 각 구간에서의 스플라인은

$M_i$들은 삼중대각(tridiagonal) 선형 시스템을 풀어 구합니다.

4가지 보간법 직접 비교

데이터 점 $(0, 1)$, $(1, 2)$, $(2, 5)$, $(3, 10)$에 대해 네 가지 보간법을 적용하여 $x = 1.5$에서의 값을 추정합니다 (참값을 $f(x) = 1 + x + \frac{x(x-1)}{2} + \frac{x(x-1)(x-2)}{6}$로 가정).

보간법 비교 요약

수치 미분

도함수를 해석적으로 구하기 어려울 때, 함수값의 차분으로 근사합니다.

차분 공식

유도 (테일러 전개): $f(x+h) = f(x) + hf'(x) + \frac{h^2}{2}f''(x) + O(h^3)$이므로

중앙 차분의 유도: $f(x+h)$와 $f(x-h)$의 테일러 전개를 빼면

2차 도함수의 수치 근사

최적 스텝 크기

$h$를 줄이면 절단 오차는 감소하지만 반올림 오차는 증가합니다. 전방 차분에서 총 오차를 최소화하는 최적 $h$는

중앙 차분에서는

리처드슨 외삽 (Richardson Extrapolation)

같은 차분 공식을 서로 다른 스텝 크기 $h$와 $h/2$로 계산한 후, 절단 오차의 주요 항을 소거하여 더 높은 정확도를 얻는 기법입니다.

중앙 차분 $D(h)$의 오차가 $O(h^2)$이면:

이 결과는 $O(h^4)$ 정확도를 갖습니다.

고계 도함수의 수치 근사

3차 도함수와 4차 도함수의 중앙 차분 공식입니다.

수치 적분

정적분 $\int_a^b f(x)\,dx$를 근사적으로 계산합니다. 구간 $[a, b]$를 $n$등분하여 $h = \frac{b-a}{n}$, $x_k = a + kh$로 놓습니다.

사다리꼴 공식 (Trapezoidal Rule)

각 소구간에서 $f$를 1차식(직선)으로 근사합니다.

오차 공식:

오차 차수: $O(h^2)$. 즉, $h$를 절반으로 줄이면 오차가 약 $\frac{1}{4}$로 줄어듭니다.

심프슨 공식 (Simpson's Rule)

두 소구간씩 묶어 $f$를 2차식(포물선)으로 근사합니다. $n$은 짝수여야 합니다.

오차 공식:

오차 차수: $O(h^4)$. 3차 이하의 다항식은 정확하게 적분합니다.

가우스 구적법 (Gaussian Quadrature)

등간격 노드 대신 최적의 노드와 가중치를 선택하여 정밀도를 극대화합니다.

$n$개의 노드로 최대 $2n-1$차 다항식을 정확하게 적분할 수 있습니다.

가우스-르장드르 구적법: 노드 $x_i$는 $n$차 르장드르 다항식 $P_n(x)$의 근이며, 가중치는

처음 몇 개의 노드와 가중치:

일반 구간 $[a, b]$로의 변환: $x = \frac{b-a}{2}t + \frac{a+b}{2}$, $dx = \frac{b-a}{2}dt$를 적용합니다.

3가지 방법으로 같은 적분 풀기 — $\int_0^{\pi} \sin(x)\,dx$

정확한 값: $\int_0^{\pi}\sin(x)\,dx = [-\cos(x)]_0^{\pi} = 2$. $n = 4$ 구간($h = \pi/4 \approx 0.7854$)으로 세 방법을 비교합니다.

수치 적분 방법 비교

복합 구적법과 롬버그 적분

롬버그 적분(Romberg Integration)은 사다리꼴 공식에 리처드슨 외삽을 반복 적용하여 고정밀 결과를 얻는 방법입니다.

$R(1, 1)$은 심프슨 공식과 동일하며, $R(2, 2)$는 부울(Boole) 공식에 대응합니다.

상미분방정식의 수치해법

초기값 문제 $y' = f(t, y)$, $y(t_0) = y_0$를 수치적으로 풀 때, 시간 스텝 $h$로 이산화하여 $y_n \approx y(t_n)$을 구합니다.

전진 오일러 방법 (Forward/Explicit Euler)

가장 간단한 방법으로, 현재 점에서의 기울기로 다음 값을 예측합니다.

오차: 국소 절단 오차 $O(h^2)$, 전역 오차 $O(h)$ — 1차 방법입니다.

예시: $y' = -2y$, $y(0) = 1$ (해석해: $y = e^{-2t}$)을 $h = 0.1$로 풀면

후진 오일러 방법 (Backward/Implicit Euler)

다음 점에서의 기울기를 사용합니다 (음함수 방법).

매 스텝에서 비선형 방정식을 풀어야 하지만, 강성(stiff) 방정식에 대해 훨씬 안정적입니다.

개선된 오일러 방법 (Heun's Method / Modified Euler)

예측-수정(Predictor-Corrector) 접근법입니다.

이는 2차 룽게-쿠타 방법의 한 형태이며, 전역 오차는 $O(h^2)$입니다.

4차 룽게-쿠타 방법 (RK4)

가장 널리 사용되는 방법으로, 정확도와 효율의 균형이 뛰어납니다.

오차: 국소 절단 오차 $O(h^5)$, 전역 오차 $O(h^4)$. 매 스텝에서 함수 평가 4회가 필요합니다.

예시: $y' = -2y$, $y(0) = 1$을 $h = 0.1$로 RK4 적용:

정확값 $e^{-0.2} \approx 0.81873$과 소수점 이하 5자리까지 일치합니다.

4가지 방법으로 같은 ODE 풀기 — $y' = -2y$, $y(0) = 1$

해석해: $y(t) = e^{-2t}$. $h = 0.5$로 $t = 0$부터 $t = 2$까지 각 방법의 결과를 비교합니다.

적응적 스텝 크기 제어 (Adaptive Step Size)

고정 스텝 크기 대신, 국소 오차 추정에 따라 스텝 크기를 자동 조절하는 방법입니다.

임베디드 룽게-쿠타 방법 (RK45 / Dormand-Prince): 같은 $k_i$ 계산으로 4차와 5차 근사를 동시에 구합니다.

두 근사의 차이로 국소 오차를 추정합니다.

스텝 크기 조절:

• $\text{err} > \text{tol}$이면 현재 스텝을 거부하고 $h$를 줄여 재계산
• $\text{err} \leq \text{tol}$이면 현재 스텝을 수용하고 $h$를 키울 수 있음

장점: 해가 급변하는 구간에서는 스텝을 줄이고, 완만한 구간에서는 키움으로써 효율성과 정확도를 동시에 확보합니다.

다단계 방법 (Multistep Methods)

이전 여러 스텝의 정보를 활용하여 다음 값을 예측합니다.

아담스-배쉬포스 2단계 (Adams-Bashforth 2-step, AB2):

양함수 방법이며 스텝당 함수 평가 1회입니다. 전역 오차 $O(h^2)$.

아담스-멀턴 2단계 (Adams-Moulton 2-step, AM2) — 사다리꼴 방법:

음함수 방법이며 전역 오차 $O(h^2)$이지만, 안정성이 월등합니다.

ODE 수치해법 비교

강성 방정식 (Stiff Equations)

해 자체는 완만하게 변하지만, 시스템의 고유값 비율이 극단적으로 큰 경우를 강성(stiff) 문제라 합니다.

강성 문제에서 양함수 방법은 안정성을 위해 매우 작은 $h$를 사용해야 하므로 비효율적입니다. 음함수 방법(후진 오일러, BDF 등)이나 특수 설계된 방법(DIRK, SDIRK)을 사용해야 합니다.

선형계의 수치 해법

$A\mathbf{x} = \mathbf{b}$ ($A$는 $n \times n$ 행렬)를 수치적으로 풀 때, 크게 직접법과 반복법으로 나뉩니다.

가우스 소거법 (Gaussian Elimination)

행렬을 상삼각 형태로 변환한 후 후진 대입(back substitution)으로 해를 구합니다.

연산 횟수: $\frac{2}{3}n^3 + O(n^2)$ — $O(n^3)$

부분 피벗팅 (Partial Pivoting): 각 단계에서 현재 열의 아래쪽 원소 중 절대값이 가장 큰 것을 피벗으로 선택합니다. 이는 수치적 안정성을 위해 필수적입니다.

부분 피벗팅이 필요한 이유: 피벗이 0에 가까우면 소거 과정에서 곱해지는 수가 매우 커져 반올림 오차가 증폭됩니다. 예를 들어,

피벗팅 없이 풀면 유한 정밀도에서 $x_2 \approx 1$, $x_1 \approx 0$을 얻지만, 행을 교환하면 정확한 답 $x_1 \approx 1$, $x_2 \approx 1$을 얻습니다.

LU 분해

$A = LU$ (또는 피벗팅 포함 $PA = LU$)로 분해하면, $A\mathbf{x} = \mathbf{b}$를 두 단계로 풀 수 있습니다.

1. 전진 대입: $L\mathbf{y} = \mathbf{b}$를 풀어 $\mathbf{y}$ 구함 — $O(n^2)$
2. 후진 대입: $U\mathbf{x} = \mathbf{y}$를 풀어 $\mathbf{x}$ 구함 — $O(n^2)$

분해 자체는 $O(n^3)$이지만, 한 번 분해하면 여러 우변 $\mathbf{b}$에 대해 $O(n^2)$으로 풀 수 있습니다.

촐레스키 분해: $A$가 대칭 양의 정부호(SPD)이면 $A = LL^T$로 분해 가능하며, 연산량이 LU 분해의 약 절반($\frac{1}{3}n^3$)입니다.

반복법

대규모 희소 행렬에서 직접법은 비효율적일 수 있으므로, 반복법이 선호됩니다. $A = D - L - U$ (대각, 엄격한 하삼각, 엄격한 상삼각)로 분할합니다.

야코비 반복법 (Jacobi Method)

성분별로 쓰면:

특징: 각 성분을 독립적으로 계산하므로 병렬화가 용이합니다.

가우스-자이델 반복법 (Gauss-Seidel Method)

성분별로 쓰면:

이미 갱신된 $x_j^{(k+1)}$을 즉시 사용하므로 야코비보다 일반적으로 빠르게 수렴합니다.

SOR (Successive Over-Relaxation)

가우스-자이델에 이완 계수 $\omega$를 도입하여 수렴을 가속합니다.

• $\omega = 1$: 가우스-자이델과 동일
• $1 < \omega < 2$: 과이완 (overrelaxation) — 수렴 가속
• $0 < \omega < 1$: 저이완 (underrelaxation) — 발산하는 경우 안정화

최적 $\omega$를 찾으면 수렴 속도가 크게 향상되지만, 최적값은 문제에 의존합니다.

수렴 조건:

직접법 vs 반복법 — 같은 시스템으로 비교

다음 시스템을 직접법(LU 분해)과 반복법(야코비, 가우스-자이델)으로 풀어 비교합니다.

정확한 해: $x_1 = 5$, $x_2 = 5$, $x_3 = \frac{15}{4} = 3.75$.

선형계 해법 비교 요약

켤레 기울기법 (Conjugate Gradient Method)

대칭 양의 정부호(SPD) 행렬에 대한 가장 효율적인 반복법입니다. $A\mathbf{x} = \mathbf{b}$를 이차 함수 $\phi(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T A\mathbf{x} - \mathbf{b}^T\mathbf{x}$의 최솟값 문제로 봅니다.

알고리즘:

1. $\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0$, $\mathbf{p}_0 = \mathbf{r}_0$
2. $\alpha_k = \frac{\mathbf{r}_k^T \mathbf{r}_k}{\mathbf{p}_k^T A \mathbf{p}_k}$
3. $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k$
4. $\mathbf{r}_{k+1} = \mathbf{r}_k - \alpha_k A \mathbf{p}_k$
5. $\beta_k = \frac{\mathbf{r}_{k+1}^T \mathbf{r}_{k+1}}{\mathbf{r}_k^T \mathbf{r}_k}$
6. $\mathbf{p}_{k+1} = \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k$

정확한 산술에서는 최대 $n$번 반복으로 정확한 해를 구합니다. 수렴 속도는 조건수에 의존합니다.

고유값 계산

행렬 $A$의 고유값과 고유벡터를 수치적으로 구하는 방법입니다.

거듭제곱법 (Power Method)

절대값이 가장 큰 고유값(지배적 고유값, dominant eigenvalue) $\lambda_1$과 대응 고유벡터를 구합니다.

알고리즘:

1. 임의의 초기 벡터 $\mathbf{v}^{(0)}$ 선택 (영벡터가 아닌)
2. $\mathbf{w}^{(k+1)} = A\mathbf{v}^{(k)}$
3. $\mathbf{v}^{(k+1)} = \frac{\mathbf{w}^{(k+1)}}{\|\mathbf{w}^{(k+1)}\|}$ (정규화)
4. 고유값 근사: $\lambda \approx \frac{(\mathbf{v}^{(k+1)})^T A \mathbf{v}^{(k+1)}}{(\mathbf{v}^{(k+1)})^T \mathbf{v}^{(k+1)}}$ (레일리 몫)

수렴: $|\lambda_1| > |\lambda_2| \geq \cdots \geq |\lambda_n|$이면 수렴하며, 수렴 속도는 $\left|\frac{\lambda_2}{\lambda_1}\right|^k$에 비례합니다. $|\lambda_2/\lambda_1|$이 1에 가까우면 수렴이 느립니다.

역거듭제곱법 (Inverse Power Method): $A^{-1}$에 거듭제곱법을 적용하면, 절대값이 가장 작은 고유값을 구합니다. 이동(shift) $\sigma$를 도입하여 $(A - \sigma I)^{-1}$에 적용하면 $\sigma$에 가장 가까운 고유값을 구할 수 있습니다.

역멱법 (Inverse Power Method)

$A^{-1}$에 거듭제곱법을 적용하여 절대값이 가장 작은 고유값을 구합니다. 실제로는 역행렬을 구하지 않고, 매 반복에서 선형 시스템 $A\mathbf{w}^{(k+1)} = \mathbf{v}^{(k)}$를 풉니다.

이동이 있는 역멱법 (Shifted Inverse Iteration): 대략적인 고유값 추정 $\sigma$가 있을 때, $(A - \sigma I)^{-1}$에 거듭제곱법을 적용하면 $\sigma$에 가장 가까운 고유값에 빠르게 수렴합니다.

$\sigma$가 정확할수록 수렴이 빨라지며, 레일리 몫 반복법에서는 매 반복마다 $\sigma$를 갱신하여 3차 수렴까지 달성할 수 있습니다.

QR 알고리즘

모든 고유값을 동시에 구하는 가장 강력한 방법입니다.

기본 QR 반복:

1. $A_0 = A$
2. $A_k = Q_k R_k$ (QR 분해)
3. $A_{k+1} = R_k Q_k$ ($= Q_k^T A_k Q_k$, 닮음 변환이므로 고유값 보존)

$A_k$는 상삼각 행렬(슈어 형태)로 수렴하며, 대각 원소가 고유값이 됩니다.

실용적 개선:

• 이동 (Shift): $A_k - \sigma_k I = Q_k R_k$, $A_{k+1} = R_k Q_k + \sigma_k I$로 수렴을 가속합니다. 윌킨슨 이동(Wilkinson shift)은 3차 수렴을 보장합니다.
• 하이센베르크 축약: 먼저 $A$를 상하이센베르크 형태 $H$로 변환($O(n^3)$)하여 이후 각 QR 반복을 $O(n^2)$으로 줄입니다.
• 묵시적 QR 이동 (Implicit QR Shift): 명시적 QR 분해 없이 하이센베르크 형태를 유지하며 연산합니다.

고유값 수치 계산 비교

최소제곱 문제

과결정(overdetermined) 시스템 $A\mathbf{x} \approx \mathbf{b}$ ($A$는 $m \times n$, $m > n$)에서 잔차 $\|\mathbf{b} - A\mathbf{x}\|_2$를 최소화하는 $\mathbf{x}$를 구합니다.

정규방정식 (Normal Equations)

$A^T A$가 양의 정부호이면 콜레스키 분해로 풀 수 있습니다.

문제점: $\kappa(A^T A) = \kappa(A)^2$이므로, $A$의 조건수가 크면 정규방정식은 수치적으로 불안정합니다.

QR 분해를 이용한 최소제곱

$A = QR$ (얇은 QR 분해)로 놓으면 최소제곱 해는

$R$이 상삼각이므로 후진 대입으로 풀 수 있습니다. 조건수가 $\kappa(R) = \kappa(A)$이므로 정규방정식보다 안정적입니다.

특이값 분해(SVD)를 이용한 최소제곱

$A = U\Sigma V^T$로 분해하면 최소제곱 해는

여기서 $\Sigma^+$는 $\Sigma$의 유사역행렬(nonzero 대각 원소의 역수)입니다.

SVD의 장점:

• 랭크 결핍(rank-deficient) 문제도 안정적으로 처리
• 최소 노름 해를 자동으로 제공
• 특이값을 통해 문제의 조건수와 유효 랭크를 직접 파악 가능

최소제곱 풀이법 비교

이산 푸리에 변환과 FFT

이산 푸리에 변환(DFT)은 이산 신호를 주파수 성분으로 분해합니다. 고속 푸리에 변환(FFT)은 DFT를 효율적으로 계산하는 알고리즘입니다.

이산 푸리에 변환 (DFT)

$N$개의 데이터 $\{x_0, x_1, \ldots, x_{N-1}\}$에 대해

역변환:

직접 계산하면 $O(N^2)$의 복소수 곱셈이 필요합니다.

FFT (Fast Fourier Transform) — 쿨리-튜키 알고리즘

$N = 2^m$일 때, DFT를 짝수 인덱스와 홀수 인덱스로 분할하여 재귀적으로 계산합니다.

여기서 $\omega = e^{-2\pi i/N}$은 $N$차 단위근입니다.

나비(Butterfly) 연산:

이 분할-정복에 의해 연산 복잡도가 $O(N \log N)$으로 줄어듭니다.

오차 분석 심화

수치 알고리즘의 신뢰성을 평가하기 위해 오차를 체계적으로 분석하는 심화 내용입니다.

전방 오차 분석 vs 후방 오차 분석

전방 오차 분석(Forward Error Analysis)은 각 연산 단계에서 발생하는 반올림 오차를 추적하여 최종 오차의 상한을 구합니다. 비관적인 상한을 주지만 실제 오차보다 크게 과대평가하는 경향이 있습니다.

후방 오차 분석(Backward Error Analysis)은 윌킨슨(Wilkinson)이 개발한 접근법으로, 계산된 결과를 약간 섭동된 입력에 대한 정확한 답으로 해석합니다.

부동소수점 연산의 후방 오차

IEEE 754 산술에서 기본 연산의 후방 오차 모델:

이 성질을 이용하면, 복잡한 알고리즘의 후방 안정성을 체계적으로 증명할 수 있습니다.

조건수 심화 — 다양한 문제에서의 조건수

수치 안정성의 계층

• 후방 안정 (Backward Stable): $\hat{f}(x) = f(x + \Delta x)$, $\frac{\|\Delta x\|}{\|x\|} = O(\epsilon_{\text{mach}})$ — 가장 강한 조건. 가우스 소거(부분 피벗), QR 분해 등.
• 혼합 안정 (Mixed Stable): $\hat{f}(x) + \Delta y = f(x + \Delta x)$ — 후방 안정보다 약간 느슨. 콜레스키 분해 등.
• 전방 안정 (Forward Stable): $\|\hat{f}(x) - f(x)\| = O(\epsilon_{\text{mach}} \kappa \|f(x)\|)$ — 가장 느슨. 조건수에 비례하는 오차 보장.
• 불안정 (Unstable): 오차가 조건수보다 빠르게 증폭됨. 피벗 없는 가우스 소거, 그람-슈미트 직교화(고전적 형태) 등.

수치해석 핵심 정리

참고자료

• Burden, R. L. & Faires, J. D. — Numerical Analysis, Cengage
• Trefethen, L. N. & Bau, D. — Numerical Linear Algebra, SIAM
• Stoer, J. & Bulirsch, R. — Introduction to Numerical Analysis, Springer
• Golub, G. H. & Van Loan, C. F. — Matrix Computations, Johns Hopkins
• 미적분학 — 수치 적분의 이론적 배경
• 선형대수학 — 선형계의 이론, 고유값 이론
• 미분방정식 — ODE의 수치적 풀이