第三章迭代法

第三章迭代法第1頁，共36頁，2023年，2月20日，星期三§3.1二分法根的估計二分法第2頁，共36頁，2023年，2月20日，星期三根的估計引理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個實(shí)根，并確定根的大致位置使誤差不超過=0.5。解:單調(diào)性分析和解的位置選步長h=2,掃描節(jié)點(diǎn)函數(shù)值異號區(qū)間內(nèi)有根第3頁，共36頁，2023年，2月20日，星期三f(x)=x33x1第4頁，共36頁，2023年，2月20日，星期三二分法(更快的掃描法)條件:設(shè)f(x)在[a,b]上連續(xù)，f(x)=0在[a,b]上存在唯一解，且f(a)f(b)<0。記Step1:Iff(a0)f(x0)<0,thenx*(a0,x0)leta1=a0,b1=x0;Elsex*(x0,b0)leta1=x0,b1=b0;Letx1=(a1+b1)/2.

Stepk:Iff(ak-1)f(xk-1)<0,thenx*(ak-1,xk-1)letak=ak-1,bk=xk-1;Elsex*(xk-1,bk-1)letak=xk-1,bk=bk-1;Letxk=(ak+bk)/2.

收斂性及截斷誤差分析:第5頁，共36頁，2023年，2月20日，星期三例3.2x33x1=0,[1,2],精度0.5e-1第6頁，共36頁，2023年，2月20日，星期三二分法優(yōu)點(diǎn)算法簡單收斂有保證只要f(x)連續(xù)缺點(diǎn)對區(qū)間兩端點(diǎn)選取條件苛刻收斂速度慢難以推廣至多維情形第7頁，共36頁，2023年，2月20日，星期三§3.2迭代法原理迭代法的思想

不動點(diǎn)原理

局部收斂性收斂性的階

第8頁，共36頁，2023年，2月20日，星期三迭代法的思想

條件:f(x)=0在x0附近有且僅有一個根設(shè)計同解變形x=g(x)迭代式xk=g(xk-1),k=1,2,…如果收斂xk

x*,則x*是f(x)=0的根第9頁，共36頁，2023年，2月20日，星期三不動點(diǎn)原理(迭代過程收斂)定理3.1(不動點(diǎn)原理)設(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]上存在唯一的不動點(diǎn)x*，且對x0[a,b],xk=g(xk-1)收斂于x*。進(jìn)一步，有誤差估計式

后驗(yàn)估計先驗(yàn)估計算法設(shè)計中迭代結(jié)束條件:近似使用|xk-xk-1|<第10頁，共36頁，2023年，2月20日，星期三不動點(diǎn)原理例3.3x3x1=0，[1,2],x0=1.5,第11頁，共36頁，2023年，2月20日，星期三不動點(diǎn)原理證明步驟解的存在性;解的唯一性;解的收斂性;誤差估計式。第12頁，共36頁，2023年，2月20日，星期三局部收斂性(格式收斂)定理3.2（局部收斂性）設(shè)g’(x)連續(xù),則存在充分靠近x*的初值，使迭代收斂于x*。證明：利用定理3.1,取L=

具有局部收斂性的迭代計算上不一定收斂，它是否收斂還要看初值是否取的恰當(dāng)；而不具有局部收斂性的迭代對任何初值都不可能收斂。應(yīng)用中:近似使用|g'(x0)|<1判斷第13頁，共36頁，2023年，2月20日，星期三收斂性的階(局部收斂速度)定義3.1當(dāng)xkx*，記ek=x*-xk，若存在實(shí)數(shù)p，使ek+1/epkc0，則稱{xk}有p階收斂速度。線性收斂p=1平方收斂p=2

第14頁，共36頁，2023年，2月20日，星期三收斂性的階(局部收斂速度)定理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}平方收斂。

證明(2)第15頁，共36頁，2023年，2月20日，星期三3.3Newton迭代法和迭代加速

牛頓(Newton)迭代法

“迭代－加速”技術(shù)（略）第16頁，共36頁，2023年，2月20日，星期三牛頓(Newton)迭代法原理(1次近似,直線代替曲線)牛頓格式第17頁，共36頁，2023年，2月20日，星期三Newton法幾何意義：切線法切線代替曲線第18頁，共36頁，2023年，2月20日，星期三Newton法局部收斂性單根：平方收斂m重根：線性收斂,f(x)=(x-x*)mq(x),q(x*)0,例3.5（P56)Newton迭代法，計算3次達(dá)到4位有效數(shù)字計算4次達(dá)到4位有效數(shù)字越是精度要求高,Newton迭代法優(yōu)勢越明顯第19頁，共36頁，2023年，2月20日，星期三“迭代－加速”技術(shù)(略)加快迭代過程的收斂速度將發(fā)散的迭代格式加工成收斂的若g’(x)在x*附近大約為D,改進(jìn)xk

=g(xk-1)為例3.6（P57)第20頁，共36頁，2023年，2月20日，星期三§4解線性方程組的迭代法

1迭代思想2Jacobi迭代和Gauss-Seidel迭代3迭代的收斂性4迭代加速——逐次超松弛（SOR）法第21頁，共36頁，2023年，2月20日，星期三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*第22頁，共36頁，2023年，2月20日，星期三2Jacobi迭代和Gauss-Seidel迭代例3.7解：變形第23頁，共36頁，2023年，2月20日，星期三Jacobi迭代Jacobi迭代初值取，精度要求=10-3。計算得||x(6)x(5)||10-3.第24頁，共36頁，2023年，2月20日，星期三Gauss-Seidel迭代Gauss-Seidel迭代初值取，精度要求=10-3。計算得||x(5)x(4)||10-3.第25頁，共36頁，2023年，2月20日，星期三編程計算公式Jacobi迭代Gauss-Seidel迭代迭代結(jié)束條件一般用||x(k)x(k-1)||

問題(1)收斂性條件?(2)||x(k)x(k-1)||作為結(jié)束條件是否可靠?第26頁，共36頁，2023年，2月20日，星期三計算公式矩陣形式和分解：

A=L(下三角)+D(對角)+U(上三角)迭代

x(k)=Gx

(k-1)+f,k=1,2,…Jacobi迭代

G=-D-1(L+U)=I-D-1Af=D-1bGauss-Seidel迭代

G=-(L+D)-1Uf=(L+D)-1b第27頁，共36頁，2023年，2月20日，星期三3迭代的收斂性定理3.4設(shè)G的某種范數(shù)||G||<1，則x=Gx+f存在唯一解，且對任意初值，迭代序列x(k)=Gx

(k-1)+f收斂于x*，進(jìn)一步有誤差估計式證明思路：(1)解的存在唯一性;(2)解的收斂性;(3)誤差估計式(習(xí)題)。

第28頁，共36頁，2023年，2月20日，星期三直接從Ax=b判斷推論若A按行嚴(yán)格對角占優(yōu)（），則解Ax=b的Jacobi迭代和Gauss-Seidel迭代均收斂。證明思路：用定理3.4.A嚴(yán)格對角占優(yōu)，則無窮大范數(shù)||G||<1Jacobi迭代G=-D-1(L+U)(直接證||G||<1)Gauss-Seidel迭代,令，先證存在某x,||x||=1,使||?||=||y||

再證當(dāng)||x||=1,有||y||<1第29頁，共36頁，2023年，2月20日，星期三Jacobi迭代(直接證||G||<1)G=-D-1(L+U)第30頁，共36頁，2023年，2月20日，星期三Gauss-Seidel迭代收斂性證明記迭代矩陣存在m,令那么且第31頁，共36頁，2023年，2月20日，星期三Gauss-Seidel迭代收斂性證明記，其中迭代矩陣那么存在k使得所以第32頁，共36頁，2023年，2月20日，星期三充分必要條件譜半徑(G)：G的特征值模的最大值定理3.5迭代x(k)=Gx

(k-1)+f對任意初值收斂(G)<1.（證明較深，略）第33頁，共36頁，2023年，2月20日，星期三三種方法比較方法一(推論):從A判斷,A嚴(yán)格對角占優(yōu)，則Jacobi迭代和Gauss-Seidel迭代收斂,充分條件,最方便方法二(定理3.4):從G判斷,有一種范數(shù)||G||<1,充分條件方法三(定理3.5):從G判斷,譜半徑(G)<1,充要條件,最寬P63,例3.8（特征值的性質(zhì)：特征值之和等于