為甚麼不能直接套用常見定理?
牛頓(Newton)法以切線近似函數,並把切線的零點用作下一個近似值。對於單根 ,導數不為零使局部二次收斂定理成為可能;在重根處切線水平,因此不能直接套用該定理。方法仍可能收斂,但速度通常改變。以下公式都討論精確實數運算;有限精度下的函數計算和停止判據需要另行分析。
定義 2.4.1
(重數為 的根)
若在包含 的開區間上
其中 是整數(此處 ), 在 附近屬於 ,則稱 是 的 重根。這個分解比單獨知道 更具體:它指明了第一個不為零的因子。
以下假設有這樣的分解,且 。記 ,普通迭代和重數修正迭代分別為
只在 且導數非零時使用這些式子。如果已知到達根,就應停止,而不是計算 。
誤差恆等式與局部收斂
定理 2.4.2
(重數的影響)
在上述條件下,當 充分接近 且 時,兩種迭代均有定義,而且
初值充分接近時,兩種迭代都收斂到 。若普通迭代沒有在有限步內到達根,則相繼誤差的絕對值滿足
對某個常數 ,修正迭代在局部滿足 。這是上界:特殊情況下修正法可能更快,甚至恰好終止。
證明
(約去誤差的公共冪)
微分得到 。方括號趨向非零數 ,因此在足夠小的鄰域內不為零。對 約去 ,便得兩個恆等式。普通迭代的誤差乘數趨向 ,它嚴格介於零與一之間。由連續性,在更小鄰域內,乘數的絕對值有固定上界 ;因此迭代點留在鄰域內,且 。若誤差從不為零,再取乘數極限即得所述比值。
對修正公式,連續性使 在局部有上界,而 有正的下界,所以 。進一步縮小初值鄰域,使 且後續迭代點都留在鄰域內,誤差便趨於零。如果某一步等於 ,就停止。這個局部證明不保證任意初值都收斂。
證明透視
每個假設在哪裏用到
證明包含一個代數步驟和兩個分析步驟。代數步驟是導數的分解 :使 的同一個冪 也整除 ,所以即使 與 都在 處為零,牛頓商 仍是 的光滑倍數。條件 用了兩次:它使方括號 遠離零,因而兩種更新在 附近都有定義;它也使普通乘數趨向 ,而不是不定式。
第一個分析步驟把極限化為一致上界。乘數只是趨向一個小於一的數,還不足以說明迭代點留在 附近;選取乘數絕對值不超過 的鄰域,這鄰域便映入自身,之後才可反覆使用上界得到 。第二個步驟針對修正更新:利用已知的 恰好消去分子的一階部分,剩下 。 在 附近連續,因而分子有界,這就給出常數 。若所用因子不等於 ,消項便失敗,線性項會保留下來。
定理預測的收斂速度,在實際觀察迭代時很容易被誤讀。
常見錯誤
(在根附近收斂不等於二次收斂)
普通牛頓迭代收斂,並不表示它具有單根時的二次收斂速度。在二重根處,誤差漸近地每步減半;要把誤差再縮小 倍,約需 步,因為 。誤差比穩定在 附近,是重根的徵兆,而不是程式錯誤;它正是提示我們估計 的訊號。
算例:修正後的第一步
例題 2.4.3
(二重根處的一步普通迭代與一步修正迭代)
令 ,從靠近 的 出發。這裏 ,。因為 、,商為 ,於是
事實上,只要分母非零,修正迭代的精確誤差映射為 ;在 處它給出 ,與上面計算一致。在零附近新誤差約為 。本例的第一步誤差更小,說明了定理,但不意味著修正對任意初值都更好。此函數還有另一個單根 。
例題 2.4.4
(普通迭代的誤差比趨向二分之一)
對同一函數,,所以當 且 時
因此 ,當 時趨向 ,與定理一致。在 處比值為 ,得 ,與前例相同。由於對 , 嚴格介於 與 之間,任何正初值都給出遞減的正誤差,而相繼比值從上方趨向 。這是線性收斂:誤差每步約減半,而不是平方。
重數選錯與數據敏感性
如果改用整數或實數係數 ,更新 的局部誤差乘數趨向 。因此錯誤係數通常留下線性項;以上論證只在 ,即 時給出局部收縮。區間外不能由此論證保證收縮,兩個端點也須另行分析。
例題 2.4.5
(端點因子 產生二週期)
取 ,於是 、,並用 。對 ,,所以
從 出發,迭代值為 :誤差的絕對值從不改變,序列不收斂。乘數恰為 ,位於收縮區間的邊界,這正是端點情況必須排除的原因。若改用 ,則 ,序列正負交替但收斂,乘數為 。
常見錯誤
(猜測的重數可能損害單根)
因為根「可能是二重根」就把牛頓步長加倍,並非無害。對 的單根(),取 的更新給出 ,就是上例的二週期;而普通牛頓法一步便到達 。只有在重數已知或已被可靠估計時,修正才有根據。
反例模式
殘差小不代表根誤差同樣小
對 ,在 處函數值僅為 ,但到根的距離是 。殘差以函數值為單位,本身不能證明 有同樣小的數值誤差。另外,將方程改為 ,當 時根變為 ;改為 則沒有實根。對未擾動方程快速收斂,並不能消除問題本身對變化的敏感性。
練習與解答
快速檢查
(對 ,推導普通牛頓更新和修正更新。)
解答 · 答案
當 時,。普通牛頓法給出 ,所以誤差恰好乘以 。使用 的修正法一步得到 。此時停止,因為下一次商沒有定義。
快速檢查
(根的重數為 ,若使用因子 ,極限誤差乘數是多少?)
解答 · 答案
。其絕對值小於一,所以局部收縮論證適用,但收斂是線性的:這不是 時的二次消項。
快速檢查
(對 ,從 計算一步修正迭代。)
解答 · 答案
由精確映射 ,。這一步誤差由 降至 ,接近預測值 。
快速檢查
(對 和 ,殘差 能否證明 ?)
解答 · 答案
不能。對這個特定函數只能推出 ,而 達到上界。要由殘差得到實用的誤差界,還需要根附近函數的額外資訊。