常用数值分析方法§1非线性方程求根.ppt

第一章,材料科学研究中的常用数值分析方法,主要内容,1非线性方程求解2线性方程组的数值解法3插值法与曲线拟合4有限差分法与有限单元法,1非线性方程求解,1.1概述1.2对分法1.3迭代法1.4Newton法1.5弦截法其他方法：Aitken加速法、Steffensen加速法、重根加速收敛法、抛物线法、牛顿下山法、劈因子法等。,1.1非线性方程求解概述,很多科学计算问题常常归结为求解方程：,非线性方程求解概述(续）,例如，从曲线y=x和y=lgx的简单草图可看出方程lgx+x=0有唯一的正根x*，但是没有求x*的准确值的已知方法，即使是对代数方程，要求其精确解也是困难的。对于二次方程ax2+bx+c=0，我们可以用熟悉的求根公式：,对于三、四次代数方程，尽管存在求解公式，但并不实用。而对于大于等于五次的代数方程，它的根不能用方程系数的解析式表示，至于一般的超越方程，更没有求根公式。因此，为求解一个非线性方程，我们必须依靠某种数值方法来求其近似解。,对于方程（1-1）要求得其准确解一般来说是不可能的。,求方程根近似解的几个问题：,设函数f(x)在区间a,b上连续，严格单调，且f(a)f(b)0,f(0)=10,f(3)=260所以仅有二个实根，分别位于(0,3),(3,)内。又因f(4)=10,所以，二个隔根区间确定为(0,3),(3,4)。,例2,从区间a,b的左端点a出发，按选定的步长h一步步向右搜索，若:,则：区间a+jh,a+(j+1)h内必有根。搜索过程也可以从b开始，这时应取步长h0(x(,)，故：f(x)在(,)上单调增加而：f(1)=90所以：原方程在（1，2）内有唯一实根。,表12,对分法的优缺点,优点：计算简单，方法可靠，容易估计误差。缺点：但它收敛较慢，不能求偶次重根，也不能求复根。因此，一般在求方程近似根时，很少单独使用，常用于为其他高速收敛算法（如牛顿法）提供初值。,1.3迭代法,迭代法是求解方程f(x)=0的根的一种主要方法。它是利用同一个迭代公式，逐次逼近方程的根，使其得到满足预先给定精度要求的近似值。,迭代法的基本思想,迭代法是一种重要的逐次逼近法，其基本思想是：设方程f(x)=0在区间a,b内有一根x*，将方程化为等价方程x=(x)，并在a,b内任取一点x0作为初始近似值，然后按迭代公式计算：,产生迭代序列x0,x1,xn,显然，若xn收敛于x*，(x)在x*处连续，就有:,这种求根方法称为迭代法，式（1-3）称为迭代格式，(x)称为迭代函数，x0称为迭代初值，xn称为迭代序列如果迭代序列收敛，则称迭代格式（1-3）收敛，否则称为发散。,即：x*是方程f(x)=0的解。,故：当n充分大时，可取xn作为方程的近似解。,迭代法举例,例4,解：容易验证，方程在1,2内有根，取x0=1.5,例4（续）,表1-2,迭代法举例（续）,例5,解：对方程进行变换，可得如下三种等价形式：,分别按以上三种形式建立迭代格式，并取x0=1进行迭代计算，结果如下：,例5的计算结果表明：将一方程化为等价方程的方法很多，由此可构造许多不同的迭代函数，得到多种迭代格式。而它们所产生的迭代序列则可能收敛，也可能发散，可能收敛很快，也可能收敛很慢。迭代法的收敛性取决于迭代函数在方程的根的邻近的性态。,迭代法的几何含义,从几何上看，迭代法是将求曲线y=f(x)的零点问题化为求曲线y=(x)与直线y=x的交点，迭代过程如图1-2所示，从初始点x0出发，沿直线x=x0走到曲线y=(x)，得点(x0,(x0)，再沿直线y=(x0)走到直线y=x，交点为(x1,(x1)，如此继续下去，越来越接近点(x*,x*)。,y,当然，迭代过程也可能出现图1-3所示的情况，此时点(xn,xn)越来越远离交点(x*,x*)，迭代序列发散。,由此可见，使用迭代法必须解决两个问题：一是迭代格式满足什么条件才能保证收敛；二是如何判别迭代收敛的速度，建立收敛快的迭代格式。,迭代法的几何含义（续）,迭代法的收敛条件（三大定理）,定理1.1（压缩映象原理）,设函数(x)在区间a,b上满足条件：,则：方程x=(x)在a,b内有唯一的根x*，且对任意初值x0a,b，迭代序列：,证明略,两个重要误差公式,1.式（1-2）说明，在正常情况下，即L不太接近于1（若L接近于1，则收敛速度很慢），可用相邻两次迭代值之差的绝对值来估计误差，控制迭代次数。,就停止计算，取xn作为方程的近似根。这种用相邻两次计算结果来估计误差的方法，称为事后估计法。,即当给定精度时，如果有：,1,2,2.而式（1-3）的误差估计，称为事前估计法，因为用它可以估计出要达到给定精度所需次数n,事实上，由,两个重要误差公式（续）,迭代法的收敛条件(之二),定理1.2,（1）对任意的xa,b，有(x)a,b；（2）存在常数0L0，使得对任意x0x*,x*+，Newton法所产生的序列xn至少二阶收敛于x*。,定理1.4表明，当初值x0充分接近x*时，Newton法的收敛速度较快，但当初值不够好时，可能会不收敛或收敛于别的根，这可从Newton法的几何意义看到：,注：NewtonsMethod收敛性依赖于x0的选取。,x*,Newton法的优缺点,优点：Newton法具有收敛快，稳定性好，精度高等优点，它是求解非线性方程的有效方法之一。缺点：每次迭代均需要计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。,1.5弦截法,不足之处：需要计算导数值，较难；,这就是弦截法迭代公式,Newton法优点：收敛快（平方阶），固定格式；,修正：以差商代替导数（微商）,弦截法迭代公式的几何解释,与x轴相交，即y=0，解出x得：,即以割线代替曲线f(x)，以割线与x轴的交点去近似曲线与x轴的交点，又称为割线法。,弦截法的几点说明,1、需要两个点x0，x1才能开始进行迭代：（1）若只给定x0，则须利用其他方法，如对分法，求x1，然后再利用弦截法，求x2，x3，；（2）若给定一有根区间，可直接用两端点作x0，x1。,xn收敛，收敛阶为1.618，超线性收敛。,3.上述弦截法又称为变端点弦截法（双点），,该法称为：定端点弦截法（单点），几何意义如右图：,弦截法的几点说明(续）,其实还可固定一端点x0写为：,弦截法举例,例9,用定端点，变端点截线法