数值分析非线性方程组的求解幻灯片.ppt

《数值分析非线性方程组的求解幻灯片.ppt》由会员分享，可在线阅读，更多相关《数值分析非线性方程组的求解幻灯片.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值分析课件非线性方程组的求解第1页，共64页，编辑于2022年，星期六预备知识预备知识q 满足函数方程满足函数方程 f(x)=0 f(x)=0 的的x x称为方程称为方程(1)(1)的的根根，或称，或称为函数为函数f(x)f(x)的的零点零点。如果函数。如果函数(x)x)可分解为可分解为 (x)=(xx)=(x s)s)m mg(x)g(x)且且g(g(s s)0,0,则称则称s s是是(x)x)的的m m重零点重零点或或(x)=0 x)=0的的m m重重根。当根。当m=1m=1时，称时，称s s是是(x)x)的的单根或单零点单根或单零点。q 定理定理 假设函数假设函数y=f(x)y=f(x

2、)在在x=sx=s的某一邻域内充分可的某一邻域内充分可 微，则微，则s s是方程是方程f(x)=0f(x)=0的的m m重根的充分必要条件是重根的充分必要条件是第2页，共64页，编辑于2022年，星期六求解非线性方程的根的问题可分为下面几个方面求解非线性方程的根的问题可分为下面几个方面：q l 根的存在性根的存在性l 根的隔离根的隔离l 根的精确化根的精确化q 非线性方程根的存在性非常复杂。非线性方程根的存在性非常复杂。l 对于代数方程即多项式方程，其根的对于代数方程即多项式方程，其根的个数与代数方程的个数与代数方程的次数相同次数相同。而且理论上已证明，对于次数。而且理论上已证明，对于次数n=

3、4n=4的多项式方程的多项式方程,它的它的根可以用公式表示根可以用公式表示,而而次数大于次数大于5 5的多项式方程的多项式方程,它的根一般不能用它的根一般不能用解析表达式表达。解析表达式表达。示示.l 对于超越方程或其他非线性方程，可能没有零点，也可对于超越方程或其他非线性方程，可能没有零点，也可能有一个或若干个零点，甚至无穷多个零点。能有一个或若干个零点，甚至无穷多个零点。第3页，共64页，编辑于2022年，星期六根的存在性定理根的存在性定理q 定理定理1 1.(根的存在定理根的存在定理)假设函数假设函数y=f(x)y=f(x)C C a,ba,b,且且f(a)f(b)0,f(a)f(b)0

4、,则至则至 少存在一点少存在一点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,b 上单调连续上单调连续,且且 f(a)f(b)0,f(a)f(b)0,则恰好只存在一点则恰好只存在一点x x (a,b)(a,b)使得使得 f(x)=0f(x)=0 第4页，共64页，编辑于2022年，星期六根的隔离根的隔离求根的隔离区间的两种方法求根的隔离区间的两种方法q 画图法画图法n 画出画出y y=f f(x x)的略图，从

5、而看出曲线与的略图，从而看出曲线与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)两曲线交点的横坐标所在的子两曲线交点的横坐标所在的子 区间即为含根区间。区间即为含根区间。例如例如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内内第5页，共64页，编辑于2

6、022年，星期六023yx画图法画图法第6页，共64页，编辑于2022年，星期六逐步搜索逐步搜索法法n 对于给定的对于给定的f f(x x)，设有根区间为设有根区间为 A A,B B，从从x x0 0=A A 出发，以步长出发，以步长h h=(=(B B-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 的函数值异号，则得到一个缩小的有根子区间的函数值异号，则得

7、到一个缩小的有根子区间 x xi i-1-1,x xi i。n 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h hn 要选择适当要选择适当h h ，使之既能把根隔离开来，工作量又使之既能把根隔离开来，工作量又 不太大。不太大。q 逐步搜索法逐步搜索法第7页，共64页，编辑于2022年，星期六二分法二分法 Bisectionq 在方程求根的方法中，最直观、最简单的方法就在方程求根的方法中，最直观、最简单的方法就 是二分法。是二分法。q 给定方程给定方程f(x)=0,f(x)=0,设设f(x)f(x)在区间在区间 a,ba,b连续连续,且且f(a)f(b)0,f

8、(a)f(b)0,则方程则方程f(x)f(x)在在(a,b)a,b)内至少有一根内至少有一根,为便于讨论为便于讨论,不妨设方不妨设方 程程f(x)=0f(x)=0在在(a,b)a,b)内只有一个内只有一个(重根视为一个重根视为一个)实根。实根。q 二分法的基本思想二分法的基本思想 用对分区间的方法，通过判别函数用对分区间的方法，通过判别函数用对分区间的方法，通过判别函数用对分区间的方法，通过判别函数f f f f(x x x x)在每个在每个在每个在每个 对分区间中点的符号，逐步将有根区间缩小，最对分区间中点的符号，逐步将有根区间缩小，最对分区间中点的符号，逐步将有根区间缩小，最对分区间中点的

9、符号，逐步将有根区间缩小，最 终求得一个具有相当精确程度的近似根终求得一个具有相当精确程度的近似根终求得一个具有相当精确程度的近似根终求得一个具有相当精确程度的近似根第8页，共64页，编辑于2022年，星期六二分法详细步骤二分法详细步骤l l l 第9页，共64页，编辑于2022年，星期六第10页，共64页，编辑于2022年，星期六二分法终止的条件二分法终止的条件q 如下条件终止，可否如下条件终止，可否？这不能保证精确值的精度！这不能保证精确值的精度！x x*第11页，共64页，编辑于2022年，星期六q 有如下估计有如下估计q 因此终止的条件为因此终止的条件为q 二分法终止的条件二分法终止的

10、条件对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k k：第12页，共64页，编辑于2022年，星期六二分法的优缺点二分法的优缺点q 优点优点l 计算简单，方法可靠，并保证收敛计算简单，方法可靠，并保证收敛 l 对函数对函数 要求不高，只要连续即可要求不高，只要连续即可。q 缺点缺点l 无法求复根和偶重根无法求复根和偶重根l 收敛慢收敛慢 l 调用一次求解一个调用一次求解一个 a,ba,b间的多个根无法求得间的多个根无法求得 一般求方程的近似根，不大单独使用，常用来为一般求方程的近似根，不大单独使用，常用来为其它方法求方程近似根提供好的初值。方程求根最常用其它方

11、法求方程近似根提供好的初值。方程求根最常用的方法是迭代法的方法是迭代法。第13页，共64页，编辑于2022年，星期六function y=erfen(fun,a,b,esp)Matlab programif feval(fun,a)*feval(fun,b)esp if feval(fun,a)*feval(fun,c)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

12、=b;end第14页，共64页，编辑于2022年，星期六第15页，共64页，编辑于2022年，星期六不动点迭代法不动点迭代法q 迭代法的迭代法的基本思想基本思想是一种逐次逼近的方法，首先是一种逐次逼近的方法，首先 给定一个粗糙的初值，然后用同一个迭代公式，给定一个粗糙的初值，然后用同一个迭代公式，反复校正这个初值，直到满足预先给出的精度要求。反复校正这个初值，直到满足预先给出的精度要求。q 迭代法的基本步骤迭代法的基本步骤f(x)=0等价变换等价变换f(x)的根x=(x)(x)的不动点第16页，共64页，编辑于2022年，星期六从一个初值从一个初值 x0 出发出发，计算计算 x1=(x0),x

13、2=(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x x*使得使得 ，且且 连续，则由连续，则由 可可知知 x*=(x*)，即即x x*是是 的不动点，也就是的不动点，也就是f f 的根。的根。不动点迭代法不动点迭代法定义定义：迭代公式迭代公式 x xk k+1+1=(x xk k)(k k=0,1,)=0,1,)被称为求被称为求解方程解方程 f f(x x)=0)=0 的的不动点迭代法不动点迭代法，其中，其中 (x x)称为称为迭代迭代函数函数。q q 第17页，共64页，编辑于2022年，星期六迭代法的几何含义迭代法的几何含义yxyy=xsy=g(x)x0p0 x1p1第1

14、8页，共64页，编辑于2022年，星期六需要讨论的问题需要讨论的问题 n 首先期望每个首先期望每个x xk k都在都在 (x x)的定义域上的定义域上,保持有界而保持有界而 且收敛到精确解且收敛到精确解;n 如何选取适合的迭代函数如何选取适合的迭代函数 (x x););n 迭代函数迭代函数 (x x)迭代满足什么条件迭代满足什么条件,迭代序列收敛到迭代序列收敛到 精确解精确解,收敛速度如何收敛速度如何;H H 第19页，共64页，编辑于2022年，星期六l 设将原方程改写成下列形式设将原方程改写成下列形式 据此建立迭代公式据此建立迭代公式 l 但但若采用方程另一种等价形式若采用方程另一种等价形

15、式建立迭代公式建立迭代公式 第20页，共64页，编辑于2022年，星期六第二种方法第二种方法仍取迭代初值仍取迭代初值 ，则有，则有 结果会越来越大，不可能趋于某个极限结果会越来越大，不可能趋于某个极限.第21页，共64页，编辑于2022年，星期六 迭代法的收敛条件迭代法的收敛条件 q 定理定理第22页，共64页，编辑于2022年，星期六 注注 q 条件条件(2)(2)可用更强更便于应用的条件代替可用更强更便于应用的条件代替:q 由误差估计可以得到迭代终止的条件由误差估计可以得到迭代终止的条件 q 由误差估计可以知道由误差估计可以知道L越小，收敛越快越小，收敛越快以及以及迭代最迭代最 少次数少次

16、数 第23页，共64页，编辑于2022年，星期六 局部收敛性局部收敛性 q 前述定理条件为前述定理条件为充分条件充分条件，非必要条件。在实际，非必要条件。在实际 应用当中应用当中 条件并不易检验条件并不易检验。q 定义定义（局部收敛性）（局部收敛性）设设 有不动点有不动点 ，如果存在如果存在 的某个邻域的某个邻域对任意对任意 ，迭代产生的序列迭代产生的序列且收敛到且收敛到 ，则称迭代法则称迭代法局部收敛局部收敛.q 定理定理 设设s s为为 (x x x x)的不动点的不动点,(x x x x)在在s s的某个邻域内连续的某个邻域内连续,且且|(x*x*x*x*)|1,|=1.0e 6)&(n

17、=1000)x=x1;x1=g(x);n=n+1;endx1nmatlab program 第28页，共64页，编辑于2022年，星期六收敛阶收敛阶(描述收敛速度描述收敛速度)收敛速度（收敛速度的阶）收敛速度（收敛速度的阶）收敛速度（收敛速度的阶）收敛速度（收敛速度的阶）q 设迭代过程设迭代过程 收敛于方程收敛于方程 的根的根 ，如果迭代误差如果迭代误差 当当 时成立下列时成立下列渐近关系式渐近关系式则称则称则称则称 xnxnxnxn 是是是是p p p p阶收敛阶收敛阶收敛阶收敛 若若 p p=1=1 ,称称 x xk k 为为线性收敛线性收敛,这时这时 0 0 1,1,称称 x xk k

18、为为超线性收敛超线性收敛;p p=2,=2,称其为称其为平方收敛平方收敛.第29页，共64页，编辑于2022年，星期六收敛阶定理收敛阶定理 q 数数p p的大小反映了迭代法的收敛速度的快慢，的大小反映了迭代法的收敛速度的快慢，P P越大，收越大，收 敛越快敛越快，所以说收敛阶是对迭代法收敛速度的一种度量。，所以说收敛阶是对迭代法收敛速度的一种度量。q（收敛阶定理）（收敛阶定理）对于迭代过程对于迭代过程 ，如果，如果 在所求在所求根根 的邻近连续，并且的邻近连续，并且:则该迭代过程在点则该迭代过程在点 邻近是邻近是P P阶收敛的阶收敛的。上述定理说明，迭代过程的收敛速度依赖于迭代函数上述定理说明

19、，迭代过程的收敛速度依赖于迭代函数 的选取的选取.第30页，共64页，编辑于2022年，星期六NewtonNewton迭代法迭代法q NewtonNewton法的基本思想法的基本思想 将非线性方程线性化，以线性方程的解逐步逼近非将非线性方程线性化，以线性方程的解逐步逼近非将非线性方程线性化，以线性方程的解逐步逼近非将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解线性方程的解线性方程的解线性方程的解 q 具体而言：设设x xk k是非线性方程是非线性方程 f f(x x)=0)=0的一个近似根，把的一个近似根，把 f f(x x)在在x xk k处作一阶泰处作一阶泰勒展开，即用前两项近似

20、代替勒展开，即用前两项近似代替则近似方程转化为则近似方程转化为 设 ，上式解为第31页，共64页，编辑于2022年，星期六NewtonNewton迭代法迭代法 于是方程于是方程 f f(x x)=0)=0的新的近似根的新的近似根x xk k+1+1，可得，可得牛顿迭代公式牛顿迭代公式q q 牛顿迭代公式为特殊的不动点迭代。牛顿迭代公式为特殊的不动点迭代。其迭代函数为其迭代函数为 第32页，共64页，编辑于2022年，星期六NewtonNewton迭代法几何解释迭代法几何解释 设设 是根是根 的某个近似值，过曲线的某个近似值，过曲线 上横上横坐标为坐标为 的点的点 引切线，并将该切线与引切线，并

21、将该切线与 轴的交点的横轴的交点的横坐标坐标 作为作为 的新的近似值的新的近似值.注意到切线方程为注意到切线方程为 第33页，共64页，编辑于2022年，星期六牛顿法的收敛性牛顿法的收敛性 q 定理定理 设f(x*)=0,f(x*)=0,且在且在 x*x*的邻域的邻域 上上 存在存在,连续连续,则可得则可得(1)(1)NewtonNewton迭代公式在迭代公式在单根情况下至少单根情况下至少2 2阶局部收敛阶局部收敛.(2)(2)定理表明，当初值定理表明，当初值定理表明，当初值定理表明，当初值x x x x0 0 0 0充分接近充分接近充分接近充分接近x x x x*时，时，时，时，Newton

22、NewtonNewtonNewton法的法的法的法的收敛速度较快，但当初值不够好时，可能会不收敛收敛速度较快，但当初值不够好时，可能会不收敛收敛速度较快，但当初值不够好时，可能会不收敛收敛速度较快，但当初值不够好时，可能会不收敛或收敛于别的根，这可从或收敛于别的根，这可从或收敛于别的根，这可从或收敛于别的根，这可从NewtonNewtonNewtonNewton法的几何意义看到：法的几何意义看到：法的几何意义看到：法的几何意义看到：q 第34页，共64页，编辑于2022年，星期六牛顿法的计算步骤牛顿法的计算步骤：步骤步骤1 1 准备准备选定初始近似值选定初始近似值 ，计算计算 步骤步骤2 2

23、迭代迭代按公式按公式迭代一次，迭代一次，得新的近似值得新的近似值 ，计算，计算步骤步骤3 3 控制控制如果如果 满足满足 或或 ，则终止迭代，以则终止迭代，以 作为所求的根；作为所求的根；否则转步骤否则转步骤4 4.此处此处 是允许误差，而是允许误差，而 第35页，共64页，编辑于2022年，星期六牛顿法的计算步骤牛顿法的计算步骤：其中其中 是取绝对误差或相对误差的控制常数，是取绝对误差或相对误差的控制常数，步骤步骤4 4 修改修改或者或者 ，则方法失败；，则方法失败；否则以否则以 代替代替 转步骤转步骤2 2继续迭代继续迭代.如果迭代次数达到预先指定的次数如果迭代次数达到预先指定的次数 ，第

24、36页，共64页，编辑于2022年，星期六function 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*,*,可使用下迭代公式可使用下

25、迭代公式:F F (x x(k k)()(x x x x(k k)=)=F F(x x(k k)第60页，共64页，编辑于2022年，星期六(1)在在 x x*附近选取附近选取 x x(0)(0)D D0 0,给定精度给定精度 00.(2)(2)反复做以下步骤反复做以下步骤,直到达到精度直到达到精度,计算计算 F F(x x(k k)和和 F F (x x(k k),),x x(k k)=(=(x x(k k)x x(k-k-1)1),求解关于求解关于 x x(k k)的方程组的方程组,计算计算 x x(k+k+1)1)=x x(k k)+x x(k k).解非线性方程组的牛顿迭代法解非线性方

26、程组的牛顿迭代法 q 算法 第61页，共64页，编辑于2022年，星期六例例解解 牛顿法迭代公式为牛顿法迭代公式为选选 x=(1,1)T,当当 k=4 时时第62页，共64页，编辑于2022年，星期六Matlab非线性方程求根的命令非线性方程求根的命令1.代数方程组的求根代数方程组的求根roots r=roots(P)2.2.求零点求零点fzero x=fzero(F,x0,option)3 3 求方程组数值解的命令求方程组数值解的命令fsolve x=fsolve(fun,x0,options)第63页，共64页，编辑于2022年，星期六复习题复习题7.1，7.4,7.5，7.8,7.97.15,7.16,7.17,7.18第64页，共64页，编辑于2022年，星期六