從純量切線到線性方程組
設 ,我們要求 。僅有一個分量的殘差很小並不夠:所有方程都必須同時成立。在當前估計 附近,線性化給出
其中 是由偏導數組成的 Jacobian 矩陣。
定義 6.3.1
(Newton 步)
當 可逆時,Newton 步 是線性方程組
的解。
實現時應求解線性方程組,而不是顯式計算 。直接求解通常比顯式構造逆矩陣更省計算,且具有較好的後向誤差性質。兩種做法都不能消除病態 Jacobian 帶來的敏感性,因此計算出的步長仍可能不準確。矩陣奇異時,線性方程可能無解或有多個解,因此 (1) 並不自動有定義。
例題 6.3.2
(圓與直線)
考慮
兩個解分別是 ,其中兩座標同號。若某次迭代位於直線上,即 且 ,則 (1) 的第二行迫使步長兩分量相等,第一行再給出
從 開始,、,已接近 。這是一個真正的向量 Newton 計算,只因對稱性而化成一維。只要第一步有解,即使起點不在直線上,第二行也會使下一迭代點恰好落在直線上。不同起點可能收斂到另一個根。令 且 ,精確誤差恆等式 顯示出該根附近的二次行為。
二次收斂究竟需要甚麼假設
使用歐氏(Euclidean)範數及其誘導矩陣範數,並記 為半徑 的閉球。
定義 6.3.3
(Lipschitz Jacobian)
若對所有 都有
稱 Jacobian 在 上具有 Lipschitz 常數 。
需要兩個事實:Jacobian 在根附近保持可逆,而且其逆保持有界。
引理 6.3.4
(根附近的 Jacobian 保持可逆)
設 在 上以常數 Lipschitz 連續, 可逆,並令 。若 ,則對每個 ,矩陣 可逆,且 。
證明
(擾動 Jacobian 的 Neumann 級數)
令 、、。則 。當 時,級數 收斂到 ,所以 可逆,且 。由於 , 可逆,並且 ,其範數至多為 。
定理 6.3.5
(局部二次收斂)
設 在包含閉球 的開集上連續可微,,並且 在該球上以常數 Lipschitz 連續。假定 可逆,記 ,並選
對每個 ,每一步精確 Newton 迭代都有定義,所有迭代點留在球內,且
因此 ,且第一條界給出至少二次收斂。這裏假設線性方程精確求解。另一個情形是球內 為常矩陣():一次精確迭代即到根,此時不使用上面的半徑公式。所選的正 半徑只是充分界,並未聲稱最優。線性系統非精確求解或捨入會加入擾動,(2) 不必原樣成立。
證明
(積分餘項與歸納)
設 ,。由引理, 可逆且 。從 到 的線段包含在球內,沿線段應用微積分基本定理可得
令 ,減去 並提出 ,得到
Lipschitz 條件將被積向量的範數界為 。由引理,
又因 ,該值至多為 。歸納可知所有迭代點留在球內並收斂;第一條不等式證明了 (2)。若 ,積分公式直接化為 ,所以 。
證明透視
顯式二次誤差界來自哪裏?
可逆給出常數 ;Lipschitz 常數用了兩次,一次在引理中使 保持接近 ,一次在積分餘項中。關鍵一步是把 寫成 Jacobian 沿通向根的線段的積分。在 中,Newton 步已把一階項恰好抵消,只剩下 的變化乘以 ,這提供了誤差的平方。證明得以收尾,是因為 把二次界變成減半,使下一個迭代點仍在球內。若 不可逆,常數 便不存在;對 ,誤差只是減半。定理是局部的:它沒有找到未知的根,也沒有證明任意起點都會進入這個球。
例題 6.3.6
(在純量方程上檢驗誤差界)
對 ,有 、根 、、,所以 ,且 。起點 的誤差 。Newton 步為 ,得 、、。誤差約為 、、。比值 約為 、、,都不超過 ,與 (2) 一致,並趨向 。正確的位數大致每步翻倍。
定理沒有排除的失敗方式
反例模式
起點的 Jacobian 奇異
在圓與直線的例子中, 處 Jacobian 的第一行為零,但 的第一分量為 。因此 Newton 線性方程組無解。兩個根處的 Jacobian 雖然可逆,卻不能保證每個起點都能計算第一步。
例題 6.3.7
(奇異的根只給出線性收斂)
即使每一步都有定義,多重根附近的收斂仍可能很慢。對 ,Jacobian 為 ,若 ,任意 都產生 。從 出發,迭代點依次為 。根 處的 Jacobian 奇異, 方向誤差每次只減半,所以定理中「 可逆」這一假設不能去掉。
所以,對實際方程組,僅憑步長或殘差決定停止,需要考慮尺度和條件數。阻尼或線搜索可能幫助避免不良步長,但對任意方程組都不能無條件保證全局收斂。
常見錯誤
(因為殘差小就停止)
沒有適當的逆或條件數界時,殘差小不必然意味著誤差小: 在 處殘差為 ,但到根的距離為一。
常見錯誤
(把局部定理當成全局保證)
定理只涉及 內的起點,並且需要已知根和 Lipschitz Jacobian。它沒有證明任意初始猜測都會收斂,也沒有證明根存在;圓與直線的例子中就有一個起點連第一步也不存在。
練習與解答
練習 6.3.8
(計算 在 處的 Jacobian 並解出 Newton 步。)
基礎
解答(3)
- 1
在 處計算 和
- 2
解 Newton 方程組
取 ,第一行給出 ,所以 。
依據: 第二行給出 ,所以兩個分量相等。
- 3
得出下一個迭代點
。驗算:,殘差遠小於 。
快速檢查
(對 ,為何 時到 的收斂不是二次的?)
計算兩次迭代。
解答 · 答案
,第一步後 。 始終為 ,但二次收斂界會迫使這一比值趨於零;根處 Jacobian 奇異。
快速檢查
(定理中若 、,且 ,給出一個允許的正半徑。)
比較 與 。
解答 · 答案
此時 ,所以 是允許的,任何更小的正半徑也是。
快速檢查
(為甚麼僅憑 ,不能對所有方程組給出統一的到根距離界?)
試試 。
解答 · 答案
對函數族 , 處殘差隨 趨於零,而到根的距離一直為一。
快速檢查
(局部定理是否證明所有起點都收斂?指出它在根附近需要的一個條件。)
看一看假設清單。
解答 · 答案
否。定理的一個假設是 可逆;它還要求 滿足 Lipschitz 界,且起點足夠接近根。對於球外任意起點,定理沒有給出結論。