数值计算方法课件CH逐次逼近法非线性方程的迭代解法

第六章逐次逼近法6.3

解非线性方程的迭代法数值计算方法华长生制作1本节主要内容3-1解非线性方程的简单迭代法3-2Newton迭代法及其变形

6.3非线性方程的迭代法

方程是在科学研究中不可缺少的工具，方程求解是科学计算中一个重要的研究对象.设函数方程统称为非线性方程

几百年前就已经找到了代数方程中二次至五次方程的求解公式,但是,对于更高次数的代数方程目前仍无有效的解析解法，对于无规律的超越方程的求解也无精确解法.因此,研究非线性方程的数值解法成为必然.注.(1)非线性方程一般情况下很难求得其解析解,

所以往往采用数值方法求解.(2)非线性方程中,通常假设函数f(x)是连续的.求非线性方程的根.f(x)=0--------(3.1)求非线性方程的根,即求曲线y=f(x)与x

轴的交点α单根区间:

方程在区间[a,b]只有一根多根区间:

方程在区间[a,b]有多个根有根区间xyy=f(x)aAbα0B保证有解3-1简单迭代法思路2.

建立迭代格式:求解非线性方程问题转化为求序列极限问题1.

将化为与它同解的方程:--------(3.2)即若存在α,使,则有;反之也成立.--------(3.3)称(3.3)为求解非线性方程的(简单)迭代法／迭代过程／迭代格式.若当时,则迭代法(3.3)收敛,就是方程(3.1)的解,否则迭代法发散.3.

从初值出发,得到序列迭代函数

根的存在与唯一性:方程有没有根？若有根,

是否唯一?研究内容

迭代格式的收敛性:如何构造收敛的迭代格式？定理3.1:解的存在与唯一性定理

收敛速度的确定；收敛阶的概念及判定定义3.1,定理3.2例1

用迭代法求的根.(1)

化为等价方程:

取,代入上式得:得迭代格式:显然,当时,,即迭代法收敛.另外即是方程f(x)=0的根.解:(2)

由还可得等价方程:

得迭代格式:取,代入上式得:显然,当时,,即迭代法发散.迭代法的收敛与发散,依赖于迭代函数的构造!迭代函数要满足什么条件,迭代法才收敛？定理3.1(P225)判断迭代是否可终止的依据若迭代函数满足定理

3.1

的条件,则迭代法收敛.那么迭代过程何时结束？由(3.4)知,只要相邻两次计算值的差达到事先给定的精度要求,迭代过程可终止,即由(3.5)知,若已知

L

的范围,则由给定的精度可大致估计迭代所需次数

k

(3.4)(3.5)判断迭代可终止的条件估计迭代次数迭代法的结束条件如何确定迭代次数？迭代法次数的确定局部收敛问题定理3.1的条件一般难于验证,且在大区间[a,b]上,这些条件未必满足,因此使用迭代法时，往往只在根α附近进行.即只要假定在α的附近的小邻域内连续,且满足则存在α的某个邻域,在S上满足定理3.1的条件,称这种收敛为局部收敛.一般,在给定精度下,要求方程在某点附近的根.例2

求在附近的一个根,要求精度.解(2)

利用定理3.1验证所建立迭代格式的收敛性(1)

首先化等价方程,建立迭代格式③

当时,所建迭代格式满足定理3.1的条件,对于初始值收敛.①

确定迭代区间,取一般选择根附近的一个小区间

当时，是单调递减函数.

当时，②00.50.6065310.106531迭代结果:10.6065310.5452390.06129220.5452390.5797030.03446430.5797030.5600650.01963840.5600650.5711720.01110750.5711720.5648630.00630960.5648630.5684390.00357670.5684390.5664090.00203080.5664090.5675600.00115190.5675600.5669070.000653α≈0.566907是方程在x=0.5附近的计算根.从定理3.1可见,一方面,当L或的值越小,迭代收敛的速度越快;另一方面,当L<1且接近1时,迭代虽收敛,但速度很慢.为定量描述迭代法收敛的快慢,引进收敛阶的概念.收敛阶的概念p=1称为线性收敛；p

>1称为超线性收敛;p

=2称为平方收敛.p越大,迭代法收敛速度越快定义3.1

设迭代格式xk+1=

(xk),当k→∞时,xk+1→α,记误差

。若存在实数p≥1和c>0满足则称迭代法为p阶收敛.--------(3.7)如何定量判断收敛速度?收敛阶的判定定理3.2

如果

x=

(x)中,迭代函数

(x)在根α附近满足： （1）

(x)存在p阶导数且连续； （2）

(α)=

(α)=…

=

(p-1)(α)=0,

(p)(α)≠0则迭代法

xk+1=

(xk)

为p

阶收敛.例3

设,,证明由建立的迭代法至少是平方收敛的.--------(3.8)Newton迭代法证明只需证明,见教材p228.3-2Newton迭代法及其变形

用迭代法解非线性方程时，如何构造迭代函数是非常重要的.

主要介绍：1）Newton迭代法2）弦截法1、Newton迭代法（又称作切线法）

Newton法是求解方程f(x)=0的一种重要的迭代法。这种方法的基本思想是设法将非线性方程f(x)=0逐步转化为某种线性方程求解。如果将非线性方程化为等价方程所以可以令，这样就能保证(1)式对应的迭代法至少是平方收敛的。即：

那么如何确定k(x)的形式使上式成立并使其所对应的迭代法收敛呢？（1）于是取(2)----(3.10)注意：1)Newton迭代法的优点:收敛速度快（至少是平方收敛的）。2)Newton迭代法的缺点：需要计算导数，如果函数f(x)比较复杂，使用Newton公式是不方便的。为了避开导数的计算，可以用导数的近似值来替代，得到所谓的弦截法。2、弦截法中含有函数的导数,不方便求.--------(3.10)代入(3.10)得Newton迭代法:可用导数的近似式代替，即--------(3.11)弦截法弦截法的收敛阶为p≈1.618BAxk-1xkxk+2xk+1xk+1xk+2αy=f(x)f(xk)f(xk-1)Newton迭代法与弦截法的几何意义xy弦截法不需要求导,但需要两个初始值;Newton

法虽需求导,但只需一个初始值.二者比较:Newton

法又称切线法例4（P230）用Newton法和弦截法分别计算方程在x=1.5附近的根α.时停止计算解取初值x0=1.5,代入上式,得计算解序列：x1≈1.34783,x2≈1.32520,x3≈1.32472,x4≈1.32472，(1)用Newton法：注意：1）Newton法在根附近收敛，初值应选在附近；初值选的不合适会导致Newton迭代法发散;2）Newton法的收敛速度与初值、收敛阶数有关。因此α≈1.32472取初值x0=1.5,x1=1.4

代入上式,得计算解序列：x2≈1.33522,x3≈1.32541,x4≈1.32472,x5≈1.32472，(3)