1、问题驱动：全球定位系统（问题驱动：全球定位系统（GPS） 人类对导航和定位的需求是伴随着人类整个文明历史的人类对导航和定位的需求是伴随着人类整个文明历史的进步而发展的，中国古代进步而发展的，中国古代“四大发明四大发明”之一的指南针是最早之一的指南针是最早的定位仪器和系统，其后还有经纬仪以及近代的雷达。如图的定位仪器和系统，其后还有经纬仪以及近代的雷达。如图5.1.15.1.1所示全球定位系统（所示全球定位系统（GPSGPS）是基于卫星的导航系统，最）是基于卫星的导航系统，最早最早由美国和前苏联分别在早最早由美国和前苏联分别在8080年代研制，并于年代研制，并于19931993年正式年正式投入使
2、用。现代社会中全球定位系统越来越深入到人们生活投入使用。现代社会中全球定位系统越来越深入到人们生活的方方面面。例如市场上出售的手持型的方方面面。例如市场上出售的手持型GPS,GPS,定位的精度可以定位的精度可以达到达到1010米以内，这无疑给旅行者提供了方便米以内，这无疑给旅行者提供了方便; ;安装有安装有GPSGPS的儿的儿童手表，家长在家里的计算机上可以追踪到孩子的位置，防童手表，家长在家里的计算机上可以追踪到孩子的位置，防止儿童走失止儿童走失; ;安装有安装有GPSGPS系统的汽车可以帮助新司机辨识道路系统的汽车可以帮助新司机辨识道路等等。等等。 图图5.1.1 卫星定位示意图卫星定位示
3、意图 美国和前苏联的美国和前苏联的GPSGPS都包括有都包括有2424颗卫星颗卫星, ,它们不断地向地它们不断地向地球发射信号报告当前位置和发出信号的时间球发射信号报告当前位置和发出信号的时间, , 卫星分布如图卫星分布如图5.1.25.1.2所示。它的基本原理是所示。它的基本原理是: :在地球的任何一个位置，至少在地球的任何一个位置，至少同时收到同时收到4 4颗以上卫星发射的信号。颗以上卫星发射的信号。126,S SS发射的信号，发射的信号， 设地球上一个点设地球上一个点R R，同时收到卫星，同时收到卫星 假设接收的信息如表假设接收的信息如表5.1.1所示。请设法确定所示。请设法确定R点的位
4、置。点的位置。 图图5.1.2 卫星分布图卫星分布图表表9.1.1GPS导航问题可归结为求解非线性代数数方程组导航问题可归结为求解非线性代数数方程组 ( )0F x , 当当 1n 时就是单个方程时就是单个方程. ( )0f x .其中其中 可以是代数方程，也可以是超越方程。使可以是代数方程，也可以是超越方程。使 成立的成立的x x 值称为方程的根，或称为值称为方程的根，或称为 的零点。科学与工程的零点。科学与工程计算中，如电路和电力系统计算、非线性力学、非线性微（计算中，如电路和电力系统计算、非线性力学、非线性微（积分）方程、非线性规划（优化）等众多领域中，问题的求积分）方程、非线性规划（优
5、化）等众多领域中，问题的求解和模拟最终往往都要解决求根或优化问题。前一种情形要解和模拟最终往往都要解决求根或优化问题。前一种情形要求出方程（组）的根；后一种情形则要求找出函数取最大或求出方程（组）的根；后一种情形则要求找出函数取最大或最小的点。最小的点。 即使是对实验数据进行拟合或数值求解微分方即使是对实验数据进行拟合或数值求解微分方程，也总是将问题简化成上述两类问题。上述除少数特殊方程，也总是将问题简化成上述两类问题。上述除少数特殊方程外，大多数非线性代数方程（组）很难使用解析法求解精程外，大多数非线性代数方程（组）很难使用解析法求解精确解，一般需要通过一些数值方法逼近方程的解。这里主要确解
6、，一般需要通过一些数值方法逼近方程的解。这里主要介绍单个方程的数值解法，方程组也可以采用类似的方法，介绍单个方程的数值解法，方程组也可以采用类似的方法，将放在后面讨论。将放在后面讨论。( )0f x ( )f x( )f x1根的存在性。方程有没有根？如果有，有几个根？根的存在性。方程有没有根？如果有，有几个根？2根的搜索。根的搜索。这些根大致在哪里？如何把根隔离开？这些根大致在哪里？如何把根隔离开？3根的精确化。根的精确化。 f (x) = 0 （5.1.1）1.1.根的存在性根的存在性定理定理1：设函数设函数 f (x) 在区间在区间a, b上连续上连续，如果如果f (a) f (b) 0
7、打打 印印结结 束束否否是是继续扫描继续扫描例例1 1：考察方程：考察方程01)(3xxxf x00.51.01.5f (x) 的的符号符号ab11kkxx2)(xf 或或不能保证不能保证 x 的精的精度度abx0 x1x*执行步骤执行步骤1计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x0)。3判断若判断若f (x0) = 0，则则x0即是根，否则检验即是根，否则检验：（1）若若f (x1)与与f (a)异号异号，则知解位于区间则知解位于区间a, x0， b1=x0, a1=a;（2）若若
8、f (x0)与与f (a)同号同号，则知解位于区间则知解位于区间x0, b， a1=x0, b1=b。反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：1122 , ,nna ba ba ba b4、当当nnba时，停止；时，停止；1()2nnnxab即为根的近似。即为根的近似。当当 n 时，时， 0nnba，即这些区间必将收缩于一点，也就是，即这些区间必将收缩于一点，也就是方程的根。在实际计算中，只要方程的根。在实际计算中，只要 ,nna b的区间长度小于预定容的区间长度小于预定容许误差许误差就可以停止搜索，即就可以停止搜索，即 111()22nnnnnbabab
9、a然后取其中点然后取其中点 nx作为方程的一个根的近似值。作为方程的一个根的近似值。 注：注： nx例例1 证明方程证明方程 1020 xex存在唯一的实根存在唯一的实根 *(0,1)x 用二分法用二分法求出此根，要求误差不超过求出此根，要求误差不超过 20.5 10。解：记解：记 ( )102xf xex，则对任意，则对任意 xR( )100 xfxe ，因而，因而， ( )f x是严格单调的，是严格单调的， ( )0f x 最多有一个根，最多有一个根，(0)10,(1)80ffe 所以，所以， ( )0f x 有唯一实根有唯一实根 *(0,1)x 又因为又因为 用二分法求解，要使用二分法求
10、解，要使 *20.5 10kxx，只要，只要 21100.5 102k解得解得 26.64lg2k ，取，取 7k 。所以只要二等分。所以只要二等分7次，即可求得满次，即可求得满足精度要求的根。计算过程如表足精度要求的根。计算过程如表5.2.1所示所示 k f(ak)及符号及符号f(xk)及符号及符号f(bk)及符号及符号01234 5670()0()0()0()0.0625()0.0625()0.078125()0.0859375()0.5(+)0.25(+)0.125(+)0.0625()0.09375(+)0.078125()0.0859375()1( + )0.5( + )0.25(
11、+ )0.125( + )0.125( + )0.09375( + )0.09375( + )0.09375( + )表表5.2.1所以，所以， *0.5 (0.08593750.09375)0.09x 简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 二分法的优缺点二分法的优缺点问题问题 虽然二分法计算简单，能够保证收敛，但是它对于方程虽然二分法计算简单，能够保证收敛，但是它对于方程单根存在区域信息要求太高，一般情况下很难实现，并单根存在区域信息要求太高，一般情况下很难实现，并且不能求重根、复根和虚根。在实际应用中
12、，用来求解且不能求重根、复根和虚根。在实际应用中，用来求解方程根的主要方法是迭代法。方程根的主要方法是迭代法。使用迭代法求解非线性代数方程的步骤为：使用迭代法求解非线性代数方程的步骤为：(1) 迭代格式的构造；迭代格式的构造；(2) 迭代格式的收敛性分析；迭代格式的收敛性分析；(3) 迭代格式的收敛速度与误差分析。迭代格式的收敛速度与误差分析。 1 1简单迭代法简单迭代法f (x) = 0 x = (x)等价变换等价变换1()(0,1,)kkxxk其中其中 (x)是连续函数。方程（是连续函数。方程（5.3.1）称为不动点方程，满足）称为不动点方程，满足（5.3.1）式的点称为）式的点称为不动点
13、，不动点，这样就将求这样就将求 （5.3.1）( )f x的零点问题转的零点问题转化为求化为求( )x的不动点问题。的不动点问题。称这种迭代格式为称这种迭代格式为不动点迭代。不动点迭代。以不动点方程为原型构造迭代格式以不动点方程为原型构造迭代格式例例3：求方程求方程0210)(xxxf的一个根的一个根.210 xxlg(2)xx构造迭代格式构造迭代格式)2lg(1kkxxx1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.3758解：解：1020 xx给定初始点给定初始点10.4771x xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (
14、x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1 定理定理2 如果如果 (x)满足下列条件满足下列条件 （1 1）当）当x a, b时，时， (x) a, b （2 2）当任意）当任意x a, b，存在，存在0 L 1，使，使 则方程则方程x = (x)在在a, b上有唯一的根上有唯一的根x*, ,且对任意初值且对任意初值 x0 a, b时，迭代序列时，迭代序列xk+1= (xk) (k = 0, 1, )收敛于收敛于 x*，且有如下误差估计式：，且有如下误差估计式：1)( Lx(5.3.2)2迭代过程的收敛性与迭代过程的收敛
15、性与误差估计误差估计*+11(2)1kkkxxxxL*10(1)1kkLxxxxL停机准则。停机准则。（5.3.3） 324100f xxx11.5，*x求方程求方程在在内的根内的根例：例：。解：解：原方程可以等价变形为下列三个迭代格式原方程可以等价变形为下列三个迭代格式2313111040,1,2,.1100,1,2,.22100,1,2,.34kkkkkkkkxxxxkxxkxkx （1） （ ） （ ）由迭代格式由迭代格式 （1） 231104kkkkxxxx01.25x 取初值取初值得得 123.04687526.04005xx 结果是发散结果是发散的？！的？！311102kkkxxx
16、01.25x 1021324354657687981091.418351.336661.379481.357861.368981.363311.366211.364731.365491.36510 xxxxxxxxxxxxxxxxxxxx，10 x由迭代格式由迭代格式 （2） 取初值取初值得得 结果精确到四位有效数字，迭代到结果精确到四位有效数字，迭代到得到收敛结果。得到收敛结果。 十步十步才能得才能得到收敛到收敛的结果！的结果！1104kkxxx01.25x 102132431.380131.363341.365471.36512xxxxxxxx4x 由迭代格式（由迭代格式（3） 取初值取初
17、值得得 结果精确到四位有效数字，迭代到结果精确到四位有效数字，迭代到得到收敛结果。得到收敛结果。四步就能四步就能得到收敛的结得到收敛的结果了！果了！ 23104xxxx 21 83xxx 1,1.5x 2381101xxx 迭代格式（迭代格式（1 1）的迭代函数为）的迭代函数为 求导得求导得 当当时时故迭代格式（故迭代格式（1 1）是发散的。）是发散的。分析分析: : 31102xx当当 时，时，1,1.5x 33111.5 ,110 1.5 ,10 1221.287,1.51,1.5x 2330,410 xxx 33323401008xxxx 迭代格式（迭代格式（2 2）的迭代函数为）的迭代
18、函数为 由由知知当当 时，时，1,1.5x 2231.51.50.65561410 1.5x 所以迭代格式（所以迭代格式（2 2）是收敛的。）是收敛的。 104xx 10101.5 ,1,1.541 41.348,1.4141,1.5x 迭代格式（迭代格式（3 3）的迭代函数为）的迭代函数为当当 时，时，1,1.5x由由 2532131040,1040,24xxxx 1,1.5x时，时， 知知当当 3212110 140.1414210 x所以迭代格式（所以迭代格式（3 3）也是收敛的。）也是收敛的。结论结论: : x x 通过以上算例可以看出对迭代函数通过以上算例可以看出对迭代函数所得到的所
19、得到的若小于若小于1 1，则收敛；且上界越小收敛速度越快。，则收敛；且上界越小收敛速度越快。求导，求导，的上界若是大于的上界若是大于1 1，则迭代格式发散；，则迭代格式发散； 3. 加速收敛技术加速收敛技术 L越小迭代法的收敛速度越快，因此，可以从越小迭代法的收敛速度越快，因此，可以从寻找较小的寻找较小的L来改进迭代格式以加快收敛速度。来改进迭代格式以加快收敛速度。思思路路(1) 松弛法松弛法引入待定参数引入待定参数 1 ，将将 ( )xx作等价变形为作等价变形为 1( )11xxx（5.3.4） 将方程右端记为将方程右端记为 ( )w x，则得到新的迭代格式，则得到新的迭代格式 1()0,1
20、,)kkxw xk（由定理由定理2知知 ( )1xL为了使新的迭代格式比原来迭为了使新的迭代格式比原来迭代格式收敛得更快，只要满足代格式收敛得更快，只要满足( )( )w xx且且 越小，所获取的越小，所获取的L就越小，就越小，迭代法收敛的就越快，因此我们希望迭代法收敛的就越快，因此我们希望 。1( ) =+ ( )1+w xx （）( )0w x 可取可取 =()1kkx ，若记，若记 11kk则（则（5.3.4）式可改写为）式可改写为1kkkkkxxx =(1-)+()n 称为称为松弛因子松弛因子，这种方法称为，这种方法称为松弛法松弛法。为使迭代速度加快，。为使迭代速度加快，需要边计算边调
21、整松弛因子。由于计算松弛因子需要用到微商，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，在实际应用中不便使用，具有一定局限性。若迭代法是线性收在实际应用中不便使用，具有一定局限性。若迭代法是线性收敛的，当计算敛的，当计算 不方便时，可以采用不方便时，可以采用埃特金加速公式埃特金加速公式。 ( )x(2) 埃特金加速公式埃特金加速公式设迭代法是线性收敛，由定义知设迭代法是线性收敛，由定义知*1*lim0kkkxxcxx成立，故当成立，故当 k 时有时有 *12*1kkkkxxxxxxxx由此可得由此可得 的近似值的近似值 x2121()2kkkkkkkxxxxxxxx（5.3.5） 由
22、此获得比由此获得比 1,kkxx和和 2kx更好的近似值更好的近似值 kx，利用利用（5.3.5）序列序列 kx的方法称为的方法称为(3) Steffensen 加速法加速法 将将Aitken加速公式与不动点迭代相结合，可得加速公式与不动点迭代相结合，可得(1)(2)(1)1112(1)1(2)(1)111(),(),0,1,2kkkkkkkkkkkxxxxxxxkxxxx （5.3.6） 式构造式构造埃特金（埃特金（AitkenAitken）加速方法）加速方法。利用（利用（5.3.6）式构造序列）式构造序列 kx的方法称为的方法称为Steffensen加速方法。加速方法。即每进行两次不动点迭
23、代，就执行一次即每进行两次不动点迭代，就执行一次Aitken加速。加速。 例例2 试用简单迭代法和试用简单迭代法和Steffensen加速法求方程加速法求方程xxe在在 0.5x 附近的根，精确至四位有效数。附近的根，精确至四位有效数。 解：记解：记 ( )xxe，简单迭代法公式为：，简单迭代法公式为： 1(),0,1,2,kkxxk计算得计算得*0.5671x kxkkxkkxk00.570.55844140.5671210.6065380.56641150.5671620.5452490.56756160.5671430.57970100.5669140.56006110.5672850.
24、57117120.5670760.56486130.56719Aitken加速公式加速公式2(1)11(2)(1)112kkkkkkkxxxxxxx计算得计算得所以所以, *0.5671x。4迭代过程的局部收敛迭代过程的局部收敛定义定义1： 若存在若存在 的某一的某一邻域邻域 ，迭代过程迭代过程 对任意初值对任意初值 均均收敛，则收敛，则 称称迭代过程迭代过程 在在根根 邻近具有局邻近具有局 部收敛性。部收敛性。*x*x*:Rxx1()(0,1,)kkxxk0 xR1()(0,1,)kkxxk 定理定理3 设设 为方程为方程 的根，的根， 在在 的的邻近邻近 连续，且连续，且 ，则，则迭代过程
25、迭代过程 在在 的的邻近具有局部收敛性。邻近具有局部收敛性。*x*x( )xx ( ) x*()1x1( )(0,1,)kkxxk*x5迭代过程的收敛速度迭代过程的收敛速度 设由某方法确定的序列设由某方法确定的序列xk收敛于方程的根收敛于方程的根x*，如果存在正实数如果存在正实数p，使得，使得*1*limkpkkxxCxx（C C为非零常数）为非零常数）定义定义2则称序列则称序列xk收敛于收敛于x*的收敛速度是的收敛速度是p阶的阶的，或称该方法，或称该方法具有具有p 阶阶收收敛速度敛速度。当。当p = 1时，称该方法为时，称该方法为线性（一次）收敛线性（一次）收敛；当当p = 2时，称方法为时
26、，称方法为平方（二次）收敛平方（二次）收敛；当；当1 p 2或或C=0,p=1时，称方法为时，称方法为超线性收敛超线性收敛。 定理定理4 4 如果如果 在在 附近的某个领域内有附近的某个领域内有 ( )( )阶阶 连续导数，且连续导数，且则迭代格式则迭代格式 在在 附近是附近是 阶局部阶局部收敛的，且有收敛的，且有1p( )*( )*()0(1,2,1)()0jpxjpx)(1kkxx*x*x)(x*( )*1*()()lim()!pkpkkxxxxxppp3 3 牛顿法牛顿法一、牛顿法的迭代公式一、牛顿法的迭代公式 考虑非线性方程考虑非线性方程 0)(xf原理：原理：将非线性方程线性化将非线
27、性方程线性化 Taylor 展开展开取取 x0 x*，将将 f (x)在在 x0 做一阶做一阶Taylor展开展开:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之间。之间。将将 (x* x0)2 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 只要只要 f C1，且每步迭代都有，且每步迭代都有 ， 而且而且*limxxkk 则则 x*就是就是 f (x)的根。的根。公式（公式（9.4.19.4.1）称为）称为牛顿迭代公式。牛顿迭代公式。)()(1kkkkxfxfxx (9.4.1)构
28、造迭代公式构造迭代公式()0kfxx*x0 x1x2xyf(x)二、牛顿法的几何意义二、牛顿法的几何意义三、牛顿法的收敛性三、牛顿法的收敛性定理定理4： 设设f (x)在在a, b上存在二阶连续导数且满足下列条件上存在二阶连续导数且满足下列条件：（1）f (a) f (b) 0则由则由（9.4.1）确定的牛顿迭代序列确定的牛顿迭代序列xk二阶收敛于二阶收敛于f (x)在在a, b上的唯一单根上的唯一单根x*。Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0四四. 牛顿迭代法的局部收敛性与收敛速度牛顿迭代法的局部收敛性与收敛速度 ，, ,且且 设设 ()0f
29、 x()0fxf在包含在包含 x的一个区间二阶连续可的一个区间二阶连续可导，则导，则Newton迭代法至少二阶收敛，即迭代法至少二阶收敛，即 12|*|( *)|lim|*|2|( *)|kkkxxfxxxfx值得注意的是，当值得注意的是，当 ( )f x充分光滑且充分光滑且 x是是 ( )0f x 的重根时，牛顿的重根时，牛顿法在法在x的附近是线性收敛的。且的附近是线性收敛的。且Newton迭代法在迭代法在 ,ba上的上的收敛性依赖于初值收敛性依赖于初值0 x的选取。即初值的选取。即初值 0 x的选取充分靠近的选取充分靠近 x时，时，一般可保证一般可保证Newton迭代法收敛。迭代法收敛。
30、32210200 xxx并得出了并得出了 1.368808107x 是该方程的一个根，无人知道他用什么是该方程的一个根，无人知道他用什么方法得出的，在当时这是一个非常有名的结果，试用牛顿法求方法得出的，在当时这是一个非常有名的结果，试用牛顿法求出此结果。出此结果。 解：解： 记记32( )21020f xxxx则则22226( )34103()33fxxxx当当 xR时，时， ( )0fx，又，又(1)70,(2)160ff *(1,2)x 所以所以 ( )0f x 有唯一实根有唯一实根 ，并改写，并改写 ( )(2)1020,( )(34)10f xxxxfxxx例例3 Leonardo于于
31、1225年研究了方程年研究了方程 用牛顿迭代格式用牛顿迭代格式10(),0,1,2,()1.5kkkkf xxxkfxx所以，所以， *1.368808107x。五、求五、求m m重根的牛顿法重根的牛顿法1 1、迭代格式、迭代格式)()(1kkkkxfxfmxx(9.4.2)2 2、重数、重数m m的确定的确定3 3、迭代格式（、迭代格式（9.4.2)9.4.2)的收敛阶（至少的收敛阶（至少2 2阶收敛）阶收敛）由于由于Newton迭代法的收敛性依赖于初值迭代法的收敛性依赖于初值 0 x的选取，如果的选取，如果 0 x离方程的根离方程的根 x较远，则较远，则Newton迭代法可能发散。为了防止
32、迭迭代法可能发散。为了防止迭代发散，可以将代发散，可以将Newton迭代法与下山法结合起来使用，放宽迭代法与下山法结合起来使用，放宽初值初值0 x的选取范围，即将（的选取范围，即将（9.4.1）式修改为：）式修改为： 1(),0,1,2,()kkkkf xxxkfx其中，其中， 01称为下山因子，选择下山因子时，希望称为下山因子，选择下山因子时，希望 ()kf x满足下满足下山法具有的单调性，即山法具有的单调性，即1()() ,0,1,2,kkf xf xk这种算法称为这种算法称为Newton下山法。下山法。在实际应用中，可选择在实际应用中，可选择 ,01kk。六、六、牛顿法的变形牛顿法的变形
33、1 1、牛顿下山法、牛顿下山法牛顿下山法的计算步骤：牛顿下山法的计算步骤：（1 1）选取初始近似值）选取初始近似值x x0 0；（2）取下山因子取下山因子 = 1= 1；)( )(1kkkkxfxfxx（3）计算计算)(1kxf)(kxf（4）计算）计算f (xk+1)，并比较，并比较 与与 的大小，分以下二种情况的大小，分以下二种情况)() 1kkxfxf21kkxx21kkxx1）若）若 ，则当，则当 时，取时，取x* xk+1，计算过程结束；，计算过程结束；当当 时，则把时，则把 xk+1 作为新的作为新的 近似值，并返回到（近似值，并返回到（3）。）。)()1kkxfxf 2）若）若
34、，则当，则当 且且|f(xk+1)| ，取，取x* xk，计算过程结束；，计算过程结束；11)(kxf否则若否则若 ，而，而 时，则把时，则把xk+1加上一个适当选定的小正数，加上一个适当选定的小正数，11)(kxf即取即取xk+1+ 作为新的作为新的xk值，并转向（值，并转向（3）重复计算；当）重复计算；当 ；且；且 时时，则将下山因子缩小一半，取，则将下山因子缩小一半，取 /2代入，并转向（代入，并转向（3）重复计算。）重复计算。 1例例5 5：求方程：求方程f f ( (x x) = ) = x x3 3 x x 1 = 0 1 = 0 的根。的根。k xk010.611/251.140
35、63211.36681311.32628411.32472牛顿下山法的计算结果：牛顿下山法的计算结果：牛顿迭代法每迭代一次都需计算函数值牛顿迭代法每迭代一次都需计算函数值 ()kf x和导数值和导数值 ()kfx计算量比较大；且迭代过程中计算计算量比较大；且迭代过程中计算 1kx时，仅利用了时，仅利用了 kx点的信息，点的信息，而没有充分利用已经求出的而没有充分利用已经求出的 12,kkxx；在导数计算比较麻烦；在导数计算比较麻烦或难以求出时，或难以求出时， 迭代格式构造迭代格式构造 (2) 构造方法：将构造方法：将Newton迭代格式中的导数用差商代替。迭代格式中的导数用差商代替。 2、割线
36、法、割线法：(1) (1) 构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；设法避开导数值的计算，因此可以采用设法避开导数值的计算，因此可以采用离散牛顿法（割线法）离散牛顿法（割线法）。 一个自然的想法就是在充分利用一个自然的想法就是在充分利用“旧信息旧信息”的同时，的同时，割线法的几何意义割线法的几何意义x0 x1切线切线割线割线切线斜率切线斜率 割线斜率割线斜率00)()()(xxxfxfxfkkk)()()()(001xxxfxfxfxxkkkkkx2割线法迭代格式割线法迭代格式：割线法的局部收敛性与收敛速度割线法的局部收敛性与收敛速度
37、()0fx 设设 ()0f x，x*: xx在在 , ,且且 f的某一邻域的某一邻域 内二阶连续可微，当内二阶连续可微，当 01,xx 时，由割线法产生的序列时，由割线法产生的序列 kx收敛于收敛于 x，且收敛阶至少为，且收敛阶至少为1.618。 3 3、 双点弦截法双点弦截法 ：切线斜率切线斜率 割线斜率割线斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx初值初值 x0 和和 x1。x0 x1x24 非线性方程组的数值解法非线性方程组的数值解法(1) 构造思想：用线性方程组近似非线性方程组，由线性构造思想：用线性方程组近似非线性方程组，由
38、线性方程组解得的向量序列，逐步逼近非线性方程组的解向量。方程组解得的向量序列，逐步逼近非线性方程组的解向量。 (2) 构造方法：若记构造方法：若记一、一、 非线性方程组的牛顿迭代法非线性方程组的牛顿迭代法 11,xxF xxnnxfxf则非线性方程组则非线性方程组 111212,00,0nnnnffx xxffx xx xF xx其中其中 2n(1,2, )if in ，且，且 中至少有一个是中至少有一个是 (1,2, )ix in的非线的非线性函数。类似于性函数。类似于1n 的情况，可将单变量方程求根的方法推广的情况，可将单变量方程求根的方法推广到非线性方程组。若已给出方程组的一个近似根到非
39、线性方程组。若已给出方程组的一个近似根 ( )( )( )( )12(, ,)kkkknxxxx。将函数。将函数 ( )F x的分量的分量 ( )(1,2, )if x in在在 ( )kx用多元函数泰勒展开，用多元函数泰勒展开，并取其线性部分可表示为并取其线性部分可表示为 ( )( )( )( )()()().kkkF xF xF xxx （9.5.1）令上式右端为零，得到线性方程组令上式右端为零，得到线性方程组( )( )( )()()()kkkF xxxF x （9.5.2） 其中其中 111122221212nnnnnnfffxxxfffxxxfffxxxFx称为称为 ( )F x的的
40、Jacobi矩阵，求解线性方程组（矩阵，求解线性方程组（9.5.2），并记解为），并记解为 (1)kx，则得，则得 ( )(1)( )( )(),(0,1, )()kkkkF xxxknF x这就是解非线性方程组（这就是解非线性方程组（9.5.1）的）的Newton迭代法。迭代法。Newton迭迭代法具有二阶的收敛速度，但对初值的要求很高，即充分靠近代法具有二阶的收敛速度，但对初值的要求很高，即充分靠近解解 x。02468051002468图 7.8HeightS6S3S4S2S1RS5N-S positions图9.5.1二、全球定位系统的求解二、全球定位系统的求解:解：卫星解：卫星 126
41、,S SS的位置如图的位置如图9.5.1所示，假设所示，假设 ( , , , )ux y z t表示表示R的当前位置，则它满足方程组的当前位置，则它满足方程组 222222222222222222(3)(2)(3)(10010.00692286)0(1)(3)(1)(10013.34256381)0(5)(7)(4)(10016.67820476)0(1)(7)(3)(10020.01384571)0(7)(6)(xyztcxyztcxyztcxyztcxyz2222227)(10023.34948666)0(1)(4)(9)(10030.02076857)0tcxyztc其中，光速其中，光速
42、 0.299792458ckms，上述方程组无疑是非线性的，但，上述方程组无疑是非线性的，但很容易将所有二次项都消去，从而得到很容易将所有二次项都消去，从而得到 44123.5975135971.102162.9979229957.286102.3983424031.406121.7987517993.512441.1991712059.7xyzt由求解非线性方程组的由求解非线性方程组的Newton迭代法知迭代格式为迭代法知迭代格式为( )(1)( )( )(),(0,1, )()kkkkF uuuknF u 1111222233334444555544123.5975102162.99792
43、86102.3983406121.7987512441.19917ffffxyztffffxyztffffuxyztffffxyztffffxyztF其中其中， 使用使用Matlab求解得迭代求解得迭代4次就可以得到相当精确的结果。次就可以得到相当精确的结果。 nxyzt00.00.00.010010.00716.3687270.374601-2.4039719.98521824.9840633.0182411.04630310000.26635.0001602.9998080.9995859999.99845.0000003.0000001.00000010000.000它的解是：它的解是：
44、5.000000,3.000000,1.000000,10000.000 xyzt历史与注记历史与注记 艾萨克艾萨克牛顿（牛顿（Isaac Newton 16421727） 牛顿是牛顿是英国物理学家、数学家、天文学家和自然哲学家。英国物理学家、数学家、天文学家和自然哲学家。1643年诞生于英格兰林肯郡乌尔索普镇。年诞生于英格兰林肯郡乌尔索普镇。1727年卒于伦敦。年卒于伦敦。1665年他发现了二项式定理，年他发现了二项式定理，1669年担任卢卡斯讲座的年担任卢卡斯讲座的教授，教授，1696年牛顿任造币厂监督，年牛顿任造币厂监督，1699年升任厂长年升任厂长,1705年因改革币制有功受封为爵士，
45、年因改革币制有功受封为爵士，1672年起他被接纳为皇年起他被接纳为皇家学会会员，家学会会员，1703年被选为皇家学会主席直到逝世。年被选为皇家学会主席直到逝世。 牛顿是有史以来最伟大的科学家之一，他在力学、数学、光学、热学、牛顿是有史以来最伟大的科学家之一，他在力学、数学、光学、热学、天文学和哲学方面都有突出的贡献。他在数学方面的贡献为：牛顿将古希天文学和哲学方面都有突出的贡献。他在数学方面的贡献为：牛顿将古希腊以来求解无穷小问题的种种特殊方法统一为两类算法：正流数术（微分腊以来求解无穷小问题的种种特殊方法统一为两类算法：正流数术（微分）和反流数术（积分），与此同时，他还在）和反流数术（积分）
46、，与此同时，他还在1676年首次公布了他发明的二年首次公布了他发明的二项式展开定理。并和项式展开定理。并和G.W.莱布尼茨几乎同时创立了微积分学。牛顿在数值莱布尼茨几乎同时创立了微积分学。牛顿在数值计算上的主要贡献有：牛顿插值法、牛顿积分法、牛顿迭代法等。计算上的主要贡献有：牛顿插值法、牛顿积分法、牛顿迭代法等。 关于特殊的非线性方程求根问题的迭代法最早出现在古希腊、巴比伦和关于特殊的非线性方程求根问题的迭代法最早出现在古希腊、巴比伦和印第安人的著作中。牛顿法的只有一部分属于牛顿本人，印第安人的著作中。牛顿法的只有一部分属于牛顿本人，1669年牛顿第一次年牛顿第一次提出了与现在牛顿法基本等价的
47、方法，但令人惊讶的是该方法并没有使用导提出了与现在牛顿法基本等价的方法，但令人惊讶的是该方法并没有使用导数，而是基于二项展开式，因此只适用于多项式。数，而是基于二项展开式，因此只适用于多项式。1690年，拉弗森对牛顿法年，拉弗森对牛顿法作了简化和改进，称为牛顿作了简化和改进，称为牛顿拉弗森法。在牛顿法中使用导数是由辛普森拉弗森法。在牛顿法中使用导数是由辛普森1740年首次提出的，并将其从一维空间推广到多维空间，这才是现在所称的牛年首次提出的，并将其从一维空间推广到多维空间，这才是现在所称的牛顿法。顿法。1798年，拉格朗日提出了牛顿法简单而精巧的表达式，并在年，拉格朗日提出了牛顿法简单而精巧的
48、表达式，并在1831年由年由傅立叶作了推广。非线性方程组的大多数方法都采用了牛顿法的设计原理，傅立叶作了推广。非线性方程组的大多数方法都采用了牛顿法的设计原理，并以牛顿法为度量标准。并以牛顿法为度量标准。“牛顿法牛顿法”以成为将不同类型非线性方程组局部线性以成为将不同类型非线性方程组局部线性化的一个经典范例。关于一维非线性方程组的解法的经典方法的详细资料可化的一个经典范例。关于一维非线性方程组的解法的经典方法的详细资料可参考文献参考文献1,2,3，若想进一步了解近期的研究成果可参考文献，若想进一步了解近期的研究成果可参考文献4,5 参考文献参考文献1J.F.Traub.IterativeMet
49、hodsfortheSolutionofEquations.PrenticeHall,EnglewoodCliffs,NJ,1964.2A.M.Ostrowski.SolutionofEquationsandSystemsofEquations.Academic,NewYork,2dedition,1966.3A.S.Householder.TheNumericalTreatmentofaSingleNonlinearEquation.McGraw-Hill,NewYork,1970.4C.T.Kelley.IterativeMethodsforLinearandNonlinearEquations.SIAM,Philadelphia,PA,1995.5W.C.Rheinboldt.MethodsforSolvingSystemsofNonlinearEquations.SIAM,Philadelphia,PA,2dedition,1998.
