定位零點
數值根是滿足 的數 的近似值。僅給出迭代公式並不能保證收斂:必須說明起點及 所滿足的條件。不同方法在進展有保證與速度快之間作出取捨;而函數值很小是否有意義,還取決於逆問題在局部的敏感程度。
定義 6.1.1
(變號夾根區間)
設 在 上連續。若 ,即 與 皆非零且異號,則稱 為 的夾根區間。
介值定理保證夾根區間內至少有一個根。二分法在 處計算 ,若 則停止,否則保留端點異號的半區間,它同樣是夾根區間。
命題 6.1.2
(二分法誤差界)
設 是 的夾根區間, 是 次對半分割後保留的區間,其中 (若某個中點恰為根,方法在該處停止)。則 含有根,長度為 ,其中點到 內至少一個根的距離不超過 。
證明
(對半分割仍保持夾根)
每個保留的半區間端點異號,故由歸納法 是夾根區間,介值定理在其中給出一個根。每一步長度減半,得 。長為 的區間內任一點到中點的距離至多為 ,所以 內的根與其中點相距不超過 。
這些條件保證存在根和誤差界,並不保證根唯一;如果 嚴格單調,則至多有一個根。
例題 6.1.3
(二分法三步逼近 2 的平方根)
對 上的 ,,。第一個中點 處 ,故保留 。第二個中點 處 ,保留 。第三個中點是 ,,下一個區間為 。兩次對半分割後,中點 與根的距離不超過 ;實際上 ,。三次對半分割後,中點 的誤差界為 ,實際誤差約為 。
常見錯誤
(沒有變號不代表沒有根)
偶重根不一定伴隨符號改變,無法單憑變號檢測。對 上的 ,,所以 不是夾根區間,但 確是根。變號測試是存在根的充分條件,並非必要條件。
不動點迭代
將方程改寫為 ,並迭代 。只有當所選改寫在討論的定義域上建立了等價關係, 的不動點才是 的根。壓縮映射定理給出一個實用的充分條件。
定義 6.1.4
(區間上的不動點與壓縮映射)
設 ,。若 ,則 稱為 的不動點。若 ,且對所有 都有 (其中 ),則稱 是 上以 為常數的壓縮映射。
定理 6.1.5
(區間上的壓縮映射定理)
設 是 上以 為常數的壓縮映射。則 中有唯一不動點 ,從 內任意初值開始的迭代都收斂到它。此外,,且 。
證明
(幾何級數尾和與 Cauchy 序列)
迭代點始終留在 中,相鄰兩項之差滿足 。求幾何級數尾和可知迭代序列為 Cauchy 序列。由 的完備性和 的閉性,它收斂到某個 。Lipschitz 不等式保證 連續,因此 。若 是另一不動點,則 強制二者相等。將壓縮不等式直接用於 和 得到第一個界;求尾和得到第二個界。
若 在 上連續、在內部可微,則當 時,中值定理給出所需 Lipschitz 界。但區間映回自身是另一項獨立條件。
反例模式
導數很小但區間不被映回自身
命題:若在 上 ,則 在 中有不動點。取 上的 。此時 ,但 ,,所以 把 映到其外部。方程 的解為 ,因此 內沒有不動點。即使是導數為一的 ,在任何區間上也沒有不動點。修正方法是加上 ,壓縮映射定理除 Lipschitz 界外還需要這個條件。
用相鄰步長得到誤差界
定理的第一個估計含有未知的 。要得到可以實際計算的估計,可把剩餘步長相加。
命題 6.1.6
(可計算的不動點誤差界)
在 上的壓縮條件下,對 ,
證明
(把剩餘步長相加)
反覆應用壓縮不等式,得 ,其中 。先用三角不等式估計 ,再令 ,便得到幾何級數尾和,即第一式。對第二式,寫出 ,然後將最後一項移到左邊。
第二式使用的是不動點殘差 ;除非知道它與原方程殘差 的關係,否則不能直接用後者代替。
例題 6.1.7
(平方根的可計算誤差保證)
對 ,在 上取 。由於 位於 , 遞增,且 。它以 為壓縮常數,區間內唯一不動點為 。從 出發得到 、。第一個界保證
這個界偏保守:實際誤差約為 。但得到保證時並不需要知道根的小數展開。這裏假設精確算術;捨入後的步長和近似的 本身不自動構成嚴格的機器級包圍。
為甚麼小步長還需要壓縮常數
當 接近一時, 很大。若已證明 ,步長 對目前誤差只給出 的界。
常見錯誤
(小步長不等於小誤差)
僅憑 很小就停止,並不構成保證。 處處有 的步長,卻沒有不動點。滿足壓縮條件時,可在 低於指定絕對容差時停止;否則這個測試沒有同樣的保證。需要嚴格電腦證明時,還要單獨處理捨入誤差。
局部吸引與排斥
當起點不確定時,整個區間映回自身很有用。在已知不動點 附近,還可使用局部判據。
命題 6.1.8
(局部吸引與排斥)
設 在 的鄰域內連續可微,且 。
- 若 ,則存在 周圍的閉區間 , 把它映回自身且在其上為壓縮映射; 內每個起點都收斂到 。
- 若 ,則對所有 都有 的迭代不可能收斂到 。
證明
(導數在不動點的連續性)
設 。由連續性,存在閉區間 ,其上 。中值定理給出,對 ,,所以 ;對 內任意兩點作同樣估計,可知 在 上為壓縮映射。由壓縮映射定理得第一部分。
設 。連續性給出 周圍較小的區間 ,其上 ,於是由中值定理,對 有 。若 ,從某個下標 起各項都留在 內,於是 ,且 。這些距離不斷增大,與 矛盾。
排斥部分並未說明離開區間後迭代會到哪裏。
例題 6.1.9
(不動點處導數等於一)
時不能由此判定收斂或發散。以 、 為例:當 時,,且 ,故符號不變而絕對值遞減;絕對值收斂到某個 ,並滿足 ,所以 。相反, 對每個非零起點有 ,絕對值遞增,不可能趨於零。兩者在零處導數都等於一,不動點都是 。
快速檢查
(在 上取 ,從 開始。證明區間不變,計算 ,用最近一步估計 ,並與實際誤差比較。)
先求出不動點。
解答 · 答案
,且 。唯一不動點是 ;、。誤差界為 ,恰好等於實際誤差。這一例中的等號不代表一般的界就是精確誤差公式。
Newton 方法
在 處將 線性化,並令切線近似為零,得到
其中要求 。在單根附近,Newton 方法可以比二分法快得多;但更新可能離開原區間,也可能遇到零導數。
定義 6.1.10
(單根與二次收斂)
若可微函數 的根 滿足 ,則稱 為單根。若存在常數 ,使得對所有充分大的 都有 ,則稱序列 二次收斂。
例題 6.1.11
(Newton 迭代逼近 2 的平方根)
對 ,從 出發,更新式為 。因此 ,。誤差依次為 、、。比值 與 保持有界,與二次收斂的預測一致;正確的位數大約每步加倍。驗算:,,所以 的殘差為 。
概念視角分析
把 Newton 法看作不動點迭代
Newton 更新就是 的不動點迭代,其不動點正是 的根。當 而且 時,求導得 ,它在單根處為零。於是局部吸引定理適用,而且在 附近收縮常數可以取得任意小,這解釋了為甚麼 Newton 法的收斂比任何線性速度都快。對於 ,,而 。
定理 6.1.12
(Newton 方法的局部二次收斂)
設 在根 的某個鄰域上屬於 , 且 。當起點充分接近 時,Newton 迭代有定義並收斂到 ,而且存在常數 ,使 。
證明
(Taylor 餘項與縮小的鄰域)
縮小鄰域為 周圍的閉區間,使其上 且 。從 向 應用 Taylor 定理,得到 。因此下一步誤差的絕對值至多為 ,其中 。取半徑 使 的初始鄰域,每一步都有 ;迭代點始終留在鄰域內且誤差按幾何速度下降,平方誤差界於是每一步都適用。
證明透視
每個條件用在哪裏
兩個常數來源不同。 加上 的連續性,在整個區間上給出下界 ,使更新式中的除法有意義,並控制 。 條件給出 Taylor 餘項所需的上界 。證明中不易察覺的一步是半徑的選取:單憑平方誤差界,不能阻止下一個迭代點跑出量度 和 的區間。要求 把平方不等式變成 ,這樣迭代點才留在區間內,歸納得以完成。若去掉 ,就不存在正數 ,論證也得不到常數 。
單根條件很重要:對 ,Newton 更新為 ;非零初值只有線性收斂。不好的起點即使在有單根時也可能失敗。
反例模式
每一步都有定義卻不收斂
命題:若每一步都有 ,則 Newton 方法收斂到某個根。取 、。此時 ,,故 。接著 ,,故 。迭代永遠在 之間循環,兩點的導數都非零,函數值 和 也從不為零。實根約在 。修正方法是採用定理的局部條件:只有起點充分接近單根時才有收斂保證。
下方演示由 開始,這是上面由 算出的第一個 Newton 迭代值。獨立的二分法從寬度為 的 開始,要使中點誤差界小於 需九次二分;下面第一道練習的初始寬度是 ,需要十次。雙週期與零導數例子說明 Newton 步驟本身不是夾根證書。
常見錯誤
(殘差小不等於根誤差小)
若在 與根 之間有 ,中值定理給出 。當 很小時此界可能很大: 在零處的殘差為 ,根誤差卻為一。穩健實現應按合適尺度檢查殘差,並檢查步長和迭代次數上限;若同時維持端點異號的區間,還可獲得獨立的誤差保證。浮點捨入最終可能阻止任一測試值繼續下降。
練習與解答
快速檢查
(初始區間長度為 。二分多少次可保證中點誤差不超過 ?)
使用中點誤差界 。
解答 · 答案
中點誤差至多為 。由於 而 ,十次足夠,且是此界所能保證的最小次數。
快速檢查
(驗證 把 映到自身且在其上為壓縮映射,並找出該區間內的不動點。)
求 的最小值和 的取值範圍。
解答 · 答案
,且 在區間內的最小值為 ;故 ,區間映回自身。此外, 從 遞增到 ,所以其絕對值至多為 。正的不動點滿足 。
快速檢查
(對 應用 Newton 方法,求非零迭代點的收斂因子。)
化簡 。
解答 · 答案
當 時,,故線性收斂,因子為 。