對分法和一般迭代法

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

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

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

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

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

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

例1用二分法求

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

解：

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

中點

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的一個實根。因為f(0)<0,f(1)>0。故f(x)在(0,1)內(nèi)有根用二分法解之，(a,b）=（0,1)’計算結(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。第七頁，共三十一頁，編輯于2023年，星期六Remark1：求奇數(shù)個根

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

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

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

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

若存在常數(shù)(0≤<1),使得對一切x1,x2∈［a,b］,成立不等式|g(x1)-g(x2)|≤|x1-x2|，(5)則稱g(x)是［a,b］上的一個壓縮映射，稱為壓縮系數(shù)第十五頁，共三十一頁，編輯于2023年，星期六考慮方程x=g(x),g(x)C[a,b],若(I)當x[a,b]時，g(x)[a,b]；(II)在［a,b］上成立不等式：|g(x1)-g(x2)|≤|x1-x2|

。則（1）g在［a,b］上存在惟一不動點x*（2）任取x0[a,b]，由xk+1=g(xk)得到的序列{xk}（［a,b】）收斂于x*

。（3）k次迭代所得到的近似不動點xk與精確不動點x*有有誤差估計式：定理3.2.1第十六頁，共三十一頁，編輯于2023年，星期六§3Fixed-PointIteration證明：①g(x)在[a,b]上存在不動點？②不動點唯一？③當k

時，

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|.這就證明了估計式(6).(5)|xk-xk-1|

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

k-1|x1-x0|聯(lián)系估計式(6)可得|xk-x*|≤k-1/(1-)|x1-x0|.即估計式(7)成立第十八頁，共三十一頁，編輯于2023年，星期六Remark：定理條件非必要條件，而且定理3.2.1中的壓縮條件不好驗證，一般來講，

若知道迭代函數(shù)g(x)∈C1『a,b］,并且滿足|g′(x)|≤≤1,對任意的x∈［a,b］,則g（x)是［a,b］上的壓縮映射第十九頁，共三十一頁，編輯于2023年，星期六例題已知方程2x-7-lgx＝0，求方程的含根區(qū)間，考查用迭代法解此方程的收斂性。第二十頁，共三十一頁，編輯于2023年，星期六第二十一頁，共三十一頁，編輯于2023年，星期六在這里我們考查在區(qū)間[3.5,4]的迭代法的收斂性很容易驗證：f(3.5)<0,f(4)>0將方程變形成等價形式：x＝(lgx+7)/2由定理3.2.1知，迭代格式xk+1＝(lgxk+7)/2在[3.5,4]內(nèi)收斂第二十二頁，共三十一頁，編輯于2023年，星期六局部收斂性定理定理3.2.2設(shè)x*為g的不動點，g(x)與g′(x)在包含x*的某鄰域U(x*)(即開區(qū)間)內(nèi)連續(xù)，且|g′(x*)|<1,則存在>0，當x0∈［x*-，x*+］時，迭代法(3)產(chǎn)生的序列{xk}［x*-，x*+］且收斂于x*.證明略（作為練習）Wedon’tknowx*,howdoweestimatetheinequality？

第二十三頁，共三十一頁，編輯于2023年，星期六舉例用一般迭代法求x3-x-1=0的正實根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)至少有一個根第二十五頁，共三十一頁，編輯于2023年，星期六將方程化為等價方程：x＝2＋lnx因此，x0（2，），xk+1＝2＋lnxk產(chǎn)生的序列xk收斂于X*取初值x0＝3.0,計算結(jié)果如下：第二十六頁，共三十一頁，編輯于2023年，星期六7314617745293.146188209103.146191628113.146192714123.146193060133.146193169143.146193204kxi03.00000000013.098612289231413378664314570220963.146037143第二十七頁，共三十一頁，編輯于2023年，星期六另一種迭代格式：