定位零點
數值根是滿足 的數 的近似值。僅給出迭代公式並不能保證收斂:必須說明起點及 所滿足的條件。不同方法在進展有保證與速度快之間作出取捨;而函數值很小是否有意義,還取決於逆問題在局部的敏感程度。
定義 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 序列,準確計算已保留的二分次數、檢視下一個切線提案,並分清已證誤差界、小殘差與重複的儲存數值。
兩個序列各有自己的狀態
I_k 是經 k 次中點符號測試後保留的區間。目前中點 m_k 會為顯示而計算,但尚未用它再二分。Newton 獨立要求 k 次更新;若較早停止,完成次數便停在該值。更改例子會重設 k,更改容限則保留目前狀態。
f(x)=x²−2; I0=[1,2]; Newton x0=3/2.
目前包圍區間與 Newton 切線
垂直陰影帶是 I_k,短虛線標示其中點,空心菱形位於 (m_k,f(m_k))。實心圓是目前 Newton 點 (x,f(x)),長虛線為切線;導數為零時切線是水平線。只有流程仍繼續時,軸上的 × 才標示下一提案;停止後不再顯示提案。曲線只以取樣繪圖,認證來自精確區間運算與表格。極窄陰影帶可能小於一像素。
目前保留區間 I_k: [1,2]; 目前中點 m_k: 3/2; Newton 迭代值 x: 1.500000; 流程狀態: 繼續.
| 保留二分次數 k | 目前保留區間 I_k | 目前中點 m_k | 精確 f(m_k) | 已認證中點誤差界 |
|---|---|---|---|---|
| 0 | [1,2] | 3/2 | 1/4 | 1/2 |
| Newton 已完成更新次數 | Newton 迭代值 x | Newton 殘差 |f(x)|,僅供示範 | x 處導數 | 下一切線提案 | 流程狀態 |
|---|---|---|---|---|---|
| 0 | 1.500000 | 0.250000 | 3.000000 | 1.416667 | 繼續 |
二分表以精確分數顯示。對這些明確乘加多項式,k≤12 的二進有理端點與中點計算所需有效二進位少於 53;專項核對另以整數運算驗證每個符號與值。Newton 使用普通 Number 算術及四捨五入標籤,並非一般的經驗證符號 Newton 解算器。
已顯示 Newton 下一提案。二分認證屬於 m_k,沒有套用到此 Newton 迭代值。
- 目前區間寬度
- 1
- 已認證中點誤差界
- 1/2
- 容限 τ
- 1/1000
- 首次足夠的保留二分次數
- 9
- 寬度界已認證所需容限
- 尚未
- Newton 已完成更新次數
- 0
- 流程狀態
- 繼續
k=0; 目前中點 m_k: 3/2; 已認證中點誤差界: 1/2. 此寬度界尚未認證所需容限。實際中點誤差可能已較小,並未證明實際精度不達標。 Newton 已完成更新次數: 0; 流程狀態: 繼續.
哪一項敘述提供誤差認證?
兩個多項式均連續。x²−2 在 [1,2] 端點異號,導數 2x≥2,故根唯一。x³−2x+2 在 [−2,−1] 的端點值為 −2、3,導數 3x²−2≥1,同樣只有一根。異號要配合連續性才能保證存在,單靠符號也不是偵測所有根的一般方法。
二分法用已測中點替換同號端點,保留異號區間並把寬度減半。初始寬度為一,I_k 寬度是 2⁻ᵏ,目前中點與區間內根的距離至多 2⁻ᵏ⁻¹。τ=1/d 時,精確充分條件為 d≤2^(k+1),d=10、100、1000 分別需 k=3、6、9。k=0 的初始中點已有 1/2 界;計算它本身不算一次已保留二分。
對 x²−2,首四個已測中點為 3/2、5/4、11/8、23/16,值為 1/4、−7/16、−7/64、17/256。四次二分後保留 [11/8,23/16],下一中點是 45/32,誤差至多 1/32。九次二分給第十個中點,界為 1/1024<1/1000。這是最壞情況包圍界,並非聲稱實際誤差恰等於它。
Newton 解切線方程 f(x)+f'(x)(t−x)=0,在 f'(x)≠0 時得 N(x)=x−f(x)/f'(x)。對 x²−2,有 N(x)=(x+2/x)/2,從 3/2 起得到 17/12、577/408。x>0 時的精確恆等式 N(x)−√2=(x−√2)²/(2x) 解釋快速改善。一般的局部二次界需要導數遠離零、f'' 有界,且迭代留在相應鄰域。任意起點未必滿足;本圖三次式有精確 0→1→0 週期,零導數例子則沒有 Newton 提案。
殘差是函數值,不是距離。g(x)=10⁻¹²(x−1) 在 x=0 的殘差為 10⁻¹²,根誤差卻為一。|x−α|≤|f(x)|/μ 需要到根的整段路徑上 |f'|≥μ>0,並非只在所示點成立。四捨五入的零或重複浮點數同樣不是精確根證明。此處區間認證建基於連續性、唯一性及有限二進有理計算的精確符號,沒有轉移到區間外的 Newton 點。
即時檢查:保留九次二分後,獲認證的是第九還是第十個中點?
是第十個;若原中點編為 m0,就是 m9。九次更新保留寬度 1/512 的 I9,其中點的界是 1/1024。若只測 m0 至 m8,目前區間會不同,不能因此把 m8 稱為具有該界的中點。
三個固定例子、最多 12 次二分及三個容限。Newton 遇零導數或儲存值重複便停止,不暗中切換二分。不實作受保護混合算法、任意函數驗證、精確 Newton 運算或真實誤差神諭;本課討論殘差、步長與夾根區間;並未推導受保護混合算法。
常見錯誤
(殘差小不等於根誤差小)
若在 與根 之間有 ,中值定理給出 。當 很小時此界可能很大: 在零處的殘差為 ,根誤差卻為一。穩健實現應按合適尺度檢查殘差,並檢查步長和迭代次數上限;若同時維持端點異號的區間,還可獲得獨立的誤差保證。浮點捨入最終可能阻止任一測試值繼續下降。
練習與解答
快速檢查
(初始區間長度為 。二分多少次可保證中點誤差不超過 ?)
使用中點誤差界 。
解答 · 答案
中點誤差至多為 。由於 而 ,十次足夠,且是此界所能保證的最小次數。
快速檢查
(驗證 把 映到自身且在其上為壓縮映射,並找出該區間內的不動點。)
求 的最小值和 的取值範圍。
解答 · 答案
,且 在區間內的最小值為 ;故 ,區間映回自身。此外, 從 遞增到 ,所以其絕對值至多為 。正的不動點滿足 。
快速檢查
(對 應用 Newton 方法,求非零迭代點的收斂因子。)
化簡 。
解答 · 答案
當 時,,故線性收斂,因子為 。