《计算方法复习新课件》由会员分享，可在线阅读，更多相关《计算方法复习新课件（98页珍藏版）》请在金锄头文库上搜索。
1、计算方法,总复习,第一章 误差和有效数字,误差的来源及分类 绝对误差、相对误差、有效数字的定义 误差同有效数字的关系 数值计算中应注意的几个问题,误差的来源及分类,模型误差 观测误差 截断误差 舍入误差,绝对误差、相对误差、有效数字的定义,绝对误差与绝对误差限 相对误差与相对误差限,绝对误差、相对误差、有效数字的定义,有效数字的定义,误差同有效数字的关系,则x*至少具有n位有效数字,四舍五入得到,如 3.14= 0.314101 （X * =0.X1X2Xn 10m） n = 3 , m = 1 | 3.14| = |3.1415926 - 3.14| =0.0015926. 0.005 =
2、10-2 = 101-3 = 10 m-n,数值计算中应注意的几个问题,避免两相近数相减 防止大数“吃”小数 除数不能太小 算法稳定性 简化运算步骤，减少运算次数,类似的：,小结： 1、什么是舍入误差？什么是截断误差？它们的来源是什么？ 2、什么是绝对误差、相对误差和有效数字？ 3、绝对误差、相对误差和有效数字之间的关系是什么？ 4、 =3.141592654 (1) 若其近似值取5位有效数字，则该近似值是多少？其绝对、相对误差限是多少？ （2）若其近似值取3.1415, 绝对误差限是什么？有效数字是什么 （3）若其近似值的绝对误差限为0.5 10-5 则该近似值是什么？,5、下列近似值有几位
3、有效数字，其相对误差限是什么？,绝对误差限是什么? （1) x1=e= 2.71828=x1* (2) x2=0.030051 x2*=0.0300 (3)x3=e/100 0.02718=x3*,第二章 非线性方程的解法,对分法 迭代法 牛顿迭代法,对分法,条件 f(x)在a,b上连续，f(a)f(b)0，单调 意义 对分次数n的计算,迭代法,迭代法,牛顿迭代法,条件 设f(x)在a,b上连续，f(a) f(b)0，且x0为a,b上根x*a, b 的一个近似值。 几何意义 用切线与x轴的交点近似代替取限于x轴的交点。,.牛顿迭代法的几何意义： 以f (x0)为斜率作过(x0 , f (x0)
4、点的直线，即作f(x)在点x0 的切线方程：,令 y=0, 则得此切线与x轴的交点x1, 即,x1,牛顿迭代法又称切线法,收敛性 由 (x) 的表达式得： | (x) | =,因为 f (x*) = 0 所以 (x*) = 0 也即 (x)在根的附近收敛很快,（1）局部收敛定理(p30) 设 f (x) 存在， 且 f (x) 在方程f(x)=0 的根x*附近不为零 ，,= L 1 , 则Newton迭代格式收敛,若| (x) | =,(2) 全局收敛定理（p31大范围收敛定理） 设 f( x) 在 a ,b 上满足 f(a)f(b) 0 则Newton迭代序列收敛于f(x) =0 在 a,
5、b的唯一根,-.保证有根,-.保证单根,-.保证凸凹性不变,-.保证收敛,牛顿迭代法,牛顿迭代公式至少二阶收敛 特点 在单根附近具有较高的收敛速度。 公式,牛顿迭代法,m重根,第三章 线性代数方程组的解法,直接法（快速有效） 迭代方法（节省内存） 向量范数、矩阵范数的定义、性质 条件数及其对相对误差的影响（三个证明）,直接法,Gauss消去法、Gauss列主元消去法（算法描述） 追赶法（三对角严格对角占优） 平方根法,Gauss消去法,消元过程,回代过程,二、算法描述 1、消元 对k=1.n-1 消元因子： C= aik(k)/ akk(k) ( i= k+1.n ） 系数变化： aij(k+
6、1) = aij(k) （i k) aij(k+1) = aij(k) - C. akj(k) ( i k , j=k+1,n+1 ),2、回代 第 i次回代公式 （ i=n,n-1.1) Xi(即a in+1(i)=(a in+1(i) - ）/aii(i),Gauss列主元消去法,关键步骤 第k次消元时，在系数矩阵A的第k列元素中选取绝对值最大的元素为主元素。,追赶法（条件）,解对称正定的平方根法 定理2：若 n阶方阵A对称正定，则存在唯一的对角元素为正的下三角阵L，使A=LLT (Cholesky分解） 即:,(i=2,.n, j=1,.i-1) (p54 3-25) -按行计算公式,按
7、列计算公式： 对j=1,2,n,i=j+1,j+2,.n,迭代方法,Jacobi迭代法 A=D-L-U Gauss-Seidel迭代法 公式及收敛条件（充分条件、充要条件）,Jacobi迭代法,分量形式 矩阵形式,记 ，,Jacobi迭代法,Jacobi迭代收敛条件 充分条件(1) :迭代矩阵至少存在一种矩阵范数|.|, 使 | C | 1 充分条件(2) : 方程组 AX=b的系数矩阵A为 严格对角占优阵 充要条件：迭代矩阵的谱半径(C) 1,Gauss-Seidel迭代法,分量形式 矩阵形式,记 ，,迭代公式为：,Gauss-Seidel迭代,充分条件： 迭代矩阵G的|G|1 A对称正定
8、A严格对角占优 充要条件：(G)1,向量范数、矩阵范数,向量范数 非负性 齐次性 三角不等式,三种常用的向量范数 1范数 2范数 范数,向量范数、矩阵范数,矩阵范数,向量范数、矩阵范数,三种常用的矩阵的算子范数,向量范数、矩阵范数,谱半径,条件数及其对相对误差的影响,条件数,Cond(A)的值越大，方程组的病态就越严重。,条件数的 性质,条件数及其对相对误差的影响,常用的条件数,（2）A的谱条件数,当A为对称正定矩阵时，,其中1，n为矩阵A的最大和最小特征值。,第四章 插值与拟合,Lagrange插值 Newton插值 差商、差分定义、性质 差商、差分表的构造、使用 样条函数插值、条件、意义
9、曲线拟合与最小二乘法(使用环境和步骤）,Lagrange插值,Lagrange插值多项式 线性插值及其余项 抛物插值（二次插值）,Lagrange插值,Lagrange插值余项 li(x)的性质,Lagrange插值,次数不超过n次的代数多项式的插值函数等于它本身。,Newton插值,公式,Newton插值,差商的定义,差商表的构造及使用,Nn ( x )=f(x0) + f x0,x1 (x-x0) +f x0,x1,x2(x-x0)(x-x1)+ + f x0,x1,x2,x3 (x-x0)(x-x1)(x-x2) . +f x0,x1,.xn (x-x0 )(x-x1)(x-x n-1)
10、,牛顿插值多项式的余项： Rn（ x ） = f x,x0,x1.xn (n+1) (x),样条函数插值、条件、意义,给定函数表 求一个函数 s(x) 满足 （1） s(xi)=yi ( i要= 0,1,n) （2）s(x) s(x)在内节点xi( i=1, n-1)上连续 （3）在每个小区间上，s(x)为三次多项式 此时，称 s(x)为三次样条插值函数,常见的边界条件有： （1）第一类边界条件：给定端点处的一阶导数值 s(x 0) =y(x0 ) （ m0= y(x0 ) ) s(x n)=y (x n ) ( m n= y (x n ) ) （2）第二类边界条件：给定端点处的二阶导数值 s
11、 (x 0) = y (x0 ) ( M0 = y (x0 ) ) s (x n)= y (x n ) ( M n = y (x n ) ) 特别情况下： M0= M n = 0 称为自然边界条件，满足自然边界条件的样条函数叫做自然样条,曲 线 拟 合 问 题 的 提 法,已知一组（二维）数据，即平面上 n个点（xi,yi) i=1,n, 寻求一个函数（曲线）y=p(x), 使 p(x) 在某种准则下与所有数据点最为接近，即曲线拟合的最好。,y=p(x),i 为点（xi,yi) 与曲线 y=p(x) 的距离,所谓”曲线拟合”,是指根据给定的数据表,寻找一个 简单的表达式来”拟合”该组数据,此处
12、的”拟合”的含义为:不要求该表达式对应的近似曲线完全通过所有的数 据点,只要求该近似曲线能够反映数据的基本变化趋势.,第五章 数值积分与微分,插值型求积公式 Newton-Cotes求积公式 复化求积公式 Gauss型求积公式 数值微分,插值型求积公式,定义 求积公式,其系数 时，则称求积公式为插值 求积公式。,例1 给定求积公式如下：,试证此求积公式是插值型的求积公式,证:设 ,则以这三点为插值节点的 Lagrange插值基函数为,由插值型求积公式的定义知，所给的求积公式是插值型求积公式。,插值型求积公式为,定理 n+1个节点的求积公式 为插值型求积公式的充要条件是公式 至少具有n次代数精度
13、。,的代数精度 可以验证, 对于f(x)=1, x时公式两端相等, 再将f(x)=x2代入公式 左端,例2 考察求积公式,两端不相等, 所以该求积公式具有 1 次代数精度. 三个节点不具有2次代数精度， 不是插值型的,右端,例3 求证,不是插值型的,证明: 设 x0 = -1, x1 =0, x2 =1, A0 =1/2, A1=1, A2=1/2 则以这三点为插值节点的Lagrange插值 基函数为,Newton-Cotes求积公式,梯形公式，精度、截断误差 抛物线（Simpson）公式，精度、截断误差 N-C求积公式的稳定性,梯形公式,梯形公式具有1阶精度,截断误差：,抛物线（Simpso
14、n）公式,抛物线公式具有3阶精度,截断误差：,Newton-Cotes求积公式的稳定性,当n8时,误差有可能传播扩大，收敛性也没有保证。因此，牛顿 柯特斯求积公式不宜采用。,复化求积公式,复化梯形公式、复化Simpson公式、截断误差 如何根据截断误差及精度确定n值，从而写出求积公式 Romberg求积公式、意义（思想）,复化梯形公式,截断误差：,复化,截断误差：,根据截断误差及精度确定n值,由余项确定截断误差绝对值的上界表示 由给定精度确定误差限 利用组成的不等式求得n值,例9 若用复合梯形公式计算积分 问积分区间要等分多少才能保证有误差不超过,写出相应的复化梯形公式(重点),解 由余项,则
15、当0 x1时,有,又,故,即:,即:,所以:,则:,取,而用复合simpson公式n=3.706 取n=4即能达到这个精度,相应的复化梯形公式为:,Romberg求积公式,Gauss型求积公式,Gauss型求积公式的定义，判断 具有2n+1次代数精度的插值型求积公式,数值微分,两点公式及其截断误差 三点公式及其截断误差,两点公式,截断误差,三点公式,三点公式,截断误差,第六章 常微分方程初值问题的数值解法,欧拉法 欧拉法、改进欧拉法、预报-校正公式 截断误差 精度 显式（隐式）、单步（多步） 绝对稳定区间的求法 龙格-库塔方法 思想、精度 显式（隐式）、单步（多步）,欧拉法,后退欧拉法,梯形公式,预报-校正公式,预报-校正公式,龙格-库塔公式,补充定义2：用单步法解模型方程 得到解满足稳定性方程 若 方法是绝对稳定的,例证明解常微分方程初值问题的梯形方法精度是二阶的，并求其局部截断误差主项,而局部截断误差按定义是： y(x i+1)-yi+1= y(x i+h)- yi+1,先将y(x i+h)在x=xi处tailor展开,分析：证明精度是二阶，即证明其局部截断误差是o(h3）,证明:,再来看 yi+1,代入上式 yi+1,例求Euler法的绝对稳定区间,所以，局部截断误差,局部截断误差为O(h3 ) 所以精度为2阶的,局部截断误差主项为：,
