数值分析方程求根的迭代法.ppt

数值分析方程求根的迭代法现在学习的是第1页，共43页远在公元前在公元前1700年的古巴比年的古巴比伦人就已有关于一、二次方程的解法。人就已有关于一、二次方程的解法。九章算九章算术(公元前公元前50100年年)其中其中“方程方程术”有有联立一次方程立一次方程组的一般解法。的一般解法。1535年意大利数学家坦特格里年意大利数学家坦特格里亚(TorTaglia)发现了三次方程的解法，卡当了三次方程的解法，卡当(HCardano)从他那里得到了从他那里得到了这种解法，于种解法，于1545年在其名著年在其名著大法大法中公布了三次中公布了三次方程的公式解，称方程的公式解，称为卡当算法。卡当算法。后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更激又提出了四次方程的解法。此成果更激发了了数学家数学家们的情的情绪，但在以后的二个世，但在以后的二个世纪中，求索工作始中，求索工作始终没有成效，没有成效，导致致人人们对高次代数方程解的存在性高次代数方程解的存在性产生了生了怀疑。疑。现在学习的是第2页，共43页1799年，高斯年，高斯证明了代数方程必有一个明了代数方程必有一个实根或复根的定理，称此根或复根的定理，称此为代数基代数基本定理，并由此可以立刻推理本定理，并由此可以立刻推理n次代数方程必有次代数方程必有n个个实根或复根。根或复根。但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到18世世纪，法国数学家拉格朗日用根置法国数学家拉格朗日用根置换方法方法统一了二、三、四方程的解法。一了二、三、四方程的解法。但求解五次方程但求解五次方程时未能如愿未能如愿,开始意开始意识到有潜藏其中的奥妙到有潜藏其中的奥妙,用用现代代术语表示就是表示就是置置换群理群理论问题。在在继续探索探索5次以上方程解的次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿程中，第一个重大突破的是挪威数学家阿贝尔(NAbel1802-1829)1824年阿年阿贝尔发表了表了“五次方程代数解法不可能存在五次方程代数解法不可能存在”的的论文，但并未受到重文，但并未受到重视，连数学大数学大师高斯也未理解高斯也未理解这项成果的重要意成果的重要意义。现在学习的是第3页，共43页1828年年17岁的法国数学家伽的法国数学家伽罗华(EGalois 1811-1832)写出了划写出了划时代的代的论文文“关关于五次方程的代数解法于五次方程的代数解法问题”，指出即使在公式中容，指出即使在公式中容许用用n次方根，并用次方根，并用类似似算法求五次或更高次代数方程的根是不可能的算法求五次或更高次代数方程的根是不可能的文章呈交法文章呈交法兰西科学院后，因西科学院后，因辈份太低遭到冷遇，且文稿份太低遭到冷遇，且文稿丢失。失。1830年伽年伽罗华再再进科学院科学院递稿，得到泊松院士的判稿，得到泊松院士的判词“完全不能理解完全不能理解”。后来伽后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两院，并卷入政事两次入次入狱，被开除学籍，又决斗受，被开除学籍，又决斗受伤，死于，死于1832年。决斗前，他把关于五次代数求年。决斗前，他把关于五次代数求解的研究成果写成解的研究成果写成长信，留了下来。信，留了下来。现在学习的是第4页，共43页十四年后，法国数学家刘十四年后，法国数学家刘维尔(JLiouville)整理并整理并发表了伽表了伽罗华的的遗作，人作，人们才意才意识到到这项近代数学近代数学发展史上的重要成果的宝展史上的重要成果的宝贵。38年后，即年后，即1870年，法国数学家若当年，法国数学家若当(CJordan)在在专著著论置置换与代数方程与代数方程中中阐发了伽了伽罗华的思想，一的思想，一门现代数学的分支代数学的分支群群论诞生了。生了。在前几个世在前几个世纪中，曾开中，曾开发出一些求解代数方程的有效算法，它出一些求解代数方程的有效算法，它们构成构成了数了数值分析中的古典算法。至于超越方程分析中的古典算法。至于超越方程则不存在一般的求根方式。不存在一般的求根方式。现在学习的是第5页，共43页在在科科学学研研究究的的数数学学问题中中更更多多的的是是非非线性性问题，它它们又又常常常常归结为非非线性方程或非性方程或非线性方程性方程组的求解的求解问题。现在学习的是第6页，共43页4.1 方程求根与二分法方程求根与二分法 4.1.1 引言引言（1.1）单变量非量非线性方程的一般形式性方程的一般形式 其中其中也可以是无也可以是无穷区区间.f(x)是是高次多高次多项式函数式函数或或超越函数超越函数（1.2）如果函数如果函数是多是多项式函数，即式函数，即其中其中为实数，数，则称方程称方程(1.1)为次代数方程次代数方程.超越函数超越函数不能表示不能表示为多多项式的函数式的函数如如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2高次代数方程高次代数方程超越方程超越方程现在学习的是第7页，共43页若若是是的的重零点，且重零点，且充分光滑，充分光滑，则次方程在复数域有且只有次方程在复数域有且只有个根（含重根，个根（含重根，重根重根为个根）个根）.超越方程超越方程它在整个它在整个轴上有无上有无穷多个解，若多个解，若取取值范范围不同，解也不同，解也不同，因此不同，因此讨论非非线性方程性方程(1.1)的求解必的求解必须强调的定的定义域，即域，即的求解区的求解区间如果如果实数数满足足，则称称是方程是方程(1.1)的的根根，或称，或称是是的的零点零点.若若可分解可分解为 其中其中为正整数，且正整数，且则称称为方程方程(1.1)的的重根重根，或，或为的的重零点重零点，时为单根根.结论结论现在学习的是第8页，共43页通常方程根的数通常方程根的数值解法大致分解法大致分为三个步三个步骤进行：行：非非线性性问题一般不存在直接的求解公式，要使用迭代法一般不存在直接的求解公式，要使用迭代法.本章将介绍常用的求解非线性方程的近似根的几种数值解法本章将介绍常用的求解非线性方程的近似根的几种数值解法 判定根的存在性。即方程有没有根？如果有根，有几个根？判定根的存在性。即方程有没有根？如果有根，有几个根？判定根的存在性。即方程有没有根？如果有根，有几个根？判定根的存在性。即方程有没有根？如果有根，有几个根？确定根的分布范确定根的分布范确定根的分布范确定根的分布范围围。即将每一个根用区。即将每一个根用区。即将每一个根用区。即将每一个根用区间间隔离开来，隔离开来，隔离开来，隔离开来，这这个个个个过过程程程程实际实际上是上是上是上是获获得方程各根的初始近似得方程各根的初始近似得方程各根的初始近似得方程各根的初始近似值值。根的精确化。将根的初始近似根的精确化。将根的初始近似根的精确化。将根的初始近似根的精确化。将根的初始近似值值按某种方法逐步精确化，直到按某种方法逐步精确化，直到按某种方法逐步精确化，直到按某种方法逐步精确化，直到满满足足足足预预先要求的精度先要求的精度先要求的精度先要求的精度为为止止止止.现在学习的是第9页，共43页如何求方程如何求方程的有根区的有根区间？设 f(x)Ca,b,且且 f(a)f(b)0,存在存在(a,b)，使，使 f()=0.根的存在性定理根的存在性定理闭区间上连续函数的介值定理闭区间上连续函数的介值定理有根区有根区间如果如果f(x)在在a,b上上还是是单调递增增或或递减减的，的，则f(x)=0仅有一有一个个实根。根。(1)描描图法法画出画出y=f(x)的略的略图，从而看出曲，从而看出曲线与与x轴交点的大致位置。也可将交点的大致位置。也可将f(x)=0等价等价变形形为g1(x)=g2(x)的形式，的形式，y=g1(x)与与y=g2(x)两曲两曲线交点交点的横坐的横坐标所在的子区所在的子区间即即为含根区含根区间。例例1 求方程求方程3x-1-cosx=0的有根区的有根区间。方程等价方程等价变形形为3x-1=cosx，y=3x-1与与y=cosx的的图像只有一个交点位于像只有一个交点位于0.5，1内内。现在学习的是第10页，共43页对的根的根进行搜索行搜索计算，算，例例2求方程求方程的有根区的有根区间.由此可知方程的有根区由此可知方程的有根区间为(2)逐步搜索法逐步搜索法 先确定方程先确定方程f(x)=0的所有的所有实根所在的区根所在的区间为a,b,从从x0=a 出出发,以步以步长 h=(b-a)/n 其中其中n是正整数，在是正整数，在a,b内取定内取定节点：点：xi=x0ih (i=0,1,2，n)计算算f(xi)的的值,依据函数依据函数值异号及异号及实根的个数确定有根区根的个数确定有根区间,通通过调整步整步长，总可找到所有有根区可找到所有有根区间。解解 现在学习的是第11页，共43页4.1.2 二分法二分法求解方程求解方程f(x)=0的的近似根近似根的一种常用的的一种常用的简单方法。方法。原理原理基本思想基本思想设函数函数f(x)在在闭区区间a,b上上连续,且且f(a)f(b)0,则 f(x)=0在在(a,b)内必有内必有实根区根区间。逐步将区逐步将区间二等分二等分,通通过判断区判断区间端点端点f(x)的符号的符号,逐步将有根逐步将有根区区间缩小小,直至有根区直至有根区间足足够地小地小,便可求出便可求出满足精度要求足精度要求的近的近似根。似根。具体做法具体做法现在学习的是第12页，共43页以以此此类推推由二分法的由二分法的过程知程知(1)(2)(3)作作为根的近似根的近似可得一个可得一个近似根的序列近似根的序列 现在学习的是第13页，共43页（1.3）且且(4)只要二分足只要二分足够多次（即多次（即充分大），便有充分大），便有 这里里为预定的精度定的精度.要使要使解解：例例3 用二分法求方程用二分法求方程 在区在区间 上的根，上的根，误差限差限为 ，问至少需至少需对分多少次？分多少次？现在学习的是第14页，共43页二分法的算法二分法的算法步步骤1准准备计算算在有根区在有根区间端点端点处的的值 步步骤2二分二分计算算在区在区间中点中点处的的值 步步骤3判断判断若若，则即是根，即是根，计算算过程程结束，否束，否则检验.若若，则以以代替代替，否，否则以以代替代替.此此时中点中点即即为所求近似根所求近似根.误差差，反复反复执行步行步骤2和步和步骤3，直到区，直到区间长度小于允度小于允许现在学习的是第15页，共43页现在学习的是第16页，共43页例例4求方程求方程 在区在区间内的一个内的一个实根，要求准确到小数点后第根，要求准确到小数点后第2位位.欲使欲使只需只需，即只要二分，即只要二分6次，便能达到次，便能达到预定的精度定的精度.解解 得到新的有根区得到新的有根区间现在学习的是第17页，共43页二分法二分法对多个零点的情况，只能算出其中一个零点。多个零点的情况，只能算出其中一个零点。即使即使 f(x)在在a,b上有零点，也未必有上有零点，也未必有 f(a)f(b)0。不管有根区不管有根区间多大多大,总能求出能求出满足精度要求的根足精度要求的根,且且对函数函数f(x)的要求不高的要求不高,只要只要连续即可即可,计算亦算亦简单。优点优点缺点缺点注：注：用二分法求根，最好先给出 f(x)草图以确定根的大概位置。或用搜索程序，将a,b分为若干小区间，对每一个满足 f(ak)f(bk)0 的区间调用二分法程序，可找出区间a,b内的多个根，且不必要求 f(a)f(b)0。现在学习的是第18页，共43页迭代法的基本思想迭代法的基本思想基基本本思思路路同解同解迭代迭代公式公式给定初值给定初值存在存在等价于等价于迭代迭代函数函数？转换是转换是否唯一否唯一几何几何意义意义现在学习的是第19页，共43页转换例子转换例子(1)x=1(x)=x3-6x2+10 x-2;(2);(3);(4);例：已知方程已知方程 x3-6x2+9x-2=0 在在 3,4 内有一根，考内有一根，考虑迭代迭代？哪种转换方法好哪种转换方法好现在学习的是第20页，共43页几何含义几何含义xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 现在学习的是第21页，共43页几何含义几何含义xyy=xxyy=xx*x*y=(x)y=(x)x0p0 x1p1x0p0 x1p1现在学习的是第22页，共43页压缩映像定理压缩映像定理定理定理设设 (x)Ca,b 且可导，若且可导，若(2)0 L 1，使得，使得|(x)|L 对对 x a,b 成立成立(1)a (x)b 对一切对一切 x a,b 都成立都成立则有则有(a)对任意对任意 x0 a,b，由，由 xk+1=(xk)产生的迭代序列产生的迭代序列 均收敛到均收敛到 (x)在在 a,b 中的唯一不动点中的唯一不动点 x*。(b)有如下的误差估计有如下的误差估计可用可用|x k+1-xk|来控制收来控制收敛精度精度L 越小收越小收敛越快越快现在学习的是第23页，共43页压缩映像定理证明压缩映像定理证明(a)由压缩映像定理可知，不动点由压缩映像定理可知，不动点 x*存在且唯一。存在且唯一。现在学习的是第24页，共43页压缩映像定理证明压缩映像定理证明(b)又又现在学习的是第25页，共43页全局收敛与局部收敛全局收敛与局部收敛 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收即迭代的收敛性与初始点的性与初始点的选取无关。取无关。这种在这种在 x*的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件|(x)|L 1 可以适当放宽可以适当放宽(2)(x)在在 x*的某个邻域内连续，且的某个邻域内连续，且|(x*)|1由由 (x)的连续性及的连续性及|(x*)|1 即可推出：即可推出：存在存在 x*的的某个某个 邻域域 N(x*)=x*-,x*+,使得使得对 x N(x*)都有都有|(x)|L 1,则由由 x0 N(x*)开始的迭代开始的迭代都收都收敛。现在学习的是第26页，共43页迭代过程的收敛速度迭代过程的收敛速度定义定义则称该迭代为则称该迭代为 r 阶收敛。(1)当当 r=1 时称为时称为线性收敛，此时，此时 C 1 时称为时称为超线性收敛。二分法线性收敛二分法线性收敛 不动点迭代中，若不动点迭代中，若 (x*)0，则则取极限得取极限得(C为常数为常数)线性收敛线性收敛现在学习的是第27页，共43页P阶收敛阶收敛设迭代设迭代 xk+1=(xk)，若，若 (p)(x)在在 x*的某邻域内连续，则该的某邻域内连续，则该迭代法具有迭代法具有 p 阶收敛的充要条件是阶收敛的充要条件是定理定理并且有并且有证明：充分性充分性.根据泰勒展开有根据泰勒展开有现在学习的是第28页，共43页必要性的证明必要性的证明必要性必要性.设迭代设迭代 xk+1=(xk)是是 p 阶收敛。阶收敛。迭代两边取极限迭代两边取极限，由，由 (x)的连续性可知的连续性可知 x*=(x*)。设设 p0 是满足是满足的最小正整数。的最小正整数。由充分性的证明过程可知迭代由充分性的证明过程可知迭代 p0 阶收敛。阶收敛。又又若若 p0 p，与迭代与迭代 p 阶收敛矛盾阶收敛矛盾p0=p现在学习的是第29页，共43页迭代过程的加速迭代过程的加速 设有不动点迭代：设有不动点迭代：设：设：缺点缺点：每次迭代需每次迭代需计算算现在学习的是第30页，共43页埃特金算法埃特金算法设：设：Aitken 加速加速当当 x收收敛到到 x*时，修正，修正项分子分子趋于零。于零。现在学习的是第31页，共43页一点注记一点注记现在学习的是第32页，共43页Newton迭代 基本思想：基本思想：将非将非线性方程性方程线性化设 xk 是是 f(x)=0 的近似根，的近似根，将将 f(x)在在 xk 一一阶 Taylor 展开展开:，在在 xk 和和 x 之之间。xyx*xkxk+1条件：条件：f(x)0现在学习的是第33页，共43页Newton迭代 Newton 法可以看作下面的不动点迭代：法可以看作下面的不动点迭代：其中其中(x*)=0Newton 法至少法至少 二阶 局部收敛定理定理 设设 f(x)在其零点在其零点 x*的某个邻域内的某个邻域内二阶连续可导二阶连续可导且且 f(x)0，则存在，则存在 x*的的某个某个 邻域邻域 N(x*)=x*-,x*+,使得对使得对 x0 N(x*)，Newton 法产生的序列以法产生的序列以不低于不低于二阶二阶的收敛速度收敛的收敛速度收敛到到 x*。现在学习的是第34页，共43页Newton迭代 Newton 法也可以看作一类特殊的加速迭代法也可以看作一类特殊的加速迭代取取 (x)=x+f(x)现在学习的是第35页，共43页收敛性定理定理定理设设 f C2a,b，且，且 f 满足满足(1)f(a)f(b)0；则则 Newton 法产生的序列收敛到法产生的序列收敛到 f 在在 a,b 的唯一零点的唯一零点 x*。现在学习的是第36页，共43页全局收敛性定理定理定理设设 f C2a,b，且，且 f 满足满足(1)f(a)f(b)0)。解：转化化为求求 x2-a=0 的正根的正根Newton 迭代：迭代：二阶收敛二阶收敛现在学习的是第38页，共43页重根情形 设设 x*是是 f(x)的的 m(m 2)重根，重根，Newton法是否收敛？法是否收敛？Taylor 展式展式Newton 迭代：迭代：线性收敛。线性收敛。且重数且重数 m 越高，收越高，收敛越慢。越慢。现在学习的是第39页，共43页提高收敛阶 提高收敛速度提高收敛速度但但 m 通常无法通常无法预先知道先知道！法一：取法一：取 二阶收敛二阶收敛法二：将求法二：将求 f(x)的重根转化为求的重根转化为求 另一个函数另一个函数 的单根。的单根。构造构造针对 (x)的具有二的具有二阶收收敛的的 Newton 迭代：迭代：令令 ，则，则 x*是是 (x)的单重根。的单重根。现在学习的是第40页，共43页降低初始点的要求例：例：求求 sin(x)-x/6=0 的正根。的正根。Newton 下山法：下山法：k k 为数列为数列 中满足中满足 的最大数。的最大数。算法 7.2(Newton下山法下山法)给定初始点定初始点 x0，精度要求，精度要求 1.如果如果|f(xk)|,停机，停机，输出出 xk2.计算算 ，=13.如果如果|f(xk+dk)|f(xk)|，令，令 xk+1=xk+dk，返回第，返回第1步；步；否否则 折半，重新折半，重新计算第算第3步步Newton法的收法的收敛依依赖于初始点的于初始点的选取。取。现在学习的是第41页，共43页割线法 Newton法的缺点：法的缺点：每步迭代都要每步迭代都要计算算导数数值 只需只需计算函数算函数值，避免，避免计算算导数；数；切切线斜率斜率 割割线斜率斜率xk-1xkxk+1xk+1切切线割割线 需要两个初始点；需要两个初始点；收收敛比比Newton法稍慢，但法稍慢，但对初始点要求同初始点要求同样高。高。现在学习的是第42页，共43页割线法公式 两点割线法 单点割线法现在学习的是第43页，共43页