第三章 方程(组)的迭代解法

1、3 方程（组）的迭代解法方程（组）的迭代解法 3.1 3.1 引言引言0)(xf（3.1.1） 本章主要讨论求解单变量非线性方程本章主要讨论求解单变量非线性方程 其中 也可以是无穷区间. ,)(,RbabaCxfx 如果实数 满足 ，则称 是方程(3.1.1)的根根，或称 是 的零点零点.*x)(xf0*)(xf*x*x1 1根的存在性。方程有没有根？如果有，有几个根？根的存在性。方程有没有根？如果有，有几个根？2 2根的搜索。这些根大致在哪里？如何把根隔离开？根的搜索。这些根大致在哪里？如何把根隔离开？3 3根的精确化（误差）。根的精确化（误差）。问题问题: : 公元前1700年的古巴比伦人

2、就已有关于一、二次方程的解法。 九章算术(公元前50100年)其中“方程术”有联立一次方程组的一般解法。 1535年意大利数学家尼柯洛冯塔纳找到了一元三次方程一般形式的求根方法。这个成就，使他在几次公开的数学较量中大获全胜，从此名扬欧洲。但是冯塔纳不愿意将他的这个重要发现公之于世. 当时的另一位意大利数学家兼医生卡尔丹诺，对冯塔纳的发现非常感兴趣。他几次诚恳地登门请教，希望获得冯塔纳的求根公式。后来，冯塔纳终于用一种隐晦得如同咒语般隐晦得如同咒语般的语言，把三次方程的解法“透露”给了卡尔丹诺。冯塔纳认为卡尔丹诺很难破解他的“咒语”，可是卡尔丹诺通过解三次方程的对比实践，很快就彻底破译了冯塔纳的

3、秘密。 卡尔丹诺把冯塔纳的三次方程求根公式，写进了自己的学术著作大法大法中，但并未提到冯塔纳的名字。 由于第一个发表三次方程求根公式的人确实是卡尔丹诺，因此后人就把这种求解方法称为“卡尔丹诺公式”。 l后来，卡尔丹诺的学生弗瑞里(Ferrari)又提出了四次方程的解法。l但对于五次方程求根，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。l1828年17岁的法国数学家伽罗华(EGalois 1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的l 文章呈交法兰西科学院后，因辈份太低

4、遭到冷遇，且文稿丢失。1830年伽罗华再进科学院递稿，得到泊松院士的判词“完全不能理解完全不能理解”。l 后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于1832年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。l 十四年后，法国数学家刘维尔(JLiouville)整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。l38年后，即1870年，法国数学家若当(CJordan)在专著论置换与代数方程中阐发了伽罗华的思想，一门现代数学的分支 群论群论诞生了。l在前几个世纪中，曾开发出一些求解代数方程的有效

5、算法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。1.1.根的存在性根的存在性定理定理1：设函数设函数 f (x) 在区间在区间a, b上连续上连续，如果如果f (a) f (b) 0， 则方程则方程 f (x) = 0 在在a, b内至少有一实根内至少有一实根x*。 定义定义：如果存在如果存在 使得使得 ，则称，则称 为为方程（方程（3.1.13.1.1）*x0)(*xf的根的根或或函数函数 的零点的零点。)(xf*x0)(xf（3.1.1）m m重根重根若若)()()(*xgxxxfm其中，其中，mxg, 0)(*为正整数，为正整数，则当则当m=1m=1时，时，称称

6、 为为方程（方程（3.1.13.1.1）*x的的 m m重根重根或或函数函数 的的m m重零点。重零点。)(xf2m的单根的单根或或函数函数 的单零点的单零点。)(xf称称 为为方程（方程（3.1.13.1.1）*x当当 时时，0)(xf（3.1.1）2. 根的搜索根的搜索(1) 图解法（利用作图软件如图解法（利用作图软件如 Matlab)(2) 扫描法（逐步搜索法）扫描法（逐步搜索法）(3) 二分法二分法* （1） (描描)做图法做图法 画出画出 y=f(x) 的草图的草图, 由由f(x)与横轴交点的大概位置与横轴交点的大概位置来确定来确定隔根区间隔根区间; 或者利用导函数或者利用导函数f

7、(x)的正、负与函的正、负与函数数f(x)的单调性的关系确定根的大概位置的单调性的关系确定根的大概位置. 若若f(x)比较复杂比较复杂, 还可将方程还可将方程f(x)=0化为一个等价化为一个等价方程方程 (x)= (x), 则曲线则曲线y= (x)与与y= (x)之之交点交点A(x*,y*)的的横坐标横坐标 x*即为原方程之根即为原方程之根, 据此也可通过作图求得据此也可通过作图求得x*的的隔根区间隔根区间. 10 xxxyxy1lgxx1lgxy1gxy 023yxabx*f(x)0 x1画出画出 f(x) 的略图，从而看出曲线与的略图，从而看出曲线与x 轴交点的位置。轴交点的位置。2从左端

8、点从左端点x = a出发，按某个预先选定的步长出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点一步一步地向右跨，每跨一步都检验每步起点x0和终点和终点x0 + h的函数值，若的函数值，若0)()(00hxfxf那么所求的根那么所求的根x*必在必在x0与与x0+h之间，这里可取之间，这里可取x0或或x0+h作为根的初始近似。作为根的初始近似。hx 0(2) 扫描法（逐步搜索法）扫描法（逐步搜索法）例例1 1：考察方程：考察方程01)(3xxxfx00.51.01.5f (x) 的符号的符号（3） 二分法二分法*（对分法）（对分法） 设设f(x)在区间在区间a, b上连续上连续

9、, f(a)f(b)0, 则在则在a, b 内有方程的根内有方程的根. 取取a, b的中点的中点 将区间一分为二将区间一分为二. 若若 f (x0)=0, 则则x0就是方程的根就是方程的根, 否则判别根否则判别根 x*在在 x0 的的左侧左侧还是还是右侧右侧., )(210bax 若若f(a) f(x0)0, 则则x*(a, x0), 令令 a1= a, b1=x0;若若f(x0) f(b)0, 则则x*(x0 , b), 令令 a1=x0, b1=b. . 不论出现哪种情况不论出现哪种情况, (a1, b1)均为均为新的有根区间新的有根区间, 它它的的长度只有原有根区间长度的一半长度只有原有

10、根区间长度的一半, 达到了达到了压缩有根压缩有根区间区间的目的的目的. 对压缩了的有根区间对压缩了的有根区间, 又可实行同样的步骤又可实行同样的步骤, 再压再压缩缩. 如此反复进行如此反复进行, 即可的一系列即可的一系列有根区间套有根区间套 ,11nnbababa 由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间an , bn的长度为的长度为)(ababnnn 21若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去. 当当 n 时，区间必将最终收缩为一时，区间必将最终收缩为一点点x* ，显然，显然

11、x*就是所求的就是所求的根根.误差误差 分析：分析：第第1步产生的步产生的21bax 有误差有误差21abx*|x 第第 k 步产生的步产生的 xk 有误差有误差kkabx*|x2 对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k ： 2lnlnln2abkabk 简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 2.由于在偶重根附近曲线由于在偶重根附近曲线 y=f(x) 为上凹或下凸为上凹或下凸, 即即 f(a)与与f(b)的符号相同的符号相同, 因此因此不能用二分法求偶重根不能用二

12、分法求偶重根.用二分法求根，最好先给出用二分法求根，最好先给出 f (x) 草图以确定根草图以确定根的大概位置。或用搜索程序，将的大概位置。或用搜索程序，将a, b分为若干小分为若干小区间，对每一个满足区间，对每一个满足 f (ak)f (bk) 0 的区间调用二的区间调用二分法程序，可找出区间分法程序，可找出区间a, b内的多个根，且不必内的多个根，且不必要求要求 f (a)f (b) 0 。 二分法的执行步骤二分法的执行步骤1计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x1)。3判断若

13、判断若f (x1) = 0，则则x1即是根，否则检验即是根，否则检验：（1）若若f (x1)与与f (a)异号异号，则知解位于区间则知解位于区间a, x1， b1=x1, a1=a;（2）若若f (x1)与与f (a)同号同号，则知解位于区间则知解位于区间x1, b， a1=x1, b1=b。反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：1122 , ,nna ba ba ba b4、当当11kkab时，停止；时，停止；)(211kkkbax即为根的近似。即为根的近似。当当 n 时，时， 0nnba，即这些区间必将收缩于一点，也就是，即这些区间必将收缩于一点，也

14、就是方程的根。在实际计算中，只要方程的根。在实际计算中，只要 ,nna b的区间长度小于预定容的区间长度小于预定容许误差许误差就可以停止搜索，即就可以停止搜索，即 2nba然后取其中点然后取其中点 nx作为方程的一个根的近似值。作为方程的一个根的近似值。 注：注： 例例2 证明方程证明方程 1020 xex存在唯一的实根存在唯一的实根 *(0,1)x 用二分法用二分法 求出此根，要求误差不超过求出此根，要求误差不超过 20.5 10。解：记解：记 ( )102xf xex，则对任意，则对任意 xR( )100 xfxe ，因而，因而， ( )f x是严格单调的，是严格单调的， ( )0f x

15、最多有一个根，最多有一个根，(0)10,(1)80ffe 所以，所以， ( )0f x 有唯一实根有唯一实根 *(0,1)x 又因为又因为 用二分法求解，要使用二分法求解，要使 *20.5 10kxx，只要，只要 21100.5 102k解得解得 26.64lg2k ，取，取 7k 。所以只要二等分。所以只要二等分7次，即可求得满次，即可求得满足精度要求的根。计算过程如下表所示足精度要求的根。计算过程如下表所示 k f(ak)及符号及符号f(xk)及符号及符号f(bk)及符号及符号01234 5670()0()0()0()0.0625()0.0625()0.078125()0.0859375(

16、)0.5(+)0.25(+)0.125(+)0.0625()0.09375(+)0.078125()0.0859375()1( + )0.5( + )0.25( + )0.125( + )0.125( + )0.09375( + )0.09375( + )0.09375( + )表表3.1所以，所以， *0.5 (0.08593750.09375)0.09x 问题问题 虽然二分法计算简单，能够保证收敛，但是它对于方程虽然二分法计算简单，能够保证收敛，但是它对于方程单根存在区域信息要求太高，一般情况下很难实现，并单根存在区域信息要求太高，一般情况下很难实现，并且不能求偶重根、复根和虚根。在实际应

17、用中，用来求且不能求偶重根、复根和虚根。在实际应用中，用来求解方程根的主要方法是迭代法。解方程根的主要方法是迭代法。使用迭代法求解非线性代数方程的步骤为：使用迭代法求解非线性代数方程的步骤为：(1) 迭代格式；迭代格式；(2) 迭代格式的收敛性的构造分析；迭代格式的收敛性的构造分析；(3) 迭代格式的收敛速度与误差分析。迭代格式的收敛速度与误差分析。 3.2 迭代法及其收敛性3.2.1 不动点迭代法不动点迭代法 将方程将方程f(x)=0改写为等价方程形式改写为等价方程形式 x= (x). (3.2.1)若要求若要求x*满足满足f(x*)=0，则，则x*= (x*)；反之亦然，称；反之亦然，称x

18、*为为函数函数 (x)的一个的一个不动点不动点. 求求f(x)的零点就等于求的零点就等于求 (x)的的不动点不动点，选择一个初始近似值，选择一个初始近似值x0，将它代入，将它代入(3.2.1)右右端，即可求得端，即可求得 x1= (x0). .lim xxkk可以如此反复迭代计算可以如此反复迭代计算 xk+1= (xk) (k=0,1,2,). (3.2.2) (x)称为迭代函数称为迭代函数. 如果对任何如果对任何x0a, b，由，由(3.2.2)得得到的序列到的序列xk有极限有极限则称迭代方程则称迭代方程(3.2.2)收敛收敛. 且且x*= (x*)为为 (x)的的不动点不动点，故称故称(3

19、.2.2)为为不动点迭代法不动点迭代法. 上述迭代法是一种逐次逼近法，其基本思想是将上述迭代法是一种逐次逼近法，其基本思想是将隐式方程隐式方程(3.1.1)归结为一组显式的计算公式归结为一组显式的计算公式(3.2.2)，迭代过程实质上是一个逐步显式化过程迭代过程实质上是一个逐步显式化过程.当当 (x)连续时，连续时，显然显然x*就是方程就是方程x= (x)之之根根(不动点不动点). 于是可以从数列于是可以从数列xk中求得满足精度要求的近似根中求得满足精度要求的近似根. 这种求根方法这种求根方法称为称为不动点迭代法不动点迭代法, 1()(0,1,2,)kkxxk 称为称为迭代格式迭代格式, (x

20、)称为称为迭代函数迭代函数, x0 称为称为迭代初值迭代初值,数列数列xk称为称为迭代序列迭代序列. 如果迭代序列收敛如果迭代序列收敛, 则称迭则称迭代格式代格式收敛收敛,否则称为否则称为发散发散. 1()(0,1,2,)kkxxk .lim xxkk3.2.2 迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(xf(x)=0)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种, ,有的收敛有的收敛, ,有的不收敛有的不收敛, ,这取决于这取决于 的性态的性态, ,方程方程 的求根问题在几何上就是确定曲的求根问题在几何上就是确定曲线线y= 与直线与直线y=x的交点的交

21、点P*的横坐标的横坐标)(xx)(x)(xx)(xxyy = 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 x1p1例例3：求方程求方程0210)(xxxf的一个根的一个根.210 xxlg(2)xx构造迭代格式构造迭代格式)2lg(1kkxxx1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.3758解：解：1020 xx给定初始点给定初始点10.4771x 03224xxx分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公

22、式，并取x0=1进行进行迭代计算，结果如下：迭代计算，结果如下：14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 解解 对方程进行如下三种变形：对方程进行如下三种变形： 例例3 用迭代法求方程用迭代法求方程x4+2x2- -x- -3=0 在区间在区间1, 1.2内的实根内的实根.准确根准确根 x* = 1.124123029, 可见可见迭代公式不同迭代公式不同, 收敛情收敛情况也不同况也不同. 第二种公式比第一种公式收敛快得多第二种公式比第一种公式收敛快得多, 而而第三种公式第三种公式不收敛不收敛.73496,8.49530710 xx12()41kkkxxx 42

23、13()23kkkkxxxx 12411()(32)kkkkxxxx 26271.124123xx671.124123xx 例例3 表明原方程化为表明原方程化为 x= (x) 的形式不同，有的的形式不同，有的收敛，有的不收敛，有的发散，只有收敛的的迭代收敛，有的不收敛，有的发散，只有收敛的的迭代过程过程xk+1= (xk) (k=0,1,2,)才有意义，为此我们首先才有意义，为此我们首先要研究要研究 (x)的不定点的存在性及迭代法的不定点的存在性及迭代法xk+1= (xk)的的收敛性收敛性.3.2.3 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察首先考察 (x)在在a

24、, b上不动点的存在唯一性上不动点的存在唯一性. 定理定理1 设设 (x)Ca, b满足以下两个条件：满足以下两个条件：1 对任意对任意xa, b有有a (x)b. .( )( ).(3.2.3)xyL xy2 存在正数存在正数La及及 (b)0, f(b)= (b)- -b0, 由连续函数性质可知存在由连续函数性质可知存在 x*(a, b) 使使 f(x*)=0，即，即x*= (x*)，x*即为即为 (x)的不动点的不动点. 再证不动点的再证不动点的唯一性唯一性. 设设x1*, x2*a, b都是都是 (x)的不动点，则由的不动点，则由(3.2.3)得得.)()(21212121 xxxxL

25、xxxx 引出矛盾，故引出矛盾，故 (x)的不动点只能是唯一的的不动点只能是唯一的. .证毕证毕. . 在在 (x)的不动点存在唯一的情况下，可得到迭代的不动点存在唯一的情况下，可得到迭代法法 xk+1= (xk)收敛的一个收敛的一个充分条件充分条件. 定理定理2 设设 (x)Ca, b满足定理满足定理1中的两个条件，中的两个条件，则对任意则对任意x0a, b，由，由xk+1= (xk)得到的迭代序列得到的迭代序列xk收敛到的不动点收敛到的不动点x*，并有，并有误差估计式误差估计式101.(3.2.4)1.(3.2.5)1kkkkkLxxxxLLxxxxL 证明证明 设设x*a, b是是 (x

26、)在在a, b上的唯一不动点上的唯一不动点, ,由条件由条件1，可知，可知xka, b，再由，再由(3. 2. 3)得得.)()(011xxLxxLxxxxkkkk 因因0L1时称时称超线性收敛超线性收敛，p=2时称时称平方收敛平方收敛. 定理定理4 对于迭代过程对于迭代过程xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根x*的邻近连续，并且的邻近连续，并且(1)( )()()()0,()0. (3.2.7)ppxxxx则该迭代过程在则该迭代过程在x*的邻近是的邻近是p阶收敛的阶收敛的. 证明证明 由于由于(x*)=0，根据定理，根据定理3立即可以断定迭立即可以断定迭代过

27、程代过程xk+1= (xk)具有局部收敛性具有局部收敛性. 再将再将 (xk)在根在根x*处做泰勒展开处做泰勒展开, 利用条件利用条件(3.2.7), 则有则有.,)(!)()()()(之间之间与与在在 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得,)(!)()(1pkpkxxpxx 因此对迭代误差，令因此对迭代误差，令k时有时有这表明迭代过程这表明迭代过程xk+1= (xk)确实为确实为p阶收敛阶收敛. 证毕证毕. .!)()(1pxeeppkk 上述定理告诉我们，迭代过程的收敛速度依赖于上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数

28、迭代函数 (x)的选取的选取. 如果如果x a, b但但 (x)0时，则时，则该迭代过程只可能是线性收敛该迭代过程只可能是线性收敛.)0( aa的三阶方法的三阶方法. 假设假设 x0 充分靠近充分靠近 x*, 求求31)(limkkkxaxa 证明证明 首先由泰勒展式可得首先由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 例子例子 证明迭代公式证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求是求而而1/4a00，故此故此迭代公式是三阶方法迭代公式是三阶方法.3.3 迭代收敛的加速方法迭代收敛的加速方法埃特金加速收敛方法埃特金加速收敛方法

29、对于收敛的迭代过程，只要迭代足够多次，就可对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大，因此迭代过程的加速是慢，从而使计算量变得很大，因此迭代过程的加速是个重要的课题个重要的课题. 设设x0是根是根x*的某个近似值的某个近似值, 用迭代公式校正一次得用迭代公式校正一次得 x1= (x0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之间之间与与在在xxxxxxxx 假设假设 (x)改变不大改变不大, 近似地取某个近似值近似地取某个近似值L, 则有则有由于由于 x

30、2- -x*L(x1- -x*).10().(3.3.1)xxL xx 若将校正值若将校正值x1= (x0)再校正一次，又得再校正一次，又得 x2= (x1)将它与将它与(3.3.1)式联立，消去未知的式联立，消去未知的L，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxxx . 0lim1 xxxxkkk在计算了在计算了x1及及x2之后，可用上式右端作为之后，可用上式右端作为x*的新近似的新近似,记作记作x1，一般情形是由，一般情形是由xk计算计算xk+1, xk+2，记，记它表明序列它表明序列xk的收敛速度比的收敛速度比xk的收

31、敛速度快的收敛速度快.2112122()2()(0,1,).(3.3.2)kkkkkkkkkkxxxxxxxxxkx(3.3.2)式称为式称为埃特金埃特金(Aitken) 2加速方法加速方法. 可以证明可以证明也称为也称为埃特金埃特金 ( Aitken ) 外推法外推法. 可以证明可以证明:)(1kkxx 为线性收敛为线性收敛,则埃特金法为平方收敛则埃特金法为平方收敛； 这个加速迭代法也可写成下面格式这个加速迭代法也可写成下面格式(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 为为 p ( p

32、1)阶收敛，阶收敛，)(x 导数连续，则埃特金法为导数连续，则埃特金法为 2p1 阶收敛阶收敛.的的 p 阶阶若若21121()2kkkkkkkxxxxxxx 例题例题 求方程求方程 x = e x 在在 x=0.5 附近的根附近的根. 解解 取取 x0=0.5, 迭代格式迭代格式x25=x26=0.5671433 若对此格式用埃特金法若对此格式用埃特金法, 则则kxkex 1 得得(1)1(1)(2)12(2)(1)2(2)1111(2)(1)11()2kkxxkkkkkkkkkxexexxxxxxx (2)(1)2(2)1111(2)(1)11()2kkkkkkkxxxxxxx 仍取仍取

33、x0=0.5 , 得得5671433. 05671433. 05671433. 05671433. 05672979. 05668708. 05676279. 05452392. 06065307. 03)2(3)1(32)2(2)1(21)2(1)1(1 xxxxxxxxx由此可见由此可见, 埃特金法加速收敛效果是相当显著的埃特金法加速收敛效果是相当显著的.(1)1(1)(2)12kkxxkkxexe 3.4 牛 顿 法3.4.1 牛顿法及其收敛性牛顿法及其收敛性)()()(000 xxxfxfxf 对于方程对于方程f(x)=0，如果，如果f(x)是线性函数，则它的是线性函数，则它的求根是容

34、易的求根是容易的. 牛顿法实质上是一种线性化方法，其牛顿法实质上是一种线性化方法，其基本思想是将非线性方程基本思想是将非线性方程f(x)=0逐步归结为某种线性逐步归结为某种线性方程来求解方程来求解. 设已知方程设已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一阶泰勒多项式近似，表示为用一阶泰勒多项式近似，表示为一、牛顿迭代法一、牛顿迭代法当当f (x0)0时，方程时，方程f(x)=0可用线性方程可用线性方程(切线切线) 近似代近似代替，即替，即 f(x0)+f (x0)(x- -x0)=0. (3.4.1)解此线性方程得解此线性方程得)()(000 xfxfx

35、x 得迭代公式得迭代公式此式称为此式称为牛顿牛顿(Newton)迭代公式迭代公式.1()(0,1,),(3.4.2)()kkkkf xxxkfx牛顿法有显然的牛顿法有显然的几何意义几何意义，方程，方程f(x)=0的根的根x*可可解释为曲线解释为曲线y=f(x)与与x轴交点的横坐标轴交点的横坐标. 设设xk是根是根x*的的某个近似值，过曲线某个近似值，过曲线y=f(x)上横坐标为上横坐标为xk的点的点Pk引切引切线，并将该切线与线，并将该切线与x轴交点的横坐标轴交点的横坐标xk+1作为作为x*的新的的新的近似值近似值. 注意到切线方程为注意到切线方程为这样求得的值这样求得的值xk+1必满足必满足

36、(3.4.1), 从而就是牛顿公式从而就是牛顿公式(3.4.2)的计算结果的计算结果. 由于这由于这种几何背景，所以牛顿迭种几何背景，所以牛顿迭代法也称代法也称切线法切线法.xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy 二、牛顿法的收敛性二、牛顿法的收敛性定理定理4： 设设f (x)在在a, b上存在二阶连续导数且满足下列条件上存在二阶连续导数且满足下列条件：（1）f (a) f (b) 0则由则由（2）（）（3）确定的牛顿迭代序列确定的牛顿迭代序列xk二阶收敛于二阶收敛于f (x)在在a, b上的唯一单根上的唯一单根x*。牛顿法收敛性依赖初值牛顿法收敛

37、性依赖初值x0的选取的选取, 如果如果x0偏离所求偏离所求根根x*较远较远, 则牛顿法可能发散则牛顿法可能发散.x*x0 x0 x0例如例如，用牛顿法求解方程，用牛顿法求解方程 x3- -x- -1=0. 此方程在此方程在x=1.5附近的一个根附近的一个根x*. 设取迭代初值设取迭代初值x0=1.5，用牛顿迭代法公式，用牛顿迭代法公式 3121.31kkkkkxxxxx计算得计算得 x1=1.34783, x2=1.32520, x3=1.32472.迭代迭代3次得到的结果次得到的结果x3有有6位有效数字位有效数字.但是，如取但是，如取x0=0.6，用上式迭代，用上式迭代1次得次得 计算得计算

38、得 x1=17.9.这个结果反而比这个结果反而比x0=0.6更偏离了所求的根更偏离了所求的根x*=1.32472. 由此得到，当由此得到，当x*为为单根单根时，牛顿迭代法在根时，牛顿迭代法在根x*的的邻近是邻近是二阶二阶(平方平方)收敛收敛的的.定理定理(局部收敛性局部收敛性) 设设f C2a, b, 若若x*为为f(x)在在a, b上的根，且上的根，且f (x*) 0，则存在，则存在x*的邻域的邻域U, 使得任取初使得任取初值值x0 U，牛顿法产生的序列，牛顿法产生的序列xk收敛到收敛到x*，且满足，且满足即有下面的局部收敛性定理即有下面的局部收敛性定理.12()lim.()2()kkkxx

39、fxxxfx)()()(xfxfxx 设设x*是是f(x)的一个单根，即的一个单根，即f(x*)=0，f (x*)0, 有有. 0)()()(, 0)()()()(2* xfxfxxfxfxfx 牛顿迭代法的迭代函数为牛顿迭代法的迭代函数为2112!22( )()1()limlim()0.()()2!2()kkkkkkxxxxfxxxxxxfx 对于给定的正数对于给定的正数C，应用牛顿法解二次方程，应用牛顿法解二次方程, 02 Cx我们现在证明，这种迭代公式对于任意初值我们现在证明，这种迭代公式对于任意初值x00都是收敛的都是收敛的.可导出求开方值可导出求开方值 的计算程序的计算程序C.21)

40、()()(,)(2 xCxxfxfxxCxxf 11.(3.4.3)2kkkCxxx3.4.2 牛顿法应用举例牛顿法应用举例事实上，对事实上，对(3.4.3)式施行配方整理，易知式施行配方整理，易知 .2121CxxCxkkk 以上两式相除得以上两式相除得.211 CxCxCxCxkkkk据此反复递推有据此反复递推有200.(3.4.4)kkkxCxCxCxC记记.200kCxCxq 整理整理(3.4.4)式，得式，得.1222kkqqCCxk 对任意初值对任意初值x00，总有，总有|q|1，故由上式推知，当，故由上式推知，当k时时 ，即迭代过程恒收敛，即迭代过程恒收敛.Cxk 解解 将原方程

41、化为将原方程化为xex= 0，则，则牛顿迭代公式为牛顿迭代公式为kkxxkkkeexxx 11取取 x0=0.5，迭代得，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433. f(x)=xex， f (x)=1+ex， 例例7 用牛顿迭代法求方程用牛顿迭代法求方程x=ex在在x=0.5附近的根附近的根.3.4.3 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法牛顿法的牛顿法的优点优点是收敛快，是收敛快，缺点缺点每步迭代要计算每步迭代要计算f(xk)及及f (xk)，计算量较大，且有时，计算量较大，且有时f (xk)计算较困难；计算较困难；初始近似值初始近似值x0

42、只在根只在根x*附近才能保证收敛，如附近才能保证收敛，如x0给给的不合适可能不收敛的不合适可能不收敛. 为克服这两个缺点，通常可用为克服这两个缺点，通常可用下述方法下述方法.简化牛顿法简化牛顿法，也称，也称平行弦法平行弦法，其迭代公式为，其迭代公式为1()0,0,1,.(3.4.5)kkkxxCf xCk迭代函数为迭代函数为 (x)=x- -Cf(x). 若若| (xk)|=|1- -Cf (x)|1，即取，即取0Cf (x)2. 在根在根x*附近成立，则迭代法附近成立，则迭代法(3.4.5)局部收敛局部收敛.在在(3.4.5)中取中取C=1/f (x0)，则称为简化牛顿法，这，则称为简化牛顿

43、法，这类方法计算量省，但只有线性收敛，其类方法计算量省，但只有线性收敛，其几何意义几何意义是用是用平行弦与平行弦与x轴交点作为轴交点作为x*的近似，见下图的近似，见下图.y=f(x)x0 x1x2x*为了防止迭代发散，我们对迭代过程再附加一项为了防止迭代发散，我们对迭代过程再附加一项要求，即具有单调性要求，即具有单调性.1()() .(3.4.6)kkf xf x满足这项要求的算法称为满足这项要求的算法称为下山法下山法.我们将牛顿法与下山法结合起来使用，即在下山我们将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛法保证函数值稳定下降的前提下，用牛顿法加快收敛

44、速度速度. 为此，我们将牛顿法的结果为此，我们将牛顿法的结果)()(1kkkkxfxfxx 与前一项的近似值与前一项的近似值xk适当加权平均作为新的改进值适当加权平均作为新的改进值11(1),(3.4.7)kkkxxx其中其中(01)称为称为下山因子下山因子，(3.4.7)即为即为1()(0,1,).(3.4.8)()kkkkf xxxkfx称为称为牛顿下山法牛顿下山法.选择下山因子时从选择下山因子时从= =1开始，逐次将开始，逐次将减半进行试减半进行试算，直到能使下降条件算，直到能使下降条件(3.4.6)成立为止成立为止. 若用此法解方程若用此法解方程x3-x-1=0 ，当，当x0=0.6时

45、由时由(3.4.8)式式求得求得x1=17.9，它不满足条件，它不满足条件(3.4.6)，通过，通过逐次减半逐次减半进行试算进行试算,当当=1/32时可求得时可求得x1=1.140625. 有有f(x0)=- -1 1.384, f(x1)=- -0.656643, 显然显然|f(x1)|f(x0)|. 计算计算x2,x3,时，均能使条件时，均能使条件(3.4.6)成立成立. 得到得到x4=1.32472即为即为x*的的近似近似.3.5 解非线性方程组的牛顿迭代法考察方程组考察方程组111( ,)0,.(3.5.1)( ,)0.nnnf xxfxx其中其中f1,fn均为均为(x1,xn)的多元

46、函数的多元函数. 若用向量记若用向量记号记号记x=(x1,xn)TRn, F=(f1,fn)T, (3.5.1)就可写成就可写成 F(x)=0. (3.5.2)当当n2，且，且 f1,fn 中至少有一个是自变量中至少有一个是自变量 x1,xn 的的非线性函数，则称方程组非线性函数，则称方程组(3.5.1)为为非线性方程组非线性方程组. 非非线性方程组求根问题是前面介绍的方程求根的直接推线性方程组求根问题是前面介绍的方程求根的直接推广，实际上只要把前面介绍的广，实际上只要把前面介绍的单变量函数单变量函数f(x)看成看成向向量函数量函数F(x) ，则可得，则可得向量方程向量方程(3.5.2)的一个

47、近似根的一个近似根x(k)=(x1(k),xn(k)T，将函数，将函数F(x)的分量的分量fi(x)(i=1,n)在在x(k)用多元函数泰勒展开，并取其线性部分，则可表示用多元函数泰勒展开，并取其线性部分，则可表示为为. ).)()()()()()(kkkxxxFxFxF 令上式右端为零，得到线性方程组令上式右端为零，得到线性方程组( )( )( )()()().(3.5.3)kkkF xxxF x其中其中11112222121( )( )( )( )( )( )( ).(3.5.4)( )( )( )nnnnnnnf xf xf xxxxf xf xf xxxxF xfxfxfxxxx称为称

48、为F(x)的的雅可比雅可比(Jacobi)矩阵矩阵.求解线性方程组求解线性方程组(3.5.3)，并记解为，并记解为x(k+1)，则得，则得(1)( )( )1( )()() (0,1,). (3.5.5)kkkkxxF xF xk这就是这就是解非线性方程组解非线性方程组(3.5.2)的的牛顿迭代法牛顿迭代法.例例12 求解方程组求解方程组 . 052),(, 032),(222121221211xxxxfxxxxf给定初值给定初值x(0)=(1.5, 1.0)T，用牛顿法求解，用牛顿法求解.解解 先求先求Jacobi矩阵矩阵.1422821)(,2421)(1212121 xxxxxFxxxF用牛顿法用牛顿法(3.5.5)得得.5)()( 23214228212)(22)(1)(2)(1)(1)(2)(1)(2)()1( kkkk