数学建模迭代法-文档资料

1、1作业作业每题分别用两种一步迭代法（要求写出迭代格式）：1） Newton迭代法；2）自己构造的非牛顿切线或割线法迭代格式（需讨论收敛性） 根据迭代格式用计算机（器）求下列非线性方程的根：2(1) ( )sin , 4xf xx在区间内的根，精确至小数点后2位。32(2) ( )491,1.5f xxx 在区间内的根，精确至小数点后3位。2q 问题背景和研究目的u 解方程（代数方程）是最常见的数学问题之一，解方程（代数方程）是最常见的数学问题之一，也是众多应用领域中不可避免的问题之一。也是众多应用领域中不可避免的问题之一。u 求解一般非线性方程没有通用的解析方法，但如果 在任意给定的精度下，能

2、够解出方程的近似解，则 可以认为问题已能够解决，至少可以满足实际需要。u 本节主要介绍一些有效的求解方程的数值方法：二分法，迭代法 （ 牛顿法）。同时要求大家学会如何利用Matlab 来求方程的近似解。2.6 非线性方程近似根非线性方程近似根3相关概念相关概念0( )f x u 如果如果 f(x) 是一次多项式，称上面的方程为是一次多项式，称上面的方程为线性方程线性方程； 否则称之为否则称之为非线性方程非线性方程。q 线性方程线性方程 与与 非线性方程非线性方程4 0f x 问题：问题： 如何求连续的非线性方程如何求连续的非线性方程 实根的近似值。实根的近似值。根的隔离根的隔离 若函数若函数

3、f(x) 在闭区间在闭区间a,b上连续，且上连续，且 f(a)f(b)0，则，则 f(x)在开区间在开区间 (a,b)内至少存在一个根。通过根的隔离，可假设此区间内存在唯一根内至少存在一个根。通过根的隔离，可假设此区间内存在唯一根 x*。1a1x2b2a2x3b3a3x4b4a4x5a5x56ba6b6x1b5q 基本思想基本思想二分法二分法将隔离区间进行对分，判断出解在某个子区间内，然将隔离区间进行对分，判断出解在某个子区间内，然后再对该子区间对分，依次类推，直到满足给定的精后再对该子区间对分，依次类推，直到满足给定的精度为止。度为止。q 适用范围适用范围求有根区间内的求有根区间内的 单根单

4、根 或或 奇数重实根奇数重实根。q 数学原理：数学原理：介值定理介值定理设设 f(x) 在在 a, b 上连续，且上连续，且 f(a) f(b)0，则由介值定，则由介值定理可得，在理可得，在 (a, b) 内至少存在一点内至少存在一点 使得使得 f( )=0。6001:,0,;Stepiaa bb预 定 精 度1211112 :, if 0,; else if 0,; else ,;iiiiiiiiiiiiiiiiStepxabfafxaa bxfbfxax bbxx break3:if,1,goto Step2; else .iiiStepbaiixx q 算法算法二分法二分法设方程在区间设

5、方程在区间 a,b 内连续，且内连续，且 f(a)f(b)0，给定精，给定精度要求度要求 ，若有，若有 |f(x)| ，则，则 x 就是就是f(x) 在区间在区间 (a,b) 内的内的 近似根近似根。7q 收敛性分析收敛性分析二分法收敛性二分法收敛性=*11111 11|()()()22 22nnnnnnxxbababa 设方程的根为设方程的根为 x* (an , bn ) ，又，又 ，所以，所以2nnabnx 0(n )根据上面的算法，我们可以得到一个每次缩小一半的根据上面的算法，我们可以得到一个每次缩小一半的区间序列区间序列 an , bn ，在，在 (an, bn ) 中含有方程的根。中

6、含有方程的根。,( , ),.a bn预定精度初始区间为估计达到预定精度所需最少二分次数11()2nnxxba2log1ban二分法总是收敛的二分法总是收敛的u 二分法的收敛速度二分法的收敛速度较慢较慢u 通常用来给出根的一个通常用来给出根的一个 较为较为粗糙的近似粗糙的近似。89简单迭代法简单迭代法q 基本思想基本思想u 构造构造 f (x) = 0 的一个等价方程：的一个等价方程： ( )xx u 从某个初值从某个初值 x0 出发，构造出发，构造迭代格式迭代格式得到一个迭代序列得到一个迭代序列 0kkx 1()kkxx k = 0, 1, 2, . . (x) 的不动点的不动点f (x)

7、= 0 x = (x)等价变换等价变换f (x) 的零点的零点 (x) 称为称为迭代函数迭代函数10u 若若 收敛，即收敛，即 ，假设，假设 (x) 连续，则连续，则q 收敛性分析收敛性分析迭代法的收敛性迭代法的收敛性 1limlim()limkkkkkkxxx lim*kkxx *x( *)x kx*( *)xx ( *)0f x 即即注：若得到的注：若得到的点列发散，则迭代法失效点列发散，则迭代法失效！11迭代法的收敛性判据迭代法的收敛性判据定理2.1：全局收敛定理2.2：全局发散定理2.3：局部收敛与发散定理2.4：收敛速度12q 定义：定义：迭代法收敛性判断迭代法收敛性判断如果存在如果

8、存在 x* 的的某个邻域某个邻域 =(x*- , x* + ), 使使得对得对 x0 开始的迭代开始的迭代 xk+1 = (xk) 都收敛都收敛, 则称该迭代法在则称该迭代法在 x* 附近附近局部收敛局部收敛。q 定理定理 1：设设 (x) 在在某个邻域某个邻域 内连续，且对内连续，且对 x 都有都有 | (x)| L 1, 则迭代局部收敛。则迭代局部收敛。13迭代法收敛性判断迭代法收敛性判断10|* |1kkLxxxxL q 定理定理 2：设设 ，且，且对对 x a, b，有有 (x) a, b；对对 x a, b，有有| (x)| L 1； 则对则对 x0 a, b ，由由迭代迭代 xk+

9、1 = (xk) 得到得到的点列都收敛（的点列都收敛（全局收敛全局收敛），且），且L 越小越小，迭代收敛，迭代收敛越快越快1,a bC14收敛阶收敛阶为了进一步研究收敛速度问题，引入阶的概念：记 ，如果 ( p=1时还要求0c1时称为超线性收敛。p越大收敛越快。*kkexx)(0lim1Npceepkkk15牛顿牛顿迭代法迭代法()()()kkkf xfxxx令：令：1()0kP x 1()()kkkkf xxxfx ()0)kfx q 基本思想：基本思想：用线性方程来用线性方程来近似近似非线性方程，即采用非线性方程，即采用线性化方法线性化方法o( )()()()()kkkkf xf xfxx

10、xxx u 设非线性方程设非线性方程 f (x)=0 , f (x) 在在 xk 处作处作 Taylor 展开展开( )P xq 牛顿迭代公式牛顿迭代公式k = 0, 1, 2, . . 16牛顿牛顿迭代公式迭代公式q 牛顿法的优点牛顿法的优点q 牛顿法是目前求解非线性方程牛顿法是目前求解非线性方程 (组组) 的主要方法的主要方法对于单重根迭代对于单重根迭代2阶收敛，收敛速度较快阶收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。特别是当迭代点充分靠近精确解时。q 牛顿法的缺点牛顿法的缺点l 对重根收敛速度只有线性收敛对重根收敛速度只有线性收敛l 对初值的选取很敏感，要求初值接近精确解对初值

11、的选取很敏感，要求初值接近精确解在实际计算中，如果要求高精度，可以先用其它方法在实际计算中，如果要求高精度，可以先用其它方法（如二分法）获得精确解的一个粗糙近似，然后再用（如二分法）获得精确解的一个粗糙近似，然后再用牛顿法求解。牛顿法求解。17牛顿迭代法大范围收敛性牛顿迭代法大范围收敛性(2) , ( ),a bf xC设函数且满足条件：1. ( ) ( )0;f a f b 2. , ,( )0;xa bfx 3.( , ),( )xa bfx 保号；4. ( ), ( ).abba ( )f xxxfx0 , ,2 , xa bNewtona b则对任意初值迭代法产生的迭代序列 阶收敛到内

12、唯一单根。18Matlab 解方程的函数解方程的函数roots(p)：多项式的多项式的所有零点所有零点，p 是多项式系数向量。是多项式系数向量。fzero(f,x0)：求求 f=0 在在 x0 附近的根，附近的根，f 可以使用可以使用 inline、字符串字符串、或、或 ，但不能是方程或符号表达式！，但不能是方程或符号表达式！solve(f,x)：求方程关于指定自变量求方程关于指定自变量x的解，的解， f 可以是可以是用字符串表示的方程用字符串表示的方程、符号表达式符号表达式或或符号方程符号方程；l solve 也可解方程组也可解方程组(包含非线性包含非线性)；l 得不到解析解时，给出数值解。

13、得不到解析解时，给出数值解。Ab：解线性方程组解线性方程组Ax=b。 19其他其他 Matlab 相关函数相关函数g=diff(f,x)：求符号表达式求符号表达式 f 关于关于 x 的导数的导数g=diff(f)：求符号表达式求符号表达式 f 关于关于默认变量默认变量的导数的导数g=diff(f,x,n)：求求 f 关于关于 x 的的 n 阶导数阶导数q diffl f 是符号表达式，也可以是字符串是符号表达式，也可以是字符串 l 默认变量由默认变量由 findsym(f,1) 确定确定 syms x f=sin(x)+3*x2; g=diff(f,x) g=diff(sin(x)+3*x2,

14、x)20作业作业每题分别用两种一步迭代法（要求写出迭代格式）：1） Newton迭代法；2）自己构造的非牛顿切线或割线法迭代格式（需讨论收敛性） 根据迭代格式用计算机（器）求下列非线性方程的根：2(1) ( )sin , 4xf xx在区间内的根，精确至小数点后2位。32(2) ( )491,1.5f xxx 在区间内的根，精确至小数点后3位。21迭代法的加速迭代法的加速1 1 ()()kkkkkxwxwx u 设迭代设迭代 xk+1 = (xk) ，第，第 k 步和第步和第 k+1 步得到的步得到的 近似根分别为近似根分别为 xk 和和 (xk) ，令，令其中其中 wk 称为加权系数或权重。

15、得新迭代称为加权系数或权重。得新迭代 xk+1 = (xk) 1( )()( )xw xwx u 加权系数加权系数 wk 的确定：令的确定：令 (x)=0 得得11( )wx 11()kkwx 22松弛迭代法松弛迭代法q 松弛法迭代公式：松弛法迭代公式：1 1 ()()kkkkkxwxwx 松弛法具有较好的加速效果，甚至有些不收敛的迭松弛法具有较好的加速效果，甚至有些不收敛的迭代格式，通过加速后也能收敛。代格式，通过加速后也能收敛。 11 1,()()kkkwxx u 缺点：缺点：每次迭代都需计算导数每次迭代都需计算导数23Altken 迭代法迭代法q Altken迭代法迭代法用用 差商差商 近似近似 微商微商211*( *)()( )( *)xxxxxx u 设设 x* 是方程的根，则由微分中值