從方程到迭代
用迭代法求解 ,首先要作一個選擇:把方程改寫成 ,再計算 。同一個方程的兩種等價改寫,迭代效果可能截然不同。開始之前,要在所討論的定義域上檢查兩個方向:所求的零點是否都是不動點?考慮範圍內的不動點是否都是原方程的零點?如果把 乘上一個可能為零的因子,就可能引入多餘的不動點。
即使改寫等價,迭代也未必收斂。設計方法時可以問:能否找到一個包含目標零點的閉區間,使 把區間映回自身,並使區間內任意兩點的距離縮小?兩個條件作用不同:映回自身使所有迭代點留在估計有效的區域;壓縮條件則控制誤差。
定理 2.3.1
(可計算的不動點誤差上界)
設 是非空有界閉區間,,並且存在已知常數 ,使得
對任意 ,迭代 收斂到 內唯一的不動點 。當 時(在上界中約定 時 ),
當 時,
知道第一步後,前者便可用於先驗估計;後者利用最近一次算出的步長。若 ,則 在 上為常數,且 。
上界從何而來
證明
(幾何級數的尾項控制其後每個迭代點)
記 ()。壓縮條件給出 ,因此 。對 ,由三角不等式和等比數列求和,
因為 ,當 增大時右邊一致趨於零,所以迭代點構成Cauchy 序列。實數的完備性和 的閉性保證極限 在 內。壓縮不等式保證 連續,於是在 中取極限得到 。若 是另一個不動點,則 迫使 。令上式中的 即得後驗上界;從 起對步長求和則得先驗上界。這些估計假設精確運算,並要求 有可靠依據,不能只憑幾步觀察猜測。
證明透視
映回自身、閉性與壓縮各用在哪裏
證明只依賴一個估計 ,而它同時需要兩個假設:壓縮不等式之所以可以用於 與 ,是因為映回自身使每個迭代點都留在 內。關鍵一步是用幾何級數的尾項控制兩個迭代點之間的距離:。令 ,這個 Cauchy 估計便成為誤差界。這就是後驗上界是最近一步乘以 、而非最近一步本身的原因:這個因子計入了其後所有步長,而 接近一時它很大。
的閉性與實數的完備性把極限放在 內。沒有閉性,結論便不成立: 以 把 映到自身,但其不動點 不在區間內。條件 另外還用了兩次:保證幾何級數收斂,以及證明唯一性。
若 在 上連續、在內部可微,且內部滿足 ,中值定理便給出壓縮不等式。導數檢驗不能代替另外檢查 。
常見錯誤
(只檢查導數而不檢查值域)
在 上取 ,處處有 ,導數檢驗通過。但 與 不相交,而 在實數上唯一的不動點是 ,不在 內。從 出發得到 ,收斂到 。由於映回自身不成立,定理關於 內不動點的結論無從談起。
完整算例
例題 2.3.2
(求正根的不動點迭代)
在 上求 ,取 。當 時,,而且
定理保證 內有唯一不動點。由於區間上 , 與原方程等價。從 出發,得到
最近一步的大小為 。取 ,便得到 的可計算誤差上界:
這個保證不需要先知道精確根 或其小數值。上界可能偏保守,但區間和導數界都已事先證明,因此它是有效的。
例題 2.3.3
( 的保守先驗步數)
在 上取 。由於 在此遞減,,且 。從 得 ,所以先驗上界為 。要保證誤差不超過 ,需要
因此 獲得保證(上界約為 ), 則否(約 )。事實上,迭代點在 時首次與不動點 相距不超過 ,因為在 附近局部因子是 ,而非 。先驗步數有效但偏保守;後驗上界 更貼近實際進展。
局部收斂是另一種結論
設 在不動點 附近連續可微。若 ,連續性保證存在一個充分小的、以 為中心的閉區間,使其上 。中值定理又給出 ,因此該區間映回自身。從這個充分小的區間出發便會收斂。這一結論沒有給出區間半徑,也不保證任意初值都成功。
反例模式
映回自身與局部導數各自都不夠
在 上, 把區間映回自身,但序列 並不收斂。此時 ,缺少嚴格壓縮。反過來, 有不動點 ,且 ;但從 出發得到 ,反而遠離零。局部條件不能保護遠處的初值。
常見錯誤
(步長小不等於誤差小)
僅憑步長小不能保證誤差小: 的不動點是零,從 出發,步長只有 ,但 的誤差為 。它的壓縮因子 ,定理恰好要求把該步長乘以 。
如何選擇鬆弛參數
常用的一族迭代是 ,其中 是非零常數。在其有定義的區間內,不動點恰好是 的零點。若區間 上已知 ,選取
便有 :線性表達式 的絕對值在 或 處達到最大。這只證明壓縮;仍須另外驗證 。如果已知零點 存在,且 關於 對稱,導數界可以保證映回自身;實際中區間可能不對稱,根的位置也可能未知。參數選得不好,即使方程很簡單也可能發散:對 取 ,得到 。
例題 2.3.4
(以鬆弛法解 )
在 上取 。這裏 落在 ,故 、、、。映射 滿足 。映回自身須另外檢查: 是凹函數,最大值為 ,而 ,所以 。從 出發,
最近一步為 ,所以 。實際誤差約為 ,落在保證範圍之內。
練習與解答
快速檢查
(在 上取 ,。驗證定理條件,求不動點,並用最近一步估計 的誤差。)
映射遞增,所以值域由端點決定。
解答 · 答案
值域為 ,且 。不動點 。算得 、,故後驗上界為 ;本例中它恰等於真實誤差。
快速檢查
(對 ,考慮 。解釋為何其不動點不全是 的零點。)
直接解 。
解答 · 答案
不動點滿足 ,所以 是多餘的不動點,而 。所求零點 仍是不動點。乘上的因子在 處為零,因而破壞了等價性。
快速檢查
(已驗證某壓縮映射的 ,且 。求一個足夠大的整數 ,使先驗上界保證 。)
使用 。
解答 · 答案
上界為 。當 時為 ,仍過大;當 時為 。因此 足夠。這裏從 開始計迭代次數;這是充分保證,並不一定是實際誤差首次達到要求的步數。
上述公式針對精確迭代。函數求值和算術中的捨入可能破壞不等式;嚴格的機器計算保證須另行控制這些誤差。因此,因停滯或迭代次數上限而退出,應與證明達到誤差容限的情況分開報告。