計(jì)算方法迭代法

1、3.1 二分法二分法3.2 迭代法原理迭代法原理3.3 newton迭代法和迭代加速迭代法和迭代加速3.4 解線性方程組的迭代法解線性方程組的迭代法 根的估計(jì)根的估計(jì) 二分法二分法引理引理3.1（連續(xù)函數(shù)的介值定理連續(xù)函數(shù)的介值定理） 設(shè)設(shè)f(x)在在a,b上連續(xù)，且上連續(xù)，且f(a)f(b)0，則存在，則存在x* (a,b)使使f(x*)=0。例例3.1 證明證明x3 3x 1 = 0 有且僅有有且僅有3個(gè)實(shí)根，并個(gè)實(shí)根，并確定根的大致位置使誤差不超過(guò)確定根的大致位置使誤差不超過(guò) =0.5。解解: : 單調(diào)性分析和解的位置單調(diào)性分析和解的位置選步長(zhǎng)選步長(zhǎng)h=2 , 掃描節(jié)點(diǎn)函數(shù)值掃描節(jié)點(diǎn)函數(shù)

2、值異號(hào)區(qū)間內(nèi)有根異號(hào)區(qū)間內(nèi)有根條件條件: 設(shè)設(shè)f(x)在在a,b上連續(xù)，上連續(xù)，f(x)=0在在a,b上存在唯一解，且上存在唯一解，且f(a)f(b)0。記。記00000,2abaa bb xstep 1: if 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

3、ak=xk-1, bk=bk-1; let xk=(ak+bk)/2. 收斂性及截?cái)嗾`差分析收斂性及截?cái)嗾`差分析:0)(21)(21)(21)(211001112ababababxxkkkkkkk優(yōu)點(diǎn)優(yōu)點(diǎn)算法簡(jiǎn)單算法簡(jiǎn)單收斂有保證收斂有保證只要只要f(x)連續(xù)連續(xù)缺點(diǎn)缺點(diǎn)對(duì)區(qū)間兩端點(diǎn)選取條件苛刻對(duì)區(qū)間兩端點(diǎn)選取條件苛刻收斂速度慢收斂速度慢迭代法的思想迭代法的思想 不動(dòng)點(diǎn)原理不動(dòng)點(diǎn)原理 局部收斂性局部收斂性收斂性的階收斂性的階 條件條件: f(x)=0 在在x0附近有且僅有一個(gè)根附近有且僅有一個(gè)根 設(shè)計(jì)同解變形設(shè)計(jì)同解變形 x=g(x) 迭代式迭代式 xk=g(xk-1), k=1,2, 如果收

4、斂如果收斂 xk x*, 則則x*是是f(x)=0 的的根根定理定理3.1 (不動(dòng)點(diǎn)原理不動(dòng)點(diǎn)原理) 設(shè)映射設(shè)映射g(x)在在a,b上有連續(xù)的上有連續(xù)的一階導(dǎo)數(shù)且滿足一階導(dǎo)數(shù)且滿足1o 封閉性封閉性： x a,b, g(x) a,b ,2o 壓縮性壓縮性： l (0,1)使對(duì)使對(duì) x a,b, |g(x)| l,則在則在a,b上存在唯一的不動(dòng)點(diǎn)上存在唯一的不動(dòng)點(diǎn)x*，且對(duì)，且對(duì) x0 a,b, xk=g(xk-1)收斂于收斂于x* 。進(jìn)一步，有誤差估計(jì)式。進(jìn)一步，有誤差估計(jì)式 1*1kkkxxllxx011xxllk后驗(yàn)估計(jì)先驗(yàn)估計(jì)算法設(shè)計(jì)中迭代結(jié)束條件算法設(shè)計(jì)中迭代結(jié)束條件: 近似使用近似使

5、用|xk-xk-1| 證明步驟證明步驟解的存在性解的存在性; 解的唯一性解的唯一性;解的收斂性解的收斂性; 誤差估計(jì)式。誤差估計(jì)式。例例3.3 3131(1)1 (2)1 kkkkxxxx不收斂收斂131)(lxg2 , 1 2 , 1 :g定理定理3.2 （局部收斂性局部收斂性）設(shè)）設(shè)g(x)連續(xù)連續(xù), , 則存在充分靠近則存在充分靠近x*的初值，使迭代收斂于的初值，使迭代收斂于x*。證明：利用定理證明：利用定理3.1,3.1,取取l= = 具有局部收斂性的迭代計(jì)算上不一定收斂，具有局部收斂性的迭代計(jì)算上不一定收斂，它是否收斂還要看初值是否取的恰當(dāng)；它是否收斂還要看初值是否取的恰當(dāng)；而不具有

6、局部收斂性的迭代對(duì)任何初值都不而不具有局部收斂性的迭代對(duì)任何初值都不可能收斂?？赡苁諗?。()1g x應(yīng)用中應(yīng)用中: 近似使用近似使用|g(x0)|1判斷判斷()1)/21g x定義定義3.1 當(dāng)當(dāng)xkx*，記，記ek= x* - xk ，若存在，若存在實(shí)數(shù)實(shí)數(shù)p，使，使ek+1/epk c 0，則稱則稱xk有有p p階收斂速度階收斂速度。線性收斂線性收斂 p=1平方收斂平方收斂 p=2 定理定理3.3 設(shè)設(shè)xk=g(xk-1) x*，則，則(1) 當(dāng)當(dāng)g(x*) 0時(shí)，時(shí)，xk線性收斂；線性收斂；(2) 當(dāng)當(dāng)g(x*)=0,而而g(x*) 0時(shí)，時(shí)，xk平方收斂。平方收斂。 牛頓牛頓(newt

7、on)迭代法迭代法 “迭代加速迭代加速”技術(shù)技術(shù)原理原理(1次近似次近似, 直線代替曲線直線代替曲線)牛頓格式牛頓格式111()()()()kkkf xf xfxxx111()()kkkf xxxfx111()()kkkkf xxxfx切線代替曲線切線代替曲線單根：平方收斂單根：平方收斂m重重根：線性收斂根：線性收斂例例3.5 （p56) newton迭代法，計(jì)算迭代法，計(jì)算3次達(dá)到次達(dá)到4位有效數(shù)字位有效數(shù)字 計(jì)算計(jì)算4次達(dá)到次達(dá)到4位有效數(shù)字位有效數(shù)字越是精度要求高越是精度要求高, newton迭代法優(yōu)勢(shì)越明顯迭代法優(yōu)勢(shì)越明顯0)()()()(2 xfxfxfxg)6(11)()()(li

8、m)(2*習(xí)題mxfxfxfxgxx 311 kkxx加快迭代過(guò)程的收斂速度加快迭代過(guò)程的收斂速度將發(fā)散的迭代格式加工成收斂的將發(fā)散的迭代格式加工成收斂的若若g(x)在在x*附近大約為附近大約為d, 改進(jìn)改進(jìn)xk = g(xk-1) 為為 例例3.6 （p57)111 ()1kkkxg xdxd1 迭代思想迭代思想2 jacobi迭代和迭代和gauss-seidel迭代迭代3 迭代的收斂性迭代的收斂性4 迭代加速迭代加速逐次超松弛（逐次超松弛（sor）法）法解大型稀疏型方程組比直接法存儲(chǔ)量小解大型稀疏型方程組比直接法存儲(chǔ)量小 條件條件: ax=b 解存在唯一解存在唯一 設(shè)計(jì)同解變形設(shè)計(jì)同解變形

9、 x=gx+f 迭代式迭代式 x(k)=gx (k-1)+f, k=1,2, 取初值取初值x(0) ，如果收斂，如果收斂 x(k) x*, 則則x*是是ax=b的解的解 x(k) x*( )0kkxx 例例3.7解：變形解：變形1231231231027.21028.354.2xxxxxxxxx1232133120.720.10.20.830.10.20.840.20.2xxxxxxxxxjacobi迭代迭代初值取初值取 ，精度要求，精度要求 =10-3。計(jì)算得計(jì)算得 |x(6) x(5)| 10-3. )1(2)1(1)(3)1(3)1(1)(2)1(3)1(2)(12 . 02 . 084

10、. 02 . 01 . 083. 02 . 01 . 072. 0kkkkkkkkkxxxxxxxxx(0)(0)(0)1231xxxgauss-seidel迭代迭代初值取初值取 ，精度要求，精度要求 =10-3。計(jì)算得計(jì)算得 |x(5) x(4)| 10-3. ( )(1)(1)123( )( )(1)213( )( )( )3120.720.10.20.830.10.20.840.20.2kkkkkkkkkxxxxxxxxx(0)(0)(0)1231xxxjacobi迭代迭代gauss-seidel迭代迭代迭代結(jié)束條件一般用迭代結(jié)束條件一般用 |x(k) x(k-1)| 問(wèn)題問(wèn)題(1)(1

11、)收斂性條件收斂性條件? (2) ? (2) |x(k) x(k-1)| 作為結(jié)束作為結(jié)束條件是否可靠條件是否可靠? ?( )(1)1,1,1,nkkiiijjjj iiixba xina1( )( )(1)111,1,inkkkiiijjijjjj iiixba xa xina 和分解：和分解： a=l(下三角下三角)+d (對(duì)角對(duì)角) +u (上三角上三角)迭代迭代 x(k)= gx (k-1) + f, k=1,2,jacobi迭代迭代 g = -d-1(l+u) = i-d-1a f = d-1 bgauss-seidel迭代迭代 g = - (l+d)-1 u f = (l+d)-1

12、 b定理定理3.4 設(shè)設(shè)g的某種范數(shù)的某種范數(shù)|g|1，則，則x=gx+f存存在唯一解，且對(duì)任意初值，迭代序列在唯一解，且對(duì)任意初值，迭代序列x(k)= gx (k-1) + f 收斂于收斂于x*，進(jìn)一步有誤差估計(jì)式，進(jìn)一步有誤差估計(jì)式證明思路證明思路：(1)解的存在唯一性解的存在唯一性; (2)解的收斂解的收斂性性;(3)誤差估計(jì)式誤差估計(jì)式( (習(xí)題習(xí)題) )。 ( )( )(1)(1)(0)11kkkkggxxxxxxgg推論推論 若若a按行嚴(yán)格對(duì)角占優(yōu)（按行嚴(yán)格對(duì)角占優(yōu)（ ），），則解則解ax=b的的jacobi迭代和迭代和gauss-seidel迭代迭代均收斂。均收斂。證明思路：用定

13、理證明思路：用定理3.4. a嚴(yán)格對(duì)角占優(yōu)，嚴(yán)格對(duì)角占優(yōu)， 則則無(wú)窮大范數(shù)無(wú)窮大范數(shù) |g|1jacobi迭代迭代(直接證直接證|g| 1)gauss-seidel迭代迭代, 令令y=gx，則，則y= -d-1(ly+ux)先證存在某先證存在某x, |x| =1, 使使|g| =|y| 再證當(dāng)再證當(dāng)|x| =1, 有有|y| 11,niiijjj iaa記迭代矩陣記迭代矩陣存在存在m,令令那么那么 且且 nnijgg)(njmjnjijniggg111maxnxxx10101mjmjjggxxgxgxgggnjjijninjjmjnjmjmax11111x記記 ，其中迭代矩陣，其中迭代矩陣那么

14、那么存在存在k使得使得所以所以u(píng)dlg1)(xgy)(1uxlydy nkjkjkjkjkknkjjkjkjjkjkkayaaxayaa1111111)(11111 kjkjkknkjkjaaay1 yxgg|kyy 譜半徑譜半徑 (g)：g的特征值模的最大值的特征值模的最大值定理定理3. 5 迭代迭代x(k)= gx (k-1) + f對(duì)任意初值收斂對(duì)任意初值收斂 (g)1. （證明較深，略）（證明較深，略）方法一方法一(推論推論): 從從a判斷判斷, a嚴(yán)格對(duì)角占優(yōu)，則嚴(yán)格對(duì)角占優(yōu)，則jacobi迭代和迭代和gauss-seidel迭代收斂迭代收斂, 充分條充分條件件, 最方便最方便方法二方法二(定理定理3.4): 從從g判斷判斷, 有一種范數(shù)有一種范數(shù)|g|1, 充分條件充分條件方法三方法三(定理定理3.5): 從從g判斷判斷,譜半徑譜半徑 (g) 1, 充充要條件要條件, 最寬最寬p63, 例例3.