对分法和一般迭代法

对分法和一般迭代法第一页，共二十九页，2022年，8月28日简介（Introduction）我们知道在实际应用中有许多非线性方程的例子，例如（1）在光的衍射理论（thetheoryofdiffractionoflight)中,我们需要求x-tanx=0的根（2）在行星轨道（planetaryorbits）的计算中,对任意的a和b，我们需要求x-asinx=b的根（3）在数学中，需要求n次多项式xn+a1

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

＝0的根求f(x)=0的根第二页，共二十九页，2022年，8月28日§4.1对分区间法(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步产生的有误差第k步产生的xk

有误差对于给定的精度,可估计二分法所需的步数k：第五页，共二十九页，2022年，8月28日

例1用二分法求

在(1,2)内的根，要求绝对误差不超过

解：

f(1)=-5<0有根区间

中点

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)内有根用二分法解之，(a,b）=（0,1)’计算结果如表：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)的方式是不唯一的,有的收敛,有的发散Forexample：2x3-x-1=0

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

如果将原方程化为等价方程由此可见，这种迭代格式是发散的

取初值第十页，共二十九页，2022年，8月28日(2)如果将原方程化为等价方程仍取初值依此类推,得

x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已经收敛,故原方程的解为x=1.0000同样的方程⇒不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?第十一页，共二十九页，2022年，8月28日收敛性分析定义2

若存在常数(0≤<1),使得对一切x1,x2∈［a,b］,成立不等式|g(x1)-g(x2)|≤|x1-x2|，(5)则称g(x)是［a,b］上的一个压缩映射，称为压缩系数第十二页，共二十九页，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*∈［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|联系估计式(6)可得|xk-x*|≤k-1/(1-)|x1-x0|.即估计式(7)成立第十五页，共二十九页，2022年，8月28日Remark：定理条件非必要条件，而且定理4.2.1中的压缩条件不好验证，一般来讲，

若知道迭代函数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*/

待定参数法：若

|g’(x)|1，则将x=g(x)等价地改造为求K，使得例：求在(1,2)的实根。如果用进行迭代，则在(1,2)中有现令希望，即在(1,2)上可取任意，例如K=0.5，则对应即产生收敛序列。第十八页，共二十九页，2022年，8月28日例题已知方程2x-7-lgx＝0，求方程的含根区间，考查用迭代法解此方程的收敛性。第十九页，共二十九页，2022年，8月28日第二十页，共二十九页，2022年，8月28日在这里我们考查在区间[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]内收敛第二十一页，共二十九页，2022年，8月28日局部收敛性定理定理4.2.2

设x*为g的不动点，g(x)与g′(x)在包含x*的某邻域U(x*)(即开区间)内连续，且|g′(x*)|<1,则存在>0，当x0∈［x*-，x*+］时，迭代法(3)产生的序列{xk}［x*-，x*+］且收敛于x*.证明略（作为练习）Wedon’tknowx*,howdoweestimatetheinequality？

第二十二页，共二十九页，2022年，8月28日举例用一般迭代法求x3-x-1=0的正实根x*容易得到：g′(x)在包含x*的某邻域U(x*)内连续，且|g′(x*)|<1第二十三页，共二十九页，2022年，8月28日例题用一般迭代法求方程x-lnx＝2在区间（2，）内的根，要求|xk-xk-1|/|xk|<=10-8解：令f(x)=x-lnx-2f(2)<0,f(4)>0,故方程在（2,4）内至少有一个根第二十四页，共二十九页，2022年，8月28日将方程化为等价方程：x＝2＋lnx因此，x0（2，），xk+1＝2＋lnxk产生的序列xk收敛于X*取初值x0＝3.0,计算结果如下：第二十五页，共二十九页，2022年，8月28日7314617745293.146188209103.1461916281