解非线性方程组的迭代解法课件.ppt

1、4.2 非线性方程组的迭代解法非线性方程组的迭代解法4.2.1 预备知识预备知识一、一般非线性方程组及其向量表示法一、一般非线性方程组及其向量表示法11221212(,)0(,)0 (4.2.1)(,)0nnnnfx xxfx xxfx xx (1,2, )niif inDRnf 其其中中，是是定定义义在在区区域域上上的的 元元实实值值函函数数，且且 中中至至少少有有一一个个是是非非性性性性函函数数。nn含含有有 个个方方程程的的 元元非非线线性性方方程程组组的的一一般般形形式式为为 TT1212,( )( ),( ),( )( )4. 2.2nnxx xxF xfxfxF xfx 令令，则则

2、方方程程组组可可表表示示为为 （ ）:nnnFDRRDR其其中中，是是定定义义在在区区域域上上的的向向量量值值函函数数。*,()xDF xx 若若存存在在使使，则则称称是是方方程程组组(4.2.1)(4.2.1)或或(4.2.2)(4.2.2)的的解解。二、多元微分学补充二、多元微分学补充()-( )- ( )lim0 (4.2.3) Thf xhf xl xhh int() () ( ),1nnfDRRxDxDl xR 设设 ：，即即 是是 的的内内点点 ，若若存存在在向向量量定定义义使使极极限限( )( )( )fxl xfxfxl xDfDfD 成成立立，则则称称 在在 处处可可微微，向

3、向量量称称为为 在在 处处的的导导数数，记记为为：；若若 是是开开区区域域且且 在在 内内每每一一点点都都可可微微，则则称称 在在 内内可可微微。 :int()(1,2,1)njfDRRxDfxfjnx 若若在在处处可可微微, ,则则 在在 处处关关于于各各自自变变量量的的偏偏导导数数定定理理存存在在，且且有有oo1 ( ) grad ( )( )2 ( ) fxfxfxf xf xf xfx 在在处处的的导导数数又又称称为为在在处处的的梯梯度度，可可记记为为或或；梯梯度度存存在在只只是是函函数数 在在 处处可可微微的的必必要要条条件件而而非非充充分分条条件件。说说明明：T12 ( ),nff

4、ffxxxx 定理1定理定理1证明证明 T12( )( ), ( ),( ),(njl xlx lxlxhe 证证明明取取：记记实实数数T12( )( ),nffffxl xxxx 存存在在，且且有有0()( )( )lim0,1,2,jjf xef xlxjn 0,),(4.2.3)jen 是是 维维基基本本单单位位向向量量 由由于于成成立立，故故有有0()( )( )lim( ),1,2,jjjf xef xf xlxjnx 从从而而 int(2) ( ),nnn nFDRRxDA xR 设设 ：，定定若若存存在在矩矩阵阵义义使使极极限限向量值函数的可微性()-( )-( )lim0 (4

5、.2. 4)hF xhF xA x hh ( ) ( )( ) FxA xFxFxA xDFDFD 成成立立，则则称称 在在 处处可可微微，矩矩阵阵称称为为 在在 处处的的导导数数记记为为；若若 是是开开区区域域且且 在在 内内每每一一点点都都可可微微，则则称称在在 内内可可微微。 :,int()1,2,nniFDRRFxDFf inxFx 设设为为向向量量值值函函数数 则则 在在处处可可微微的的充充分分必必要要条条件件是是 的的所所有有分分量量 ()()在在处处可可定定理理微微；若若 在在 处处2 2可可微微, ,则则有有JacobiFx称称为为 在在 处处的的矩矩阵阵。1111212( )

6、( )( )( )( )( )( )( )nijn nnnnnfxfxfxxxxf xFxxfxfxfxxxx 定理2定理2证明 T12( )( ),)( ,( )nF xfxfxfx 由由于于, ,证证明明：所所以以，存存在在( ), nil xR 向向量量使使极极限限()-( )- ( )lim01,2,Tiihf xhf xl xhinh ( ),(4.2.4)n nA xR 存存在在矩矩阵阵使使式式成成立立是是成成立立，与与等等价价的的， TTTT12( )( ),( ),( ),nA xl xlxlx 并并且且即即( )(1,2, )( )ifxinxF xx 在在 处处可可微微是是

7、在在 处处可可微微的的充充分分必必2( )F xx要要条条件件。又又根根据据定定理理 ，当当在在 处处可可微微时时，有有( )( )ijn nf xFxx 定理3 :nnFDRR 定定3 3 设设理理JacobiFxFxo o1 1 若若在在 处处的的矩矩阵阵存存在在且且连连续续，则则在在 处处可可( ) ( )ijn nf xFxFxx 微微，此此时时称称 在在 处处连连续续可可微微，且且 int()FxDFx o o2 2若若 在在处处可可微微，则则 在在 处处连连续续；0 FDDD o o 3 3若若 在在开开区区域域 内内可可微微, ,为为开开凸凸区区域域，则则对对任任意意00 xDx

8、hD 的的和和，以以下下等等式式成成立立 1122()()( + )( )01,1,2,()TTkTnnfxhfxhF x hF xhknfxh 其其中中, ,。三、收敛向量序列的收敛速度三、收敛向量序列的收敛速度 kxrc是是阶阶收收敛敛的的， 是是它它的的收收敛敛因因子子。 * , 3 0, kkkxxexx 设设向向量量序序列列收收敛敛于于定定义义1,2,10krc 如如果果存存在在常常数数和和常常数数，使使极极限限 1limkrkkece 1()rkkkKee 成成立立，或或者者使使得得当当某某个个常常数数 时时，有有 * kxxr成成立立，则则称称序序列列收收敛敛于于具具有有阶阶速速

9、度度，简简称称 =101kxrc 当当时时，称称序序列列是是线线性性收收敛敛的的，此此时时必必有有； 1kxr当当时时，称称序序列列是是超超线线性性收收敛敛的的； =2kxr当当时时，称称序序列列是是平平方方收收敛敛的的；4.2.2 简单迭代法简单迭代法( )0F x 把把方方程程组组改改写写成成与与之之等等价价的的形形式式 ( xG x ) )( (4 4. .2 2. .5 5) )*(nnGDRRxDxG xx 其其中中 ：。若若满满足足) ), ,则则称称(G xG x为为函函数数) )的的。因因此此) )的的不不动动点点就就不不动动点点是是方方程程组组( )0;( )0F xF x

10、的的解解 求求方方程程组组的的解解就就转转化化为为求求函函数数的的(G x) )的的不不动动点点。(0),xD 适适当当选选取取初初始始向向量量构构成成迭迭代代公公式式迭代公式迭代公式 (4.2.6) 称为求解方程组称为求解方程组 F(x)=0 的的简单迭代法简单迭代法，又称为不动点迭代法。又称为不动点迭代法。G(x)称为迭代函数。称为迭代函数。 简单迭代法简单迭代法( +1)( )(),0,1,2, (4.2.6)kkxG xk (0)(+1)()0(1) ,(),0,1,2,kkxDxG xk 对对任任取取的的由由迭迭代代公公式式产产生生*( )(1)(0)(2) (4.2.8)1kkLx

11、xxxL 成成立立误误差差估估计计式式 压缩映射原理04() nnGDRRDD 设设 ：在在闭闭域域定定理理压压缩缩映映象象原原理理上上满满足足条条件件o0001 ();GDG DD 把把映映入入它它自自身身，即即o002 G(0,1),DLx yD 在在上上是是压压缩缩映映射射，即即存存在在常常数数使使对对任任意意的的则则以以下下结结论论成成立立： ( )*00( );kxDG xDx 的的序序列列收收敛敛于于函函数数在在区区域域内内存存在在唯唯一一的的不不动动点点( )( ) (4.2.7)G xG yL xy *( )( )(1) 1kkkLxxxxL (4.2.9)o0 (1) 1D

12、( (0 0) )由由于于x x以以及及条条件件 可可知知由由( (4 4. .2 2. .6 6) )证证明明产产生生的的序序压缩映射原理的证明 o( )02kDx 列列有有意意义义且且。又又由由条条件件得得( )( )()()kkG xG x ( )(1)kkL xx (1)( )kkxx 1m 当当时时有有(1)(0)(4.2.10)1kLxxL (1)(0)kL xx ()( )k mkxx ()(1)1mk ik iixx 1(1)(0)1mk iiLxx (1)(0)(1)1kmLLxxL *o( )002( )kDxDG xx 是是闭闭区区域域，的的极极限限。又又由由条条件件 知

13、知，01,Lk 因因所所以以当当 趋趋于于 时时，上上式式中中的的最最后后一一项项是是无无穷穷 ( )CauchynkRx小小量量，由由收收敛敛原原理理，序序列列在在中中收收敛敛，又又由由*(1)( )*0limlim()()kkkkDxxG xG x 在在上上连连续续，因因而而有有，*( )0 xF x 即即是是方方程程组组的的解解。*0,( )0 xyDF x 设设是是的的两两个个不不同同的的解解，则则有有*()()xyG xG y*L xy *xy*0( )0 xF xD 这这表表明明，是是在在内内的的是是唯唯一一解解。*( )(1)(0)(4.2.10) , 12)kkLxxxxLm

14、在在中中，让让得得( )(1)1kkLxxL ()( )k mkxx ()(1)1mk ik iixx ( )(1)1mikkiL xx ( )(1)(1)1mkkLLxxL *( )( )(1),1kkkLxxxmxL 再再让让得得说明说明( )(1)o( )*( +1)o*( )o1 ( )2 3 ( ),=1 kkkkkxxe kxxxLxxG xBxdLB 简简单单迭迭代代法法的的精精度度控控制制与与终终止止条条件件；由由知知简简单单迭迭代代法法是是线线性性收收敛敛的的；对对线线性性方方程程组组迭迭代代函函数数有有是是收收敛敛的的充充分分必必要要条条件件。局部收敛定理 *0(0)( +

15、1)( )0( )*0int() ( )0 ( )5() ( )1,0 ,(),0,1,2, nnkkkGDRRxDF xxG xG xDx xxxDxG xkxDx 设设 ：, ,是是方方程程组组的的解解， 在在可可微微。若若谱谱半半径径则则存存在在开开球球对对任任取取的的由由迭迭代代公公定定理理局局部部收收敛敛式式产产生生序序列列收收敛敛于于定定理理。例例1 1例例1 用简单迭代法求解以下方程组用简单迭代法求解以下方程组1122123cossin04sincos0 xxxxxx ( )(1)12( )( )10kkkxxe kx 要要求求满满足足精精度度解：解：设设1212121(coss

16、in)3, ( )1(sincos)4xxxxG xxxx ( )xG x 则则方方程程组组可可改改写写成成。22,xRyR 并并且且，对对任任意意的的112212221(coscossinsin)3( )( )1(sinsincoscos)4xyxyG xG yxyxy 712A xyAxyxy 121211sincos733,1211cossin44AA 其其中中， (0)( ),kxRx 因因此此，任任取取初初始始向向量量简简单单迭迭代代法法产产生生序序列列收收敛敛于于原原方方程程组组的的唯唯一一解解。 0 1.000000000000 1.000000000000 1 0.460591

17、096892 0.345443322669 1.421123164881 2 0.411467922913 0.346350778276 0.119385184710 4 0.414178646247 0.337726634268 0.01083777184826 0.415169427139 0.336791217026 0.00000000000527 0.415169427139 0.336791217025 0.00000000000228 0.415169427139 0.336791217025 0.000000000001( )( )12 ( ) kkkexkx (1)( )(

18、)112(1)( )( )2121=cossin31sincos4kkkkkkxxxxxx 迭迭代代公公式式：计算结果计算结果4.2.3 Newton迭代法迭代法*( )0int()( ) F xxDF xx 方方程程组组存存在在解解，在在设设的的某某个个开开 *( )0,0kDx xxx 球球内内可可微微。又又设设是是方方程程组组的的( )TaylorkF x第第 个个近近似似值值，则则由由的的一一阶阶近近似似( )( )( )1()( )()()knkkiiijjjjf xf xf xxxx ( )( )( )()()()1,2,Tkkkifxfxxxin Newton迭迭代法代法的构的构

19、造造用用线线性性方方程程组组 ( )( )( )()()()01,2,Tkkkif xfxxxin ( )( )( ) () (4.2.11)kkkFxxxF x 即即( )0F x 近近似似代代替替原原非非线线性性方方程程组组，并并用用它它的的解解近近似似作作为为( )0F xk 的的第第 + +1 1个个近近似似解解，由由此此得得到到迭迭代代公公式式 1(1)( )( )( )()0,1,2, (4.2.12)kkkkxxFxF xk (4.2.12Newton) 解解非非称称迭迭代代公公式式为为线线性性程程组组的的法法。方方收敛性定理 *00( )00*( )int()( )0( ) (

20、) ,0, Newton( 6 )kkxDF xF xxSDFxDx xxSxDDxxF xSxx 是是方方程程组组的的解解，在在包包含含 的的某某个个开开区区域域内内内内连连续续可可微微，且且可可逆逆，则则存存在在闭闭球球使使对对任任意意的的，由由法法产产生生的的迭迭代代序序列列且且超超线线性性收收敛敛于于 ；若若更更有有在在 内内二二阶阶连连续续可可微微，则则序序列列至至少少平平方方收收敛敛定定于于设设理理。Newton迭代算法迭代算法 o*(0)0( )( )( )( )( )*( )( )( +1)( )( )( )1 0,1,2,(1)(2) ,(4)(4) =+:1(5),()(3

21、1) ) kkkkkkkkkkkkxxDMkF xFxxxxxxxxxxkkFxkMF x o o在在 附附近近选选取取，给给定定精精度度水水平平 和和最最大大迭迭代代次次数数；2 2对对于于执执行行计计算算和和；求求解解关关于于的的线线性性方方程程组组则则，终终止止迭迭代代；否否则则转转；计计算算，；若若转转；若若继继续续 M 迭迭代代；否否则则 输输出出次次迭迭代代不不成成功功的的信信息息，终终止止迭迭代代。例2例例2 用用Newton迭代法求解例迭代法求解例1中的方程组中的方程组解：解： 0 1.000000000000 1.000000000000 -5.052e-001 -5.972

22、e-001 1 0.494755413740 0.402823742334 -7.826e-002 -6.498e-002 1.207e+00 2 0.416494170060 0.337842812163 -1.324e-003 -1.051e-003 1.879e-001 3 0.415169794209 0.336791496852 -3.671e-007 -2.798e-007 3.190e-003 4 0.415169427139 0.336791217025 -2.770e-014 -2.067e-014 8.841e-007 5 0.415169427139 0.336791217025 6.673e-014( )( )( )( )( )( )121112( )( )( )( )( )( )122212( +1)( )( ) Newton3sincos3cossincos4sin4sincos=+0,1,2,kkkkkkkkkkkkkkkxxxxxxxxxxxxxxxk 法法迭迭代代公公式式为为，( )( )( )( )1212 ( )kkkkkxxxexk计算结果计算结果