数值分析 第七章 非线性方程（组）的数值解法

数值分析 Numerical Analysis第七章 非线性方程（组）的数值解 法郑州大学研究生课程 （2014-2015学年第一学期） ISCM 2007,Beijing China1第七章 非线性方程（组）的数值解法§7.1 引言 §7.2 二分区间法 §7.3 迭代法及其加速 §7.4 牛顿迭代法 §7.5 弦截法 §7.6 解非线性方程组的迭代解法ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.1 引言在科学研究和工程设计中, 经常会遇到的一大类 问题是非线性方程 f (x)=0 的求根问题，其中f (x)为非 线性函数。方程f ( x) =0的根, 亦称为函数 f(x) 的零点。 非线性方程的例子 （1）在光的衍射理论中,需要求x-tanx=0的根 （2）在行星轨道的计算中, 需要求x-asinx=b的根ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.1 引言当 f (x)不是x的线性函数时，称对应的函数方程f (x)=0为非线性方程。 如果 f(x)是多项式函数，则称为代数方程。 否则为超越方程（三角方程，指数、对数方程 等）。一般称n次多项式构成的方程 为n次代数方程,当n1时,方程显然是非线性的ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.1 引言如果f (x)可以分解成 ,其中m为 正整数且 ,则称x*是f(x)的m重零点,或 称方程f (x)=0的m重根。当m=1时称x*为单根。求方程根的问题，就几何上讲,是求曲线 y=f (x)与 x轴交点的横坐标。ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.1 引言Ø 公元前1700年的古巴比伦人有关于一、二次代数方程的解 法。九章算术(公元前50100年)其中“方程术”有联 立一次方程组的一般解法。Ø 1535年意大利数学家坦特格里亚(TorTaglia)发现了三次代数 方程的解法，卡当(H·Cardano)从他那里得到了这种解法 ，于1545年在其名著大法中公布了三次方程的公式解 ，称为卡当算法。Ø 后来卡当的学生弗瑞里(Ferrari)又提出了四次代数方程的解 法。此成果更激发了数学家们的情绪，但在以后的二个世 纪中，求索工作始终没有成效，导致人们对高次代数方程 解的存在性产生了怀疑。代数方程求根的历史ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.1 引言代数方程求根的历史Ø 1799年，高斯证明了代数方程必有一个实根或复根的定理 ，称此为代数基本定理，并由此可以立刻推理n次代数方 程必有n个实根或复根。 Ø 但在以后的几十年中仍然没有找出高次代数方程的公式解 。一直到18世纪，法国数学家拉格朗日用根置换方法统一 了二、三、四次方程的解法。 Ø 在继续探索5次以上方程解的艰难历程中，第一个重大突 破的是挪威数学家阿贝尔(N·Abel1802-1829) 1824年阿 贝尔发表了“五次方程的代数解法不可能存在”的论文， 但并未受到重视，连数学大师高斯也未理解这项成果的重 要意义。ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.1 引言代数方程求根的历史Ø1828年17岁的法国数学家伽罗华(E·Galois 1811-1832)写 出了划时代的论文“关于五次方程的代数解法问题”，指 出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的。”，Ø“他一劳永逸地发现了一个折磨了数学家几个世纪的谜团的答案：在什么条件下一个方程有解？” ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.1 引言理论上已证明，对于次数n0在区间（0，2）内至少有一个实根设从x=0出发,取h=0.5为步长向右进行根的搜索,列表如下确定有根区间的方法ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 区间法xf(x)0 0.5 1.0 1.5 2 + + 可以看出，在1.0,1.5内必有一根确定有根区间的方法ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法二分法求根过程 取有根区间a,b之中点, 将它分为两半,分点,这样就可得缩小有根区间ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法 对压缩了的有根区间 施行同样的手法,即取中点 ,将区间 再分为两半,然后再确定有根区间 ,其长度是 的二分之一。ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法 如此反复下去,若不出现 ,即可得出一系列有根区间序列：上述每个区间都是前一个区间的一半,因此的长度当k时趋于零,这些区间最终收敛于一点x* 即为所求的根 。ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法每次二分后,取有根区间 的中点作为根的近似值，得到一个近似根的序列该序列以根x*为极限只要二分足够多次(即k足够大),便有这里为给定精度,由于 ,则 ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法当给定精度0后,要想 成立,只要取k满足 即可，亦即当: 时,做到第K+1次二分,计算得到的 就是 满足精度要求的近似根 。ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis二分区间法算法实现ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis例7.2.2 证明方程 在区间2, 3内有一 个根 , 使用二分法求误差不超过0.5×10-3 的根要二分多少次？证明 令 且f(x)在2, 3上连续,故方程f(x)=0在2,3内至少 有一个根。又 当时 时， ,故f(x)在2, 3上是单调递增函数, 从而f(x)在2, 3上有且仅有一根。给定误差限 0.5×10-3 ,使用二分法时ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法误差限为 只要取k满足 即可，亦即 所以需二分10次便可达到要求。ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.2 二分区间法二分法的优点不管有根区间 多大,总能求出满足精度要求的 根,且对函数f(x)的要求不高,只要连续即可,计算亦简单; 二分法的局限性只能用于求函数的实根,不能用于求复根及偶数重根 ,它的收敛速度与比值为 的等比级数相同。 ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis例7.2.3 求方程f(x)= x 3 e-x =0的一个实根。因为 f(0)0。 故f(x)在(0,1)内有根 用二分法解之，(a,b）=（0,1)计算结果如表： kak bk xk f(xk)符号 00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，误差为| x* -x10|0），使 迭代法的收敛速度则称序列 是 p 阶收敛的,c称渐近误差常数 。特别地,p=1时称为线性收敛,p=2时称为平方 收敛。1 0xn+1X*ayx0Bf´´(x)>0a=x0yx0B=x0f´´(x)<0ayx0Bf´´(x)<0a =x0牛顿迭代法的收敛性ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis§7.4 牛顿(Newton)迭代法牛顿迭代法对初值x0的选取要求比较高。 x0必须充 分靠近x*才能保证局部收敛。定理7.4.2 如果在有根区间a,b上连续且不变号，在a,b上取初始近似根x0满足，则牛顿迭代法产生的迭代序列单调收敛于方程 f(x)=0在该区间上的唯一解。ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis结论：结论：Newton法的收敛性依赖于x0 的选取。x*x0x0x0不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysis牛顿迭代法的算法实现ISCM 2007,Beiji ng China2014-2015学年课程 数值分析 Numerical Analysisq 牛顿法的优点q 牛顿法是目前求解非线性方程 (组) 的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭 代点充分靠近精确解时。可求重根和复根。q 牛顿的缺点 l 对重根收敛速度较慢（线性收敛）l 对初值的