计算方法期末复习课件.ppt

1、考试范围 课堂中重点讲述内容 课堂例题 作业习题第一章 绪论 关于有效数字的位数问题若近似值x 的误差限是某一数位的半个单位，该位到 x 的第一位非零数字共有n位，则称x 有n 位有效数字定义10 3141510 *.,证明：3.1415926535897932; 例问： 有几位有效数字？请证明你的结论。* *3.1415 31 4*0.0000926. 0.0005 0.5*1005 10 |.有4 位有效数字，*精确到小数点后第 3 位。类似题目： 作业中习题一的一、二 题。第二章 插值与拟合 拉格朗日插值 N次拉格朗日插值多项式公式 余项 牛顿插值 Hermit 插值 二次曲线拟合一、一

2、、 n次次拉格朗日插值拉格朗日插值niyxLiin,., 0,)( 求求 n 次插值多项式次插值多项式 使得使得nnnxaxaaxL10)(已知: f(xi)=yi (i=0,1,n)nkkknyxlxL0)()()()()()()()()()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl k = 0, 1 , n .结论:n次拉格朗日插值多项式次拉格朗日插值多项式n次拉格朗日插值基函数次拉格朗日插值基函数 nkjjjkjkxxxxxl0)()()(设节点设节点 , f(x) 在在 a,b 上具有上具有 n+1阶导数，阶导数，Ln(x)是其是其n次次Lagrang

3、e插值多项式，插值多项式，则对则对 bxxxan 10其中 Lagrange插值余项定理插值余项定理1(1)( )( )( )( )(1)!( )nnnnfRxf xLxnx,( , )a b01( )niinxxx , ,( , )xa ba b 存在， 使得 解利用三点二次Lagrange插值.记则f(x)的二次Lagrange插值多项式为 012012( ),100,121,144,10,11,12f xx xxxyyy10010,12111,144121150201122012010210122021()()()()()()( )()()()()()()xxxxxxxxxxxxL xy

4、yyxxxxxxxxxxxx插值法计算 ，并估计误差。例1：已知2(115)155(115)(115 121)(115 144)(115 100)(115 144)1011(100121)(100144)(121 100)(121 144)fL(115 100)(115 121)1210.722756(144100)(144121)00163125. 010)144115)(121115)(100115(161)115()144)(121)(100(161)()()()(61)(52252210)3(2RxxxxxRxxxxxxfxR2583)( xxf误差估计差商的计算-差商表一阶差商一阶差

5、商 二阶差商二阶差商三阶差商三阶差商四阶差商四阶差商ix0 x1x2x3x4x( )if x1()f x2()f x3()f x4()f x0()f x01,f x x12 ,f x x23,f x x34,f x x012,f x x x123 ,f x x x234,f x x x0123,f x x x x1234 ,f x x x x01234 , , ,f x x x x x二、 牛顿插值多项式)()()().()(,.,).()(,.,.)(,)(,)()(1101011010102100100 xExNxxxxxxxxxxxxfxxxxxxxxxfxxxxxxxfxxxxfxfx

6、fnnnnnnn例 已知x=0, 2, 3, 5对应的函数值为y=1, 3, 2, 5，作三次Newton插值多项式.如再增加x=6时的函数数值为6，作四次Newton插值多项式. 解 首先构造差商表 xi f(xi) 一阶差商 二阶差商 三阶差商 0 1 2 3 1 3 2 -1 -2/3 5 5 3/2 5/6 3/10三次Newton插值多项式为323( )1(2)(2)(3)310Nxxx xx xx 增加x4=6，f(x4)=6作差商表 xi f(xi) 一阶差商 二阶差商 三阶差商 四阶差商 0 1 2 3 1 3 2 -1 -2/3 5 5 3/2 5/6 3/10 6 6 1

7、-1/6 -1/4 -11/120四次Newton插值多项为42311( )1(2)(2)(3)(2)(3)(5)310120Nxxx xx xxx xxx 三、 Hermit插值x0 x0yy1y1xy0y1y33( ),( )0,1iiiiHxyHxyi已知：构造一个次数3的多项式H3(x) ，满足插值条件：（* *）两点三次Hermit插值x0 x0yy1y1xy0y1y33( ),( )0,1iiiiHxyHxyi已知：构造一个次数3的多项式H3(x) ，满足插值条件：（* *）两点三次Hermit插值（续1）直接设dcxbxaxxH233)(待定系数将使计算复杂，且不易推广到高次。回

8、忆Lagrange插值基函数的方法，引入四个基函数)(),(),(),(1010 xxxx使之满足0)(0)(0)(1)(10001000 xxxx10111011()0()1()0()0 xxxx0)(1)(0)(0)(10001000 xxxx10111011()0()0()0()1xxxx5 5两点三次Hermit插值（续2）300110011( )( )( )( )( )Hxyxyxyxyx令0101( ),( ),( ),( )xxxx其中其中都是次数为都是次数为3 3的多项式的多项式则则H3 3( (x) )是一个次数是一个次数 3 3的多项式且满足插值条件的多项式且满足插值条件（

9、*）2100)()(xxxxbax 210012()()bxxxx2011()axx基函数求法：基函数求法：0( )x求求0101()0()0 xx00()1x21010100)(21()(xxxxxxxxx 3 320101011)(21()(xxxxxxxxx 同理设 由0(x0)=1 ，得 , 于是同理有2100)()(xxxxax 210100)()(xxxxxxx 201011)()(xxxxxxx 2011()axx定理：满足插值条件（*）的三次Hermite插值多项式H3(x)存在且唯一。三三 多项式拟合多项式拟合假设给定数据点假设给定数据点),(iiyx(i=0,1,m)，为所

10、有次数不超过为所有次数不超过)(mnn的多项式构成的函数类，现求一的多项式构成的函数类，现求一,使得使得nkkknxaxP0)(min)(00202 miminkikikiinyxayxPI(1)当拟合函数为多项式时，称为多项式拟合，满足式当拟合函数为多项式时，称为多项式拟合，满足式（1）的的)(xPn称为最小二乘拟合多项式。特别地，当称为最小二乘拟合多项式。特别地，当 n=1n=1 时，称为时，称为线性拟合或直线拟合线性拟合或直线拟合。四、拟合(2)12例题 例 设函数y=f(x)的离散数据如下表所示 试用二次多项式拟合上述数据.01234500.20.40.60.811.0001.2211

11、.4921.8222.2262.718iixiy 解方程组得 所以二次拟合多项式为08612. 5433. 6479.105664. 18 . 12 . 28 . 12 . 232 . 236210aaa0121.006321428,0.862589295,0.842410704aaa21.0063214280.8625892950.842410704yxx解：设所求的二次拟合多项式为则有如下方程组第三章、数值积分与数值微分一、等距节点求积公式梯形公式 ( )d ( )( )2babaf xxf af bTSimpson公式( )d( )4( )62babaabf xxf aff bS四、代数

12、精度的概念. ,1, 次次代代数数精精度度定定义义1 1mmm则则称称该该求求积积公公式式具具有有立立次次的的多多项项式式不不精精确确成成而而对对于于某某一一个个都都精精确确成成立立的的多多项项式式对对于于所所有有次次数数不不超超过过若若一一个个求求积积公公式式 定义定义2 2：若一个求积公式对若一个求积公式对f(x)=1, x, x2 , x m均均精确成立，而对精确成立，而对f(x)=x m+1不精确成立不精确成立, ,则称此求积则称此求积公式具有公式具有m次代数精度次代数精度.验证:梯形公式 1次代数精度辛甫生公式 3 次代数精度0()()nbkkakfx dxA fx 定理: 求积公式

13、至少有n次代数精度的充要条件是它是插值型求积公式。换言之，n+1个节点的插值型求积公式 至少具有 n 次代数精度 例例 设有求积公式设有求积公式求求A0，A1，A2，使其代数精度尽量高，并问此时求积公，使其代数精度尽量高，并问此时求积公式的代数精度式的代数精度 解：（解：（3个未知系数需三个方程）个未知系数需三个方程）令求积公式分别对令求积公式分别对f(x) = 1、x、x2精确成立。即精确成立。即 解之得解之得A0 = A2 = 1/3，A1 = 4/3，11210) 1 ()0() 1()(fAfAfAdxxf1120211201121032012AAdxxAAxdxAAAdx二、复合求积

14、法复合梯形公式1122()( )()( )nnkkhTff af xf b 复合Simpson公式111012426( )( )()()( )nnnkkkkhSff af xf xf b 例：利用函数表分别利用复合梯形公式、复合Simpson公式计算积分 的近似值，10sin xIdxx 0 1/8 1/4 3/8 10.9973980.9896880.976727 1/2 5/8 6/8 7/8 10.9588510.9361560.9088580.8771930.841471ix()if x将区间 8等分，用复合梯形公式, 得到0 1 , 解：81113022 8848153712848(

15、 )( )( )( )( )( )( )( )( )( )T ffffffffff 0 945692. 问题： 8等分对应于逐次二分的次数为几次？411357046 4888811321424( )( )( )( )( )( )( )( )( )( )Sffffffffff 0 9460832. 将区间 4等分，用复合Simpson公式, 得到0 1 , 三、龙贝格算法通过上述通过上述3个积分值序列求积分近似值的方法，个积分值序列求积分近似值的方法，称之为称之为Romberg算法。算法。4个积分值序列：个积分值序列： 2kT梯形值序列梯形值序列Simpson值序列值序列Romberg值序列值序

16、列Cotes值序列值序列 2kS 2kC 2kR122244 1kkkTTS 122222441kkkSSC 132232441kkkCCR 图3.3.1计算停止准则计算停止准则: :同一行或同一列相邻两数之差的同一行或同一列相邻两数之差的绝对值不超过预先给定的误差绝对值不超过预先给定的误差. . Romberg 算法：算法：例：例：用用Romberg算法求解定积分：算法求解定积分：12041dxx误差限：误差限：1.0e-5 212112141( ),0,1, (0)4, (1)2,1(0)(1)1 42322116112( )( )3.1,252241 3.13333333f xabffx

17、ffTfTTfSTT（）这里所以（ ）计算， 解：解：（要求两分三次，保留要求两分三次，保留5位有效数字）位有效数字）212112141( ),0,1, (0)4, (1)2,1(0)(1)1 42322116112( )( )3.1,252241 3.13333333f xabffxffTfTTfSTT（）这里所以（ ）计算， 解：按解：按Romberg公式的求积步骤进行计算，结果如下：公式的求积步骤进行计算，结果如下：42422211133()(),441113 ()()3.13117624444 3.141569316 3.14211815ffTTffTTSSSC（ ）计算及然后由公式算

18、出四、数值微分第四章、非线性方程的数值解法重点： 迭代法一、简单迭代法收敛定理局部收敛定理例设例设F(x)=x+c(x2-3)，应如何选取，应如何选取c才能才能使迭使迭xk+1=F(xk)代具有局部收敛性？代具有局部收敛性？ 解解: : 方程方程x=F(x)的根为的根为 ，函数，函数F(x)在根附近具有连续一阶导数，又在根附近具有连续一阶导数，又 F (x)=1+2cx, ，解，解 得得 解解 得得 从而要使迭代从而要使迭代xk+1=F(xk) 具有局部收敛性，具有局部收敛性， 则则 . 123,3 (3)12 31Fc 103c |( 3)|12 31Fc103c 103c例例 已知迭代公式

19、已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛。证明该迭代公式平方收敛。证证: 迭代公式相应的迭代函数为迭代公式相应的迭代函数为21132kkkxxx 33* x2132)(xxx 436)(232)(xxxx ，将将 代入，代入，故迭代公式故迭代公式平方收敛平方收敛。33* x032336*)(0*)(33 xx，二、牛顿迭代法第五章、 线性方程组的数值解法 直接求解： 高斯消去法 高斯列主元消去法 矩阵的三角分解法： Doolittle 分解法 迭代法 雅克比迭代法 高斯-赛德尔迭代法 SOR迭代法 雅克比迭代法和高斯-赛德尔迭代法的收敛性判断 （1.充要条件求解矩阵特征值，2. 严格

20、占优）111()()( )()kkkiiixxx12325610413191963630 xxx 例例: :用矩阵的直接三角分解法解方程组用矩阵的直接三角分解法解方程组或或 用用 Doolittle 分解法分解法111213212223313233111213312121311111(1)256100413191063611256462322ALUuuuluullukuuuaalluu 解解： 分分解解，令令，；，。时时，LUAululaukuulalulauulauk 473652143121434/ )(7)6(219352132233213313333221231323213212323

21、12212222所以所以时：时：，时：时：123123211021193413010,19201,34304(10, 1,4)TLybyyyyyyy （ ）解解得得即即123321(3)25610371441,2,3(3,2,1)TUxyxxxxxxx 解解解解得得：所所以以方方程程组组的的解解为为。 Jacobi迭代矩阵的特征方程的推导迭代矩阵的特征方程的推导 Gauss-Seidel迭代矩阵的特征方程的推导迭代矩阵的特征方程的推导第七章、常微分方程的数值解法尤拉法及改进尤拉法1(,)(0,1,2,.)iiiiyyh f x yi 三三 改进尤拉公式改进尤拉公式 Step 1: 先用先用显式

22、尤显式尤拉公式作拉公式作预测预测，算出，算出),(1iiiiyxfhyy Step 2: 再将再将 代入代入隐式隐式梯形公式的右边作梯形公式的右边作校正校正，得到，得到1 iy),(),(2111 iiiiiiyxfyxfhyy改进尤拉公式改进尤拉公式 这是一种显式格式这是一种显式格式, ,它可以表示为嵌套形式它可以表示为嵌套形式。 )1,., 0(),(,),(211 niyxfhyxfyxfhyyiiiiiiii改进尤拉公式改进尤拉公式例：用改进尤拉公式求解初值问题例：用改进尤拉公式求解初值问题 要求取步长h=0.2，计算y(1.2)及y(1.4)的近似值，小数点后至少保留5位. 解 设f

23、(x,y)=-y-y2sinx , x0=1,y0=1, xi=x0+ih=1+0.2i, 改进改进尤拉公式为 2dsin0d(1)1yyyxxy1111( ,) ( ,)(,)2iiiiiiiiiiyyhf x yhyyf x yf xy 于是有 由y0=1计算得110.631706(1.2)0.715489yyy220.476965(1.4)0.526112yyy212211110.2(sin)0.1(sinsin)iiiiiiiiiiiiiyyyyxyyyyxyyx注意：审题举例： 1.拟合多项式的次数2.题中要求使用的公式：“复合”梯形or梯形公式，“复合”simpson or Simpson。3. 保留的有效位数