動機
根是滿足 f(r)=0 的數。即使無法方便地寫出精確根,我們仍可計算近似值;但有用的近似應伴隨誤差判斷。圖像只能提示位置,不能證明零點存在或數字可靠。我們先建立保證存在性的區間,再研究局部可能更快的迭代。
二分法
設 f 在 [a,b] 連續且 f(a)f(b)<0。介值定理保證 (a,b) 至少有一個根。取中點 m=(a+b)/2:若 f(m)=0 便停止;否則保留端點函數值異號的半區間。每一步由連續性和異號性保留至少一個根。初始區間可能有多個根,方法並不找出所有根。
經 n 次二分後,區間長度為 (b−a)/2n;其中心 mn 到該區間內任何根 r 的距離至多為半個區間長度:
∣mn−r∣≤2n+1b−a.
因此只須令右邊不超過 ε,便保證絕對誤差不超過 ε。上述證明假設算術和符號判斷精確;實際捨入可能影響符號,最終中點亦可能與端點相同;穩健的實作必須顧及這一點。
例如 f(x)=x2−2,由 [1,2] 開始。f(1.5)>0,保留 [1,1.5];f(1.25)<0,保留 [1.25,1.5];f(1.375)<0,保留 [1.375,1.5]。最後中點 1.4375 距區間內某根至多 0.0625,全程毋須導數。
異號是充分條件而非必要條件:(x−1)2 在 [0,2] 兩端皆為正,仍在 1 有根。沒有連續性時,異號亦不足夠:1/x 在零兩側異號,但在包含零的區間不連續,也沒有零點。
牛頓迭代
在 f′(xn)=0 時,牛頓(Newton)迭代用切線 f(xn)+f′(xn)(x−xn) 近似曲線;令切線為零,得到
xn+1=xn−f′(xn)f(xn).
對 f(x)=x2−2,由 x0=1.5 開始,x1=17/12≈1.4166667,x2=577/408≈1.4142157。它們很接近 2,但快速收斂是局部結論,並不適用於所有起點。
若 f 在根 r 附近二次連續可微且 f′(r)=0,則起點充分接近 r 時,迭代有定義、留在該鄰域並收斂至 r,且對某常數 C 有 ∣xn+1−r∣≤C∣xn−r∣2。
記 en=xn−r。由於 f′ 連續且 f′(r)=0,存在 ρ>0 與 m>0,使 f 在 J=[r−ρ,r+ρ] 上屬於 C2,並且在 J 上 ∣f′(x)∣≥m。令 K=Jmax∣f′′∣、C=K/(2m);若 C=0 取 δ=ρ,否則取 δ=min(ρ,1/(2C))。
設 ∣en∣≤δ。則 xn∈J,故 f′(xn)=0,xn+1 有定義。從 xn 向 r 使用泰勒(Taylor)定理,對兩點之間(因而在 J 內)的某個 ξn,
0=f(xn)+f′(xn)(r−xn)+21f′′(ξn)(r−xn)2.除以 f′(xn) 並代入牛頓公式,得
en+1=2f′(xn)f′′(ξn)en2,∣en+1∣≤Cen2≤Cδ∣en∣≤21∣en∣.由歸納法,只要 ∣e0∣≤δ,每個迭代值都有定義、留在 [r−δ,r+δ] 內,且 ∣en∣≤2−n∣e0∣→0。不等式 ∣en+1∣≤Cen2 就是二次界。鄰域與常數依賴函數和根,定理並沒有提供全局起點規則。
證明透視
鄰域是怎樣選出來的
每個假設只用一次。二次連續可微給出帶點 ξn 的泰勒餘項,並由緊緻區間上的連續性給出有限的 K。條件 f′(r)=0 只用來在 r 附近保持 ∣f′∣≥m,使分母 f′(xn) 既非零又受控制。兩者合起來產生一個常數 C=K/(2m)。
不顯然的一步是選取 δ≤1/(2C)。單靠二次恆等式推不出收斂,因為 ∣en∣ 大時 Cen2 可以超過 ∣en∣。但在半徑 δ 的鄰域內有 Cen2≤21∣en∣,這同時完成兩件事:使下一個迭代值留在常數仍然有效的鄰域內,並迫使誤差按幾何級數遞減。只有在收斂已知之後,這個界才讀作二次收斂。若 f′(r)=0,m 須隨鄰域縮小,C 沒有上界,論證根本無法開始。
起點與根同樣重要。對 f(x)=x3−2x+2,牛頓映射把 0 送到 1,又把 1 送回 0;起點不夠接近時,迭代可以循環而根本不收斂。
反例模式
二重根處二次界失效
一個誘人的說法是:牛頓法在光滑函數的每個根附近都二次收斂。取 f(x)=(x−1)2,它光滑、根為 1,但 f′(1)=0。對 xn=1,
xn+1=xn−2(xn−1)(xn−1)2=2xn+1,en+1=21en.若對所有足夠大的 n 都有 ∣en+1∣≤Cen2,便得 21≤C∣en∣;但 en→0,這不可能。收斂只是線性的。修正後的命題正是上述定理:根必須是單根,f′(r)=0。對這個已知為二重根的 f,修正步 x−2f(x)/f′(x) 一步便落在 1。
停止與保護
步長小可能表示收斂,也可能來自捨入或尺度不佳。殘差小必須配合敏感度判斷:f(x)=10−12(x−1) 在 x=0 的殘差雖為 10−12,根誤差卻是 1。若 x 與根 r 之間處處有 ∣f′∣≥m>0,中值定理才給出 ∣x−r∣≤∣f(x)∣/m。
在單根附近,步長 ∣xn+1−xn∣ 與誤差 ∣xn−r∣ 的主導項相同,所以常被用作停止準則。在重根附近卻不是這樣。對 f(x)=(x−1)2 及 xn=1.1,步長為 f(xn)/f′(xn)=0.01/0.2=0.05,誤差卻是 0.1。沒有導數界或夾逼區間時,步長小只是跡象,而不是保證。
一個實用策略是保持連續函數的異號區間,只在牛頓步安全地落於區間內時接受,否則二分,再用新點的符號更新區間。具體實作仍須規定接受及停止準則,但保留區間可持續提供存在性證明。
不動點觀點
牛頓法可寫成 xn+1=g(xn),其中 g(x)=x−f(x)/f′(x),只在分母非零時有定義。更一般地,若 g 在閉區間 I 上可微、把 I 映到自身,且區間上處處有 ∣g′(x)∣≤q<1,則從 I 任何起點的迭代均收斂至其中唯一的不動點。
中值定理給出 ∣g(x)−g(y)∣≤q∣x−y∣;相鄰兩項的距離因此按幾何級數遞減,其和有限,故迭代是閉區間內的Cauchy 序列。由連續性,極限是不動點;把同一不等式用於兩個不動點便得唯一性。
這些條件充分但非必要。它們證明的是 g 的不動點,仍須核對該點是否解原方程。牛頓映射在單根處有 g′(r)=0,與局部快速收斂一致;但 f′ 為零時映射無定義,不能跨越該點套用定理。
例如 x2=2 可寫成 g(x)=(x+2/x)/2。在 I=[1,2] 上,g 映區間到自身,且 ∣g′(x)∣=∣1−2/x2∣/2≤1/2,因此定理保證該區間內任何起點均收斂。這比觀察幾步似乎有效提供更強的依據。
根的敏感度與重根
設 f(r)=0、f′(r)=0,把方程擾動為 f(x)+η=0,其中常數 η 很小。若新根為 r+Δr,泰勒展開給出 f′(r)Δr+η 約為零,故 Δr≈−η/f′(r)。導數小會放大垂直擾動;這是絕對敏感度陳述。重新縮放函數也會縮放 η,因此必須說明單位和擾動模型。
重根的反應可能更劇烈。f(x)=x2 改成 x2−ε=0(ε>0)有兩根 ±ε;改成 x2+ε=0 則沒有實根。小垂直擾動可改變根的位置及實根數量。這不違反牛頓法二次收斂定理,因為零點處 f′(0)=0,不符合定理假設。
比較收斂速度
例如,若最終有 ∣en+1∣≤q∣en∣,其中 q<1,誤差便線性收斂;若最終有 ∣en+1∣≤C∣en∣2,便二次收斂。二次迭代足夠接近根後正確位數可快速增加;線性方法每步大致增加固定數目的位數。這些描述針對漸近誤差,並非每步成本。牛頓法需要導數,遠離根時可能失敗;二分法則保留區間及簡單的最壞情況界。
對 x2−2 從 x0=1 開始,牛頓步依次為 3/2、17/12、577/408。代入迭代式並化簡,得到精確誤差恆等式
xn+1−2=2xn(xn−2)2.這裏正的迭代值遠離零,因此平方誤差解釋了快速收斂。起點可能與後續點位於根的不同側;牛頓序列本身一般不保持夾逼區間。
二分法的收斂證明
保留的閉區間互相嵌套、長度趨零,且每個都由介值定理包含根;端點因而趨向共同極限。連續性證明極限為零點:若極限的函數值嚴格為正或負,則充分接近的兩個端點會有相同符號,與始終異號矛盾。故存在性及區間收縮共同解釋收斂;單有區間長度趨零,沒有連續性和異號,不能證明極限是根。
後驗誤差與停止例子
先驗界在計算前選定,例如二分法所需步數;後驗界利用計算後得到的數據。若保留連續異號區間 [an,bn],其中點與區間內任何根的距離至多 (bn−an)/2,與之前採取了多少安全牛頓步無關。相反,牛頓修正量 ∣f(xn)/f′(xn)∣ 本身一般不是嚴格誤差界,因為它依靠切線近似。
考慮 f(x)=x2−2 及區間 [1,2],假設計算得 x=1.4142。區間上 f′(x)=2x≥2,中值定理給出 ∣x−2∣≤∣x2−2∣/2。此處 x2−2=−0.00003836,故界為 0.00001918。精確誤差更小,但推導這個界並不需要知道精確根的小數展開。導數下界須在近似點與根之間成立,只知道近似點的導數並不足夠。
停止規則應說明所需絕對或相對容許誤差,以及所界定的量。夾逼寬度控制絕對根誤差;殘差準則在尺度不同時可能方便,但要配合敏感度估計才能保證根的準確度。接近零時,即使用相對準則也需考慮絕對容許誤差。此外,應設最大步數或停滯檢查,避免不斷重複同一浮點值;若未達所需保證,停止時須如實報告,而非稱結果準確。
對下面最後一題的 f(x)=x3−1,f′(x)=3x2 在零處為零,因此「處處 f′(x)>0」的較強命題不成立。然而因式分解 y3−x3=(y−x)(y2+xy+x2) 直接證明嚴格遞增。反過來,單有導數非負仍容許函數在某區間為常數;嚴格遞增需要額外論證。
存在、唯一、收斂和迭代值的數值準確度是四個不同的結論,各有自己的假設。
總結
連續異號區間證明根存在,並以寬度控制中點誤差;它既不保證唯一,也可能漏掉不變號的根。牛頓切線迭代在單根附近常有二次收斂,但導數及起點假設不可省略。保護式方法可用夾逼區間約束牛頓步,同時保留局部快速收斂的可能。
判斷結果時應先確定證據:夾逼區間、配合導數下界的殘差,或另有根據的後驗估計。f(x) 的大小取決於函數尺度,距根的距離還取決於斜率。因此把 f 乘以非零常數不改變根,卻改變原始殘差。停止規則須考慮此區別及有限精度停滯。
找到一個根並未解決所有根的問題。二分法在一個區間找到根之後,原區間內外仍可能有其他根;要計算根的數目,需要單調性或其他數根定理等額外數據。有限個採樣點的數值圖像無法排除採樣點之間未觀察到的振盪。
練習
快速檢查
(從 [1,2] 二分求 x3−2 的根,至少多少次能保證中點誤差不超過 10−3?)
使用誤差界 (b−a)/2n+1。
解答 · 答案
要求 2−(n+1)≤10−3。由 210=1024,n=9 足夠;此界下 n=8 不足。
快速檢查
(對 x2−3 從 x0=2 做一步牛頓法。)
這裏 f′(x)=2x。
解答 · 答案
x1=2−(4−3)/4=7/4。
解答 · 答案
函數可如 (x−1)2 在 [0,2] 接觸橫軸而不變號;穿過橫軸兩次也可使端點同號。
快速檢查
(設 f(x)=x3−1,區間為 [0,2]。證明其中恰有一個實根,然後做兩步二分。最終區間中點是否必然是精確根?說明甚麼數據保證唯一性。)
解答 · 答案
函數連續且端點值異號。它在實數上嚴格遞增,因為 y>x 時 y3−x3=(y−x)(y2+xy+x2)>0;所以根唯一。第一個中點是 1,且 f(1)=0,方法即停止,毋須第二步。恰好命中是本例的特殊性質,並非一般保證;沒有單調性時,初始異號只保證至少一個根,並不保證恰好一個。