差分与求根问题课件.ppt

1、12023-2-5 问题1：建模时碰到导数模型怎么办？)1()(),(:00yxybxayxfdxdy其一般形式为其一般形式为前提条件：前提条件：:.),(),(:,),(方程的理论知方程的理论知为常数。这样由常微分为常数。这样由常微分）条件）条件满足李普希兹（满足李普希兹（且关于且关于连续连续函数函数LyyLyxfyxfLipschitzyyxf.)(存在且唯一存在且唯一的解的解xy)1(初值问题初值问题22023-2-5，取为常数取为常数通常将步长通常将步长称为步长。称为步长。相邻两个节点的间距相邻两个节点的间距的近似值的近似值上的值上的值在一系列离散节点在一系列离散节点解解法，即寻求问题

2、的法，即寻求问题的所谓初值问题的数值解所谓初值问题的数值解hhxxhNnyxybxxxxxaxynnnnnnNn ),1,0()()(1210初值问题数值解的提法初值问题数值解的提法.2,1,0 ,0nnhxxn32023-2-5对微分方程进行数值求解对微分方程进行数值求解,首先要将微分方程离散化首先要将微分方程离散化.一般采用以下几种方法一般采用以下几种方法:(1)(1)用差商近似导数用差商近似导数)(,)(:11nnnnxyyxyy令令进一步进一步hyydxdynn1nnnnnnxxxyxyxyxfyxdxdynn11),()(,42023-2-5(2)(2)用数值积分近似积分用数值积分近

3、似积分1)(,()()(1nnxxnndxxyxfxyxy即即)(,)(:11nnnnxyyxyy令令进一步进一步11),()(,(nnxxnnnnyyyxhfdxxyxf实际上是矩形法实际上是矩形法宽宽高高),1,0(),(11ndxyxfdxdxdynnnnxxxx52023-2-5(3)用用Taylor多项式近似并可估计误差多项式近似并可估计误差)(!2)()()(!2)()()()(221nnnnnnnxyhxhyxyyhxhyxyhxyxy)(,)(:11nnnnxyyxyy令令进一步进一步),(1nnnnyxhfyy)(max2)(211xyhyxybxann Taylor展开方法

4、的处理手续繁琐，演绎过程冗长展开方法的处理手续繁琐，演绎过程冗长繁杂。所以，现实中应用较少。繁杂。所以，现实中应用较少。62023-2-5u差分方法u目标：将寻求微分方程的解目标：将寻求微分方程的解y(x)的分析问题转化的分析问题转化为计算离散值为计算离散值yn的代数问题的代数问题u差分：差分：相邻函数值之差相邻函数值之差u采用差分格式（步进方式），求解过程随着节采用差分格式（步进方式），求解过程随着节点排列的次序一步一步向前推进，即利用点排列的次序一步一步向前推进，即利用yn,yn-1,yn-2,计算计算yn+1的递推公式的递推公式u由于计算模型仅含一个变元由于计算模型仅含一个变元yn+1，

5、问题规模减小，问题规模减小72023-2-5v两类差分格式 单步法：单步法：直接利用上一步的信息直接利用上一步的信息yn设计某设计某种嵌套结构来提高差分格式的精度，如种嵌套结构来提高差分格式的精度，如Runge-Kutta方法方法 线性多步法线性多步法：利用前面多步的老信息：利用前面多步的老信息yn,yn-1,yn-2,通过线性组合生成高精度的差通过线性组合生成高精度的差分格式分格式82023-2-5用差商近似区间左端点的导数用差商近似区间左端点的导数hxyxyxynnn)()()(1问题转化为问题转化为,.)3,2,1,0()(),(001nxyyyxhfyynnnnEuler格式格式1.1

6、.Euler方法)(,)()()()(1nnnnnnxyxhfxyxyhxyxy)1()(),(00yxybxayxfy式为式为已知初值问题的一般形已知初值问题的一般形92023-2-51)0()10(2)1.0(yxyxyyh步长步长求解初值问题求解初值问题例例解解yxyyxf/2),(初值问题的迭代公式为初值问题的迭代公式为:1)0()/2(),(1yyxyhyyxhfyynnnnnnnnxy21:解的表达式解的表达式102023-2-5近似解精确解0 1.0.1 1.10.2 1.19180.3 1.27740.4 1.35820.5 1.43510.6 1.50900.7 1.5803

7、0.8 1.64980.9 1.71781.0 1.7848y0 -1y0.1-1.0954y0.2-1.1832y0.3-1.2649y0.4-1.3416y0.5-1.4142y0.6-1.4832y0.7-1.5492y0.8-1.6125y0.9-1.6733y1.0-1.7321112023-2-5 已知，必有切线方程。已知，必有切线方程。及及由于由于斜率斜率则则的切线（存在！）的切线（存在！）出发求解曲线出发求解曲线由由欧拉方法的几何解释：欧拉方法的几何解释：,|,000000),(0000yxyxfyxfdxdyxy yyxyx),()(|0000),(0000yxfxxydxd

8、yxxyyyx：由点斜式写出切线方程由点斜式写出切线方程122023-2-5）（：，可由切线算出，可由切线算出，则，则为为等步长等步长0001101,yxhfyyyhxxh 2 1 0 ,)(11，）（点的值：点的值：在在逐步计算出逐步计算出nyxhfyyxxyynnnnnY=y(x)ab1x2xEuler格式精度较低，仅为格式精度较低，仅为1阶！阶！注：注：这是这是“折线法折线法”而非而非“切切线法线法”，即除第一个点是曲线，即除第一个点是曲线切线外，其余点则不是！切线外，其余点则不是！132023-2-5hxyxyxynnn11 端点处的导数：端点处的导数：用向后差商近似区间右用向后差商近

9、似区间右00111,yxyyxhfyynnnn则得隐式则得隐式Euler格式：格式：隐式隐式Euler格式精度仍很低，还是格式精度仍很低，还是1阶！阶！142023-2-5hxyxyxynnn2 11端点处的导数：端点处的导数：用中心差商近似区间左用中心差商近似区间左0011,2 yxyyxhfyynnnn则得则得Euler两步格式：两步格式：Euler两步格式精度较前两种有所提高！两步格式精度较前两种有所提高！但：需借助于某种一步法另提供一个开始值但：需借助于某种一步法另提供一个开始值y1。152023-2-5对上面第一个方程的两端从对上面第一个方程的两端从xn到到xn+1进行积分进行积分:

10、)(,)(,()()(11nnxxnnxyxhfdxxyxfxyxynn),(),(2111nnnnnnyxfyxfhyy是显式是显式Euler格式与隐式格式与隐式Euler格式的算术平均，比格式的算术平均，比Euler精度高一些（精度高一些（2阶），但计算量较大阶），但计算量较大梯形格式梯形格式)1()(),(00bxayxyyxfy式为：式为：已知初值问题的一般形已知初值问题的一般形)(,)(,2)(,()()(1111nnnnxxnnxyxfxyxfhdxxyxfxyxynn162023-2-5 ,2,2 1 01111nnnnnnnnnnyxfyxfhyyyxhfyyn，对对实际计算中

11、只迭代一次，这样建立的预报校正系统称作实际计算中只迭代一次，这样建立的预报校正系统称作改进的欧拉公式改进的欧拉公式。改进的改进的Euler方法方法将梯形格式与显式将梯形格式与显式Euler格式结合，形成格式结合，形成预报校正系统预报校正系统：预报值预报值001121211)(),(),()(2:yxyhKyxfKyxfKKKhyynnnnnn作等价变换作等价变换校正值校正值172023-2-5例例解yxyyxf/2),(1)0()10(2)1.0(yxyxyyh步长步长求解初值问题求解初值问题xy21:解的表达式解的表达式001121211)(),(),()(2:yxyhKyxfKyxfKKK

12、hyynnnnnn作等价变换作等价变换182023-2-5Euler近似解精确解0 1.0.1 1.09590.2 1.18410.3 1.26620.4 1.34340.5 1.41640.6 1.48600.7 1.55250.8 1.61650.9 1.67821.0 1.7379改进Euler近似解0 1.0.1 1.10.2 1.19180.3 1.27740.4 1.35820.5 1.43510.6 1.50900.7 1.58030.8 1.64980.9 1.71781.0 1.7848y0 -1y0.1-1.0954y0.2-1.1832y0.3-1.2649y0.4-1.

13、3416y0.5-1.4142y0.6-1.4832y0.7-1.5492y0.8-1.6125y0.9-1.6733y1.0-1.7321192023-2-5Euler方法的收敛性和精度分析方法的收敛性和精度分析v Euler显式、隐式格式与改进的显式、隐式格式与改进的Euler格式是收敛的格式是收敛的v 称称某个差分格式具有某个差分格式具有m阶精度阶精度，如果其对应的近似，如果其对应的近似关系式对于次数关系式对于次数m的多项式均能准确成立，而对的多项式均能准确成立，而对于于y=xm+1不准确不准确 显式Euler格式：1阶 隐式Euler格式：1阶 梯形格式：2阶202023-2-52.龙

14、格-库塔(Runge-Kutta)方法理论上理论上,公式阶数越高，精确度越高，但计算量过大公式阶数越高，精确度越高，但计算量过大观察观察),(Euler111nnnnyxfKhKyy格式：格式：),(),()(2Euler121211hKyhxfKyxfKKKhyynnnnnn格式：格式：改进的改进的只要对平均斜率提供一种算法，便可由上式导出一种只要对平均斜率提供一种算法，便可由上式导出一种计算格式计算格式)(,)()(1yhfxyxynn平均斜率平均斜率212023-2-5共同的特点是共同的特点是:1 ),(nyyxf合来计算合来计算在某点上的值的线性组在某点上的值的线性组用用的偏导数，提高

15、了精度的偏导数，提高了精度避免计算函数避免计算函数),(yxf),(),(11111ijjijnininnriiinnKhyhpxfKyxfKKhyy方法方法方法，简称方法，简称阶阶上式称为上式称为均为常数均为常数这里这里K-R Kutta-Runge.,rpijii,.,2ri 给我们的启示：给我们的启示：设法在设法在xn,xn+1上多预报几个点的斜率，上多预报几个点的斜率，对它们进行加权平均作为平均斜率对它们进行加权平均作为平均斜率222023-2-5111),(hKyyyxfKnnnn),(),()1(121211phKyxfKyxfKKKhyynpnnnnn21121212,),(hK

16、yyKhyxfKyxfKnnnnnnEuler中点中点格式格式),(),(21121211hKyxfKyxfKKKhyynnnnnn特例特例2：当当p=1/2,=1时时当当r2时，二阶时，二阶R-K格式格式当当r1时，一阶时，一阶R-K格式格式Euler格式格式改进的改进的Euler格式格式特例特例1：当当p=1,=1/2时时232023-2-5格式格式时，得到三阶的时，得到三阶的Kutta3r.)2(,2,462113121213211KKhyxfKKhyxfKyxfKKKKhyynnnnnnnn三阶三阶R-K方法方法.四阶经典四阶经典R-K格式格式.,2,2,226314221312121

17、43211hKyxfKKhyxfKKhyxfKyxfKKKKKhyynnnnnnnnnn242023-2-51)0()10(2)1.0(K-R43yxyxyyh步长步长公式求解初值问题公式求解初值问题阶阶阶、阶、利用利用例例解解yxyyxf/2),(.)2(,2,462113121213211KKhyxfKKhyxfKyxfKKKKhyynnnnnnnn.,2,2,22631422131212143211hKyxfKKhyxfKKhyxfKyxfKKKKKhyynnnnnnnnnn252023-2-5精确解y0 -1y0.1-1.09545y0.2-1.18322y0.3-1.26491y0.

18、4-1.34164y0.5-1.41421y0.6-1.483240 1.0.1 1.097740.2 1.187570.3 1.271290.4 1.350130.5 1.424990.6 1.49657改进Euler近似解0 1.0.1 1.095440.2 1.183220.3 1.264910.4 1.341650.5 1.414220.6 1.483263阶R-K近似解262023-2-5精确解y0-1y0.1-1.09545y0.2-1.18322y0.3-1.26491y0.4-1.34164y0.5-1.41421y0.6-1.483240 1.0.1 1.095440.2 1

19、.183220.3 1.264910.4 1.341650.5 1.414220.6 1.483263阶R-K近似解0.0 10.1 1.095450.2 1.183220.3 1.264910.4 1.341640.5 1.414220.6 1.483244阶R-K近似解272023-2-5.),1,0(),0()(01110为实数为实数其中系数其中系数多项式方程多项式方程niaaaxaxaxaxfinnnn 的求根问题的求根问题讨论单变量非线性方程讨论单变量非线性方程0)(xf问题：问题：重点研究重点研究的的求求根根问问题题 由于函数由于函数f(x)的复杂性，在绝大多数情况下没的复杂性，在

20、绝大多数情况下没有根的显式表达式。有根的显式表达式。出发点：出发点：数值方法求根的近数值方法求根的近似值似值282023-2-5.0)(,0)()()()(,)(.)(1)2(1)1(:.0)(),()()(*)(*)1(*xfxfxfxfxgmxfxmxfxmxmxmxgmxgxxxfmmm充分光滑，则充分光滑，则且且重零点重零点的的是是若若重零点重零点的的为为重根，或重根，或为为称称当当为单根，为单根，时，称时，称当当则则为正整数，且为正整数，且其中其中若若个个根根，本本章章不不涉涉及及复复根根有有次次方方程程在在复复数数域域有有且且只只nn的零点的零点称为函数称为函数则则若若)(,0*)

21、(*xfxxf 一般提法与结论一般提法与结论292023-2-5采用迭代法求根采用迭代法求根的多项式方程求根多可的多项式方程求根多可一样，通常对一样，通常对与一般连续函数方程与一般连续函数方程30)(nxf搜索法：搜索法：先求出使先求出使 的点，然后将这些点的点，然后将这些点放在放在定义域内，从而将定义域分成几部分，算出驻定义域内，从而将定义域分成几部分，算出驻点处的函数值，即可知道方程的有根区间。点处的函数值，即可知道方程的有根区间。0)(xf1.根的搜索302023-2-5。有且仅有一个单实根有且仅有一个单实根，则在，则在上连续且单调，上连续且单调，在在设设*,0)()(,)(xbabfa

22、fbaxf.,0 0 0(1)1010101000aaxbxfbbxaxfxxxf，令，令若若；，令，令若若；则根为则根为若若,)(1 ,)2(2211baba的的计计算算，并并产产生生区区间间重重复复对对根的二分搜索法根的二分搜索法根存在，但未必好求，可用二分法。不妨假设根存在，但未必好求，可用二分法。不妨假设f(a)0，取中点，取中点x0=(a+b)/2，312023-2-5，考察有根区间考察有根区间,ba.,.,2211kkbabababa可得出一系列有根区间可得出一系列有根区间如此反复二分下去，即如此反复二分下去，即.,*该点显然就是所求的根该点显然就是所求的根于一点于一点即这些区间最

23、终必收敛即这些区间最终必收敛xab21bab aa 1211ba x211221122,2ababababab 02/,时时当当的长度的长度，其中其中kkkkkkababba322023-2-5 kxx*则有则有,22*1kkkkababxx由于由于充充分分大大），只只要要二二分分足足够够多多次次（即即 k.为为预预定定的的精精度度这这里里 ab21bab aa 1211ba x332023-2-5对对分分区区间间次次数数的的估估计计：122*nnnnababxx由由12lnln)ln(abn不不难难得得出出：优点：对函数要求低，计算简单优点：对函数要求低，计算简单缺点：收敛慢且对有偶数重根的

24、情况不适合缺点：收敛慢且对有偶数重根的情况不适合二分法的特点：二分法的特点：342023-2-5 .2,5.1101)(3位位要求准确到小数点后第要求准确到小数点后第一个实根一个实根内的内的，在区间在区间求方程求方程 xxxf例例 解：解：0)(,0)(,5.1,0.1 bfafba，将将区区间间二二等等分分，则则中中点点25.10 x,5.125.1 0)(111010babbxaxf得新的有根区间得新的有根区间，令令如此二分下去即可。现估计二分次数如此二分下去即可。现估计二分次数64.5005.0*nxxn所以，二分所以，二分6次可达到要求。次可达到要求。352023-2-5基本思想基本思

25、想 构造不动点方程，以求得近似根。即由构造不动点方程，以求得近似根。即由方程方程f(x)=0变换为其等价形式变换为其等价形式x=(x)，然后建立，然后建立迭代格式迭代格式)(1kkxx )()lim()(limlim*1*xxxxxkkkkkk 当给定初值当给定初值x0后后,由迭代格式可求得数列由迭代格式可求得数列xk。此。此数列可能收敛，也可能不收敛。如果数列可能收敛，也可能不收敛。如果xk收敛于收敛于x*，则它就是方程的根。因为：则它就是方程的根。因为：可作为方程根的近似值可作为方程根的近似值充分大时，充分大时，故故kxk2.迭代法及其收敛性362023-2-5，使使隐隐式式方方程程显显式

26、式化化改改写写为为将将方方程程)(0)(xxxf 按上述方法构造迭代格式来求解方程的方法按上述方法构造迭代格式来求解方程的方法称为称为简单迭代法简单迭代法或或逐次迭代法逐次迭代法。称称为为迭迭代代函函数数)(x则则称称迭迭代代方方程程收收敛敛。1,0 )(1kxxkk按按公公式式反反复复迭迭代代*lim xxxkkk：若相应的序列若相应的序列372023-2-5求方程求方程01)(3 xxxf.5.1*0 xx附近的根附近的根在在将方程改写成下列形式将方程改写成下列形式 31xx据此建立迭代公式据此建立迭代公式,2,1,0131kxxkk例例 解:382023-2-5求方程求方程02010)(

27、3 xxxf要求精确到六位小数。要求精确到六位小数。附近的根附近的根在在,5.1*0 xx 将方程分别改写成下列形式将方程分别改写成下列形式 2011)1(3xxx据此建立迭代公式据此建立迭代公式,2,1,02011)1(31kxxxkkk例例解1020)2(2xx1020)2(21nnxx392023-2-5压压缩缩映映象象原原理理定理定理一致地成立一致地成立，使对，使对，存在常数存在常数压缩性条件：压缩性条件：）（；总有总有对任意对任意）封闭性条件：）封闭性条件：（,102,)(,1baxLLbaxbaxLx)(.*)(,)(01xxxbaxxxkk的根的根收敛于方程收敛于方程对于任给初值

28、对于任给初值则迭代过程则迭代过程，且且满满足足：上上具具有有连连续续的的一一阶阶导导数数在在设设,)(bax01*101*,)(,xxLLxxxxxbaxnnnn 并有并有且对任意的且对任意的 越越小小，收收敛敛的的越越快快L402023-2-5yxLyxLx)()()(只要证明：只要证明：,bayx显显然然提提示示yxLyxyx)()()(中中值值定定理理412023-2-5迭代法的局部收敛性迭代法的局部收敛性定义：定义：对于方程对于方程的某个邻域的某个邻域，若在，若在*)(xxx.),2,1,0)(:*10*附近是局部收敛的附近是局部收敛的在在式式均收敛，则称该迭代格均收敛，则称该迭代格迭

29、代格式迭代格式，对任意初值对任意初值为足够小的定数），使为足够小的定数），使（xkxxxxxkk的某个邻域的某个邻域在在数，数，的邻近有连续的一阶导的邻近有连续的一阶导的根的根在方程在方程设设*)()(xxxxx.)(1)()2(.)(1)()1(1*1*发散发散时，迭代格式时，迭代格式当当局部收敛局部收敛时，迭代格式时，迭代格式当当kkkkxxxxxx定理定理422023-2-5求方程求方程02010)(3xxxf要求精确到六位小数。要求精确到六位小数。附近的根附近的根在在,5.1*0 xx 将方程分别改写成下列形式。将方程分别改写成下列形式。)(2011)1(13xxxx例例解)(1020

30、)2(22xxx1113)()1(21xx1)10(40)(1020)2(2222xxxxx,所以迭代法发散所以迭代法发散.所以迭代法收敛所以迭代法收敛.21020)(12xx25.110 x432023-2-53/2131)1(31)(1)(xxxx，解：令解：令,21 3)(1)(2232中中，在区间在区间时，时，而当而当xxxx.所所以以迭迭代代法法发发散散求方程求方程01)(3 xxxf.5.1*0 xx附附近近的的根根在在 例例,1)41(31|)(|21 3/11 x中中，在在区区间间,23)(21313x又因又因.所所以以迭迭代代法法收收敛敛1|)(|2 x442023-2-5迭

31、代过程的收敛速度迭代过程的收敛速度收敛越快。收敛越快。性越显著，迭代过程性越显著，迭代过程的值越小，误差的压缩的值越小，误差的压缩性，且性，且收敛收敛时，迭代过程具有局部时，迭代过程具有局部当当从前面的定义，从前面的定义，)(1)(*xx性。性。过程至少具有平方收敛过程至少具有平方收敛，则称该迭代，则称该迭代收敛的；若收敛的；若则称该迭代过程是线性则称该迭代过程是线性，若，若迭代过程迭代过程对于具有局部收敛性的对于具有局部收敛性的0)(0)()(*1xxxxkk452023-2-5展开，有展开，有在点在点数数，将函，将函假定假定有近似根有近似根设已知方程设已知方程kkkxxfxfxxf)()0

32、)(0)()()()(kkkxxxfxfxf0)()(kkkxxxfxf令令，则则有有：记记校校正正值值为为1kx,1,0)()(1kxfxfxxkkkk3.Newton法.Newton）法法这这就就是是牛牛顿顿（462023-2-5 222)()()()()()()(1)(xfxfxfxfxfxfxfx 牛顿法对应的迭代方程为牛顿法对应的迭代方程为 ，故其迭代故其迭代函数为函数为 )()()(xfxfxx )()(xfxfxx )0)(xf邻近为平方收敛。邻近为平方收敛。的单根的单根法在法在定理：定理：*0)(Newtonxxf0)(*xf 假设假设 x*是方程是方程 f(x)=0的单根，即

33、的单根，即 f(x*)=0,则则 0)(*x472023-2-5.01xxe用牛顿法解方程用牛顿法解方程例例xxexxfxexf)1()(1)(，)1,0(0)(,0)(1,0,01)1(,01)0(*xxfxfxeff有唯一根有唯一根，且且5.00 x取取5.0)()(01xxfxfxxkkkk用牛顿迭代格式：用牛顿迭代格式：解迭代解迭代解1.0.571021.0.571022.0.5671562.0.5671563.0.5671433.0.5671434.0.5671434.0.5671435.0.5671435.0.5671436.0.5671436.0.5671437.0.5671437.0.5671438.0.5671438.0.567143精确解精确解 x-0.567143 482023-2-5牛顿法的特点牛顿法的特点优点优点:收敛快，逻辑结构简单收敛快，逻辑结构简单!缺点缺点:附近才能保证收敛附近才能保证收敛只在根只在根初始近似初始近似发生中断发生中断，程序常，程序常和和每一步都要计算每一步都要计算*0)2()()()1(xxxfxfkk若初值选的不恰当，迭代法从一个根跳到另一个根若初值选的不恰当，迭代法从一个根跳到另一个根的情形的情形,即会导致迭代发散。即会导致迭代发散。