실습 · 연습문제 2개

연속함수 $f$가 구간 $[a, b]$의 양 끝에서 부호가 다르면($f(a)f(b) < 0$) 중간값 정리에 따라 그 사이에 근이 있다. 이분법(bisection)은 중점 $m = (a+b)/2$에서 부호를 확인해, 부호가 바뀌는 쪽 절반을 남기는 일을 반복한다. 구간 폭이 매번 절반이 되므로 느리지만, 부호가 바뀌는 구간만 주어지면 반드시 수렴한다.

함수 bisection(f, a, b, xtol=1e-12, max_iter=200)를 완성한다.

• $f(a)$와 $f(b)$의 부호가 같으면 ValueError를 낸다. 둘 중 하나가 정확히 0이면 그 끝점을 바로 반환한다(반복 0번).
• 구간 폭 $b - a$가 $2 \cdot$xtol 이하가 되면 멈추고 중점을 반환한다. 그러면 반환값과 근의 거리가 xtol 이하임이 보장된다. 중점에서 $f(m) = 0$이면 바로 $m$을 반환한다.
• (x, n_iter)를 반환한다. n_iter는 구간을 절반으로 줄인 횟수다.
• max_iter번 안에 끝나지 않으면 그때의 중점을 반환한다.

힌트: 구간 $[a, b]$에서 $k$번 절반으로 줄이면 폭은 $(b - a)/2^k$다. 테스트는 반복 횟수가 이 식에서 예측한 값과 같은지도 확인한다. 부호 비교는 f(a) * f(m) 대신 np.sign으로 하면 아주 큰 값·작은 값의 곱이 overflow·underflow하는 것을 피할 수 있다(9.1장).

비선형 연립방정식 $\mathbf{F}(\mathbf{x}) = \mathbf{0}$($\mathbf{F}: \mathbb{R}^n \to \mathbb{R}^n$)의 Newton step은 Jacobian $\mathbf{J}(\mathbf{x})$에 대한 선형시스템

$$\mathbf{J}(\mathbf{x}_k)\,\Delta\mathbf{x} = -\mathbf{F}(\mathbf{x}_k)$$

의 해다. 순수 Newton은 $\mathbf{x}_{k+1} = \mathbf{x}_k + \Delta\mathbf{x}$로 가지만, 근에서 멀면 step이 너무 커서 발산할 수 있다. damped Newton은 step 길이 $t \in (0, 1]$을 줄여 가며

$$\|\mathbf{F}(\mathbf{x}_k + t\,\Delta\mathbf{x})\| < \|\mathbf{F}(\mathbf{x}_k)\|$$

를 만족하는 첫 $t$(1, 1/2, 1/4, …)를 쓴다(backtracking line search).

함수 damped_newton(F, J, x0, tol=1e-10, max_iter=50)를 완성한다.

• F(x)는 shape (n,), J(x)는 shape (n, n)을 반환한다.
• 매 반복의 처음에 $\|\mathbf{F}(\mathbf{x}_k)\| \le$ tol이면 멈춘다.
• Newton step은 np.linalg.solve로 구한다. 역행렬을 만들지 않는다.
• $t$는 1에서 시작해 조건을 만족할 때까지 절반으로 줄인다. $t < 10^{-8}$이 되도록 만족하지 않으면 그 $t$로 그냥 진행한다.
• (x, n_iter)를 반환한다. n_iter는 수행한 Newton step의 수다.

테스트는 순수 Newton이 발산하는 초기값에서 damped Newton이 수렴하는지, 근 근처에서 몇 번 만에 끝나는지(2차 수렴)를 확인한다.