本週主要學習三種 root finding algorithms:

  1. Bisection method: 最慢, 但一定保證 works
  2. Newton’s method: 最快, 但需要好的 initialization, 也需要對 function 微分
  3. Secant method: 算快, 對於沒辦法寫出微分公式的話也可以用

Bisection Method | Lecture 13

image.png

從有兩個值 $x_0,x_1$ 出發, 其中 $f(x_0)f(x_1)<0$, 及正負號相反.

概念很好理解, 只要 $f$ 是 continuous 就一定能找到解.

Newton's Method | Lecture 14

image.png

需要微分和一個好的 initial guess. 公式為:

$$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} $$

印象以前有學到證明在 root 的夠小的 neighborhood 裡, Newton’s method 必收斂. (喔有, 課程等等會證明)

高維度的情況: [Systems of Nonlinear Equations | Lecture 33](https://bobondemon.notion.site/Systems-of-Nonlinear-Equations-Lecture-33-19bedc3d531d803d8f58d02144572a08)

Secant Method | Lecture 15

image.png

相當於對 Newton’s method 的微分項做個簡單數值逼近, 即用:

$$ f'(x_n)\approx\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}} $$

這個逼近叫做 secant.