北航计算方法复习题课件

计算方法复习课2019-12-29计算方法复习课2019-12-291教学内容引论第一章插值方法第二章数值积分第三章常微分方程的差分方法第四章方程求根的迭代法第五章线性方程组的迭代法第六章线性方程组的直接法（但精度、误差等概念要贯穿于考题中）教学内容引论（但精度、误差等概念要贯穿于考题中）2考题形式填空题——主要考察基本概念，对方法的理解共8题，共40分五章的内容基本平均分配大题——计算、证明等5-6道题，共60分五章的内容基本平均分配其中有1-2道题为作业题或书上的例题（可能改数）考题形式填空题——主要考察基本概念，对方法的理解3第一章插值方法拉格朗日插值（插值余项）埃特金算法牛顿插值埃尔米特插值分段插值样条插值曲线拟合的最小二乘法第一章插值方法拉格朗日插值（插值余项）4第一章插值方法计算函数值

需要计算函数值，但函数关系复杂，没有解析表达式。常见的有：由观测数据计算未观测到的点的函数值。

——由观测数据构造一个适当的简单函数近似的代替要寻求的函数——插值法。

第一章插值方法计算函数值5第一章插值方法几个典型问题：

问题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：即过给定点，也要求导数相同。第一章插值方法几个典型问题：6第一章插值方法

问题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)。几何意义：x0x1x2x3x4xg(x)

f(x)代数插值：为多项式函数集第一章插值方法问题1：设函数y=f(x)定义域为7第一章插值方法

问题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)。代数插值：为多项式函数集Lagrange插值公式Aitken插值公式Newton插值公式

第一章插值方法问题1：设函数y=f(x)定义域为8第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数满足与节点有关，而与f

无关给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC第一章插值方法Lagrange插值公式Lagrange多项9第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数思考1：令R[x]n+1表示所有的不高于n次的实系数多项式和零多项式构成的集合，假设函数y=f(x)的已知值(xi，yi)(yi=f(xi)，i=0，1，…，n)，寻找一个多项式Pn(x)R[x]n+1，满足：Pn(xi)=f(xi)(i=0，1，…，n)(*)唯一性？思考2：f(x)=xk(k=0,1,…,n)关于互异节点xi(i=0,1,…,n)的拉格朗日插值公式第一章插值方法Lagrange插值公式Lagrange多项10第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数1.20.4-0.8-2.0yi=f(xi)2.01.81.4

1.0

xi求的值

求方程在[1，2]内根的近似值。反插值问题例：已知单调连续函数在如下采样点的函数值：第一章插值方法Lagrange插值公式Lagrange多项11第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数（2）Lagrange插值多项式结构对称，形式简单.注：（1）若不将多项式次数限制为n

，则插值多项式不唯一。（4）当插值节点增加时，拉氏基函数需要重新计算，

n较大时，计算量非常大,故常用于理论分析。（3）误差估计第一章插值方法Lagrange插值公式Lagrange多项12第一章插值方法Aitken插值公式(效率，或临时增加一个节点)利用两个k-1次插值fk-1(xk-1)，fk-1(xi)再做线性插值，结果得到k次插值fk(xi)的结果特点：高次插值过程归结为线性插值的多次重复；数据的一致程度可判断插值结果的精度。给定3个节点及节点上的函数值(xi，f(xi))(i=0，…，2)，按Aitken插值方法构造插值函数，试在下图中画出任意给定x对应的f2(x2)

第一章插值方法Aitken插值公式(效率，或临时增加一个节13第一章插值方法Newton插值公式——具有承袭性的显示插值公式差商具有对称性余项？第一章插值方法Newton插值公式——具有承袭性的显示插值14第一章插值方法问题2：求做n次多项式pn(x)，使满足条件：为一组已给数据。Taylor插值第一章插值方法问题2：求做n次多项式pn(x)，使满足条件15第一章插值方法问题3：=问题1+问题2：即过给定点，也要求导数相同。Hermite插值求函数f(x)的二次近似式P2(x)，满足：

P2(x0)=f(x0)=y0,P’2(x0)=f’(x0)=y’0,P2(x1)=f(x1)=y1。求函数f(x)的三次近似式p3(x)，满足：

P3(x0)=f(x0)=y0,P’3(x0)=f’(x0)=y’0,P3(x1)=f(x1)=y1，

P’3(x1)=f’(x1)=y’1基函数法余项？？第一章插值方法问题3：=问题1+问题2：即过给定点，也要求16第一章插值方法分段插值高次插值可能会产生龙格现象

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

第一章插值方法分段插值高次插值可能会产生龙格现象-5-17第一章插值方法高次插值可能会产生龙格现象分段插值光滑性问题样条插值第一章插值方法高次插值可能会产生龙格现象分段插值光滑性问题18第二章数值积分机械求积牛顿-柯特斯公式龙贝格算法高斯公式数值微分第二章数值积分机械求积19第二章数值积分为什么研究数值积分：

(1)有些函数的原函数不能用初等函数表现为有限的形式；

(2)原函数的形式复杂；

(3)原函数没有具体的表达式，只有离散点。

——定积分的数值解法(效率+精度)。第二章数值积分为什么研究数值积分：20第二章数值积分机械求积

用被积函数f(x)的若干节点xi(a≤x0<x1<…<xn≤b)处的函数值f(xi)的线性组合

(数值积分公式，求积公式)

作为I(f)的近似值。求积节点：xi(i=0，1，…，n)

求积系数：Ai(i=0，1，…，n)与f(x)无关；一般形式

第二章数值积分机械求积用被积函数21第二章数值积分机械求积一般形式

一般性问题：

求积公式的收敛性:求积系数的特征:求积公式的稳定性:求积系数全为正时，公式是稳定的第二章数值积分机械求积一般形式一般性问题：求22第二章数值积分机械求积一般形式

一般性问题：

求积公式的精度：

如果求积公式对一切不高于m次的多项式都恒成立，而对于某个m+1次多项式不能精确成立，则称该求积公式具有m次代数精度。

求积公式具有次m代数精

度的充要条件是为时求积公式精确成立，而为时求积公式

不能成为等式。第二章数值积分机械求积一般形式一般性问题：求23第二章数值积分机械求积一般形式

Q1、节点已知，系数Ai如何选取Q2、节点自由选取，怎么选第二章数值积分机械求积一般形式Q1、节点已知，系24第二章数值积分求积节点固定的情况一般思想：取简单的、便于积分且又逼近于被积函数f(x)的函数φ(x)代替f(x)来构造求积公式；典型——插值多项式pn(x)dx插值型求积公式第二章数值积分求积节点固定的情况一般思想：取简单的、便于积25插值型求积公式余项：插值型求积公式的代数精度：插值型求积公式至少具有n次代数精度具有n次代数精度的求积公式必是插值型的第二章数值积分求积节点固定的情况插值型求积公式余项：插值型求积公式的代数精度：第二章数值积26第二章数值积分求积节点固定的情况设[a，b]为有限区间，取h=(b-a)/n，等距节点xi=a+i·h(i=0，1，…，n)。记x=a+t·h(0≤t≤n)，则：牛顿-柯特斯公式第二章数值积分求积节点固定的情况设[a，b]为有限区间，取27第二章数值积分求积节点固定的情况梯形公式Simpson公式Cotes公式阶数越高越好？精度？稳定性？

n为偶数时，Newton—Cotes求积公式至少具有n+1次代数精度。

n为奇数时，Newton—Cotes求积公式至少具有n次代数精度。复化求积公式第二章数值积分求积节点固定的情况梯形公式Simpson公式28第二章数值积分求积节点可选择的情况高斯求积公式——提高精度①当求积节点个数确定后，不管这些求积节点如何选取，求积公式的代数精度最高能达到多少？②具有最高代数精度的求积公式中求积节点如何选取？第二章数值积分求积节点可选择的情况①当求积节点个数确定后，29第二章数值积分求积节点可选择的情况高斯求积公式——提高精度不失一般性，由代数精度构造插值型数值求积公式

求积节点xi(i=1，2，…，n)(

a≤x1≤x2≤…≤xn≤b)。适当的选取求积节点xi和求积系数Ai，可以使得该插值公式具有2n-1次代数精度。

——高斯求积公式和高斯求积点。第二章数值积分求积节点可选择的情况30第二章数值积分求积节点可选择的情况高斯求积公式——提高精度n=1：

中点公式n=2：具有3次代数精度。对于任意区间[a,b]，第二章数值积分求积节点可选择的情况n=1：中点公式n=2：31第二章数值积分求积节点可选择的情况高斯求积公式——提高精度高斯点的特点

节点xi(i=1，2，…，n)是高斯点的充要条件是：多项式与一切次数≤n-1的多项式p(x)正交，即成立：高次的高斯公式不便于应用，一般可借鉴复合求积方法第二章数值积分求积节点可选择的情况高斯点的特点节点x32第二章数值积分求积节点可选择的情况高斯求积公式——提高精度高斯求积公式的余项

Gauss型求积公式总是稳定的。设f在[a,b]上连续，则Gauss型求积公式是收敛的高斯求积公式的稳定性

高斯求积公式的收敛性

第二章数值积分求积节点可选择的情况高斯求积公式的余项33第三章常微分方程的差分方法欧拉方法改进的欧拉方法龙格-库塔方法亚当姆斯方法收敛性与稳定性方程组与高阶方程的情形边值问题重点：构造某种格式格式的收敛性和稳定性格式的精度第三章常微分方程的差分方法欧拉方法重点：34第三章常微分方程的差分方法典型的微分方程(一阶方程的初值问题)求解的核心——消除导数离散化方法差分方法是一类重要的数值解法初值问题的解表示过点的一条曲线初值问题的数值解表示一组离散点列第三章常微分方程的差分方法典型的微分方程(一阶方程的初值问35第三章常微分方程的差分方法局部截断误差整体截断误差设是准确的，用某种方法计算时产生的截断误差，称为该方法的局部截断误差称为某方法在点的整体截断误差去掉准确的前提如果其局部截断误差为O(hp+1)，称该数值方法的精度是p阶的定义精度判断收敛性第三章常微分方程的差分方法局部截断误差设是准确的，36第三章常微分方程的差分方法Euler方法——差商代替导数隐式Euler方法——向后差商两步Euler格式——中心差商公式第三章常微分方程的差分方法Euler方法——差商代替导数37第三章常微分方程的差分方法微分方程转化为积分方程选取不同的数值积分公式——不同的离散方法(差分格式)矩形格式

梯形格式

第三章常微分方程的差分方法微分方程转化为积分方程矩形格式38第三章常微分方程的差分方法改进的欧拉方法：预报-校正系统第三章常微分方程的差分方法改进的欧拉方法：预报-校正系统39第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)思想

核心是如何确定——区间[xn,xn+1]上的平均斜率第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)—40第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)思想

核心是如何确定——区间[xn,xn+1]上的平均斜率第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)—41第三章常微分方程的差分方法龙格-库塔方法二阶龙格-库塔：取xn和xn+p=

xn+ph，0<p≤1。

合理的确定λ、p，以提高精度。有：λp=1/2。

——二阶Runge-Kutta格式（二阶精度）λ=1/2，p=1，改进的Euler公式；λ=1，p=1/2，变形的Euler公式——中点公式；类似可得三阶Runge-Kutta格式（三阶精度）第三章常微分方程的差分方法龙格-库塔方法二阶龙格-库塔：取42第三章常微分方程的差分方法龙格库塔方法的基本思想亚当姆斯方法的基本思想第三章常微分方程的差分方法龙格库塔方法的基本思想亚当姆斯方43第三章常微分方程的差分方法亚当姆斯方法基本思想：利用xn，xn-1，xn-2…上的斜率值减少计算yn+1的计算量或提高精度。取合理的λ，使上述格式具有二阶精度——二阶Adams格式（λ=-1/2）第三章常微分方程的差分方法亚当姆斯方法基本思想：利用xn，44第三章常微分方程的差分方法亚当姆斯方法斜率外推变成内插（改善精度）——隐式亚当姆斯格式三阶

四阶二阶隐式Adams格式第三章常微分方程的差分方法亚当姆斯方法斜率外推变成内插（改45第三章常微分方程的差分方法收敛性与稳定性—收敛性问题

若，则称该方法收敛。欧拉格式：如果初值准确，则有h→0,en→0，Euler格式收敛。第三章常微分方程的差分方法收敛性与稳定性—收敛性问题

46第三章常微分方程的差分方法收敛性与稳定性—稳定性问题

每一步的计算并不严格准确，存在计算误差的传播问题——扰动。

若

则称为稳定的。第三章常微分方程的差分方法收敛性与稳定性—稳定性问题

每47北航计算方法复习题课件48第四章方程根的迭代法迭代过程的收敛性迭代过程的加速牛顿法弦截法重点：不动点理论写出有收敛性的格式，用于解题第四章方程根的迭代法迭代过程的收敛性重点：49第四章方程根的迭代法迭代法基本思想

从给定的一个或几个初始近似值(初始值)x0、x1、x2、…、xr出发，按某种方法产生的一个序列x0，x1，x2，…，xr，xr+1，…，xk，…称为迭代序列，使得此序列收敛于方程f(x)=0的一个根x*。

当k足够大时，取xk作为x*的近似值。需要讨论的问题

迭代法的构造(迭代格式)；

迭代序列的收敛性和收敛速度；

误差估计。第四章方程根的迭代法迭代法基本思想从给定50第四章方程根的迭代法迭代格式

如何构造序列x0，x1，x2，…，xk

如何判断迭代格式的好坏收敛性及收敛速度误差估计第四章方程根的迭代法迭代格式如何构造序列x0，x1，x251第四章方程根的迭代法收敛性

解的收敛与初值选取范围有关。

大范围收敛：从任何可取的初始值出发都能保证收敛；

局部收敛：初始值充分接近于所要求的根，如果存在邻域Δ：，使迭代过程对于任何初值x0

∈δ均收敛。收敛速度——收敛阶数

令

若存在实数λ和非零常数C，使得

则称该迭代法为λ阶收敛，或者说收敛阶数为λ。第四章方程根的迭代法收敛性

解的收敛与初值52第四章方程根的迭代法将非线性方程f(x)=0化为等价方程x=g(x)

f(x)=0x=g(x)（迭代函数）等价变换f(x)的根g(x)的不动点第四章方程根的迭代法将非线性方程f(x)=0化为等价方程53第四章方程根的迭代法

假设g(x)为定义在有限区间[a，b]上的一个实函数，满足下列条件：

(1)

(2)存在0L<1，对于任意x

∈[a，b]

，成立

则对任意的初始值x0∈[a，b]

，由Picard迭代产生的序列都收敛于g(x)的唯一不动点x*，并有误差估计式不动点迭代不动点理论（压缩映像原理）定理1第四章方程根的迭代法假设g(x)为定义在有限区间[a54第四章方程根的迭代法——封闭性条件——压缩性条件——判断结果的精度——速度——迭代步数估计

1）两个条件：

(1)

(2)存在0L<1，对于任意x

∈[a，b]

，成立

2）两个误差估计式的作用：第四章方程根的迭代法——封闭性条件——压缩性条件——判断结55第四章方程根的迭代法局部收敛

设为的不动点，在的某邻域连续，且，则迭代法(*)局部收敛。定理2第四章方程根的迭代法局部收敛设为56第四章方程根的迭代法收敛速度定理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，使得

则称该迭代法为λ阶收敛，或者说收敛阶数为λ。

第四章方程根的迭代法收敛速度定理3：在定理1的假设条件下，57第四章方程根的迭代法牛顿法xyx*x0切线法假设函数f(x)有m(m>2)阶连续导数，x*是方程f(x)=0的单根，则当x0充分接近x*时，Newton法收敛，且至少为二阶收敛。Newton法的收敛性与x0的选取有关第四章方程根的迭代法牛顿法xyx*x0切线法假设函数f(x58牛顿迭代法的优缺点

优点：在单根附近,牛顿迭代法具有平方收敛(至少)的

速度，所以在迭代过程中只要迭代几次就会得

到很精确解。

缺点:1.重根情形下为局部线性收敛;2.牛顿迭代法计算量比较大:因每次迭代除计算

函数值外还要计算导数值;3.选定的初值要接近方程的解，否则有可能得不

到收敛的结果;第四章方程根的迭代法牛顿迭代法的优缺点优点：在单根附近59第四章方程根的迭代法弦截法导数计算比较复杂，采用差商公式替换Newton公式中的导数，有：

当x0充分接近x*，0<|g’(x)|<1，从而线性收敛提高收敛速度？第四章方程根的迭代法弦截法导数计算比较复杂，采用差商公式替60第五章线性方程组的迭代法迭代公式的建立迭代过程的收敛性迭代法的基本原理Jacobi迭代Gauss-Seidel迭代SOR法

第五章线性方程组的迭代法迭代公式的建立61第五章线性方程组的迭代法迭代公式的建立与解f(x)=0

的不动点迭代相似，将方程组等价改写成形式，从而建立迭代格式

，从出发，生成迭代序列第五章线性方程组的迭代法迭代公式的建立与解f(x)=062第五章线性方程组的迭代法迭代过程的收敛性定理1

迭代法收敛的充要条件是定理2

若||M||<1，则迭代格式收敛。定理3——误差估计式若||M||<1，则近似解x(k)满足第五章线性方程组的迭代法迭代过程的收敛性定理1

63第五章线性方程组的迭代法雅可比迭代

设线性方程组Ax=b的系数矩阵A=[aij]n×n非奇异，且主对角元素aii≠0，i=1，2，…，n。将A分解为

从而有：

Dx=b-(L+U)x或x=-D-1(L+U)x+D-1b对角占优对角占优方程组的Jacobi迭代收敛Mg第五章线性方程组的迭代法雅可比迭代设线性方程组64第五章线性方程组的迭代法高斯-塞德尔迭代x(k)=-(D+L)-1Ux(k-1)+(D+L)-1bx(k)=D-1(b-Lx(k)-Ux(k-1))x=-D-1(L+U)x+D-1bMgMgx(k)=D-1(b-Lx(k-1)-Ux(k-1))第五章线性方程组的迭代法高斯-塞德尔迭代x(k)=-(D+65第五章线性方程组的迭代法松弛法(Gauss-Seidel的加速方法)ω为松弛因子，0<ω<2。取x(k)

=D-1(b-Lx(k)-Ux(k-1))，则有:

x(k)

=ω(D-1(b-Lx(k)-Ux(k-1)))

+(1-ω)x(k-1)超松弛法（SOR法）

1<ω<2。

第五章线性方程组的迭代法松弛法(Gauss-Seidel的66注意准确性、精度、有效数字的概念贯穿于各个求解过程当中考试中没有特别复杂的计算要把解题思想写清楚低阶的公式应该记住注意准确性、精度、有效数字的概念贯穿于各个求解过程当中67计算方法复习课2019-12-29计算方法复习课2019-12-2968教学内容引论第一章插值方法第二章数值积分第三章常微分方程的差分方法第四章方程求根的迭代法第五章线性方程组的迭代法第六章线性方程组的直接法（但精度、误差等概念要贯穿于考题中）教学内容引论（但精度、误差等概念要贯穿于考题中）69考题形式填空题——主要考察基本概念，对方法的理解共8题，共40分五章的内容基本平均分配大题——计算、证明等5-6道题，共60分五章的内容基本平均分配其中有1-2道题为作业题或书上的例题（可能改数）考题形式填空题——主要考察基本概念，对方法的理解70第一章插值方法拉格朗日插值（插值余项）埃特金算法牛顿插值埃尔米特插值分段插值样条插值曲线拟合的最小二乘法第一章插值方法拉格朗日插值（插值余项）71第一章插值方法计算函数值

需要计算函数值，但函数关系复杂，没有解析表达式。常见的有：由观测数据计算未观测到的点的函数值。

——由观测数据构造一个适当的简单函数近似的代替要寻求的函数——插值法。

第一章插值方法计算函数值72第一章插值方法几个典型问题：

问题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：即过给定点，也要求导数相同。第一章插值方法几个典型问题：73第一章插值方法

问题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)。几何意义：x0x1x2x3x4xg(x)

f(x)代数插值：为多项式函数集第一章插值方法问题1：设函数y=f(x)定义域为74第一章插值方法

问题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)。代数插值：为多项式函数集Lagrange插值公式Aitken插值公式Newton插值公式

第一章插值方法问题1：设函数y=f(x)定义域为75第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数满足与节点有关，而与f

无关给定xi=i+1,i=0,1,2,3,4,5.下面哪个是l2(x)的图像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC第一章插值方法Lagrange插值公式Lagrange多项76第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数思考1：令R[x]n+1表示所有的不高于n次的实系数多项式和零多项式构成的集合，假设函数y=f(x)的已知值(xi，yi)(yi=f(xi)，i=0，1，…，n)，寻找一个多项式Pn(x)R[x]n+1，满足：Pn(xi)=f(xi)(i=0，1，…，n)(*)唯一性？思考2：f(x)=xk(k=0,1,…,n)关于互异节点xi(i=0,1,…,n)的拉格朗日插值公式第一章插值方法Lagrange插值公式Lagrange多项77第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数1.20.4-0.8-2.0yi=f(xi)2.01.81.4

1.0

xi求的值

求方程在[1，2]内根的近似值。反插值问题例：已知单调连续函数在如下采样点的函数值：第一章插值方法Lagrange插值公式Lagrange多项78第一章插值方法Lagrange插值公式Lagrange多项式Lagrange基函数（2）Lagrange插值多项式结构对称，形式简单.注：（1）若不将多项式次数限制为n

，则插值多项式不唯一。（4）当插值节点增加时，拉氏基函数需要重新计算，

n较大时，计算量非常大,故常用于理论分析。（3）误差估计第一章插值方法Lagrange插值公式Lagrange多项79第一章插值方法Aitken插值公式(效率，或临时增加一个节点)利用两个k-1次插值fk-1(xk-1)，fk-1(xi)再做线性插值，结果得到k次插值fk(xi)的结果特点：高次插值过程归结为线性插值的多次重复；数据的一致程度可判断插值结果的精度。给定3个节点及节点上的函数值(xi，f(xi))(i=0，…，2)，按Aitken插值方法构造插值函数，试在下图中画出任意给定x对应的f2(x2)

第一章插值方法Aitken插值公式(效率，或临时增加一个节80第一章插值方法Newton插值公式——具有承袭性的显示插值公式差商具有对称性余项？第一章插值方法Newton插值公式——具有承袭性的显示插值81第一章插值方法问题2：求做n次多项式pn(x)，使满足条件：为一组已给数据。Taylor插值第一章插值方法问题2：求做n次多项式pn(x)，使满足条件82第一章插值方法问题3：=问题1+问题2：即过给定点，也要求导数相同。Hermite插值求函数f(x)的二次近似式P2(x)，满足：

P2(x0)=f(x0)=y0,P’2(x0)=f’(x0)=y’0,P2(x1)=f(x1)=y1。求函数f(x)的三次近似式p3(x)，满足：

P3(x0)=f(x0)=y0,P’3(x0)=f’(x0)=y’0,P3(x1)=f(x1)=y1，

P’3(x1)=f’(x1)=y’1基函数法余项？？第一章插值方法问题3：=问题1+问题2：即过给定点，也要求83第一章插值方法分段插值高次插值可能会产生龙格现象

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

第一章插值方法分段插值高次插值可能会产生龙格现象-5-84第一章插值方法高次插值可能会产生龙格现象分段插值光滑性问题样条插值第一章插值方法高次插值可能会产生龙格现象分段插值光滑性问题85第二章数值积分机械求积牛顿-柯特斯公式龙贝格算法高斯公式数值微分第二章数值积分机械求积86第二章数值积分为什么研究数值积分：

(1)有些函数的原函数不能用初等函数表现为有限的形式；

(2)原函数的形式复杂；

(3)原函数没有具体的表达式，只有离散点。

——定积分的数值解法(效率+精度)。第二章数值积分为什么研究数值积分：87第二章数值积分机械求积

用被积函数f(x)的若干节点xi(a≤x0<x1<…<xn≤b)处的函数值f(xi)的线性组合

(数值积分公式，求积公式)

作为I(f)的近似值。求积节点：xi(i=0，1，…，n)

求积系数：Ai(i=0，1，…，n)与f(x)无关；一般形式

第二章数值积分机械求积用被积函数88第二章数值积分机械求积一般形式

一般性问题：

求积公式的收敛性:求积系数的特征:求积公式的稳定性:求积系数全为正时，公式是稳定的第二章数值积分机械求积一般形式一般性问题：求89第二章数值积分机械求积一般形式

一般性问题：

求积公式的精度：

如果求积公式对一切不高于m次的多项式都恒成立，而对于某个m+1次多项式不能精确成立，则称该求积公式具有m次代数精度。

求积公式具有次m代数精

度的充要条件是为时求积公式精确成立，而为时求积公式

不能成为等式。第二章数值积分机械求积一般形式一般性问题：求90第二章数值积分机械求积一般形式

Q1、节点已知，系数Ai如何选取Q2、节点自由选取，怎么选第二章数值积分机械求积一般形式Q1、节点已知，系91第二章数值积分求积节点固定的情况一般思想：取简单的、便于积分且又逼近于被积函数f(x)的函数φ(x)代替f(x)来构造求积公式；典型——插值多项式pn(x)dx插值型求积公式第二章数值积分求积节点固定的情况一般思想：取简单的、便于积92插值型求积公式余项：插值型求积公式的代数精度：插值型求积公式至少具有n次代数精度具有n次代数精度的求积公式必是插值型的第二章数值积分求积节点固定的情况插值型求积公式余项：插值型求积公式的代数精度：第二章数值积93第二章数值积分求积节点固定的情况设[a，b]为有限区间，取h=(b-a)/n，等距节点xi=a+i·h(i=0，1，…，n)。记x=a+t·h(0≤t≤n)，则：牛顿-柯特斯公式第二章数值积分求积节点固定的情况设[a，b]为有限区间，取94第二章数值积分求积节点固定的情况梯形公式Simpson公式Cotes公式阶数越高越好？精度？稳定性？

n为偶数时，Newton—Cotes求积公式至少具有n+1次代数精度。

n为奇数时，Newton—Cotes求积公式至少具有n次代数精度。复化求积公式第二章数值积分求积节点固定的情况梯形公式Simpson公式95第二章数值积分求积节点可选择的情况高斯求积公式——提高精度①当求积节点个数确定后，不管这些求积节点如何选取，求积公式的代数精度最高能达到多少？②具有最高代数精度的求积公式中求积节点如何选取？第二章数值积分求积节点可选择的情况①当求积节点个数确定后，96第二章数值积分求积节点可选择的情况高斯求积公式——提高精度不失一般性，由代数精度构造插值型数值求积公式

求积节点xi(i=1，2，…，n)(

a≤x1≤x2≤…≤xn≤b)。适当的选取求积节点xi和求积系数Ai，可以使得该插值公式具有2n-1次代数精度。

——高斯求积公式和高斯求积点。第二章数值积分求积节点可选择的情况97第二章数值积分求积节点可选择的情况高斯求积公式——提高精度n=1：

中点公式n=2：具有3次代数精度。对于任意区间[a,b]，第二章数值积分求积节点可选择的情况n=1：中点公式n=2：98第二章数值积分求积节点可选择的情况高斯求积公式——提高精度高斯点的特点

节点xi(i=1，2，…，n)是高斯点的充要条件是：多项式与一切次数≤n-1的多项式p(x)正交，即成立：高次的高斯公式不便于应用，一般可借鉴复合求积方法第二章数值积分求积节点可选择的情况高斯点的特点节点x99第二章数值积分求积节点可选择的情况高斯求积公式——提高精度高斯求积公式的余项

Gauss型求积公式总是稳定的。设f在[a,b]上连续，则Gauss型求积公式是收敛的高斯求积公式的稳定性

高斯求积公式的收敛性

第二章数值积分求积节点可选择的情况高斯求积公式的余项100第三章常微分方程的差分方法欧拉方法改进的欧拉方法龙格-库塔方法亚当姆斯方法收敛性与稳定性方程组与高阶方程的情形边值问题重点：构造某种格式格式的收敛性和稳定性格式的精度第三章常微分方程的差分方法欧拉方法重点：101第三章常微分方程的差分方法典型的微分方程(一阶方程的初值问题)求解的核心——消除导数离散化方法差分方法是一类重要的数值解法初值问题的解表示过点的一条曲线初值问题的数值解表示一组离散点列第三章常微分方程的差分方法典型的微分方程(一阶方程的初值问102第三章常微分方程的差分方法局部截断误差整体截断误差设是准确的，用某种方法计算时产生的截断误差，称为该方法的局部截断误差称为某方法在点的整体截断误差去掉准确的前提如果其局部截断误差为O(hp+1)，称该数值方法的精度是p阶的定义精度判断收敛性第三章常微分方程的差分方法局部截断误差设是准确的，103第三章常微分方程的差分方法Euler方法——差商代替导数隐式Euler方法——向后差商两步Euler格式——中心差商公式第三章常微分方程的差分方法Euler方法——差商代替导数104第三章常微分方程的差分方法微分方程转化为积分方程选取不同的数值积分公式——不同的离散方法(差分格式)矩形格式

梯形格式

第三章常微分方程的差分方法微分方程转化为积分方程矩形格式105第三章常微分方程的差分方法改进的欧拉方法：预报-校正系统第三章常微分方程的差分方法改进的欧拉方法：预报-校正系统106第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)思想

核心是如何确定——区间[xn,xn+1]上的平均斜率第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)—107第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)思想

核心是如何确定——区间[xn,xn+1]上的平均斜率第三章常微分方程的差分方法龙格-库塔方法高精度(构造！)—108第三章常微分方程的差分方法龙格-库塔方法二阶龙格-库塔：取xn和xn+p=

xn+ph，0<p≤1。

合理的确定λ、p，以提高精度。有：λp=1/2。

——二阶Runge-Kutta格式（二阶精度）λ=1/2，p=1，改进的Euler公式；λ=1，p=1/2，变形的Euler公式——中点公式；类似可得三阶Runge-Kutta格式（三阶精度）第三章常微分方程的差分方法龙格-库塔方法二阶龙格-库塔：取109第三章常微分方程的差分方法龙格库塔方法的基本思想亚当姆斯方法的基本思想第三章常微分方程的差分方法龙格库塔方法的基本思想亚当姆斯方110第三章常微分方程的差分方法亚当姆斯方法基本思想：利用xn，xn-1，xn-2…上的斜率值减少计算yn+1的计算量或提高精度。取合理的λ，使上述格式具有二阶精度——二阶Adams格式（λ=-1/2）第三章常微分方程的差分方法亚当姆斯方法基本思想：利用xn，111第三章常微分方程的差分方法亚当姆斯方法斜率外推变成内插（改善精度）——隐式亚当姆斯格式三阶

四阶二阶隐式Adams格式第三章常微分方程的差分方法亚当姆斯方法斜率外推变成内插（改112第三章常微分方程的差分方法收敛性与稳定性—收敛性问题

若，则称该方法收敛。欧拉格式：如果初值准确，则有h→0,en→0，Euler格式收敛。第三章常微分方程的差分方法收敛性与稳定性—收敛性问题

113第三章常微分方程的差分方法收敛性与稳定性—稳定性问题

每一步的计算并不严格准确，存在计算误差的传播问题——扰动。

若

则称为稳定的。第三章常微分方程的差分方法收敛性与稳定性—稳定性问题

每114北航计算方法复习题课件115第四章方程根的迭代法迭代过程的收敛性迭代过程的加速牛顿法弦截法重点：不动点理论写出有收敛性的格式，用于解题第四章方程根的迭代法迭代过程的收敛性重点：116第四章方程根的迭代法迭代法基本思想

从给定的一个或几个初始近似值(初始值)x0、x1、x2、…、xr出发，按某种方法产生的一个序列x0，x1，x2，…，xr，xr+1，…，xk，…称为迭代序列，使得此序列收敛于方程f(x)=0的一个根x*。

当k足够大时，取xk作为x*的近似值。需要讨论的问题

迭代法的构造(迭代格式)；

迭代序列的收敛性和收敛速度；

误差估计。第四章方程根的迭代法迭代法基本思想从给定117第四章方程根的迭代法迭代格式

如何构造序列x0，x1，x2，…，xk

如何判断迭代格式的好坏收敛性及收敛速度误差估计第四章方程根的迭代法迭代格式如何构造序列x0，x1，x2118第四章方程根的迭代法收敛性

解的收敛与初值选取范围有关。

大范围收敛：从任何可取的初始值出发都能保证收敛；

局部收敛：初始值充分接近于所要求的根，如果存在邻域Δ：，使迭代过程对于任何初值x0

∈δ均收敛。收敛速度——收敛阶数

令

若存在实数λ和非零常数C，使得

则称该迭代法为λ阶收敛，或者说收敛阶数为λ。第四章方程根的迭代法收敛性

解的收敛与初值119第四章方程根的迭代法将非线性方程f(x)=0化为等价方程x=g(x)

f(x)=0x=g(x)（迭代函数）等价变换f(x)的根g(x)的不动点第四章方程根的迭代法将非线性方程f(x)=0化为等价方程120第四章方程根的迭代法

假设g(x)为定义在有限区间[a，b]上的一个实函数，满足下列条件：

(1)

(2)存在0L<1，对于任意x

∈[a，b]

，成立

则对任意的初始值x0∈[a，b]

，由Picard迭代产生的序列都收敛于g(x)的唯一不动点x*，并有误差估计式不动点迭代不动点理论（压缩映像原理）定理1第四章方程根的迭代法假设g(x)为定义在有限区间[a121第四章方程根的迭代法——封闭性条件——压缩性条件——判断结果的精度——速度——迭代步数估计

1）两个条件：

(1)

(2)存在0L<1，对于任意x

∈[a，b]

，成立