您當前的位置：首頁 > 攝影

高效估計開方和e

作者：由未灬秋色發表于攝影時間：2018-06-05

上一篇估計開方的文章裡，介紹了一種簡便的方法去估計

$\sqrt{2}$

的值，當然評論裡有大牛也提到牛頓迭代或許更高效。牛頓迭代、弦割法等等最初都是為了

計算非線性方程零點

產生的，可以設計一個以

$\sqrt{2}$

為零點的函式，在收斂域內作幾次迭代，就可以得到相當精確的結果。事實上，前一篇文章裡的方法也有背景，就是連分數，計算的階越高，相當於連分數的階數越高，下面這個式子便可以解釋這一點：

$\sqrt{2}-1=\dfrac{1}{\sqrt{2}+1}=\dfrac{1}{2+\sqrt{2}-1}=\dfrac{1}{2+\frac{1}{\sqrt{2}+1}}=\dfrac{1}{2+\frac{1}{2+\frac{1}{\sqrt{2}+1}}}=\cdots$

本文，就以牛頓迭代為背景，介紹一種方法來估計

$\sqrt{2}$

和

。（值得注意的是，估值的結果往往是一個體積龐大的分數，但是事實上，

根據丟番圖逼近理論，在之前估計 #FormatImgID_6# 的文章中出現的結果均為同體積分數中的最佳值，意即估計值與 #FormatImgID_7# 之間不存在分母更小的既約分數

）

首先考慮

$\sqrt{2}$

的左側。

構造數列滿足

$\left\{\begin{array}{l} 0<a_1<\sqrt{2}\\ a_{n+1}=\dfrac{4a_n}{a_n^2+2} \end{array}\right.$

，易知

$a_1<a_2<\cdots<a_n<\sqrt{2}$

。

不妨取

$a_1=\dfrac{7}{5}$

，則有

$a_2=\dfrac{140}{99}\approx1.4141$

，

$a_3=\dfrac{27720}{19601}\approx1.414213561$

第三項即有

位準確數字。再考慮

$\sqrt{2}$

的右側。

構造數列滿足

$\left\{\begin{array}{l} b_1>\sqrt{2}\\ b_{n+1}=\dfrac{b_n}{2}+\dfrac{1}{b_n} \end{array}\right.$

，易知

$b_1>b_2>\cdots>b_n>\sqrt{2}$

。

不妨取

$b_1=\dfrac{17}{12}$

，則有

$b_2=\dfrac{577}{408}\approx1.414216$

，

$b_3=\dfrac{665857}{470832}\approx 1.414213562375$

此結果具有

位準確數字。

這種方法雖然看起來高效的一比，但事實上，

背後的工作要遠遠比算幾個數要多

。不僅要考慮收斂性和收斂速度，還要考慮計算成本。上面給的例子也只是我覺得比較適合手算的數列。

如果為了計算

，也可以利用類似的辦法，但是要注意，一般的，滿足

且

以及存在

$\delta>0$

及

使對任意

$x\in U^\circ(e,\delta)$

都有

$|f(x)-f(e)|\leqslant L|x-e|$

的函式（這句話真長），基本都會帶著

$\ln$

之類的玩意，所以迭代起來較為繁瑣，就儘量只迭代一次，並且初值選的越接近

越好。這就要求函式的一階導數在

附近越接近於

越好。

其實，對於

的下界，

$e>\sum_{k=0}^n\dfrac{1}{k!}(n\in\mathbb{N^\ast})$

的估計效果就已經非常好了，主要是上界的問題，上界若是利用

$e^x<\dfrac{2+x}{2-x}(0<x<2)$

及

$1=\dfrac{1}{3}+\dfrac{1}{4}+\dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{20}$

這樣的連續分數拆分，也只能得到

$e<\dfrac{41}{15}\approx 2.73333$

這樣粗糙的結果。來看下迭代的效果：

構造數列滿足

$\left\{\begin{array}{l} c_1>0\\ c_{n+1}=\dfrac{c_n}{\ln c_n} \end{array}\right.$

，易知

$c_2>c_3>\cdots>c_n>e$

。

不妨取

$c_1=\dfrac{19}{7}$

，則有

$c_2=\dfrac{19}{7\ln\frac{19}{7}}\approx 2.718285$

。

這個方法除了會帶對數之外，精度還是相當不錯的。如果硬要得到分數結果，可以利用泰勒的上界：

$e<\sum_{k=0}^{n-1}\dfrac{1}{k!}+\dfrac{n+1}{n\cdot n!}(n\in\mathbb{N^\ast})$

，令

即可得到

$e<\dfrac{11743}{4320}\approx 2.718287$

，有五位的精度。

用泰勒雖然可以迅速的逼近

的值，但是由於通分之後分子帶有

，計算量並不會小到哪裡去，而得到的結果也不是同體積分數中的最佳值，所以更多的時候寧願會使用

$\dfrac{19}{7\ln\frac{19}{7}}$

這樣的結果也不會帶著一大坨式子去懟……

等後面寫篇文章專門介紹連分式，會有更好的估計

的方法和結果。

標簽：迭代分數結果數列估計

上一篇:晨會互動小遊戲（三）

下一篇：這個工具竟然可以自動開啟手機所有許可權？來看看吧！

猜你喜歡