数值分析课件chap7非线性方程组的求解

1、非线性方程求根非线性方程求根q ( )0f x 例如：非线性有限元问题、非线性断裂问题、及其它例如：非线性有限元问题、非线性断裂问题、及其它非线性力学问题、电路问题、电力系统计算、医学、非线性力学问题、电路问题、电力系统计算、医学、生命学、天气预报、非线性规划、经济问题等生命学、天气预报、非线性规划、经济问题等。 描述工程和科学技术实际问题的数学模型，通常都难以描述工程和科学技术实际问题的数学模型，通常都难以 获得根的简单易用的显式表达式，因此，要研究求近似获得根的简单易用的显式表达式，因此，要研究求近似 根的方法，并讨论这些方法的收敛性和收敛速度根的方法，并讨论这些方法的收敛性和收敛速度预备

2、知识预备知识q 满足函数方程 f(x)=0 的x称为方程(1)的根，或称为函数f(x)的零点。如果函数(x)可分解为 (x)=(xs)mg(x)且g(s )0,则称s是(x)的m重零点或(x)=0的m重根。当m=1时，称s是(x)的单根或单零点。q 定理定理 假设函数假设函数y=f(x)y=f(x)在在x=sx=s的某一邻域内充分可的某一邻域内充分可 微，则微，则s s是方程是方程f(x )=0f(x )=0的的m m重根的充分必要条件是重根的充分必要条件是0)(, 0)()()()()1(sfsfsfsfmm求解非线性方程的根的问题可分为下面几个方面求解非线性方程的根的问题可分为下面几个方面

3、：q l 根的存在性根的存在性l 根的隔离根的隔离l 根的精确化根的精确化q 非线性方程根的存在性非常复杂。非线性方程根的存在性非常复杂。l 对于代数方程即多项式方程，其根的对于代数方程即多项式方程，其根的个数与代数方程个数与代数方程的次数相同的次数相同。而且理论上已证明，对于次数。而且理论上已证明，对于次数n=4n=4的多项的多项式方程式方程, ,它的根可以用公式表示它的根可以用公式表示, ,而而次数大于次数大于5 5的多项式方的多项式方程程, ,它的根一般不能用解析表达式表达。它的根一般不能用解析表达式表达。示示. .l 对于超越方程或其他非线性方程，可能没有零点，也对于超越方程或其他非线

4、性方程，可能没有零点，也可能有一个或若干个零点，甚至无穷多个零点。可能有一个或若干个零点，甚至无穷多个零点。根的存在性定理根的存在性定理q 定理定理1 1. .( (根的存在定理根的存在定理) ) 假设函数假设函数y=f(x)y=f(x) C C a,ba,b , ,且且f(a)f(b)0, f(a)f(b)0, 则至则至 少存在一点少存在一点x x (a,b)(a,b)使得使得f(x )=0. f(x )=0. ( (并称区间并称区间( (a,b)a,b)为有根区间为有根区间).). q 定理定理2 2. .（根的唯一性）（根的唯一性） 假设函数假设函数y=f(x)y=f(x)在在 a,ba

5、,b 上单调连续上单调连续, ,且且 f(a)f(b)0,f(a)f(b)0, 则恰好只存在一点则恰好只存在一点x x (a,b)(a,b)使得使得 f(x )=0f(x )=0 根的隔离根的隔离求根的隔离区间的两种方法求根的隔离区间的两种方法q 画图法画图法n 画出画出y y = = f f ( (x x) )的略图，从而看出曲线与的略图，从而看出曲线与x x轴交轴交 点的大致位置。点的大致位置。n 也可将也可将f f ( (x x) = 0) = 0分解为分解为 1 1( (x x)= )= 2 2( (x x) )的形式，的形式， 1 1( (x x) )与与 2 2( (x x) )两

6、曲线交点的横坐标所在的子两曲线交点的横坐标所在的子 区间即为含根区间。区间即为含根区间。 例如例如x xlglgx x 1 = 0 1 = 0 可以改写为可以改写为lglgx x=1/=1/x x 画出对数曲线画出对数曲线y y=lg=lgx x, ,与双曲线与双曲线y y= 1/= 1/x x, ,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内xy1023yxxylog画图法画图法逐步搜索逐步搜索法法n 对于给定的对于给定的f f ( (x x) )，设有根区间为设有根区间为 A A, ,B B ，从从x x0 0= =A A 出发，以步长出发，以步长h h=(=(B B

7、- -A A)/)/n n( (n n是正整数是正整数) )，在，在 A A, ,B B 内取定节点：内取定节点：x xi i= =x x0 0ihih ( (i i=0=0，1 1，2 2，n n) )， 从左至右检查从左至右检查f f ( (x xi i) )的符号，如发现的符号，如发现x xi i与端点与端点x x0 0 的函数值异号，则得到一个缩小的有根子区间的函数值异号，则得到一个缩小的有根子区间 x xi i-1-1, ,x xi i。n 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h hn 要选择适当要选择适当h h ，使之既能把根隔离开来，工

8、作量又使之既能把根隔离开来，工作量又 不太大。不太大。q 逐步搜索法逐步搜索法二分法二分法 Bisectionq 在方程求根的方法中，最直观、最简单的方法就在方程求根的方法中，最直观、最简单的方法就 是二分法。是二分法。q 给定方程给定方程f(x)=0,f(x)=0,设设f(x)f(x)在区间在区间 a,ba,b连续连续, ,且且f(a)f(b)0,f(a)f(b)0, 则方程则方程f(x)f(x)在在( (a,b)a,b)内至少有一根内至少有一根, ,为便于讨论为便于讨论, ,不妨设方不妨设方 程程f(x)=0f(x)=0在在( (a,b)a,b)内只有一个内只有一个( (重根视为一个重根视

9、为一个) )实根。实根。q 二分法的基本思想二分法的基本思想 二分法详细步骤二分法详细步骤l l 0011 (),().2001.记有根区间a ,b =a,b,取 中点 并计算abxf x 111101011110111101110():()0,() ()0,;,.2. 判断的值若则 为根；若取=即否则取=即f xf xxf xf aaa b xa baxax b ba bx b k-1k-1kkk-1k-1kkkkk-1k-1k-1,2()0,()(a)0,abkkkkkk3. 继续运算， 由区间,构造区间,并得到：若则为所求的根;若则取a ,b =,;否则, 可取a ,b =,.kabab

10、abxxf xxf xfxx l 11*(a) () ()01(b) ()2(c) .,.;,()0,(,),lim,limkkkkkkkkkkkkkkf af bbabaababxf xxabaxb 0 00 01 11 1k kk k0 01 1k k0 01 1k k这这样样就就得得到到一一系系列列闭闭区区间间： a a , , b b ， a a , , b b ，. . . . . . a a , , b b , , . . . . . . , , k k= =0 0, , 1 1, , 2 2, , . . . . . . . . , ,并并满满足足：a aa aa ab bb b

11、b b即即满满足足并并且且*,limkkkxxx 二分法终止的条件二分法终止的条件)(kxfq 如下条件终止，可否如下条件终止，可否 ？这不能保证精确值的精度！这不能保证精确值的精度！x x*q 有如下估计有如下估计q 因此终止的条件为因此终止的条件为q 二分法终止的条件二分法终止的条件11*)(21kkkkkababxx1kkkkxxorab对于给定的精度对于给定的精度 , ,可估计二分法所需的步数可估计二分法所需的步数 k k ：)(log22abkabk二分法的优缺点q 优点优点l 计算简单，方法可靠，并保证收敛计算简单，方法可靠，并保证收敛 l 对函数对函数 要求不高，只要连续即可要求

12、不高，只要连续即可。q 缺点缺点l 无法求复根和偶重根无法求复根和偶重根l 收敛慢收敛慢 l 调用一次求解一个调用一次求解一个 a, ba, b间的多个根无法求得间的多个根无法求得 一般求方程的近似根，不大单独使用，常用一般求方程的近似根，不大单独使用，常用来为其它方法求方程近似根提供好的初值。方程来为其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法求根最常用的方法是迭代法。function y=erfen(fun,a,b,esp)Matlab programif feval(fun, a)*feval(fun, b)esp if feval(fun,a)*feval(fun,c

13、)0 b = c ; c = ( a+b) / 2 ; elseif feval(fun,c)*feval(fun,b)0 a = c ; c = ( a+b) / 2 ; else y = c ; end n= n+1 ; endy = c ;elseif feval(fun,a) = 0 y = a ; elseif feval(fun,b) = 0 y = b ; end01)(3xxxf3242.13203.063203.13281.153281.13438.143438.13125.133125.1375.12375.125.1125.15.10.10)(17符号表kkkkxfxba

14、k不动点迭代法q 迭代法的迭代法的基本思想基本思想是一种逐次逼近的方法，首先是一种逐次逼近的方法，首先 给定一个粗糙的初值，然后用同一个迭代公式，给定一个粗糙的初值，然后用同一个迭代公式， 反复校正这个初值，直到满足预先给出的精度要求。反复校正这个初值，直到满足预先给出的精度要求。q 迭代法的基本步骤迭代法的基本步骤f (x) = 0等价变换等价变换f (x) 的根的根x= (x) (x)的不动点的不动点从一个初值从一个初值 x0 出发出发，计算计算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若若 收敛，即存在收敛，即存在 x x* * 使得使得 ，且且 连续，

15、则由连续，则由 可可知知 x* = (x* )，即即x x* *是是 的不动点，也就是的不动点，也就是f f 的根。的根。 0kkx*limxxkk kkkkxgx limlim1)., 1 , 0()(1kxxkk不动点迭代法定义定义：迭代公式迭代公式 x xk k+1+1= = ( (x xk k) ) ( (k k= 0,1, ) = 0,1, ) 被被称为求解方程称为求解方程 f f( (x x)=0 )=0 的的不动点迭代法不动点迭代法，其中，其中( (x x) )称为称为迭代函数迭代函数。q q 迭代法的几何含义迭代法的几何含义y) :)(xyxyxx交点即真根。xyy = xsy

16、=g(x)x0p0 x1p1需要讨论的问题 n 首先期望每个首先期望每个x xk k都在都在 ( (x x) )的定义域上的定义域上, ,保持有界而保持有界而 且收敛到精确解且收敛到精确解; ;n 如何选取适合的迭代函数如何选取适合的迭代函数 ( (x x) ;) ;n 迭代函数迭代函数 ( (x x) )迭代满足什么条件迭代满足什么条件, ,迭代序列收敛到迭代序列收敛到 精确解精确解, ,收敛速度如何收敛速度如何; ; H 。5 . 101)(03附近的根在求方程xxxxfl 设将原方程改写成下列形式设将原方程改写成下列形式 . 13xx据此建立迭代公式据此建立迭代公式 ).,2, 1 ,0

17、(131kxxkkl 但但若采用方程另一种等价形式若采用方程另一种等价形式13 xx，131kkxx建立迭代公式建立迭代公式 32494. 1432472. 1832588. 1332472. 1733086. 1232473. 1635721. 1132476. 155 . 10kkxkxk第二种方法第二种方法仍取迭代初值仍取迭代初值 ，则有，则有 5 .10 x.39.12,375.221xx结果会越来越大，不可能趋于某个极限结果会越来越大，不可能趋于某个极限. . 迭代法的收敛条件迭代法的收敛条件 q 定理定理*10|1kkLxxxxL且满足上连续在设迭代函数,)(bax;)(,)1(b

18、xabax时当有且满足存在一正数,10,)2(baxLL1212()()xxL xx1 .( ) , *2 .oxa bx则 函数在上存在唯一的不动点此迭代法一定收敛，且有如下估计式*11|1kkkxxxxL 注注 q 条件条件(2)(2)可用更强更便于应用的条件代替可用更强更便于应用的条件代替: q 由误差估计可以得到迭代终止的条件由误差估计可以得到迭代终止的条件 , 1)(Lxkkxx1q 由误差估计可以知道由误差估计可以知道L越小，收敛越快越小，收敛越快以及以及迭代迭代最最 少次数少次数 LxxLnln)1 (ln01可得到： 局部收敛性局部收敛性 q 前述定理条件为前述定理条件为充分条

19、件充分条件，非必要条件。在实际，非必要条件。在实际 应用当应用当中中 条件并不易检验条件并不易检验。 q 定义定义 （局部收敛性）（局部收敛性）设设 有不动点有不动点 ，)( x*x如果存在如果存在 的某个邻域的某个邻域*x,*: xxR对任意对任意 ，Rx0迭代产生的序列迭代产生的序列,Rxk且收敛到且收敛到 ，*x则称迭代法则称迭代法局部收敛局部收敛. .q 定理定理 设设s s为为的不动点的不动点, , 在在s s的某个邻域内连续的某个邻域内连续, , 且且| | 1, |= 1.0e 6 ) &( n=1000 ) x = x1 ; x1=g(x); n = n+1 ;endx

20、1nmatlab program 收敛阶(描述收敛速度) q 设迭代过程设迭代过程 收敛于方程收敛于方程 )(1kkxx)( xx的根的根 ，*x如果迭代误差如果迭代误差 当当 时成立下列时成立下列*xxekkk渐近关系式渐近关系式),0(1CCeepkk常数 若若 p p = 1 = 1 , , 称称 x xk k 为为线性收敛线性收敛, , 这时这时 0 0 1, 1, 称称 x xk k 为为超线性收敛超线性收敛; ; p p=2, =2, 称其为称其为平方收敛平方收敛. .收敛阶定理 q 数数p p的大小反映了迭代法的收敛速度的快慢，的大小反映了迭代法的收敛速度的快慢，P P越大，收越

21、大，收 敛越快敛越快，所以说收敛阶是对迭代法收敛速度的一种度量。，所以说收敛阶是对迭代法收敛速度的一种度量。 q （收敛阶定理）（收敛阶定理） 对于迭代过程对于迭代过程 ，如果，如果 在所求根在所求根 的邻近连续，并且的邻近连续，并且: : 则该迭代过程在点则该迭代过程在点 邻近是邻近是P P阶收敛的阶收敛的。)(1kkxx)()(xp*(1)*()()()0pxxx0)(*)(xp*x*x 上述定理说明，迭代过程的收敛速度依赖于迭代函数上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取的选取. . )( xNewton迭代法q q 具体而言： 设设x xk k是非线性方程是非线性方程 f

22、 f( (x x)=0)=0的一个近似根，把的一个近似根，把 f f( (x x) )在在x xk k处处作一阶泰勒展开，即用前两项近似代替作一阶泰勒展开，即用前两项近似代替( )( )( )()kkkf xf xf xx x则近似方程转化为则近似方程转化为 ()()()0kkkf xfxxx设 ，上式解为( )0fx ()()kkkf xxxfxNewton迭代法 于是方程于是方程 f f( (x x)=0)=0的新的近似根的新的近似根x xk k+1+1，可得，可得牛顿迭牛顿迭代公式代公式q 1()0,1,2,()kkkkf xxxkfxq 牛顿迭代公式为特殊的不动点迭代。牛顿迭代公式为特

23、殊的不动点迭代。 其迭代函数为其迭代函数为 ,)()()(xfxfxxNewton迭代法几何解释 设设 是根是根 的某个近似值，过曲线的某个近似值，过曲线 上横上横坐标为坐标为 的点的点 引切线，并将该切线与引切线，并将该切线与 轴的交点的横轴的交点的横坐标坐标 作为作为 的新的近似值的新的近似值. . kx*x)( xfy kxkPx1kx*x 注意到切线方程为注意到切线方程为 ).)()(kkkxxxfxfy牛顿法的收敛性 q 定理定理 设f(xf(x* *)=0, ,)=0, ,且在且在 x x* * 的邻域的邻域 上上 存在存在, , 连续连续, ,则可得则可得 (1) (1)Newt

24、onNewton迭代公式在迭代公式在单根情况下至少单根情况下至少2 2阶局部收敛阶局部收敛. . (2) (2)( *)0fxf*1* 2*()()()2()limnnnxxfxcxxfxq 牛顿法的计算步骤：步骤步骤1 1 准备准备选定初始近似值选定初始近似值 ，0 x),(00 xff计算计算 ).(00 xff步骤步骤2 2 迭代迭代按公式按公式0001/ ffxx迭代一次，迭代一次，得新的近似值得新的近似值 ，计算，计算1x).(),(1111xffxff步骤步骤3 3 控制控制如果如果 满足满足 或或 ，1x121f则终止迭代，以则终止迭代，以 作为所求的根；作为所求的根；1x否则转

25、步骤否则转步骤4 4. 此处此处 是允许误差，而是允许误差，而 21,牛顿法的计算步骤：，时当时当CxxxxCxxx1101101其中其中 是取绝对误差或相对误差的控制常数，是取绝对误差或相对误差的控制常数，C步骤步骤4 4 修改修改或者或者 ，则方法失败；，则方法失败；01f 否则以否则以 代替代替 转步骤转步骤2 2继续迭代继续迭代. .),(111ffx),(000ffx如果迭代次数达到预先指定的次数如果迭代次数达到预先指定的次数 ，Nfunction y=newton(x0)x1=x0fc(x0)/df(x0); n = 1;while (abs(x1 x0)=1.0e6)&(n0 0 S S, ,使对使对 x x0 0 D D0 0，由牛顿迭代公式产生的序列由牛顿迭代公式产生的序列 x x( (k k) ) D D0 0，且此序列，且此序列超线性超线性收敛于收敛于x x* *；进一步，进一步，若若F F( (x x) )在在S S内内2 2次连续可微，则次连续可微，则序列序列 x x( (k k) ) 至少是至少是平方收敛平方收敛的的. .求方程组求方程组F F( (x x)=0)=0的解的解x x* *, ,可使用下迭代公式可使用下迭代公式: : F F (