扰动误差分析.docx
- 文档编号:10899004
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:18
- 大小:210.07KB
扰动误差分析.docx
《扰动误差分析.docx》由会员分享,可在线阅读,更多相关《扰动误差分析.docx(18页珍藏版)》请在冰点文库上搜索。
扰动误差分析
第2章线性代数方程组数值解法I:
直接法
考虑方程组Axb(ARnn非奇异,bRn且b0)(261)
设A有误差A,b有误差b,则因此引起解x有误差,即有扰动方程组
(AA)(xx)bb
现在来研究如何通过A和b对x的影响作出估计。
定理2.6.1设方程组(2.6.1)中A,b分别有扰动A,b,因而解向量有误差x;
AHA
1
Ia1!
IIA
(A
(A
证明
(A)x(A)(x)
两边取范数有
INI||AlbIIAl州
(1)A精确,即A0,b有扰动b,从而A(xx)bb
⑵A有扰动A,b精确,即b0,这时(AA)(xx)b
xIA1AA
x1A*A
当IA1A很小时,上式可近似表示为
2•条件数与病态方程组
定义2.6.1设A为非奇异矩阵,称数A1A即
cond(A)AA|
为矩阵A的条件数。
矩阵A的条件数的一些基本性质:
(1)任何非奇异矩阵A,对任一算子范数||均有
cond(A)1
cond(A)cond(A)
cond(A)cond(A)
cond(U)21
(4)设1与n为A按模最大和最小的特征值,则
cond(A)
特别地,若AAt(即A对称),则cond(A)—
n
若A对称正定,则cond(A)2
证明略
证明:
A1b,综合两式得估计式两端
1_IHI|r||_
cond(A)b|IaIIa1]b||x
例2.6.1
用平方根法解线性方程组
_10787一
r厂
_32—
7565
©
23
86109
33
-75910-
•
-31™
粗看来没什么特别,可以验证其特确解为
现虚假设方程组右端项可能有谖总比如设b有抚动Bb,即
(32+0,1?
23-0.1,33+0.1,31-0.1)T
再解方程组,剧有扰动解
=(黑2厂口・6,15t-Ll)r
可见b的微小扰动bb对解X有相当大的影响6x.为此,检查方程组的条件
數.采用2-条件数・由A算出牯征值
入1=30/887入严3”58入严厲8431入严Q.01015注意方程组是一个对称组*可得方程组条件数
A30.2887叭⑷尸厂°丽严亦a
可见方釋组相当病态+上述出St的规象实厲有因,解方程组时注意检瓷条件数,碉有助于避免盲目地计算・遠里.由5b=(0,1,-Q.1,0,1厂0,1)『^5x=(8.2厂13.6r3.5厂2・1)T可算出
IbII5=60,025
于是强实际相对误差
II5bII=0*21x1=2
I5xII,16,397
世=8,198
IIxIIn2
II5xtt3=16,397
而按定理牯计
Lllb<2984sJ2LL.
IXll2务切…lbl[2
0L2
9,943
由此看出,理论分析与实际计算基本一致.
3•事后误差估计
定理2.6.2设方程组Axb,A非奇异,A非奇异,b0,x是精确解,x
是近似解,剩余向量rbAx,则有估计式
例题讲解2
例题2.1对方程组Ax=b,A非奇异不一定能作顺序Gauss消去过程,或者说,A非奇异不一定有LU分解。
证这类命题只需举一个反例即可。
反例要尽可能简单,这里可考虑2阶、元素为1或0。
构造反例一般要经过多次“失败-修正”过程。
10
考虑A=,易见A非奇异。
显然,顺序Gauss消去过程的01
第1步就不能进行。
从LU分解来看,设有A=LU分解,则有
10=1bc=bc
01a1dabacd
于是有b=0和ab=1同时成立,这就自相矛盾了。
例题2.2设方程组
0.001
2.000
3.000
x1
1.000
1.000
3.712
4.623
x2
=2.000
2.000
1.072
5.643
x3
3.000
试手算(或辅以计算器)分别用
(1)顺序Guass消去法
(2)列主元Gauss消去法
(3)直接三角分解法求解,要求计算中取4位有效数字,最后结果舍入成3位有效数字。
上述方程组用4位浮点数进行计算而舍入为3位有效数字的精确解为:
*T
x*(0.4900.05100.368)T
解
(1)顺序Gauss消去过程计算有
1.000
l211000
0.001
2.000
3.000
A
b1.000
3.712
4.623
1.000
第1步消元21
l312000
2.000
1.072
5.643
1.000
0.001
2.000
3.000
1.000
2004
3005
1002
第2步消元l321.977
4001
6006
2006
0.0012.000
3.000
1.000
2004
3005
1002
5015
2006
回代过程求解并舍入得
x
0.399,0.0998,0.400,T
3)令A=LU,用
(2)列主兀Gauss消去过程计算有
0.001
2.000
3.000
1.000
Ab
1.000
3.712
4.623
2.000
选主元a31
2.000换行E1E
2.000
1.072
5.643
3.000
2.000
1.072
5.643
3.000
第1步消元
l21
0.5000
1.000
3.712
4.623
2.000
l31
0.0005
0.001
2.000
3.000
1.000
2.000
1.072
5.643
3.000
3.716
1.802
0.5000
选主元,仍为
a22
2.001
3.003
1.002
2.000
1.072
5.643
3.000
3.716
1.802
0.5000
第2步消元
l32
0.6300
1.868
0.6870
回代过程求解并舍入
0.0513,0.368T
x0.490,
Doolittle分解计算得
1
与精确解x*比较可见,列主元Gauss消去法的解精确度最高;其他两种方法的解精确度较差,但彼此接近(这正好符合两种方法实质是一样的情况)。
例题2.3Gauss消去法的一种自然而又简单的改进是所谓Gauss-Jordan消
(k)(k)
去法。
先考虑顺序Gauss消去法过程的情形。
它只是把a这一列中a下面的
kkkk
(k)(k)
元素消为0,而Gauss-Jordan消去过程则把a这一列元素的a以外全部消去为kkkk
(k)
0,并且约化akk=1。
为此,需进行n步消元,第n列也消为只剩下一个元素1,
其余均为0(因此,△n工0在这里也是必要的)。
这样一来,不用回代过程,
方程组的解就在b的位置上。
现在依据上述导引,做
(1)试用Gauss-Jordan消肖去法解方程组
111x.
2x2=0
211X3
(2)试给出Gauss-Jordan算法的核心部分。
(3)由上述两点能得出什么思考?
解
(1)用增广矩阵的演变来描述求解过程
11111111
1220—0111
21110313
10021002
—0111—0102
00260013
于是有x=(2,2,3)
(2)Gauss-Jordan消肖去法算法的核心部分为:
对k=1,2,…,n,做
a^
akjJ-(j=k,k+1,…,n,n+1)
akk
对k=1,2,…,nAi工k,做
aijJaj-ajkakj(j=k+1,…,n,n+1)
输出解Xi=ai,n1(i=1,2,…,n)
(4)从上述做法可引发如下思考:
Gauss-Jordan消去过程自然也可考虑加上选主元和换行的技巧;就计算量而言,Gauss-Jordan消去过程
3
显然要大(可推导其乘除运算次数为—级,而顺序Gauss消去过
2
3
程乘除运算次数为—级)。
因此,用Gauss-Jordan消去法解方程组
3
并不经济。
但它有什么用途呢?
这又引出一个新的思考。
例题2.4设LRn*n为非奇异下三角阵,试
(1)写出求解方程组Lx=f的计算公式;
(2)统计上述求解过程的乘除法次数;
(3)给出求L1的计算公式。
解
(1)这是解下三角方程组的递推公式:
x1f1/l11
i1
x2(filijxj)/lii(i2,3,,n)
j1
(2)乘除法运算,第一式有1次,第二次i=2时有2次,…,i=n时有n次,故上述公式的乘除运算次数有
1+2+…+n=n(n1)/2(次)
(3)因L非奇异,L1存在,且由矩阵知识知L1也为下三角阵,记L1(Vj),
由LL1I,即
l11
V11
1
LL1l21l22
V21
V22
1
ln1ln2
lnnVn1
Vn2
Vnn
1
考虑
I的对角线元素
,显然
有li
iVii
1(i
1,2,,n),于
1/lii(i
1,2,,n)。
考虑I对角线以下的元素,即对
i2,3,
n;j
1,2,
i
1,则有
n
likVkj
k1
i
likVkj
k1
lik
Vkj
lijVij
0
于是得
Vij(likVkj)/lii(i
2,3,,n;j
1,2,
i
1)
是得
Vii
例题2.5设A=(aj)Rn*n对称,其顺序主子式厶i工0(i=1,2,…,n),试
(1)证明分解A=LDL存在唯一,其中L为单位下三角阵,D为对角阵;
(2)写出利用此分解求解方程组Ax=b的步骤(这称为改进的平方根法);(3)用改进的平方跟法解方程组
3
3
5
x1
10
3
5
9
x2
16
5
9
17
x3
30
解
(1)由A的顺序主子式不为零,故存在唯一分解式A=LU,L为单位下三角
阵,U为上三角阵。
改写A=LU=LDU0,D为对角阵,U0为单位上三角阵。
由
A对称,有A=AT=(LDU0)T=U;(DLt),又由分解的唯一性即得Uj=L或
U0=Lt,于是代入可得A=LU=LDUo=LDLt存在唯一。
(2)将A=LDLT代入Ax=b得LDLTx=b,令DLTx=y(即LTx=D-1y),则Ly=b,改进平方根法如下:
1)将A直接分解为A=LDLT,即求出L,D;
2)求解下三角方程组Ly=b,得y;
3)求解上三角方程组LTx=D-1y,得x。
(3)令A=LDLT
可见改进平方根法比原始平方根法避免了开方运算;另一方面,改进平方根法对满足LU分解条件的对称矩阵(不一定要正定)都适用。
例题2.6已知方程组Ax=b的系数矩阵形如:
其中A的n-1阶、主子距阵,*为其实数,。
试设计一个求解上述方程组基于追赶的解决方案
解把A记为
A=
V,U€R.对Bn1用追赶法可
Bn1Tu
其中Bn-1为A的n-1阶(对三角型)主子距阵,作三角分解
11
2
d11
222
1d22
Bn1=
p21
=P-Q
n2
n2n2
1
n2
n1n1
dn2
再对A作三角分解,
A=
Bn1
P0QZPQPWT10dn=WTQWZTd
其中Z€RN-1)由下三角方程组Pz=v求出,WR(N-1)由方程组WTQ=uT(即下三角方程组QtW=U)求出,dn由WT+dn=n算出。
由此,求解上述方程组的解决方案如下:
(1)对n1用追赶法求出P,Q;
(2)解下三角方程组Pz=v,求出z;
(3)解下三角方程组QtW=U求出W;
(4)计算dn=n-WTz;
(5)前推解下三角方程组
(6)回代解上三角方程组
aibi
xi
c2a2
b2
x2
例题2.7设三对角方程组Ax=b,其中A=c3
a3b3
x3
x=
cnianibni
xni
cnan
xn
d1
d2
dn1
dn
⑴试建立A的顺序主子式k(k=1,2,…,n)的逆推公式
解补充记0=1,则显然有
般地,猜想
k=akkibkiCkk2(k=3,4,…,n)
用归纳法证明:
当k=2时,上式成立。
现假设有则由
aibi
c2a2
b2
k=
=akkibkickk2
ck2ak2bk2
ckiakibki
ckak
可知上述猜想成立。
综上所述,可得递推公式:
1a1
kakk1bk1ckk2(k23...,n)
(2)由Ax=d的第一个方程可得
b1d1
X1X2
即得x1由x2表示的关系式。
将它代入第二个方程c2x1a1x2b2x3d2,又可得
X2由X3表示的关系式……如此继续代入,直到第n1个方程,于是有如下形式
的关系式
XkfkXk1gk(k=2,3,…,n1)⑵
整理可得
与关系式
(2)比较得
代入
(1)得X1仏2g1,可见
(2)式对k=1也成立;又由⑷中取k=n,则可得fn0,
gn虫Cn£^1,而由于方程组Ax=d的第n个方程CnXn1anXndn可以写成anfn1an
CnXn1anXnbnXn1dn,其中g0,Xn10,从而上述的代入可直至第n
个方程,也就是说
(2)和(3)式对kn也成立,于是有Xngn。
综上所述,可得解三对角方程组的新算法如下:
b1d1
—,gi—
aia
dk2,3,...,n1)
ckfk1ak
dnCngn1
anfn1an
Xngn
XkfkXk1gk(kn1,n2,...,2,1)
例题2.8证明下列两个命题(其中?
均为算子范数):
(1)设BRn*n且B1,贝U
1I土B非奇异;
2IB1]。
1B
⑵设ARn*n非奇异,BRn*n奇异,则
1AB
cond(A)|A|
证明
(1)这个命题通常被作为矩阵范数和谱半径理论中的一个通用定理,它与本章2.6节提供的定理2.61和定理2.62组成最基本的3个定理。
现用反证法证明命题
(1)。
若I土B奇异,则齐次方程组(I±B)x=0有非零解~0,且~B~,
于是有II~iIII和1。
即有IIBmax醫仁这与假设
B1矛盾,可知IB非奇异。
关于
(2),由
I丨B1I丨B1丨BB||lIBP]|H|IIB|B
移项整理
IIb壯||b|||i|
由假设||B1及注意到I1II21,于是可得
IB1
1
II
1IBI
(2)对需要证明的不等式,自然与上述提及的3个基本定理联系起来。
可以尝试
一下,但会发现难以联系得起来。
先分析:
要证的不等式即为
1冒condA1||AB|||A1|注意到|ABA]||AB|A],故若能证明下式即可
1|ABA1
用反证法,设1ABA1不成立,即有|ABA11,利用命题
(1),则有
111
I(AB)AIIBABA
非奇异,从而BA1AB也非奇异,这与题设B奇异矛盾,于是可知1ABA1
成立,进而1|AB|A成立,于是提出的不等式成立。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 扰动 误差 分析