실습 · 연습문제 2개

반복법의 오차 $e_k = |x_k - x^*|$가

$$e_{k+1} \approx C\, e_k^{\,p}$$

를 따르면 수렴 차수(order of convergence)가 $p$다. $p = 1$이면 선형 수렴, $p = 2$이면 2차 수렴이다. 연속한 세 오차에서 $C$를 소거하면

$$p_k = \frac{\log(e_{k+1} / e_k)}{\log(e_k / e_{k-1})}$$

로 $p$를 추정할 수 있다.

함수 estimate_order(errors)를 완성한다.

• errors는 양수 오차의 1차원 배열 $(e_0, e_1, \dots, e_{n-1})$이다($n \ge 3$).
• $k = 1, \dots, n-2$에 대한 추정값 $p_k$를 담은 길이 $n - 2$의 NumPy 배열을 반환한다.

테스트는 선형 수렴($e_k = 0.5^k$), 2차 수렴($e_{k+1} = e_k^2$), 실제 Newton 반복과 secant 반복의 오차에 적용해 추정값을 확인한다.

참고: 실제 반복에서 오차가 machine epsilon 근처까지 줄면 반올림 오차 때문에 추정값이 흔들린다. 추정값은 오차가 충분히 크고 점근 영역에 들어선 구간에서 읽는다.

$ax^2 + bx + c = 0$의 근의 공식

$$x_{1,2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

은 $|b|$가 $|ac|$보다 훨씬 크면 한 근에서 거의 같은 두 수 $-b$와 $\pm\sqrt{b^2-4ac}$를 빼게 되어 유효숫자를 잃는다. 근 자체는 계수의 작은 변화에 둔감한(조건이 좋은) 문제인데도, 알고리즘이 불안정해서 생기는 오차다.

함수 quadratic_roots(a, b, c)를 완성한다.

• 실근 두 개를 작은 것부터 정렬한 튜플 (x1, x2)로 반환한다. 테스트는 $a \neq 0$이고 $b^2 - 4ac > 0$인 경우만 넣는다.
• 두 근 모두 상대 오차가 $10^{-14}$ 이하여야 한다. 예: $x^2 - 10^8 x + 1 = 0$의 작은 근은 약 $10^{-8}$이다.
• $b = 0$이어도 동작해야 한다.

힌트: 부호가 같은 두 수를 더하는 쪽의 근을 먼저 구한다. $q = -\tfrac{1}{2}\big(b + \operatorname{sign}(b)\sqrt{b^2 - 4ac}\big)$로 두면 $x = q/a$가 한 근이고, 근과 계수의 관계(Vieta) $x_1 x_2 = c/a$에서 다른 근은 $c/q$다. np.sign(0)은 0이므로 $b = 0$일 때의 부호를 따로 정한다.