뉴턴 방법은 접선의 기울기, 곧 도함수가 필요하다. 할선법은 도함수 대신 최근 두 점을 잇는 직선(할선)의 기울기를 써서, 그 직선이 \(x\)축과 만나는 곳으로 간다. 도함수를 계산할 필요가 없고 뉴턴 방법에 가깝게 빠르다. 시작점이 두 개 필요하지만 이분법처럼 근을 사이에 둘 필요는 없다. 다만 두 점의 함수 값이 같으면 0으로 나누게 되고, 수렴이 보장되지 않는다.
예시로 보기
\(f(x) = e^{-x} - x\)의 근(참값 0.56714329…)을 \(x_{-1} = 0\), \(x_0 = 1\)에서 찾는다.
| 반복 | 두 점 | 함수 값 | 새 점 | \(\lvert\epsilon_t\rvert\) |
|---|---|---|---|---|
| 1 | \(x_{-1} = 0\), \(x_0 = 1\) | \(1.00000\), \(-0.63212\) | \(x_1 = 1 - \frac{-0.63212(0 - 1)}{1 - (-0.63212)} = 0.61270\) | 8.0% |
| 2 | \(x_0 = 1\), \(x_1 = 0.61270\) | \(-0.63212\), \(-0.07081\) | \(x_2 = 0.61270 - \frac{-0.07081(1 - 0.61270)}{-0.63212 - (-0.07081)} = 0.56384\) | 0.58% |
둘째 반복의 두 점은 모두 근의 오른쪽에 있다(함수 값이 둘 다 음수). 이분법이었다면 이렇게 할 수 없다.
할선은 곡선 위 두 점을 잇는 직선이고, 이 직선이 \(x\)축과 만나는 곳(×)이 다음 점이다. 둘째 할선(주황)은 근 오른쪽의 두 점으로 그었는데도 근 바로 옆에 떨어진다1.
정의
뉴턴 방법 \(x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}\)에서 도함수를 최근 두 점의 기울기(1계 분할 차분)로 바꾼다.
\[f'(x_i) \approx \frac{f(x_i) - f(x_{i-1})}{x_i - x_{i-1}}\]넣으면 할선법이다.
\[x_{i+1} = x_i - \frac{f(x_i)(x_i - x_{i-1})}{f(x_i) - f(x_{i-1})}\]입력: 시작점 두 개 \(x_{-1}\), \(x_0\), 허용 오차. 출력: 근의 근삿값. 매 반복 \(f\)를 한 번만 새로 계산한다(앞 점의 값은 다시 쓴다).
flowchart TD
A["시작점 두 개, 두 점의 f 값"] --> B{"두 f 값이 같은가?"}
B -->|"예"| X["0으로 나누게 된다. 시작점을 바꾼다"]
B -->|"아니오"| C["할선이 x축과 만나는 점을 새 점으로"]
C --> D["새 점에서 f를 한 번 계산"]
D --> E{"상대 오차가 허용 오차 이하인가?"}
E -->|"예"| Y["새 점을 답으로"]
E -->|"아니오"| F["가장 오래된 점을 버리고 최근 두 점을 남김"]
F --> B
고리를 한 번 돌 때마다 점 하나가 새로 들어오고 가장 오래된 점이 빠진다. 이분법과 달리 부호를 보고 고르는 단계가 없다2.
할선법의 장점과 단점은 다음과 같다.
| 장점 | 단점 |
|---|---|
| 수렴하면 빠르다 | 실패할 수 있다(수렴 보장 없음) |
| 두 시작점이 근을 사이에 둘 필요가 없다 | \(f(x_i) = f(x_{i-1})\)이면 0으로 나눈다 |
근 근처에서 오차는 대략 \(e_{i+1} \propto e_i^{1.618}\)로 준다. 뉴턴 방법(지수 2)보다 조금 느리지만 도함수 계산이 없어 한 반복이 싸다3.
활용
- 도함수를 식으로 구하기 어렵거나 계산이 비쌀 때 뉴턴 대신 쓴다. 이분법과 섞어 안전장치를 둔 방법이 가위치법(regula falsi)과 브렌트 방법이다3.
- 흔한 실수: 두 시작점의 함수 값이 같거나 거의 같게 고르는 것. \(f(x) = x^2 - 4\)에서 \(-1\)과 \(1\)을 고르면 분모가 0이다.
연결
- 선수: 선형 근사와 뉴턴 방법(도함수를 쓰는 원형), 뉴턴 다항식과 분할 차분(기울기 = 1계 분할 차분)
- 근을 사이에 두는 안전한 방법: 이분법
- 네 방법 비교: 근 찾기 방법 비교
확인 문제
C1 할선법의 갱신식을 쓰고, 뉴턴 방법의 무엇을 바꾼 것인지 말하라.
답: \(x_{i+1} = x_i - \frac{f(x_i)(x_i - x_{i-1})}{f(x_i) - f(x_{i-1})}\). 도함수 \(f'(x_i)\)를 두 점의 기울기 \(\frac{f(x_i) - f(x_{i-1})}{x_i - x_{i-1}}\)로 바꿨다.
C2 \(f(x) = x^2 - 2\), 시작점 \(1\)과 \(2\)로 할선법을 한 번 하라.
답: \(f(1) = -1\), \(f(2) = 2\). \(x = 2 - \frac{2(2 - 1)}{2 - (-1)} = 2 - \frac23 = \frac43 \approx 1.333\).
C3 할선법도 시작점이 둘이고 이분법도 둘이다. 두 방법이 시작점에 요구하는 것과 보장하는 것은 어떻게 다른가?
답: 이분법은 두 점의 부호가 달라야 하고(근을 사이에 둠), 대신 늘 수렴한다. 할선법은 그런 조건이 없지만 수렴이 보장되지 않는다. 할선법은 수렴하면 훨씬 빠르다.