解非线性方程的迭代法

解非线性方程的迭代法设

(x)在区间[a,b]上连续且(a)(b)<0,根据连续函数的介值定理,区间[a,b]上必有方程(x)=0的根,称[a,b]为方程(x)=0的有根区间.ab

xy=(x)x0x1y0设

(x)在区间[a,b]上连续且(a)(b)<0.二分法的基本思想是：将有根区间逐次分半，每次保留新的有根区间，其长度减少一半，这样有根区间长度将逐渐缩小，直至缩为一点，此点即为方程的根。a1=ab1=x0a2=x1b2=b1第2页,共32页，2024年2月25日，星期天得到新的有根区间[a1,b1],下面说明二分法的数学计算过程。0ab

yxy=(x)记a0=a,b0=b,计算若(a0)(x0)<0,取a1=a0,b1=x0;若(a0)(x0)>0,取a1=x0,b1=b0而且有根区间[a1,b1]长度是有根区间[a0,b0]长度的一半；x0再对有根区间[a1,b1]重复上面运算,即:计算若(a1)(x1)<0,取a2=a1,b2=x1;若(a1)(x1)>0,取a2=x1,b2=b1,得到新的有根区间[a2,b2].而且有根区间x1[a2,b2]长度是有根区间[a1,b1]长度的一半.一直进行下去,直到求出有根区间[ak,bk].第3页,共32页，2024年2月25日，星期天再计算当|bk-ak|<时停止计算，取xk。可见,k趋向无穷大时,xk收敛于

.而且,若要|xk-|<,只要此时可取近似根xk.在计算过程中,若出现|(xk)|<,或bk-ak<，则可取xk作为方程(x)=0的近似根,终止运算.例1用二分法求x3+4x-7=0在区间[1,2]内根的近似值,并估计误差.显然有第4页,共32页，2024年2月25日，星期天

解这里

(x)=x3+4x-7，(1)(2)=-18<0,而且(x)=3x2+4>0,所以(x)=0在[1,2]区间有唯一根.取x0=1.5,由于

(x0)=2.375,得新有根区间[1,1.5],x1=1.25,由于

(x1)=-0.0468,得新有根区间[1.25,1.5],x2=1.375,由于

(x2)=1.0996,得新有根区间[1.25,1.375],x3=1.3125,由于

(x3)=0.511,得新有根区间[1.25,1.3125],

………………….x9=1.254882813,得有根区间[1.254882813,1.255859375],x10=1.255371094,(x10)=-0.000105285取

x10=1.255371094作为方程根的近似值,且有第5页,共32页，2024年2月25日，星期天只需k>5ln210-115.61.即需取k=16,x16.如果取精度

=10-5,则要使二分法要求函数在区间[a，b]上连续，且在区间两端点函数值符号相反，二分法运算简便、可靠、易于在计算机上实现。但是，若方程

(x)=0在区间[a，b]上根多于1个时，也只能求出其中的一个根。另外，若方程(x)=0在区间[a，b]有重根时，也未必满足(a)(b)<0.而且由于二分法收敛的速度不是很快,一般不单独使用,而多用于为其他方法提供一个比较好的初始近似值.ab

(x)第6页,共32页，2024年2月25日，星期天

§2.1简单迭代法的一般形式§2简单迭代法首先把方程

(x)=0改写成等价(同解)形式

x=(x)(4.2)得到迭代序列{xk},如果xk,对(4.3)取极限，则有=(),即是方程

(x)=0的根.取一个适当的初始值x0,然后进行迭代计算

xk+1=(xk),k=0,1,2,…(4.3)这种求方程根的方法称为简单迭代法.其中

(x)称为迭代函数

,式(4.3)称为迭代格式.若迭代序列{xk}收敛,

则称简单迭代法是收敛的.第7页,共32页，2024年2月25日，星期天

解由于

(1)(2)=-4<0,则方程在[1,2]内有根。改写原方程为等价方程。求方程x3-2x-3=0在[1,2]内的根.例2

如果取初值x0=1.9,迭代计算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.89329069678910…1.893289471.893289251.893289211.893289201.89328920……建立迭代格式：第8页,共32页，2024年2月25日，星期天由计算结果有，x10=x9，因此可取

x10=1.89328920.

定义4.1

设

(x)为定义在区间I上的函数,且对任何xI,均有(x)I,则称(x)为I到自身上的映射.方程也可改写成x=(x3-3)/2,建立迭代格式

xk+1=(xk3-3)/2,k=0,1,2,…仍取初值x0=1.9,则有

x1=1.9295,x2=2.0917,x3=3.0760,x4=13.0529可见,xk,此迭代格式是发散的.§2.2简单迭代法的收敛条件

定义4.2

设

(x)为I到自身上的映射,且存在0<L<1,使对任何x1,x2

I,有|(x2)-(x1)|L|x2-x1|,则称(x)为I上的压缩映射,L称为Lipschitz常数.第9页,共32页，2024年2月25日，星期天显然，压缩映射(x)是I上连续函数。反之不然,如(x)=x.

定理4.2

若

(x)为I到自身上的映射,且(x)C1(I),|(x)|L<1,则(x)为I上的压缩映射.

证对任意x1,x2I,利用中值定理，可有

|(x2)-(x1)|=|()||x2-x1|L|x2-x1|

定义4.3

若

(x)为I到自身上的映射,且I满足,=(),则称为(x)的不动点.(方程

x=(x)的解）

定理4.3

若

(x)为I上的压缩映射,则(x)在I上存在唯一的一个不动点,且对任何x0I,由迭代格式

xk+1=(xk),k=0,1,2,…产生的序列{xk}收敛于(x)的不动点.第10页,共32页，2024年2月25日，星期天

证不妨设I=[a,b],作函数

(x)=(x)-x,由于x[a,b]时,(x)[a,b],则(a)=(a)-a0,(b)=(b)-b0,由(x)的连续性,必存在I,使()=()-=0,即=(),就是(x)的不动点.

唯一性：若

,I均为(x)的不动点,利用压缩条件有

|-|=|()-()|L|-|<|-|所以只能=,即(x)在I上仅有一个不动点.收敛性：对任意x0I,有x1=(x0)I,递推得{xk}I。设是(x)的不动点,则由xk+1=(xk)，=()，得到

|xk+1-|=|(xk)-()|L|xk-|L2|xk-1-|…Lk+1|x0-|因L<1,所以xk,k.第11页,共32页，2024年2月25日，星期天

推论

若

(x)C1[a,b],且满足

1.a(x)b,x[a,b];2.|(x)|L<1,x[a,b].则迭代格式xk+1=(xk),k=0,1,2,…,x0[a,b]都收敛于方程x=(x)在区间[a,b]的唯一根.在例2中，对x3-2x-3=0，x

[1,2],建立了两种迭代格式:xk+1=(xk3-3)/2,k=0,1,2,…,(x)=(x3-3)/2对第1种可验证：|(x)|<2/3<1,x

[1,2],所以迭代收敛；对第2种可有：|(x)|=3x2/2>1,x

[1,2],所以不能保证收敛。第12页,共32页，2024年2月25日，星期天实际上,由连续性知,存在>0,使对任何xI=[-,+]都有|(x)|L<1.这种收敛称为局部收敛，它要求初值x0充分靠近根。§2.3简单迭代法的误差分析与收敛阶定理4.4

若

=(),(x)在附近具有一阶连续导数,且|()|<1,则存在>0,当x0I=[-,+]时,有

(1)由迭代xk+1=(xk)产生的迭代序列xkI;

(3)

是I上(x)的唯一不动点.

定理4.5

若

(x)为I上压缩映射,则x0I,由迭代

xk+1=(xk),k=0,1,2,…，产生的迭代序列xk

满足估计:第13页,共32页，2024年2月25日，星期天

证由xk+1=(xk),=(),得到

|xk+1-xk|=|(xk)-(xk-1)|L|xk-xk-1||xk+1-|=|(xk)-()|L|xk-|因此|xk-

|=|xk-xk+1+xk+1-||xk+1-xk|+|xk+1-|L|xk-xk-1|+L|xk-|由误差估计式可见,对任一

>0,要使|xk-|<,只要第14页,共32页，2024年2月25日，星期天

求方程xex-1=0在0.5附近的根,精度要求

=10-3.

解可以验证方程xex-1=0在区间[0.5,0.6]内仅有一个根.例3改写方程为x=e-x,建立迭代格式由于(x)=e-x,在[0.5,0.6]上有|(x)|e-0.50.6<1.所以迭代法收敛.取初值x0=0.5,计算得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065第15页,共32页，2024年2月25日，星期天所以,取近似根

x10=0.56691满足精度要求.如果精度要求为=10-5,则由可知,需要迭代20次.如果对方程xex-1=0，建立等价形式：x=-lnx,和迭代格式：xk+1=-lnxk，k=0,1,…,此时迭代函数

(x)=-lnx，|(x)|=|1/x|>1,x

[0.5,0.6].则此迭代不收敛。第16页,共32页，2024年2月25日，星期天

定义4.4

设迭代序列

xk

收敛于,如果存在正实数p和正常数C,使得或|xk+1-|C|xk-|p,k>>1则称序列

xk

是p阶收敛的,称p是收敛阶,C是渐近误差常数.

p=1称为线性收敛;p>1称超线性收敛;p=2称平方收敛.对简单迭代法xk+1=(xk),由于

|xk+1-|=|(xk)-()|=|(k)||xk-|那么,当()0时,有

p反映了收敛速度，当|xk-|时，可有|xk+1-|Cp。第17页,共32页，2024年2月25日，星期天于是因此,当

(x)满足条件(4.4)时，简单迭代法是m阶收敛的.所以,当()0时,简单迭代法是线性收敛的.设

()=()=…=(m-1)()=0,,(m)()0,

m>1(4.4)

|xk+1-|=|(xk)-()|所以下面介绍Aitken加速算法，此方法可对线性收敛的简单迭代法起到加速作用，而且可应用于其它数值方法中。此时第18页,共32页，2024年2月25日，星期天假设

(1)(2)，则有由于

xk+1-=(1)(xk-)

xk+2-=(2)(xk+1-)即

(xk+1-)2(xk-)(xk+2-)

xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2

解得第19页,共32页，2024年2月25日，星期天则序列注意,如果第k步发生zk-2yk+xk=0,就终止计算,取

xk.如果记要比序列{xk}更快地收敛于

,可构造如下的Aitken加速算法:例4分别用简单迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)第20页,共32页，2024年2月25日，星期天取x0=/2,计算结果如下k简单迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078第21页,共32页，2024年2月25日，星期天

Newton迭代法是求非线性方程根的最重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求解方程的重根、复根及非线性方程组.§3Newton迭代法

§3.1Newton迭代公式设(x)在有根区间[a,b]上二阶连续可微,由初始近似x0出发，假设第k步迭代值xk已知，如何确定xk+1?,因为利用()=0且舍去高阶小项(-xk)2，则得到

0(xk)+(xk)(-xk)解得xk-(xk)/(xk)≌xk+1第22页,共32页，2024年2月25日，星期天从而得到迭代公式：迭代格式(4.5)称为Newton迭代法.一般要求在附近

(x)0。

xyox0y=(x)x1x2例如，由x0出发，切线方程是：

y-(x0)=(x0)(x-x0)或y=(x0)+(x0)(x-x0)，它与x轴(y=0)的交点是

x1=x0-(x0)/(x0)Newton迭代法的几何意义是：用曲线上点(xk,(xk))处切线与x轴的交点作为新的迭代值xk+1。第23页,共32页，2024年2月25日，星期天

Newton迭代法xK+1=xk-(xk)/(xk)相当于取迭代函数所以Newton迭代法也叫切线法.

§3.2Newton迭代法的收敛性的简单迭代法.因为如果是(x)=0的单根,即()=0,但()0,则有()=0,从而可知Newton迭代法是局部收敛的，且至少为二阶收敛。下面进一步讨论Newton迭代法收敛性。因为所以第24页,共32页，2024年2月25日，星期天于是有可见,Newton迭代法当

()≠0是平方收敛的.记M2=max|(x)|,m1=min|(x)|.则有

|xk+1-|C|xk-|2因此

C|xk+1-|(C|xk-|)2

(C|xk-1-|)4可见,当C|x0-|<1,即|x0-|<2m1/M2时,Newton迭代法是收敛的.第25页,共32页，2024年2月25日，星期天

设

(x)在单根附近具有二阶连续导数,在邻域(x)0。则对充分接近的初值x0,Newton迭代法产生的序列xk

收敛于,并且定理4.6取x0=0.5,计算结果如下:

例5

用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求

=10-5.

解

Newton迭代格式为第26页,共32页，2024年2月25日，星期天kxkƒ(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.00000000从结果可见,Newton迭代法迭代3次已获得精确到小数点后五位的近似解,迭代4次已获得精确到小数点后八位的近似解.与例3比较(20次)可见Newton迭代法收敛的确实快.§3.3Newton迭代法的变形1.简化Newton迭代法第27页,共32页，2024年2月25日，星期天为了简化计算

(xk),采用迭代格式称为简化Newton迭代法.oxyy=(x)

x0x1x2x3在区间I=[-,+]上,取M与(x)同号,且|M|>1/2max|(x)|时,简化Newton迭代法对x0I收敛.通常取M=(x0).简化Newton迭代法一般只具有线性收敛.

2.割线法将近似公式第28页,共32页，2024年2月25日，星期天oxyy=(x)

x0x1x2x3代入Newton迭代法中，得到迭代格式初值x0,x1取定，称为割线法.若

(x)在根附近二次连续可微,且()0,可以证明割线法是超线性收敛的,且有割线法收敛的阶为

3.计算重根的Newton迭代法第29页,共32页，2024年2月25日，星期天