数值计算方法总复习

数值计算方法总复习第一章

引言截断误差、舍入误差误差、误差限有效数字误差的传播如:若将前若干项的部分和作为函数值的近似公式,由于以后各项都舍弃了,自然产生了误差。Taylor展开截断误差

舍入误差

绝对误差、绝对误差限工程上常记为

误差、误差限例如

相对误差、相对误差限例1解:已知近似值为:精确值为:求

绝对误差、相对误差绝对误差相对误差或

有效数字用科学计数法，记其中若则称有n

位有效数字，精确到

。，的截取按四舍五入规则有4位有效数字有6位有效数字有8位有效数字例2

数据误差的传播绝对误差为：相对误差为：称为f的条件数，其绝对值的大小可反映函数值对数据的敏感程度

误差的传播利用上面的误差估计公式，可以得到两个数的和、差、积、商的误差估计

误差的控制、算法的稳定性第二章

非线性方程求根基本概念

局部收敛、全局收敛

收敛阶算法及其收敛性

二分法

简单迭代法

牛顿法及其简单变形局部收敛与全局收敛上面定理所涉及的收敛性，即在根邻域的收敛性称为局部收敛性，具有局部收敛性质的迭代法通常对初值的要求很高，使用起来不太方便。因而，人们通常希望迭代算法对相对大的范围的初始点具有收敛性，这种收敛性称为全局收敛性。定义2.2.1

设迭代过程

收敛于

的根.如果迭代误差

满足下列关系则称该迭代序列是p

阶收敛的(时要求)。当p=1时，称为线性收敛；当p>1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。显然，迭代序列的收敛阶越高，它的收敛速度就越快。收敛阶补充定理算法的基本思想：将区间对分，保留有根的区间，舍去无根的区间。如此往复，以逐步逼近方程的根。基本条件：二分法算法的步骤ax0b

a1b1此时有误差估计：常用来估计k的值算法的收敛性用二分法求方程

在[1,1.5]内的实根，要求

解即可推出所需的迭代次数满足在区间[1,1.5]上至少存在一个根。其具体过程如下：例由于因而由误差估计式

的符号01.00001.50001.2500-11.25001.50001.375+21.25001.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-等价变换原理：简单迭代迭代格式：定理2.2.1收敛性：压缩映像保证迭代不中断Lipschitz条件定理2.2.1的条件(2)不容易得到,由微分中值定理：推论不难得到如下推论。从而，有如下误差估计：定理

在推论的条件下，有误差估计式注

由于定理中条件(1)一般难于验证，而且在大区间上，这些条件也不一定都成立。所以实际使用迭代法总是在根的邻近进行。表明收敛性与初值的选择有关！定理2.2.2例解也可化为等价方程.但此时定理条件不成立，迭代序列不能保证收敛。将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解。基本思想Newton迭代方法迭代格式

Newton迭代法的计算步骤缺点：对初值要求较高，计算量较大。优点：收敛速度快，精度高，格式简单，应用广泛。优点与缺点

局部收敛性全局收敛性定理2.2.3

保证了根的存在性

函数单调，根惟一函数图形的凸向不变例解简化Newton法迭代格式进一步简化收敛性与收敛速度推广的简化Newton法只有线性收敛速度。迭代格式收敛性与收敛速度迭代格式收敛性与收敛速度Newton下山法迭代格式收敛性与收敛速度弦割法迭代格式收敛性与收敛速度单点弦割法单点弦割法的局部收敛性由简单迭代的一般收敛性理论可以推出：单点弦割法是局部收敛的且一般只有线性收敛速度。单点弦割法的全局收敛性定理2.3.2

第三章

线性方程组的数值解法基本概念

向量范数、矩阵范数、条件数

严格对角占优矩阵、对角占优矩阵、不可约矩阵算法及其收敛性

高斯消元法

矩阵的三角分解及其应用

迭代法--------(1)--------(2)--------(3)--------(4)显然并且由于例

求下列向量的各种常用范数解根据向量的常用范数可以得到常用的矩阵算子范数--------(10)--------(11)--------(12)证明见书P70例求矩阵A的各种常用范数解由于特征方程为容易计算计算较复杂对矩阵元素的变化比较敏感不是从属范数较少使用(理论上)使用最广泛性质较好定义3.3.5--------(13)矩阵的谱半径显然，由定义可知实特征值为绝对值，复特征值为模定义3.3.7矩阵的条件数矩阵A的条件数与所取范数有关。通常记显然，当A对称时，严格对角占优矩阵对角占优矩阵不可约矩阵容易验证下面矩阵按行（或列）都不严格对角占优，但它是不可约按行（或列）对角占优的。虽然不可约，但不按行（或列）对角占优。而矩阵Gauss消元法基本思想：Gauss消元法的运算量数级不必选主元的情况：当系数矩阵A对称正定或严格对角占优或不可约对角占优时，可不必选主元。Gauss消元法是不稳定的算法，其中小主元是不稳定的根源。因而在Gauss消元法中要避免小主元的出现。这就需要采用“选主元”的技术。所谓选主元，简单地说就是选取绝对值最大的元素作主元（全选主元或列选主元）。算法的稳定性：矩阵的LU分解法按上图逐框求出矩阵A的LU分解,紧凑格式法。上一页下一页

返回

定理若矩阵A非奇异,则A能分解为LU的充分必要条件是A的所有顺序主子式均不为0.定理若非奇异矩阵A有LU分解,则此分解是唯一的.定理设n阶对称正定矩阵A，则存在唯一的单位下三角阵L及对角阵D

使得。称为矩阵A的乔累斯基分解上一页下一页

返回

定理设矩阵A对称正定，则存在唯一的对角元为正的下三角阵L，使得。称为对称正定矩阵A的乔累斯基分解利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法例：利用系数矩阵的LU分解,求解方程组解：LU分解的紧凑格式为上一页下一页

返回

迭代法的一般形式及其收敛性迭代法（一）雅可比(Jacobi)迭代法几种古典迭代算法建立迭代格式：记

Jacobi迭代的矩阵形式易知，Jacobi迭代有（二）逐次代换法（Gauss－Seidel迭代）

Gauss－Seidel迭代的矩阵形式（三）逐次超松弛迭代（SOR迭代）

SOR迭代的矩阵形式定理3.4.1（一）收敛性判别定理定理3.14一般迭代算法的收敛性定理3.4.2Jacobi迭代收敛！Gauss-Seidel迭代发散！古典迭代法的收敛性第四章

插值方法基本概念

插值节点、插值多项式、插值基函数差商及其性质算法及其收敛性Lagrange插值Newton插值

分段线性插值------(1)这就是插值问题,(1)式为插值条件,Lagrange插值就是选用节点上的函数值作为插值条件，选用代数多项式作为插值函数。

Lagrange插值已知n+1个互异插值节点

(xi,f(xi)),i=0,1,2,…,n。插值基函数：基函数仅与节点有关而与被插函数无关！容易验证，

Ln(xi)=f(xi),i=0,1,2,…,n.n次Lagrange插值多项式：

因此n次Lagrange插值多项式还可表示成例4.1.4

已知插值点

(-2.00,17.00),(0.00,1.00),(1.00,2.00),(2.00,17.00),

求三次插值，并计算f(0.6)。解先计算4个节点上的基函数：三次Lagrange插值多项式为：

f(0.6)≈L3(0.6)=-0.472.

n次插值多项式的误差定理4.1.3

设Ln(x)是[a,b]上过插值点(xi,f(xi)),i=0,1,2,…,n的n次Lagrange插值多项式，节点xi两两互异，若f(x)∈Cn+1[a,b],则∀x∈[a,b],存在ζ=ζ(x)∈[a,b],使得

Lagrange插值的优缺点

优点：形式整齐、规范，理论上保证插值的存在唯一性。

缺点：计算量大，重复计算多，不具有承袭性。

Newton插值因此，每加一个节点时，只附加一项上去即可。有再继续下去待定系数的形式将更复杂一阶差商：f(x)关于点x0，x1的一阶差商记为f[x0,x1]，差商及其性质二阶差商：f(x)关于点x0，x1，x2的二阶差商记为f[x0,x1,x2],一般地，k阶差商f[x0,x1,…,xk]

定义为：

性质1

k阶差商f[x0,x1,…,xk]可表成节点上函数值f(x0),

f(x1),…,f(xk)的线性组合，即

例如，k=2时，性质2

各阶差商具有对称性,即改变差商中节点的次序不会

改变差商的值。设i0,i1,…,ik为0,1,…,k的任一排列,则

由性质1知，任意改变节点的次序，只改变公式右端求和的次序，故其值不变。例如,由定义知，性质3

若f(x)为n次多项式，则一阶差商f[x,xi]为n

−1次多项式。由定义性质4若f(x)在[a,b]存在n+1阶导数，xi∈[a,b],

i=0,1,…,n,固定x∈[a,b],则n+1

阶差商与导数

存在如下关系：

令x=xi,则分子为0,说明分子中含有因子x

−

xi,与分母约去。解

例对

f(x)=x7−x4+3x+1，

求

f[20,21]，f[x,20,21,…,26]和f[x,20,21,…,27]。利用差商与导数的关系（性质4）！显然，

f(7)

(x)=7!,f(8)

(x)=0,由性质4得由差商的定义

一阶差商是由节点上函数值定义的，二阶差商是由一阶差商定义的，…，依此构造差商表：i

xif(xi)一阶差商二阶差商

三阶差商

…n阶差商0

x0f(x0)1

x1f(x1)f[x0,x1]2

x2f(x2)f[x1,x2]f[x0,x1,x2]3

x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]………………n

xnf(xn)f[xn−1,xn]f[xn−2,xn−1,xn]f[xn−3,…,xn]…

f[x0,x1,…,xn]差商的计算

n次Newton插值公式插值误差为：由插值的唯一性，Ln(x)=Nn(x)。因此，Newton插值是Lagrange插值的另一种表示形式。他们的误差也相同，即当f(x)∈Cn+1[a,b]时，有故得差商的性质4例给定四个插值点(−2,17),(0,1),(1,2),(2,19),计算N2(0.9),N3(0.9)。解首先列差商表i

xif(xi)f[xi

−1,xi]f[xi

−2,xi

−1,xi]f[xi

−3,xi

−2,xi

−1,xi]0

−2

171

01-82

12133

2191785/4所以，N2(0.9)=17−8(0.9+2)+3(0.9+2)×0.9=1.63;N3(0.9)=N2(0.9)+1.25×0.9(0.9+2)(0.9−1)=1.30375.差分及其性质一般地，m阶差分定义为1.

线性性质，例如差分的重要性质2.

若f(x)

是m次多项式，则3.差分值可由函数值算出，即函数值可由差分值算出，即由Rn(x)的表达式得4.各阶差分之间有如下关系5.差商和差分有如下关系函数的差分可以列成如下向前差分、向后差分和中心差分表向前差分、向后差分表中心差分表等距节点Newton插值1.Newton前插公式

Newton前插公式插值余项为2.Newton后插公式插值余项为插值多项式与被插函数的逼近程度同分点的数目和位置有关。一般地，分点越多，逼近程度越好，但也有例外。例4.4.1分段线性插值不同次数的Lagrange插值多项式的比较图Runge现象：插值多项式在插值区间上发生剧烈的震荡。它揭示了高次插值多项式存在的缺陷。产生的原因：误差由截断误差和舍入误差两部分组成，而在插值的计算过程中，舍入误差可能会扩散或放大。n越大，端点附近抖动越大由于高次多项式插值很可能产生Runge现象，在多项式插值中一般不宜选取高次多项式。分段线性插值给定

N+1个插值点：(xi，yi)，i=0,1,2,…,N.过这N

+1个点，可作折线函数P(x)=IN(x)：称之为函数f(x)的分段线性插值。分段线性插值函数也可以写成基函数的形式：其中基函数

li(x)为非负的且局部非零（称为局部支撑性）的分段线性函数：可以看出，当节点加密时，分段线性插值函数与被插函数的函数值有很好的近似性。例

已知函数在区间[0,5]上取等距插值节点（如下表），求区间上分段线性插值函数，并利用它求出近似值。xi012345yi10.50.20.10.058820.03846解:

在每个分段区间上，于是，实际值:当n=7时，

P(4.5)=0.04762270321996当n=10时，P(4.5)=0.04705882352941由此可见，对于光滑性要求不高的插值问题，分段线性插值的效果非常好！计算也简单!0.04705882352941定理4.4.1设函数

f(x)∈C[a,b]，则有如下收敛性：定理4.4.2设函数

f(x)∈C2[a,b]，则例4.4.2

已知

计算

f(1.2),f(3.3).解第五章

函数最佳逼近基本概念

正规方程组算法及其收敛性

离散最小二乘逼近

最佳平方逼近一般最小二乘拟合多项式对于离散数据:(xk,yk),k=1,2,…,m,用n(n<m)次多项式来拟合曲线。设多项式的系数是下述极小值问题的解：一阶必要条件：直接计算易得故或称为正规方程组。可表示为例5.1.4

用二次多项式函数拟合如下数据:xi-3-2-10123yi4230-1-2-5解设p(x)=a0+a1x+a2x2,形成正规方程组：m=7.约定直接计算有：方法一一般地，为定义在X上的广义多项式，记为定义残差的平方和：最小二乘问题为：求解极小值问题正规方程组便可化为：将其表示成矩阵形式例5.1.6

用给定数据，求经验公式f(x)=a+bx3.

x=-3-2-124

y=14.38.34.78.322.7解

约定直接计算得法方程于是法方程组为：所求经验公式为：f(x)=10.675+0.137x3.函数的最佳平方逼近上述问题等价于求多元函数的最小值。由多元函数取极值的必要条件得于是有上述方程组称为正规方程组。也可以写为例5.2.1解取基函数为建立正规方程组：根据内积公式，可得正规方程组为：所求拟合函数为：第六章

数值微积分基本概念

代数精度算法及其收敛性Newton-Cotes求积公式

复化梯形公式和复化辛普森公式两点微分公式和三点微分公式

定义

设有近似式则称该近似式具有m次的代数精度。代数精度也称代数精确度代数精度容易验证：梯形求积公式的代数精度为1，Simpson求积公式的代数精度为3.例试确定下面积分公式中的参数使其代数精确度尽量高.解因此所以该积分公式具有3次代数精确度。例求以下微分公式的代数精度解故代数精度为2.对于一般的n阶插值型求积公式由误差公式可知，其代数精度至少为n.对于Newton－Cotes求积公式，我们有：定理定理Newton-Cotes求积公式在微积分中，定积分是Riemann和的极限，即数值积分就是取定积分极限中的有限项的和，即其中，xk称为积分节点,Ak称为积分系数。我们的任务就是确定积分系数Ak

,使

I[f]≈In[f].最常用的方法就是用插值多项式近似代替被积函数

f(x)来确定Ak.得数值积分公式：截断误差为：（1）基本求积公式Newton-Cotes求积公式是指等距节点下使用Lagrange插值多项式建立的数值求积公式。各节点为：其中而因此有令n阶Newton-Cotes求积公式Newton-Cotes公式的余项(误差)即有注意是等距节点Newton-Cotes求积公式可化为：

Cotes系数与积分区间无关，仅与n和k有关。表

Cotes系数(n=1,2,…,8)下面列出两个低阶Newton-Cotes公式及其余项Cotes系数为：求积公式为：称为梯形求积公式（或两点公式）

梯形求积公式及其余项

积分中值定理：连续、可积不变号故梯形公式的余项为：几何意义：直边梯形代替曲边梯形

Cotes系数为：求积公式为：抛物线（Simpson）求积公式及其余项上式称为