第8章 非线性方程求解

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

§2迭代法

2.1迭代格式

2.2收敛性条件

2.3迭代法的收敛阶

§3牛顿迭代法

3.1迭代格式

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

xyoab*x*这种方程往往无法求得其精确解，只能通过数值方法求其近似解。这里我们将介绍两种数值方法：非线性方程求根是我们经常碰到的问题，例如：(1).二分法;(2).迭代法：一般迭代法、牛顿迭代法、弦截法.则x*称为f(x)的m重零点（根）。§1二分法对于

f(x)=0

（8.1）

设

f(x)∈C[a,b]

，且

f(a)f(b)<0

，则知（8.1）在(a,b)

内至少有一实根x*

。如果在(a,b)内有(8.1)的唯一实根x*

：则可以用二分法进行求解，求解的步骤如下：xyoab*x*Step1

计算f(a)、f(b)

及

若令a1=a,若则x*∈[a1,b1]则若b1=b,令则x*∈[a1,b1]x*abx*ababx*a1b1a1b1a=a0,b=b0stepk：计算f(ak-1)、f(bk-1)

及

若则

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

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

2）令b0=ba=a0a1b1a2b2

例8.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我们采用二分法进行计算，每一次的计算结果由下表给出k

ak

bk

xk=(ak+bk)/2

f(xk)0

1.0

1.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.3242这里的a=1.0,b=1.5

,

取ε=0.005，代入上面的不等式即

2k+1

>102取k=6,也就是计算6次就可以达到满足精度要求的近似解.另外，我们也可以提前确定计算次数，这时利用关系式

—>

(k+1)lg

2

>2二分法优点：算法简单；f(x)连续即可，常用来定根的范围；缺点：只能求单实根；收敛速度慢。§2、一般迭代解法一、迭代格式的构造对于f(x)=0(8.1)将其改写为x=g(x)(8.2)取适当的初值

x0

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

的迭代法，g(x)

称为迭代函数。xk+1=g(xk

),k=0,1,2,…(8.3)设x*

为

(8.1)

精确解，如果，则称迭代解{xk

}

收敛，否则称为发散。简单迭代法迭代函数g(x)的不动点简单迭代法也称为单点迭代法或不动点迭代法例8.2

用简单迭代法求x3-2x-3=0

在[1,2]内的根。解：容易验证方程[1,2]在

内只有单根。(1)若改写原方程为得迭代格式取初始值x0=1.9

，由上面的迭代格式求得近似解如下：这里……………由于x8、x9相当接近，故可取x*≈x8=1.89328920。(2)如果将原方程x3-2x-3=0改为

仍取初值x0=1.9

，得迭代格式如下：x1=1.8945647x2=1.89352114x8=1.89328920x9=1.89328920得到的近似解是不收敛的，越来越发散。

由此可见:迭代函数

g(x)

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

求得近似解为：x0=1.900x1=1.930x2=2.095x3=3.098x4=13.37那么，思考如下问题：(1)如何选取合适的迭代函数g(x)

？(2)迭代函数g(x)应满足什么条件，序列{xk}才会收敛(即迭代格式xk+1=g(xk)才会收敛)呢？下面我们将讨论这一问题。

二、收敛性条件定理8.1

设迭代函数g(x)

满足条件由方程f(x)=0

产生的迭代格式:xk+1=g(xk

),k=0,1,2,…(8.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]

;则有以下结论：全局收敛定理连续性映内性压缩性1）方程f(x)=0

或者x=g(x)

在[a,b]

上有唯一解x*.3）x*有误差估计式

2）对于任意的x0∈[a,b]

迭代格式xk+1=g(xk)，k=0,1,2…收敛,而且：或4）解存在惟一性收敛性事先误差估计事后误差估计与收敛速度有关无穷小之比

收敛性只与迭代函数g(x)有关；收敛速度主要取决于L，越小收敛越快；终止条件可用事先或事后误差确定。例8.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,…收敛.下面确定满足精度要求ε=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.60653ixiixi00.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-6关于解的唯一性的判别，还可以借助于根的存在性定理。我们用另一种方法完成上面的例子。再由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,1]

其它步骤与前面的相同，可以完成问题的解决。当含根区间较大时，全局收敛定理条件不易满足，可在根的邻域考虑在根附近收敛，远处发散在实际应用中，通常已经知道方程f(x)=0

根的x*在在某点x0

附近存在，希望采用迭代法求出足够精确的近似解。这时，在使用迭代法时，总是在根x*的邻域内考虑。上面定理中的第二个条件|g’(x)|≤L<1

在较大的区间内有可能不成立，但在根的附近是成立的。由此给出下面局部收敛性定理

定理8.2(迭代法局部收敛性定理)：如果方程x=g(x)

满足条件：1).g(x)在方程的解x*的邻域内连续可微；

2).|g’(x*)|<1(由于g(x)在x*的邻域内连续可微，故一定存在L使得|g’(x*)|≤L<1

，且在x*附近|g’

(x*)|≤L

)；则定理8.1的结论成立。

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

∞时则称迭代法是p

阶收敛的，当p=1

且0<c<1时称为线性收敛，当p=2

时称为平方收敛或二阶收敛。p=1,c=1/2与二分法差不多例如，对于迭代解xk+1=g(xk)与精确解x*=g(x*)两式相减，得到如果则迭代格式xk+1=g(xk)

线性收敛（收敛时至少线性）。且线性收敛二阶收敛例8.4

如果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*之间，这时由于

|g’(x*)|=0<1,所以迭代格式xk+1=g(xk)，k=0,1,2,…收敛，且具有p阶收敛速度。上面讨论的迭代法也称作一般迭代法，下面我们再介绍两种收敛阶较高的迭代法——牛顿迭代法和弦截法。§3、牛顿迭代法一、迭代格式由f(x)=0

改变为x=g(x)

往往只是线性收敛的，采用f(x)

近似代替可得出高阶收敛方法。设x*

为

f(x)=0

的解，xk

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

方程求根的牛顿迭代法为又称为切线法，可以通过其几何意义明确这一称呼，如下图所示：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*。

二、收敛性与收敛阶对于牛顿迭代格法迭代函数为导数为在精确解x*

处,由f(x*)=0得到|g’(x*)|=0=L<1

由局部收敛性知：牛顿法局部收敛（单根附近至少二阶）。得到：关于收敛阶，由牛顿迭代格式再由Taylor展式得到：两式相减得：即：当k∞

时xk

x*,ξx*这时如果则Newton迭代法具有二阶收敛速度（重根线性收敛）

。例8.5

用牛顿迭代法求方程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

次。x22=0.56714303例8.6

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

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

代入牛顿迭代格式将n=2

代入上式得到：如果分别取a=2,a=3,a=5,并要求精度为ε=10-5，计算结果如下：a=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.23606797简化牛顿法（平行弦法：线性收敛）；拟牛顿法

§4弦截法（割线法）一、双点弦截法对于牛顿迭代法当f

’(x)不存在时，可以用作近似代替,得到并称其为双点弦截法。其几何几何解释为：在曲线上任取两点(x0,f(x0))、(x1

,f(x1))，作割线，方程为多点迭代法令y=0,解得：再过两点(x1,f(x1))、(x2,f(x2))作割线，得割线方程：再令y=0,解得：以此类推，最后得到的近似解x0,x1

,x2

,…越来越靠近x*。x0xyoabx*x1x2(x0,f(x0))(x1,f(x1))x3x4yx1xoabx*x0x2(x1,f(x1))x3(x0,f(x0))(x2,f(x2))

二、单点弦截法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以此类推，可以得到单点弦截公