弦截法求方程根

第二章非线性方程求根§1方程求根与二分法§2迭代法§3迭代收敛的加速法§4牛顿法§5弦截法与抛物线法§6

解非线性方程组的牛顿迭代法5/7/2025【本章重点】

1．不动点迭代法及其收敛性与收敛速度。

2．Newton迭代法【学习目标】本章主要掌握方程求根的不动点迭代法及其收敛性，收敛阶及Steffensen加速迭代原理，熟练掌握Newton法及其收敛性和Newton法应用于求平方根和立方根。5/7/2025【课前思考】

1．什么是方程f(x)=0求根的二分法？如何估计近似根xn的误差?

2．什么是不动点迭代法？怎样判断迭代法的收敛性？

3．迭代法收敛速度：收敛阶定义，如何加速迭代收敛？

4．给出方程f(x)＝0求根的Newton法，它有何优缺点？如何用Newton法求方程根？

5/7/2025§1方程求根与二分法单个变量的方程

f(x)=0

(1.1)

求根是数值计算经常遇到的问题.当f(x)为一般连续函数时，称式(2.1.1)为超越方程，如果f为多项式

f(x)=a0xn+a1xn-1+…+an-1x+

an

(1.2)若a0≠0,f(x)为n次多项式，此时方程(1.1)称为代数(或多项式)方程.如果x*(实数或复数)使f(x*)=0，则称x*为方程(1.1)的根，若f(x)=(x-x*)mg(x)，m为正整数，且g(x*)≠0，当m＞1时，称x*为方程(1.1)的m重根或称x*是f的m重零点.若x*是f的m重零点，且g充分光滑，则f(x*)=f’(x*)=…=

f(m-1)(x*)=

0

，f(m)(x*)

≠

0

。当f为式(1.2)表示的代数多项式时，根据代数基本定理可知方程(1.1)有n个根(含复根，m重根为m个根)，对n=1,2的代数方程的根是大家熟悉的。5/7/2025而当n=3,4时方程的根，可在数学手册中查到虽可用公式表示，但表达式太复杂，一般不用；当n≥5已没有直接用公式表达的求根算法。因此对n≥3的代数方程求根方法与一般超越方程(1.1)一样都采用迭代方法求根，设(表示f在区间上连续)，若有f(a)f(b)＜0,则f(x)=0在区间上至少有一个实根，称为有根区间，通常可用逐次搜索法求得方程(1.1)的有根区间.方程的三个有根区间为［2,3］,［3,4］,［5,6］.例2.1

求方程f(x)=x3-11.1x2+38.8x-41.77=0的有根区间.解

根据有根区间定义，对方程的根进行搜索计算，结果如下表：§1方程求根与二分法5/7/2025二分法原理给定方程f(x)=0,设f(x)在区间[a,b]连续,且f(a)f(b)<0,则方程f(x)在(a,b)内至少有一根,为便于讨论,不妨设方程f(x)=0在(a,b)内只有一实根x*采取使有根区间逐步缩小,从而得到满足精度要求的实根x*的近似值xk。取[a,b]区间二等分的中点x0=(a+b)/2,若f(x0)=0,则x0是f(x)=0的实根若f(a)f(x0)<0成立,则必在区间(a,x0)内,取a1=a,b1=x0;否则必在区间(x0,b)内,取a1=x0,b1=b,这样,得到新区间(a1,b1),其长度为[a,b]的一半,如此继续下去,进行k次等分后,得到一组不断缩小的区间,[a,b],[a1,b1],......[ak,bk].§1方程求根与二分法5/7/2025其中每一个区间都是前一个长度的一半,从而[ak,bk]的长度为

如此继续下去,则有这些区间将收敛于一点,该点即为所求的根.当做到第k步时，有为给定精度此时即为所求方程的近似解.

以上方法就是用于求非线性方程实根近似值的二分法.§1方程求根与二分法akbkxkx*5/7/2025abx1x2ab不能保证

x

的精度x*

xx*§1方程求根与二分法5/7/2025

取x6=1.3242

，误差为|x*-x6|<0.005

。例1，求方程f(x)=x3–x-1=0在区间[1，1.5]的一个实根，要求准确到小数点后的第2位。

解：因为f(1)<0，f(1.5)>0。故f(x)在(1，1.5)内有根。考虑二分次数，由误差估计公式：有2k>50,k>50/ln2≈5.645(26=64)k至少取6用二分法解之，(a,b）=（1,1.5)计算结果如表：k ak

bk

xk

f(xk)符号 0 1.0 1.5 1.2500 － 1 1.2500 － 1.3750＋

2 －

1.37501.3125－

3 1.3125－

1.3438＋ 4 － 1.3438 1.3281＋ 5 － 1.3281 1.3203－ 6 1.3203－ 1.3242－

5/7/2025

例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。5/7/2025

例3:用二分法求方程

在区间(1,2)内的实根,要求误差限为

。

解：令f(1)<0,f(2)>0记I0=[1,2],x0=(1+2)/2=1.5因为f(x0)f(1)>0得I1=[1.5,2],x1=(1.5+2)/2=1.75f(x1)f(1.5)<0得I2=[1.5,1.75],x2=(1.5+1.75)/2=1.625…….I6=[1.681875,1.6875],I7=[1.671875,1.679688]b7-a7=0.781310-2<10-2

x*x7=1.67585/7/2025§1方程求根与二分法误差分析：第1步产生的有误差第k步产生的xk

有误差对于给定的精度

,可估计二分法所需的步数k：①简单;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢

注：用二分法求根，最好先给出f(x)

草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。5/7/2025例：利用二分法求方程f(x)=-tanx在区间[0，∏/2]内的实根，使精度达到10-5。程序设计x=0:0.1:pi/2;y=sqrt(x.^2+1)-tan(x);plot(x,y)5/7/2025function[x,k]=deminmethod(a,b,f,emg)fa=feval(f,a);fab=feval(f,(a+b)/2);k=0;whileabs(b-a)>emgiffab==0x=(a+b)/2;return;elseif

fa*fab<0b=(a+b)/2;elsea=(a+b)/2;endfa=feval(f,a);fab=feval(f,(a+b)/2);k=k+1;endx=(a+b)/2;函数文件func2.mfunctionf=func2(x)f=sqrt(x^2+1)-tan(x);在命令窗口中输入：f=@func2;[x0,k]=deminmethod(0,pi/2,f,10^-5)%a,b表示求解区间[a,b]的端点%f表示所求解方程的函数名%emg是精度指标%x表示所求近似值%k表示循环次数deminmethod.mx0=0.94145973617123k=185/7/2025§2迭代法f(x)=0等价变换f(x)的根g(x)的不动点从一个初值x0

出发，计算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得

，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f

的根。x=g(x)(2.1)称

xk+1=g(xk)

（2.2）为不动点迭代法.

5/7/2025§2迭代法xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1

x0p0x1p1

x0p0x1p1

x0p0x1p1

5/7/2025

若将方程改为

，构造迭代法

(2.4)

计算结果见表2-2.表2－2

从结果看它是收敛的，且在6位有效数字时x7=x8=1.32472即为根x*的近似值.例2.3求方程f(x)=x3–x-1=0在x0=1.5附近的根x*.

解若将方程改写为

x=x3-1,

构造迭代法

(2.3)

由x0=1.5,x1=2.375,x2=12.39,…可知，xk显然不收敛.例题表明构造迭代法(2.2)，必须使迭代序列{xk}收敛，才能求得方程(2.1)的解x*.下面给出解的存在唯一性和迭代收敛性定理.§2迭代法5/7/2025定理考虑方程x=g(x),g(x)

C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)0L<1使得

|g’

(x)|L<1对

x[a,b]成立。则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点。并且有误差估计式：

(k=1,2,…)且存在极限收敛

唯一

x,y[a,b]有|g(x)-g(y)|≤

L|x-y|存在§2迭代法5/7/2025证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则之间。而③当k

时，

xk收敛到x*？

§2迭代法5/7/2025④⑤

⑥

可用来控制收敛精度L越小收敛越快

§2迭代法5/7/2025注：上述定理为全局收敛性，不易检验定理条件。可将[a,b]缩小，定义局部收敛性：若在x*的某

邻域P:|xx*|

有g(x)

C1[a,b]且|g’(x*)|<1，则由

x0

P

开始的迭代序列{xk}

P局部收敛于x*。即调整初值可得到收敛的结果。x=x3-1，g(x)=x3-1，g’(x)=3x2>1(x∈[1,2])不满足条件，所得序列{xk}发散。(x∈[1,2])满足条件，所得序列{xk}收敛。解析：xP，总有g(x)P.§2迭代法?5/7/2025定义：设迭代过程xk+1=g(xk)收敛于方程x=g(x)的根x*,如果迭代误差ek=xk-x*当k->∞时成立下列渐进关系：则称该迭代过程是p阶收敛的。特别地，p=1时称线性收敛；p>1时称超线性收敛；p=2时称平方收敛.定理:对于迭代过程xk+1=g(xk)，如果g(p)(x)在所求根x*的邻近连续，并且则称该迭代过程在x*的邻近是p阶收敛的.§2迭代法5/7/2025分析：g(x)在x*处的p-1阶泰勒展式§2迭代法5/7/2025发散1阶收敛发散例：用不同方法求方程x2-3=0的根x*=,并讨论是否收敛和收敛的阶数。§2迭代法5/7/20252阶收敛§2迭代法5/7/2025例：利用迭代法求方程f(x)=x3-x-1在x0=1.5附近的根x*，使精度达到10-5。程序设计>>[f,k]=diedai(10^-5,1.5)function[f,k]=diedai(eps,x0)%eps是精度指标%x0表初值formatlongx(1)=x0;x(2)=(x(1)+1)^(1/3);%x(2)=x(1)^3-1;k=2;whileabs(x(k)-x(k-1))>epsx(k+1)=(x(k)+1)^(1/3);%x(k+1)=x(k)^3-1;k=k+1;endk=k-1;f=x';考虑用和（k=0,1,2,…)两种迭代公式！§2迭代法5/7/2025f=1.500000000000001.357208808297451.330860958801431.325883774232351.324939363401881.324760011292701.324725945226891.32471947453436k=7§2迭代法5/7/2025

Aitken（埃特金）加速：xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)改进、加速收敛x1-x*=g(x0)-g(x*)=g’(§)(x0-x*)≈L(x0-x*)其中g’(x)≈L即：x1-x*≈L(x0-x*)同理x2-x*≈L(x1-x*)§3迭代收敛的加速法5/7/2025一般地，记：称为Aitken（埃特金）⊿2

加速方法。§3迭代收敛的加速法比收敛得略快。可以证明表明5/7/2025

Steffensen（斯蒂芬森）加速：§3迭代收敛的加速法其实是将原不动点迭代计算两次合并成一步得到，可改为另一种不动点迭代法:将Aitken（埃特金）加速与不动点迭代结合.可得到如下迭代法:5/7/2025§3迭代收敛的加速法定理3.1

若x*

为上式定义的函数φ(x)的不动点，则x*

为g(x)的不动点.反之，若x*是g(x)的不动点，设g’’(x)存在,g’(x*

)

≠0，则x*是φ(x)的不动点且斯蒂芬森迭代法是二阶收敛的.(证明略）例2.3用Steffensen

（斯蒂芬森）加速法求方程f(x)=x3–x-1=0在x0=1.5附近的根x*.

解前面指出:若将方程改写为

x=x3-1,

构造迭代公式

(2.3)

由x0=1.5,x1=2.375,x2=12.39,…可知，xk显然不收敛.现在用Steffensen

（斯蒂芬森）加速法,5/7/2025§3迭代收敛的加速法取g(x)=x3-1,则:5/7/2025程序设计function[f,k]=Steffensen(eps,x0)%eps是精度指标%x0表初值formatlongx(1)=x0;x(2)=x(1)-(x(1)^3-x(1)-1)^2/((x(1)^3-1)^3-2x(1)^3+x(1)+1);k=2;whileabs(x(k)-x(k-1))>epsx(k+1)=x(k)-(x(k)^3-x(k)-1)^2/((x(k)^3-1)^3-2x(k)^3+x(k)+1);k=k+1;endk=k-1;f=x';5/7/2025>>[f,k]=Steffensen(10^-5,1.5)f=1.500000000000001.416292974588941.355650441476641.328948777284011.324804489041041.324717993968811.324717957244751.32471795724475k=7>>[f,k]=diedai(10^-5,1.5)f=1.500000000000001.357208808297451.330860958801431.325883774232351.324939363401881.324760011292701.324725945226891.324719474534361.324718245448941.324718011988201.324717967643091.324717959219881.324717957619921.324717957316011.32471795725828k=145/7/2025§4牛顿法（切线法）原理：将非线性方程线性化

——Taylor展开将f(x)在xk

做一阶Taylor展开:，

在xk

和x

之间。将(x

xk)2

看成高阶小量，则有：xyx*xk只要f

C1，每一步迭代都有f’(xk

)0，而且，则

x*就是f

的根。5/7/2025牛顿法事实上是一种特殊的不动点迭代,其中:收敛解析：由Taylor展开：

假设x*是f(x)的单根,即f(x*)=0,f’(x*)0

则故牛顿法在根x*的附近是二阶收敛。5/7/2025注：Newton’sMethod收敛性依赖于x0

的选取。x*x0

x0

x05/7/2025

下山法——Newton’sMethod

局部微调：原理：若由xk

得到的xk+1不能使|f|减小，则在xk

和xk+1之间找一个更好的点，使得。xkxk+1改进与推广从=1开始，逐次将减半进行计算直至能够满足下降条件：注：

=1时就是Newton’sMethod公式。当

=1代入效果不好时，将

减半计算。5/7/2025例：用牛顿下山法求方程的根，使精度达到10^-6,初始值分别选取x0=-1.2和2.0x=-5:0.1:5;y=sqrt(x.^2+1)-tan(x);plot(x,y)5/7/2025function[x,k]=Mendnewton(f,x0,emg)%emg是精度指标，k、u分别表示迭代次数和下山因子[f1,d1]=feval(f,x0);%d1表示非线性方程f在x0处的导数值，k=1;x(1)=x0;x(2)=x(1)-f1/d1;whileabs(f1)>emgu=1;k=k+1;[f1,d1]=feval(f,x(k));x(k+1)=x(k)-u*f1/d1;[f2,d2]=feval(f,x(k+1));whileabs(f2)>abs(f1)%保证迭代后的函数值比迭代前的函数值小

u=u/2;x(k+1)=x(k)-u*f1/d1;%牛顿下山迭代

[f2,d2]=feval(f,x(k+1));endendfunction[f,d]=func3(x)f=sqrt(x^2+1)-tan(x);d1='sqrt(x^2+1)-tan(x)';d=subs(diff(d1));%对函数f求一次导数

%subs将sym型数据转化为double型Conversiontodoublefromsym.5/7/2025x=-1.200000000000