計算方法迭代法

1、第三章迭代法,3.1 二分法 3.2 迭代法原理 3.3 Newton迭代法和迭代加速 3.4 解線性方程組的迭代法,3.1 二分法,根的估計 二分法,根的估計,引理3.1（連續(xù)函數(shù)的介值定理） 設(shè)f(x)在a,b上連續(xù)，且f(a)f(b)0，則存在x*(a,b)使f(x*)=0。 例3.1 證明x33x1 = 0 有且僅有3個實根，并確定根的大致位置使誤差不超過 =0.5。 解: 單調(diào)性分析和解的位置 選步長h=2, 掃描節(jié)點函數(shù)值 異號區(qū)間內(nèi)有根,f(x)= x33x1,二分法,條件: 設(shè)f(x)在a,b上連續(xù)，f(x)=0在a,b上存在唯一解，且f(a)f(b)0。記,Step 1: I

2、f f(a0)f(x0)0, then x*(a0,x0) let a1=a0, b1=x0; Else x*(x0,b0) let a1=x0, b1=b0; Let x1=(a1+b1)/2.,Step k: If f(ak-1)f(xk-1)0, then x*(ak-1,xk-1) let ak=ak-1, bk=xk-1; Else x*(xk-1,bk-1) let ak=xk-1, bk=bk-1; Let xk=(ak+bk)/2.,收斂性及截斷誤差分析:,例3.2 x33x1 = 0, 1,2, 精度0.5e-1,二分法,優(yōu)點 算法簡單 收斂有保證 只要f(x)連續(xù) 缺點 對

3、區(qū)間兩端點選取條件苛刻 收斂速度慢,3.2 迭代法原理,迭代法的思想 不動點原理 局部收斂性 收斂性的階,迭代法的思想,條件: f(x)=0 在x0附近有且僅有一個根 設(shè)計同解變形 x=g(x) 迭代式 xk=g(xk-1), k=1,2, 如果收斂 xk x*, 則x*是f(x)=0 的根,不動點原理(迭代過程收斂),定理3.1 (不動點原理) 設(shè)映射g(x)在a,b上有連續(xù)的一階導(dǎo)數(shù)且滿足 1o 封閉性：x a,b, g(x) a,b , 2o 壓縮性： L (0,1)使對x a,b, |g(x)|L, 則在a,b上存在唯一的不動點x*，且對x0 a,b, xk=g(xk-1)收斂于x*

4、。進一步，有誤差估計式,算法設(shè)計中迭代結(jié)束條件: 近似使用|xk-xk-1|,不動點原理,證明步驟 解的存在性; 解的唯一性; 解的收斂性; 誤差估計式。 例3.3,局部收斂性(格式收斂),定理3.2 （局部收斂性）設(shè)g(x)連續(xù), 則存在充分靠近x*的初值，使迭代收斂于x*。 證明：利用定理3.1,取L= 具有局部收斂性的迭代計算上不一定收斂，它是否收斂還要看初值是否取的恰當(dāng)； 而不具有局部收斂性的迭代對任何初值都不可能收斂。,應(yīng)用中: 近似使用|g(x0)|1判斷,收斂性的階(局部收斂速度),定義3.1 當(dāng)xkx*，記ek= x* - xk ，若存在實數(shù)p，使 ek+1/epk c0， 則

5、稱xk有p階收斂速度。 線性收斂 p=1 平方收斂 p=2,定理3.3 設(shè)xk=g(xk-1) x*，則 (1) 當(dāng)g(x*)0時，xk線性收斂； (2) 當(dāng)g(x*)=0,而g(x*) 0時，xk平方收斂。,3.3 Newton迭代法和迭代加速,牛頓(Newton)迭代法 “迭代加速”技術(shù),牛頓(Newton)迭代法,原理(1次近似, 直線代替曲線) 牛頓格式,Newton法幾何意義：切線法,切線代替曲線,Newton法局部收斂性,單根：平方收斂 m重根：線性收斂 例3.5 （P56) Newton迭代法，計算3次達(dá)到4位有效數(shù)字 計算4次達(dá)到4位有效數(shù)字 越是精度要求高, Newton迭代

6、法優(yōu)勢越明顯,“迭代加速”技術(shù),加快迭代過程的收斂速度 將發(fā)散的迭代格式加工成收斂的 若g(x)在x*附近大約為D, 改進xk = g(xk-1) 為 例3.6 （P57),4 解線性方程組的迭代法,1 迭代思想 2 Jacobi迭代和Gauss-Seidel迭代 3 迭代的收斂性 4 迭代加速逐次超松弛（SOR）法,1 迭代思想,解大型稀疏型方程組比直接法存儲量小 條件: Ax=b 解存在唯一 設(shè)計同解變形 x=Gx+f 迭代式 x(k)=Gx (k-1)+f, k=1,2, 取初值x(0) ，如果收斂 x(k) x*, 則x*是Ax=b的解 x(k) x*,2 Jacobi迭代和Gauss

7、-Seidel迭代,例3.7 解：變形,Jacobi迭代,Jacobi迭代 初值取 ，精度要求 =10-3。 計算得 |x(6) x(5)|10-3.,Gauss-Seidel迭代,Gauss-Seidel迭代 初值取 ，精度要求 =10-3。 計算得 |x(5) x(4)|10-3.,編程計算公式,Jacobi迭代 Gauss-Seidel迭代 迭代結(jié)束條件一般用 |x(k) x(k-1)| 問題(1)收斂性條件? (2) |x(k) x(k-1)| 作為結(jié)束條件是否可靠?,計算公式矩陣形式,和分解： A=L(下三角)+D (對角) +U (上三角) 迭代 x(k)= Gx (k-1) +

8、f, k=1,2, Jacobi迭代 G = -D-1(L+U) = I-D-1A f = D-1 b Gauss-Seidel迭代 G = - (L+D)-1 U f = (L+D)-1 b,3 迭代的收斂性,定理3.4 設(shè)G的某種范數(shù)|G|1，則x=Gx+f存在唯一解，且對任意初值，迭代序列 x(k)= Gx (k-1) + f 收斂于x*，進一步有誤差估計式 證明思路：(1)解的存在唯一性; (2)解的收斂性;(3)誤差估計式(習(xí)題)。,直接從Ax=b判斷,推論 若A按行嚴(yán)格對角占優(yōu)（ ），則解Ax=b的Jacobi迭代和Gauss-Seidel迭代均收斂。 證明思路：用定理3.4. A

9、嚴(yán)格對角占優(yōu)， 則無窮大范數(shù) |G|1 Jacobi迭代(直接證|G|1) Gauss-Seidel迭代, 令y=Gx，則y= -D-1(Ly+Ux) 先證存在某x, |x| =1, 使|G| =|y| 再證當(dāng)|x| =1, 有|y| 1,Gauss-Seidel迭代收斂性證明,記迭代矩陣 存在m, 令 那么 且,Gauss-Seidel迭代收斂性證明,記 ，其中迭代矩陣 那么 存在k使得 所以,充分必要條件,譜半徑(G)：G的特征值模的最大值 定理3. 5 迭代x(k)= Gx (k-1) + f對任意初值收斂(G)1. （證明較深，略）,三種方法比較,方法一(推論): 從A判斷, A嚴(yán)格對角占優(yōu)，則Jacobi迭代和Gauss-Seidel迭代收斂, 充分條件, 最方便 方法二(定理3.4): 從G判斷, 有一種范數(shù)|G|1, 充分條件 方法三(定理3.5): 從G判斷,譜半徑(G) 1, 充要條件, 最寬 P63, 例3.8（特征值的性質(zhì)：特征值