[수치해석] 3강 | Roots: Open Methods

수치해석 — Roots: Open Methods

이전 내용에서는 Bisection Method와 False-Position Method처럼 근이 존재하는 구간을 먼저 설정하고 그 범위를 좁혀가는 Bracketing Method를 살펴봤다.

이번에는 근을 반드시 특정 구간 안에 가두지 않고, 하나 또는 두 개의 초기값에서 반복 계산을 시작하는 Open Method를 알아본다.

📌 이번 장의 주요 내용

① Bracketing Method와 Open Method의 차이
② Simple Fixed-point Iteration
③ Fixed-point의 수렴과 발산
④ Wegstein Method
⑤ Newton-Raphson Method
⑥ Secant Method
⑦ Modified Secant Method
⑧ Brent Method
⑨ Polynomial Roots
⑩ Multiple Roots
⑪ Systems of Nonlinear Equations

01. Bracketing Methods vs. Open Methods

Bracketing Method에서는 근이 존재하는 구간을 하한값 x_l과 상한값 x_u로 설정한다.

반면 Open Method는 하나의 초기값 또는 두 개의 초기값만을 사용하여 반복 계산을 시작한다.

구분	Bracketing Method	Open Method
초기 설정	근을 포함하는 구간 필요	하나 또는 두 개의 초기값
근의 포함 여부	근이 구간 안에 존재	초기값이 근을 감쌀 필요 없음
특징	안정적인 수렴	빠르게 수렴할 수 있음
문제점	상대적으로 느릴 수 있음	발산할 수 있음

02. Simple Fixed-point Iteration

고정점 반복법에서는 먼저

f(x) = 0

형태의 방정식을 다음과 같이 변형한다.

x = g(x)

초기값 x₀가 주어지면 다음 반복식을 사용한다.

x_k = g(x_k-1)

즉,

x₀

↓

x₁ = g(x₀)

↓

x₂ = g(x₁)

↓

x₃ = g(x₂)

↓

반복

⚠️ 주의

고정점 반복법은 초기값과 함수 g(x)의 형태에 따라 근으로 수렴할 수도 있고 발산할 수도 있다.

반복 과정의 근사 상대오차는 다음과 같이 계산한다.

ε_a = | (x_i+1 − x_i) / x_i+1 | × 100%

Simple Fixed-point Iteration 기본 개념

03. Fixed-point Iteration 예제

다음 함수를 생각해보자.

f(x) = e^−x − x

f(x) = 0이므로,

x = e^−x

따라서 반복식은

x_i+1 = e^−x_i

이다.

초기값을 x₀ = 0으로 두면,

x₁ = e⁰ = 1.0

x₂ = e⁻¹ ≈ 0.367879

x₃ ≈ 0.692201

x₄ ≈ 0.500473

이처럼 값이 실제 근 주변을 오가면서 점차 근에 가까워진다. 실제 근은 약 0.56714329이다.

f(x) = e−x − x와 y = x, y = e−x 교점 

04. Cobweb Diagram

Fixed-point Iteration의 반복 과정을 그래프로 표현한 것을 Cobweb Diagram이라고 한다.

x = g(x)를 다음 두 함수로 나누어 생각한다.

y = x

y = g(x)

두 그래프의 교점이

x = g(x)

를 만족하는 지점이므로 근이 된다.

초기값 x₀에서 시작하여 y = g(x)와 y = x 사이를 반복적으로 이동하면 x₁, x₂, x₃가 만들어진다.

Fixed-point Iteration Cobweb Diagram

05. Fixed-point Iteration의 수렴과 발산

Fixed-point Iteration의 오차 관계는 다음과 같이 표현할 수 있다.

E_i+1 = g′(ξ)E_i

따라서 g(x)의 기울기 절댓값이 수렴 여부를 결정한다.

조건	결과
|g′(ξ)| < 1	수렴
|g′(ξ)| > 1	발산
|g′(ξ)| = 1	무한 반복 가능

💡 핵심

고정점 근처에서 |g′(x)|가 1보다 작다면 반복할수록 오차가 줄어들어 근으로 수렴한다.

Fixed-point Iteration 수렴 / 발산 4가지 경우

06. Wegstein Method

Fixed-point Iteration은 단순하지만 수렴 속도가 느리거나 아예 발산할 수도 있다.

Wegstein Method는 두 개의 연속된 추정값을 이용하여 다음 추정값을 더 효율적으로 계산한다.

두 점

(x_i-1, g(x_i-1))

와

(x_i, g(x_i))

를 직선으로 연결한다.

이 직선과 45° 선인 y = x의 교점을 다음 추정값으로 사용한다.

x_i+1 = [ x_ig(x_i-1) − x_i-1g(x_i) ] / [ x_i − x_i-1 − g(x_i) + g(x_i-1) ]

Wegstein Method는 Fixed-point Iteration보다 더 빠르게 수렴할 수 있으며, Fixed-point Iteration이 발산하는 경우를 안정화하는 데 사용될 수 있다.

Wegstein Method 기하학적 원리

07. Newton-Raphson Method

Newton-Raphson Method는 가장 널리 사용되는 근 찾기 방법 중 하나다.

현재 추정값 x_i에서 함수의 접선을 구하고, 그 접선이 x축과 만나는 지점을 다음 추정값 x_i+1로 사용한다.

x_i+1 = x_i − f(x_i) / f′(x_i)

현재 값 x_i

↓

f(x_i)와 f′(x_i) 계산

↓

접선 생성

↓

접선과 x축의 교점 계산

↓

새로운 x_i+1

Newton-Raphson Method는 일반적으로 Quadratic Convergence를 보이기 때문에 빠르게 수렴할 수 있다.

Newton-Raphson Method 접선과 반복 과정

08. Newton-Raphson이 잘 수렴하지 않는 경우

Newton-Raphson Method가 항상 수렴하는 것은 아니다.

① 근이 변곡점 근처에 있는 경우

접선의 기울기가 작아 수렴이 느려지거나 불안정할 수 있다.

② 극값 근처에서 진동하는 경우

반복값이 양쪽을 오가면서 수렴하지 않을 수 있다.

③ 다른 근으로 이동하는 경우

초기값에 따라 예상한 근이 아닌 다른 근으로 수렴할 수 있다.

④ f′(x) = 0인 경우

Newton-Raphson 공식에서 분모가 0이 되어 계산할 수 없다.

Newton-Raphson Method 실패 사례 4가지

09. Secant Method

Newton-Raphson Method의 가장 큰 문제 중 하나는 미분값 f′(x)를 계산해야 한다는 점이다.

Secant Method는 실제 미분 대신 두 점 사이의 기울기로 미분을 근사한다.

f′(x_i) ≈ [ f(x_i) − f(x_i-1) ] / [ x_i − x_i-1 ]

이를 Newton-Raphson 식에 적용하면

x_i+1 = x_i − f(x_i) [ x_i − x_i-1 ] / [ f(x_i) − f(x_i-1) ]

이 된다.

Secant Method는 두 개의 초기값을 필요로 하지만, 그 두 값 사이에서 함수값의 부호가 반드시 바뀔 필요는 없다. 따라서 Bracketing Method가 아니라 Open Method이다.

Secant Method 두 점과 다음 추정값

10. False Position vs. Secant

False Position과 Secant Method는 모두 두 점을 연결한 직선을 이용한다는 점에서 비슷해 보인다.

하지만 가장 중요한 차이는 근을 포함하는 구간을 유지하는가이다.

구분	False Position	Secant
Bracket 유지	유지함	유지하지 않음
부호 변화 조건	필요	필요 없음
분류	Bracketing Method	Open Method
수렴 특성	비교적 안정적	빠를 수 있으나 발산 가능

False Position vs. Secant 비교

11. Modified Secant Method

Modified Secant Method는 두 개의 독립적인 초기 추정값 대신 현재 x에 작은 변화량을 적용해서 미분을 근사한다.

f′(x_i) ≈ [ f(x_i + δx_i) − f(x_i) ] / δx_i

여기서 δ는 매우 작은 perturbation fraction이다.

δ 선택 시 주의

δ가 너무 작으면 subtractive cancellation에 의해 round-off error가 발생할 수 있다.

반대로 δ가 너무 크면 근사 정확도가 떨어져 발산할 수 있다.

12. Brent Method

Brent Method는 Bracketing Method의 안정성과 Open Method의 빠른 수렴을 결합한 Hybrid Method이다.

근을 포함하는 bracket 설정

↓

빠른 Open Method 시도

↓

결과가 bracket 안에 있는가?

↓

아니면 안정적인 closed method 사용

↓

다시 Open Method 시도

Brent Method

안정성 + 빠른 수렴을 동시에 얻기 위한 방법이다.

13. Multiple Roots

Multiple Root는 한 위치에서 근이 중복되어 나타나는 경우다.

대표적으로 함수가 x축에 접하는 형태가 나타날 수 있다.

이 경우 함수값의 부호가 변하지 않을 수 있기 때문에 Bracketing Method가 근을 찾지 못할 수 있다.

또한 다음 조건이 동시에 나타날 수 있다.

f(x) = 0

f′(x) = 0

따라서 Newton-Raphson이나 Secant Method에서도 수렴 문제가 발생할 수 있다.

Double Root / Triple Root / Quadruple Root

Multiple Root를 다루기 위한 한 가지 방법은 다음 함수를 새로 정의하는 것이다.

u(x) = f(x) / f′(x)

그리고 u(x)에 Newton-Raphson 형태를 적용한다.

14. Systems of Nonlinear Equations

지금까지는 하나의 변수에 대한 방정식을 다뤘다. 하지만 여러 개의 비선형 방정식을 동시에 풀어야 하는 경우도 있다.

예를 들어

x² + xy = 10

y + 3xy² = 57

이라면 다음 두 함수를 동시에 0으로 만드는 (x, y)를 찾아야 한다.

u(x,y) = x² + xy − 10 = 0

v(x,y) = y + 3xy² − 57 = 0

이 문제는 1변수 Newton-Raphson을 여러 변수로 확장한 Multi-dimensional Newton-Raphson으로 접근할 수 있다.

Systems of Nonlinear Equations / Multi-dimensional Newton-Raphson

15. 핵심 정리

Open Method
→ 근을 반드시 구간 안에 가둘 필요가 없다.

Fixed-point Iteration
→ f(x) = 0을 x = g(x)로 바꿔 반복한다.

Fixed-point 수렴 조건
→ |g′(ξ)| < 1이면 수렴한다.

Wegstein Method
→ 두 연속 추정값을 이용하여 고정점 반복법을 가속한다.

Newton-Raphson
→ 접선과 x축의 교점을 다음 추정값으로 사용한다.

Secant Method
→ 실제 미분 대신 두 점 사이 기울기를 사용한다.

Modified Secant
→ δ만큼 변화시킨 값으로 미분을 근사한다.

Brent Method
→ Bracketing의 안정성과 Open Method의 빠른 수렴을 결합한다.

Multiple Roots
→ 부호가 바뀌지 않거나 f′(x) = 0이 되어 일반적인 방법에서 문제가 생길 수 있다.