由一條方程到多條方程
「夾逼法與牛頓法」一課以切線代替 ,解單一方程 。許多問題有多個未知數及同樣多條方程,例如兩條曲線的交點。同一想法依然適用:在當前點以最佳線性近似取代映射,並解所得的線性方程組。新增的計算成分是每步要解一個線性方程組,所以本單元也用到消去法與分解各單元。我們證明局部二次收斂定理,並說明各假設如何失效。
定義
定義 2.5.1
(雅可比矩陣與牛頓步)
設 在開集 上連續可微,分量為 。其雅可比(Jacobi)矩陣為 ,元素 。根是滿足 的點 。 在 處的線性近似為 。牛頓(Newton)法令此近似為零:
此步恰在 非奇異時有定義;實際上從不顯式求 ,而是解方程組,例如用帶主元的 LU 分解。當 ,這就是熟悉的 。全篇 表示向量範數及其誘導的矩陣範數。
局部二次收斂
引理 2.5.2
(受擾動可逆矩陣的逆)
設 可逆且 ,則 可逆,且
證明
(提出未擾動的矩陣)
令 ,則 。級數 依範數收斂;相消求和 顯示其和為 ,範數至多為 。由於 ,乘積 正是 的逆,其範數至多為 。
定理 2.5.3
(牛頓法的局部二次收斂)
設 連續可微,, 非奇異,記 。假設在球 上雅可比矩陣滿足 Lipschitz 條件:。令 。若 ,則每個 都非奇異,所有迭代點留在球內,且
特別地,,且為二次收斂。
證明
(線性化誤差對照一致的逆矩陣界)
設 ,。首先 ,所以 ,且 。由 Neumann 級數(擾動)引理, 可逆,且 。設 為牛頓更新,則
沿線段用微積分基本定理,,所以方括號等於 ,其範數至多為 。因此 。由於 ,有 ,故 。每一步都可重複此論證,誤差趨於 。
證明透視
一個半徑擔當兩個任務
證明的關鍵,是把新誤差寫成 作用於線性化誤差。方括號 正是切線模型的偏差,Lipschitz 條件使它成為二次量 。球是凸集,所以由 到 的線段留在該條件成立的範圍內。 非奇異只透過 使用,而引理把它轉成根附近的一致界 。
半徑 擔當兩個任務:它令 ,使引理適用;又令 ,使新誤差至多為舊誤差的一半。第二個任務把 留在球內,同一估計才可在下一步再次使用,歸納因而閉合。若 奇異, 沒有定義,也不存在這樣的半徑;下面根處雅可比矩陣奇異的例子顯示,二次收斂此時確實喪失。
有兩點重要。二次收斂表示迭代點足夠接近後,正確數字的位數每步大約翻倍。其次,定理是局部的:對任意起始點它沒有說明任何事。
例題
例題 2.5.4
(圓與雙曲線)
解 ,它有根 。此處 ,行列式為 。由 開始。
第 1 步。 ,,行列式為 。解 :,即 。故 。
第 2 步。 ,,求解得 。
以最大範數量度,誤差為 ,下一個迭代點約為 :迭代點足夠接近後,正確數字的位數每步大約翻倍,與定理一致。
例題 2.5.5
(根處雅可比矩陣奇異)
對 ,唯一的根是 ,該處 奇異。第一個分量的牛頓步為 ,第二個分量一步便精確。因此第一個座標每次只減半:收斂是線性而非二次。單一方程的重根也出現同樣的損失。
例題 2.5.6
(以純量情形驗算)
取 ,,,步 為 。由 :,,故 。然後 ,,,與 相差約 。誤差 再次顯示正確數字位數翻倍。
常見錯誤與細微之處
- 收斂是局部的,可能收斂到另一個根。 圓與雙曲線的方程組有四個根:、、、,到達哪一個視乎起始點。
- 定理要求根處雅可比矩陣非奇異,且雅可比矩陣滿足 Lipschitz 條件。 缺少這些條件,收斂可能是線性的,甚至失敗。
- 成本。 每步需要 、 及一次分解,稠密 方程組約需 次運算。
常見錯誤
(以為牛頓步總是存在)
對圓與雙曲線, 在直線 上為零。在 ,雅可比矩陣為 ,是奇異的;由於 ,方程 無解,牛頓步沒有定義。實作必須偵測奇異或接近奇異的分解,而不是除以極小的主元。
常見錯誤
(把小殘差當作小誤差)
對 ,唯一的根是 ,。在 ,殘差範數為 ,誤差範數卻是一。只有當 不大時, 小才表示誤差小。
常見錯誤
(對雅可比矩陣求逆而非解方程組)
牛頓步只需解 。對稠密矩陣,帶主元的 LU 分解約需 次運算,而構造 約需其三倍,且通常徒增捨入誤差。
反例模式
牛頓法並非全局收斂
一個誘人的讀法是:只要根是單根,牛頓法由任何起點都收斂。取 、,唯一的根是 ,且 。由 出發,迭代 給出 、、,迭代點發散。這與定理並不矛盾:此處 ,而 在 取最大值 ,所以定理只保證 時收斂。全局收斂需要線搜索或區間等保障措施。
習題
快速檢查
(對 由 作兩步牛頓迭代,並與根 比較。)
第一條方程是線性的,所以每一步都保持 。
解答 · 答案
。在 :,。解 與 ,得 ,,,。在 :,。解 與 :,,。故 。到 的最大範數誤差由 降至 ,再降至 。
快速檢查
(對 及 ,求 並解釋為何收斂是線性的。)
兩個分量互不相關。
解答 · 答案
兩個分量互不牽連。 給出第一個座標 ,第二個座標當 時 (一步便精確,因 )。故 時 。誤差每步減半,是比值為 的線性收斂;根處雅可比矩陣奇異,所以定理不適用。
快速檢查
(對 ( 非奇異),證明牛頓法由任何 出發都一步到達解。)
的雅可比矩陣是 。
解答 · 答案
此時 ,。該步解 ,得 ,,即精確解。
快速檢查
(對 ,估計用 LU 分解解稠密雅可比方程組時,一步牛頓迭代的運算次數,取 。)
代入 。
解答 · 答案
次運算,另加計算 、 及三角求解()的低階項。