對(duì)分法和一般迭代法

對(duì)分法和一般迭代法[]第一頁，共三十一頁，編輯于2023年，星期六簡介（Introduction）我們知道在實(shí)際應(yīng)用中有許多非線性方程的例子，例如（1）在光的衍射理論（thetheoryofdiffractionoflight)中,我們需要求x-tanx=0的根（2）在行星軌道（planetaryorbits）的計(jì)算中,對(duì)任意的a和b，我們需要求x-asinx=b的根（3）在數(shù)學(xué)中，需要求n次多項(xiàng)式xn+a1

xn-1+...+an-1x+an

＝0的根求f(x)=0的根第二頁，共三十一頁，編輯于2023年，星期六§3.1對(duì)分區(qū)間法(BisectionMethod)原理：若f(x)

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

在(a,b)上必有一根。第三頁，共三十一頁，編輯于2023年，星期六abx1x2a1b2x*b1a2停機(jī)條件（terminationcondition）：或第四頁，共三十一頁，編輯于2023年，星期六誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對(duì)于給定的精度,可估計(jì)二分法所需的步數(shù)k：第五頁，共三十一頁，編輯于2023年，星期六

例1用二分法求

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

解：

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)第六頁，共三十一頁，編輯于2023年，星期六

例2，求方程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)符號(hào) 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。第七頁，共三十一頁，編輯于2023年，星期六Remark1：求奇數(shù)個(gè)根

Findsolutionstotheequationontheintervals[0,4]，Usethebisectionmethodtocomputeasolutionwithanaccuracyof10－7.Determinethenumberofiterationstouse..第八頁，共三十一頁，編輯于2023年，星期六[0,1],[1.5,2.5]and[3,4]，利用前面的公式可計(jì)算迭代次數(shù)為k=23.第九頁，共三十一頁，編輯于2023年，星期六Remark2:要區(qū)別根與奇異點(diǎn)Considerf(x)=tan(x)ontheinterval(0,3).Usethe20iterationsofthebisectionmethodandseewhathappens.Explaintheresultsthatyouobtained.（如下圖）第十頁，共三十一頁，編輯于2023年，星期六Remark3:二分發(fā)不能用來求重根第十一頁，共三十一頁，編輯于2023年，星期六f(x)=0x=g(x)等價(jià)變換f(x)的根g(x)的不動(dòng)點(diǎn)§3.2單個(gè)方程的迭代法f(x)=0化為等價(jià)方程x=g(x)的方式是不唯一的,有的收斂,有的發(fā)散Forexample：2x3-x-1=0第十二頁，共三十一頁，編輯于2023年，星期六(1)

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

取初值第十三頁，共三十一頁，編輯于2023年，星期六(2)如果將原方程化為等價(jià)方程仍取初值依此類推,得

x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已經(jīng)收斂,故原方程的解為x=1.0000同樣的方程?不同的迭代格式有不同的結(jié)果什么形式的迭代法能夠收斂呢?第十四頁，共三十一頁，編輯于2023年，星期六收斂性分析定義2

若存在常數(shù)(0≤<1),使得對(duì)一切x1,x2∈［a,b］,成立不等式|g(x1)-g(x2)|≤|x1-x2|，(5)則稱g(x)是［a,b］上的一個(gè)壓縮映射，稱為壓縮系數(shù)第十五頁，共三十一頁，編輯于2023年，星期六考慮方程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］上存在惟一不動(dòng)點(diǎn)x*（2）任取x0[a,b]，由xk+1=g(xk)得到的序列{xk}（［a,b】）收斂于x*

。（3）k次迭代所得到的近似不動(dòng)點(diǎn)xk與精確不動(dòng)點(diǎn)x*有有誤差估計(jì)式：定理3.2.1第十六頁，共三十一頁，編輯于2023年，星期六§3Fixed-PointIteration證明：①g(x)在[a,b]上存在不動(dòng)點(diǎn)？②不動(dòng)點(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*).第十七頁，共三十一頁，編輯于2023年，星期六§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)成立第十八頁，共三十一頁，編輯于2023年，星期六Remark：定理?xiàng)l件非必要條件，而且定理3.2.1中的壓縮條件不好驗(yàn)證，一般來講，

若知道迭代函數(shù)g(x)∈C1『a,b］,并且滿足|g′(x)|≤≤1,對(duì)任意的x∈［a,b］,則g（x)是［a,b］上的壓縮映射第十九頁，共三十一頁，編輯于2023年，星期六例題已知方程2x-7-lgx＝0，求方程的含根區(qū)間，考查用迭代法解此方程的收斂性。第二十頁，共三十一頁，編輯于2023年，星期六第二十一頁，共三十一頁，編輯于2023年，星期六在這里我們考查在區(qū)間[3.5,4]的迭代法的收斂性很容易驗(yàn)證：f(3.5)<0,f(4)>0將方程變形成等價(jià)形式：x＝(lgx+7)/2由定理3.2.1知，迭代格式xk+1＝(lgxk+7)/2在[3.5,4]內(nèi)收斂第二十二頁，共三十一頁，編輯于2023年，星期六局部收斂性定理定理3.2.2設(shè)x*為g的不動(dòng)點(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？

第二十三頁，共三十一頁，編輯于2023年，星期六舉例用一般迭代法求x3-x-1=0的正實(shí)根x*容易得到：g′(x)在包含x*的某鄰域U(x*)內(nèi)連續(xù)，且|g′(x*)|<1第二十四頁，共三十一頁，編輯于2023年，星期六例題用一般迭代法求方程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è)根第二十五頁，共三十一頁，編輯于2023年，星期六將方程化為等價(jià)方程：x＝2＋lnx因此，x0（2，），xk+1＝2＋lnxk產(chǎn)生的序列xk收斂于X*取初值x0＝3.0,計(jì)算結(jié)果如下：第二十六頁，共三十一頁，編輯于2023年，星期六7314617745293.146188209103.146191628113.146192714123.146193060133.146193169143.146193204kxi03.00000000013.098612289231413378664314570220963.146037143第二十七頁，共三十一頁，編輯于2023年，星期六另一種迭代格式：