第2章计算方法

1、第二章第二章 一元非线性方程的解法一元非线性方程的解法 设非线性方程为设非线性方程为 f (x)=0 (2-1) 方程（方程（2-1）的解）的解 x* 称为方程的根或函数称为方程的根或函数f (x)的零点。的零点。若若f (x)可表示为可表示为 f (x)=(x-x*)m g (x)其中其中m为大于为大于1的整数的整数,且且g(x) 0,称称x*为方程为方程(2-1)的的m重根重根,或函数或函数 f (x) 的的m重零点重零点.若若 f (x)为为n次多项式次多项式,则称则称 f (x)=0为为n次代数方程次代数方程;若若 f (x)为超越函数为超越函数,则称则称f (x)=0为超越方程为超越

2、方程 。 若若 f (x)在在a,b内连续内连续, 且且 f(a)f(b)0, f (0)=10, f (3)=- -260可见可见 f (x) 仅有两个实根仅有两个实根, 分别位于分别位于(0, 3) , (3,+), 又又 f (4)=10, 所以第二根的隔根区间可缩小为所以第二根的隔根区间可缩小为 (3,4)。以上分析可用下表表示以上分析可用下表表示x(-,0)0 (0,3) 3 (3,4) 4 (4,+) f (x) f (x) - 0+ - 0-+ + 隔根区间隔根区间(0,3)(3,4)2. 逐步搜索法逐步搜索法 从区间从区间a,b的左端点的左端点 a 出发出发, 按选定的步长按选

3、定的步长h 一一步步向右搜索，若步步向右搜索，若f(a+jh) f(a+(j+1)h)0 (j=0,1,2, )则区间则区间 a+jh , a+(j+1)h 内必有根。搜索过程也可从内必有根。搜索过程也可从b开始，这时应取步长开始，这时应取步长 h 0。二、二分法二、二分法 设设f (x)在区间在区间a,b 上连续上连续, f (a) f (b)0, 则则a, b内有方程的根。取内有方程的根。取 a , b 的中点的中点将区间一分为二。若将区间一分为二。若 f ( x0 ) = 0, 则则 x0 就是方程的根就是方程的根,否则判别根否则判别根 x*在在 x0 的左侧还是右侧。的左侧还是右侧。,

4、 )(bax 210若若f (a) f (x0) 0, 则则x*(x0 , b ), 令令 a1= x0 , b1=b. 不论出现哪种情况不论出现哪种情况,( a1 , b1 )均为新的有根区间均为新的有根区间, 它它的长度只有原有根区间长度的一半的长度只有原有根区间长度的一半, 达到了压缩有根达到了压缩有根区间的目的。区间的目的。 对压缩了的有根区间对压缩了的有根区间, 又可实行同样的步骤又可实行同样的步骤, 再压再压缩。如此反复进行缩。如此反复进行, 即可的一系列有根区间套即可的一系列有根区间套 ,11nnbababa由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，

5、因此区间 an , bn 的长度为的长度为)(ababnnn 21若每次二分时所取区间中点都不是根，则上述过程若每次二分时所取区间中点都不是根，则上述过程将无限进行下去。当将无限进行下去。当 n 时，区间必将最终收缩时，区间必将最终收缩为一点为一点x* ，显然，显然x*就是所求的根。若就是所求的根。若取区间取区间 an , bn 的中点的中点)(nnnbax 21作为作为x*的的 近似值，则有下述误差估计式近似值，则有下述误差估计式)22()(21)(21*1 ababxxnnnn只要只要 n 足够大足够大, 即区间二分次数足够多即区间二分次数足够多 ），误差），误差就可足够小。就可足够小。)

6、,(,*11 nnnbaxx 由于在偶重根附近曲线由于在偶重根附近曲线 y=f(x) 为上凹或下凸，为上凹或下凸，即即 f(a) 与与 f(b) 的符号相同，因此不能用二分法求的符号相同，因此不能用二分法求偶重根偶重根.例例 2 用二分法求例用二分法求例1中（中（1）方程的实根）方程的实根,要求误差要求误差不超过不超过0.005。解解 由例由例1可知可知x* (1,1.5), 要想满足题意，即：要想满足题意，即：| x* - -xn|0.005，则要，则要005. 021)15 . 1(21)(21211 nnnab由此解得由此解得, 6 . 512lg2 n取取n=6。按二分法计。按二分法计

7、算过程见下表。算过程见下表。x6 = 1.3242 为所求之近似根。为所求之近似根。n an bn xn f (xn)01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3242- -+- -+ - - - -(1) f(a)0(2) 根据精根据精 度要求，度要求，取到小数取到小数点后四位点后四位 即可即可.第二节 迭代法一、迭代法的基本思想迭代法是一种重要的逐次逼近法迭代法是一种重要的逐次逼近法,其基本思想是：其基本思想是：

8、将方程将方程 f (x）= 0 化为等价方程化为等价方程, )(xx 然后在隔根区间内取一点然后在隔根区间内取一点 x0 ，按下式计算，按下式计算)32(), 2 , 1 , 0()(1 kxxkk 计算结果生成数列计算结果生成数列 x0 , x1 , , xk , (2-4)如果这个数列有极限如果这个数列有极限,*limxxkk 当当 (x) 连续时连续时, 显然显然 x* 就是方程就是方程 x= (x) 之根之根. 于于是可以从此数列中求得满足精度要求的近似根是可以从此数列中求得满足精度要求的近似根. 这种这种求根方法称为迭代法求根方法称为迭代法, 式式 (2-3) 称为迭代格式称为迭代格

9、式, (x) 称称为迭代函数，为迭代函数，x0 称为迭代初值，数列（称为迭代初值，数列（2-4）称为迭代）称为迭代序列。如果迭代序列收敛序列。如果迭代序列收敛, 则称迭代格式（则称迭代格式（2-3）收）收敛敛, 否则称为发散。否则称为发散。例例3 3 用迭代法求方程用迭代法求方程 x4+2x2- -x- -3=0 在区间在区间1, 1.2内内的实根。的实根。 解解 对方程进行如下三种变形：对方程进行如下三种变形： 03224xxx分别按以上三种形式建立迭代格式，并取分别按以上三种形式建立迭代格式，并取x0=1进行进行迭代计算，结果如下：迭代计算，结果如下：7433176212726111049

10、5307. 8,96, )(124123. 1, )(124123. 1, )( xxxxxxxxxxxxkkkkkk 14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 准确根准确根 x* = 1.124123029, 可见迭代格式不同可见迭代格式不同, 收敛情收敛情况也不同。第二种格式比第一种格式收敛快得多况也不同。第二种格式比第一种格式收敛快得多,而而第三种格式不收敛。第三种格式不收敛。二、迭代法的收敛条件定理定理1 设设)(x 在在a , b上存在上存在,且满足条件：且满足条件：（1）当）当xa , b时，时，; ,)(bax （2）存在正数）存在正数L1，使对

11、任意的，使对任意的 xa , b,。1)( Lx 则则 （1）方程）方程)(xx 在在a , b上有唯一根上有唯一根 x*;（2）对任意迭代初值）对任意迭代初值 x0a , b,迭代序列迭代序列), 2 , 1 , 0()(1 kxxkk 收敛于收敛于x*。 证（证（1）先证方程）先证方程)(xx 之解存在且唯一之解存在且唯一.由于由于)(x 在在a , b上存在，所以上存在，所以)(x 连续。作函数连续。作函数, )()(xxxf 则则 f (x) 在在a , b上连续。由条件上连续。由条件(1) f (a) 0 , f (b) 0 , 故存在故存在x*a , b ,使使 f (x*) =

12、0 , 即即。)(*xx 设方程设方程)(xx 还有一根还有一根, 则由微分中则由微分中值定理及条件（值定理及条件（2）有）有 *)()()(xLxxx此式仅当此式仅当0* x才能成立，因此才能成立，因此。*x （2）再证迭代格式）再证迭代格式)(1kkxx 收敛收敛任取任取 x0 a, b ，由微分中值定理，有，由微分中值定理，有1*1*1*)()()( kkkkxxLxxxxxx 反复用此不等式，并注意反复用此不等式，并注意 0 L 1，因此，因此x*-xkLkx*-x00 ( k)即迭代过程收敛，且即迭代过程收敛，且。 xxkklim证毕。证毕。 此定理在理论上十分重要，但是条件（此定理

13、在理论上十分重要，但是条件（1）却不）却不容易判别。如果仅在根的邻域中考察迭代格式，则容易判别。如果仅在根的邻域中考察迭代格式，则下述定理可避免条件（下述定理可避免条件（1）的判别。）的判别。定理定理2 若方程若方程)( xx 之根的某邻域之根的某邻域 *|xxxR内内)(x 存在，且存在正常数存在，且存在正常数 L 1时称为超线性收敛时称为超线性收敛.显然显然, 收敛阶越大收敛阶越大, 收敛越快收敛越快.利用微分中值定理及泰勒展式可得下面的定理利用微分中值定理及泰勒展式可得下面的定理3. 三、迭代法的收敛速度三、迭代法的收敛速度若若, xxkk定理定理3 设设 x*为为)(xx 之根之根,

14、在在x*的邻域的邻域 R)(x 有连续的有连续的 p 阶导阶导 数，则数，则,1)(0)1( x 若若则迭代过程在则迭代过程在 x* 的邻近的邻近为线性收敛；为线性收敛；, 0)(, 0)()()() 2()() 1( xxxxpp 若若则迭代过程在则迭代过程在 x* 的邻近为的邻近为 p 阶收敛。阶收敛。内内)0( aa的三阶方法。假设的三阶方法。假设 x0 充分靠近充分靠近 x*, 求求31)(limkkkxaxa 解解 由泰勒展式可得由泰勒展式可得aaxaxakkkkkk41)(! 31)(lim)(lim3131 例例4 证明迭代公式证明迭代公式 xk+1=xk(xk2+3a)/(3x

15、k2+a)是求是求迭迭代代格格式式)92(2)()()()1(1)2(12)1(1)2(1)2(11)1(1)2(1)1(1 kkkkkkkkkkkxxxxxxxxxxx称为埃特金称为埃特金 ( Aitken ) 外推法，可以证明，若外推法，可以证明，若)(1kkxx 为线性收敛，则埃特金法为平方为线性收敛，则埃特金法为平方四、加速迭代法四、加速迭代法收敛；若收敛；若)(1kkxx 为为 p ( p 1)阶收敛，阶收敛，)(x 的的 p 阶导数连续，则埃特金法为阶导数连续，则埃特金法为 2p 1 阶收敛。阶收敛。例例5 求方程求方程 x = e x 在在 x = 0.5 附近的根附近的根.解解

16、 取取 x0 = 0.5, 迭代格式迭代格式x25 = x26 = 0.5671433 若对此格式用埃特金法若对此格式用埃特金法, 则则kxkex 1 得得kkkkkkkxkxkxxxxxxxexexkk )1(1)2(12)1(1)2(1)2(11)2(2)1(12)()1(1仍取仍取 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由此可见由此可见, 埃特金法加

17、速收敛效果是相当显著的埃特金法加速收敛效果是相当显著的.第三节第三节 牛顿切线法牛顿切线法一、牛顿法的基本思想一、牛顿法的基本思想 设已知方程设已知方程 f (x) = 0 的近似根的近似根 x0，且在，且在 x0附近附近 f (x)可用一阶泰勒多项式近似，表示为可用一阶泰勒多项式近似，表示为)()()(000 xxxfxfxf 当当 f (x0) 0 时，方程时，方程 f (x) = 0 可用线性方程近似可用线性方程近似代替，即代替，即 f ( x0)+ f (x0) ( x - - x0 )=0解此线性方程得解此线性方程得)()(000 xfxfxx 取此取此 x 作为原方程的新近似根作为

18、原方程的新近似根 x1，重复以上步骤，重复以上步骤，得迭代公式得迭代公式)102(), 1 , 0()()(1 kxfxfxxkkkk此式称为牛顿此式称为牛顿(Newton)迭代公式。迭代公式。二、牛顿法的几何意义二、牛顿法的几何意义若过曲线若过曲线 y= f (x)上的点上的点 P ( xk , f ( xk )引切线，引切线，该切线与该切线与 x 轴交点的横坐标即为由牛顿迭代公式轴交点的横坐标即为由牛顿迭代公式求得的求得的 xk+1 , 因此牛顿迭代法也称牛顿切线法。因此牛顿迭代法也称牛顿切线法。例例6 用牛顿迭代法求方程用牛顿迭代法求方程 x = e x 在在 x =0.5附近附近 的根

19、。的根。 解解 将原方程化为将原方程化为 x e x = 0，则，则牛顿迭代格式为牛顿迭代格式为kkxxkkkeexxx 11取取 x0 =0.5，迭代得，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433 f(x)= x e x ， f (x)=1+ e x, 三、牛顿迭代法的收敛速度三、牛顿迭代法的收敛速度)()()(xfxfxx 由于由于 f ( x*) = 0 ，所以当，所以当 f ( x*) 0 时时, ，不不一一定定为为 0)()()(0)()()()(*xfxfxxfxfxfx 牛顿迭代法的迭代函数为牛顿迭代法的迭代函数为1、当、当 x* 为单根

20、时，牛顿迭代法在根为单根时，牛顿迭代法在根 x* 的附近至少的附近至少 是二阶收敛的；是二阶收敛的；2、当、当 x* 为重根时，设为为重根时，设为m重根，则重根，则 f (x)可表为可表为 f (x) = ( x - x* )m g ( x )其中其中 g (x*) 0，此时用牛顿迭代法求，此时用牛顿迭代法求 x* 仍然收敛，仍然收敛，只是收敛速度将大大减慢。事实上，因为只是收敛速度将大大减慢。事实上，因为)()()()()()()(*1kkkkkkkkkkxgxxxgmxgxxxxfxfxx 令令 ek= xk x*，则，则)()()(*11kkkkkkkkxgexmgxgeexxe 可见用

21、牛顿法求方程的重根仅为线性收敛。可见用牛顿法求方程的重根仅为线性收敛。有两种方法可以提高求重根的收敛速度：有两种方法可以提高求重根的收敛速度：)132(011)()()(1limlim1 mxgexmgxgeekkkkkkkk1）将求重根问题化为求单根问题，注意函数）将求重根问题化为求单根问题，注意函数)01)()()()()()(* mxQxQxxxfxfxu所以化为求所以化为求 u(x)=0的单根的单根,是平方收敛的是平方收敛的.格式为格式为 )()()()()()()(21kkkkkkkkkkxfxfxfxfxfxxuxuxx 2）采用如下迭代格式）采用如下迭代格式3、计算重根的牛顿迭代

22、法、计算重根的牛顿迭代法)142()()(1 kkkkxfxfmxx下面介绍一个求重数的方法，令下面介绍一个求重数的方法，令211 kkkkkxxxx 则则121121111 kkkkkkkkkkkeeeeeeeeee 由式（由式（2-13）可知）可知mmmkk111lim 因此可用下式估计因此可用下式估计 m)152(11 km 例例8 用牛顿迭代法求用牛顿迭代法求 f (x)=(x- -1)sin(x- -1)+3x- -x3+1=0 在在0.95附近之根。附近之根。 解解 取取 x0 = 0.95, 用用牛顿迭代法式牛顿迭代法式(2-10)求得的求得的 xk 见右表见右表 可可见见 xk 收敛很慢。收敛很慢。由重根数由重根数 m 为为 2 用用式（式（2-14）得）得x0=0.95 x1=0.9988559 x2=x3=1收敛速度大大加快于直接用牛顿迭代公式收敛速度大大加快于直接用牛顿迭代公式(2-10).k xk k m01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.05111、简化牛顿迭代法、简化牛顿迭代法在牛顿迭代公式（