计算方法-总复习

计算方法——总复习第1章绪论误差的概念误差的传播注意的问题相对误差误差相对误差限：相对误差的绝对值的上界有效数字如果近似值x*的误差限是某一位的半个单位，该位到x*的第一位非零数字共有n位,我们称x*有n位有效数字。有n位。则其相对误差限为定理1设近似值有效数字定义：用x*表示x的近似值，并将x*表示成若其误差限,则称x*具有n位有效数字,这里m

是整数,a10.绝对误差限相对误差限n为有效数字m为科学计数法中的误差的传播误差的传播注意的问题注意避免两个相近数的相减

避免除数的绝对值远小于被除数的绝对值防止大数“吃掉”小数第2章方程求根二分法迭代法牛顿切线法割线法将区间一分为二。若

f(x0)=0,

则

x0就是方程的根,否则判别根

在

x0

的左侧还是右侧。

内有方程的根。

设

f(x)在区间[a,b]上连续,

则[a,b]若

则

∈(a,x0

),令a1=a,b1=x0;若

则

∈(x0,b),令a1=x0

,b1=b。取[a,b]的中点二分法二分法将方程

f(x)=0

化为等价方程然后在隔根区间内取一点

x0

，按下式计算计算结果生成数列迭代法定理2

若方程之根的某邻域0<L<1，使内存在,且存在正常数则迭代过程在

的邻近为

p阶收敛。(1)若为线性收敛；则迭代过程在的邻近(2)若定理3之根,在

的邻域

U内有连续的

p阶导数，则

设

为牛顿切线法1、当为单根时，牛顿迭代法在根的附近至少是二阶收敛的；2、当为m重根时，牛顿迭代法在根的附近是线性

收敛的。定理设在满足则方程在上有且只有一个实根，由牛顿法迭代公式计算得到的近似解序列收敛于方程的根双点割线法或记忆割线法收敛阶为单点割线法单点割线法在单根附近是线性收敛的。第3章线性方程组求解高斯消元法高斯主元素消元法高斯——若当消元法矩阵分解向量与矩阵的范数、误差分析迭代法、雅可比、高斯—塞德尔迭代法高斯消元法其中lik=aik(k)/akk(k),

k=1,2,…,n,i=k+1,k+2,…,n。高斯消元法定理1

如果在消元过程中A的主元素(k=1,2,…,n),则可通过高斯消元法求出Ax=b

的解.定理2

Ax=b

可用高斯消元法求解的充分必要条件是：系数矩阵A的各阶顺序主子式均不为零.高斯主元素消元法列主元素消元法第k步先选列主元aik(k),其次将aik(k)（行对换）换到akk(k)的位置上,再消元，其中第k步先选主元aij(k),其次将aij(k)（行、列对换）换到akk(k)的位置上,再消元,其中二完全主元素消元法

P15,2题高斯—若当消元法

在高斯消元过程中，先将主元素化为1，而后将主元所在列的其它元素均化为零，最后将系数矩阵化为单位矩阵I，无需回代就可求得原方程的解，此法称为高斯—约当消元法。高斯-若尔当消元法的运算量比高斯消元法大。矩阵分解定理1

若矩阵A非奇异，则A能分解为LU的充分必要条件是A的顺序主子式不为0。定理2

若非奇异矩阵A有LU分解,则此分解是唯一的。LU分解法a11a12a1k

a1n

u11u12u1k

u1n

第1框a21a22a2k

a2n

l21u22u2k

u2n第2框

ak1ak2

akk

akn

lk1lk2

ukk

ukn第k框

an1an2ankann

ln1ln2

lnk

unn第n框Ly=b

Ux=y

Ly=bUx=yLDLT

(Cholesky)分解法要求：矩阵A对称且其顺序主子式均不为0。Ly=bLTx=D-1y

Ly=bLTx=D-1y平方根法（LLT

分解法）要求：矩阵A对称正定,其顺序主子式均大于0。Ly=bLTx=y

Ly=b

LTx=y追赶法要求：A为三对角矩阵。交替计算Ly=dUx=y①非负性

||x||0

，等号仅当x=0时成立；②齐次性对任何实数

,||

x||=||·||x||；③三角不等式

||x+y||||x||+||y||；则称||x||为向量x的范数。定义1

对任意n维向量x

Rn，若对应非负实数

||x||，满足向量的范数向量的范数设x=(x1

,x2

,…,xn)T

，常用的向量范数有它们分别叫做向量的-范数、1-范数、2-范数、p-范数（0<p<+）。-范数1-范数2-范数p-范数定义2

对任意n阶方阵A=(aij)nn，若对应一个非负实数||A||

，满足①非负性

||A||

0

且||A||=0当且仅当A=0；②齐次性对任意实数

,||

A||=||

||A||；③三角不等式对任意两个n阶方阵A与B,有||A+B||||A||+||B||；④相容性

||AB||||A||||B||则称||A||

为矩阵A的范数。矩阵的范数常用的矩阵范数有它们分别叫做矩阵的-范数、1-范数、2-范数。（矩阵的行范数）（矩阵的列范数）矩阵的范数（矩阵的谱范数）定义3

设n阶方阵A=(aij)nn的特征值为i(i=1,2,…,n),称为A的谱半径。定理1(特征值上界)设n阶方阵A=(aij)nn，则有即A的谱半径不超过A的任何一种范数.定理2

设为与某种向量范数相容的特征向量，则定义2设A是非奇异矩阵,称数condv(A)

=||A-1||v||A||v(v=1,2或)为矩阵A的条件数

.

(1)cond∞(A)=||A-1||||A||;

(2)A的谱条件数：通常使用的条件数,有

条件数的性质:

(1).对任何非奇异矩阵,都有condv(A)

≥1.事实上

condv(cA)

=condv(A).

(2).设A为非奇异矩阵且c≠0(常数),则

(3).如果A为正交矩阵,则cond2(A)

=1;如果B为非奇异矩阵,A为正交矩阵,则

cond2(AB)

=cond2(BA)

=cond2(B).迭代法把矩阵A分解成矩阵N和P之差，A=N-P

，其中N为非奇异矩阵，于是，方程组

Ax=b便可以表示成其中建立迭代公式定理11）

迭代格式

x(k+1)=Bx(k)

+f

收敛

limBk=O；2）

迭代格式

x(k+1)=Bx(k)

+f

收敛

(B)<1。雅可比迭代法记矩阵A=D-L-U

，其中于是雅可比迭代法可写为矩阵形式其Jacobi迭代矩阵为B1=BJ=D-1(L+U)建立迭代格式高斯——塞德尔迭代法其G-S迭代矩阵为B2=BG=(D-L)-1U于是高斯—塞德尔迭代法可写为矩阵形式定义1

设n阶矩阵A=(aij)n×n，如果

则称矩阵A为行（或列）严格对角占优。或

定理3若矩阵A行（或列）严格对角占优，则解线性方程组Ax=b的Jacobi

迭代法和Gauss-Seidel

迭代法均收敛

。

定理4若A为正定矩阵，则方程组Ax=b的Gauss—Seidel迭代法收敛。第4章特征值和特征向量——适用大型稀疏矩阵幂法：求最大特征值及其对应特征向量的一种向量迭代法。反幂法：求最小特征值及其对应特征向量的一种向量迭代法。原点平移法当k充分大时,有其中mk是向量yk中绝对值最大的第一个分量.这时xk分量的模最大为1.幂法收敛速度取决于比值,比值越小,收敛越快.反幂法因为A-1的计算比较困难，所以解方程组先对A进行LU分解A=LU,此时反幂法的迭代公式为当k充分大时,有原点平移法引进矩阵B=A-pI.其中p为参数，设A的特征值为i，则对矩阵B的特征值为i-p

，而且A,B的特征向量相同.其他步骤同幂法或反幂法。第5章代数插值拉格朗日插值多项式Newton插值多项式Hermite插值分段低次插值反插值拉格朗日基函数：拉格朗日插值多项式利用拉格朗日基函数式li(x),构造多项式余项：牛顿插值法为函数f(x)在点x0,x1,…,xk的k阶差商：（列表计算）牛顿插值多形式为：xk函数值一阶差商二阶差商三阶差商...

x0x1

x2

x3...

f(x0)

f(x1)f(x2)f(x3)...

f[x0,x1]

f[x1,x2]

f[x2,x3]

...

f[x0,x1,x2]

f[x1,x2,x3]

...

f[x0,x1,x2,x3]

......差商表差商的性质性质2差商与节点的排列次序无关，差商的对称性：

f[x0,x1,x2,...,xn]=f[x1,x0,x2,...,xn]=…=f[x1,x2,...,xn,

x0

]性质1

差商可以表示为函数值的线性组合，即性质3

若f(x)在[a,b]上存在n阶导数,且节点x0,x1,…,xn∈[a,b],则至少存在一点[a,b]

满足下式差分设插值节点为等距节点,即xk=x0+kh(k=0,1,…,n)的情形，这里h称为步长.一般地，n阶差分分别称为函数f(x)在点xk处的n阶向前差分和n阶向后差分.（一般列表计算）

一般来说，如果要计算x0附近的f(x)，用牛顿前插公式；如果要计算xn附近的f(x)，用牛顿后插公式.由给定函数表计算各阶差分可由差分表给出.函数值一阶差分二阶差分三阶差分四阶差分...

f(x0)

f(x1)f(x2)f(x3)f(x4)...

f0

(f1)

f1

(f2)

f2

(f3)f3

(f4)...

2f0

(2f2)

2f1

(2f3)2f2

(2f4)...

3f0

(3f3)

3f1

(3f4)...4f0

(4f4)......牛顿前插公式牛顿后插公式Hermite插值法且与x有关)分段低次线性插值法分别作线性插值得,在每个子区间[xi,

xi+1]已知则P(x)就是区间[a,b]上的分段线性插值函数.其中分段低次Hermite插值法[xi,xi+1]作埃尔米特插值，得已知在每个子区间其中如用拉格朗日插值多项式对上表做反插值有反插值的余项为反插值第6章数值拟合和数值逼近最小二乘超定方程组一般最小二乘拟合具体的做法是求p(x)使最小二乘法基本原理最小二乘法这个线性方程组称为法方程组或正规方程组.超定方程法定理x*是Ax=b的最小二乘解的充要条件为x*是ATAx=ATb

的解.这里ATAx=ATb是关于x1,x2,…,xn的线性方程组，称为正规方程组或法方程组.一般最小二乘法记即有方程组的矩阵乘法形式为几类经适当变换化为线性拟合求解的曲线拟合方程及变换关系拟合函数类型变量代换化成线性后函数y=aeb/x

(a>0)y*=lny,x*=1/xy*=a*+bx*y=1/(a+be-x)x*=e-x,y*=1/yy*=a+bx*

y=1/(ax+b)y*=1/yy*=b+axy=x/(ax+b)y*=1/y,x*=1/xy*=a+bx*y2=ax2+bx+cy*=y2y*=ax2+bx+cy=1/(ax2+bx+c)y*=1/yy*=ax2+bx+cy=x/(ax2+bx+c)y*=x/yy*=ax2+bx+cy=a+b/x+c/x2x*=1/xy*=a+bx*+cx*2还有一些其它的函数也可以通过变换得到线性函数.第7章数值积分和数值微分牛顿—柯特斯复合求积公式高斯求积公式数值微分梯形公式(中)矩形公式定义1如果求积公式(1)对所有次数不超过m的多项式都精确成立；(2)至少对一个m+1次多项式不精确成立，则称该公式具有m次代数精度.代数精度定理7.1一个求积公式具有m次代数精度的充要条件是该求积公式：(2)对xm+1不精确成立。(1)对xk(k=0,1,…,m)精确成立；牛顿—柯特斯称为n阶牛顿－柯特斯公式,其中称为柯特斯系数.(k=0,1,…,n)柯特斯系数表(书p176有n=8的表)定理7.3n阶牛顿-柯特斯公式的代数精度至少为当n为偶数当n为奇数

(2)若

f(x)C4[a,b],则Simpson公式余项为

牛顿-柯特斯公式不稳定。定理7.4(1)若

f(x)C2[a,b],梯形公式余项为复合求积公式1.复合梯形公式2.复合辛卜生公式高斯求积公式适当选取求积节点xk,可使其具有2n+1次代数精度.这种求积公式称为高斯(Gauss)求积公式,简称高斯公式,其求积节点xk称为高斯点.高斯求积公式是稳定的，也是收敛的.高斯－勒让德求积公式的节点和系数表n节点数求积节点xk求积系数Ａk