遞推需要的不只是候選值
解 可以猜測 的極限,但不能證明迭代收斂,甚至不能保證各項留在定義域中。壓縮條件補上這些步驟,也提供定量誤差界。
定義 5.1.1
(閉區間上的壓縮映射)
設 為非空閉有界區間, 為映射。若存在常數 ,,使
則稱 為 上的壓縮映射。取 ,數列 稱為 的迭代;滿足 的點 稱為不動點。
條件 保證每項有定義;同一個 控制區間內所有點對。
定理 5.1.2
(帶誤差界的壓縮映射定理)
設 為 上以 為常數的壓縮映射。則 在 中恰有一個不動點 ,且從任意 出發,迭代收斂到 。此外,對 ,
而對 ,
為何迭代收斂
證明
(Cauchy 迭代、不動的極限與尾和估計)
令 ,並約定 (包括 )。因 ,每個 都在 內。反覆使用壓縮不等式得 。當 ,三角不等式及等比和給出
右邊趨零,所以迭代是 Cauchy 序列。實數完備性給出極限 , 的閉性保證 。壓縮不等式也給出 的連續性,於是對 取極限,得到 。
若 都是不動點,則 。因 ,只能有 。在尾和估計中令 ,得先驗界。
至於後驗界,固定 ,對從 出發的迭代使用指標為 的先驗界。其第一步是 ,第一個差是 ,所以 。其中的 是已為 證明的常數;若沒有這樣的界,單靠一步差小並不足夠。
證明透視
壓縮證明中各個假設的作用
這個證明有四步,每一步用到不同的假設。第一, 使每個迭代點都留在可以使用 的集合內。第二, 把望遠鏡式的差變成收斂的等比級數,從而使數列為 Cauchy。第三,實數完備性提供極限, 的閉性使極限留在定義域;之後才可用 的連續性(它本身由壓縮不等式推出)確認極限是不動點。第四,唯一性是另一次比較 ,這裏再次用 迫使 。誤差界就是第二步中等比級數的尾和。若去掉 ,第二步與第四步同時失效。
嚴格不等式 不能換成 ,即使不動點是唯一的也一樣。
反例模式
只有唯一不動點不保證收斂
斷言:若 滿足 且有唯一不動點,則迭代收斂到該點。這是錯的。取 。解 得唯一不動點 。但從 出發,迭代為 永遠交替,且對每個 都有 。這裏 ,常數恰為 ,定理不適用。修正方法是要求嚴格的常數 。
例子
例題 5.1.3
(一個顯式的壓縮映射及其誤差界)
在 上取 。對 有 ,所以區間不變。對 ,
因此可取 。由 開始得 、。不動點方程為 ,兩根為 ;只有 在 。存在與收斂已先證明,選根是在確定極限,而非假設它存在。
在 的最新步差界為 。實際誤差 ,遠在界之內。
例題 5.1.4
(選取迭代次數)
對同一映射,,,,所以先驗界為 。要保證誤差小於 ,需要 。由於 ,而 ,能保證成立的最小選擇是 。這個保證不需要事先知道 。
例題 5.1.5
(邊界情形 )
設 上 。因為兩邊都是 ,不等式在 時成立。對任意 ,,其後每項都是 ,所以 。先驗界在 時 ,故 ,與事實完全吻合。 時它寫成 ,這也成立,因為 。
常見錯誤
常見錯誤
(從不變區間以外出發)
對 ,不動點方程有兩個根: 與 。從 內出發時,只有第一個是極限。從 出發,迭代為 ,無界遞增。壓縮估計只在 上證明過,而根 在區間之外。
常見錯誤
(最後一步差小不等於誤差小)
界 含有因子 ,當 接近 時這個因子很大。對 上的 及 ,有 、、。因此 ,因子 恰好取得。當步差小於容許值就停止,只能保證誤差小於容許值的九倍。
練習與解答
快速檢查
(對例子的映射 ,由 精確求 。)
把 作用於 一次。
解答 · 答案
。
快速檢查
(若 、,估計 。)
使用後驗界。
解答 · 答案
因子為 ,所以 。
快速檢查
(若 定義於 ,為何上面的閉區間定理不適用?)
看看迭代點趨向哪裏。
解答 · 答案
定義域不閉。由正初值開始的迭代都趨於 ,而 在定義域之外,所以域內沒有不動點。
快速檢查
(若 ,一步後會怎樣?)
把 代入壓縮不等式。
解答 · 答案
不等式迫使 在非空定義域上為常數。該值屬於 且是不動點,所以從 起各項均等於它。