《工科数值分析第七章wang教学课件PPT.pptx》由会员分享，可在线阅读，更多相关《工科数值分析第七章wang教学课件PPT.pptx（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、工科数值分析第七章wang2第七章函数方程的数值解法3内容提要内容提要n 函数方程求根与二分法函数方程求根与二分法n 不动点迭代法不动点迭代法n 牛顿迭代法及其改进牛顿迭代法及其改进n 函函数方程组的牛顿迭代法数方程组的牛顿迭代法n 案例及案例及Matlab实现实现4函数方程求根与二分法函数方程求根与二分法n 函数方程求根的基本概念函数方程求根的基本概念n二分法二分法1根的存在性。方程有没有根？如果有，有几个根？根的存在性。方程有没有根？如果有，有几个根？2根的搜索。根的搜索。这些根大致在哪里？如何把根隔离开？这些根大致在哪里？如何把根隔离开？3根的精确化。根的精确化。 f (x) = 0 （
2、7.1）函数方程求根的基本概念函数方程求根的基本概念1.1.根的存在性根的存在性定理定理1：设函数设函数 f (x) 在区间在区间a, b上连续上连续，如果如果f (a) f (b) 0， 则方程则方程 f (x) = 0 在在a, b内至少有一实根内至少有一实根x*。 定义定义：如果存在如果存在 使得使得 ，则称，则称 为为方程方程（7.17.1）*x0)(*xf的根的根或或函数函数 的零点的零点。)(xf*x2mm m重根重根若若)()()(*xgxxxfm其中，其中，mxg, 0)(*为正整数，为正整数，则当则当m=1m=1时，时，称称 为为方程方程（7.17.1）的单根的单根或或函数函
3、数 的单零点的单零点。*x)(xf称称 为为方程方程（7.17.1）的的 m m重根重根或或函数函数 的的m m重零点。重零点。*x)(xf当当 时时，2. 根的搜索根的搜索(1) 图解法（利用作图软件如图解法（利用作图软件如 Matlab)(2) 解析法解析法(3) 近似方程法近似方程法(4) 定步长搜索法定步长搜索法abx*f(x)0 x1画出画出 f(x) 的略图，从而看出曲线与的略图，从而看出曲线与x 轴交点的位置。轴交点的位置。2从左端点从左端点x = a出发，按某个预先选定的步长出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点一步一步地向右跨，每跨一步都检验每步
4、起点x0和终点和终点x0 + h的函数值，若的函数值，若0)()(00hxfxf那么所求的根那么所求的根x*必在必在x0与与x0+h之间，这里可取之间，这里可取x0或或x0+h作为根的初始近似。作为根的初始近似。hx 0图解法和逐步搜索法图解法和逐步搜索法10函数方程求根的基本概函数方程求根的基本概念念-例例 逐步搜索法或增量搜索法32 11.138.841.770 xxx例如求方程的有根区间 x 0 1 2 3 4 5 6f(x)的符号 + + +由此可知方程的有根区间为1,2 3,4 5,6二分法二分法0000101110( )( )0,() / 2. ()( ),. ( )(),; ,f
5、 af bxabf xf xxf af xaxbbaa bx设取假如是的零点，那么输出停止假若不然，若与同号，则否则。0 xyX*x0aby=f(x)a1b1二分过程中有三个量在变：（区间、近似根、区间长度）11110111(1) , ,(2),22(3),22kkkkkkkka ba babbabaxxxbababa baba二分法二分法*1*()/2()| ()/2()/2. kkkkkkkkxxbaxabxakkxbx因故有, 因此，只要二分的足够多次（即 充分大），便有，这里为预定的精度.二分法收敛性分析二分法收敛性分析3 ( )101.0,1.52.f xxx 求在内的一个实根，准确
6、到小数点后位例例k ak bk xkf(xk)符号0123456 1.0 1.25 1.31251.3203 1.5 1.3751.34381.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 + + + *66(6)0.005kxx：只要二分 次，便能达到预定的精度分析二分法举例二分法举例 优点：优点： 算法简单，且总是收敛的算法简单，且总是收敛的 缺点：缺点：l 收敛收敛太慢，故一般不单独将其用于求根太慢，故一般不单独将其用于求根，只用只用其为根其为根求得求得一个较好的近似值；一个较好的近似值；l 无法直接求偶重根无法直接求偶重根二分法优
7、缺点二分法优缺点167.2不不动点迭代动点迭代法法7.2.1基本概基本概念念 将方程（7-1）改写成等价的形式 （7-6）若 满足 ，则 ；反之亦然，称为函数 的一个不动点不动点. 求 的零点就等价于求 的不动点. 选择一个初始近似值 ，将它代入(7-6)右端，即可求得（7-1）17如此反复迭代计算 （7-7） 称为迭代函数. 如果对任何 ，由（7-7）得到的序列 有极限 则称迭代方程(7-7)收敛，且 为 的不动点，故称（7-7）为不动点迭代法不动点迭代法. 迭代法的几何意义xy)(xy xy xy迭代法的几何意义迭代法的几何意义21例例1 1 求方程 在 附近的根 解解 将方程改写成下列形
8、式 据此建立迭代公式 22各步迭代的结果见表7-3. 这时可以认为 实际上已满足方程，即为所求的根. 如果仅取6位数字，那么结果 与 完全相同，23但若采用方程的另一种等价形式建立迭代公式 仍取迭代初值 ，则有 结果会越来越大，不可能趋于某个极限. 这种不收敛的迭代过程称作是发散发散的.如图7-3. 一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.图7-324 讨论迭代序列的收敛问题. 例例2 2 用不同方法求方程 的根 解解 这里 ，可改写为各种不同的等价形式 其不动点为 由此构造不同的迭代法：25取 ，对上述4种迭代法，计算三步所得的结果如下表. xyy = xxyy =
9、xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1x0p0 x1p1x0p0 x1p1x0p0 x1p127 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察 在 上不动点的存在唯一性. 定理定理1 1 设 满足以下两个条件： 1. 对任意 有 2. 存在正常数 ，使对任意 都有 （7-12）则 在 上存在唯一的不动点 28 因 ，以下设 及 ， 若 或 ，则不动点为 或 ，存在性得证.定义函数显然 ，由连续函数性质可知存在 , 且满足使 , 即即为 的不动点.证证明明 先证不动点存在性. 29 再
10、证唯一性. 设 都是 的不动点，引出矛盾.故 的不动点只能是唯一的. 则由(7-12)得 （7-12）30（7-13） 定理定理2 2 设 满足定理1中的两个条件，则对任意 ，由（7-7）得到的迭代序列 收敛到 的不动点 ，并有误差估计 证明证明 设 是 在 上的唯一不动点，由条件，可知 ，再由（7-12）得 因 ，故当 时序列 收敛到 .（7-12）（7-7）31 再证明估计式（7-13）， 由（7-12）有 （7-14）反复递推得 于是对任意正整数 有（7-13）（7-12）32在上式令 ，注意到 即得式（7-13）. 迭代过程是个极限过程. 在用迭代法实际计算时，必须按精度要求控制迭代次
11、数. 原则上可以用误差估计式（7-13）确定迭代次数，但由于它含有信息 而不便于实际应用. 根据式（7-14），对任意正整数 有 在上式中令 知 33 由此可见，只要相邻两次计算结果的偏差 足够小即可保证近似值 具有足够精度. 对定理1和定理2中的条件2，如果且对任意 有 （7-15）则由中值定理可知对 有 表明定理中的条件2可用（7-15）代替. 34 例1中，当 时， ,在区间 中， ，故（7-15）成立. 又因 ，故定理1中条件1也成立.所以迭代法是收敛的. 而当 时， ，在区间 中 不满足定理条件.（7-15）357.2.3 局部收敛性与收敛阶局部收敛性与收敛阶 上面给出了迭代序列 在
12、区间 上的收敛性， 定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性. 定义定义1 1 设 有不动点 ，如果存在 的某个邻域 对任意 ，迭代（7-7）产生的序列 且收敛到 ，则称迭代法（7-7）局部收敛局部收敛. .通常称为全局收敛性. （7-7）36 证明证明 由连续函数的性质，存在 的某个邻域 使对于任意 成立 定理定理3 3 设 为 的不动点， 在 的某个邻域连续，且 ，则迭代法（7-7）局部收敛.此外，对于任意 ，总有 ，于是依据定理2可以断定迭代过程 对于任意初值 均收敛.这是因为 （7-7）37 定义定义2 2 设迭代过程 收敛于方程的根 ，如果迭
13、代误差 当 时成立下列渐近关系式则称该迭代过程是 阶收敛阶收敛的. 特别地, 时称线性收敛线性收敛，时称超线性收敛超线性收敛，时称平方收敛平方收敛. 38 定理定理4 4 对于迭代过程 ，如果 在所求根 的邻近连续，并且 则该迭代过程在点 邻近是 阶收敛的. （7-17） 证明证明 由于 ，据定理3立即可以断定迭代过程 具有局部收敛性. 再将 在根 处做泰勒展开，利用条件（7-17），则有 39注意到 ，因此对迭代误差，当 时有 这表明迭代过程 确实为 阶收敛. 由上式得 上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取. 如果当 时 ，则该迭代过程只可能是线性收敛. 40 在例2中，迭
14、代法（3）的 ，故它只是线性收敛. 而迭代法（4）的 ，而 由定理4知 ，该迭代过程为2阶收敛. 考考虑非线性方程虑非线性方程 0)(xf原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f (x)在在 x0 做一阶做一阶Taylor展开展开:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之间。之间。牛顿法及其改进牛顿法及其改进将将 (x* x0)2 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 只要只要 f C1，且每步迭代都有，且每步
15、迭代都有f ( xk ) 0， 而且而且*limxxkk 则则 x*就是就是 f (x)的根。的根。公式公式（7-237-23）称为称为牛顿迭代公式。牛顿迭代公式。)()(1kkkkxfxfxx (7-23)构造迭代公式构造迭代公式牛顿迭代公式牛顿迭代公式x*x0 x1x2xyf(x)牛顿法几何意义牛顿法几何意义45由于 假定 是 的一个单根，即 ，则由上式知 于是依据定理4可以断定，牛顿法在根 的邻近是平方收敛的. 牛顿法的迭代函数为 又因 （7-23）牛顿法的局部收敛性牛顿法的局部收敛性 所以Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0思考题如何改进牛顿法呢?简化的牛顿法改修为注意仅适合于线性收敛!牛顿法的改进牛顿法的改进牛顿下山法思路称为牛顿下山法其中直到满足:)()(1kkxfxf 牛顿下山法