—非线性方程求根.pptx

会计学1非线性方程非线性方程(fngchng)求根求根第一页，共62页。本章本章(bn zhn)内容内容二分法迭代法牛顿迭代法与弦割法非线性方程组牛顿法求根迭代法的收敛阶和Aitken加速(ji s)方法（*）第1页/共62页第二页，共62页。2.1 引言引言(ynyn)n n在科学研究和工程问题中，常常会遇到非线性方程在科学研究和工程问题中，常常会遇到非线性方程(fngchng)(fngchng)或非线性方程或非线性方程(fngchng)(fngchng)组的问题。例组的问题。例如解如解4 4次代数方程次代数方程(fngchng)(fngchng)n n或超越方程或超越方程(fngchng)(fngchng)n n一般的，我们记非线性方程一般的，我们记非线性方程(fngchng)(fngchng)为为第2页/共62页第三页，共62页。建筑机械中常使用(shyng)阶梯柱，需要其整体稳定性，临界力Pcr由下式给出等截面(jimin)均质悬臂梁的固有频率由下式给出非线性方程(fngchng)求根第3页/共62页第四页，共62页。三根刚度系数相同的软弹簧组成图示系统，承受载荷Px,Py，求节点O之位移？软弹簧(tnhung)变形大，O点位移大。超静定，非线性 未知量:ux，uy第4页/共62页第五页，共62页。三弹簧(tnhung)的伸长量分别为变形(bin xng)后，各弹簧与水平线的夹角分别为节点(ji din)平衡方程非线性方程组第5页/共62页第六页，共62页。三弹簧(tnhung)换成三根铰接杆，杆的拉伸刚度很大。节点O的位移是“无穷小量”，可以线性化变形(bin xng)后，各杆与水平线的夹角不变节点(ji din)平衡方程线性方程组第6页/共62页第七页，共62页。求解f(x)=0，解x*称为方程的根，即f(x)的零点;f(x)为n次多项式就是n 次代数方程;(n=5，不能用解析式表示解)f (x)为超越(choyu)函数时，就是超越(choyu)方程。若f(x)=(x-x*)m g(x)，g(x)0，m为正整数，则称 x*为f(x)=0的m重根，或为f(x)的m重零点。m=1时，称x*为f(x)=0的单根。第7页/共62页第八页，共62页。线性的（一次解）线性的（一次解）单个方程单个方程 多项式（多项式（n n个解）个解）代数方程代数方程 非线性非线性 超越的（解的数目不定）超越的（解的数目不定）线性（一组解）线性（一组解）方程组方程组 非线性（多组解）非线性（多组解）f(x)=0 f(x)=0的根，当的根，当 f(x)f(x)复杂时，很难求得。复杂时，很难求得。实际应用中只需求得满足一定精度的近似根即可实际应用中只需求得满足一定精度的近似根即可 （找近似有效简单（找近似有效简单(ji(ji ndn)ndn)方法）方法）。第8页/共62页第九页，共62页。n n方程求根特点方程求根特点n n1.1.根的存在性根的存在性n n方程有没有根，有几个根？方程有没有根，有几个根？n n定理定理1 1（代数基本定理）：在复数范围内，（代数基本定理）：在复数范围内，n n次代数方程至次代数方程至少有一个少有一个(y(y )根。根。n n f(x)=anxn+an-1xn-1+a1x+a0=0 f(x)=anxn+an-1xn-1+a1x+a0=0n n 其中：其中：nn正整数，正整数，xx复变量，复变量，n n a0an a0an为实、复常数。为实、复常数。n n定理定理2 2：n n 次代数方程有次代数方程有 n n 个根。个根。n n 2.2.根的分布（有根区间）根的分布（有根区间）n n求根的隔离区间，定一个求根的隔离区间，定一个(y(y )a,b)a,b，使，使a,ba,b内有且只内有且只有一个有一个(y(y )x*)x*使使f(x*)=0f(x*)=0第9页/共62页第十页，共62页。定理定理3 3：设函数：设函数f(x)f(x)在在a,ba,b内连续，严格单调，且内连续，严格单调，且f(a)*f(b)0f(a)*f(b)0，则在，则在a,ba,b内内f(x)=0f(x)=0有且仅有一个实根。有且仅有一个实根。通常有两种做法来确定隔离区间通常有两种做法来确定隔离区间(q jin)(q jin)：（1 1）作）作y=f(x)y=f(x)的草图，看的草图，看f(x)f(x)在在x x轴的交点位置来定区间轴的交点位置来定区间(q jin)a,b(q jin)a,b（2 2）逐步搜索，在连续区间）逐步搜索，在连续区间(q jin)a,b(q jin)a,b内，选取适当的内，选取适当的x1x1，x2x2(a,b)(a,b)，若，若f(x1)*f(x2)0f(x1)*f(x2)0f(x)0，即，即f(x)f(x)为一单调递增为一单调递增函数。函数。那么那么f(x)=0f(x)=0在（在（-，+）内最多只有一个）内最多只有一个实根。实根。又又 f(0)=03-3*02+4*0-3=-30 f(0)=03-3*02+4*0-3=-30 f(1)=13-3*12+4*1-3=-10 f(1)=13-3*12+4*1-3=-10 f(2)=03-3*22+4*2-3=10 f(0)*f(2)0 f(0)*f(2)0，故在故在0 0，2 2内有唯一实根。内有唯一实根。第12页/共62页第十三页，共62页。2.2 二分法二分法0 xyX*x0aby=f(x)a1b10 xyX*x0aby=f(x)a1b1第13页/共62页第十四页，共62页。0 xyX*x0aby=f(x)a1b10 xyX*x0aby=f(x)a1b1第14页/共62页第十五页，共62页。第15页/共62页第十六页，共62页。5.2 二分法二分法第16页/共62页第十七页，共62页。5.2 二分法二分法第17页/共62页第十八页，共62页。5.2 二分法二分法第18页/共62页第十九页，共62页。n n二分法优缺点二分法优缺点n n优点：计算简单，方法可靠，只要求优点：计算简单，方法可靠，只要求f(x)f(x)连续连续(linx)(linx)，在两个点上异号。，在两个点上异号。n n缺点：不能求偶数重根缺点：不能求偶数重根,也不能求复根也不能求复根,收敛速度不收敛速度不算太快算太快(与以与以1/21/2为比值的等比级数相同为比值的等比级数相同)。n n因此，一般在求方程近似根时，不单独使用，常用来因此，一般在求方程近似根时，不单独使用，常用来为其它方法提供好的初值。为其它方法提供好的初值。n n对于方程求根，最常用方法是迭代法。对于方程求根，最常用方法是迭代法。第19页/共62页第二十页，共62页。f(x)=0 x=g(x)等价变换等价变换f(x)的根的根g(x)的不动点的不动点2.3 迭代法迭代法n n迭代法迭代法 /*/*Fixed-Point Iteration*/Fixed-Point Iteration*/第20页/共62页第二十一页，共62页。n n一.迭代格式(g shi)的构造第21页/共62页第二十二页，共62页。5.3 迭代法迭代法n n二二.迭代迭代(di di)(di di)过程的几何表示过程的几何表示O x*x2 x1 x0 xyy=xy=g(x)P0P1P2P*Q1Q2第22页/共62页第二十三页，共62页。n n例例1 1：用迭代法求方程：用迭代法求方程f(x)=x2-2x-3=0f(x)=x2-2x-3=0的根（的根（x1=3x1=3，x2=-1x2=-1）n n 解：解：(1)(1)方程改写方程改写(g(g ixi)ixi)成成 x=(2x+3)1/2 x=(2x+3)1/2 n n 建立迭代公式建立迭代公式 xk+1=(2xk+3)1/2 (k=0,1,2)xk+1=(2xk+3)1/2 (k=0,1,2)，n n 取取x0=4x0=4，x1=3.316x1=3.316，x2=3.104x2=3.104，x3=3.034x3=3.034，n n x4=3.011 x4=3.011，x5=3.004x5=3.004n n 当当k k，xk xk 3 3，收敛；，收敛；n n n n (2)(2)方程改写方程改写(g(g ixi)ixi)成成 x=1/2*(x2-3)x=1/2*(x2-3)n n 建立迭代公式建立迭代公式 xk=1/2*(xk 2-3)(k=0,1,2)xk=1/2*(xk 2-3)(k=0,1,2)，n n 取取x0=4x0=4，x1=6.5 x1=6.5，x2=19.625 x2=19.625，x3=191.0 x3=191.0n n 当当k k，xk xk ，发散。，发散。第23页/共62页第二十四页，共62页。n n例例2 2：对对f(x)=x3+4x2-10=0f(x)=x3+4x2-10=0（此方程在（此方程在1,21,2中有唯一根）用不同中有唯一根）用不同(b(b tntn)方法化成等价方程。方法化成等价方程。n n 取初始取初始(ch sh)近似值近似值x0=1.5，迭代结果表，迭代结果表明明迭代过程迭代过程(a)、(b)不适定，不适定，(c)、(d)、(e)都收敛，但收敛速度相差很大。都收敛，但收敛速度相差很大。解：可化成很多不同解：可化成很多不同(b tn)等价方程，例如等价方程，例如第24页/共62页第二十五页，共62页。n n三三.迭代法的收敛性迭代法的收敛性n n g(x)g(x)如何构造如何构造n n 基本问题基本问题(wnt)xk(wnt)xk的收敛性的收敛性(收敛否？如何加速收敛否？如何加速?)?)n n 误差估计误差估计n n 从几何上考察迭代法的收敛性，见下页从几何上考察迭代法的收敛性，见下页n n 第25页/共62页第二十六页，共62页。5.3 迭代法迭代法0g(x*)1-1g(x*)1g(x*)-1xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1第26页/共62页第二十七页，共62页。n n n n具体的迭代具体的迭代(di di)(di di)收敛定理。收敛定理。第27页/共62页第二十八页，共62页。n n四四.整体整体(zhngt(zhngt)收敛性收敛性第28页/共62页第二十九页，共62页。5.3 迭代法迭代法证明：证明：依此类推依此类推(y c li tu)第29页/共62页第三十页，共62页。5.3 迭代法迭代法可用可用 来控制收敛精度；来控制收敛精度；即判断迭代是否中即判断迭代是否中止止L越小收敛越快越小收敛越快见上页见上页第30页/共62页第三十一页，共62页。n n五五.局部收敛性局部收敛性第31页/共62页第三十二页，共62页。5.3 迭代法迭代法证明证明(zhngmng)：第32页/共62页第三十三页，共62页。第33页/共62页第三十四页，共62页。n n牛顿迭代法（Newton-Raphson Method）n n 一般迭代法的特例，且迭代函数有固定(gdng)的形式。n n一.迭代格式的构造n n1.原理 n n构造 g(x)的一条重要途径：用近似方程代替原方程求根。n n牛顿法是将非线形方程线性化。2.4 牛顿牛顿(ni dn)迭代法迭代法第34页/共62页第三十五页，共62页。Taylor展开展开(zhn ki)线性化（重要思线性化（重要思想）想）n n2.方法(fngf)第35页/共62页第三十六页，共62页。5.4 牛顿牛顿(ni dn)雷扶生法雷扶生法n二二.Newton迭代法的几何迭代法的几何(j h)意义意义实实际际上上牛牛顿顿迭迭代代公公式式是是曲曲线线在在xk点点上上的的切切线线 与与 x轴轴 交交 点点(jiodin)的的横横坐坐标标，即即用用切切线线与与 x轴轴交交点点(jiodin)的的坐坐标标近近似似代代替替曲曲线线与与 x轴轴的的交交点点(jiodin)坐坐标标，故故也也称称切切线线法法。第36页/共62页第三十七页，共62页。产生产生(chnshng)的序列单调有界的序列单调有界,保证收敛保证收敛.1.收敛收敛(shulin)的充分条件的充分条件设设 f C2a,b，若，若(1)f(a)f(b)0；则牛顿法产生的序列则牛顿法产生的序列 xk 收敛收敛(shulin)到到f(x)在在 a,b 的唯一根。的唯一根。有根有根根唯一根唯一(wi y)n n三.Newton迭代法收敛定理第37页/共62页第三十八页，共62页。5.4 牛顿牛顿(ni dn)雷扶生法雷扶生法第38页/共62页第三十九页，共62页。第39页/共62页第四十页，共62页。5.4 牛顿牛顿(ni dn)雷扶生法雷扶生法由由 Taylor 展开展开(zhn ki)：只要只要 f(x*)0，则令，则令 可得结论。可得结论。在单根在单根/*simple root*/附近附近(fjn)收敛快收敛快 第40页/共62页第四十一页，共62页。5.4 牛顿牛顿(ni dn)雷扶生法雷扶生法3.x03.x0的选取对牛顿法收敛性的影响的选取对牛顿法收敛性的影响 即：牛顿法的收敛性依赖于即：牛顿法的收敛性依赖于x0 x0的选取。的选取。取取 x0 x0 使使 f(x0)f”(x0)0 f(x0)f”(x0)0，则收敛速度增大。常，则收敛速度增大。常 用二分法获取初值用二分法获取初值 x0 x0，再进行迭代求解。，再进行迭代求解。迭代过程中若迭代过程中若f(x0)0f(x0)0或迭代次数超过某个或迭代次数超过某个(m(m u u )上上 界界M,M,仍达不到要求的精度仍达不到要求的精度,则迭代计算失败。则迭代计算失败。x*x0 x0 x0第41页/共62页第四十二页，共62页。例例1：第42页/共62页第四十三页，共62页。第43页/共62页第四十四页，共62页。4 弦割法弦割法n n（一）（一）.引入意义引入意义n n牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数 ,当当 比较复杂时比较复杂时,不仅每次计算不仅每次计算 带来很多不便，而且还可能十带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算节介绍的弦截法便是一种不必进行导数运算(yn sun)(yn sun)的求根方法。弦截的求根方法。弦截法在迭代过程中不仅用到前一步法在迭代过程中不仅用到前一步 处的函数值，而且还使用处的函数值，而且还使用 处的函处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。数值来构造迭代函数，这样做能提高迭代的收敛速度。第44页/共62页第四十五页，共62页。n n（二）（二）.弦割法基本弦割法基本(jbn)(jbn)思想思想第45页/共62页第四十六页，共62页。n n三三.弦割法几何弦割法几何(j(j h)h)意义意义第46页/共62页第四十七页，共62页。n n例：用弦割法解方程的根达到达到(d do)精度精度10-8 迭代迭代(di di)5次次x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553第47页/共62页第四十八页，共62页。例：例：用正割法求方程用正割法求方程 在在 初始初始 值邻近的一个值邻近的一个(y)根。要求根。要求解：取解：取 ,令令 利用正割迭代公式利用正割迭代公式 计算过程略，计算过程略，取近似根取近似根 则可满足精度要求。则可满足精度要求。第48页/共62页第四十九页，共62页。n6 解非线性方程组的迭代法第49页/共62页第五十页，共62页。在迭代点x(k)，将各函数(hnsh)作一阶Taylor展开另展开式等于零，得到(d do)下一个迭代点x(k+1)第50页/共62页第五十一页，共62页。第51页/共62页第五十二页，共62页。第52页/共62页第五十三页，共62页。kx(k)0123(1.5,1.0)T(1.5,0.75)T(1.488095,0.755952)T(1.488034,0.755983)T第53页/共62页第五十四页，共62页。5.6 迭代法的收敛阶和迭代法的收敛阶和Aitken加加速速(ji s)方法方法n n一.迭代(di di)过程的收敛速度n n二.常见迭代(di di)过程的收敛阶n n三.埃特金(Aitken)加速法n n四.斯蒂芬森(Steffensen)法第54页/共62页第五十五页，共62页。6 迭代法的收敛阶和迭代法的收敛阶和Aitken加速加速(ji s)方法方法n n一一.迭代过程的收敛迭代过程的收敛(shuli(shuli n)n)速度速度n n 一种迭代法要具有实用价值，不但要肯定它是收敛一种迭代法要具有实用价值，不但要肯定它是收敛(shuli(shuli n)n)的，还要求它收敛的，还要求它收敛(shuli(shuli n)n)的比较快。的比较快。所谓迭代过程的收敛所谓迭代过程的收敛(shuli(shuli n)n)速度，是指在接近收速度，是指在接近收敛敛(shuli(shuli n)n)时迭代误差的下降速度，具体地说，如时迭代误差的下降速度，具体地说，如果迭代误差果迭代误差 n n 当当 时成立时成立n n 则称迭代过程是则称迭代过程是 p p 阶收敛阶收敛(shuli(shuli n)n)的。的。第55页/共62页第五十六页，共62页。n n特别地，特别地，n np=1(p=1(且且 0 C 1)0 C 1 p 1 时称超线性收敛，时称超线性收敛，n n其中其中 p=2 p=2 时称二次收敛时称二次收敛n n （或称为平方收敛）。（或称为平方收敛）。n n p p 越大，越大，xk xk 收敛于收敛于 x*x*的速度就越快。的速度就越快。n n p p 值的大小是衡量一个迭代值的大小是衡量一个迭代(di di)(di di)过程优劣的标志之过程优劣的标志之一。一。第56页/共62页第五十七页，共62页。n n二二.常见常见(chn(chn jin)jin)迭代过程的收敛阶迭代过程的收敛阶n n 一般迭代法：一般迭代法：p p1 1，线性收敛，线性收敛n n牛顿法：牛顿法：p p2 2，二阶收敛（当，二阶收敛（当x*x*为二重根时，线性收为二重根时，线性收敛）敛）n n弦割法：弦割法：p=1.618p=1.618，超线性收敛，超线性收敛n n对收敛较慢数列对收敛较慢数列 xk xk，一个补救的方法是采用加速公，一个补救的方法是采用加速公式。式。第57页/共62页第五十八页，共62页。n n三三.埃特金埃特金(Aitken)(Aitken)加速加速(ji s)(ji s)法法第58页/共62页第五十九页，共62页。5.6 迭代法的收敛阶和迭代法的收敛阶和Aitken加加速速(ji s)方法方法xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)第59页/共62页第六十页，共62页。第60页/共62页第六十一页，共62页。例例 用埃特金方法用埃特金方法(fngf)求方程求方程 在在初值初值 附近的一个根附近的一个根,精度要求精度要求 ，取迭代取迭代(di di)格式格式解解 埃特金方法迭代埃特金方法迭代(di di)格式格式为为只迭代二次就得到满足精度要求的解。只迭代二次就得到满足精度要求的解。第61页/共62页第六十二页，共62页。