할선법

2.1. 방법의 유도

할선법은 함수 f의 영점을 찾기 위한 반복적인 수치 해석 방법이다. 초기값 와 에서 시작하여, 점 와 를 지나는 할선을 그린다. 이 할선의 방정식은 기울기-절편 형태로 다음과 같이 표현할 수 있다.

:$y\; =\; \backslash frac\{f(x\_1)\; -\; f(x\_0)\}\{x\_1\; -\; x\_0\}(x\; -\; x\_1)\; +\; f(x\_1).$

이 선형 함수의 근, 즉 을 만족하는 의 값은 다음과 같다.

:$x\; =\; x\_1\; -\; f(x\_1)\; \backslash frac\{x\_1\; -\; x\_0\}\{f(x\_1)\; -\; f(x\_0)\}.$

이 값을 로 사용하고, 와 대신 과 를 사용하여 위 과정을 반복한다. , 등을 계산하여 충분히 높은 정밀도 수준 (과 사이의 충분히 작은 차이)에 도달할 때까지 반복한다.

:$$
\begin{align}
x_2 & = x_1 - f(x_1) \frac{x_1 - x_0}{f(x_1) - f(x_0)}, \\[6pt]
x_3 & = x_2 - f(x_2) \frac{x_2 - x_1}{f(x_2) - f(x_1)}, \\[6pt]
& \,\,\,\vdots \\[6pt]
x_n & = x_{n-1} - f(x_{n-1}) \frac{x_{n-1} - x_{n-2}}{f(x_{n-1}) - f(x_{n-2})}.
\end{align}

일반적으로 다음과 같이 표현할 수 있다.

:$x\_\{n\}=x\_\{n-1\}-f(x\_\{n-1\})\{\backslash frac\; \{x\_\{n-1\}-x\_\{n-2\}\}\{f(x\_\{n-1\})-f(x\_\{n-2\})\}\}=\{\backslash frac\; \{x\_\{n-2\}f(x\_\{n-1\})-x\_\{n-1\}f(x\_\{n-2\})\}\{f(x\_\{n-1\})-f(x\_\{n-2\})\}\}$

3. 수렴성

할선법의 반복 ${\displaystyle x_{n}}$은 초기값 ${\displaystyle x_{0}}$과 ${\displaystyle x_{1}}$이 근에 충분히 가깝고 ${\displaystyle f}$가 잘 동작하는 경우 ${\displaystyle f}$의 근으로 수렴한다. ${\displaystyle f}$가 두 번 연속 미분 가능하고 문제의 근이 단순근(중복도 1)일 때, 수렴 차수는 황금비 ${\displaystyle \varphi =(1+{\sqrt {5}})/2\approx 1.618}$이다. 이 수렴은 초선형이지만 이차 수렴보다는 느리다.

초기값이 근에 충분히 가깝지 않거나 ${\displaystyle f}$가 잘 동작하지 않으면 할선법이 전혀 수렴하지 않을 수도 있다. "충분히 가깝다"에 대한 일반적인 정의는 없지만, 수렴 기준은 초기값 사이의 간격에서 함수의 "울퉁불퉁함"과 관련이 있다. 예를 들어, ${\displaystyle f}$가 해당 간격에서 미분 가능하고 간격 내에 ${\displaystyle f'=0}$인 점이 있는 경우 알고리즘이 수렴하지 않을 수 있다.

함수 ${\displaystyle f}$가 2번 연속 미분 가능하고 ${\displaystyle f'(x_{*})\neq 0}$이며, ${\displaystyle f''(x_{*})\neq 0}$라면 수열 ${\displaystyle x_{k}}$는 ${\displaystyle x_{*}}$에 수렴하며, 그 수렴 속도는 황금비 ${\displaystyle \varphi =(1+{\sqrt {5}})/2\asymp 1.6}$이다.

4. 다른 근 찾기 방법과의 비교

이분법과 달리 할선법은 근이 연속적인 반복에서 묶여 있을 필요가 없으므로 항상 수렴하지는 않는다. 가위치법(또는 regula falsi^라틴어)은 할선법과 같은 공식을 사용하지만, 할선법처럼 x_n-1과 x_n-2에 공식을 적용하는 대신, x_n-1과 f(x_k)와 f(x_n-1)이 다른 부호를 갖는 마지막 반복 x_k에 적용한다. 따라서 가위치법은 항상 수렴하지만, 수렴 차수는 선형이다. 할선법의 초선형 수렴 차수를 유지하면서도 수렴성을 보장하는 방법으로는 ITP 방법이나 Illinois 방법 등이 있다.

4.1. 뉴턴법과의 관계

할선법은 뉴턴법의 공식에서 미분값을 다음과 같은 유한 차분 근사로 대체한 것으로 볼 수 있다.

:$f\text{'}(x\_\{n-1\})\; \backslash approx\; \backslash frac\{f(x\_\{n-1\})\; -\; f(x\_\{n-2\})\}\{x\_\{n-1\}\; -\; x\_\{n-2\}\}$

따라서 할선법은 도함수가 근사값으로 대체되는 방법으로 해석될 수 있으며, 준 뉴턴법의 일종이다.

뉴턴법과 할선법을 비교하면, 뉴턴법이 더 빠르게 수렴한다 (2차 vs 황금비 φ ≈ 1.6). 그러나 뉴턴법은 매 단계에서 함수 f와 그 도함수 f'의 값을 모두 구해야 하는 반면, 할선법은 함수 f의 값만 계산하면 된다. 따라서 함수 f의 계산 비용이 도함수의 계산 비용보다 훨씬 크거나, 도함수를 구하기 어려운 경우에는 할선법이 뉴턴법보다 더 효율적일 수 있다. 예를 들어, f를 평가하는 데 도함수를 평가하는 것만큼 시간이 걸리고 다른 모든 비용을 무시한다고 가정하면, 뉴턴법의 한 단계와 동일한 비용으로 할선법의 두 단계를 수행할 수 있다. 이때 할선법은 오차의 로그를 φ² ≈ 2.6만큼 감소시키고, 뉴턴법은 오차의 로그를 2만큼 감소시키므로 할선법이 더 빠르다. 더 높은 차원에서, 뉴턴법에 필요한 모든 편도함수, 즉 야코비 행렬은 함수 자체보다 계산하는 데 훨씬 더 많은 비용이 들 수 있다. 그러나 도함수 또는 도함수들의 평가를 위한 병렬 처리를 고려한다면, 뉴턴법이 전체적으로 더 많은 계산 연산을 소요하더라도 실제 계산 시간은 더 빠를 수 있다.

단순히 차분 근사한 뉴턴법과 비교하면, 할선법은 수렴까지의 반복 횟수는 늘지만, 1회 반복당 함수 평가 횟수는 적다. 따라서 총 연산량에 대한 함수 평가 비용의 비율이 큰 경우에는 수렴까지의 계산 시간을 단축할 수도 있다.

5. 일반화

브로이덴 방법은 할선법을 여러 차원으로 일반화한 방법이다.

--

6. 계산 예시

다음은 파이썬을 이용한 할선법 구현 예시이다.


def secant_method(f, x0, x1, iterations):
"""할선법을 사용하여 계산된 근을 반환합니다."""
for i in range(iterations):
x2 = x1 - f(x1) * (x1 - x0) / float(f(x1) - f(x0))
x0, x1 = x1, x2
# 여기에 중단 기준을 적용합니다(아래 참조).
return x2

def f_example(x):
return x ** 2 - 612

root = secant_method(f_example, 10, 30, 5)

print(f"Root: {root}") # Root: 24.738633748750722


위 코드에서 적절한 중단 기준을 설정하는 것이 중요하다. 그렇지 않으면, 부동 소수점 숫자의 제한된 정밀도로 인해 알고리즘이 너무 많은 반복을 실행하여 부정확한 결과를 반환할 수 있다.