清华大学贾忠孝高值第三次作业参考答案

贾哥的作业

高等数值分析第三章作业参考答案

1.考虑线性方程组Ax=b,其中A是对称正定矩阵.用Galerkin原理求解方程K=L=Span(v),这里v是一个固定的向量.e0=x x0,e1=x x1证明

(e1,Ae1)=(e0,Ae0) (r,v)2/(Av,v),

其中r=b Ax0.v应当取哪个向量在某种意义上是最佳的?

( )

证明.令x1=x0+αv,那么r1=r αAv,e1=e0 αv.由Galerkin原

理,有(r1,v)=0,因此α=(r,v)/(Av,v).注意到r1=Ae1,r=Ae,有(Ae1,v)=0.于是

(e1,Ae1)=(e0 αv,Ae1)=(e0,Ae1)=(e0,Ae0) α(e0,Av)=(e0,Ae0) α(r,v)即( )式成立.由( )式知当v=e0时, e1 A=0最小,即近似解与精确解的误差在A范数意义下最小,算法一步收敛(但是实际中这个v不能精确找到);在最速下降意义下v=r时最佳

.

2.求证：考虑线性方程组Ax=b,其中A是对称正定矩阵.取K=L=Span(r,Ar).用Galerkin方法求解,其中r是上一步的残余向量.

(a)用r和满足(r,Ap)=0的p向量构成K中的一组基.给出计算p的公

式.

解.设p=r+αAr,(r,Ap)=0等价于(Ar,p)=0.解得α=

(Ar,r)/(Ar,Ar

).

(b)写出从x0到x1的计算公式.

解.设x1=x0+β1r+β2p,那么r1=r β1Ar β2Ap,再由Galerkin原

理,有(r1,r)=(r1,p)=0,解得

β1=(r,r)/(Ar,r),

β2=(r,p)/(Ap,p)

.

(c)该算法收敛吗?

贾哥的作业

解.该算法可描述为：

(1)选初始x0∈Rn,计算初始残差r0=b Ax0,ε>0为停机准则；(2)对k=0,1,2,...直到 rk <ε

αk=

(rk,Ark)

;

(Ark,Ark)

pk=rk+αArk;βk=

(rk,rk)

;

(Ark,rk)(rk,pk)γk=;

(Apk,pk)

rk+1=rk βkArk γkApk;xk+1=xk+βkrk+γkpk.

此算法本质上是由CG迭代一步就重启得到的,所以是收敛的,下面给出证法.

设用此算法得到的xk+1=xk+p¯1(A)rk,那么 ek+1 A=

p1∈P1

min ek+p1(A)rk A≤ ek+p¯1(A)rk A= ek p¯1(A)Aek A

≤max|p (λi)| ek A

1≤i≤n

其中0<λ1≤...≤λn为A的特征值,p (t)=1 tp¯1(t)是过(0,1)点的

λ二次多项式.当p 满足p (λ1)=p (λn)= p (λ+)时可使max|p (λi)|达2

1≤i≤n

到最小.经计算可得

(λ1 λn)2

minmax|p (λi)|≤<12p 1≤i≤n(λ1 λn)+8λ1λn

故若令κ=λ1/λn,则

(κ 1)2

ek+1 A≤2 ek A,

κ+6κ+1

方法收敛

.

3.考虑方程组

D Fxb 1 1 = 1 , E D2x2b2

贾哥的作业

其中D1,D2是m×m的非奇异矩阵.取L1=K1=Span{e1,e2,···,em},L2=K2=Span{em+1,em+2,···,en}.依次用(L1,K1),(L2,K2)按讲义46和47页公式

Az =r0

r0 Azm⊥LWTAVym=WTr0

xm=x0+V(WTAV) 1WTr0

各进行一步计算.写出一个程序不断按这个方法计算下去,并验证算法收敛性.用Li=AKi重复上述各步骤.

(0)x1

,令r0=b Ax0,V1=[e1,e2,...,em],V2= 解.对任意给定x0=(0)x2

[em,em+1,...,en].

对Li=Ki情形,依次用(L1,K1),(L2,K2)各进行一步计算：

(L1,K1)z1=V1y1r0 Az1⊥L1

(V1TAV1)y1=V1Tr0,

(1)

(1)

(1)(1)

(L2,K2)z1=V2y2r0 Az1⊥L2

(V2TAV2)y2=V2Tr0, D2y2=V2Tr0

1T

x1=x0 V2D2V2r0(2)

(2)

(2)(2)

D1y1=V1Tr0

1T

x1=x0+V1D1V1r0

得如下算法：

(1)选初始x0∈Rn,计算初始残差r0=b Ax0,ε>0为停机准则；(2)对k=1,2,...直到 rk <ε

求解D1y1=rk 1(1:m);

求解 D2y2=rk 1(m+1:n);

xk=xk 1+V1y1+V2y2;rk=rk 1 AV1y1 AV2y2.

贾哥的作业

收敛性:

1D1

rk=rk 1 A

=

1ED1

1 D2

rk 1

1

FD2

rk 1 Brk 1

1 1

FD2)<1.算法收敛 ρ(B)<1 ρ(ED1

对Li=AKi情形,依次用(L1,K1),(L2,K2)各进行一步计算:

(L1,K1)z1=V1y1∈K1r0 Az1⊥L1=AK1(V1TATAV1)y1=V1TATr0

T

(D1D1+ETE)y1=V1TATr0

T

x1=x0+(D1D1+ETE) 1V1TATr0(1)

(1)

(2)

(1)(1)

(2)

(L2,K2)z1=V2y2∈K2r0 Az1⊥L2=AK2(V2TATAV2)y2=V2TATr0

T

(D2D2+FTF)y2=V2TATr0

T

x1=x0+(D2D2+FTF) 1V2TATr0

(2)

(2)

得如下算法：

(1)选初始x0∈Rn,计算初始残差r0=b Ax0,ε>0为停机准则；(2)对k=1,2,...直到 rk <ε

T

求解(D1D1+ETE)y1=(ATrk 1)(1:m);T求解(D2D2+FTF)y2=(ATrk 1)(m+1:n);

xk=xk 1+V1y1+V2y2;rk=rk 1 AV1y1 AV2y2.

收敛性:

T(D1D1+ETE) 1

rk=rk 1 A (I B)rk 1

算法收敛 ρ(I B)<1 0<λ(B)<2

.

T(D2D2+FTF) 1

ATrk 1

贾哥的作业

4.令

0 13 2 ... ,...A= ... ...... 2

0 13

3 2

1 0 b= .

. . 2

用Galerkin原理求解Ax=b.取x0=0,Vm=Wm=(e1,e2,···,em).对不同的m,观察 b Axm 和 xm x 的变化,其中x 为方程的精确解.

解.对于 b Axm 和 xm x ,都是前n 1步下降趋势微乎其微,到

第n

步突然收敛。

m 1

5.对于m<n,Arnoldi过程产生的向量序列{vi}mr0}的i=1是空间Span{r0,Ar0,···,A

一组标准正交基,而且vm+1⊥Span{r0,Ar0,···,Am 1r0}.

证明.第m(<n)步的Arnoldi过程可表示为

Avm=h1,mv1+h2,mv2+···+hm,mvm+hm+1,mvm+1,

其中v1=r0/ r0 .当m=1时,Av1=h1,1v1+h2,1v2,显然命题成立.

设m=k<n 1时成立,即Span{v1,v2,...,vk}=Span{r0,Ar0,···,Ak 1r0}并且vk+1⊥Span{r0,Ar0,···,Ak 1r0}.那么当m=k+1时,由

Avk=h1,kv1+h2,kv2+···+hk,kvk+hk+1,kvk+1,

知vk+1∈Span{v1,v2,...,vk,Avk} Span{r0,Ar0,···,Akr0},因此

Span{v1,v2,...,vk+1} Span{r0,Ar0,···,Akr0}

,又由于两者都是k+1维的,故Span{v1,v2,...,vk+1}=Span{r0,Ar0,·& …… 此处隐藏：1679字，全部文档内容请下载后查看。喜欢就下载吧 ……