對分法和一般迭代法

對分法和一般迭代法第一頁，共二十九頁，2022年，8月28日簡介（Introduction）我們知道在實際應用中有許多非線性方程的例子，例如（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的根第二頁，共二十九頁，2022年，8月28日§4.1對分區(qū)間法(BisectionMethod)原理：若f(x)

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

在(a,b)上必有一根。第三頁，共二十九頁，2022年，8月28日abx1x2a1b2x*b1a2停機條件（terminationcondition）：或第四頁，共二十九頁，2022年，8月28日誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對于給定的精度,可估計二分法所需的步數(shù)k：第五頁，共二十九頁，2022年，8月28日

例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)第六頁，共二十九頁，2022年，8月28日

例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。第七頁，共二十九頁，2022年，8月28日Remark:二分法不能用來求重根第八頁，共二十九頁，2022年，8月28日f(x)=0x=g(x)等價變換f(x)的根g(x)的不動點§4.2單個方程的迭代法f(x)=0化為等價方程x=g(x)的方式是不唯一的,有的收斂,有的發(fā)散Forexample：2x3-x-1=0

xk+1=g(xk)(3)第九頁，共二十九頁，2022年，8月28日(1)

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

取初值第十頁，共二十九頁，2022年，8月28日(2)如果將原方程化為等價方程仍取初值依此類推,得

x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已經(jīng)收斂,故原方程的解為x=1.0000同樣的方程?不同的迭代格式有不同的結(jié)果什么形式的迭代法能夠收斂呢?第十一頁，共二十九頁，2022年，8月28日收斂性分析定義2

若存在常數(shù)(0≤<1),使得對一切x1,x2∈［a,b］,成立不等式|g(x1)-g(x2)|≤|x1-x2|，(5)則稱g(x)是［a,b］上的一個壓縮映射，稱為壓縮系數(shù)第十二頁，共二十九頁，2022年，8月28日考慮方程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*有有誤差估計式：定理第十三頁，共二十九頁，2022年，8月28日§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*).第十四頁，共二十九頁，2022年，8月28日§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)成立第十五頁，共二十九頁，2022年，8月28日Remark：定理條件非必要條件，而且定理4.2.1中的壓縮條件不好驗證，一般來講，

若知道迭代函數(shù)g(x)∈C1『a,b］,并且滿足|g′(x)|≤<1,對任意的x∈［a,b］,則g（x)是［a,b］上的壓縮映射第十六頁，共二十九頁，2022年，8月28日xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1第十七頁，共二十九頁，2022年，8月28日改進、加速收斂/*acceleratingconvergence*/

待定參數(shù)法：若

|g’(x)|1，則將x=g(x)等價地改造為求K，使得例：求在(1,2)的實根。如果用進行迭代，則在(1,2)中有現(xiàn)令希望，即在(1,2)上可取任意，例如K=0.5，則對應即產(chǎn)生收斂序列。第十八頁，共二十九頁，2022年，8月28日例題已知方程2x-7-lgx＝0，求方程的含根區(qū)間，考查用迭代法解此方程的收斂性。第十九頁，共二十九頁，2022年，8月28日第二十頁，共二十九頁，2022年，8月28日在這里我們考查在區(qū)間[3.5,4]的迭代法的收斂性很容易驗證：f(3.5)<0,f(4)>0將方程變形成等價形式：x＝(lgx+7)/2由定理4.2.1知，迭代格式xk+1＝(lgxk+7)/2在[3.5,4]內(nèi)收斂第二十一頁，共二十九頁，2022年，8月28日局部收斂性定理定理4.2.2

設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？

第二十二頁，共二十九頁，2022年，8月28日舉例用一般迭代法求x3-x-1=0的正實根x*容易得到：g′(x)在包含x*的某鄰域U(x*)內(nèi)連續(xù)，且|g′(x*)|<1第二十三頁，共二十九頁，2022年，8月28日例題用一般迭代法求方程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)至少有一個根第二十四頁，共二十九頁，2022年，8月28日將方程化為等價方程：x＝2＋lnx因此，x0（2，），xk+1＝2＋lnxk產(chǎn)生的序列xk收斂于X*取初值x0＝3.0,計算結(jié)果如下：第二十五頁，共二十九頁，2022年，8月28日7314617745293.146188209103.1461916281