《计算机数值方法第3章课件》由会员分享，可在线阅读，更多相关《计算机数值方法第3章课件（45页珍藏版）》请在金锄头文库上搜索。
1、定义：设f(x)为一元连续函数，称方程f(x)=0为函数方程。特别地，当f(x)不是 x 的线性函数时，称对应的函数方程为非线性方程。在非在非线线性方程中，当性方程中，当f f( (x x) )为为多多项项式函数式函数时时，称，称为为代数方程代数方程代数方程代数方程，其一般形式如下：，其一般形式如下：此即此即为为n n次代数方程。若存在一点次代数方程。若存在一点x x* *，使，使f f( (x x*)=0*)=0，则则x x* *称称为为方程方程f f( (x x)=0)=0的根。的根。1计算机数值方法第3章当当f f( (x x) )不是多不是多项项式函数式函数时时，如，如f f( (x
2、x)=)=e ex x-sin-sinx x，则则f f( (x x)=0)=0称称为为超越方程超越方程超越方程超越方程。 在非在非线线性方程中，性方程中，绝绝大部分没有求根公式，就大部分没有求根公式，就必必须须借助于数借助于数值计值计算方法算方法逐次逼近法逐次逼近法逐次逼近法逐次逼近法来完成。来完成。对对对对 分分分分 法法法法 及及及及 区区区区 间间间间 迭迭迭迭 代代代代 法法法法利利用用连连续续函函数数f f( (x x) )的的零零点点定定理理，将将f f( (x x)=0)=0的的含含根根区区间间逐逐次次减减半半缩缩小小，构构造造出出收收敛敛的的点点列列 x xk k ，来来逐逐
3、步步逼近逼近f f( (x x)=0)=0的根的根x x* *的数的数值计值计算方法称算方法称为为对对分法分法分法分法。2计算机数值方法第3章零点定理指出：若f(x)a , b，且满足f(a)f(b)0，则在区间a , b上至少有一点 ，使f( )=0。 a a x x0 0 x x* * x x1 1 b b 将将含含根根区区间间对对分分为为两两个个子子区区间间后后，在在其其上上又又可可利利用用零零点点定定理理确确定定根根在在哪哪个个子子区区间间上上。如如此此继继续续下下去去就就得得到到各各子子区区间间的中点构成点列的中点构成点列 x xk k 中，它将收中，它将收敛敛于于f f( (x x
4、)=0)=0的根的根x x* *处处。3计算机数值方法第3章 例例例例2.12.1用用对对分分法法求求下下面面方方程程在在区区间间11，22内内的的根根，要求要求绝对误绝对误差不超差不超过过1010-3-3。解解解解因因为为f f(1)= -5(1)= -5，f f(2)=14(2)=14，所以在区，所以在区间间1 , 21 , 2内内有根，故可以使用有根，故可以使用对对分法。分法。c c=(1+2)/2=1.5=(1+2)/2=1.5，f f( (c c) )2.3752.375，含根区，含根区间为间为 a a1 1 , , b b1 1= 1 , 1.5= 1 , 1.5c c1 1=(1
5、+1.5)/2=1.25=(1+1.5)/2=1.25，f f(c(c1 1) )-1.79687-1.79687，含根区，含根区间为间为 a a2 2 , , b b2 2= 1.25 , 1.5= 1.25 , 1.5，c c9 9=(1.36128125+1.365234375)/2=1.364257813=(1.36128125+1.365234375)/2=1.364257813，4计算机数值方法第3章f(c9)= -0.01605，含根区间为a10 , b10= 1.364257813 , 1.365234375因因误误差差故可停止故可停止计计算，得准确根算，得准确根x x* *的
6、近似的近似值为值为c c9 9=1.365234375=1.365234375。5计算机数值方法第3章1 1、二分法的收、二分法的收、二分法的收、二分法的收敛敛性性性性二分法又称二分法又称区区区区间间迭代法迭代法迭代法迭代法。在求根区。在求根区间间 a a , , b b 上，上，只要只要满满足足f f( (a a) )f f( (b b)0)0，则则此种迭代是收此种迭代是收敛敛的。的。2 2、如何控制迭代（一般而言）？、如何控制迭代（一般而言）？、如何控制迭代（一般而言）？、如何控制迭代（一般而言）？（1 1）给给定精度控制量定精度控制量EPSEPS，如二分法以，如二分法以长长度度| |a
7、ak k-b-bk k|EPSEPS或区或区间间中点中点c ck k函数函数值值| |f f( (c ck k)|)|EPSEPS为为控控制条件；制条件；（2 2）给给定最大允定最大允许许迭代次数（即区迭代次数（即区间对间对分次数）分次数），以避免因迭代，以避免因迭代发发散而无散而无穷穷迭代。迭代。6计算机数值方法第3章二分法迭代次数估算二分法迭代次数估算二分法迭代次数估算二分法迭代次数估算：设设迭代次数迭代次数为为N N，精度控制量，精度控制量为为EPSEPS，则则可按下可按下式估算：式估算：如如例例例例2.12.1，EPSEPS=10=10-3-3，b b- -a a=1=1，故有：，故有
8、：故所需迭代次数故所需迭代次数为为N N=10=10。为为在在计计算机上算机上实现实现二分法求根，下面二分法求根，下面对对其其计计算步算步骤骤（或（或称算法）称算法）进进行描述：行描述：7计算机数值方法第3章INPUT端点a , b；误差EPS；迭代次数上界N；定义函数f(x)。OUTPUT 近似解 c 或迭代失败的信息Step1FA= f(a) ; FB= f(b)If（FAFB0）Then k=0 ; Do Step2Else OUTPUT （不能用对分法求解) STOP End IfStep2While kN Do Steps36Step3c=(a+b)/2 ; FC= f(c)Step
9、4If（|FC|EPSOr（(b-a)/20）Then a=c ; FA=FC Else b=c End If/计算ak，bk转向Step3Step7OUTPUT（次数已达上界，迭代不收敛 , k）STOP8计算机数值方法第3章9计算机数值方法第3章练习题求方程cosx=x的根（1）验证方程在区间0, /2内有单根；（2）令a0=0，b0= /2，用对分法求解可得一系列的含根区间a0 , b0、a1 , b1、a2 , b2，试求出a2、b2。1 1、对对分法的缺点：分法的缺点：分法的缺点：分法的缺点：每迭代一次含根区每迭代一次含根区间缩间缩小一半，收小一半，收敛敛速度速度较较慢。慢。2 2、
10、比例求根法：、比例求根法：、比例求根法：、比例求根法：基本思想基本思想基本思想基本思想：以函数：以函数 f f( (x x) )曲曲线线在含根区在含根区间间上上 a ak k , , b bk k 的割的割线线与与 x x 轴轴的交点的交点 x xk k 逐步逼近根逐步逼近根 x x* *。10计算机数值方法第3章如下如下图图所示，所示，连连接接ABAB弦交弦交x x轴轴于于x xk k，判断，判断f f( (x xk k) )是是否与否与f f( (a ak k) ) 同号：同号：若同号，若同号，则则a ak k+1+1= =x xk k，b bk k+1+1= =b bk k；不同号，不同
11、号，则则a ak k+1+1= =a ak k，b bk k+1+1= =x xk k 。 o ob bk ka ak kx xk kx x* *A AB By yx x利用三角形利用三角形a ak kAxAxk k与三角形与三角形b bk kBxBxk k相似，有相似，有 11计算机数值方法第3章于是得到数列于是得到数列 x xk k 的迭代格式：的迭代格式： 如果如果给给定条件定条件f f( (a a) )f f( (b b)0)0，且，且f f ( (x x) )与与f ”f ”( (x x) )不不变变号，号，则则上述方法一定收上述方法一定收敛敛于所求的根。于所求的根。12计算机数值方
12、法第3章1、由非线性方程f(x)=0，将其变换为等价形式x= (x)；2、构造迭代公式xk+1= (xk)；3、取初值 x0，计算x1= (x0)、x2= (x1)、，即可获得一个数列xk，并以此数列的收敛点作为所求根的数值计算方法简单迭代法，其中 (x)迭代函数， xk迭代数列，如果该数列收敛，即 ：简简简简 单单单单 迭迭迭迭 代代代代 法法法法13计算机数值方法第3章因此有因此有 = = ( ( ) )，则则 即即为为方程方程f f( (x x)=0)=0的根。的根。在在实际实际的的计计算中算中给给定一个精度控制量定一个精度控制量 ，当，当| |x xk k+1+1- -x xk k|
13、时时，取，取 = =x xk k+1+1作作为为方程方程f f( (x x)=0)=0的根。的根。由由方方程程f f( (x x)=0)=0构构造造等等价价形形式式x x= = ( (x x) )时时， ( (x x) )的的形形式式不不是是唯唯一一的的，而而且且并并非非每每种种迭迭代代函函数数 ( (x x) )所所构构成成的的迭迭代代形形式式x xk k+1+1= = ( (x xk k) )都都能能保保证证所所形形成成的的数数列列收收敛敛，如下例所示：如下例所示： 例例例例 用迭代法求区用迭代法求区间间2 , 32 , 3内方程内方程x x3 3-2-2x x-5=0-5=0的根的根14
14、计算机数值方法第3章解一解一解一解一将将方方程程两两边边同同时时加加上上2x+52x+5，再再开开三三次次方方得同解方程：得同解方程：作迭代格式：作迭代格式：取取迭代得：迭代得：x x1 1=2.154434690=2.154434690，x x2 2=2.103612029,=2.103612029,x x3 3=2.095927410=2.095927410，x x4 4=2.094553215,=2.094553215,x x5 5=2.094583250=2.094583250，x x6 6=2.094556309,=2.094556309,15计算机数值方法第3章x7=2.09455
15、2215,x8=2.094551593,x9=2.094551498,x10=2.094551484,x11=2.094551482=x12由于x11=x12，再迭代已无变化，可见 x11。解二解二解二解二将方程两将方程两边边同加同加2 2x x3 3+5+5，再同除，再同除3 3x x2 2-2-2，得，得同解方程：同解方程：x x=(2=(2x x3 3+5)/(3+5)/(3x x2 2-2)-2)。作迭代格式作迭代格式 ：取取x x0 0=2.5=2.5迭代得：迭代得： x x1 1=2.164179104,=2.164179104,x x2 2=2.097135356,=2.0971
16、35356,x x3 3=2.094555232,=2.094555232,x x4 4=2.094551484,=2.094551484,x x5 5= =x x4 4，故，故 x x4 416计算机数值方法第3章解三解三解三解三将方程两将方程两边边同同时时加上加上2 2x x，再同除，再同除2 2，得同，得同解方程：解方程：作迭代格式：作迭代格式：取取x x0 0=2.5=2.5迭代得：迭代得：x x1 1=5.3125, =5.3125, x x2 2=72.46643066, =72.46643066, x x3 3=190272.0118,=190272.0118,x x4 4=3.
17、444250536=3.444250536 10101515, , x x5 5=2.042933398=2.042933398 10104646，计计算算 x x6 6 时时将溢出。将溢出。由此可由此可见见，迭代序列是否收，迭代序列是否收敛敛和收和收敛敛的速度的的速度的快慢，与迭代函数快慢，与迭代函数 ( (x x) ) 有关。有关。17计算机数值方法第3章说明：方程f(x)=0 改写为等价形式x= (x)，则求f(x)=0的根即求直线y=x与曲线y= (x)的交点。由xk+1= (xk)的迭代过程示意如下图：设设迭代函数迭代函数 ( (x x) )满满足条件：足条件：（1 1） 当当x x
18、 a a , , b b 时时， ( (x x) ) a a , , b b; ;（2 2） 存存在在正正数数L L11，使使对对任任意意x x a a , , bb有有| | ( (x x)| )| L L11，则则对对任任意意初初值值x x0 0 a a , , b b ，迭迭代代数数列列x xk k+1+1= = ( (x xk k) )收收敛敛于于方方程程x x= = ( (x x) )在在 a a , , b b 上上唯唯一一的的根根即即 ( (x x) ) 的不的不动动点点x x* *且有如下且有如下误误差限表达式：差限表达式：18计算机数值方法第3章y=xy=(x)x x0 0x
19、 x1 1x x2 2x x* *I I） | | ( (x x) |1) |11）取初值x02）x1= (x0)3）x2= (x1)，迭代计算的结果xk+1离直线与曲线的交点(x*, (x*)越来越远。即迭代序列不能收敛。y y= =x xx x0 0x x1 1x x2 2x x* *y y= = ( (x x) )20计算机数值方法第3章对对上上例例中中的的三三种种迭迭代代函函数数，因因2.0945514822.094551482，可分可分别验证别验证如下：如下：故依上述迭代法收故依上述迭代法收敛敛定理可知，前两种迭代函定理可知，前两种迭代函数能保数能保证证所构成迭代数列在根所构成迭代数
20、列在根处处收收敛敛，而第三种，而第三种迭代函数不能保迭代函数不能保证证收收敛敛。21计算机数值方法第3章迭代法收敛定理的证明迭代法收敛定理的证明：（1）根（不动点x*）的存在与唯一存在性：f(x)=x- ( (x x) )，由，由，由，由a a (a)(a)，得，得，得，得f(a)=a-f(a)=a- (a)0(a)0，由，由，由，由 (b) b(b) b，得得得得f(b)=b-f(b)=b- (b) 0(b) 0，则则a,ba,b区区区区间间上必存在上必存在上必存在上必存在 x*使f(x*)=x*- ( (x*x*)=0)=0唯一性：假唯一性：假唯一性：假唯一性：假设设存在另一个根（不存在另
21、一个根（不存在另一个根（不存在另一个根（不动动点点点点x*x*）使得）使得）使得）使得x*- ( (x*x*)=0)=0由因因 L1，所以，所以x*-x*=0，即，即x*=x*（2）给定迭代初值）给定迭代初值x0，收敛性的证明：，收敛性的证明：因因 L1，当，当k时时Lk+10，即，即xk+1x*（3）误差估计（误差限表达式）：取某）误差估计（误差限表达式）：取某xk作为根时误差不超过多少？作为根时误差不超过多少？22计算机数值方法第3章当整数p时，时，Lp0，xk+px*，即，即|x*-xk|Lk|x1-x0|/(1-L)23计算机数值方法第3章在区间1 , 2上显然有| (x)|1，而且当
22、x 1 , 2时显然也有 (x) 1 , 2，由迭代法收敛定理可知，迭代格式 例例例例 求求 在在11，22上的根，用上的根，用简单简单迭代迭代法法计计算当算当| |x xk k+1+1- -x xk k|10|00），使），使则则称序列称序列 x xk k 是是 阶阶收收收收敛敛的的。当当 =1=1且且0c10c11时时称称为为超超超超线线性收性收性收性收敛敛。特。特别别地，当地，当 =2=2时时称称为为平方收平方收平方收平方收敛敛。显显然，收然，收敛阶敛阶越高，越高，则则收收敛敛速度越快。速度越快。27计算机数值方法第3章可知，当迭代过程收敛且 (x)连续时，有3 3、简单简单迭代法的收迭
23、代法的收迭代法的收迭代法的收敛阶讨论敛阶讨论：由由这这表明，当表明，当 ( (x x) ) 0 0时时，简单简单迭代法是迭代法是迭代法是迭代法是线线性收性收性收性收敛敛的的的的。4 4、AitkenAitken加速收加速收加速收加速收敛敛法法法法设简单设简单迭代序列迭代序列 x xk k 收收敛敛于根于根x x* *，则则由下式由下式28计算机数值方法第3章这一操作总结为如下式表示的过程：可知，当可知，当k k充分大充分大时时有有这说这说明，在明，在计计算出算出x xk k、x xk k+1+1和和x xk k+2+2后再用三者后再用三者组组合合计计算一个新算一个新值值，有可能更接近于方程的根
24、，有可能更接近于方程的根x x* *，从而加快迭代速度。从而加快迭代速度。29计算机数值方法第3章牛牛顿顿迭迭代代法法又又称称切切切切线线法法法法。如如下下图图所所示示，函函数数方方程程f f( (x x)=0)=0有根有根为为 ，为为求出求出 ：（1 1）过过点点( (x x0 0, ,y y0 0) )作作曲曲线线y y= =f f( (x x) )的的切切线线，该该切切线线与与x x轴轴交于交于x x1 1；该该切切线线的点斜式方程的点斜式方程为为 令令y y=0=0，得，得该该切切线线与与x x轴轴的交点的交点 : :牛牛牛牛 顿顿顿顿 迭迭迭迭 代代代代 法法法法30计算机数值方法第
25、3章（2）过点(x1,y1)再作切线则与x轴交于x2，同理可得： y=f(x) x x0 0 x x1 1 x x2 2 x x3 3(x0,y0)(x1,y1)(x2,y2)31计算机数值方法第3章如此继续下去，即构成了迭代格式（牛顿迭代格式）： 对对于函数方程于函数方程f f( (x x)=0)=0，且，且满满足下面的条件：足下面的条件： （1 1） f f( (x x) )在区在区间间 a a, ,b b 上一、二上一、二阶导阶导数均存在数均存在且且f f (x)(x) 0 0，f f ” ”( (x x) )不不变变号；号；（2 2） f f( (a a) )f f( (b b)0)0
26、；（3 3） 给给定初定初值值x x0 0 a a, ,b b ，有有则则采用牛采用牛顿顿迭代法所得的迭代序列迭代法所得的迭代序列x xk k将收将收敛敛于函数于函数方程方程f f( (x x)=0)=0在区在区间间 a a, ,b b 上的唯一根上的唯一根 。32计算机数值方法第3章对以上三个条件的说明：（1） 保证了根的存在；（2 2） 保保证证了函数了函数f f( (x x) )的的单调单调性及根的唯一性；性及根的唯一性； （3 3）三个条件）三个条件则则共同保共同保证证了序列了序列xxk k 的收的收敛敛性。性。下面只下面只下面只下面只证证明在明在明在明在满满足上述条件足上述条件足上述
27、条件足上述条件时时的收的收的收的收敛敛性：性：性：性：为为方便叙述，不妨方便叙述，不妨设设：即函数曲即函数曲线线y y= =f f( (x x) )单调单调增加、上凹。此增加、上凹。此时时，因取初，因取初值值x x0 0使使 则则由由得：得：从而有：从而有：33计算机数值方法第3章故知 x1x0。同理可证： xkxk-1x1x0。这表明迭代序列xk单调减小而且有下界 ，即收敛于所求根 。 例例例例 用牛用牛顿顿迭代法求迭代法求x x3 3+2+2x x2 2+10+10x x-20=0-20=0在在x x=1=1附近的根，附近的根，计计算算结结果果误误差小于差小于1010-5-5。解解解解：令
28、令f f( (x x)= )= x x3 3+2+2x x2 2+10+10x x-20-20，考考虑虑区区间间00，22上上f f(0)(0)f f(2)0(2)0+100，f”f”( (x x)=6)=6x x+40+40，可可知知f f( (x x)=0)=0在在00，22上有唯一的根，按牛上有唯一的根，按牛顿顿迭代法构造迭代式：迭代法构造迭代式：34计算机数值方法第3章取初值x0=2时显然有f(x0)f”(x0)0，故牛顿迭代收敛。 例例例例 用牛用牛顿顿迭代法求迭代法求 解解解解： 令令则则方程方程f f( (x x)=)=x x2 2-3=0-3=0的根即的根即为为所求，取含根区所
29、求，取含根区间间1 , 21 , 2时时有有所以方程有唯一的根。构造牛所以方程有唯一的根。构造牛顿顿迭代格式：迭代格式：取初取初值值x x0 0=2=2，显显然有然有故迭代数列收故迭代数列收敛敛于函数方程的根。于函数方程的根。35计算机数值方法第3章牛顿迭代法为平方收敛（收敛阶为2）。证明：由f(x)在xk处的泰勒展开式将将x x= =x x* *代入上式，并由代入上式，并由f f( (x x* *)=0)=0可得：可得：故有：故有：因而：因而：所以由收所以由收敛阶敛阶的定的定义义可知，可知，牛牛牛牛顿顿迭代法具有迭代法具有迭代法具有迭代法具有2 2阶阶收收收收敛敛。36计算机数值方法第3章弦
30、截法又称割线法。如下图所示，函数方程f(x)=0有根为 ，为求出 ：弦弦弦弦 截截截截 法法法法y y= =f f( (x x) )x x1 1x x0 0x x2 2x x3 3x x4 4 37计算机数值方法第3章（1）过点(x0,y0)和点(x1,y1)作曲线y=f(x)的割线，该割线与x轴交于x2；该割线的点斜式方程为令令y y=0=0，得，得该该割割线线与与x x轴轴的交点的交点x x2 2 : :（2 2）过过点点( (x x0 0, ,y y0 0) )和和( (x x2 2, ,y y2 2) )再作割再作割线则线则与与x x轴轴交于交于x x3 3，可得：，可得：如此如此继续
31、继续下去，即构成了迭代格式：下去，即构成了迭代格式：38计算机数值方法第3章每次所作割线与x轴的交点将逐步逼近所求根 。此种弦割法称为单点弦割法。双点弦截法：双点弦截法：双点弦截法：双点弦截法：如下如下图图所示，所示，过过点点( (x x0 0, ,y y0 0) )和点和点( (x x1 1, ,y y1 1) )作曲作曲线线y y= =f f( (x x) )的割的割线线，该该割割线线与与x x轴轴交于交于x x2 2；过过点点( (x x1 1, ,y y1 1) )和和( (x x2 2, ,y y2 2) )再作再作割割线则线则与与x x轴轴交于交于x x3 3，。o oy y= =
32、f f( (x x) )x xy yx x1 1x x0 0x x2 2x x3 3x x4 4双点弦截法迭代格式双点弦截法迭代格式双点弦截法迭代格式双点弦截法迭代格式为为：39计算机数值方法第3章一）数据说明：（1）精度控制量EPS，最大迭代次数MAXREPT；（2）迭代初值x0，x1；（3）x_k0、x_k1、x_k2，用于进行迭代计算；（4）自定义函数f(x)二）操作说明：step1输入迭代初值x0和x1；step2x_k0=x0 ; x_k1=x1 ; x_k2 ; k=0 ; p=1.0;step3While pEPS And k=MAXREPT Dostep4x_k2=x_k1-f
33、(x_k1)*(x_k1-x_k0)/(f(x_k1)-f(x_k0);step5p= fabs(x_k2-x_k1);step6x_k0=x_k1 ; x_k1=x_k2;step7k=k+1;step8输出x_k2即为所求根。40计算机数值方法第3章一、问题描述一、问题描述以二阶非线性方程组为例：非非非非 线线线线 性性性性 方方方方 程程程程 组组组组 求求求求 解解解解其中至少有一个方程其中至少有一个方程为为非非线线性方程，求其性方程，求其根根根根，即即一一组组数据数据( (x x* * , , y y* *) )二、基本思想（牛顿迭代法）二、基本思想（牛顿迭代法）二、基本思想（牛顿迭
34、代法）二、基本思想（牛顿迭代法）将非将非线线性方程性方程组组作向量化作向量化处处理，即理，即：令令，则则原方程原方程组为组为所求所求根根根根即即：，使，使41计算机数值方法第3章如此如此则则可用迭代法求根，即用可用迭代法求根，即用u u0 0, ,u u1 1,u uk k, ,u uk k+1+1序列逐次逼近根序列逐次逼近根u u* *。三、构造方法三、构造方法三、构造方法三、构造方法将将f f1 1( (x x , , y y), ),f f2 2( (x x , , y y) )在在( (x xk k , , y yk k) )处处作泰勒展开，并取作泰勒展开，并取其其线线性部分，得到方程性部分，得到方程组组：令令，则则有有42计算机数值方法第3章将u=uk+1代入上式得牛顿迭代格式：，即，即令令，得，得上式左右两上式左右两边边同乘同乘，得，得从初从初值值u u0 0开始，逐次开始，逐次计计算算，及，及，直到，直到43计算机数值方法第3章取初值四、实例四、实例四、实例四、实例求解非求解非线线性方程性方程组组：解：解：44计算机数值方法第3章由按此种方法按此种方法继续继续做下去，直到做下去，直到45计算机数值方法第3章
