第二章 非线性方程的数值解法11148.ppt

第二章非线性方程的数值解法,2.1二分法,2.2非线性方程求解的迭代法,2.3非线性方程求解的matlab函数,历史背景,在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程:f(x)=0(2.1)的求根问题，其中f(x)为非线性函数。方程f(x)=0的根,亦称为函数f(x)的零点。,当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。,求解方程,的数值解法大致可以分为三步骤：,（1）根的存在性，方程是否有根？如果有，有几个对于多项式方程，n次方程有n个根。,（2）根的隔离，把区间分为较小的子区间，每个子区间或者有一个根，或者没有根。这样可以将有根区间内的任一点都可看成根的一个近似值,（3）根的精确化，对某个近似值设法逐步精确化，使其满足一定的精确要求,2.1二分法,二分法又称二分区间法,是求解方程(2.1)的近似根的一种常用的简单方法。,设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,根据连续函数的性质可知,方程f(x)=0在(a,b)内必有实根,称区间a,b为有根区间。,为明确起见,假定方程f(x)=0在区间a,b内有惟一实根x*。二分法的基本思想是:首先确定有根区间,将区间二等分,通过判断f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。,由高等数学知识可知,设f(x)为区间a,b上的单值连续函数,如果f(a)f(b)0,则a,b中至少有一个实根。如果f(x)在a,b上还是单调递增或递减函数，则方程f(x)=0仅有一个实根。,记笔记,由此可大体确定根所在子区间，方法有：(1)画图法(2)逐步搜索法,y=f(x),a,b,y,x,取有根区间a,b之中点,将它分为两半,分点,这样就可缩小有根区间。,2.1.2二分法求根,设方程f(x)=0在区间a,b内有根,二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下：,对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一。如此反复下去,若不出现,即可得出一系列有根区间序列：,上述每个区间都是前一个区间的一半,因此的长度：,当k时趋于零,这些区间最终收敛于一点x*即为所求的根。,每次二分后,取有根区间的中点作为根的近似值，得到一个近似根的序列：该序列以根x*为极限只要二分足够多次(即k足够大),便有这里为给定精度,由于,则：,当给定精度0后,要想成立,只要取k满足即可，亦即当:,时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。在程序中通常用相邻的与的差的绝对值或与的差的绝对值是否小于来决定二分区间的次数。,二分法算法实现,二分法的优点是不管有根区间a,b多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单。它的局限性是只能用于求函数的实根,不能用于求复根及重根,2.2非线性方程求解的迭代法,对于一般的非线性方程，没有通常所说的求根公式来求其精确解，需要设计近似求解方法，已知方程的一个近似根，通过构造一个递推关系，即迭代格式，使用这个格式反复校正根的近似值，计算出方程的近似序列。使之逐步精确化，最后得到满足精度要求的结果。这种方法称之为迭代法,2.2.1迭代法的基本思想,即如果数使f(x)=0,则也有,反之,若,则也有,称为迭代函数任取一个初值,代入式的右端,得到：,2.2.2不动点迭代法及其收敛性为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程：(2.5)其中为x的连续函数。,再将代入式的右端,得到依此类推,得到一个数列：其一般表示为：,式(2.6)称为求解非线性方程的简单迭代法。,(2.6),如果由迭代格式产生的序列收敛,即：,则称迭代法收敛。,实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求，只要某个k满足：,即可结束计算并取,迭代函数的构造方法是多种多样的。,例3用迭代法求方程在x=1.5附近的一个根。解将方程改写成如下两种等价形式：,相应地可得到两个迭代公式：,如果取初始值1.5，可用上述两个迭代公式分别进行迭代。,迭代法的算法框图,2迭代法的几何意义,通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于的性态,方程的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标。,(a),(b),5迭代法收敛的条件对方程f(x)=0可以构造不同的迭代公式,但迭代公式：并非总是收敛的。那么,当迭代函数满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代。,定理2.1,证明：,（一、证明存在惟一性）,由于,（二、证明收敛与初值的无关性）,简单迭代法收敛定理,简单迭代法收敛定理,简单迭代法收敛定理,定理2.2,压缩影响原理的应用,提示,压缩影响原理的应用,迭代法的局部收敛性,定义2.1：对于方程,定理2.3,迭代法的局部收敛性,求方程,例3回顾,压缩影响原理应用的例题,例4对方程,构造收敛的迭代格式,求其最小正根,计算过程保留4位小数。解容易判断1,2是方程的有根区间,且在此区间内,所以此方程在区间1,2有且仅有一根。将原方程改写成以下两种等价形式。,即：不满足收敛条件。,即：不满足收敛条件。,即：此时迭代公式满足迭代收敛条件。,2.2.3迭代过程的加速,对于收敛的迭代过程，只要迭代足够的次数，就可以使结果达到任意精度，但有时迭代过程的收敛速度缓慢，从而使计算量变得很大。因此，迭代过程的加速在计算方法中是一个重要研究课题。,迭代法的收敛速度，是指在接近收敛时迭代误差的下降速度。,定义2.2设迭代过程,收敛于方程,的根，,设误差,，若存在某实数,及常数,使,则迭代过程,是P阶收敛，,当,时，称为线性收敛。,当,时，称为平方收敛。,当,时，称为超线性收敛。,数p的大小反应收敛速度的快慢，p越大，则收敛越快。,不可能直接确定,定理2.,松弛法,对于迭代法,于是,即,令,2.19,2.20,为了使2.20迭代收敛比2.19收敛快,希望,得,因此有松弛迭代法:,从后面的例子可以看出,加速效果是明显的,甚至一些不收敛的迭代法经过松弛加速后也能收敛,取,由于,不容易得到，所以用,代替,不方便,中值定理