数值分析非线性方程组的求解精品文稿.ppt

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

1、数值分析课件非线性方程组的求解第1页，本讲稿共64页预备知识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)在在x=sx=s的某一邻域

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

3、数大于5 5的多项式方程的多项式方程,它的根一般不它的根一般不能用解析表达式表达。能用解析表达式表达。示示.l 对于超越方程或其他非线性方程，可能没有零点，也可能有一对于超越方程或其他非线性方程，可能没有零点，也可能有一个或若干个零点，甚至无穷多个零点。个或若干个零点，甚至无穷多个零点。第3页，本讲稿共64页根的存在性定理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)

4、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页根的隔离求根的隔离区间的两种方法求根的隔离区间的两种方法q 画图法画图法n 画出画出y y=f f(x x)的略图，从而看出曲线与的略图，从而看出曲线与x x轴交轴交 点的大致位置。点的大致位置。n 也可将也可将f f(x x)=0)=0分解为分解为 1 1(x x)=

5、)=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页023yx画图法第6页，本讲稿共64页逐步搜索法n 对于给定的对于给定的f f(x x)，设有根区间为设有根区间为 A A,B B，从从x x0 0=A A

6、 出发，以步长出发，以步长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 的函数值异号，则得到一个缩小的有根子区间的函数值异号，则得到一个缩小的有根子区间 x xi i-1-1,x xi i。n 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h hn 要选择适当要选择适当h h ，使之既能把根隔离开来，工

7、作量又使之既能把根隔离开来，工作量又 不太大。不太大。q 逐步搜索法逐步搜索法第7页，本讲稿共64页二分法 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)内只有一个内只有一个(重根视为一个重根视为一个)实

8、根。实根。q 二分法的基本思想二分法的基本思想 用对分区间的方法，通过判别函数用对分区间的方法，通过判别函数用对分区间的方法，通过判别函数用对分区间的方法，通过判别函数f f f f(x x x x)在每个在每个在每个在每个 对分区间中点的符号，逐步将有根区间缩小，最对分区间中点的符号，逐步将有根区间缩小，最对分区间中点的符号，逐步将有根区间缩小，最对分区间中点的符号，逐步将有根区间缩小，最 终求得一个具有相当精确程度的近似根终求得一个具有相当精确程度的近似根终求得一个具有相当精确程度的近似根终求得一个具有相当精确程度的近似根第8页，本讲稿共64页二分法详细步骤l l l 第9页，本讲稿共64

9、页第10页，本讲稿共64页二分法终止的条件q 如下条件终止，可否如下条件终止，可否？这不能保证精确值的精度！x x*第11页，本讲稿共64页q 有如下估计有如下估计q 因此终止的条件为因此终止的条件为q 二分法终止的条件对于给定的精度 ,可估计二分法所需的步数 k：第12页，本讲稿共64页二分法的优缺点二分法的优缺点q 优点优点l 计算简单，方法可靠，并保证收敛计算简单，方法可靠，并保证收敛 l 对函数对函数 要求不高，只要连续即可要求不高，只要连续即可。q 缺点缺点l 无法求复根和偶重根无法求复根和偶重根l 收敛慢收敛慢 l 调用一次求解一个调用一次求解一个 a,ba,b间的多个根无法求得间

10、的多个根无法求得 一般求方程的近似根，不大单独使用，常用来一般求方程的近似根，不大单独使用，常用来为其它方法求方程近似根提供好的初值。方程求根为其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法最常用的方法是迭代法。第13页，本讲稿共64页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=

11、c;end n=n+1;endy=c;elseif feval(fun,a)=0 y=a;elseif feval(fun,b)=0 y=b;end第14页，本讲稿共64页第15页，本讲稿共64页不动点迭代法q 迭代法的基本思想是一种逐次逼近的方法，首先 给定一个粗糙的初值，然后用同一个迭代公式，反复校正这个初值，直到满足预先给出的精度要求。q 迭代法的基本步骤f(x)=0等价变换f(x)的根x=(x)(x)的不动点第16页，本讲稿共64页从一个初值从一个初值 x0 出发出发，计算计算 x1=(x0),x2=(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x x*使得使得 ，且且

12、 连续，则由连续，则由 可可知知 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页迭代法的几何含义yxyy=xsy=g(x)x0p0 x1p1第18页，本讲稿共64页需要讨论的问题需要讨论的问题 n 首先期望每个首先期望每个x xk k都在都在 (x x)的定义域上的定义域上,保持有

13、界而保持有界而 且收敛到精确解且收敛到精确解;n 如何选取适合的迭代函数如何选取适合的迭代函数 (x x););n 迭代函数迭代函数 (x x)迭代满足什么条件迭代满足什么条件,迭代序列收敛迭代序列收敛到到 精确解精确解,收敛速度如何收敛速度如何;H H 第19页，本讲稿共64页l 设将原方程改写成下列形式设将原方程改写成下列形式 据此建立迭代公式据此建立迭代公式 l 但若采用方程另一种等价形式建立迭代公式建立迭代公式 第20页，本讲稿共64页第二种方法仍取迭代初值 ，则有 结果会越来越大，不可能趋于某个极限.第21页，本讲稿共64页 迭代法的收敛条件迭代法的收敛条件 q 定理第22页，本讲稿

14、共64页 注注 q 条件(2)可用更强更便于应用的条件代替:q 由误差估计可以得到迭代终止的条件 q 由误差估计可以知道L越小，收敛越快以及迭代最 少次数 第23页，本讲稿共64页 局部收敛性局部收敛性 q 前述定理条件为充分条件，非必要条件。在实际 应用当中 条件并不易检验。q 定义（局部收敛性）设 有不动点 ，如果存在 的某个邻域对任意 ，迭代产生的序列迭代产生的序列且收敛到 ，则称迭代法则称迭代法局部收敛局部收敛.q 定理定理 设设s s为为 (x x x x)的不动点的不动点,(x x x x)在在s s的某个邻域内连续的某个邻域内连续,且且|(x*x*x*x*)|1,|=1.0e 6

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

16、敛.第29页，本讲稿共64页收敛阶定理收敛阶定理 q 数p的大小反映了迭代法的收敛速度的快慢，P越大，收 敛越快，所以说收敛阶是对迭代法收敛速度的一种度量。q（收敛阶定理）对于迭代过程 ，如果 在所求根 的邻近连续，并且:则该迭代过程在点 邻近是P阶收敛的。上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取.第30页，本讲稿共64页NewtonNewton迭代法迭代法q NewtonNewton法的基本思想法的基本思想 将非线性方程线性化，以线性方程的解逐步逼近非线性将非线性方程线性化，以线性方程的解逐步逼近非线性将非线性方程线性化，以线性方程的解逐步逼近非线性将非线性方程线性化，以线性方

17、程的解逐步逼近非线性方程的解方程的解方程的解方程的解 q 具体而言：设设x xk k是非线性方程是非线性方程 f f(x x)=0)=0的一个近似根，把的一个近似根，把 f f(x x)在在x xk k处作一阶处作一阶泰勒展开，即用前两项近似代替泰勒展开，即用前两项近似代替则近似方程转化为则近似方程转化为 设 ，上式解为第31页，本讲稿共64页NewtonNewton迭代法迭代法 于是方程于是方程 f f(x x)=0)=0的新的近似根的新的近似根x xk k+1+1，可得，可得牛顿迭代公式牛顿迭代公式q q 牛顿迭代公式为特殊的不动点迭代。其迭代函数为 第32页，本讲稿共64页NewtonN

18、ewton迭代法几何解释迭代法几何解释 设 是根 的某个近似值，过曲线 上横坐标为 的点 引切线，并将该切线与 轴的交点的横坐标 作为 的新的近似值.注意到切线方程为注意到切线方程为 第33页，本讲稿共64页牛顿法的收敛性牛顿法的收敛性 q 定理 设f(x*)=0,且在 x*的邻域 上 存在,连续,则可得(1)Newton迭代公式在单根情况下至少2阶局部收敛.(2)定理表明，当初值定理表明，当初值定理表明，当初值定理表明，当初值x x x x0 0 0 0充分接近充分接近充分接近充分接近x x x x*时，时，时，时，NewtonNewtonNewtonNewton法的法的法的法的收敛速度较快

19、，但当初值不够好时，可能会不收敛收敛速度较快，但当初值不够好时，可能会不收敛收敛速度较快，但当初值不够好时，可能会不收敛收敛速度较快，但当初值不够好时，可能会不收敛或收敛于别的根，这可从或收敛于别的根，这可从或收敛于别的根，这可从或收敛于别的根，这可从NewtonNewtonNewtonNewton法的几何意义看到：法的几何意义看到：法的几何意义看到：法的几何意义看到：q 第34页，本讲稿共64页牛顿法的计算步骤牛顿法的计算步骤：步骤1 准备选定初始近似值 ，计算 步骤2 迭代按公式迭代一次，得新的近似值 ，计算步骤3 控制如果 满足 或 ，则终止迭代，以 作为所求的根；否则转步骤否则转步骤4

20、 4.此处 是允许误差，而 第35页，本讲稿共64页牛顿法的计算步骤牛顿法的计算步骤：其中 是取绝对误差或相对误差的控制常数，步骤4 修改或者 ，则方法失败；否则以 代替 转步骤2继续迭代.如果迭代次数达到预先指定的次数 ，第36页，本讲稿共64页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

21、(x x)在在S S内内2 2次连续可微，则次连续可微，则序列序列 x x(k k)至少是至少是平方平方收敛收敛的的.求方程组F(x)=0的解x*,可使用下迭代公式:F(x(k)(x x(k)=F(x(k)第60页，本讲稿共64页(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).解非线性方程组的牛顿迭代法 q 算法 第61页，本讲稿共64页例解解解解 牛顿法迭代公式为牛顿法迭代公式为选选 x=(1,1)T,当当 k=4 时时第62页，本讲稿共64页Matlab非线性方程求根的命令1.代数方程组的求根roots r=roots(P)2.求零点fzero x=fzero(F,x0,option)3 求方程组数值解的命令fsolve x=fsolve(fun,x0,options)第63页，本讲稿共64页复习题7.1，7.4,7.5，7.8,7.97.15,7.16,7.17,7.18第64页，本讲稿共64页