第二章-非线性方程(组)的迭代解法课件.ppt

1、 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-161第二章 非线性方程非线性方程(组组)求根方法求根方法()0nnnf:RRxRf x问问题题：的的函函数数,求求使使。非线性 若 n=1,称为非线性方程求根非线性方程求根问题；n1，称为非线性方程组求解问题。理论问题：理论问题：（1）解的存在性存在性。即有解还是无解，有多少解。（2）解的性态性态。即孤立解的区域，解的重数，光滑性。关于解的存在性及其性态，不是数值分析所讨论的问题。我们总认为：，内有唯一解在一个确定的区域*)(xRxfn我

2、们的任务是用数值方法求满足一定精度要求的近似解！通常求其精确解是困难的 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-162 二分法内容内容:一般迭代法 牛顿迭代法 迭代法的加速 非线性方程组的牛顿迭代法*Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1631、二分法二分法:满足,找nn,ba,ba,baa,b1100设 在区间 上连续且有 ，则 在区间 内有解，不妨设解唯一不妨设

3、解唯一！)(xf0)()(bfaf,ba,ba)(xf算法构造原理算法构造原理:;即0,)()(1)nnnn,baxbfaf*(001121abababnnnnn)(21 (2).*limxxnn 2,令nnnbax111 *22nnnnxxbaba则()();有根区间 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-164x1aabx2b什么时候停止？b a)(1kxf或或x*算法停止的条件算法停止的条件x,其中为容许误差！Numerical Analysis J.G.Liu Schoo

4、l of Math.&Phys.North China Elec.P.U.2022-12-165综合上述，得到如下算法，综合上述，得到如下算法，(),();abff aff b输入，计算(1);(,2xffbax计算(2)为所求根，结束！则若xf,(3)否则否则;,0ffxbffba则若;,0ffxaffaa则若(4),2abbax若则为所求根，结束！否则否则，转(2)；例例1内的实根。，在计算21 0104)(23xxxf，取691010可得*1.36523,x 共计算21次！注：注：其中 为精度控制参数!,Numerical Analysis J.G.Liu School of Math.

5、&Phys.North China Elec.P.U.2022-12-166二分法只能求有根区间中的奇数重的实根;不变号了！(?)0,)(,为偶数时，当于是),(充分大以后，当xf,baxm,xx,bannnnn*关于二分法的讨论关于二分法的讨论(1)*mxf xmf xxxxxx事实上，设为()的 重根，即()()(）()连续且()0)。0)(时，当0,)的连续性，则(由0,)(不妨设xxxxx*二分法线性收敛;(2)二分法可用来细化有根区间，这是它的一大优点!(3)故二分法可以用来确定迭代法的迭代初值迭代初值!返回主目录 Numerical Analysis J.G.Liu School

6、of Math.&Phys.North China Elec.P.U.2022-12-1672、一般迭代法、一般迭代法(1)称为迭代函数。()，(0)(xxxxf(2)01*0 1 2)nnxUxxxn,构造迭代格式在解的邻域内选定初值(),()(3)。及收敛速度（收敛阶）的收敛性讨论nx(一一)构造方法构造方法(1)Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-168例例2的实根。，在用一般迭代法计算21 104)(23xxxf;)4/(10)(10)4(4410)(;4101043;

7、1021)(104 2;104)(1222333223xxxxxxxxxxxxxxxxxxxxxxxx：方法：方法：方法：方法401.5,10,x取初值用以上四种方法算，结果如下：Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1691.50001.5000-0.8750 -0.8750 6.7324 6.7324-69.7200-69.72001.0275e+81.0275e+8不收敛不收敛 1.50001.5000 1.2870 1.2870 1.4025 1.4025 1.3455

8、1.3455 1.3752 1.3752 1.3601 1.3601 1.3678 1.3678 1.3639 1.3639 1.3659 1.3659 1.3649 1.3649 1.3654 1.3654 1.3651 1.3651 1.3653 1.3653 1.3652 1.36521.3652 1.3652 1.5000 1.5000 0.8165 0.8165 2.9969 2.9969 0-2.9412i 0-2.9412i不收敛不收敛 1.5000 1.34841.3484 1.3674 1.3674 1.3650 1.3650 1.3653 1.3653 1.36521.36

9、52 1.3652 1.3652方法1方法2方法3方法4*收敛与否，以及收敛快慢，取决于迭代函数迭代函数15次6次*精度控制的表达式？Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1610011*xxLLxxnn(二二)大范围收敛定理大范围收敛定理1(),xCa b设，,)(,baxbax(1)(2),(,1)(baxLx；内有唯一的根在*,)(xbaxx则(1)01,(),lim*;nnnnnxa bxxxa bxx，由迭代=产生的序列且(2)(3)11*nnnxxLLxx 下面看证明

10、过程，即 是自映射；)(x Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1611(1),()(xxxF令由条件(1)可得解的存在性；由条件(2)可证解的唯一性！(2)由条件(1)可知;,baxn111*()(*)()*nnnnnxxxxxxL xx*0 xxLn 1L*;limxxnn(3)*)1(*111xxLxxLxxxxxxxxxxxxnnnnnnnnn得证；11nnnnxxL xx进而可证!Numerical Analysis J.G.Liu School of Math.&P

11、hys.North China Elec.P.U.2022-12-1612(三三)局部收敛定理局部收敛定理设*),(*xx)(x在包含x*某个开区间内连续，若,1*)(Lx*limxxnn由迭代(1)产生的序列 ,*,*xxxn,*,*0 xxx使得,0则证明证明:略略!注：注：当定理条件成立时，只要x0充分充分接近x*，就能保证迭代序列xn收敛于x*！且有与前一定理完全相同的不等式成立！Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1613分析例分析例2 2四种迭代格式的收敛性，四种迭

12、代格式的收敛性，一般迭代法只有理论上的意义，因为构造保证收敛保证收敛的迭代函数比较困难。注注:方法1的收敛性分析方法2的收敛性分析方法3的收敛性分析方法4的收敛性分析四种迭代格式的计算结果见本课件P9!取定初值x0=1.5，=1e-4,Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1614（四）（四）收敛阶（速度）的讨论收敛阶（速度）的讨论阶收敛。是则称若pcxxxxnnpnnx),0(*lim1定义定义:p=1 线性收敛；p=2 平方收敛；2p1 超线性收敛；注：注：1、p=1时，c0

13、时，收敛于 ；2）当x00时，收敛于 ；CC（*）;)(2121CxxCxkkk )(2121CxxCxkkk1121211kkkqxCq001;xCqxC1)得证!2）001=;xCpqxC事实上事实上，对（*）式进行配方可得下面证明1），;)()(1200211kCxCxCxCxCxCxkkkk Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1627（2）对于给定的正数C，应用牛顿法求解方程 。01 Cx可得),2,1,0()2(1nCxxxkkk可以证明上述迭代算法对任意初值 都收

14、敛于 ！Cx200C121)1(1)2(1CxCCCxxCxkkkk事实上事实上，21)1(1kkCxCx从而20(1)kCx)(0)1(,11 2000kCxCxCxk从而时，当)(C1 kxk即#Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1628牛顿迭代法的几点说明牛顿迭代法的几点说明牛顿迭代法算法简单，且局部收敛，但初值x0的选择困难！(1)(2)牛顿迭代每步都要计算导数 ，增加了计算量！)(nxf(3)定理表明牛顿迭代求单根有效且平方收敛（能求重根吗？）。(一)一般来说采用试

15、探法，可以结合二分法二分法或通过做出函数图形函数图形来帮助选择初值！关于初值(二)导数的计算(1)利用牛顿迭代法先计算几步，比如计算到了第k步，得到近似值xk，接下来用 来代替导数，该算法通常是线性收敛线性收敛的！)(1kxfc Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1629(2)一个实用的方法是用差分代替微分，即)()()(111nnnnnnnxfxfxfxxxx此迭代法称为割线法割线法！它是超线性收敛超线性收敛的！(三)关于重根的问题),(*)()(*)(1)(*)()(),

16、0*)()(*)()(1)(*11xhxxmxgxxmxgxxmxfxgxgxxxfmmxfxmmm，此时重根（的是设),()/()()()()(xhxgx-xmxxfxfxx*1)(),()()()(其中，0*1xhxgxxmxgxh Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-163011)(故 ,1)(mxmx1*1*可见，当x*为重根时，牛顿迭代线性收敛，且随着m的增加，收敛性变差！计算重根的改进算法计算重根的改进算法(1)210()(1,nxfxfmxxnnnn）至少平方收敛

17、。(证明略!)设重数m已知，应用牛顿迭代法得1()()mu xf x令 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1631返回主目录(2)重数不知道时，一个实用的方法是，令(),()fxu xfx）则()0()0f xu x ，*()xu x且是的单根。直接对 应用牛顿迭代法求解:()u x12()()()(0,1,2,)()()()()nnnnnnnnnnu xf x f xxxxnu xf xf x fx至少平方收敛！(3)通过史蒂芬森（Steffensen）迭代算法进行加速！N

18、umerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1632解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法11221212(,)0(,)0 (,)0nnnnf x xxfx xxfx xx：非线性方程组问问题题12()0,(,)nTnnF xxDRFfffFDR 简写为：，其中 ：。Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1633(0)1(1)()()()*()()()0 1

19、2()*kkkkxN x xxF xF x k,F x：当非奇异时，至少二阶收敛。牛牛顿顿迭迭代代法法111122221212()nnnnnnfffxxxfffxxxFxfffxxx其中，Jacobi矩阵 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1634()()()(1)()()(1)()()()(2)()kkkkkkF xF xxF xxxxF x 牛顿迭代法每步除 计算外，还需解方程组 显然工作量很大！可能奇异或病态，从而导致解方程组失败 或产生数值不稳定。注意事项：注意事项：

20、为了解决上述问题，提出拟牛顿法。Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1635(0)0()(1)()1 ().(),0,1,2,.kkkkkkkAF xAxF xxxxkAAA 形如：拟拟牛牛顿顿法法0(1)()1()0 10,()kkkkkAAAxxA F x例如：、即形成 ()()()()()(-1)()1111()()(-1)(1)()1()()(,)(,)()ikkjkkkkkkijjjijjjikkkjjjkkkkfAxfxxxfxxxfxxxxxA F x2、差商代替

21、导数形成 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1636kA总之，使的的不同构造，形成不同的。下面给出一种很实用的拟牛顿方法拟拟牛牛顿顿法法(k+1)(k+1)k+1k+1A A F(x)F(x)Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1637 Broyden Broyden秩秩1 1方法方法(1)()-1()(0)01()(1)(1)()(1)2(1)()()(11

22、1)-()(),()()()(-)()(-)(kkkkkkkkkkkkkkkkkkxxA F xAFxAAAF xF xFxAxxOxxAxxF 根据令满足方程：(1)()()kkxF x Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1638(1)()(1)()(1)()()(1)()()()()()()()()()()()2)()2(1)()()2()2,()()1()1()()()()()kkkkkkkkkkkTkkkkkkkkkkkkkTkkkkkksxxyF xF xvsA v

23、uvvyuyA vvAyA vvAxxF xF xv 令 由（）()()1()kkTkkAAuv设 为秩 矩阵，即。Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1639综合上述，得到综合上述，得到Broyden秩秩1方法：方法：(1)()()1(0)00(1)()(1)()T1T ()(),()(),1 )0(kkkkkkkkkkkkkTkkkxxB F xBF xBIsxxyF xF xBBsB y s ByssBBy可以证明，当时具有超线性其中，或收敛性。11111()1TTTA

24、uv AAuvAv A u又 可可以以证证明明 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-164011(TkkkkkkkkFxAAu vAuvA 有时）是对称的，由 看出：当对称时，只要与成比例，就可保证对称。)(1)1()1kkBroydenvF xBroyden（在秩 方法中，取即得到对称秩 方法：Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1641kTkkkTkkkkk

25、kkkkkkkkkkkkkyyBsyBsyBsBBxFxFyxxsIxFBxFBxx)()(,)()(,)()(1)()1()()1(1)0(0)()()1(或其中返回主目录 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1642例例2的实根。，在用一般迭代法计算21 104)(23xxxf321()410;xxxxx方法：返回2()1381 2()1,xxxx在，内不满足局部收敛性定理!故可能发散。可以验证，Numerical Analysis J.G.Liu School of Ma

26、th.&Phys.North China Elec.P.U.2022-12-1643例例2的实根。，在用一般迭代法计算21 104)(23xxxf23312 410()10;2xxxxx方法：返回 在1,1.5内是自映射，并且1606.0)5.1()(x)(x满足大范围收敛定理！收敛。可以验证，Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1644例例2的实根。，在用一般迭代法计算21 104)(23xxxf3221034104;10 ()4xxxxxxxxx 方法：返回*1.3652()1,xx找不到的邻域使因此方法3不满足局部收敛性定理！可能发散。可以验证，Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1645例例2的实根。，在用一般迭代法计算21 104)(23xxxf24(4)10()10/(4);xxxxx方法：返回()12()0.15,xx因此在，内为自映射，且即满足大范围收敛性定理！收敛。可以验证，(1)1.581,(2)1.291