计算方法上机实验指导

计算方法上机实验指导一、非线性方程求解（一）问题的指出二分法1方法概要假定 f ( x) 在 a, b 上连续， f (a) f (b)0 且 f (x) 在 (a,b) 内仅有一实根x* 取区间中点c ，若 f (c)0，则 c 恰为其根，否则，根据f (a) f (c)0 是否成立，可判断出根所属的新的有根子区间 ( a, c) 或 (c, b) ，为节省内存，仍称其为 (a, b) 。运算重复进行， 直到满足精度要求为止，即 | c x* | b a 。式中 a, b 为新的有根子区间的端点。2计算框图开始定义 f ( x) ，读入 a,b, cc( ab) / 2是否f (a) f (c)0acbc否ba是输出 a,b 及 (ab) / 2结束Nowton 迭代法1方法概要x0 为初始猜测，则由递推关系xk 1xkf ( xk )f ( xk )产生逼近解 x* 的迭代序列 xk ，这个递推公式就是Newton 法。当 x0 距 x* 较近时， xk 很快收敛于 x* 。但当 x0 选择不当时，会导致 xk 发散。故我们事先规定迭代的最多次数。若超过这个次数，还不收敛，则停止迭代另选初值。2计算框图开始定义 f ( x)输入 x 0 ,1 ,2 , Nk1是f (x0 )1否x1x0f ( x0 )f( x0 )| x1x0 |x0x1否kk 1k N是2否是输出迭代输出 x1输出奇失败标志异标志结束（二）目的掌握二分法与牛顿法的基本原理及应用（三）要求1用二分法计算方程sin xx202在 (1, 2) 内的根的近似值2用二分法计算方程x3x10在 (1, 1.5) 内的根的近似值(0.5 10 5 ) 。3用牛顿法求下列非线性方程的近似根。xex10x00.5x3x10x01( x1)2 (2x1) 0x00. 45x0 0. 6 54用改进的牛顿法xk 1xk2 f ( xk )f ( xk )计算方程( x 1)2 (2x 1)0x0 0.55的近似根，并与要求3.中的的结果进行比较。二、 Gauuss列主元消去法（一）问题的提出由地一般线性方程组在使用Gauss 消去法求解时，从求解过程中可以清楚地看到，若akk(k 1)0 ，必须施以行交换的手续，才能使消去过程继续下去。有时既使akk(k 1)0 ，但其绝对值很小，由于舍入误差的影响，消去过程也会出现不稳定现象。因此，为使这种不稳定现象发生的可能性减至最小，在施行消去过程时每一步都要选主元素，即要寻找行r ，使| ark(k 1) | max | aik(k 1)|i k并将第 r 行与第 k 行交换，以使 akk(k1) 的当前值（即 aik(k1) 的数值）远大于0。这种列主元消去法的主要步骤如下：1消元过程对 k 1,2, , n 1，做1o 选主元，记| ark |max | aik |i k若 ark0 ，说明方程组系数矩阵奇异，则停止计算，否则进行2o。2o交换 A （增广矩阵）的r , k 两行元素arjakjj k, , n 13o计算aijaijaik akj / akkik1,njk1, n12回代过程对 kn, n 1, ,2,1 ，计算nxk(ak ,n 1akj xj / akk )j k 1其计算框图如下：开始输入 A （增广矩阵）k1| ark |max | aik |ik是ark0否交换 A 中 r , k 两行aijaijaikakj / akkik 1, njk1, ,n 1是kn1k 1否xk(ak, n 1nakj xj ) / akkjk1kn ,n1,2,1输出 x结束（二）目的1熟悉 Gauss 列主元消去法，编出实用程序。2认识选主元技术的重要性。3明确对于哪些系数矩阵A ，在求解过程中不需使用选主元技术。（三）要求1编制程序，用Gauss 列主元消去法求解线性方程组Ax b，并打印结果，其中10 8231（1） A13.7124.623 ，b221.0725.643342410（2） A21710，b3410972与不选主元的Gauss 消去法结果比较并分析原因。三、 Runge 现象的产生和克服（一）问题的提出在给定 n1个插值节点和相应的函数值以后构造n 次插值多项式的方法。从余项的表达式看出， 插值多项式与被插函数逼近的程度是同分点的数目及位置有关的。能不能说， 分点越多，插值多项式对函数的逼近程度越好呢？答案是否定的，在本世纪初Runge 指出了这种多项式插值的缺点。什么是 Runge 现象呢？例：给定函数f ( x)11 x125x21取等距节点 xi12 i (i 0,1, ,10) ，试建立插值多项式10 (x) ，并研究它与 f (x) 的10误差。插值多项式的次数为10，用拉格朗日插值公式有1010 ( x)f ( xi)li( x)i0其中f ( xi)125xi21xi12 i, i 0,1,1010li ( x)( x x0 ) ( xxi 1)( x xi 1 ) (x x10 )( xix0 ) (xixi 1)( xi xi 1) ( xi x10 )画出它们的图形，从图中可以看出，在 0.20, 0 区间内10 (x) 能较好地逼近f ( x) ，但在其他部分10 (x) 与 f (x) 的差异较大， 越靠近端点， 逼近的效果越差。 事实上可以证明，对1这个函数在 1, 1 区间内用 n 1个等距节点作插值多项式10 ( x) ，当 n时25x21n (x) 只能在 | x |0.73 内收敛，而在这个区间之外是发散的，这一现象称为Runge 现象。从上面例子看到， 在区间上给定等距插值节点，过这些插值节点作拉格朗日插值多项式，节点不断加密时，构造的插值多项式的次数也不断提高，但是，尽管被插值函数是连续的，高次插值多项式也不一定收敛到相应的被插值函数。解决 Runge 现象有分段线性插值，三次样条插值等方法。分段线性插值：设在区间 a, b 上，给定 n1插值节点ax0x1xnb和相应的函数值y0 , y1 , yn ，求作一个插值函数( x) ，具有下面性质：（ 1）( xj )y j , j0,1,2,n（ 2）(x) 在每个小区间 x j , xj 1 上是线性函数。插值函数( x) 叫做区间 a,b 上对数据 ( xi , yi )(i0,1, n) 的分段线性插值函数。三次样条插值给定区间 a, b 一个分划: ax0x1xNb若函数 S(x) 满足下述两条件：1） S( x) 在每个小区间 xj 1, x j ( j1,2, N ) 上是 3 次多项式。2） S( x) 及其直到2 阶导数在 a,b 连续。则称S( x) 是关于分划的三次样条函数。（二）目的1深刻认识多项式插值的缺点；2明确插值的不收敛性怎样克服；3明确精度与节点、插值方法的关系。（三）要求给定函数 f ( x)1,1 x 1，及节点 xj1 ( j225x21), j 1,2, , N 1，试1N用如下插值方法如何克服Runge 现象1用多项式插值计算出下列插值SN (0),SN (0.06 0.1k ), SN ( 0.060.1k)k0,1,9 ，观察是否会产生Runge 现象。2用下列方法进行计算，并且比较它们克服Runge 现象的效果。（ 1）分段线性插值（ 2）三次样条函数插值（一） ，条件为：SN (x j )f ( xj ), j1, N1SN ( xi )f ( xj ), i1, N1（ 3）三次样条函数插值（二），条件为SN (x j )f (x j ),j1, N1SN (xi )f ( xi ), i1, N13编程序，打印结果分析。（ 1）编写计算程序，调试计算，比较每种插值在插值点上与精确值的误差是多少。（ 2）同一种插值法，当节点增多时，精度怎样？（ 3）打印程序、结果，写出实验报告。四、多项式最小二乘法（一）问题的提出对于给定的测量数据 ( xi , f i )(i1,2,n) 设函数分布为my( x)a jj (x)j 0特别地，取j (x) 为多项式形式j ( x)x jj0,1,2, m则根据最小二乘原理，可构造泛函nnj (xi ) 2H (a0 ,a1 , , am )( fia ji 1j 0令H0k0,1,2, mak则可得到法方程mnnj ( xi ) k ( xi )ajfi k ( xi )j 0i 1i 1k 0,1,2, m求解该方程组，则可得到解a0 , a1 , a2 , am ，因此可得到数据的最小二乘解mf ( x)ajj ( x)j0（二）目的1学习使用最小二乘原理2了解法方程的特性（三）要求用最小二乘方法处理实验数据。xi3456789fi2.01 2.98 3.50 5.02 5.47 6.02 7.05并作出 f ( x)的近似分布图。五、龙贝格积分法（一）问题的提出考虑积分bI ( f )f ( x)dxa欲求其近似值，可以采用如下公式：（复化）梯形公式（复化）辛卜生公式（复化）柯特斯公式Tn 1 h f ( xi )f ( xi 1 )i0 2Eb a h2 f ( ) a, b12n 1 hSi f ( xi ) 4 f ( xi 1 )f ( xi 1)0 62b ah4Ef (4)( ) a ,b1802Cn 1 h 7 f (xi ) 32 f ( x1 ) 12 f ( x 1 )i 0 90i42i32 f ( xi 3 ) 7 f ( xi 1)46E2(ba)hf (6) ( ) a ,b9454这里，梯形公式显得算法简单，具有如下递推关系T2 n1 Tnh n 1f (x 1 )22 i 02i因此，很容易实现从低阶的计算结果推算出高阶的近似值，而只需要花费较少的附加函数计算。但是，由于梯形公式收敛阶较低，收敛速度缓慢。所以，如何提高收敛速度，自然是人们极为关心的课题。为此，记T0, k 为将区间 a, b 进行 2k等份的复化梯形积分结果，T 为1,k将区间 a,b 进行 2k 等份的复化辛卜生积分结果， T2,k为将区间 a, b 进行 2k 等份的复化柯特斯积分结果。根据李查逊（Richardson）外推加速方法，可得到Tm,k4m Tm 1,k 1Tm 1,kk0,1,2,4m1m0,1,2,可以证明，如果 f (x) 充分光滑，则有lim Tm,k I ( f )（ m 固定）klim Tm,0I ( f )m这是一个收敛速度更快的一个数值求积公式，我们称为龙贝格积分法。该方法的计算可按下表进行T0,0T0 ,1T0,2T0,mT1,0T1, 1T1,m1T2,0T2, m2Tm,0很明显，龙贝格计算过程在计算机上实现时，只需开辟一个一维数组，即每次计算的结果Tm ,k ，可存放在 T0, k 位置上，其最终结果Tm,0 是存放在 T0,0位置上。具体的计算过程为：1准备初值，计算T0,0ab f (a)f (b)2且 k0 （ k 为等份次数）2按梯形公式的递推关系，计算a 2kT0, k 11b1ba1T0, kk 1f ( a2k(i)22i023按龙贝格公式计算加速值T0,k mTm,k m4m Tm 1,k 1 mTm 1,k mm0,1,2, , k4m14精度控制。对给定的精度，若|Tm,0Tm 1,0 |则终止计算，并取 T0, sTm, s 作为所求结果；否则 kk1 ，重复 24 步，直到满足精度为止。（二）目的1理解和掌握龙贝格积分法的原理；2学会使用龙贝格积分法；3明确龙贝格积分法的收敛速度及应用时容易出现的问题。（三）要求1用龙贝格积分法计算下列积分的近似值（ 1）1003（ 2）1 sin x12dx6x dx ；0dx ；（3）sin xx02打印龙贝格积分法的函数表，使积分结果更加清楚。3分析所出现的问题并加以讨论。六、常微分方程初值问题的数值解法（一）问题的提出一阶常微分方程初值问题dyf (x, y)dx（6.1）y(x0 )y0的数值解法是近似计算中很重要的部分。常微分方程初值问题的数值解法是求方程（ 6.1）的解在点列xnxn 1hn (n0,1,)上的近似值yn ，这里hn 是xn 1 到 xn 的步长，一般略去下标记为h 。常微分方程初值问题的数值解法一般分为两大类：（ 1）单步法：这类方法在计算yn 时，只用到xn 1 、 xn 和yn ，即前一步的值。因此，在有了初值以后就可以逐步往下计算。典型方法如龙格库塔( RK)方法。（ 2 ） 多 步 法 ： 这 类 方 法 在 计 算 yn 1 时 ， 除 用 到 xn 1 、 xn 和 yn 以 外 ， 还 要 用yn p ( p 1,2,k; k 0) ，即前面 k 步的值。典型方法如Adams 方法。经典的 RK 方法是一个四阶的方法，它的计算公式是：yn 1ynh2K2 2K3 K4 )( K16K1f ( xn ,yn )K 2f ( xnh , ynh K1 )（6.2）22K 3f ( xnh , ynh K 2 )22K 4f ( xnh, ynhK 3 )R K 方法的优点是：单步法、精度高，计算过程便于改变步长，缺点是计算量较大，每前进一步需要计算四次函数值 f 。四阶 Adams 预测校正方法是一个线性多步法，它是由Adams 显式公式和隐式公式组成，计算公式是：预测yn 1fn 1校正yn 1fn 1它的局部截断误差是ynh(55 fn 59 fn 1 37 f n 2 9 f n 3 )24f ( xn1,yn1)（ 6.3）ynh (9 f n 1 19 fn5 fn 1 fn 2 )24f ( xn1,yn1)y(xn 1)yn 1O(h5 ) 。利用 Adams 显式和隐式公式具有同阶截断误差但系数不同的特点，将截断误差以预测值和校正值来表示，在预测和校正公式中分别以它们各自的截断误差来进行补足，可期望使精度进一步得到改善。用yn 的预测值和校正值，修正后的预测校正公式为：pn 和 cn 分别表示第 n 步预测pn 1修正mn 1求 fmm 1校正cn 1修正yn 1求导yn 1ynh (55 fn59 fn 1 37 f n 2 9 f n 3 )24pn 1251 (cnpn )270f ( xn 1 , mn 1 )ynh19 fn 5 fn 1 f n 2 )(9mm 124cn119 (cn 1pn 1 )270f (xn 1 , yn 1 )（ 6.4）由于开始无预测值和校正值可以利用，故令p0 c0 0 ，以后就按上面步预计算。此方法的优点是：可以节省计算量（与R K方法相比减少了函数f 的计算次数）；缺点是：它不是自开始的， 需要先知道前面四个点的值y0 , y1 , y2 , y3 ，因此，它不能独立使用。 另外，它也不便于改变步长。（二）目的和意义通过实便，编写程序上机计算，使得对常微分方程初值问题的数值解法有更深的理解，掌握单步法和线性多步法是如何进行实际计算的及两类方法的适用范围和优缺点，特别是对这两类方法中最有代表性的方法；RK 方法和 Adams 方法及预测校正方法有更好的理解。通过这两种方法的配合使用，掌握不同方法如何配合在一起，解决实际问题。（三）实际计算例题1初值问题yx2y2,( 1x0)y( 1)0取步长 h 0.1 ，计算在 1, 0上的数值解。2初值问题：y2xy(0 x1.5)y ,y(0)1取步长 h 0.1 ，计算在 0, 1.5 上的数值解。（四）要求1求解所给的实际计算例题，先用RK 公式（ 6.2）计算 y1 , y2 , y3 ，然后用修正的Adams 预测校正公式（6.4）计算其余点上值。2编写计算程序，调试计算。分析计算结果是否合理、准确，并把解析解求出，与数值解相比较。要求结果保留五位小数。3打印程序、结果，写出实验报告。4把上面的计算方案应用到其它的线性多步法上，写出计算方案。善待自己，学会放弃，得而不喜，失而不烦，弃而不悔，多一份执着和自信，添一份洒脱和从容，才是潇洒快乐的人生！善待自己，学会原谅。谁都会遇到不顺心的事，谁都会碰到不顺眼的人。如果你不学会原谅，就会活得痛苦，活得很累。既要学会原谅自己，又要学会原谅别人，还要学会原谅生活。原谅自己，并不意味着对自己的放纵；原谅别人，并不代表着丢弃原则，原谅生活，并不是不热爱生活。学会原谅一切，只是为了善待别人和善待自己，也是为了善待一切。生命，每个人只有一次，或长或短；生活，每个人都在继续，或悲或欢；人生，每个人都在旅途，或起或伏。人无完人，事无完美，有些小人，你不须计较，计较会烦；有些繁事，你不必在意，在意会累。假如你与所有不喜欢的人过不去，假如你与所有不顺心的事都计较，一辈子还不是要累死，气死呀？！善待自己，使自己成为最好的，比善待别人更有意义。我们除了学会律己，宽容别人，成全别人之外，还要学会成全自己，宽容自己，给自己更多的时间和空间，来不断发展和完善自己。这样，你才生活得充实，幸福。