第9章 2-非线性方程组的迭代解法

1、 中至少有一个是中至少有一个是x的非线的非线性函数，若其全为线性的则为线性方程组。性函数，若其全为线性的则为线性方程组。12(,)(1, 2,)infxxxin9.3 非线性方程组的迭代解法非线性方程组的迭代解法TnxfxfxfxF)(),(),()(21 含有含有n个未知数的个未知数的n个方程的非线性方程组为个方程的非线性方程组为 (1)其中其中 为为n维列向量，维列向量，0)( xFTnxxxx),(21 非线性方程组包非线性方程组包 括：括： 高次方程组高次方程组, ,即即代数方程组代数方程组超越方程组超越方程组产生背景产生背景: 许多科学理论与工程技术都可化为非线性方程组许多科学理论与

2、工程技术都可化为非线性方程组求解的特点：求解的特点： 无求解公式，无直接解法无求解公式，无直接解法， 难求得精确解。难求得精确解。求解的方法：求解的方法： 间接法即迭代法。间接法即迭代法。迭代法求解的要求：迭代法求解的要求： l 收敛收敛l 计算效率计算效率( (快慢快慢) )l 数值稳定性数值稳定性( (考虑计算机的舍入误差考虑计算机的舍入误差) ) 初始值好初始值好迭代公式合适迭代公式合适( (好的好的) )一一.一般迭代法一般迭代法 ( )0 ( ) fxxxf改 写为 同 解 方 程其 中 ，连 续1 ( ) (0,1,2,.) kkxxk由迭代公式 121 ,.,.,*kkkx xx

3、xxx产生数列若收敛，设极限为，则1limlim ()*( *)kkkkxxxx10 *( ),kxf xkx即即是是之之根根，故故当当 充充分分大大时时可可作作近近似似值值1.建立建立xyy = xxyy = xxyy = xxyy = xx*x*x*x*x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1)(xy)(xy)(xy)(xy)(xy2.迭代法的收敛性迭代法的收敛性 3 1(,.) , xa b设迭代函数在上定连续理且满足;)(,)1(bxabax时当有且满足存在一正数,10,)2(baxLLLx| )(|1 .( ) , *oxxa bx则方程在内有唯一

4、解012 . , ,()*okkxa bxxx对于任意初值迭代法均收敛于11*.3kkkoxxLLxx011*.4xxLLxxkko(局部收敛性)（收敛定理）（收敛定理）则则设设),x(x)x(g 连连续续)(,0)()(,0)()(xbbbgaaag*x , , g(x )0, |( ) |1 g (x)1(x)0g(x),g(x)0a,b.x(x)a,b x .a bxL故 至 少 有 一 个 根使由则递 增 故在上 根 唯 一 即在内 有 唯 一 解),x(xkk 1对对于于迭迭代代法法由微分中值定理由微分中值定理*1xxk*)()(xxk*)(xxkkkxx1)()(1kkxx)(1k

5、kxxkkxx11kkxxL*1xxk*xxLk)(*11kkkxxxxL)(*11kkkxxLxxLkkkxxLLxx111*Lx|)(|由于11*kkkxxLLxx2121kkxxLL011xxLLk0 1 *)xx(lim,Lkk由由于于*)(,10 xxxxkk均收敛于迭代法因此对任意初值11*kkkxxLLxx011xxLLk注注：L L越小，收敛越快。越小，收敛越快。指出指出:只要构造的迭代函数满足只要构造的迭代函数满足1|)(|Lx就收敛迭代法)(1kkxx3o4o 迭代法的收敛阶迭代法的收敛阶(收敛速度收敛速度) 定义定义3.1. :设设.limkkx 若有实数若有实数c0,p

6、11,使使1| (0)|lim|kpkkccxx 则称则称kx是是 p阶阶收敛收敛,相应的迭代法称为相应的迭代法称为p阶方法阶方法. 特别特别, p = 1,称线性收敛称线性收敛; 1p2,称超线性收敛称超线性收敛 p=2,称平方收敛。称平方收敛。(2)3. 非线性方程组的一般迭代法非线性方程组的一般迭代法12( )( ),( ),( )Tnxxxxx (3)并构造不动点迭代法并构造不动点迭代法 (1)( )(),0,1,kkxxk (4) 把方程组把方程组(1)改写成下面便于迭代的等价形式：改写成下面便于迭代的等价形式：对于给定的初始点对于给定的初始点(0)x, ,若由此生成的序列若由此生成

7、的序列( )kx收敛，收敛，*)(limxxkk (1)(1)的解。的解。是方程组是方程组 的不动点，的不动点， 是迭是迭。即。即满足满足连续函数连续函数. .则则的的是自变量是自变量是连续的是连续的, ,即即. .且且( )x12( ),( ),( )nxxx12,nx xx*x*()xx *x代函数代函数( )x*x例例1 设有非线性方程组设有非线性方程组081008102122122121xxxxxxx把它写成等价形式把它写成等价形式 22111212222121 211( ,)(8)101( ,)(8)10 xx xxxxx xx xx并由此构造不动点迭代法并由此构造不动点迭代法 (1

8、)( )( )( ) 2( ) 2111212(1)( )( )( )( ) 2( )22121211(,)()()8101(,)()810kkkkkkkkkkkxxxxxxxxxxx, 1 , 0k)(1kx)(2kx取初始点取初始点 。计算结果列于表。计算结果列于表1，可见迭代收敛到方，可见迭代收敛到方程的解程的解Tx)0 , 0()0(Tx) 1 , 1 (*表表 1k012 18 1900.80.9280.9999999720.99999998900.80.9310.9999999720.999999989 函数也称映射，若函数函数也称映射，若函数 的定义域为的定义域为 ，则可，则可用

9、映射符号用映射符号 简便地表示为简便地表示为 。为了讨论不动。为了讨论不动点迭代法（点迭代法（4）的收敛性，先定义向量值函数的映内性和压）的收敛性，先定义向量值函数的映内性和压缩性。缩性。)(xnRDnnRRD:二二.牛顿迭代法牛顿迭代法1. 一元方程牛顿法一元方程牛顿法将将 在点在点 作作TaylorTaylor展开展开: : 2()( )()()()()2!( )()()()kkkkkkkkfxf xf xfxxxxxf xf xfxxxTaylorTaylor展开线性化（展开线性化（重要思想重要思想） 近似于近似于 解出解出 , 记为记为 , ,则则1 (k0,() 1,.) ( 5)(

10、kkkkf xxxfxkx( )0f x ()()()0kkkf xfxxx( )f xx1kx 与与 轴轴的交点的交点 ，作为下一个迭代点，作为下一个迭代点 , ,即即 用用 在点在点 处处的切线的切线kx( )f x()()()kkkyf xfxxxxx1kx1() ()kkkkf xxxfx)()(1kkkkxfxfxxNewtonNewton迭代法迭代法需要求每个迭代点处的导数需要求每个迭代点处的导数复杂！复杂！0(),kkxfxx用近似替代中的得)()(01xfxfxxkkk(6)这种格式称为这种格式称为简化简化NewtonNewton迭代法迭代法精度稍低精度稍低()kf x无论哪种

11、迭代法：无论哪种迭代法：NewtonNewton迭代法迭代法简化简化NewtonNewton法法( )arctan0,x*0f xx精确解用用NewtonNewton迭代法求解迭代法求解: :)1(arctan21kkkkxxxxx0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017是否收敛均与初值的位置有关是否收敛均与初值的位置有关. .20 x若若取取初初值值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.963110-10 x5 = 0收敛收敛发散发散10 x若若取取初初值值2. 非线性方程组的非线

12、性方程组的Newton法法 对于非线性方程组，也可以构造类似于一元方程的对于非线性方程组，也可以构造类似于一元方程的Newton迭代法。设迭代法。设 是方程组（是方程组（1）的解，）的解， 是方程组的一个近似解。是方程组的一个近似解。用点用点 处的一阶处的一阶Taylor展开式近似每一个分量函数展开式近似每一个分量函数的值的值 ，有，有*x)(kx)(kx0)(* xfi( )*( )*( )1()()()(),1,2,knkkiiijjjjf xf xf xxxinx其中其中 为为 的的Jacobi矩阵矩阵 在在 的值，而的值，而写成向量形式有写成向量形式有*( )( )*( )()()()

13、()kkkF xF xF xxx)( )(kxF)(xF)( xF)(kx 11112122221212( )( )( )( )( )( )( )( )( )TnTnTnnnnnfxf xf xxxxf xfxfxfxfxxxxFxfxfxfxfxxxx若矩阵若矩阵 非奇异，则可以用使（非奇异，则可以用使（7）右端为零的向量作为）右端为零的向量作为一个新的一个新的 的近似值，记为的近似值，记为 ，于是得到，于是得到Newton迭代法迭代法)( )(kxF*x)1( kx(1)( )( )1( )()(),1,2,kkkkxxF xF xk（8)0(x)()(1kkxx其中其中 是给定的初值向量

14、。如果写成一般不动点迭代是给定的初值向量。如果写成一般不动点迭代 的形式，则的形式，则Newton迭代函数为迭代函数为)()( ()(1xFxFxx(9)在在Newton法实际计算过程中，第法实际计算过程中，第k步是先解线性方程组步是先解线性方程组解出解出 后，再令后，再令 ，其中包括了计算向量，其中包括了计算向量 和矩阵和矩阵 )()( )()()(kkkxFxxF(10)(kxkkkxxx )1()()(kxF)( )(kxF例例4 用用Newton法解例法解例1的方程组的方程组解解 对该方程组有对该方程组有取初始向量取初始向量 ，解方程组，解方程组 ，即，即2211221212108( )108xxxF xx xxx1222122102( )1210 xxF xxx xTx)0 , 0()0()()( )0()0()0(xFxxF88101010)0(x081008102122122121xxxxxxx求出求出 后，后， 。同理计算。同理计算 结果结果列于表