1、n远在公元前远在公元前1700年的古巴比伦人就已有关于一、二次方程年的古巴比伦人就已有关于一、二次方程的解法。的解法。九章算术九章算术(公元前公元前50100年年)其中其中“方程术方程术”有联立一次方程组的一般解法。有联立一次方程组的一般解法。n1535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)发现了三次方发现了三次方程的解法，卡当程的解法，卡当(HCardano)从他那里得到了这种解法，从他那里得到了这种解法，于于1545年在其名著年在其名著大法大法中公布了三次方程的公式解，中公布了三次方程的公式解，称为卡当算法。称为卡当算法。n后来卡当的学生弗瑞里后来卡当的学生
2、弗瑞里(Ferrari)又提出了四次方程的解法。又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。在性产生了怀疑。n17991799年，高斯证明了代数方程必有一个实根或复根的定理，年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理称此为代数基本定理，并由此可以立刻推理n n次代数方程必次代数方程必有有n n个实根或复根。个实根或复根。n但在以后的几十年中仍然没有找出高
3、次代数方程的公式解。但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到一直到1818世纪，法国数学家拉格朗日用根置换方法统一了世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。二、三、四方程的解法。n但求解五次方程时未能如愿但求解五次方程时未能如愿,开始意识到有潜藏其中的奥妙开始意识到有潜藏其中的奥妙,用现代术语表示就是置换群理论问题。用现代术语表示就是置换群理论问题。n在继续探索在继续探索5 5次以上方程解的艰难历程中，第一个重大突破次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔的是挪威数学家阿贝尔(NAbel1802-1829)1824(NAbel180
4、2-1829)1824年阿贝尔年阿贝尔发表了发表了“五次方程代数解法不可能存在五次方程代数解法不可能存在”的论文，但并未的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。受到重视，连数学大师高斯也未理解这项成果的重要意义。n1828年年17岁的法国数学家伽罗华岁的法国数学家伽罗华(EGalois 1811-1832)写出写出了划时代的论文了划时代的论文“关于五次方程的代数解法问题关于五次方程的代数解法问题”，指出即，指出即使在公式中容许用使在公式中容许用n次方根，并用类似算法求五次或更高次次方根，并用类似算法求五次或更高次代数方程的根是不可能的代数方程的根是不可能的n文章呈交法
5、兰西科学院后，因辈份太低遭到冷遇，且文稿丢文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。失。1830年伽罗华再进科学院递稿，得到泊松院士的判词年伽罗华再进科学院递稿，得到泊松院士的判词“完全不能理解完全不能理解”。n后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于死于1832年。决斗前，他把关于五次代数求解的研究成果年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。写成长信，留了下来。n十四年后，法国数学家刘维
6、尔十四年后，法国数学家刘维尔(JLiouville)整理并发表了整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。要成果的宝贵。n38年后，即年后，即1870年，法国数学家若当年，法国数学家若当(CJordan)在专著在专著论置换与代数方程论置换与代数方程中阐发了伽罗华的思想，一门现代中阐发了伽罗华的思想，一门现代数学的分支数学的分支群论诞生了。群论诞生了。n在前几个世纪中，曾开发出一些求解代数方程的有效算法，在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存它们构成
7、了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。在一般的求根方式。在科学研究的数学问题中更多的是非线性问题，它们又在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。常常归结为非线性方程或非线性方程组的求解问题。第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法/*Numerical Solutions of Nonlinear Equations*/7.1 方程求根与二分法方程求根与二分法 7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 7.3 迭代收敛的加速方法迭代收敛的加速方法 7.4 牛顿法牛顿法 7.5
8、 弦截法与抛物线法弦截法与抛物线法 7.6 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点7.7 非线性方程组的数值解法非线性方程组的数值解法7.1 方程求根与二分法方程求根与二分法 7.1.1 引言引言0)(xf（1.1）单变量单变量非线性非线性方程的一般形式方程的一般形式 其中其中 也可以是无穷区间也可以是无穷区间.,)(,RbabaCxfx),0()(01110 aaxaxaxaxfnnnn（1.2）如果函数如果函数 是多项式函数，即是多项式函数，即)(xf其中其中 为实数，则称方程为实数，则称方程(1.2)(1.2)为为 次代数方程次代数方程.),1,0(,00niaai
9、n超越函数超越函数 不能表示为多项式的函数不能表示为多项式的函数如如 (x)=3x5-2x4+8x2-7x+1=0 (x)=e2x+1-xln(sinx)-2=0高次代数方程高次代数方程超越方程超越方程代数方程与超越方程代数方程与超越方程方程的根与函数的零点方程的根与函数的零点如果实数如果实数 满足满足 ，*x0*)(xf0)(xf（1.1）)(xf*x*x则称则称 是方程是方程(1.1)(1.1)的的根根，或称，或称 是是 的的零点零点.若若 可分解为可分解为 )(xf),(*)()(xgxxxfm 其中其中 为正整数，为正整数，m.0*)(xg则称则称 为方程为方程(1.1)(1.1)的的
10、 重根重根，或，或 为为 的的 重零点重零点，*xm*x)(xfm1m 时为时为单根单根.若若 是是 的的 重零点，且重零点，且 充分光滑，则充分光滑，则*x)(xfm)(xg,0*)(*)(*)()1(xfxfxfm.0*)()(xfm结论结论 次方程在复数域有且只有次方程在复数域有且只有 个根（含重根，个根（含重根，重根为重根为 个根）个根）.mmnn 设设 f(x)Ca,b,且且 f(a)f(b)0,至少存在至少存在(a,b)，使，使 f()=0.根的存在性定理根的存在性定理闭区间上连续函数的介值定理闭区间上连续函数的介值定理如果如果f(x)在在a,b上上单调递增单调递增或或递减递减的，
11、则的，则f(x)=0仅有一个实根。仅有一个实根。有根区间有根区间通常方程根的数值解法大致分为通常方程根的数值解法大致分为2个步骤进行：个步骤进行：本章将介绍常用的求解非线性方程的近似根的几种数值解法本章将介绍常用的求解非线性方程的近似根的几种数值解法 如何求方程如何求方程 的有根区间？的有根区间？0)(xf(1)(1)描图法描图法画出画出y=f(x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的大致位置。轴交点的大致位置。例例1 1 求方程求方程3 3x-1-1-cosx=0 0的有根区间。的有根区间。方程等价变形为方程等价变形为3 3x-1=-1=cosx，y=3 3x-1-1与与y
12、=cosx的图像只有一个交点位于的图像只有一个交点位于0.50.5，11内内。将将f(x)=0)=0等价变形为等价变形为g1 1(x)=)=g2 2(x)的形式，的形式，y=g1 1(x)与与y=g2 2(x)两曲线交点的横坐标所在的子区间即为有根区间。两曲线交点的横坐标所在的子区间即为有根区间。(2)解析法解析法根据函数的连续性、介值定理和单调性寻找有根区间和唯一根据函数的连续性、介值定理和单调性寻找有根区间和唯一根的区间。根的区间。对对 的根进行搜索计算，的根进行搜索计算，0)(xf 例例2 2 求方程求方程 的有根的有根区间区间.077.418.381.11)(23xxxxf的符号计算结
13、果表)(6543210 1-7xfx由此可知方程的有根区间为由此可知方程的有根区间为 .6,5,4,3,2,1(3)定步长搜索法定步长搜索法 在某一区间在某一区间a,b上上,从从x0=a 出发出发,以步长以步长 h=(b-a)/n 其中其中n是正整数，在是正整数，在a,b内取定节点：内取定节点：xi=x0ih (i=0,1,2，)考察函数值考察函数值f(xi)的符号的符号,当当f(x)连续且连续且f(xi).f(x i+1)0，则区则区间间xi,x i+1为有根区间为有根区间,若导数不变号有唯一根。若导数不变号有唯一根。解解 7.1.2 二分法二分法/*Bisection Method*/求解
14、方程求解方程f(x)=0的的近似根近似根的最直观、最简单方法。的最直观、最简单方法。原理原理基本思想基本思想设函数设函数f(x)Ca,b上连续上连续,且且f(a)f(b)0,则则 f(x)=0在在(a,b)内至少存在一个根。内至少存在一个根。逐步将区间二等分逐步将区间二等分,通过判断区间端点通过判断区间端点f(x)的符号的符号,将有根区将有根区间缩小间缩小,直至有根区间足够地小直至有根区间足够地小,便可求出便可求出满足精度要求满足精度要求的的近似根。近似根。具体做法具体做法)(xfy aboxy x 20bax 1b 1112xba 2a 3a 1a2222xba 2b3b11,a b22,a
15、 b33,a b以此类推以此类推由二分法的过程知由二分法的过程知,2211 kkbabababa,0)().(*kkkkbaxbfaf (1)kkkkkababab2211 (2)(3)2kkkbax 作为作为根的近似根的近似近似根的序列近似根的序列,210kxxxx2/)(*kkkabxx（1.3）,2/)(1kab且且(4)只要二分足够多次（即只要二分足够多次（即 充分大），便有充分大），便有 k,*kxx这里这里 为为预定的精度预定的精度.12lnln)ln(abk,*kxx要使要使解解：211 510,.;ab，21 5 11012ln(.)lnln 4.64例例3 用二分法求方程用二
16、分法求方程 在区间在区间 上的根，误差上的根，误差限为限为 ，问至少需对分多少次？，问至少需对分多少次？310 xx 1 1 5,.210 12lnln)ln(abk5 k y n 开 始 输 入 a,b,(a+b)/2 x f(a)f(x)0?xb x a|b-a|0 输 出 x 结 束 y n 二分法的算法二分法的算法例例4 求方程求方程 01)(3xxxf在区间在区间 内的一个实根，要求准确到小数点后第内的一个实根，要求准确到小数点后第2 2位位.5.1,0.1欲使欲使5.1,0.1ba0)(,0)(bfaf25.10 x只需只需 ，即只要二分，即只要二分6 6次，便能达到预定的精度次，
17、便能达到预定的精度.6k2/)(*kkkabxx12/)(kab,005.021211k 解解 0)(0 xf5.1,25.1101bbxa.,11ba得到新的有根区间得到新的有根区间 3242.13203.063203.13281.153281.13438.143438.13125.133125.1375.12375.125.1125.15.10.10)(符符号号kkkkxfxbak二分法对多个零点的情况，只能算出其中一个零点。二分法对多个零点的情况，只能算出其中一个零点。即使即使 f(x)在在a,b上有零点，也未必有上有零点，也未必有 f(a)f(b)0。不管有根区间多大不管有根区间多大,
18、总能求出满足精度要求的根总能求出满足精度要求的根,且对函数且对函数f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算亦简单。计算亦简单。优点优点缺点缺点用二分法求根，最好先给出用二分法求根，最好先给出 f(x)草图以确定根的大草图以确定根的大概位置。或用搜索程序，将概位置。或用搜索程序，将a,b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f(ak)f(bk)0 的区间调用二分法程序，可找出区的区间调用二分法程序，可找出区间间a,b内的多个根，且不必要求内的多个根，且不必要求 f(a)f(b)0。7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 迭代法迭代法逐次逼近的
19、方法逐次逼近的方法 首先取一个粗糙的近似值，然后用同一个递推公式，反复首先取一个粗糙的近似值，然后用同一个递推公式，反复校正这个初值，直到满足预先给出的精度要求为止。校正这个初值，直到满足预先给出的精度要求为止。如何构造一个合适的递推公式？如何构造一个合适的递推公式？7.2.1 不动点与不动点迭代法不动点与不动点迭代法/*Fixed-Point Iteration*/).(xx (2.1)0)(xf若若 满足满足 ，则则 ；反之亦然，称反之亦然，称为函数为函数 的一个的一个不动点不动点.*x0*)(xf*)(*xx*x)(x已知方程已知方程 在区间在区间a,b 内有一个根内有一个根x*，在区间
20、，在区间a,b0)(xf 求求 的的零点零点就就等价于等价于求求 的的不动点不动点.)(xf)(x).,1,0()(1kxxkk(2.2)称为称为迭代函数迭代函数.)(x迭代格式迭代格式,)(baCx 格式的收敛性格式的收敛性.*limxxkk得到序列得到序列 有极限有极限 0kkx,0bax 如果对任何如果对任何 ，由迭代，由迭代).,1,0()(1 kxxkk 不动点迭代法不动点迭代法且且 为为 的的不动点不动点。*)(*xx)(x 不动点迭代不动点迭代是一种是一种逐次逼近逐次逼近的方法的方法,用某个固定公式用某个固定公式反复校正反复校正根的近似值根的近似值,使之逐步精确化，最后得到满足精
21、度要求的结果。使之逐步精确化，最后得到满足精度要求的结果。对预先给定的精度要求对预先给定的精度要求，只要某个只要某个k满足满足 1kkxx即可结束计算并取即可结束计算并取 kxx*迭代终止的判定迭代终止的判定则称则称迭代法收敛迭代法收敛，例例5 求方程求方程 01)(3xxxf(2.3)在在 附近的根附近的根 5.10 x.*x13 xx解解构造迭代格式。构造迭代格式。方法一：方法一：),2,1,0(131 kxxkk取迭代函数取迭代函数1)(31 xx 构造迭代格式构造迭代格式取初值取初值5.10 x002.1904396.12375.25.13210kxk发散发散方法二：方法二：取迭代函数
22、取迭代函数321)(kxx 构造迭代格式构造迭代格式取初值取初值5.10 x31 xx),2,1,0(131 kxxkk32494.1432472.1832588.1332472.1733086.1232473.1635721.1132476.155.1037kkxkxk表 即为所求的根即为所求的根.7x如果仅取如果仅取6 6位数字，位数字，结果结果 与与 完全相同，完全相同，7x8x说明：迭代函数不唯一，迭代点列可能收敛，也可说明：迭代函数不唯一，迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初能发散，迭代收敛与否不仅与迭代函数有关，还与初始点有关。始点有关。不动点迭代的
23、几何解释不动点迭代的几何解释*x交点的横坐标交点的横坐标 )()(xyxyxx y=x2x0 x1x)(xy )(0 x)(1x)(2x xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p17.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 不动点的存在不动点的存在唯一性定理唯一性定理 定理定理1,2 设设 满足以下两个条件：满足以下两个条件：,)(baCx 1.对任意对任意 有有 ,bax bxa )(2.存在正常数存在正常数 ，使对任意使对任
24、意 都有都有 1 L,bayx.)()(yxLyx(2.4)则则(1)(1)在在 上存在唯一的不动点上存在唯一的不动点 )(x,ba.*x.1*01xxLLxxkk (2.5)kx得到的迭代得到的迭代序列序列(2)(2)对任意对任意 ，由，由,0bax),1,0()(1 kxxkk)(x*x收敛到收敛到 的不动点的不动点 ，并有误差估计并有误差估计 L L 越越 收敛越快收敛越快小小事前估计：选取事前估计：选取k，预先估计迭代次数。预先估计迭代次数。定义函数定义函数.)()(xxxf显然显然 ，,)(baCxf,0)()(aaaf且且,0)()(bbbf由零点定理知存在由零点定理知存在 ,),
25、(*bax*),(*xx使使 ,0*)(xf即即唯一性唯一性 设设 都是都是 的不动点，的不动点，,21baxx)(x)()(2121xxxx故故 的不动点是唯一的的不动点是唯一的.)(x则由则由.2121xxxxL.)()(yxLyx即为即为 的不动点的不动点.)(x*x得得矛盾矛盾.证明证明(1)(1)若若 或或 ，则不动点为则不动点为 或或 ，aa)(bb)(ab 因因 ，bxa)(以下设以下设 及及 ，aa)(bb)(存在性存在性(2)(2)设设 是是 在在 上的唯一不动点，上的唯一不动点，,ba,*bax)(x,baxk由条件，可知由条件，可知*)()(*1xxxxkk 因因 ，故当
26、故当 时序列时序列 收敛到收敛到 .10 Lkkx*x*1xxLk .*0 xxLk .)()(yxLyx 又由又由误差估计误差估计收敛性收敛性由由.)()(yxLyx)()(211 kkkkxxxx （2.6）.21 kkxxL得得反复递推得反复递推得 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1(kkkxxLxxL1*1 kkkxxLLxx.1*01xxLLxxkk 迭代过程的控制迭代过程的控制只要相邻两次计算结果的偏差只要相邻两次计算结果的偏差 足够小，即可保证足够小，即可保证 1 kkxx近似值近似值 具有足够精度具有足够精度.kx011*xxLLxxkk 事后估计事后估计事前估计：选取事前估计：选取k，预先估计迭代次数。预先估计迭代次数。1*1 kkkxxLLxx注：注：定理定理1 1、2 2的条件的条件(2)(2)可替换为可替换为,1)(Lx(2.7)如果如果 且对任意且对任意 有有 ,bax,)(1baCx 则由中值定理可知对则由中值定理可知对 有有 ,bayx)()()(yxyx).,(,bayxL
