数值分析总结.pdf

文档介绍：该【数值分析总结 】是由【小辰GG】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【数值分析总结 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
数值分析复****总结
第二章数值分析基本概念
教学内容:

误差、误差限、相对误差、相对误差限和有效数字的定义及相互关系;
误差的来源和误差的基本特性;
误差的计算(估计)的基本方法。

数值分析中的病态和不稳定性问题介绍;
病态问题和不稳定算法的实例分析。

避免相近二数相减;
避免小分母;
避免大数吃小数;
选用稳定的算法。

数值分析的任务
数值分析是研究求解各类数学问题的数值方法和有关理论的学科
数值分析的过程
构造算法、使用算法、分析算法

误差概念和分析
误差的定义:
设x是精确值,p是近似值,则定义两者之差是绝对误差:
xp
a
由于精确值一般是未知的,因而Δ不能求出来,但可以根据测量误差或计算情况估计它的上限
|x-p|
称为绝对误差限。
相对误差定义为绝对误差与精确值之比

a
rx:.

a称为相对误差限
rx
误差的来源:
舍入误差
将无限位字长的精确数处理成有限位字长近似数的处理方法称为舍入方法。带来舍人误差。
有效数字
对于
a=a0a1…+1…am+n(a0≠0)
的近似数,若|Δ|≤-n,
则称a为具有m+n+1位有效数字的有效数,其中每一位数字都叫做a的有效数字。有效数和
可靠数的最末位数字称为可疑数字
有效数位的多少直接影响到近似值的绝对误差与相对误差的大小。
推论1对于给出的有效数,其绝对误差限不大于其最末数字的半个单位。
x10m
12n
1
xx10mn
2
推论2对于给出的一个有效数,其相对误差限可估计如下:
x10m
12n
5
(x)10n
ra
1
例:计算y=lnx。若x20,则取x的几位有效数字可保证y的相对误差<%?
截断误差
用数值法求解数学模型时,往往用简单代替复杂,或者用有限过程代替无限过程所引起的误差。
数值计算的算法问题
“良态”问题和“病态”问题
在适定的情况下,若对于原始数据很小的变化δX,对应的参数误差δy也很小,则称该数学问题是良态
问题;若δy很大,则称为病态问题。
病态问题中解对于数据的变化率都很大,因此数据微小变化必将导致参数模型精确解的很大变化。
数学问题的性态完全取决于该数学问题本身的属性,在采用数值方法求解之前就存在,与数值方法无关。
稳定算法和不稳定算法
如果用数值方法计算时,舍入误差对结果影响小的算法称为稳定算法。否则称为不稳定算法。
数值计算应注意的问题:.
第三章线性方程组求解的数值方法
教学内容:

消元法的实现过程;
主元问题。

矩阵LU分解的一般计算公式;
利用LU分解的线性方程组求解方法;
Cholesky分解;
Matlab的Cholesky分解函数。

向量范数及其性质;
矩阵函数及其性质;
常用范数形式。

迭代求解的思路;
Jacobi迭代法;
高斯_赛德尔迭代法;
松弛法;
迭代法的收敛性。

线性方程组解的误差分析;
条件数和方程组的病态性。
消元法:
问题:
消去法是按照系数矩阵的主对角线上的元素(主元)进行消元。从而可能出现:
(1)某个主元为零,导致消元过程无法进行。
(2)当某个主元的绝对值很小时,计算结果误差很大。
定理:
若A的所有顺序主子式均不为0,则高斯消元无需换行即可进行到底,得到唯一解。
全主元消去法
每一步选绝对值最大的元素为主元素。
|a|max|a|0;
ijij
kkki,jn
列主元消去法
省去换列的步骤,每次仅选一列中最大的元。
|a|max|a|0
ik,kik
kin:.
矩阵三角分解法
由Gauss消去法加上列主元(或全主元)有LU分解:
ALU
1uuu

11121n
l1uu
21222n
Lll1U
3132

lll1u

n1n2n(n1)nn
由:
aaaa1000uuuu
1112131411121314
aaaal1000uuu
2122232421222344
aaaall1000uu
3132333431323334
aaaalll1000u

4142434441424344
uuuu
11121314
luluuluuluu
21112112222**********
lululululuululuu
31113112322231133223333114322434
lululululululululuu
41114112422241134223433341144224433444
得到计算公式:
ua,j1,,n
1j1j
lau,i2,,n
i1i111
对k2,3,,n计算
k-1
ualujk,,n
kjkjkmmj
m1
k-1
l(alu)/uik1,,n
ikikimmkkk
m1
算法:
(1)解Y:yb
11
yi-1y
bl,i2,3,,n
iiijj
j1
(2)解x:xyu
nnnn
i1
xyuxu,

iiijjii
jn
in1,,1
Cholesky分解:
回顾对称正定矩阵的定义和性质。
由对称性推出::.
ALLT
定理:
设矩阵A对称正定,则存在非奇异下三角阵L使得ALLT。若限定L对角元为正,则分解唯一。
Matlab中的Cholesky分解函数:
chol()
向量和矩阵的范数
为了研究线性方程组近似解的误差估计和迭代法的收敛性,引进向量(矩阵)的范数的概念。
向量范数
定义:
Rnx,yRn
空间的向量范数||·||对任意满足下列条件:
(正定性)
(1)||x||0;||x||0x0
(齐次性)
(2)||x||||||x||C
(三角不等式)
(3)||xy||||x||||y||
常用范数:
n
xx
1i
i11/2
n
xx2

2i

i1
n1/p
xxp

pi

i1
xmaxx
i
i
定理:
Rn
上一切范数都等价。
矩阵范数
定义:
Rnm空间的向量范数||·||对任意满足下列条件:A,BRnm:.
(1)||A||0;||A||0A0

(2)||A||||||A||
(3)||AB||||A||||B||
(4)*||AB||||A||·||B||
常用矩阵范数:
Frobenius范数:
nn
||A|||a|2
Fij
i1j1
由向量范数||·||导出关于矩阵ARnn的p范数:
p
||Ax||
||A||maxpmax||Ax||
p||x||p
x0||x||p1
p
n
||A||max|a|
特别有:(行和范数)
ij
1in
j1
n
||A||max|a|(列和范数)
11jnij
i1
||A||(ATA)(谱范数)
2max
谱半径:
矩阵A的谱半径记为
(A)=max,其中为A的特征根。
ii
i
定理:
对任意算子范数||·||有
(A)||A||
定理:
若A对称,则有
A(A)
2
定理:
若矩阵B对某个算子范数满足||B||<1,则必有:.
(1)(IB)可逆。
1
(2)IB1
1||B||
解线性方程组的迭代法
研究内容:
如何建立迭代公式?
收敛速度?
向量序列的收敛条件?
误差估计?
思路:
对线性方程组Axb
其中A(a)非奇异矩阵,b(b,,b)T
ijnn1n
构造其形如xMxg
的同解方程组,其中M为n阶方阵,gRn。
任取初始向量x(0)Rn,代入迭代公式
x(k1)Mx(k)g(k=0,1,2,)
产生向量序列{x(k)},当k充分大时,以x(k)作为
方程组Axb的近似解,这就是求解线性方程组
的单步定常线性迭代法。M称为迭代矩阵。
收敛问题::.
定义:设{A(k)}为n阶方阵序列,A为n阶方阵,如果
limA(k)A0
k
其中为矩阵范数,则称序列{A(k)}收敛于矩阵A,记为
limA(k)A
k
定理:设{A(k)}(a(k))(k1,2,),A(a)均为n阶方阵,
ijij
则矩阵序列{A(k)}收敛于矩阵A的充要条件为
lima(k)a(i,j1,2,,n)
kijij
证明略。
定理表明,向量序列和矩阵序列的收敛可以归结为对应
分量或对应元素序列的收敛。
若按x(k1)Mx(k)g产生的向量序列{x(k)}收敛于向量x,
则有xlimx(k1)lim[Mx(k)g]Mxg
kk
即x是方程组Axb的解。
雅可比(Jacobi)迭代法
高斯—塞德尔迭代法
迭代法的收敛性
定理:设A为n阶方阵,则limAk0的充要条件为(A)1。
k
证:必要性:若limAk0
k
由矩阵收敛的定义知limAk0又因(A)A
k
0(Ak)[(A)]kAk
由极限存在的准则,有lim[(A)]k=0所以(A)1。
k
1(A)
充分性。若(A)1,取0,由上一定理
2
知,存在一种矩阵范数,使得
1(A)
A(A)1
2
而AkAk,limAklimAk0limAk0.
kkk
:.
推论2松弛法收敛的必要条件是02。
证:设松弛法的迭代矩阵M有特征值,,,。
12n
因为det(M)[(M)]n
12n
由定理,松弛法收敛必有det(M)1
又因为det(M)(DL)1(1)DU
1
(DL)1
aaa
1122nn
(1)DU(1)naaa
1122nn
det(M)(1)n102。
迭代法收敛与否只决定于迭代矩阵的谱半径,与初始向
量及右端项无关。对同一方程组,由于不同的迭代法迭代
矩阵不同,可能出现有的方法收敛,有的方法发散的情形。
设有线性方程组Axb,下列结论成立:
,则
Jacobi迭代法和Gauss-Seidel迭代法均收敛。
,01,则松弛法收敛。
,则松弛法收敛的充要条件为
02。
1012210

上两例中:A1102B121

115012

A为严格对角占优阵,故Jacobi与Gauss-Seidel迭
代均收敛。B为非严格对角占优阵,但为对称正定
阵,=。
误差估计::.
定理:设有迭代格式x(k1)Mx(k)g,若M1,
(k)*
x收敛于x,则有误差估计式
Mk
x(k)x*x(1)x(0)
1M
证:因(M)M1,故IM0,于是
1*
(IM)存在,方程组xMxg有唯一解x,
且x*(IM)1g。从而有
x(k)x*M(x(k1)x*)Mk(x(0)x*)
Mk[x(0)(IM)1g]
Mk(IM)1[(IM)x(0)g]
Mk(IM)1[x(0)x(1)]
定理:设有迭代格式x(k1)Mx(k)g,若M1,
(k)*
x收敛于x,则有误差估计式
M
x(k)x*x(k)x(k1)
1M
证:因x(k)x*M(x(k1)x*)M[x(k1)(IM)1g]
M(IM)1[x(k1)Mx(k1)g]M(IM)1(x(k1)x(k))
x(k)x*M(IM)1x(k1)x(k)
M
x(k)x(k1).
1M
当M不太接近1时,可用x(k)x(k1)作为停机准则。
误差分析:
问题的提出:
设A为非奇异矩阵,非齐次方程组
Axb
的准确解为x,当A和b有一个小的扰动A,b时,
方程组有准确解xx,即
(AA)(xx)bb
我们需要研究x与A,b之间的关系。
:.
b有扰动,A无扰动
||x||||b||
(||A||||A1||)
||x||||b||
A有扰动,b有扰动
||x||||(IA1A)1||||A1||||A||||x||
||x||||A1||||A||
(IA1A)1A1A
||x||1||A1A||
A
||A1||||A||
||A||A
||A1||||A||
A||A||
1||A1||||A||
||A||
A有扰动,b有扰动
类似推导,可得
A
||A1||||A||
||x||||A||bA
()
||x||A||b||||A||
1||A1||||A||
||A||
定义:
条件数:cond(A)=||A–1||||A||
条件数与所取的矩阵范数有关。
常用的条件数有:
()1cond(A)AA1

(ATA)
(2)cond(A)AA1max
222(ATA)
min
条件数的性质:
,cond(A)1
0,有
cond(cA)cond(A)
,cond(A)1
2
结论:
当条件数很大时,方程组Ax=b是病态问题;当条件数较小时,方程组Ax=b是良态问题。
实际计算中,病态矩阵的判断::.
在消元过程中,出现小主元。
矩阵行列式的值很小,或有某些行(列)近似线性相关。
矩阵元素间的数量级相差太大。
第四章函数的数值逼近

插值多项式的存在唯一性;
插值基函数和插值多项式的一般形式;
插值的误差分析;
多项式插值的Runge现象。

分段线性插值;
Hermite插值和分段Hermite插值。

样条插值的定义;
三次样条函数的计算;
Matlab中的插值函数。

曲线拟合的最小二乘法法;
多项式拟合方法;
Matlab中的多项式拟合函数;

权内积;
正交多项式的最佳平方逼近。
插值问题:
函数解析式未知,或计算复杂,用函数p(x)去近似代替它,使得
p(xi)=yi(i=0,1,2,…,n)
函数p(xi)称为插值函数。
x0,x1,…xn称为插值节点或简称节点。
插值节点所界的区间称为插值区间。
p(xi)=yi称为插值条件。
多项式的插值问题
构造n次多项式:.
Pn(x)=a0+a1x+a2x2+…+anxn
使满足Pn(xi)=yi(i=0,1,2,…,n),
讨论的主要内容:
如何求出插值函数;
插值函数的存在性;
收敛性和误差估计。
拉格朗日插值
插值多项式的存在唯一性:
过n1个点(x,y),i0,1,2,...,n,作多项式
ii
Paax...axn
n01n
可转化为解线性方程组:
aax...axny
010n00
aax...axny
011n11
...
aax...axny
01nnnn
只需证明a的存在且唯一。
i
xn...x1
00
xn...x1
A10
由


xn...x1

nn
det(A)(xx)0
ij
ij
结论
通过n+1个节点的n阶插值多项式唯一存在。
一次和二次插值公式:
一次基函数
xx
l(x)k1
kxx
kk+1
xx
l(x)k
k1xx
k1k
二次基函数:.
(xx)(xx)
l(x)kk1
k1(xx)(xx)
k1kk1k1
(xx)(xx)
l(x)k1k1
k(xx)(xx)
kk1kk1
(xx)(xx)
l(x)k1k
k1(xx)(xx)
k1k1k1k
拉格朗日插值多项式的一般形式:
n1个基函数l(x),l(x),...l(x),满足:
01n
()1l(x)是n次多项式。
i
(2)l(x)1,且l(x)0,(ki)
iiik
(xx)...(xx)(xx)...(xx)
l(x)0i1i1n
i(xx)...(xx)(xx)...(xx)
i0ii1ii1in
插值公式:
P(x)yl(x)yl(x)...yl(x)
n0011nn
n
yl(x)
kk
k0
插值的误差分析:
设函数yf(x)的n阶导数f(n)(x)在[a,b]上连续,
f(n+1)(x)在(a,b)存在,节点axx...xb,
01n
P(x)是n次拉格朗日插值多项式,则对任意的x[a,b],
n
插值余项
f(n+1)()
R(x)f(x)P(x)(x)
nn(n1)!n1
思考:
是否插值的节点越多,多项式插值越精确?
是否多项式的阶数越高,多项式插值越精确?
演示:多项式插值的Runge现象
分段低次插值
随着插值结点数增加,插值多项式的次数也相应增加,而对于高次插值容易带来剧烈振荡,
带来数值不稳定。为了既要增加插值结点,减小插值区间,以便更好的逼近被插值函数,又要不
增加插值多项式的次数以减少误差,我们可以采用分段插值的办法。:.
分段线性插值
xxxx
I(x)k1fkf(xxx)
hxxkxxk1kk1
kk1k1k
若用插值基函数表示,则:
n
I(x)=fl(x)x[a,b]
hjj
j0
其中:l(x)满足l(x)
jjkjk
xx
j1xxx

xxj1j
jj1
xx

l(x)j1xxx
jxxjj1
jj1

0x[x,x]
j1j1

收敛性:
f(x)I(x)l(x)f(x)fl(x)f(x)f
hkkk1k1
(l(x)l(x))(h)(h)
kk1k
其中,(h)maxf(x')f(x'')
x'x''h
当f(x)C[a,b],则lim(h)0
h0
因此,只要f(x)C[a,b],
limI(x)f(x)
h
h0
埃尔米特插值
求解的思路:
H(x)aax...ax2n1
2n1012n1
求插值基函数(x),(x),(i0,1,...,n)
ii
满足:
()1(x),(x)是2n1次多项式。
ii
(2)(x),且'(x)0,(i,k0,1,...,n)
iki,kik
'
(3)(x),且(x)0,(i,k0,1,...,n)
iki,kik
于是:
n
H(x)[y(x)m(x)]
2n1iiii
i0:.
利用拉格朗日插值基函数
(xx)...(xx)(xx)...(xx)
l(x)0i1i1n
i(xx)...(xx)(xx)...(xx)
i0ii1ii1in
得到

n1
(x)12(xx)l2(x)
iixxi
k0
ik
ki
同理,由(x)在x(ik)处函数族和导数值均
ik
为0,且(x)0,故
ii
(x)=c(xx)l2(x)
iii
由于'(x)1,有'(x)cl2(x)1
iiiiii
(x)=(xx)l2(x)
iii
n
H(x)[y(x)m(x)]
2n1iiii
i0
Hermite插值的唯一性:
Hermite插值的余项
函数yf(x)的2n+2阶导数f(2n+2)(x)在(a,b)存在,
对任意的x[a,b],
Hermite插值余项
f(2n+2)()
R(x)f(x)H(x)2(x)
2n1(2n2)!n1
分段Hermite插值:
三次样条插值
第五章数值积分

线性和二次求积公式;
求积公式的代数精度;:.
求积公式的误差分析;
复合求积公式;
高斯求积公式;
MATLAB中的数值积分函数。

积分方程的数值求解的思路分析;
积分方程的数值求解方法介绍。
n次代数精度
bn
f(x)dxAf(x)
akk
k0
对于任意不超过n次的代数多项式都准确成立,而对某一个m+1次代数多项式不成立,。
梯形公式
bba
f(x)dx[f(a)f(b)]
a2
(ba)3
截断误差:R[f]=-f()(ab)
1
12
辛普森公式
b-aab
S=[f(a)4f()f(b)]
62
:
复化求积公式:
复化梯形公式
hn1
Tf(a)f(b)2f(akh)

n2
k1
ba
截断误差:R(f)hM=maxf(x)
,M2
N
axb
复化辛普森公式
hn1n1
S[f(a)4f(x)2f(x)f(b)]
n6k1/2k
k0k0
ba
截断误差:R[f]h4MMmaxf()(x)
N
28804
,axb
:.
高斯求积公式
定义
bn
求积公式f(x)dxAf(x)含有2n2个
akk
k0
待定参数x,A(k0,1,,n),适当选择这些参
kk
数使其具有2n+1次代数精度。这类求积公式
称为高斯公式。x(k0,1,,n)是高斯点。
k
bn
高斯求积公式f(x)dxAf(x),
akk
k0
1dn(x21)n
节点为P(x)的零点(高斯点)
n2nn!dxn
f(n)()
b
其余项:R(x)(x)dx
n(n)!n
a
Matlab积分函数
函数名功能
quad采用Simpson计算积分。精度高,较常用
quad8采用8样条Newton-Cotes公式计算积分。精度高,最常用
trapz采用梯形法计算积分。精度差,速度快
积分方程的数值求解
Fredholm积分方程:
b
y(t)k(t,s)y(s)dsf(t)
a
求解思路
用数值积分代替积分
bn
由k(x,s)y(s)dsAk(x,x)y(x)
kkk
ak1
n
y(x)Ak(x,x)y(x)f(x)
kkk
k1:.
n
y(x)Ak(x,x)y(x)f(x)
kkkkkk
k1
(IK)yf
第六章常微分方程初值问题

基本理论和方程离散化;
欧拉方法

教学要点:
欧拉公式:
y(x)yyhf(x,y)
kkkkk(k,,,...,n)

xxkh
k
局部截断误差是O(h2).
改进欧拉公式:
预报值yyhf(x,y)
k1kkk
h
校正值yy[f(x,y)f(x,y)]
k1k2kkk1k1
hh
或表示成:yy[f(x,y)f(x,yf(x,y))]
k1k2kkk1k2kk
平均形式:

yyhf(x,y)
pkkk

yyhf(x,y)
ckkp


y(yy)
kpc
局部截断误差是O(h3).
龙格—库塔方法:.
一般地,RK方法设近似公式为
p
yyhcK

n1nii
i1

Kf(x,y)
1nn

i1
Kf(xah,y