《北航计算方法复习题幻灯片资料》由会员分享，可在线阅读，更多相关《北航计算方法复习题幻灯片资料（67页珍藏版）》请在金锄头文库上搜索。
1、计算方法,复习课 2011-12-29,教学内容,引论 第一章 插值方法 第二章 数值积分 第三章 常微分方程的差分方法 第四章 方程求根的迭代法 第五章 线性方程组的迭代法 第六章 线性方程组的直接法,（但精度、误差等概念要贯穿于考题中）,考题形式,填空题主要考察基本概念，对方法的理解 共8题，共40分 五章的内容基本平均分配 大题计算、证明等 5-6道题，共60分 五章的内容基本平均分配 其中有1-2道题为作业题或书上的例题（可能改数）,第一章 插值方法,计算函数值 需要计算函数值，但函数关系复杂，没有解析表达式。 常见的有：由观测数据计算未观测到的点的函数值。 由观测数据构造一个适当的简
2、单函数近似的代替要寻求的函数插值法。,第一章 插值方法,几个典型问题： 问题1：设函数y=f(x)定义域为a，b，x0，x1，xn是a，b上的n+1个互异点，且yi=f(xi)已知，要构造一个函数g(x)，使得g(xi)=yi(i=0,1, ,n)。 问题2：求做n次多项式pn(x)，使满足条件： 为一组已给数据。 问题3：=问题1+问题2：即过给定点，也要求导数相同。,第一章 插值方法,问题1：设函数y=f(x)定义域为a，b，x0，x1，xn是a，b上的n+1个互异点，且yi=f(xi)已知，要构造一个函数g(x)，使得g(xi)=yi(i=0,1, ,n)。,第一章 插值方法,问题1：设
3、函数y=f(x)定义域为a，b，x0，x1，xn是a，b上的n+1个互异点，且yi=f(xi)已知，要构造一个函数g(x)，使得g(xi)=yi(i=0,1, ,n)。,Lagrange插值公式 Aitken插值公式 Newton插值公式,第一章 插值方法,Lagrange插值公式,Lagrange多项式,Lagrange基函数,满足,与 节点 有关，而与 f 无关,第一章 插值方法,Lagrange插值公式,Lagrange多项式,Lagrange基函数,思考2： f(x)=xk(k=0,1,n)关于互异节点xi(i=0,1,n)的拉格朗日插值公式,第一章 插值方法,Lagrange插值公式
4、,Lagrange多项式,Lagrange基函数,第一章 插值方法,Lagrange插值公式,Lagrange多项式,Lagrange基函数,第一章 插值方法,Aitken插值公式,(效率，或临时增加一个节点),利用两个k-1次插值fk-1(xk-1)， fk-1(xi)再做线性插值，结果得到k次插值fk(xi)的结果,特点： 高次插值过程归结为线性插值的多次重复； 数据的一致程度可判断插值结果的精度。,给定3个节点及节点上的函数值(xi，f(xi)(i=0，2)，按Aitken插值方法构造插值函数，试在下图中画出任意给定x对应的f2(x2),第一章 插值方法,Newton插值公式具有承袭性的
5、显示插值公式,差商具有对称性,余项？,第一章 插值方法,问题2：求做n次多项式pn(x)，使满足条件： 为一组已给数据。,Taylor插值,第一章 插值方法,问题3：=问题1+问题2：即过给定点，也要求导数相同。,Hermite插值,求函数f(x)的二次近似式P2(x)，满足： P2(x0)= f(x0) =y0, P2(x0)= f(x0) =y0, P2(x1)= f(x1) =y1。,求函数f(x)的三次近似式p3(x)，满足： P3(x0)= f(x0) =y0, P3(x0)= f(x0) =y0, P3(x1)= f(x1) =y1， P3(x1)= f(x1) =y1,基函数法,
6、余项？,第一章 插值方法,高次插值可能会产生龙格现象,第一章 插值方法,高次插值可能会产生龙格现象,分段插值,第二章 数值积分,机械求积 牛顿-柯特斯公式 龙贝格算法 高斯公式 数值微分,第二章 数值积分,为什么研究数值积分： (1) 有些函数的原函数不能用初等函数表现为有限的形式； (2) 原函数的形式复杂； (3) 原函数没有具体的表达式，只有离散点。定积分的数值解法(效率+精度)。,第二章 数值积分,机械求积,用被积函数f(x)的若干节点xi (ax0 x1 xnb)处的函数值f(xi)的线性组合 (数值积分公式，求积公式) 作为I(f)的近似值。 求积节点：xi(i=0，1，n) 求积
7、系数：Ai(i=0，1，n)与f(x)无关；,一般形式,第二章 数值积分,机械求积,一般形式,一般性问题：,求积公式的收敛性:,求积系数的特征:,求积公式的稳定性:,求积系数全为正时，公式是稳定的,第二章 数值积分,机械求积,一般形式,一般性问题：,求积公式的精度：,第二章 数值积分,机械求积,一般形式,第二章 数值积分,求积节点固定的情况,一般思想：取简单的、便于积分且又逼近于被积函数f(x)的函数(x)代替f(x)来构造求积公式； 典型插值多项式,pn(x)dx,插值型求积公式,插值型求积公式余项：,插值型求积公式的代数精度： 插值型求积公式至少具有n次代数精度 具有n次代数精度的求积公式
8、必是插值型的,第二章 数值积分,求积节点固定的情况,第二章 数值积分,求积节点固定的情况,设a，b为有限区间，取h=(b-a)/n，等距节点 xi=a+ih(i=0，1，n)。,记x=a+th(0t n)，则：,牛顿-柯特斯公式,第二章 数值积分,求积节点固定的情况,梯形公式,Simpson公式,Cotes公式,阶数越高越好？,精度？ 稳定性？,第二章 数值积分,求积节点可选择的情况 高斯求积公式提高精度,第二章 数值积分,求积节点可选择的情况 高斯求积公式提高精度,不失一般性，由代数精度构造插值型数值求积公式 求积节点xi(i=1，2，n)( ax1 x2 xn b)。 适当的选取求积节点x
9、i和求积系数Ai，可以使得该插值公式具有2n-1次代数精度。高斯求积公式和高斯求积点。,第二章 数值积分,求积节点可选择的情况 高斯求积公式提高精度,n=1：,中点公式,n=2： 具有3次代数精度。,对于任意区间a,b，,第二章 数值积分,求积节点可选择的情况 高斯求积公式提高精度,高斯点的特点,节点xi(i=1，2，n)是高斯点的充要条件是：多项式 与一切次数n-1的多项式p(x)正交，即成立：,高次的高斯公式不便于应用，一般可借鉴复合求积方法,第二章 数值积分,求积节点可选择的情况 高斯求积公式提高精度,高斯求积公式的余项,Gauss型求积公式总是稳定的。,设f在a,b上连续，则Gauss
10、型求积公式是收敛的,高斯求积公式的稳定性,高斯求积公式的收敛性,第三章 常微分方程的差分方法,欧拉方法 改进的欧拉方法 龙格-库塔方法 亚当姆斯方法 收敛性与稳定性 方程组与高阶方程的情形 边值问题,重点： 构造某种格式 格式的收敛性和稳定性 格式的精度,第三章 常微分方程的差分方法,典型的微分方程(一阶方程的初值问题),求解的核心消除导数 离散化方法,差分方法是一类重要的数值解法,第三章 常微分方程的差分方法,局部截断误差 整体截断误差,第三章 常微分方程的差分方法,Euler方法差商代替导数 隐式Euler方法向后差商 两步Euler格式中心差商公式,第三章 常微分方程的差分方法,微分方程
11、转化为积分方程 选取不同的数值积分公式不同的离散方法(差分格式),矩形格式 梯形格式,第三章 常微分方程的差分方法,改进的欧拉方法：预报-校正系统,第三章 常微分方程的差分方法,龙格-库塔方法,高精度(构造！) 思想核心是如何确定,区间xn, xn+1上的平均斜率,第三章 常微分方程的差分方法,龙格-库塔方法,高精度(构造！) 思想核心是如何确定,区间xn, xn+1上的平均斜率,第三章 常微分方程的差分方法,龙格-库塔方法,二阶龙格-库塔：取xn和xn+p= xn+ph，0p1。合理的确定、p，以提高精度。,有： p=1/2。二阶Runge-Kutta格式（二阶精度）,=1/2，p=1，改进
12、的Euler公式； =1，p=1/2，变形的Euler公式中点公式；,类似可得三阶Runge-Kutta格式（三阶精度）,第三章 常微分方程的差分方法,龙格库塔方法的基本思想,亚当姆斯方法的基本思想,第三章 常微分方程的差分方法,亚当姆斯方法,基本思想：利用xn，xn-1， xn-2 上的斜率值减少计算yn+1的计算量或提高精度。,取合理的，使上述格式具有二阶精度 二阶Adams格式（=-1/2）,第三章 常微分方程的差分方法,亚当姆斯方法,斜率外推变成内插（改善精度）隐式亚当姆斯格式,三阶 四阶,二阶隐式Adams格式,第三章 常微分方程的差分方法,收敛性与稳定性, 收敛性问题 若 ，则称该
13、方法收敛。,欧拉格式： 如果初值准确，则有h0,en 0，Euler格式收敛。,第三章 常微分方程的差分方法,收敛性与稳定性, 稳定性问题,每一步的计算并不严格准确，存在计算误差的传播问题扰动。 若则称为稳定的。,第四章 方程根的迭代法,迭代过程的收敛性 迭代过程的加速 牛顿法 弦截法,重点： 不动点理论 写出有收敛性的格式，用于解题,第四章 方程根的迭代法,迭代法基本思想,从给定的一个或几个初始近似值(初始值)x0、x1、x2、xr出发，按某种方法产生的一个序列x0，x1，x2，xr， xr+1，xk ，称为迭代序列，使得此序列收敛于方程f(x)=0的一个根x*。 当k足够大时，取xk作为x
14、*的近似值。,需要讨论的问题 迭代法的构造(迭代格式)； 迭代序列的收敛性和收敛速度； 误差估计。,第四章 方程根的迭代法,迭代格式,如何构造序列x0，x1，x2，xk,如何判断迭代格式的好坏,收敛性及收敛速度,误差估计,第四章 方程根的迭代法,收敛性 解的收敛与初值选取范围有关。 大范围收敛：从任何可取的初始值出发都能保证收敛； 局部收敛：初始值充分接近于所要求的根，如果存在邻域： ，使迭代过程对于任何初值x0 均收敛。,收敛速度收敛阶数 令 若存在实数和非零常数C，使得 则称该迭代法为阶收敛，或者说收敛阶数为。,第四章 方程根的迭代法,将非线性方程f(x)=0化为等价方程 x=g(x),f
15、 (x) = 0,x = g (x)（迭代函数）,f (x) 的根,g (x) 的不动点,第四章 方程根的迭代法,假设g(x)为定义在有限区间a，b上的一个实函数，满足下列条件： (1) (2) 存在 0 L1，对于任意x a，b ，成立则对任意的初始值x0 a，b ，由Picard迭代产生的序列都收敛于g(x)的唯一不动点x*，并有误差估计式,不动点迭代 不动点理论（压缩映像原理）,定理1,第四章 方程根的迭代法,封闭性条件,压缩性条件,判断结果的精度,速度 迭代步数估计,1）两个条件： (1) (2) 存在 0 L1，对于任意x a，b ，成立 2）两个误差估计式的作用：,第四章 方程根的迭代法,局部收敛,设 为 的不动点， 在 的某邻域连续， 且 ，则迭代法(*)局部收敛。,定理2,第四章 方程根的迭代法,收敛速度,定理3：在定理1的假设条件下，再设g(x)在区间a，b上为m(2)次连续可微，且在x=g(x)的根x*处gj(x*)=0，j=1, m-1，gm(x*) 0。则Picard迭代为m阶收敛。线性收敛(m=1)，平方收敛(m=2)。,令 若存在实数和非零常数C，使得 则称该迭代法为阶收敛，或者说收敛阶数为。,第四章 方程根的迭代法,牛顿法,切线法,假设函数f(x)有m(m 2)阶连续导数，x*是方程f(x)=0的单根，则当x0充分接近x*时，N
