第6章 - 非线性方程求根方法

第六章非线性方程数值解法基础知识非线性方程的二分法解x=g(x)的简单迭代法解f(x)=0的Newton迭代法1§1基础知识一、非线性方程、非线性方程组非线性方程组包括：

高次方程(组),即代数方程(组)超越方程(组)二、非线性方程(组)求解的特点产生的背景:许多科学理论与工程技术都可化为非线性方程(组)求解的特点：无求解公式，无直接解法，难求得精确解。例:

超越方程ex+cosx

=1没有一定的解法。又例如对于大于等于五次的代数方程，无解析根表达公式，只能使用数值方法对于实际问题进行求解。2原理由连续函数介值定理,则至少存在某个x*(a,b)，使得f(x*)=0,即[a,b]内至少有方程的一个根,称[a,b]为f(x)的一个含根区间，且考虑非线性方程：

f(x)=0如果3从一个初始近似值出发,重复某种计算过程来不断改进近似解，有限次改进后,计算出一个满足误差要求的近似解，这种求解方法称为迭代法。求解的方法：间接法，也即迭代法。求解的要求：

收敛计算效率(快慢)

数值稳定性(考虑计算机的舍入误差)初始值好迭代公式合适(好的)定义：间接法(迭代法):4根的存在性：方程是否有根？如果有根，有几个根？根的隔离：确定根所在的区间，使方程在这个小区间内有且仅有一个根，这一过程称为根的隔离，完成根的隔离，就可得到方程的各个根的近似值。根的精确化：已知一个根的粗略近似值后，将近似解逐步精确化，直到满足给定精度为止。

关于根的存在性是纯数学问题，不详细介绍，可查阅有关代数学内容。求方程根的近似解，一般有下列几个问题：从区间[a,b]的左端点a出发，按选定的步长h一步步向右搜索，若:则区间[a+jh,a+(j+1)h]内必有根。搜索过程也可以从

b开始，这时应取步长h<0。

逐步搜索：介值定理5定义序列的收敛性三、基本定义则称点列收敛于点X*记为或当6一、原理把含根区间不断缩短，使含根区间之间含有一个满足误差要求的近似解。§2二分法7找中点：令计算：f0=f(x0)(即中点函数值)生成含根区间二、具体过程(方法)令若f(x0)=0,则x*=x0,若f(x0)·f(a0)>0,取a1=x0,b1=b0,若f(x0)·f(a0)<0,取a1=a0,b1=x08生成含根区间[a1,b1]满足:以[a1,b1]取代[a0,b0],重复以上过程，得[a2,b2]…一般的,设已得含根区间[ai,bi]，i=0,1,…,k,满足：(2)9对区间[ak,bk]，找中点：令计算：fk=f(xk)(中点函数值)生成含根区间:若f(xk)=0,则x*=xk,如图若f(xk)·f(ak)>0,取ak+1=xk,bk+1=bk,如图若f(xk)·f(ak)<0,取ak+1=ak,bk+1=xk，如图生成含根区间[ak+1,bk+1],满足(2)式{ak}单增，有上界x*,{bk}单减，有下界x*10所以，近似解序列其极限为即序列收敛于f(x)=0的一个根x*即且f(x*)=0说明:只要就有此时可计算或估计二分法执行的次数k.事实上,由两边取对数对于给定的误差界可取11收敛速度不快,仅与公比为1/2的等比级数的收敛速度相同。即是线性收敛的。不能用于求偶重根、复根；不能推广到多元方程组求解；不能求出所有根(即有可能漏根)。对函数要求低(只要连续,在两个端点异号)。二分法是收敛的。优点:例如图该点可求出,但漏掉了四个点缺点:

12试用二分法求方程：f(x)=x3+10x-20=0的唯一实根，要求误差不超过Nanbnxnf(xn)0121.5-1.62511.521.752.85937521.51.751.6250.5410156331.51.6251.5625-0.5603027341.56251.6251.59375-0.0143127451.593751.6251.6093750.2621727061.593751.60937501.60156250.1236367271.593751.60156251.59765620.0545888581.593751.59765621.59570310.0201197991.593751.59570311.59472660.00289896101.593751.59472661.5942383-0.00570803111.59423831.59472661.5944824-0.00140482121.59448241.59472661.59460450.00074700131.59448241.59460451.5945435-0.00032893141.59454361.59460461.5945741

例13§3解x=g(x)的简单迭代法一、简单迭代法(1)先将f(x)=0化为等价方程(3.2)式称为简单迭代法或单点迭代法或逐次逼近法。g(x)称为迭代函数。思想：(2)从某初始值x0出发,作序列{xk}若{xk}收敛于x*且g(x)连续，则x*是f(x)=0的根。14说明:由f(x)=0化成等价方程x=g(x)的方法有很多种。如何选取迭代函数g(x)？

g(x)满足什么条件，迭代序列收敛？收敛速度是多少？如何加速迭代序列的收敛速度？问题:15解改写原方程为等价方程求方程x3-2x-3=0在[1,2]内的根.例

建立迭代格式如果取初值x0=1.9,计算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.89329069678910…1.893289471.893289251.893289211.893289201.89328920……16问题:定义4若迭代序列{xk}保持有界,且全在g(x)定义域内，则简单迭代法则简单迭代法(3.2)称为收敛的。由xk+1=g(xk)，求xk+1，但xk

是否位于定义域上？称为适定的；若进一步有17当迭代(3.2)收敛时,极限点x*又是g(x)的连续点,则g(x)把定义域的每个x

映成了g(x)，因此，(3.2)的解也称为g(x)的不动点。换言之，g(x)是映射，若x*满足注:

适定是收敛必要条件，即不适定则一定不收敛。即x*是(3.2)的解。称x*是g(x)的不动点。18说明：几何意义x=g(x)从初始点x0出发，沿直线x=x0走到曲线y=g

(x)，得点(x0,

g(x0))，再沿直线y=g(x0)走到直线y=x，交点为(x1,g(x1))，如此继续下去，越来越接近点(x*,x*)。19xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p120二、收敛定理定理3(压缩不动点定理或压缩映象定理)若迭代函数g(x)满足使有则有以下结论：

x=g(x)在[a,b]上有唯一解x*;对有误差估计214.若存在，则证明：由介值定理，h(x)在[a,b]上至少存在一个根x*令唯一性从而设y*是在[a,b]上另一根，则1.解的唯一存在性22由条件(1)知{xk}适定，那么2.序列收敛性3.误差估计23＃4.导数利用导数的定义(3.4)式的条件较难验证，常采用导数来代替。即有推论1：推论1定理3中(3.4)可用下式替代24在[-1,1]上不满足定理3的条件2，实际上x=0是解，只要x0取在0的附近，把(-1,1)缩小使得3.定理条件非必要条件，可将[a,b]缩小，定义局部收敛性：若在x*

的某领域B

={x||xx*|}，有gC1[a,b]且|g’(x*)|<1，则由x0B

开始的迭代收敛。即调整初值可得到收敛的结果。例如注：从结论3可知，L越小收敛越快，L叫做渐进收敛因子。从误差估计式可见,对任一>0,要使|xk-x*|<,只要

25定理4（局部收敛定理）有且有误差估计：实际计算中往往只在根x*邻近讨论，有局部收敛定理4：若g(x)在不动点x*的δ邻域满足则

x0

[x*-δ,x*+δ]

，由xk+1=g(xk)产生的序列{xk}收敛于x*。26说明：定理中的条件是充分但非必要条件。见定理3注。证明：＃27推论2(3.6)式的条件较难验证,常采用导数来代替。即有推论2：若g(x)在不动点x*处可微，且|g’(x*)|<1,则存在δ>0,则

x0

[x*-δ,x*+δ]

，由xk+1=g(xk)产生的序列{xk}收敛于x*。且28证明：任取由知存在，成立即由定理4得证。＃29求方程xex-1=0在0.5附近的根,精度要求=10-3.解可以验证方程xex-1=0在区间[0.5,0.6]内仅有一个根.例30改写方程为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.0006531所以,取近似根x10=0.56691满足精度要求.如果精度要求为=10-5,则由可知,需要迭代20次.32例用简单迭代法求的近似值。解：设则近似值计算转化为求方程x(x+2)=1的正根，

取作为的近似值，得：等价方程：以x0=0为初始值近似得到迭代序列：33取区间为在上满足定理3。故迭代法收敛。即1.4142157就是近似值。下证序列收敛于只要证满足定理3，又34若收敛于X*，若存在常数C，使得三、简单迭代法的收敛阶定义收敛阶p=1时,称为线性收敛;收敛阶p>1时,称为超收敛;收敛阶p=2

时,称为平方收敛序列的收敛阶数越高,收敛速度越快特别:35一般的，简单迭代是线性收敛，但在一定条件下，迭代是高阶收敛的。有定理5：定理5（高阶收敛定理）则简单迭代法局部收敛，且收敛阶为m。分析：已知条件有各阶导数均为0,因此用泰勒公式展开。若g(x)在不动点x*

邻近有m阶的连续导数，且满足36＃证明：由推论2，简单迭代法是局部收敛的。即37四、迭代函数g(x)的选取方法选取的g(x)必须满足:两方程同解；迭代序列收敛于其根。两种选g(x)的方法:使得设λ为正常数，试用g(x)≡x-λf(x)作为迭代函数，选择λ，使得成立.，且存在常数m，M对于f(x)=0的迭代格式1.假设在含根区间[a,b]上存在(*)38作为迭代函数.则简单迭代法收敛于f(x)=0的根x*。特别,使得(牛顿迭代法的变形)则(*)式成立。故可用392.若求得原方程的根x*。则前述方法不能使用。此时，若g(x)的反函数x=t(x)容易求出，可用t(x)作为迭代函数。因为x=g(x)与x=t(x)同根。于是，可用迭代格式40例

求在上的根.解:在上有根.方程与等价.但故不能用作为迭代函数.的反函数的导数在[1,2]上满足所以可用t(x)作迭代函数进行求根。41五、迭代的加速方法(Aitken加速)原理对于线性收敛数列,有于是整理化简得加速收敛序列42结合不动点迭代格式，有xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)43六、迭代结束条件1)根据实际问题需要定出解的误差界由定出迭代次数2)用相邻两次近似值有多少位有效数字相同,判断是否停机.注:编程序时,要注意结束条件.定出的k往往不准确,因为计算中有舍入误差，故使迭代次数比计算的大。44§4解f(x)=0的Newton迭代法原理:

非线性方程局部线性化(Taylor展开)单根附近具有较高的收敛速度(平方收敛)一、Newton迭代公式1公式:设f(x)二次连续可导，xk

是方程的第k次近似解则f(x)在点xk的Taylor展开式：其中ξ(x,xk)。忽略高阶小量，取前端的线性部分(线性主部)，用其近似f(x)，有45Newton迭代公式:说明:推导过程中是用f(x)的泰勒展开式的线性部分作为f(x)的近似值,因此说Newton法是一个逐次线性化方法。把作为第k+1次近似解，即得(4.1)462几何意义y=f(x)图象如图，xk是f(x)=0的k次近似，曲线上对应的点为(xk,f(xk))，过该点做y=f(x)的切线Lk，交x轴于点xk+1，Lk方程：用以近似曲线y=f(x)，则Lk与x轴的交点xk+1作为f(x)=0的第k+1次近似解。即由(4.2)式令y=0得此即Newton法的迭代公式，因此Newton法也称为切线法。xyox0y=(x)x1x247定理10（Newton法局部二阶收敛性）如果f(x)在解x*邻近二次连续可导,且则存在δ>0，只要Newton序列二阶收敛于x*,即二、Newton法收敛性1收敛定理(4.3)48证明：于是有49定理11（Newton法非局部收敛定理）且满足:在上不变号；在上不取零。则对满足Newton序列单调二阶收敛于f(x)=0在[a,b]上的唯一解x*.50例用Newton法求解解:首先可以判断解在(0,1)内.(恒正)(不变号)则Newton迭代序列单调二阶收敛到方程在(0,1)内的唯一根，取初始值x0=1,计算结果如表：kxkf(xk)f’(xk)010.4596976941.84147098410.7503638670.0189230731.68190495220.739112890.0000464541.67363254430.7390851330又f(x)=x–cos

x在(0,1)有51从适当的x0,x1生成迭代序列的方法称为正割法。1正割法(割线法)三、Newton法的推广与改进采用迭代格式割线法也可看作以(xn-1，f(xn-1))，(xn，f(xn))作线性插值，而以此插值多项式近似f(x)，以其零点近似f(x)的零点。52即，用f(x)关于xk-1,xk的线性插值函数来近似函数f(x)。取L(x)=0的根作为f(x)=0的新近似根,即x*的k+1次近似oxyy=(x)x0x1x2x3几何意义来近似原曲线并用割线与x轴的交点xk+1

，近似方程的根x*。用连接(xk-1,f(xk-1)),(xk,f(xk))两点的直线53注：若(x)在根x*附近二次连续可微,且f’(x*)≠0,可以证明割线法是收敛的,且有割线法收敛的阶为(超线性收敛)xk,xk-1可以在x*的同侧，也可以在x*的两侧，割线与x轴的交点xk+1比xk，xk-1都更接近真解。542计算重根的Newton迭代法事实上，设x*是f(x)=0的m(m>1)重根,即由于的单根.称之为带参数m的Newton迭代法,它是求方程(x)=0m重根的具有平方收敛的迭代法.可见,x*恰是方程应用Newton迭代法可得:55再看函数:可见,x*恰是方程u(x)=0的单根,应用Newton迭代法有即为求方程(x)=0重根的具有平方收敛的迭代法,而且不需知道根的重数.u(x)=0的单根即为f(x)=0的重根.且该迭代是二阶收敛的.(定理10)(4.5)56例

利用Newton迭代法求方程oxy246810y=f(x)解：y=(x)的图形为可见,方程在x=4附近有一个重根,在x=7附近有一单根.的正实根利用Newton迭代法57求方程的单根,取初值x0=7,精度

=10-6,计算可得:

x4=7.34846923,x5=7.348469229,|x5-x4|=0.000000001可见,迭代5次就得到满足精度的解x5=7.348469229利用求重根的Newton迭代法(4.5)求重根,取x0=4,计算可得x3=4.300000,x4=4.300000,|x4-x3|=0.000000006然而若用一般的Newton迭代法(4.5)求重根,取x0=4,虽然也收敛,却需要迭代19次才能得到满足精度要求的解.可见,迭代4次就得到满足精度的解x4=4.300000.利用带参数m=2的Newton迭代法,取x0=4可得x2=4.2999898.58四、Newton下山法(修正的Newton法)牛顿法收敛速度快，但对初值要求苛刻。在实际应用中不容易确定，有时往往由于初值选取不当而使迭代不收敛.Newton下山法是