標籤：

Lisp Scheme SICP 數值分析數學

SICP 1.45證明？

01-07

題目詳見SICP 1.45，也可參見http://sarabander.github.io/sicp/html/1_002e3.xhtml#Exercise-1_002e45或者Structure and Interpretation
of Computer Programs倒數第二個exercise。
大意是通過求 $f(y) = x/y^{n-1}$ 的不動點來近似求解x的n次方根，問需要幾次平均阻尼（average-damp）才能得到一個收斂的演算法而不會產生震蕩之類的問題。實驗結果是 $lfloorlog_2 n floor$ ，不過我不明白為什麼。

不知道有沒有相關的定理或者證明？

其實還是和牛頓法有一點點關係。

需要求解x的n次方根，那麼等價於求解以下方程的零點

$f(y)=y^n-x$

我們看看m次的平均阻尼是個什麼過程：

$frac{1}{2}(cdotsfrac{1}{2}(frac{1}{2}(frac{x}{y^{n-1}}+y)+y)cdots+y)=frac{1}{2^m}left(frac{x}{y^{n-1}}+(2^m-1)y ight)$

也就是每次迭代，都是這樣的（這裡有意省略了 k+1 的下標）：

$y=frac{1}{2^m}left(frac{x}{y_k^{n-1}}+(2^m-1)y_k ight)$

這和牛頓法很像。

這是一個關於 y 的一次方程，也就是一條直線，這麼寫會更清楚一些：

$g(y)=2^my_k^{n-1}y-x-(2^m-1)y_k^n$

迭代過程，就是不斷求解這條直線的零點。

這條直線呢，是經過這個點的： $(y_k,y_k^n-x)$ ，也就是說，是在 $f(y)$ 上的。

另一方面，這條直線的斜率，是 $2^my_k^{n-1}$ ，顯然，隨著平均阻尼過程的增加，m 增大，斜率也增大。先看個圖：

中間黃色的直線是切線，牛頓法就是用的這條直線。如果直線斜率比切線斜率小，就是綠色直線的情況；如果直線斜率比切線大，就是紅色直線的情況。

顯然，綠色直線的情況會引起迭代過程震蕩。事實上，必須保證直線的零點永遠在曲線零點的同一側（這個容易說明，只要直線斜率與切線斜率之比為常數並且小於1，那麼就不能保證直線的零點永遠在曲線零點的同一側）所以直線的斜率必須大於等於切線的斜率，也就是

$2^my_k^{n-1}ge ny^{n-1}$

於是

$mge log_2n$

推薦閱讀：

※怎麼理解從lambda運算元到實際的函數式程序設計語言？

TAG:數學 | Lisp | Scheme | SICP | 數值分析 |