数学建模迭代法教材课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,作业,每题分别用两种一步迭代法（要求写出迭代格式）：,1,）,Newton迭代法；,2）自己构造的非牛顿切线或割线法迭代格式（需讨论收敛性）,根据迭代格式用计算机（器）求下列非线性方程的根：,作业每题分别用两种一步迭代法（要求写出迭代格式）：,问题背景和研究目的,解方程（代数方程）是最常见的数学问题之一，也是众多应用领域中不可避免的问题之一。,求解一般非线性方程,没有通用的解析方法，但如果 在任意给定的精度下，能够解出方程的近似解，则 可以认为问题已能够解决，至少可以满足实际需要。,本节主要介绍一些有效的求解方程的数值方法：,二分法,，,迭代法,（,牛顿法）,。同时要求大家学会如何利用,Matlab,来求方程的近似解。,2.6 非线性方程近似根,问题背景和研究目的 解方程（代数方程）是最常见的数学问题之,相关概念,如果,f,(,x,),是一次多项式，称上面的方程为,线性方程,； 否则称之为,非线性方程,。,线性方程,与,非线性方程,相关概念 如果 f(x) 是一次多项式，称上面的方程为线性,问题：,如何求连续的非线性方程 实根的近似值。,根的隔离,若函数,f,(,x,),在闭区间,a,b,上连续，且,f,(,a,),f,(,b,)0,，则,f,(,x,),在开区间,(,a,b,),内至少存在一个根。通过根的隔离，可假设此区间内存在唯一根,x,*,。,问题：根的隔离 若函数 f(x) 在闭区间a,基本思想,二分法,将隔离区间进行对分，判断出解在某个子区间内，然后再对该子区间对分，依次类推，直到满足给定的精度为止。,适用范围,求有根区间内的,单根,或,奇数重实根,。,数学原理：,介值定理,设,f,(,x,),在,a, b,上连续，且,f,(,a,),f,(,b,)0,，则由介值定理可得，在,(,a,b,),内至少存在一点,使得,f,(,)=0,。,基本思想二分法将隔离区间进行对分，判断出解在某个子区间内，,算法,二分法,设方程在区间,a,b,内连续，且,f,(,a,),f,(,b,)0,，给定精度要求,，若有,|,f,(,x,)|,，则,x,就是,f,(,x,),在区间,(,a,b,),内的,近似根,。,算法二分法设方程在区间 a,b 内连续，且 f(a)f,收敛性分析,二分法收敛性,设方程的根为,x*,(,a,n,b,n,),，又 ，所以,0,(,n,),根据上面的算法，我们可以得到一个每次缩小一半的区间序列,a,n,b,n,，在,(,a,n,b,n,),中含有方程的根。,二分法总是收敛的,二分法的收敛速度,较慢,通常用来给出根的一个,较为,粗糙的近似,。,收敛性分析二分法收敛性设方程的根为 x* (an ,数学建模迭代法教材课件,简单迭代法,基本思想,构造,f,(,x,) = 0,的一个等价方程：,从某个初值,x,0,出发，构造,迭代格式,得到一个迭代序列,k,= 0, 1, 2, . .,(,x,),的不动点,f,(,x,) = 0,x,=,(,x,),等价变换,f,(,x,),的零点,(,x,),称为,迭代函数,简单迭代法 基本思想 构造 f (x) = 0 的一个等价方,若 收敛，即 ，假设,(,x,),连续，则,收敛性分析,迭代法的收敛性,即,注：若得到的,点列发散，则迭代法失效,！,若 收敛，即,迭代法的收敛性判据,定理,2.1,：全局收敛,定理,2.2,：全局发散,定理,2.3,：局部收敛与发散,定理,2.4,：收敛速度,迭代法的收敛性判据定理2.1：全局收敛定理2.2：全局发散定,定义：,迭代法收敛性判断,如果存在,x*,的,某个,邻域,=(,x,*,-,x*,+,),使得对,x,0, ,开始的迭代,x,k,+1,=,(,x,k,),都收敛,则称该迭代法在,x*,附近,局部收敛,。,定理 1：,设,(,x,),在,某个邻域,内连续，且对,x,都有,|,(,x,)|,L, 1,则迭代局部收敛。,定义：迭代法收敛性判断如果存在 x* 的某个邻域 =(,迭代法收敛性判断,定理,2,：,设 ，且,对,x,a,b,，,有,(,x,),a,b,；,对,x,a,b,，,有,|,(,x,)|,L, 1,；,则对,x,0,a,b,，,由,迭代,x,k,+1,=,(,x,k,),得到的点列都收敛（,全局收敛,），且,L,越小,，迭代收敛,越快,迭代法收敛性判断 定理 2：设 ，,收敛阶,为了进一步研究收敛速度问题，引入阶的概念：,记 ，如果,(,p=,1时还要求0,c,1时称为超线性收敛,。,p,越大收敛越快。,收敛阶为了进一步研究收敛速度问题，引入阶的概念：,牛顿,迭代法,令：,基本思想：,用线性方程来,近似,非线性方程，即采用,线性化方法,设非线性方程,f,(,x,)=0,f,(,x,),在,x,k,处作,Taylor,展开,牛顿迭代公式,k,= 0, 1, 2, . .,牛顿迭代法令： 基本思想：用线性方程来近似非线性方程，即采用,牛顿,迭代公式,牛顿法的优点,牛顿法是目前求解非线性方程 (组) 的主要方法,对于单重根迭代,2,阶收敛，收敛速度较快,，,特别是当迭代点充分靠近精确解时。,牛顿法的缺点,对重根收敛速度只有线性收敛,对初值的选取很敏感，要求初值接近精确解,在实际计算中，如果要求高精度，可以先用其它方法（如二分法）获得精确解的一个粗糙近似，然后再用牛顿法求解。,牛顿迭代公式 牛顿法的优点 牛顿法是目前求解非线性方程 (组,牛顿迭代法大范围收敛性,牛顿迭代法大范围收敛性,Matlab 解方程的函数,roots(p),：,多项式的,所有零点,，,p,是多项式系数向量。,fzero,(,f,x0,),：,求,f=0,在,x0,附近的根，,f,可以使用,inline,、,字符串,、或,，但不能是方程或符号表达式！,solve(f,x),：,求方程关于指定自变量,x,的解，,f,可以是,用字符串表示的方程,、,符号表达式,或,符号方程,；,solve,也可解方程组(包含非线性)；,得不到解析解时，给出数值解。,Ab,：,解线性方程组,Ax=b,。,Matlab 解方程的函数roots(p)：多项式的所有零点,其他 Matlab 相关函数,g=diff(f,x),：,求符号表达式,f,关于,x,的导数,g=diff(f),：,求符号表达式,f,关于,默认变量,的导数,g=diff(f,x,n),：,求,f,关于,x,的,n,阶导数,diff,f,是符号表达式，也可以是字符串,默认变量由,findsym(f,1),确定,syms x,f=sin(x)+3*x2;,g=diff(f,x),g=diff(,sin(x)+3*x2,x,),其他 Matlab 相关函数g=diff(f,x)：求符号表,作业,每题分别用两种一步迭代法（要求写出迭代格式）：,1,）,Newton迭代法；,2）自己构造的非牛顿切线或割线法迭代格式（需讨论收敛性）,根据迭代格式用计算机（器）求下列非线性方程的根：,作业每题分别用两种一步迭代法（要求写出迭代格式）：,迭代法的加速,设迭代,x,k,+1,=,(,x,k,),，第,k,步和第,k,+1,步得到的,近似根分别为,x,k,和,(,x,k,),，令,其中,w,k,称为加权系数或权重。得新迭代,x,k,+1,=,(,x,k,),加权系数,w,k,的确定：令,(,x,)=0,得,迭代法的加速 设迭代 xk+1 = (xk) ，第 k 步,松弛迭代法,松弛法迭代公式：,松弛法具有较好的加速效果，甚至有些不收敛的迭代格式，通过加速后也能收敛。,缺点：,每次迭代都需计算导数,松弛迭代法 松弛法迭代公式：松弛法具有较好的加速效果，甚至有,Altken,迭代法,Altken迭代法,用,差商,近似,微商,设,x*,是方程的根，则由微分中值定理可得,Altken 迭代法 Altken迭代法用 差商 近似 微商,Altken,迭代法,Altken迭代公式,k,= 0, 1, 2, . .,Altken,法同样具有较好的加速效果,Altken 迭代法 Altken迭代公式 k = 0, 1,