计算方法 4方程求根迭代法

1、第5章 方程求根的数值解法1 二分法二分法2 迭代法迭代法3 切线法切线法(牛顿法牛顿法)4 弦截法弦截法5 加速迭代法加速迭代法 1二分法二分法 我们已经熟悉求解一元一次方程、一元二次方程以及某些特殊类型的高次代数方程或非线性方程的方法。这些方法都是代数解法,求出的根是方程的准确根。但是在许多实际问题中遇到的方程,例如代数方程 x3-x-1=0 或超越方程 cos03xxe 等等,看上去形式简单,但却不易求其准确根。为此,只能求方程达到一定精度的近似根。 方程的形式很多,我们主要讨论一元非线性方程,也即 f(x)=0 (51) 方程(51)可以有实根,也可以有复根或者重根等。本章主要讨论它的

2、实根的数值计算问题。 方程根的数值计算大致可分三个步骤进行: (1) 判定根的存在性。 (2)确定根的分布范围,即将每一个根用区间隔离开来。 (3)根的精确化,即根据根的初始近似值按某种方法逐步精确化,直至满足预先要求的精度为止。 设f(x)为定义在某区间上的连续函数,方程(51)存在实根。虽然方程(51)的根的分布范围一般比较复杂,但我们不难将函数f(x)的定义域分成若干个只含一个实根的区间。 例如考虑方程 x2-2x-1=0 由图5.1所示,该方程的一个负实根在-1和0之间,另一个正实根在2和3之间。 图 5.1 这样,我们总可以假设方程(51)(a,b)内有且仅有一个单实根x*。由连续函

3、数的介值定理知 f(a)f(b)0 若数值b-a较小,那么我们可在(a,b)上任取一点x0作为方程的初始近似根。 例如,方程 f(x)=x3-x-1=0 由于f(1)0,f(1.5)0,又f(x)在区间(1,1.5)上单调连续,故可知在(1,1.5)内有且仅有一个实根。于是可取某个端点或区间内某一个点的值作为根的初始近似值。 设函数f(x)在区间a,b上单调连续,且 f(a)f(b)0 则方程(51)在区间(a,b)内有且仅有一个实根x。下面在有根区间(a,b)内介绍二分法的基本思想。 计算f(a)与f(x0),若 f(a)f(x0)0 则根x(a,x0),令 a1=a,b1=x0 否则x(x

4、0,b),令 a1=x0,b1=b图 5 .2 如此逐次往复下去,便得到一系列有根区间 (a,b),(a1,b1),(a2,b2),(ak,bk), 其中111()21()2kkkkkkkbabababa这里a0=a, b0=b显然有 (52) 当k时,区间(ak,bk)最终必收敛于一点,该点就是所求方程(51)的根x。 我们把每次二分后的有根区间(ak,bk)的中点 1()2kkkxab作为所求根x的近似值,这样获得一个近似根的序列 x0,x1,x2,xk,该序列必以根x为极限,即limkkxx111()2kkkkkxxbaba(53) 故对于预先给定的精度,若有11kkba 则结果xk就是

5、方程(51)满足预给精度的近似根,也即kxx由式(52)和(53)还可得到误差估计式为11()2kkxxba(54) 对于确定的精度,从式(54)易求得需要二等分的次数k。 二分法具有简单和易操作的优点。其计算步骤如下,框图如图5.3所示。1.计算步骤 输入有根区间的端点a,b及预先给定的精度;(a+b)/2 x;若f(a)f(x)0,则xb,转向;否则xa,转向。若b-a,则输出方程满足精度的根x,结束;否则转向。 2. 计算框图 例1 求方程 f(x)=x3-x-1=0 在区间(1,1.5)内的根。要求用四位小数计算,精确到10-2。 解 这里 a=1,b=1.5 取区间(1,1.5)的中

6、点01(1 1.5)1.252x 图 5.3 由于f(1)0,f(1.25)0,则令 a1=1.25, b1=1.5 得到新的有根区间(1.25,1.5) 表 51 2 迭代法迭代法 迭代法的基本思想是:首先将方程(51)改写成某种等价形式,由等价形式构造相应的迭代公式,然后选取方程的某个初始近似根x0,代入迭代公式反复校正根的近似值,直到满足精度要求为止。迭代法是一种数值计算中重要的逐次逼近方法。 例如,求方程 x3-x-1=0 在x=1.5附近的一个根(用六位有效数字计算)。 首先将原方程改写成等价形式31xx用初始近似根 x0=1.5 代入式(55)的右端可得3011.35721xx x

7、1与x0相差较大,如果改用x1作为近似根代入式(55)的右端得32110,1,2,xxk 表 52 对于一般形式的方程(51),首先我们设法将其化为下列等价形式 x=g(x) (57) 然后按(57)构造迭代公式 从给定的初始近似根x0出发,按迭代公式(58)可以得到一个数列 x0,x1,x2,xk, 若这个数列xk有极限,则迭代公式(58)是收敛的。此时数列的极限1(),0,1,2,kkxg xklimkkxx 就是原方程(51)的根。 虽然迭代法的基本思想很简单,但效果并不总是令人满意的。对于上例,若按方程写成另一种等价形式 x=x3-1 (59) 建立迭代公式 xk+1=x3k-1, k

8、=0,1,2, 仍取初始值x0=1.5, 则迭代结果为 x1=2.375 x2=12.3976 定理设方程x=g(x)在(a,b)内有根x,g(x)满足李普希茨(Lipschitz)条件:即对(a,b)内任意的x1和x2都有1212()()g xg xq xx q为某个确定的正数,若q1,则方程在(a,b)内有唯一的根;且迭代公式 xk+1=g(xk) 对任意初始近似值x0均收敛于方程的根x;还有误差估计式11011kkkkqqxxxxxxqq(511) 因为，对任意正整数p有 11211111()1kpkkpkpkkkkppkkpkkxxxxxxxxqqq xxqqxxq 当 时，p11kk

9、kpkxxqqxx 证 由已知条件知,x为方程x=g(x)的根,即x=g(x)()()xg xyg y设 也是方程的根,即xy于是,由李普希茨条件得因为q1,所以上式矛盾,故必有xy*)()(yxqygxgyx 亦即方程在(a,b)内有唯一的根。 再考虑迭代公式 x k+1=g(xk) , k=0,1,2, 由李普希茨条件10()()kkkxxg xg xq xx(512) 由(512)可得 10kkxxq xx(513) 因为q1,当k时,qk0,即有 10kxxlimkkxx所以 也就是对任意初始值x0迭代公式收敛。利用李普希茨条件111)()(kkkkkkxxqxgxgxx 迭代法的几何

10、意义:把方程(51)求根的问题改写成(57)变为求数列xn的极限,实际上是把求根问题转化为求( )yxyg x 图 5.4 迭代过程(58)就是在x轴取初始近似值x0,过x0作y轴的平行线交曲线y=g(x)于p0,p0的横坐标为x0,纵坐标为g(x0)(g(x0)=x1),也即 p0(x0,x1) 再在x轴上取x1作为新的近似值,过x1作y轴的平行线交曲线y=g(x)于p1,p1的横坐标为x1,纵坐标为 g(x1)(g(x1)=x2),也即 p1(x1,x2) 而这相当于过p0引平行于x轴的直线交y=x于 Q1(x1,x2) 再过Q1引平行于y轴的直线交曲线y=g(x)于 p1(x1,x2)

11、仿此可得到点列 p0(x0,x1),p1(x1,x2),p2(x2,x3), 若limlimkkkkppxx则迭代法收敛,见图5.4(a);否则迭代法发散,见图5.4(b)。 必须说明两点: 要验证g(x)是否满足李氏条件一般比较困难,若g(x)可微,可用充分条件来代替。这里q1是非常重要的条件,否则不能保证迭代收敛。 对于收敛的迭代过程,误差估计式(511)说明迭代值的偏差xk-xk-1相当小,就能保证迭代误差x-xk足够小。因此在具体计算时常常用条件 xk-x k-1 (515) 来控制迭代过程结束。 ( )1g xq 迭代法的突出优点是算法的逻辑结构简单,且在计算时,中间结果若有扰动,仍

12、不会影响计算结果。其计算步骤为: (1)确定方程f(x)=0的等价形式x=g(x),为确保迭代过程的收敛,要求g(x)满足李普希茨条件(或g(x)q1); (2)选取初始值x0,按公式 x k+1=g(xk), k=0,1,2, 进行迭代; (3)若x k+1-xk,则停止计算,xx k+1。 例2 求方程 x=e-x 在x=0.5附近的一个根。按五位小数计算,计算结果 的精度要求为=10-3。 解 过x=0.5以步长h=0.1计算 f(x)=x-e-x 由于 f(0.5)0,f(0.6)0 故所求的根在区间(0.5,0.6)内,且在x=0.5附近()0.61xe 图 5.5 表表 53 因此

13、用迭代公式 由表可见1xkkex 10 xxxxe为方程 最后,我们给出一个说明,在将方程(51)化为等价形式(57)时,g(x)的形式是多种多样的,选取不当,迭代公式(58)就不会收敛。最一般的形式可以写成 x=x+(x)f(x) (516) 这里(x)为任意一个正(或负)的函数。于是 g(x)=x+(x)f(x) (517) 这样可根据式(517)选取(x),使得迭代公式 (58)满足收敛条件 ( )11( )( )g xqa xfx 特别当取 (518) 时,由式(516)构造的迭代公式为下面要介绍的切线迭代公式;当取11( ),1,2,( )()kkxxa xkf xf x (519)

14、 时,可得到弦截迭代公式。 3 切线法切线法(牛顿法牛顿法) 切线法是求解方程(51)的一种重要迭代方法。如图5.6,曲线y=f(x)与x轴的交点x就是方程(51)的根。 图图 5.6 与x轴的交点为x k+1,其方程为1()()()0()()()kkkkkkkyf xfxxxf xfxxx 点xk+1满足该切线方程,即可得到切线迭代公式(或牛顿迭代公式)1(),0,1,2,()kkkkf xxxkfx(520) 切线法是非线性方程线性化的方法。其计算步骤为: 给出初始近似根x0及精度。 计算 若x1-x0,则转向;否则x1x0,转向。 输出满足精度的根x1,结束。 切线法的计算框图见图5.7

15、。 0010()()f xxxfx图 5.7 例3 用切线法求方程 xex-1=0 的根(取五位小数计算)。 取x0=0.5,迭代结果如表54所示。 由于11kxkkkkxexxxxxe 表表 54 切线迭代公式(520)对应着(51)的等价方程( )( )( )f xxxg xfx由于 2( )( )( )( )f x fxg xfx(521) 若 是方程(51)的一个单实根,即x()0,()0()0f xfxg x 所以,在点 附近切线法收敛,而且收敛速度比较快。 根据式(521)易得切线迭代公式的收敛条件为 x2( )( )( )1( )f x fxg xfx4 弦截法弦截法 切线法迭代

16、简单,收敛速度也较快,但就是需要计算导数f(x),有时使用会带来麻烦。这一节介绍的弦截法就避免了切线法的不足。 点xk+1满足该弦的方程,即有11()()()()kkkkkkf xf xyf xxxxx111()()0()()kkkkkkkf xf xf xxxxx从而可求得弦截迭代公式 111()()()()kkkkkkkf xxxxxf xf x(523) 图 5.8 表 55 例4 用弦截法解方程 xex-1=0 解 取x0=0.5,x1=0.6作为初始近似根,令 f(x)=x-e-x=0 利用公式(523)得到弦截迭代公式为1111()()()kkkxkkkkkxxkkxexxxxxx

17、xe计算结果见表55。 与切线法的计算结果比较,可以看出弦截法的收敛速度也是比较快的。 5 加速迭代法加速迭代法 已知方程(51)的近似根xk,按迭代公式(58)可求得x k+1。现考虑把x k+1作为过渡值,记为1()kkxg x(524) 11kkkxmxnx(525) 还是设x为方程(51)的一个实根,即 由式(524)和(526)得到 ()xg x11()()( )()kkkkxxg xg xxxgxx也即 11()1111,11kkkkkxxa xxaxxxaaamnxaa整理得到 于是,只要取 (527) (528) (529) 这样可得到加速迭代公式 111()111kkkkkx

18、g xaxxxaa(530) 例5 用加速迭代公式求方程 x=e-x 在x=0.5附近的一个根。 解 因为在x=0.5附近 g(x)=-e-x g(0.5)=-e-0.5-0.6 故加速迭代公式的具体形式为11110.61.61.6kxkkkkxexxx表 56 图 5.9 与例2比较,同一例用一般迭代法要迭代十次才能得到满足精度=10-3的结果,而这里仅迭代三次便可达到=10-5的高精度结果。这种加速过程取得的效果极为显著。 为了避免计算导数ag(x),下面介绍埃特金(Aitken)迭代方法。它也是一种加速迭代法。 11111()()()()kkkkkxg xxxg xg xa xx(531) 将式(527)与式(531)联立消去a得到1