Chapter 17 · 부록
용어집 & 종합 퀴즈
열여섯 장의 알고리즘을 한곳에 모았습니다. 문제 앞에서 실제로 묻는 것은 늘 넷입니다. 어떤 방법을 쓸까, 오차는 h나 반복 수에 따라 얼마나 줄까, 비용은 얼마일까, 언제 터질까. 고르기 도우미 → 오차·비용 한눈표 → 수렴 차수 → 안정성 조건 → 용어 검색 → 종합 퀴즈 순서입니다.
알고리즘 고르기 도우미
무엇을 계산하는지 고르고, 문제의 성질(도함수가 있는가, 행렬이 대칭인가, 강성인가…)을 고르면 먼저 써 볼 방법(강조)과 대안, 다룬 절로 가는 링크가 나옵니다.
GUIDE
이 문제, 어떤 알고리즘으로?
무엇을
문제의 성질
오차·수렴—
조심할 것—
안내는 교과서 수준의 일반 원칙입니다. 어떤 방법이든 마지막 검산은 같습니다. h(또는 허용 오차)를 반으로 줄여 답이 기대한 차수만큼 변하는지 보고, 잔차와 조건수를 함께 확인합니다.
방법별 오차 차수·비용 한눈표
h는 간격, n은 미지수(점) 수, N은 표본·격자 수, κ는 조건수입니다. 비용은 대표적인 flop 수 또는 함수 계산 횟수입니다.
| 방법 | 오차 | 비용 | 장 |
|---|---|---|---|
| n차 다항식 보간 | f⁽ⁿ⁺¹⁾(ξ)/(n+1)! · ∏(x − xᵢ) | 무게중심: 준비 O(n²), 점당 O(n) | 5장 |
| 조각별 선형 | h²/8 · max|f″|, O(h²) | O(1)/점 | 6장 |
| PCHIP | 약 O(h³), 단조 유지 | O(n) | 6장 |
| 3차 스플라인 | 고정·not-a-knot O(h⁴), 자연 O(h²) | 삼중대각 O(n) | 6장 |
| 최소제곱(QR) | 상대 오차 ≈ κ(A)u | 2mn² − 2n³/3 | 7장 |
| 정규 방정식 | ≈ κ(A)²u (자릿수 2배 손실) | 약 mn² | 7장 |
| DFT 직접 / FFT | 유니터리, κ = 1 | O(N²) / (N/2)log₂N 곱셈 | 8장 |
| 방법 | 오차 | 비용·한계 | 장 |
|---|---|---|---|
| 전진·후진 차분 | (h/2)f″, O(h) | h* ≈ √ε, 약 8자리 | 9장 |
| 중앙 차분 | (h²/6)f‴, O(h²) | h* ≈ ∛ε, 약 10자리 | 9장 |
| 복소 스텝 | O(h²), 뺄셈 없음 | h = 10⁻²⁰도 됨 | 9장 |
| 자동 미분 | 기계 정밀도 | 전진: 입력당 1회, 후진: 출력당 1회 | 9장 |
| 합성 사다리꼴·중점 | O(h²), 주기 함수는 지수적 | f n + 1회 | 10장 |
| 합성 심프슨 | O(h⁴), 3차까지 정확 | f n + 1회 | 10장 |
| 롬베르크 | 열마다 차수 +2 | 새 중점만 계산 | 10장 |
| n점 가우스–르장드르 | 2n − 1차까지 정확 | f n회, 가중치 양수 | 10장 |
| 몬테카를로 | σ/√N, 차원 무관 | 한 자리에 표본 100배 | 10장 |
| 방법 | 전역 오차 | 걸음당 비용 | 장 |
|---|---|---|---|
| 명시적 오일러 | O(h) | f 1회 | 11장 |
| 음적 오일러 · BDF1 | O(h) | 뉴턴(선형계) | 11장 |
| RK4 | O(h⁴) | f 4회 | 11장 |
| 도르만드–프린스 5(4) | O(h⁵), 오차 추정 포함 | 7단, FSAL로 f 6회 | 11장 |
| k단계 AB / AM | O(hᵏ) / O(hᵏ⁺¹) | f 1회 / PECE 2회 | 11장 |
| BDF k (k ≤ 6) | O(hᵏ) | 단순화 뉴턴, LU 재사용 | 11장 |
| 스퇴르머–베를레 | O(h²), 에너지 오차 유계 | f 1회 | 11장 |
| 열 FTCS / BTCS | O(Δt + Δx²) | O(n) / 토머스 O(n) | 16장 |
| 크랭크–니콜슨 | O(Δt² + Δx²) | 토머스 O(n) | 16장 |
| 풍상 / 랙스–벤드로프 | O(Δt + Δx) / O(Δt² + Δx²) | O(n) | 16장 |
| 방법 | 정확도·수렴 | 비용 | 장 |
|---|---|---|---|
| LU(부분 피벗팅) | 후방 안정, 오차 ≈ κu | (2/3)n³ + 우변당 2n² | 12장 |
| 촐레스키 | 피벗팅 없이 안정 | (1/3)n³ | 12장 |
| 토머스 / 띠 LU | 대각 우세면 안정 | 약 8n / O(nw²) | 12장 |
| 야코비·G–S | 비율 ρ(G); 푸아송 O(N²)회 | 반복당 O(nnz) | 13장 |
| 최적 SOR · CG | 푸아송 O(N)회; CG (√κ−1)/(√κ+1) | 반복당 O(nnz) | 13장 |
| 다중 격자 | 격자와 무관한 반복 수 | O(n) | 13장 |
| QR 알고리즘 | 후방 안정, 고유값당 2–3단계 | 비대칭 약 10n³, 대칭 (4/3)n³ | 14장 |
| 경사 하강 / 모멘텀 | (κ−1)/(κ+1) / (√κ−1)/(√κ+1) | 기울기 1회 | 15장 |
| 뉴턴 / BFGS | 2차 / 초선형 | O(n³) / O(n²) | 15장 |
수렴 차수 비교
반복법의 속도는 |en+1| ≈ C|en|p의 차수 p와 상수 C로 요약됩니다. 공평하게 비교하려면 한 단계의 비용(함수·도함수 계산, 선형계 풀이)까지 셉니다.
| 방법 | 차수 p | 단계당 계산 | 장 |
|---|---|---|---|
| 이분법 | 1 (C = 1/2), 자릿수당 3.3번 | f 1 | 3장 |
| 고정점 반복 | 1 (C = |g′(r)|) | g 1 | 3장 |
| 가위치법 / 일리노이 | 1 / 약 1.44 | f 1 | 3장 |
| 할선법 | 1.618 (p² = p + 1) | f 1, 효율 1.618 | 3장 |
| 역2차 보간 | 약 1.839 | f 1 | 3장 |
| 뉴턴(단순근) | 2 | f + f′, 효율 1.414 | 3장 |
| 뉴턴(m중근) | 1 (C = (m − 1)/m) | f + f′ | 3장 |
| 황금 분할 / 포물선 | 1 (C = 0.618) / 약 1.32 | f 1 | 15장 |
| 방법 | 수렴 | 단계당 계산 | 장 |
|---|---|---|---|
| 다변수 뉴턴 | 2 | F, J, 선형계 | 4장 |
| 브로이든 · BFGS | 초선형 | F(∇f) 1, O(n²) | 4장 |
| 가우스–뉴턴 | 영 잔차면 2, 아니면 1(잔차가 크면 느림) | J, 최소제곱 | 15장 |
| 정상 반복(야코비·G–S·SOR) | 1 (C = ρ(G)), G–S: ρJ² | Ax 1 | 13장 |
| 최급 강하 / CG | (κ−1)/(κ+1) / (√κ−1)/(√κ+1) | Ax 1 | 13장 |
| 거듭제곱법 | 1 (C = |λ₂/λ₁|) | Ax 1 | 14장 |
| 이동 역반복 | 1 (C = |λJ − σ|/|λK − σ|) | LU 재사용 풀이 | 14장 |
| 레일리 몫 반복 | 대칭 3, 비대칭 2 | 매번 새 풀이 | 14장 |
SIMULATOR
수렴 차수 경주: 10⁻¹⁵까지 몇 번?
가로축
모델: eₙ₊₁ = C·eₙᵖ. 선형(p = 1)은 위 슬라이더의 C, 초선형은 C = 1로 둡니다. 함수 계산 수는 선형·할선 1, 뉴턴 2(f, f′)로 셉니다. 해볼 것: ① e₀를 10⁻³으로 줄이면 2차·3차는 한두 번 덜 걸리고, 선형은 줄어든 자릿수만큼 꼬박 덜 걸립니다. ② '함수 계산 수'에서 할선법이 뉴턴을 앞지르는지 보세요(효율 지수 1.618 대 1.414). ③ C = 0.95는 ρ(G)가 1에 가까운 야코비 반복이나 |λ₂/λ₁| ≈ 1인 거듭제곱법의 모습입니다.
안정성 조건 모음
"수렴 = 일관성 + 안정성"(11장, 16장 랙스 동등성). 정확도가 아니라 안정성이 걸음 폭을 정하는 순간을 알아보는 것이 핵심입니다.
| 방법 | 음의 실수축 안정 구간 | 성격 |
|---|---|---|
| 명시적 오일러 | |1 + z| ≤ 1, (−2, 0) | h ≤ 2/|λ| |
| AB2 · AB3 · AB4 | (−1, 0) · (−0.545, 0) · (−0.300, 0) | 차수 ↑, 영역 ↓ |
| RK4 · DP5 | (−2.785, 0) · (−3.306, 0) | 명시적 |
| AM3 · AM4 | (−6, 0) · (−3, 0) | 음적, 유한 영역 |
| 사다리꼴(AM2) | 왼쪽 반평면 전체 | A-안정, L-안정 아님 |
| 음적 오일러 · BDF2 | 왼쪽 반평면 전체 | A-안정 + L-안정 |
| BDF3 · 4 · 5 · 6 | A(α): 86.03°, 73.35°, 51.84°, 17.84° | 제2 장벽, BDF7부터 영 안정 아님 |
| 다단계 일반 | 근 조건(영 안정) | 달퀴스트 동등성 |
| 방법 | 안정 조건 | 증폭 인자 G |
|---|---|---|
| 열 FTCS | r ≤ 1/2 | 1 − 4r sin²(θ/2) |
| 열 BTCS | 무조건 | 1/(1 + 4r sin²(θ/2)) |
| 크랭크–니콜슨 | 무조건(큰 r에서 G → −1 진동) | (1 − 2r sin²(θ/2))/(1 + 2r sin²(θ/2)) |
| 이류 중앙 FTCS | 없음(무조건 불안정) | |G|² = 1 + C²sin²θ |
| 풍상 차분 | 0 ≤ C ≤ 1 | 수치 확산 (aΔx/2)(1 − C) |
| 랙스–벤드로프 | |C| ≤ 1 | 2차, 진동(분산) |
| 파동 립프로그 | C ≤ 1 (CFL) | |G| = 1, 수치 분산 |
| 방법 | 조건 |
|---|---|
| 고정점 반복 | 근 근처에서 |g′| < 1(축소 사상) |
| 뉴턴(1변수·다변수) | 단순근·J(r) 가역, 충분히 가까운 출발점(먼 곳은 감쇠) |
| 정상 반복 | ρ(G) < 1 (필요충분) |
| 야코비 · G–S | 엄격한 대각 우세면 수렴, SPD면 G–S 수렴 |
| SOR | 0 < ω < 2 필요, SPD면 충분 |
| CG | A가 대칭 양정치 |
| 경사 하강(고정 걸음) | 0 < αL < 2, 최선 α = 2/(L + μ) |
| BFGS | yᵀs > 0(울프 조건)이면 양정치 유지 |
SIMULATOR
안정성이 정하는 걸음 폭
용어집
종합 퀴즈
열여섯 장에서 두 문제씩, 모두 32문항입니다. 몇 줄의 손계산으로 푸는 문제와 방법의 성질을 묻는 문제가 섞여 있습니다. 답을 고르면 해설이 열리고, 틀린 문제의 장이 위에 모입니다.
0 / 0