数值分析课件 第二章2.2

数值分析第二章解非线性方程的数值方法一、二分法二、迭代法三、Newton法对给定方程f(x)=0,可以用各种方法转化成等价方程二、迭代法1迭代法的基本思想若x*是f(x)的根,即若,则有称x*为函数的一个不动点.设x0是一个近似解，可以构造序列迭代法(2.2)称为简单迭代法或单点迭代法.称函数为迭代函数.简单迭代法(2.2),若迭代序列{xk}保持有界,全在定义域内称为适定的;若进一步有称为是收敛的.若收敛，即存在x*使得则由

的连续性和可得x*=

(x*)，即x*是

的不动点，也就是f(x)的零点。kxk012345671.51.357211.330861.325881.324941.324761.324731.32472例求x3-x-1=0在1.5附近的根x*解xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=

(x)y=

(x)y=

(x)y=

(x)x0p0x1p1x0p0x1p1

x0p0x1p1

x0p0x1p1

x2

2收敛定理和误差估计定理1

设在[a,b]上有连续的一阶导数,且(1)有(2)则有(1)函数在[a,b]上存在唯一的不动点x*由迭代公式(2.2)得到的序列(2)都收敛到方程的根x*(3)(4)证明(1)先证明存在性,作函数由条件(1)可知由连续函数根的存在定理可知,必有使得h(x*)=0，即再证明唯一性,设也是一个解,即那么因为L<1,所以有(2)由条件(2)和Lagrange中值定理得因为L<1,所以当时,有(3)和(4)利用(2)的方法令即分别得定理1的几点说明(i)通常将条件(1)称为映内性；(ii)条件(2)也可以改为：存在常数L且0<L<1使得结论仍然成立,这个条件通常称为压缩性；(iii)结论(3)说明的误差大概是常数乘上Lk,但是一般L未知;(iv)结论(4)说明与有关因此得到迭代法的终止条件3一般迭代法的算法算法：(1)取初始点x0,最大迭代次数N和精度要求并置k=0；(2)计算(3)若则停止计算；(4)若k=N,则停止计算；否则k=k+1,转(2).4局部收敛定理迭代序列{xk}在区间[a,b]上的收敛性通常称为全局收敛性.实际应用只在不动点x*的邻近考察收敛性，称为局部收敛性.定义设有不动点x*,如果存在x*的某个邻域对任意的迭代(2.2)产生的序列且收敛到x*,则称(2.2)局部收敛.证明由连续函数的性质,存在x*的某个邻域对任意的有而根据定理1可以断定迭代过程(2.2)对任意初值均收敛.定理2若x*为迭代函数的不动点,在x*的某个邻域内有连续导数,且则迭代法(2.2)局部收敛.例只用四则运算不用开方求方程x2-3=0的根解kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123

׃

x0

x1

x2

x3

׃23987׃21.521.5׃21.751.734751.732631׃21.751.7321431.732051׃例设试讨论a的取值范围使迭代公式(2.2)局部收敛到解因为所以由定理2可知只需即所以当时,迭代公式收敛.例5迭代收敛的阶则称该迭代为r阶收敛.(C为常数)(1)当r=1时称为线性收敛，此时C<1；(2)

当r=2时称为二次收敛，或平方收敛；(3)当r=1,C=0时称为超线性收敛.二分法线性收敛;定义设迭代

收敛到的不动点x*.记ek=xk

x*，若不动点迭代中，若则线性收敛则迭代公式是p阶收敛的，且定理3

设迭代若在x*的某邻域内连续，且证明：

根据泰勒展开有6迭代加速若则迭代公式(2.2)只是线性收敛的取初始点x0,令那么由此得迭代公式如何求L?再令得到由此得Steffensen加速法Steffensen加速法是平方收敛的.三、Newton法1Newton法基本思想设xk是f(x)=0的近似根,将f(x)在xk一阶Taylor

展开:(

在xk和x之间)当

f‘(x)0时,即将非线性方程线性化于是xyx*xkxk+1Newton法的几何意义Newton法的本质就是不断用切线来近似曲线，因此Newton法也成为切线法.2Newton法的算法(1)取初始点x0,最大迭代次数N和精度要求ε置k=0;(2)计算(3)若则停止计算;(4)若k=N则停止计算;否则置k=k+1,转(2).Newton法可以看作下面的不动点迭代：其中

’(x*)=0Newton法至少二阶局部收敛3Newton法收敛性证明(略)Newton法也可以看作一类特殊的加速迭代取

(x)=x-f(x)定理4

设f(x)在其零点x*的某个邻域内二阶连续可导且

0，则存在x*的某个

邻域N(x*)

=[x*-

,x*

+

],

使得对

x0

N(x*)，Newton法产生的序列以不低于二阶的收敛速度收敛到x*.例设计一个二阶收敛算法计算

(a>0).解：转化为求

x2-a=0的正根Newton迭代：二阶收敛设x*是f(x)的m(m

2)重根,Newton法是否收敛？4

重根情况所以Newton迭代：线性收敛,且重数m越高,收敛越慢.提高收敛速度但m通常无法预先知道！法一：取

二阶收敛法二：将求f(x)的重根转化为求另一个函数的单根.

构造针对

(x)的具有二阶收敛的Newton迭代：令，则x*是

(x)的单重根.

例取初始点x0=1.5,分别用Newton法和求重根的两种方法计算f(x)=(x+1)(x-1)2=0解(1)Newton法迭代公式k012345xk1.51.27271.14411.07441.03781.0191k6789……13xk1.00961.00481.00241.0012……1.0001(2)方法一：取,m=2迭代公式为方法二:迭代公式为取k0123方法一xk1.51.04551.00051.0000方法二xk1.50.96080.99961.0000两种改进方法的结果比较用Newton迭代公式求解,只能是线性收敛,而改进的两种方法都具有二阶收敛,所以计算速度要快得多.但是很多问题事先不知道根的重数，所以方法一有时并不实用.Newton法的收敛依赖于初始点的选取.5Newton下山法如果x0偏离所求根x*较远,则Newton法可能发散,为防止迭代发散,我们对迭代过程再附加一项要求,即具有单调性:满足这项要求的算法称为下山法

k为数列中满足的最大数.§4Newton-RaphsonMethod

弦截法/*Seca