数值分析对分法和一般迭代法

数值分析对分法和一般迭代法第1页，课件共41页，创作于2023年2月非线性方程求根1．根的存在性。方程有没有根？如果有根，有几个根？定理1：设函数f(x)在区间[a,b]上连续，如果f(a)

f(b)<0，

则方程f(x)=0在[a,b]内至少有一实根x*。

2．这些根大致在哪里？如何把根隔离开来？3．根的精确化第2页，课件共41页，创作于2023年2月abx*f(x)1．画出f(x)的略图，从而看出曲线与x轴交点的位置。2．从左端点x=a出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点x0和终点x0+h的函数值，若那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h作为根的初始近似。第3页，课件共41页，创作于2023年2月

开始读入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印结束否是继续扫描

第4页，课件共41页，创作于2023年2月例1：考察方程的含根区间x00.51.01.5f(x)符号－－－＋可见，含根区间为

[1,1.5]第5页，课件共41页，创作于2023年2月§4.1对分区间法(BisectionMethod)原理：若f(x)

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

在(a,b)上必有一根。第6页，课件共41页，创作于2023年2月abx1x2a1b2x*b1a2或不能保证

x

的精度2xx*第7页，课件共41页，创作于2023年2月

执行步骤1．计算f(x)在有解区间[a,b]端点处的值，f(a)，f(b)。2．计算f(x)在区间中点处的值f(x1)。3．判断若f(x1)=0，则x1即是根，否则检验：（1）若f(x1)与f(a)异号，则知解位于区间[a,x1]，

b1=x1,a1=a;（2）若f(x1)与f(a)同号，则知解位于区间[x1,b]，

a1=x1,b1=b。反复执行步骤2、3，便可得到一系列有根区间：

(a,b),(a1,b1),…,(ak,bk),…第8页，课件共41页，创作于2023年2月4、当时，则即为根的近似。①简单;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢第9页，课件共41页，创作于2023年2月误差分析：第1步产生的有误差第k步产生的xk

有误差对于给定的精度,可估计二分法所需的步数k：第10页，课件共41页，创作于2023年2月定义f(x)f(a)

f(b)>0f(a)

f(b)=0f(a)=0打印b,k打印a,k结束是是是否否否m=(a+b)/2|a-b|<f(a)f(b)>0打印m,ka=mb=m结束k=k+1是是否否输入k=0第11页，课件共41页，创作于2023年2月

例2用二分法求

在(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)第12页，课件共41页，创作于2023年2月12

例3，求方程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。第13页，课件共41页，创作于2023年2月Remark1：求奇数个根

Findsolutionstotheequationontheintervals[0,4]，Usethebisectionmethodtocomputeasolutionwithanaccuracyof10－7.Determinethenumberofiterationstouse..第14页，课件共41页，创作于2023年2月[0,1],[1.5,2.5]and[3,4]，利用前面的公式可计算迭代次数为k=23.第15页，课件共41页，创作于2023年2月Remark2:要区别根与奇异点Considerf(x)=tan(x)ontheinterval(0,3).Usethe20iterationsofthebisectionmethodandseewhathappens.Explaintheresultsthatyouobtained.（如下图）第16页，课件共41页，创作于2023年2月Remark3:二分法不能用来求重根第17页，课件共41页，创作于2023年2月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)第18页，课件共41页，创作于2023年2月(1)

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

取初值第19页，课件共41页，创作于2023年2月(2)如果将原方程化为等价方程仍取初值依此类推,得

x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000已经收敛,故原方程的解为x=1.0000同样的方程⇒不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?第20页，课件共41页，创作于2023年2月收敛性分析定义2

若存在常数(0≤<1),使得对一切x1,x2∈［a,b］,成立不等式|g(x1)-g(x2)|≤|x1-x2|，(5)则称g(x)是［a,b］上的一个压缩映射，称为压缩系数第21页，课件共41页，创作于2023年2月

考虑方程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*有误差估计式：定理4.2.1第22页，课件共41页，创作于2023年2月§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*).第23页，课件共41页，创作于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|.这就证明了估计式(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)成立第24页，课件共41页，创作于2023年2月Remark：定理条件非必要条件，而且定理4.2.1中的压缩条件不好验证，一般来讲，

若知道迭代函数g(x)∈C1『a,b］,并且满足|g′(x)|≤<1,对任意的x∈［a,b］,则g（x)是［a,b］上的压缩映射第25页，课件共41页，创作于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页，创作于2023年2月改进、加速收敛/*acceleratingconvergence*/

待定参数法：若

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

第31页，课件共41页，创作于2023年2月举例用一般迭代法求x3-x-1=0的正实根x*容易得到：g′(x)在包含x*的某邻域U(x*)内连续，且|g′(x*)|<1第32页，课件共41页，创作于2023年2月例题用一般迭代法求方程x-lnx＝2在区间（2，）内的根，要求|xk-xk-1|/|xk|<=10-8解：令f(x)=x-lnx-2f(2)<0,f(4)>0,故方程在（2,4）内至少有一个根第33页，课件共41页，创作于2023年2月将方程化为等价方程：x＝2＋lnx因此，x0（2，），xk+1＝2＋lnxk产生的序列xk收敛于X*取初值x0＝3.0,计算结果如下：第34页，课件共41页，创作于2023年2月7314617745293.146188209103.146191628113.146192714123.146193060133.146193169143.146193204kxi03.00000000013.098612289231413378664314570220963.146037143第35页，课件共41页，创作于2023年2月另一种迭代格式：

03.0000000001314619344133.146193221第36页，课件共41页，创作于2023年2月程序演示由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。第37页，课件共41页，创作于2023年2月

定义1.:设序列{xk}收敛于x*，若存在p≥1和正数c，使得成立则称{xk}为p阶收敛的特别,

p=1，要求c<1,称线性收敛;1<p<2,称超线性收敛

p=2,称平方收敛。迭代法的收敛阶(收敛速度)第38页，课件共41页，创作于2023年2月定理4.2.3设x*为g的不动点，p≥2为正整数，g在x*的某邻域Ｕ(x*)内p阶连续可微，且g′(x*)=g″(x*)=…=g(p-1)(x*)=0，而g(p)