非线性方程的数值解法.ppt

第二章 非线性方程的数值解法2.1 二分法2.2 非线性方程求解的迭代法2.3 非线性方程求解的matlab函数历史背景代数方程的求根问题是一个古老的数学问题理论上， 次代数方程在复数域内一定有 个根(考虑重数)早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个一般也不存在根的解析表达式因此需要研究数值方法求得满足一定精度要求的根的近似解 在科学研究和工程设计中, 经常会遇到的一大类 问题是非线性方程: 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仅有一个实根记笔记n由此可大体确定根所在子区间，方法有：(1) 画图法(2) 逐步搜索法y=f(x)abyx① 取有根区间[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.3 迭代过程的加速迭代过程的加速对于收敛的迭代过程，只要迭代足够的次数，就可以使结果达到任意精度，但有时迭代过程的收敛速度缓慢，从而使计算量变得很大因此，迭代过程的加速在计算方法中是一个重要研究课题迭代法的收敛速度，是指在接近收敛时迭代误差的 下降速度。

定义2.2 设迭代过程收敛于方程的根 ，设误差，若存在某实数及常数使则迭代过程是P阶收敛，当时，称为线性收敛当时，称为平方收敛当时，称为超线性收敛数p的大小反应收 敛速度的快慢，p 越大，则收敛越快 不可能直接确定定理2. 松弛法对于迭代法于是即令2.192.20为了使 2.20 迭代收敛比2.19收敛快希望得因此有松弛迭代法:从后面的例子可以看出,加速效果是明显的甚至一些不收敛的迭代法经过松弛加速后也能收敛取由于不容易得到，所以用代替不方便中值定理差商近似代替导数即于是可以得到迭代格式:其中-------(2.27)上组公式称为Altken公式或Altken加速将(2.27)式综合后可得一个解析式表示的迭代法:上式称为Steffensen迭代法Altken公式与Steffensen公式是等价的加速效果也是很明显的。