第6章方程与方程组迭代解法

1、第第6章章 方程与方程组的迭代解法方程与方程组的迭代解法n方程求根法n线性代数方程组迭代解法n非线性方程组的迭代解法引言引言12( )0( ,)0(1,2, )inf xAxbf x xxin本章重点介绍求解非线性方程的几种常见和有效的数值方法，同时也对线性方程组及非线性方程组的求解介绍一些最基本的解法。这些方法是对经典的解析方法的突破性开拓和补充，数值方法可借助计算机完成。6.1 方程求根法方程求根法n试探法与二分法n迭代法及其收敛条件n迭代法收敛速度n加速收敛技术n牛顿迭代法n弦割法( )0f x 本节讨论求解方程 的近似解法。6.1.1 试探法和二分法试探法和二分法( ) , ( ) (

2、 )0,( , )( )0( )0yf xa bf a f ba bff xf x：如果函数在区间连续且则在区间内必定存在 ，使。 称为函数（ ）的零零点定点或理的根。理论依据：理论依据：试探法试探法11()01() ()0()2kkkkkkf xxf xf xxxh1.若发现，则取 为 ；2.若发现，则取为 。 所得 的近似值误差不超过 。01-,(0),(), ( ),().inb anhxaih innf xf xf x任取正整数 令顺次计算，二分法（区间平分法）二分法（区间平分法） 1111112 , ,()a baa bb cab先 确 定 有 根 区 间 令111111122221

3、122. () ( )0, , ,().f af ca cc ba bbaba若则 为有根区间， 否则 为有根区间.记新的有根区间为 且11.( )0,f cc1 若则根223.,a b对于重复上述过程.*,1212nnnnxxa bnaxbn设所求的根为 ，则 ， ，即 ， ，0)(21lim)(lim1nababnnnnxbannnnlimlim1()2nnnxcab可可取取 11221,() 2nnnnna ba ba bbaba于是求方程求方程 f(x)=0的根的二分法算法的根的二分法算法(1): , ,;(2)( ) ( )01,3;(3)|11)(),( );22)( ) ( )0

4、 , , ; , , .end while;1(4)().2a ba biff a f bthena belsewhile abxabf xiff a f xthena ba xelsea bx bxab输入 有根区间的值及精度控制量返回第 步 重新输入值转第 步时做令计算输出例题例题n例 设方程 解：取h=0.1,扫描得： 又 即 在 有唯一根。 2 , 1 , , 1)(3baxxxf0344. 0)4 . 1 (061. 0)3 . 1 (ff.4 . 1 , 3 . 1 方程的有根区间为2( )310,1.3,1.4fxxx 0)(xf4 . 1 , 3 . 1 有根区间有根区间：1.

5、300000000, 1.4000000001.300000000, 1.3500000001.300000000, 1.3250000001.312500000, 1.3250000001.318750000, 1.3250000001.321875000, 1.3250000001.323437500, 1.3250000001.324218750, 1.3250000001.324609375, 1.325000000 x1.32480f=3.6990*10(-4)6.1.2 迭代法及收敛性迭代法及收敛性对于 有时可以写成 形式 0)(xf)(xxxxxxcos0cos3331011xx

6、xxxx 如：如：迭代法及收敛性迭代法及收敛性 考察方程 。这种方程是隐式方程，因而不能直接求出它的根，但如果给出根的某个猜测值 ， 代入 中的右端得到 ，再以 为一个猜测值，代入 的右端得 反复迭代得)(xx0 x)(xx)(01xx1x)(xx)(12xx1()0,1,kkxxk迭代法及收敛性迭代法及收敛性 若 收敛， 即 故 是 的一个根kxklimkx)(xxn 1limlim ()(lim)( )nnnnnxxx 1()0,1,kkxxk迭代法的几何意义迭代法的几何意义n 交点的横坐标 *x)()(xyxyxxy=x2x0 x1x简单迭代法简单迭代法 将 变为另一种等价形式 。选取

7、的某一近似值 ，则按递推关系 产生迭代序列 。这种方法称为简单迭代法。0)(xf)(xx,0bax k 1k()0,1,xxkkx例题例题33111, 0,1,2,kkxxxxk解：由建立迭代公式计算结果如下：3( )10f xxx试用迭代法求方程在区间(1,3)内的实根。例题例题n精确到小数点后五位5102132472. 1x例题n但如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列31xx3111,2,kkxxk 5 . 10 x 2.3751x 12.392x kx迭代法的收敛性迭代法的收敛性01 , ()( ) , kkxa bxxxxa b则对任意初值，由迭代产生

8、的数列收敛于方程在的唯一根。( )1) , ( ) , 1 , ( )1,xxa bxa bLxa bxL迭代收敛定理：设迭代函数满足条件：当时，；2)存在正数，使对任意，有迭代收敛定理迭代收敛定理n证明：不失一般性，不妨设 否则 为方程的根。n首先证明根的存在性首先证明根的存在性 令 ( ), ( )aabbba或( )( )g xxx迭代收敛定理迭代收敛定理 则 ， 即 由条件2） 是 上的连续函数所以 是 上的连续函数。故由零点定理 在 上至少有一根( )( )0g aaa( )0g b ( )( )0g ag b)(x,ba( )g x,ba( )0g x ,ba( , )a b迭代收

9、敛定理迭代收敛定理n再证根的唯一性 设有 均为方程的根 则 因为 0L1 ，所以只可能 ， 即根是唯一的。12, , a b 121212| |()()|L 12迭代收敛定理迭代收敛定理n最后证迭代序列的收敛性 与n 无关，而0L1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。迭代法p 阶收敛的充要条件是：迭代函数 满足( )x(1)( )( )( )( )00pp ，但。6.1.4 加速收敛技术加速收敛技术*1. (1)kkkxxx1松弛法：适当选取常数 (称为松弛因子)，令22*112122.()() ()2kkkkkkkkkkkkkxxxxxxxxxxxxx艾特肯加速法：线性收

10、敛时，令2111212().2kkkkkkkkkkxxxxxxxxxx，其中 为根12121123(),1,2,4,5,7,8,; (),3,6,9,2kkkkkkkkkxxkxxxxkxxx斯蒂芬森迭代法：1/1( ) 最佳因子11 ()(1)kkkxxx松弛迭代法：适当选取常数 (称为松弛因子)，令1001111(), 3.(),1,2,3, ()()kkkkkkkkkkkkxzxzxkxxxzxxxzxz插值加速法：6.1.5 Newton迭代法迭代法0200000( )0( )1( )()()()()( )2f xxf xf xf xxxfxxxfxx设是的根，又为 附近的一个值，对作

11、泰勒展开，其中 在 和之间2000010( )()()()()( )2xff xxfxxf令，则Newton迭代法迭代法去掉 的二次项，有：即以x1代替x0重复以上的过程，继续下去得：0 x0000()()()0f xfxx fx0100()()f xxxfxNewton迭代法迭代法1()0,1,()( )0nnnnnf xxxnfxxf x以此产生的序列来得到的近Newton法，又似解，称之为称切线法。Newton迭代法几何解释迭代法几何解释n几何意义例例 用牛顿法求 的近似解。解：由零点定理：0cos)(xxxf内有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsin1)(

12、1cos0,11 sinnnnnnxxxxnx，01234440.739361330.7390851780.7390851330.7390851330.739085133xxxxxx取得，故取 例题n例 用Newton法计算 解：22( )02f xxaa其中迭代公式得及由Newtonxxf2)(21212()0,1,22nnnnnnxxxxnxx012331.51.416666671.4142156861.4142135622 xxxxx取，则，。与的精确值相比， 是已有十位有效数的近似值。Newton迭代法算法框图迭代法算法框图Newton迭代法算法迭代法算法。输出）转（做输入110100

13、1001000:)4(;2) 3;)2;/) 1|while(3);();()2(;,) 1 (xendwhilexxffxxfxffxffxNewton迭代法收敛性迭代法收敛性定理 设函数 ，且满足 若初值 满足 时，由Newton法产生的序列收敛到 在a,b上的唯一根。,)(2baCxf上恒正或恒负。在,)() 3);,( , 0)()2; 0)()() 1baxfbaxxfbfaf ,0bax 0)()(00 xfxf0)(xfNewton迭代法收敛性迭代法收敛性证明： 根的存在性n根的唯一性内至少有一个根。在知）及由条件（),(0)(,)(1baxfbaCxf( )0,( )Ca,b,

14、( )( ) , ( )0( , ),fxfxfxf xa bf xa b由及知保号，故是上严格单调函数，因此在内有唯一根 记此根为 。Newton迭代法收敛性迭代法收敛性n收敛性000000010000010( )0,( )0,( )0,( )0()()0 , ,()0,()0,()0()()0()()()f af bfxfxf xfxxbf xfxfxf xxxxfxf xfxxx不妨设，由知，所以而Newton迭代法收敛性迭代法收敛性 2000021001010,Taylor1 0( )()()()( )()21( )()02()ff xfxxfxfxxfxxxxx 另一方面由展式两式相

15、减因此有。再以 代替 继续上述推理有00100()()()fxfxxxNewton迭代法收敛性迭代法收敛性1lim()1,2,.(),( )0nnnnnnxf xxxnfxnf 故必有极限，记。由当时 可得，由根的唯一性知。110n 0. nnnxxxxx故序列是单调减有下界的序列。Newton迭代法收敛性迭代法收敛性n推论推论 在定理条件下，在定理条件下， Newton迭代法迭代法具有平方收敛速度。具有平方收敛速度。2n 112()1()2()1( )lim02( )nnnnnnnnfxxfxxefef 证明类似定理证明，一般有其中，介于 与 之间，则故结论成立。Newton迭代法的变形迭代

16、法的变形1k21k1k1.2 ()()sgn()()2 ()()()2.()()kkkkkkkkkkkkf xxxf xf xfxf xfxf xxxf xf xxxC改进牛顿迭代法： 牛顿下山法：， 为下山因子;3. 简化牛顿法：6.2.4 弦截法弦截法nNewton迭代法有一个较强的要求是迭代法有一个较强的要求是 且存在。因此，用弦的斜率且存在。因此，用弦的斜率 近似的替代近似的替代 。 0)( xf)(xf )()()()()(,(P)(,(P,)(10101111100010*xxxxxfxfxfyxfxxfxbxaxxbaxf得弦的方程及则过，取上有唯一零点在设弦截法弦截法n令y=0

17、,解得弦与x轴的交点是坐标x2123010,()(1,2,)()()nnnnnx xxxxxxf xnf xf x再由计算称之为定端点单点弦割法(弦截法).10121101021110( )()( )()0( )( )()f xf xf xxxxxxxxxf xf xf x解得弦截法弦截法123111,()(1,2,)()()nnnnnnnx xxxxxxf xnf xf x若由计算以此类推称之为双点弦割法(变端点弦截法,快速弦截法)。弦截法的几何解释弦截法的几何解释弦截法收敛定理弦截法收敛定理2*2121( ) , , , ,( )0,12max |( ) |,max |( ) |0axba

18、xbf xCa ba bxxxf xMqmMfxmfx 定理:设为足够小的正数是的根 如果其中，则010*111*(1)()1,2,()();(2)()1,2,()()( 51)/2nnnnnnnnnnnnnnxxxxf xnf xf xxxxxxxf xnf xf xxpx由，确定的序列线性收敛到由，确定的序列以的敛速收敛到 。6.2 线性方程组迭代解法线性方程组迭代解法 迭代法适用于系数矩阵为稀疏矩阵稀疏矩阵的方程组.n基本迭代法n基本迭代法的收敛条件6.2.1 基本迭代法基本迭代法(Jacobi迭代法迭代法)111221331112221 12332221 122,11()/,()/,0

19、,1()/.nnnniinnnnn nnnnxba xa xa xaxba xa xa xaAxbainxba xa xaxa123213121(1)( )( )( )11213111(1)( )( )( )22123222(1)( )( )( )12,1()/,()/,()/.nnnnkkkknkkkknkkkknnnn nnnxba xa xa xaxba xa xa xaxba xa xaxa迭代公式1(1)( )( )( )( )1,11,11()/,1.inkkkkkiii iii iiiniixba xaxaxa xa in 分量形式：12312312321312331220232

20、4,(2423)/20,812,(12)/8,2-31530.(3023)/15.Jacobixxxxxxxxxxxxxxxxxx例6.2.1：用迭代法求解方程组(0)(12)(13)(12)(0,0,0)(0.767353807,1.38409760,2.125368111)TTxxxxx取1232332(1)( )( )(1)( )( )1(1)( )( )1(2423)/20,(12)/8,(3023)/15.kkkkkkkkkxxxJacobixxxxxx迭代格式为：6.2.1 基本迭代法基本迭代法(Seidel迭代法迭代法)123213121(1)( )( )( )11213111(

21、1)(1)( )( )22123222(1)(1)(1)(1)12,1()/,()/,()/.nnnnkkkknkkkknkkkknnnn nnnxba xa xa xaxba xa xa xaxba xa xaxa迭代公式123213121(1)( )( )( )11213111(1)( )( )( )22123222(1)( )( )( )12,1()/,()/,Jacobi()/.nnnnkkkknkkkknkkkknnnn nnnxba xa xa xaxba xa xa xaxba xa xaxa迭代公式1232332(1)( )( )(1)(1)( )1(1)(1)(1)1(0)(

22、8)(9)(8)(2423)/20,(12)/8,(3023)/15.(0,0,0)=(0.767353807,1.38409760,2.125368111)kkkkkkkkkTTSeidelxxxxxxxxxxxxxx用迭代公式求解例6.2.1,迭代格式为：取6.2.1 基本迭代法基本迭代法(SOR迭代法迭代法)12312132121(1)( )( )( )( )11213111(1)(1)( )( )( )22123222(1)(1)(1)(1)( )12,1()/(1),()/(1),()/(1).nnnnnkkkkknkkkkknkkkkknnnn nnnxba xa xa xaxxb

23、a xa xa xaxxba xa xaxax123213121(1)( )( )( )11213111(1)(1)( )( )22123222(1)(1)(1)(1)12,1()/,()/,()/.nnnnkkkknkkkknkkkknnnn nnnxba xa xa xaxba xa xa xaSeidelxba xa xaxa迭代：6.2.2 基本迭代法收敛条件基本迭代法收敛条件(1)1( )(1)1( )(1)1( )();() ;() (1).kkkkkkJacobixDEF xbxDEFxbxDEDF xb则迭代格式： Seidel迭代格式： SOR迭代格式：12131112123

24、22231321,12,10 00 0 ,0 000nnnnnnnnn naaaaaaaaaaDEFaaaaa 记(1)( ).kkxBxg统一形式：迭代收敛定理迭代收敛定理112SOR023Jacobi01SOR4Jacobi2 SOR02BAADA推论 ：矩阵范数时迭代收敛。推论 ：法收敛的必要条件是。推论 ： 严格对角占优时迭代，的迭代收敛。推论 ： 对称正定时， 迭代收敛也对称正定，迭代收敛。(1)( )0( )1.kkkxBxgkBB 迭代法 收敛 时或谱半径例例6.4 判断求解判断求解AX=b的三种迭代法是否的三种迭代法是否收敛，其中收敛，其中A为为0111111210.50.5(

25、1)130 ,(2)0.510.52070.50.5122(3)22nnnAAA 112(1)130207A T,11211=10,=20,130201320711221302072Jacobi02SOR=1SeidelAAAADADA 122显然即 对称. 又顺序主子式故 对称正定，又显然也是对称正定的. 故按推论4，迭代及的迭代（包括的迭代）均收敛。(2) A对称正定，但|2D-A|=0,说明2D-A不正定，故Jacobi迭代发散，02时SOR迭代收敛；(3) A为严格对角占优矩阵，故Jacobi迭代收敛，0=1时SOR迭代收敛；011112210.50.5(2)0.510.5(3)20.

26、50.512nnnAA，1212945,3107.94Jacobi1SOR310 xxxxA 解： 交换方程次序得 严格对角占优， 故迭代，0的迭代收敛。1212.3107,945.xxxx 例65 对下列方程组写出保证收敛的迭代格式.(1)( )(1)( )( )12121(1)( )(1)(1)( )21212(54)/9(54)/9(1)0.70.3(0.70.3)(1)kkkkkkkkkkxxxxxxxxxx迭代格式分别为：6.3 非线性代数方程组的迭代解法非线性代数方程组的迭代解法11221212( ,)0,( ,)0,( ,)0.nnnnf x xxfx xxfx xx讨论如下非线

27、性方程组的迭代解法：6.3.1 简单迭代法简单迭代法111122221212( )( )1nnnnnnxxxxxxxxLxxx记 则时，简单迭代收敛。1212(1)( )( )( )(1)( )( ,),1(,),1().iniinkkkkikkxx xxinxxxxinxx 改写方程为：，作成迭代格式：，简单迭代的向量形式：6.3.1 Seidel迭代迭代1(1)(1)(1)( )( )1(,),1inkkkkkiiixxxxxin 迭代格式：，( )1122(1)( )(0)(7)(8)(7)(1)(1)(1)2111(10.1),0411() .48kxkkkkkxxexxxSeidelxxxxx迭代格式112212140.11,.140.8xxxeSeidelxxx例66：用简单迭代格式和迭代格式求解方程组1(1)( )( )( )( )1(,