計算小數除法

設有一變數除法為

$a/b$ ，可以改寫成

$a\times (1/b)$，故只需要求

$1/b$ 的值再乘上

$a$ 即可求得其值

---

縮小問題規模

• 已知
  $k$ 值，求
  $1/k$ 的值為何？

套用牛頓法：

$x=1/k\Rightarrow 1/x=k$

$f(x)=1/x-k,f^{\prime }(x)=-1/x^2$

$x_{n+1}=x_n-\frac{1/x_n-k}{-1/x_n^2}=2x_n-k{x}_n^2=x_n(2-k{x}_n)$

---

展開遞迴式並化簡(驗算用)

假設

$x=1/k$,

$r=k{x}_n$

$x_n=x_n$

$x_{n+1}=x_n(2-r)$

$x_{n+2}=x_n(4-6r+4r^2-r^3)$

$x_{n+3}=x_n(8-28r+56r^2-{70}^3+56r^4-28r^5+8r^6-r^7)$
…

可利用遞迴關係得出結果趨近於

$x=x_n\cdot \sum _{i=1}(-1{)}^{i-1}{C}_i^n{r}^i$

即為巴斯卡三角形中

$(1-x{)}^n$ 的變化式，最終可得其簡化式為：

$x=x_n\cdot \frac{1-(1-r{)}^{2^t}}{r}$

$t$ 即為牛頓法的迭代次數

參考源自 wiki

---

假設

$x=1/k$,

$r=-k{x}_0$

$x_1=x_0(2-k{x}_0)=x_0(2+r)=2x_0+r{x}_0$

$x_2=x_1(2-k{x}_1)=(2x_0+r{x}_0)(2-k(2x_0+r{x}_0))=(2x_0+r{x}_0)(2-2k{x}_0+rk{x}_0)$

$=4x_0-4k{x}_0^2+2rk{x}_0^2+2r{x}_0-2rk{x}_0^2+r^{2}k{x}_0^2=4x_0+2r{x}_0-4k{x}_0^2+r^{2}k{x}_0^2$

$=$