非线性方程求根-补充知识VIP

非线性方程的数值解§1二分法

§2迭代法2.1迭代格式2.2收敛性条件2.3迭代法的收敛阶

§3牛顿迭代法

3.1迭代格式3.2迭代法的收敛阶§4弦割法

xyoab*x*4/2/20231解析解与数值解由推理的方法计算---解析解(精确解)。近似计算（数值计算）---数值解(近似解）。常借助于计算机。对于工科而言，各门后续课程和未来的工程实践中遇到最大量的将是数值计算问题。4/2/20232这种方程往往无法求得其精确解，只能通过数值方法求其近似解。这里我们将介绍两种数值方法：非线性方程求根是我们经常碰到的问题，例如：(1).二分法;(2).迭代法：一般迭代法、牛顿迭代法、弦截法.4/2/20233§1二分法对于

f(x)=0

（1）

设

f(x)∈C[a,b]

，且

f(a)f(b)<0

，则知（1）在(a,b)内至少有一实根x*。如果在(a,b)内有(1)的唯一实根x*：则可以用二分法进行求解，求解的步骤如下：xyoab*x*4/2/20234Step1计算f(a)、f(b)及

若令a1=a,若则x*∈[a1,b1]则若b1=b,令则x*∈[a1,b1]x*abx*ababx*a1b1a1b14/2/20235stepk：计算f(ak-1)、f(bk-1)及

若则

令ak=ak-1,若则x*∈[ak,bk]若bk=bk-1,令则x*∈[ak,bk]最后可取x*akbk4/2/20236误差

运算次数的控制,可以用下面两种方式处理：1）令

2）令b0a0a1b1a2b24/2/20237

例1求方程x3-x-1=0在区间[1,1.5]内的实根，要求误差不超过0.005.解：令f(x)=x3-x-1则有

f(1)=-1,f(1.5)=0.875且由

f’(x)=3x2-1>0,x∈[1.0,1.5]可知f(x)=0在[1,1.5]

内有唯一实根x*。这时f(1)f(1.5)<0x*Ox1.01.5y我们采用二分法进行计算，每一次的计算结果由下表给出4/2/20238kakbkxk=(ak+bk)/2f(xk)01.01.5

1

2

3

456f(x)=x3-x-1,f(1)=-1<0,f(1.5)=0.875>01.25-0.29691.251.51.3750.22461.251.3751.3125-0.05151.31251.3751.34380.08281.31251.34381.32810.01451.31251.32811.3203-0.01881.32031.32811.3242-0.0018这时|x6-x5|=0.0039<0.005,可得近似解

x*≈x6=1.32424/2/20239这里的a=1.0,b=1.5,取ε=0.005，代入上面的不等式即

2k+1>102取k=6,也就是计算6次就可以达到满足精度要求的近似解.应当注意：二分法要求f(x)连续，但只能求单根且收敛速度不快。下面我们介绍迭代解法。另外，我们也可以提前确定计算次数，这时利用关系式

—>

(k+1)lg

2

>24/2/202310§2、迭代解法一、迭代格式的构造对于f(x)=0(1)将其改写为x=g(x)(2)取适当的初值

x0

得迭代格式:并称其为求解(1)

的迭代法，g(x)称为迭代函数。xk+1=g(xk),k=0,1,2,…(3)设x*为

(1)

精确解，如果，则称迭代解{xk}收敛，否则称为发散。4/2/202311例2

用简单迭代法求x3-2x-3=0在[1,2]内的根。解：容易验证方程[1,2]在

内只有单根。改写原方程为得迭代格式取初始值x0=1.9，由上面的迭代格式求得近似解如下：这里4/2/202312……………由于x8、x9相当接近，故可取x*≈x8=1.89328920。如果将原方程x3-2x-3=0改为

仍取初值x0=1.9，得迭代格式如下：x1=1.8945647x2=1.89352114x8=1.89328920x9=1.893289204/2/202313得到的近似解是不收敛的，越来越发散。

由此可见迭代函数g(x)

选取的适当，近似解将会收敛；选取的不适当，近似解将会发散。

求得近似解为：x0=1.900x1=1.930x2=2.095x3=3.098x4=13.37那么选择怎样的g(x)

迭代格式才会收敛呢？下面我们将讨论这一问题。

4/2/202314二、收敛性条件定理1

设迭代函数g(x)满足条件由方程f(x)=0产生的迭代格式:xk+1=g(xk),k=0,1,2,…(3)具有如下的收敛性条件.

1）g(x)∈C[a,b]

;3）g’(x)存在，且存在0<L<1，使得对一切x∈[a,b]，

|g’(x)|≤L<1

2）当x∈[a,b]

时,g(x)∈[a,b]

;则有以下结论：4/2/2023151）方程f(x)=0或者x=g(x)在[a,b]上有唯一解x*.3）x*有误差估计式

2）对于任意的x0∈[a,b]迭代格式xk+1=g(xk)，k=0,1,2…收敛,而且：或4）4/2/202316例3确定xex–1=0

在[0.5，0.65]

内是否存在唯一实根，如果存在，试构造一收敛的迭代格式，并求出近似解，精度要求为ε=10-5。解:将原方程改写成如下的形式x=e-x,则g(x)=e-x检查定理的条件：1).g(x)∈C[0.5,0.65]

;2).g(x)=e-x在[0.5,0.65]在内递减,而且g(0.5)=0.6065,g(0.65)=0.5220，

故有g(x)∈[0.5,0.65]。3).由g’(x)=-e-x可得|g’(x)|=|-e-x|≤0.6065.由此可知x

=e-x可在[0.5,0.65]上有唯一解,而且迭代格式xk+1=e-xk

,k=0,1,2,…收敛.4/2/202317下面确定满足精度要求ε=10-5需要迭代的次数：任取一个初始解x0=0.5,则由迭代格式xk+1=e–xk求得故最少需迭代22次,计算结果为按照误差估计式于是两边取对数得到：klg

0.61<-5+lg3.66查表计算得到：-0.21k<-4.43解得k>4.43/0.21=21.12.x1=e–x0=e–0.5=0.606534/2/202318ixiixi00.50000000110.5672772010.60653066120.5670673520.54523921130.5671863630.57970310140.5671188640.56006463150.5671571450.57117215160.5671354360.56486295170.5671477470.56843805180.5671407680.56640945190.5671447290.56755963200.56714248100.56690721210.56714375x22=0.56714303|x21-x22|=0.00000072<0.000001=10-64/2/202319关于解的唯一性的判别，还可以借助于根的存在性定理。我们用另一种方法完成上面的例子。再由xex–1=0得x=e-x,x∈[0.5,0.65],其中g(x)=e-x.说明f(x)=0在[0.5,0.65]上至少有一个实根，又由于解法二:令f(x)=xex-1,有f(0.5)=-0.176,f(0.65)=0.5220

f(0.5)f(0.65)<0

说明f(x)在[0.5,0.65]上严格递增，所以在[0.5,0.65]只有一个实根x*。f’(x)=(x+1)ex>0,x∈[0.5,0.65]

其它步骤与前面的相同，可以完成问题的解决。4/2/202320在实际应用中，通常已经知道方程f(x)=0根的x*在在某点x0附近存在，希望采用迭代法求出足够精确的近似解。这时，在使用迭代法时，总是在根x*的邻域内考虑。上面定理中的第二个条件|g’(x)|≤L<1在较大的区间内有可能不成立，但在根的附近是成立的。由此给出下面局部收敛性定理

定理2(迭代法局部收敛性定理)：如果方程x=g(x)满足条件：1).g(x)在方程的解x*的邻域内连续可微；2).|g’(x*)|<1(由于g(x)在x*的邻域内连续可微，故一定存在L使得|g’(x*)|≤L<1)；则定理1的结论成立。4/2/202321例4已知方程x=e-x

在0.5附近有一实根，如果采用迭代格式xk+1=e-xk

,k=0,1,2,…试判断是否收敛

。解：取g(x)=e-x，求得g’(x)=-e-x，由于所以，当取定初值x0=0.5

时，该迭代格式收敛。|g’(0.5)|=0.6065<14/2/202322

三、迭代法的收敛阶迭代法收敛速度的快慢可以通过收敛阶来衡量，下面给出这一概念。定义：由迭代法xk+1=g(xk)产生的误差ek=xk-x*，如果当k

∞时则称迭代法是p

阶收敛的，当p=1时称为线性收敛，当p=2时称为平方收敛。4/2/202323例如，对于迭代解xk+1=g(xk)与精确解x*=g(x*)两式相减，得到如果则迭代格式xk+1=g(xk)

线性收敛。且4/2/202324例5如果g(x)在方程x=g(x)

根x*的附近具p阶连续导函数,且g’(x*)=g”(x*)=…=g(p-1)(x*)=0,但g(p)(x*)≠0，试证明迭代格式xk+1=g(xk)，k=0,1,2,…具有p阶收敛速度。证明：利用Taylor展式得到ek+1=xk+1-x*=g(xk)-g(x*)其中ξ位于

xk与x*之间，这时4/2/202325由于|g’(x*)|=0<1,所以迭代格式xk+1=g(xk)，k=0,1,2,…收敛，且具有p阶收敛速度。上面讨论的迭代法也称作一般迭代法，下面我们再介绍两种收敛阶较高的迭代法——牛顿迭代法和弦截法。4/2/202326§3、牛顿迭代法一、迭代格式由f(x)=0,改变为x=g(x)往往只是线性收敛的，采用f(x)近似代替可得出高阶收敛方法。设x*为

f(x)=0的解，xk为近似解，则由Taylor展式略去高次项得4/2/202327令故解得如果并称（1）为方程求根的牛顿迭代格式。则（1）而f(x*)=0

4/2/202328方程求根的牛顿迭代法为又称为切线法，可以通过其几何意义明确这一称呼，如下图所示：x0xyoabx*x1x21).在解的附近任取一点x0,在曲线上过点(x0,f(x0))作切线y=f(x0)+f’(x0)(x-x0)(x0,f(x0))令y=0,得到切线与x轴的交点2).再过点(x1,f(x1))作切线y=f(x1)+f’(x1)(x-x1)(x1,f(x1))令y=0,得到切线与x轴的交点以此类推，最后得到的近似解x0,x1,x2,…越来越靠近x*。4/2/202329

二、收敛性与收敛阶对于牛顿迭代格法迭代函数为导数为在精确解x*处,由f(x*)=0得到|g’(x*)|=0=L<1

由局部收敛性可知：牛顿迭代法是局部收敛的。4/2/202330得到：关于收敛阶，由牛顿迭代格式再由Taylor展式得到：两式相减得：即：当k∞时xk

x*,ξx*这时如果则说明Newton迭代法具有二阶收敛速度。4/2/202331例6

用牛顿迭代法求方程xex-1=0在x0=0.5附近的根。解:已知方程在[0.5,0.6]内有唯一实根,令f(x)=xex-1则f’(x)=(x+1)ex

,这样可以得到Newton迭代格式：或者取初值进行计算：x0=0.5x1=0.57102043x2=0.56715556x3=0.56714329精度为10-5。如果用一般迭代法xk+1=e-xk

,k=0,1,2,…，要达到同样精度，则需要迭代22次。4/2/202332例7

求的值(a>0).例如，对于

解：利用迭顿迭代法，令得计算格式则有xn=a再令f(x)=xn-a,得到f’(x)=nxn-1,代入牛顿迭代格式将n=2

代入上式得到：如果分别取a=2,a=3,a=5,并要求精度为ε=10-5，计算结果如下：4/2/202333a=2,ε=10-5

a=3,ε=10-5

a=5,ε=10-5

x0=1.00000000x1=1.50000000x2=1.41666667x3=1.41421569x4=1.41421356x5=1.41421356x0=1.00000000x1=2.00000000x2=1.75000000x3=1.73214285x4=1.73205081x5=1.73205080x0=1.00000000x1=3.00000000x2=2.33333333x3=2.23809523x4=2.23606889x5=2.23606797x6=2.236067974/2/202334

§4弦截法（割线法）一、双点弦截法对于牛顿迭代法当f’(x)不存在时，可以用作近似代替,得到并称其为双点弦截法。4/2/202335其几何几何解释为：令y=0,解得：x0xyoabx*x1x2(x0,f(x0))(x1,f(x1))x3在曲线上任取两点(x0,f(x0))、(x1,f(x1))，作割线，方程为再过两点(x1,f(x1))、(x2,f(x2))作割线，得割线方程：再令y=0,解得：以此类推，最后得到的近似解x0,x1,x2,…越来越靠近x*。4/2/202336二、单点弦截法x0xyoabx*x1x2(x0,f(x0))(x1,f(x1))x3在曲线上过两点(x0,f(x0))、(x1,f(x1))作割线，方程为令y=0,解得：再过两点(x0,f(x0))、(x2,f(x2))作割线得割线方程：再令y=0,解得：x4以此类推，可以得到单点弦截公式：4/2/202337总结二分法：根的存在唯一性、计算公式及精度控制一般迭代法：迭代法的构造、收敛性和局部收敛性定理、收敛阶、精度控制牛顿迭代法：迭代公式、局部收性与收敛阶、几何意义弦截法：双点弦截公式与单点弦截公式、几何意义、收敛性与收敛阶算法的程序：各个算法的程序设计4/2/202338练习1用牛顿迭代法求方程在附近的近似根，误差不超过10-3。牛顿迭代法的迭代函数为：相应的matlab代码为：clear;x=0.5;fori=1:3x=x-(x^3+x^2+x-1)/(3*x^2+2x+1)end可算得迭代数列的前三项0.5455,0.5437,0.5437。经三次迭代就大大超了精度4/2/202339练习2用牛顿迭代法求方程的近似正实根，由此建立一种求平方根的计算方法。由计算可知，迭代格式为，在实验12的练习4中已经进行了讨论。练习3

用牛顿迭代法求方程的正根。牛顿迭代法的迭代函数为如果取初值为，相应的MATLAB代码为4/2/202340clearx=0;fori=1:6x=x-(x*exp(x)-1)/((x+1)*exp(x))end可得迭代数列前6项为1.0000，0.6839，0.57750.5672，0.5671，0.5671，说明迭代实收敛的。如果取初值为10，相应的MATLAB代码为clear;x=10.0;fori=1:20x=x-(x*exp(x)-1)/((x+1)*exp(x))y(i)=x;End4/2/202341可算得迭代数列的前20项为9.0909，8.19007.2989，6.4194，5.5544，4.7076，3.8844，3.0933，2.34871.6759，1.1195，0.7453，0.59020.5676，0.5671，0.5671，0.5671，0.5671，0.5671，0.5671,说明迭代是收敛的。如果取初值或，可算得迭代数列是发散的，根据函数图形分析原因。练习4

求方程在附近的根，精确到10-5先直接使用的迭代格式，相应的MATLAB代码为n=0;esp=1.05e-5;x=0.5;whileabs(x-exp(-x))>espx=exp(-x);n=n+1;endx,n