《解非线性方程优秀课件.ppt》由会员分享，可在线阅读，更多相关《解非线性方程优秀课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、解非线性方程第1页，本讲稿共38页本章目的本章目的：讲述用于实际计算中求 f(x)=0 的根的近似值的几种常用方法。方程根的数值计算大致可以分为三个步骤三个步骤：(1)判断根的存在性；(2)确定根的分布范围(根的隔离)；(3)根的精确化。根的隔离根的隔离1.分析法：分析法：利用对函数 f(x)的各种性质的分析来确定根的分布范围。例例：试确定f(x)=x3-6x2+9x-1=0各根的分布范围。隔根区间为(0,1)、(1,3)、(3,4)第2页，本讲稿共38页2.逐步搜索法：逐步搜索法：先确定方程先确定方程 f(x)=0的所有实根所在的区间的所有实根所在的区间a,b，再按照，再按照选定的步长选定的
2、步长 h=(b a)/n，取点，取点 xk=a+k h(k=0,1,2,.,n)，逐步计算函数值逐步计算函数值 f(xk),依据函数值异号及实根的个数确定隔根依据函数值异号及实根的个数确定隔根区间区间.必要时可以调整步长必要时可以调整步长 h,总可以把隔根区间全部找出总可以把隔根区间全部找出.代数方程根的代数方程根的模上下界定理模上下界定理：定理定理：设代数方程设代数方程 f(x)=xm+am-1xm-1+a1x+a0=0则则:(1)若若=max|am-1|,|a1|,|a0|,方程根的模小于方程根的模小于+1；(2)若若 v=1/|a0|max1,|am-1|,|a1|,方程根的模大于方程根
3、的模大于1/(v+1).例例：求方程求方程 x3-3.2 x2+1.9 x+0.8=0 的隔根区间。的隔根区间。解解：设方程的根为设方程的根为 由由 =max|-3.2|,|1.9|,|0.8|=3.2;v=(1/0.8)max1,|-3.2|,|1.9|=4 第3页，本讲稿共38页得：得：0.2|4.2 即：即：-4.2 -0.2 ,0.2 4.2取取 n=8,h=0.5,计算计算 f(xk)xk-0.7-0.20.21.21.72.2 f(xk)-2.440.281.060.20-0.31 0.14由上表可知隔根区间为由上表可知隔根区间为-0.7,-0.2,1.2,1.7,1.7,2.23
4、.图解法：图解法：由函数图像来确定根的大体位置。由函数图像来确定根的大体位置。第4页，本讲稿共38页4.1 二分法二分法(对分区间法对分区间法)(Bisection Method)原理：原理：若若 f(x)Ca,b单调，且单调，且 f(a)f(b)0，则则 f(x)在在(a,b)上有且仅有一实根。上有且仅有一实根。基本思想：基本思想：通过计算隔根区间的中点，逐步将隔根区间通过计算隔根区间的中点，逐步将隔根区间缩小，从而得到方程的近似根数列缩小，从而得到方程的近似根数列 xn。第5页，本讲稿共38页abx1x2a1b2x*b1a2(1)(1)先将先将 a,b 等分为两个小区间等分为两个小区间,分
5、点记为分点记为x0=(=(a+b)/)/2,判断判断根属于哪个小区间根属于哪个小区间,舍去无根区间保留有根区间舍去无根区间保留有根区间 a 1,b1.即即,若若 f(x0)=0,则则x0=x*.设设 f(x0)0,若若 f(a)f(x0)0,则则x*(a,x0),这时令这时令a1=a,b1=x0;否则否则,x*(x0,b),此时令此时令a1=x0,b1=b.总之总之,可以得到可以得到x*所在的新区间所在的新区间a1,b1,其长度为其长度为a,b的一半的一半.二分法的步骤：二分法的步骤：(2)对区间对区间a1,b1 实施上述同样的过程实施上述同样的过程,得中点得中点 x1=(a1+b1)/2 和
6、和x*的新区间的新区间a2,b2,如此继续下去如此继续下去,则得一系列有根区间则得一系列有根区间:(3)a0,b0=a,b,a1,b1,a2,b2,.,ak,bk,第6页，本讲稿共38页其中其中 bk-ak=(bk-1-ak-1)/2 .因此因此 bk-ak=(b-a)/2k ,当当k+时时,有根区间有根区间ak,bk 最最终必收敛于一点终必收敛于一点,该点就是所求方程的根该点就是所求方程的根x*.把每次二分后的有根区间把每次二分后的有根区间ak,bk 的中点的中点xk=(ak+bk)/2作为作为根根x*的近似值的近似值,则可得一个根的近似值序列则可得一个根的近似值序列 x0,x1,x2,.,
7、xk,.该序列的极限即为该序列的极限即为x*.定理定理1.设设x*是是 f(x)=0在在a,b内的唯一根内的唯一根,且且 f(a)f(b)0,则则二分法计算过程中二分法计算过程中,各隔根区间的中点数列各隔根区间的中点数列 满足满足:|xn x*|(b a)/2n+1第7页，本讲稿共38页误差误差 分析：分析：第第1步产生的步产生的有误差有误差第第 k+1 步产生的步产生的 xk 有误差有误差(1)对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：停机条件停机条件（termination condition）或误差控制方法：）或误差控制方法：(2)事后估计误差事后
8、估计误差.先对分先对分,再判断所得中点是否满足再判断所得中点是否满足(3)用不等式用不等式 控制误差。控制误差。第8页，本讲稿共38页 例例例例1 1 用二分法求用二分法求 在在(1,2)内的根，要求绝对内的根，要求绝对 误差不超过误差不超过 解解解解：f(1)=-50 -(1,2)+f(1.5)0 (1,1.5)f(1.25)0 (1.25,1.375)f(1.313)0 (1.313,1.375)f(1.344)0 (1.344,1.375)f(1.360)0 (1.360,1.368)第9页，本讲稿共38页例例2:求方程求方程 f(x)=x 3 e-x=0的一个实根。的一个实根。解：解：
9、因为因为 f(0)0.故故 f(x)在在(0,1)内有根内有根.(a,b)=(0,1),计算结果如表：计算结果如表：ka bk xk f(xk)符号符号 00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取取x10=0.7729，误差为误差为|x*-x10|1/211.第10页，本讲稿共38页Remark1：求奇数个
10、根：求奇数个根 Find solutions to the equation x3-6x2+10 x 4=0on the intervals 0,4，Use the bisection method to compute a solution with an accuracy of 107.Determine the number of iterations to use.0,1,1.5,2.5 and 3,4，利用前面的公式可计算利用前面的公式可计算迭代次数为迭代次数为k=23.第11页，本讲稿共38页Remark2:要区别根与奇异点要区别根与奇异点Consider f(x)=tan x o
11、n the interval(0,3).Use the 20 iterations of the bisection method and see what happens.Explain the results that you obtained.（如右图）Remark3:二分法不能用来求重二分法不能用来求重根根,且收敛速度较慢且收敛速度较慢.优点优点:对函数的性质要求低对函数的性质要求低,程程序简单序简单,易操作易操作.第12页，本讲稿共38页4.2 简单迭代法简单迭代法基本思想：基本思想：先将方程先将方程f(x)=0改写成某种等价形式改写成某种等价形式,由等由等价形式构造相应的迭代公式价
12、形式构造相应的迭代公式,然后选取方程的某个然后选取方程的某个初始近似根初始近似根 x0,代入迭代公式反复校正根的近似值代入迭代公式反复校正根的近似值,直到满足精度要求为止直到满足精度要求为止.具体做法：具体做法：(1)(1)把把 f(x)=0 0 改写成下列等价形式改写成下列等价形式f(x)=0 x=(x)等价变换等价变换f(x)的根的根 (x)的不动点的不动点第13页，本讲稿共38页(2)(2)构造迭代格式：构造迭代格式：,k=0,1,2,=0,1,2,(3)(3)从给定的初始值从给定的初始值x0 0出发出发,按照迭代公式即可得一个按照迭代公式即可得一个数列数列 x0,x1,x2,xk,(4
13、)(4)若有极限若有极限,则迭代公式收敛则迭代公式收敛,此时数列极限即为此时数列极限即为原方程的根原方程的根,即即这里这里 (x)称为迭代函数称为迭代函数注：注：f(x)=0 化为等价方程化为等价方程 x=(x)的方式是不唯一的的方式是不唯一的,故迭代格式也故迭代格式也不唯一不唯一,有的收敛有的收敛,有的发散有的发散.第14页，本讲稿共38页(1)(1)(1)(1)如果将原方程化为等价方程如果将原方程化为等价方程由此可见，这种迭代格式是发散的由此可见，这种迭代格式是发散的 取初值取初值For example：2x3 x 1=0(2)(2)(2)(2)如果将原方程化为等价方程如果将原方程化为等价
14、方程仍取初值仍取初值第15页，本讲稿共38页依此类推依此类推,得得 x3=0.9940 x4=0.9990 x5=0.9998 x6=1.0000 x7=1.0000已经收敛已经收敛,故原方程的解为故原方程的解为 x=1.0000 同样的方程同样的方程 不同的迭代格式不同的迭代格式 有不同的结果有不同的结果什么形式的迭代什么形式的迭代法能够收敛呢法能够收敛呢?收敛性分析收敛性分析定义定义:若存在常数若存在常数 (0 1),使得对一切使得对一切 x1,x2 a,b,成立不成立不等式等式|g(x1)-g(x2)|x1 -x2|则称则称 g(x)是是a,b上的一个压缩映射上的一个压缩映射,称为压缩系
15、数称为压缩系数第16页，本讲稿共38页 考虑方程考虑方程 x=(x),(x)Ca,b,若若(I)当当 x a,b 时，时，(x)a,b；(II)在在a,b上成立不等式上成立不等式:|(x1)-(x2)|x1-x2|,(0 1)则则(1)(x)在在a,b上存在惟一不动点上存在惟一不动点 x*(2)任取任取 x0 a,b，由，由 xk+1=(xk)得到的序列得到的序列 xk(a,b)收敛于收敛于x*。(3)k 次迭代所得到的近似不动点次迭代所得到的近似不动点 xk 与精确不动点与精确不动点 x*有误差估计式：有误差估计式：定理定理4.2第17页，本讲稿共38页证明：证明：(x)在在a,b上存在不动
16、点？上存在不动点？不动点唯一？不动点唯一？当当k 时，时，xk 收敛到收敛到 x*？|x*-x|=|(x*)-(x)|x*-x|.因因0 1,故必有故必有 x=x*若有若有x a,b,满足满足 (x)=)=x，则则|xk-x*|=|(xk-1)-(x*)|xk-1-x*|2|xk-2-x*|k|x0-x*|0.令令G(x)=(x)-x,x a,b，由条件知由条件知G(a)=(a)-a0,G(b)=(b)-b0.由条件知由条件知G(x)在在a,b上连续，又由介值上连续，又由介值定理知存在定理知存在 x*a,b，使使G(x*)=0，即即x*=(x*).第18页，本讲稿共38页 可用可用 来控制收敛
17、精度来控制收敛精度 越小越小,收敛越快收敛越快(4)|xk-x*|=|(xk-1)-(x*)|xk-1-x*|(|xk-xk-1|+|xk-x*|),故有故有|xk-x*|/(1-)|xk-xk-1|.这就证明了第一个估计式这就证明了第一个估计式.(5)|xk-xk-1|=|(xk-1)-(xk-2)|xk-1-xk-2|k-1|x1-x0|结合上一估计式可得结合上一估计式可得|xk-x*|k-1/(1-)|x1-x0|.即第二个估计式成立即第二个估计式成立第19页，本讲稿共38页RemarkRemark：定理条件非必要条件，而且定理定理条件非必要条件，而且定理4.24.2中的压缩中的压缩条件
18、不好验证，一般来讲条件不好验证，一般来讲 若知道迭代函数若知道迭代函数 (x)C1a,b,并且满足并且满足|(x)|1,对任意的对任意的 x a,b,则则 (x)是是a,b上的压缩映射上的压缩映射.第20页，本讲稿共38页例例3:已知方程已知方程 2x 7-lgx0，求方程的含根区间，考查用，求方程的含根区间，考查用迭代法解此方程的收敛性。迭代法解此方程的收敛性。第21页，本讲稿共38页解：解：在这里我们考查在区间在这里我们考查在区间3.5,4的迭代法的收敛性的迭代法的收敛性很容易验证：很容易验证：f(3.5)0将方程变形成等价形式：将方程变形成等价形式：x(lg x+7)/2由定理由定理4.
19、2知，迭代格式知，迭代格式 xk+1(lg xk+7)/2在在3.5,4内收敛内收敛.第22页，本讲稿共38页局部收敛局部收敛Def:(局部收敛局部收敛)设设x*为为 的不动点的不动点,若存在若存在x*的一个闭邻域的一个闭邻域U(x*,)=x*-,x*+(0),使得对任意使得对任意x0 U(x*,),由迭代格式由迭代格式 xk+1=(xk)(k=0,1,2,)产生的序列产生的序列 xk 都收敛于都收敛于x*,则称迭代则称迭代过程过程 xk+1=(xk)在的闭邻域在的闭邻域U(x*,)内是内是局部收敛局部收敛的的.定理定理4.3:设设x*为为 的不动点的不动点,(x)与与 (x)在包含在包含x*
20、的某邻域的某邻域U(x*)(即开区间即开区间)内连续内连续,且且|(x*)|L 1,则迭代格式则迭代格式 xk+1=(xk)(k=0,1,2,)具有局部收敛性具有局部收敛性.证明略证明略We dont know x*,how do we estimate the inequality？第23页，本讲稿共38页例例4:用一般迭代法求用一般迭代法求x3-x-1=0 的正实根的正实根x*解解:将方程改写成将方程改写成则迭代函数为则迭代函数为易知易知:(x)在包含在包含x*的某邻域的某邻域U(x*)内连续内连续,且且|(x*)|1.因此迭代格式因此迭代格式 在在x*附近收附近收敛敛.例例5:用一般迭代
21、法求方程用一般迭代法求方程 x ln x2 在区间在区间(2,)内的内的根根,要求要求|xk-xk-1|/|xk|10-8第24页，本讲稿共38页解：解：令令 f(x)=x-ln x-2 f(2)0,故方程在故方程在(2,4)内至少有一个根内至少有一个根 因此方程在因此方程在(2,)内仅有一个根内仅有一个根 x*,且且 x*(2,4)将方程化为等价方程：将方程化为等价方程：x2ln x因此因此,x0(2,),xk+12lnxk 产生的序列产生的序列 xk 收敛于收敛于x*取初值取初值x03.0,计算结果如下：计算结果如下：第25页，本讲稿共38页k xi8 3.1461774529 3.146
22、18820910 3.14619162811 3.14619271412 3.14619306013 3.14619316914 3.146193204 k xi 0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 3.146037143 7 3.146143611第26页，本讲稿共38页另一种迭代格式另一种迭代格式：0 3.000000000 1 3.147918433 2 3.146193441 3 3.146193221注：注：由此可见由此可见,对同一个非线性方程的迭代
23、格式对同一个非线性方程的迭代格式,在在 收敛的情形下收敛的情形下,有的收敛快有的收敛快,有的收敛慢有的收敛慢.第27页，本讲稿共38页 Def:设序列设序列 xk 收敛于收敛于x*,记记ek=xk-x*,若存在若存在 p1和正数和正数C，使得成立使得成立则称则称 xk 为为 p 阶收敛的阶收敛的.特别地特别地 p=1,且且0C 1,称超线性收敛称超线性收敛;p=2,称平方收敛称平方收敛.迭代法的收敛阶迭代法的收敛阶(收敛速度收敛速度)注：注：收敛阶收敛阶 p 反映了迭代格式收敛的反映了迭代格式收敛的快慢快慢,p 越大收敛越大收敛越快越快.第28页，本讲稿共38页定理定理4.4:设设x*为为 的
24、不动点的不动点,p1为正整数为正整数,在在x*的某邻的某邻域域(x*)内内p 阶连续可微阶连续可微,且且 (x*)=(x*)=(p-1)(x*)=0,而而 (p)(x*)0则存在则存在 0,当当x0 x*-,x*+(x0 x*)时时,由迭代格式产由迭代格式产生的序列生的序列 xk 以以 p 阶收敛速度收敛于阶收敛速度收敛于x*.Prove:(1)由由 (x*)=0必存在必存在 0,当当x0 x*-,x*+U(x*)时时,由迭代格由迭代格式产生的序列式产生的序列 xk 收敛于收敛于x*,并有并有xk x*-,x*+由泰勒公式有由泰勒公式有第29页，本讲稿共38页由条件知由条件知(2)由于由于 在
25、在x*处处 p 阶连续可微且阶连续可微且 (p)(x*)0,知必存在知必存在x*的某邻域的某邻域(x*),当当x U(x*)时时,有有 (p)(x)0.由于由于 x*-,x*+U(x*),故故 (p)()0,k=0,1,2,可见可见,当初值当初值x0 x*时时,xkx*.于是有于是有即即 xk 有有p 阶收敛速度阶收敛速度.第30页，本讲稿共38页4.3 迭代过程的加速迭代过程的加速加速迭代的收敛方法主要用于线性收敛的迭代格式加速迭代的收敛方法主要用于线性收敛的迭代格式一、松弛迭代一、松弛迭代设设 xk 是根是根 x*的某个近似值的某个近似值,用迭代公式校正一次用迭代公式校正一次,得得假设假设
26、 在所考察的范围内改变不大在所考察的范围内改变不大,设其估计值设其估计值为为L,则有则有由此解得：由此解得：记：记：第31页，本讲稿共38页则得加速迭代公式：则得加速迭代公式：或或若记若记则则 称为松弛因子称为松弛因子,故这种方法也称为松弛迭代法故这种方法也称为松弛迭代法,从从理论上讲理论上讲,取取 最有效最有效;实际应用时常取实际应用时常取 近似代替近似代替 .第32页，本讲稿共38页一、一、Aitken迭代迭代将迭代值将迭代值 再迭代一次再迭代一次,得得 由于由于 联立消去联立消去L,得得 解得：解得：这样就得到这样就得到Atiken加速迭代公式：加速迭代公式：第33页，本讲稿共38页或或
27、 注：注：Aitken加速迭代对线性收敛迭代格式的加速效果是非加速迭代对线性收敛迭代格式的加速效果是非常明显的常明显的.定理定理4.5:设设 的迭代函数的迭代函数 在其不动点在其不动点 x*的某邻域的某邻域 内有二阶连续导内有二阶连续导数数,且且 ,则则Atiken加速迭代二阶收敛加速迭代二阶收敛.第34页，本讲稿共38页Prove：Aitken迭代函数为：迭代函数为：(1)：先证先证 与与 有相同的不动点有相同的不动点 10 若若 ,则则20 若若 ,则则(2)：再证二阶收敛再证二阶收敛第35页，本讲稿共38页所以所以于是于是故有故有所以所以Aitken迭代二阶收敛迭代二阶收敛.第36页，本讲稿共38页定理定理4.6:如果由迭代公式如果由迭代公式 产生的产生的数列数列 满足满足 (1)收敛于收敛于x*(2)则由上述则由上述Aitken加速迭代公式产生的数列加速迭代公式产生的数列 比比 较快地收敛于根较快地收敛于根 x*,即即第37页，本讲稿共38页例例6：用用Aitken加速迭代公式求方程加速迭代公式求方程 的根的根.解：解：Aitken加速迭代公式为加速迭代公式为取初始值取初始值 ,代入计算代入计算可得可得第38页，本讲稿共38页