數(shù)值分析對分法和一般迭代法

數(shù)值分析對分法和一般迭代法第1頁，課件共41頁，創(chuàng)作于2023年2月非線性方程求根1．根的存在性。方程有沒有根？如果有根，有幾個(gè)根？定理1：設(shè)函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，如果f(a)

f(b)<0，

則方程f(x)=0在[a,b]內(nèi)至少有一實(shí)根x*。

2．這些根大致在哪里？如何把根隔離開來？3．根的精確化第2頁，課件共41頁，創(chuàng)作于2023年2月abx*f(x)1．畫出f(x)的略圖，從而看出曲線與x軸交點(diǎn)的位置。2．從左端點(diǎn)x=a出發(fā)，按某個(gè)預(yù)先選定的步長h一步一步地向右跨，每跨一步都檢驗(yàn)每步起點(diǎn)x0和終點(diǎn)x0+h的函數(shù)值，若那么所求的根x*必在x0與x0+h之間，這里可取x0或x0+h作為根的初始近似。第3頁，課件共41頁，創(chuàng)作于2023年2月

開始讀入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印結(jié)束否是繼續(xù)掃描

第4頁，課件共41頁，創(chuàng)作于2023年2月例1：考察方程的含根區(qū)間x00.51.01.5f(x)符號－－－＋可見，含根區(qū)間為

[1,1.5]第5頁，課件共41頁，創(chuàng)作于2023年2月§4.1對分區(qū)間法(BisectionMethod)原理：若f(x)

C[a,b]，且f(a)·f(b)<0，則f(x)

在(a,b)上必有一根。第6頁，課件共41頁，創(chuàng)作于2023年2月abx1x2a1b2x*b1a2或不能保證

x

的精度2xx*第7頁，課件共41頁，創(chuàng)作于2023年2月

執(zhí)行步驟1．計(jì)算f(x)在有解區(qū)間[a,b]端點(diǎn)處的值，f(a)，f(b)。2．計(jì)算f(x)在區(qū)間中點(diǎn)處的值f(x1)。3．判斷若f(x1)=0，則x1即是根，否則檢驗(yàn)：（1）若f(x1)與f(a)異號，則知解位于區(qū)間[a,x1]，

b1=x1,a1=a;（2）若f(x1)與f(a)同號，則知解位于區(qū)間[x1,b]，

a1=x1,b1=b。反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：

(a,b),(a1,b1),…,(ak,bk),…第8頁，課件共41頁，創(chuàng)作于2023年2月4、當(dāng)時(shí)，則即為根的近似。①簡單;②對f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及偶重根②收斂慢第9頁，課件共41頁，創(chuàng)作于2023年2月誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對于給定的精度,可估計(jì)二分法所需的步數(shù)k：第10頁，課件共41頁，創(chuàng)作于2023年2月定義f(x)f(a)

f(b)>0f(a)

f(b)=0f(a)=0打印b,k打印a,k結(jié)束是是是否否否m=(a+b)/2|a-b|<f(a)f(b)>0打印m,ka=mb=m結(jié)束k=k+1是是否否輸入k=0第11頁，課件共41頁，創(chuàng)作于2023年2月

例2用二分法求

在(1,2)內(nèi)的根，要求絕對誤差不超過

解：

f(1)=-5<0有根區(qū)間

中點(diǎn)

f(2)=14>0-(1,2)+

f(1.25)<0(1.25,1.5)f(1.375)>0(1.25,1.375)f(1.313)<0(1.313,1.375)f(1.344)<0(1.344,1.375)f(1.360)<0(1.360,1.375)f(1.368)>0(1.360,1.368)

f(1.5)>0(1,1.5)第12頁，課件共41頁，創(chuàng)作于2023年2月12

例3，求方程f(x)=x3–e-x=0的一個(gè)實(shí)根。因?yàn)閒(0)<0,f(1)>0。故f(x)在(0,1)內(nèi)有根用二分法解之，(a,b）=（0,1)’計(jì)算結(jié)果如表：k a bk xk f(xk)符號 0 0 1 0.5000 － 1 0.5000 － 0.7500－ 2 0.7500 － 0.8750 ＋ 3 － 0.8750 0.8125 ＋ 4 － 0.8125 0.7812 ＋ 5 － 0.7812 0.7656 － 6 0.7656 － 0.7734 ＋ 7 － 0.7734 0.7695 － 80.7695－ 0.7714 － 9 0.7714 － 0.7724 － 10 0.7724 － 0.7729 ＋

取x10=0.7729，誤差為|x*-x10|<=1/211。第13頁，課件共41頁，創(chuàng)作于2023年2月Remark1：求奇數(shù)個(gè)根

Findsolutionstotheequationontheintervals[0,4]，Usethebisectionmethodtocomputeasolutionwithanaccuracyof10－7.Determinethenumberofiterationstouse..第14頁，課件共41頁，創(chuàng)作于2023年2月[0,1],[1.5,2.5]and[3,4]，利用前面的公式可計(jì)算迭代次數(shù)為k=23.第15頁，課件共41頁，創(chuàng)作于2023年2月Remark2:要區(qū)別根與奇異點(diǎn)Considerf(x)=tan(x)ontheinterval(0,3).Usethe20iterationsofthebisectionmethodandseewhathappens.Explaintheresultsthatyouobtained.（如下圖）第16頁，課件共41頁，創(chuàng)作于2023年2月Remark3:二分法不能用來求重根第17頁，課件共41頁，創(chuàng)作于2023年2月f(x)=0x=g(x)等價(jià)變換f(x)的根g(x)的不動點(diǎn)§4.2單個(gè)方程的迭代法f(x)=0化為等價(jià)方程x=g(x)的方式是不唯一的,有的收斂,有的發(fā)散

Forexample：2x3-x-1=0

xk+1=g(xk)(3)第18頁，課件共41頁，創(chuàng)作于2023年2月(1)

如果將原方程化為等價(jià)方程由此可見，這種迭代格式是發(fā)散的

取初值第19頁，課件共41頁，創(chuàng)作于2023年2月(2)如果將原方程化為等價(jià)方程仍取初值依此類推,得

x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已經(jīng)收斂,故原方程的解為x=1.0000同樣的方程?不同的迭代格式有不同的結(jié)果什么形式的迭代法能夠收斂呢?第20頁，課件共41頁，創(chuàng)作于2023年2月收斂性分析定義2

若存在常數(shù)(0≤<1),使得對一切x1,x2∈［a,b］,成立不等式|g(x1)-g(x2)|≤|x1-x2|，(5)則稱g(x)是［a,b］上的一個(gè)壓縮映射，稱為壓縮系數(shù)第21頁，課件共41頁，創(chuàng)作于2023年2月

考慮方程x=g(x),g(x)C[a,b],若(I)當(dāng)x[a,b]時(shí)，g(x)[a,b]；(II)在［a,b］上成立不等式：|g(x1)-g(x2)|≤|x1-x2|

。則（1）g在［a,b］上存在惟一不動點(diǎn)x*（2）任取x0[a,b]，由xk+1=g(xk)

得到的序列{xk}（［a,b】）收斂于x*

。（3）k次迭代所得到的近似不動點(diǎn)xk與精確不動點(diǎn)x*有誤差估計(jì)式：定理4.2.1第22頁，課件共41頁，創(chuàng)作于2023年2月§3Fixed-PointIteration證明：①g(x)在[a,b]上存在不動點(diǎn)？②不動點(diǎn)唯一？③當(dāng)k

時(shí)，

xk收斂到x*？|x*-x′|=|g(x*)-g(x′)|≤|x*-x′|.因0≤<1，故必有x′=x*若有x′∈［a,b］,滿足g(x′)=x′，則|xk-x*|=|g(xk-1)-g(x*)|≤|xk-1-x*|≤2|xk-2-x*|≤…≤k|x0-x*|0,令G(x)=g(x)-x,x∈［a,b］，由條件①知G(a)=g(a)-a≥0,G(b)=g(b)-b≤0.由條件②知G(x)在［a,b］上連續(xù)，又由介值定理知存在x*∈［a,b］，使G(x*)=0，即x*=g(x*).第23頁，課件共41頁，創(chuàng)作于2023年2月§3Fixed-PointIteration可用來控制收斂精度越小，收斂越快(4)|xk-x*|=|g(xk-1)-g(x*)|≤|xk-1-x*|≤

（|xk-xk-1|+|xk-x*|）,故有|xk-x*|≤/(1-)|xk-xk-1|.這就證明了估計(jì)式(6).(5)|xk-xk-1|

=|g(xk-1)-g(xk-2)|≤|xk-1-xk-2|≤…≤

k-1|x1-x0|聯(lián)系估計(jì)式(6)可得|xk-x*|≤k-1/(1-)|x1-x0|.即估計(jì)式(7)成立第24頁，課件共41頁，創(chuàng)作于2023年2月Remark：定理?xiàng)l件非必要條件，而且定理4.2.1中的壓縮條件不好驗(yàn)證，一般來講，

若知道迭代函數(shù)g(x)∈C1『a,b］,并且滿足|g′(x)|≤<1,對任意的x∈［a,b］,則g（x)是［a,b］上的壓縮映射第25頁，課件共41頁，創(chuàng)作于2023年2月xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1第26頁，課件共41頁，創(chuàng)作于2023年2月改進(jìn)、加速收斂/*acceleratingconvergence*/

待定參數(shù)法：若

|g’(x)|1，則將x=g(x)等價(jià)地改造為求K，使得例：求在(1,2)的實(shí)根。如果用進(jìn)行迭代，則在(1,2)中有現(xiàn)令希望，即在(1,2)上可取任意，例如K=0.5，則對應(yīng)即產(chǎn)生收斂序列。第27頁，課件共41頁，創(chuàng)作于2023年2月例題已知方程2x-7-lgx＝0，求方程的含根區(qū)間，考查用迭代法解此方程的收斂性。第28頁，課件共41頁，創(chuàng)作于2023年2月第29頁，課件共41頁，創(chuàng)作于2023年2月在這里我們考查在區(qū)間[3.5,4]的迭代法的收斂性很容易驗(yàn)證：f(3.5)<0,f(4)>0將方程變形成等價(jià)形式：x＝(lgx+7)/2由定理4.2.1知，迭代格式xk+1＝(lgxk+7)/2在[3.5,4]內(nèi)收斂第30頁，課件共41頁，創(chuàng)作于2023年2月局部收斂性定理定理4.2.2設(shè)x*為g的不動點(diǎn)，g(x)與g′(x)在包含x*的某鄰域U(x*)(即開區(qū)間)內(nèi)連續(xù)，且|g′(x*)|<1,則存在>0，當(dāng)x0∈［x*-

，x*+］時(shí)，迭代法(3)產(chǎn)生的序列{xk}

［x*-

，x*+］且收斂于x*.證明略（作為練習(xí)）Wedon’tknowx*,howdoweestimatetheinequality？

第31頁，課件共41頁，創(chuàng)作于2023年2月舉例用一般迭代法求x3-x-1=0的正實(shí)根x*容易得到：g′(x)在包含x*的某鄰域U(x*)內(nèi)連續(xù)，且|g′(x*)|<1第32頁，課件共41頁，創(chuàng)作于2023年2月例題用一般迭代法求方程x-lnx＝2在區(qū)間（2，）內(nèi)的根，要求|xk-xk-1|/|xk|<=10-8解：令f(x)=x-lnx-2f(2)<0,f(4)>0,故方程在（2,4）內(nèi)至少有一個(gè)根第33頁，課件共41頁，創(chuàng)作于2023年2月將方程化為等價(jià)方程：x＝2＋lnx因此，x0（2，），xk+1＝2＋lnxk產(chǎn)生的序列xk收斂于X*取初值x0＝3.0,計(jì)算結(jié)果如下：第34頁，課件共41頁，創(chuàng)作于2023年2月7314617745293.146188209103.146191628113.146192714123.146193060133.146193169143.146193204kxi03.00000000013.098612289231413378664314570220963.146037143第35頁，課件共41頁，創(chuàng)作于2023年2月另一種迭代格式：

03.0000000001314619344133.146193221第36頁，課件共41頁，創(chuàng)作于2023年2月程序演示由此可見，對同一個(gè)非線性方程的迭代格式，在收斂的情形下，有的收斂快，有的收斂慢。第37頁，課件共41頁，創(chuàng)作于2023年2月

定義1.:設(shè)序列{xk}收斂于x*，若存在p≥1和正數(shù)c，使得成立則稱{xk}為p階收斂的特別,

p=1，要求c<1,稱線性收斂;1<p<2,稱超線性收斂

p=2,稱平方收斂。迭代法的收斂階(收斂速度)第38頁，課件共41頁，創(chuàng)作于2023年2月定理4.2.3設(shè)x*為g的不動點(diǎn)，p≥2為正整數(shù)，g在x*的某鄰域Ｕ(x*)內(nèi)p階連續(xù)可微，且g′(x*)=g″(x*)=…=g(p-1)(x*)=0，而g(p)