以斜率取代導數
牛頓(Newton)法使用切線。當導數不可得或計算成本高昂時,可以用通過前兩個點的割線作為近似。
定義 6.2.1
(割線迭代)
設 且 。割線迭代定義
這是在該兩點對 作線性插值所得直線的零點。此方法需要兩個初始值,且分母不得為零。它並非區間包夾法:即使初始兩點位於根的兩側,之後的點也不一定仍介於兩者之間。
例題 6.2.2
(二次函數上的一步割線迭代)
取 ,、。則 ,,故 。用插值直線驗算:其斜率為 ,零點為 ,結果一致。由於 ,新點位於根 的左方,與根相距 ,比 (距離 )和 (距離 )近得多。
局部誤差乘積
設 為一個根,並記 。關鍵估計涉及兩個相鄰的誤差。
引理 6.2.3
(一步割線迭代的誤差乘積)
設 ,其中 為包含 的區間,,且在 上 、。若相異的 均位於 內,則割線步的分母不為零,且
證明
(插值誤差與割線斜率)
設 為 通過 與 的線性插值函數。在 處應用帶餘項的插值公式( 恰為節點時公式同樣成立),得
其中 為包含該三點的區間中的某一點。 的斜率是差商 ,由中值定理,其大小至少為 : 連續,且在 上不會變號。特別是它不為零,所以這一步有定義。由於 , 等於斜率的大小乘以 。結合以上事實即得所述的界。若其中一個迭代點已經是 ,則停止;無需再作迭代。
定義 6.2.4
(超線性收斂)
設序列 且 ,記 。若 ,則稱它超線性收斂。
定理 6.2.5
(割線法的局部超線性收斂)
假設 在單根 附近成立,即 且 。存在一個鄰域,使得該鄰域內任意兩個相異的起始點都會產生良定的割線序列並收斂至 ,除非某一步到達根而使算法停止。若序列從未到達根,則
因此,就此比值而言,收斂是超線性的。
證明
(先得固定收縮因子,再得趨零的比值)
把 周圍的閉區間縮小,使導數有正的下界 ,且二階導數有有限的上界 。選取足夠小的 ,使閉的 -鄰域落在此區間內,且 ,其中 。若當前兩個誤差均不超過 ,則乘積估計給出 。透過歸納法,所有點都保持在該鄰域內,並且誤差以幾何速度趨向零。只要當前點不是根,下一個點就與它不同;於是 在該區間上的嚴格單調性使下一個分母不為零。最後,。
證明透視
超線性強於固定的幾何因子
乘積估計首先給出固定的收縮因子 ,使迭代保持在受控的鄰域內。只有在兩個誤差均趨向零之後,我們才能把比值的界改進為 。此證明並不需要所謂黃金比例收斂階的說法,也不需要在每一步估計 。
例子與局限
例題 6.2.6
(割線迭代逼近二的平方根)
對於 ,取 、,
誤差為 、、,比值 、 都很小。下一個迭代點是 ,,。這些迭代點趨近 ;局部定理保證,只要兩個相鄰的迭代點落在足夠小的鄰域內,序列便會收斂,但它本身並不能證明任意的起始點對都會到達該鄰域。
常見錯誤
(割線法不保證根留在最新兩點之間)
上例中, 與 位於 兩側, 與 也是。但 與 都小於 ,根並不介於兩者之間,下一步 便跳到另一側,大於 (確實 )。與二分法不同,割線法並不維持變號的夾根區間,所以最新兩點本身不提供誤差保證。
反例模式
在到達根之前可能出現零分母
對於 ,相異的起始點 與 滿足 。即使兩點均不是根,割線的分母仍為零。穩健的實現必須檢測這種情況;只涉及單一單根附近的局部定理,並不能支持在整體範圍內忽略這一點。
這些假設在重根處同樣重要。對於 ,取正的相異起始值,遞推式化簡為 。導數在根處為零,因此在零附近不存在正的下界 ,上述定理並不適用。
例題 6.2.7
(二重根使超線性收斂失效)
對 和正的相異 ,上面的遞推式等價於 。記 ,得到 Fibonacci 遞推 ,所以 以 的速度增長,其中 ,而 。誤差比值 趨向 ,並非趨向 。例如 、 給出 ,即 :相繼比值為 ,趨近 。序列確實收斂,但只是線性收斂。
練習與解答
快速檢查
(對於 ,從 、 出發,計算一步割線迭代。)
先計算兩點的函數值。
解答 · 答案
且 ,所以 。
快速檢查
(為甚麼局部定理能確保差商不為零?)
把差商與 聯繫起來。
解答 · 答案
對所選區間中兩個不同的點, 連續且遠離零,因此由中值定理,差商的大小有下界 。
快速檢查
(對於 ,局部定理是否保證從 、 出發會收斂?)
比較兩點的函數值。
解答 · 答案
不保證:這兩個點並不位於同一個受控的單根鄰域內,而且它們的函數值相等,所以第一個分母為零。
快速檢查
(若乘積界成立,且兩個誤差均趨向零而從未到達根,解釋為甚麼誤差比值趨向零。)
把乘積界除以 。
解答 · 答案
把 除以 ,得到比值至多為 。