2024年数值分析大作业.docx

第二次计算试验：SVD及其应用

梁杰存310739航博143

措施

求矩阵A奇异值分解一种途径是求解ATA的特性值，但由于舍入误差轻易丢掉小奇异值。因此一般先将矩阵上双对角化，既构造正交阵和,使得QTAW=B(upper-bidiagnal)。这一过程可以通过逐次Household变换或逐次Given’s变换完毕，尚有一种基于待定系数法思想的Lanczos算法。由于Linpack中SVD算法需要输入上双对角矩阵，本文采用Lanczos算法实現上双对角化。

隐式零移位QR法（implicitzero-shiftQR）

与老式移位QR迭代算法不一样，隐式零移位QR算法不进行移位，并且第一步构造右乘Given’s变换矩阵GR(1,2)将上双对角矩阵B的(1,2)位置上的元素消零，而不是老式措施中引入一种非零元素。但这一步也許会使本来為零的b12变為非零。第二步左乘Given’s阵GL(1,2)使得為0，但也許会使為零b13变為非零。与上述环节类似，将b13变為0后也許会使b23非零。如下图所示，反复上述环节最终将恢复為上双对角矩阵，既完毕一步隐式零移位QR迭代。反复迭代，矩阵B将趋近与对角阵阵，对角元既特性值。

图SEQ图\*ARABIC1隐式QR迭代

分而治之(Divide-and-conquer)

分而治之算法将上双对角阵B提成有两个互相独立对角块矩阵与另一矩阵之和，既：

B=

因此矩阵B的特性值与矩阵D+ρuuT的特性值相似，其中D=

det

由于D-λI非奇异，则det

在每个di与d

试验计算

取10个对角阵Σi(i=1,2,…10)(表2.1)，由QR分解得到两个正交阵U,V，从而得到10个矩阵Ai=V*Σi*UT(i=1,2,…10)。

其中矩阵构造以及上双对角化运用Matlab编程实現，SVD算法选择LAPACK函数库中的SDBSQR和SDBSDC函数，分别对应隐式QR算法和分而治之算法，并在Matlab中编译调用。

表2.1对角阵Σ的性质

矩阵

维数M×N

奇异值分布

rank(

σ

阐明

Σ

100×100

100,99,…3,2,1

100

100

100到1的等差数列

Σ

100×100

1.299,1.298

100

1.2

1.299

Σ

100×100

1,

100

1.2

1到1.2-99

Σ

100×100

[50,50,49,49,…,1,1]

100

50

50到1等差并反复

Σ

100×100

1,1,...

100

1.2

1到1.2-49

Σ

100×100

[50,49,…2,1,0,…0]

50

50

50到1等差，其他為0

Σ

100×100

1,

50

1.2

1到1.2-49等比，其他為

Σ

500×500

[500,499,…,2,1]

500

500

500到1的等差数列

Σ

10×10

[

10

10

1015

Σ

10×10

[1,…

10

10

1到10-15

计算成果如表2.2以及表2.3所示，分别列出隐式QR迭代和分而治之算法的计算時间，最小奇异值和对应左右特性向量的误差，以及奇异值和左右特性向量的平均误差。

表2.2隐式QR迭代计算成果

time（s）

σ

u

|v

σ

u

|v

A1

0.0043

0.2116

1.4065

1.4114

0.6314

0.6838

1.0299

A2

0.0024

3.36E+04

1.4000

1.4001

9.24E+03

1.4386

1.4142

A3

0.0025

3.30E+04

1.4000

1.4001

9.07E+03

1.4386

1.4142

A4

0.0038

0.1619

1.4249

1.4260

1.07E-06

1.5461

1.5461

A5

0.0017

26.1991

1.3930

1.3936

1.8739

1.3730

1.4000

A6

0.0044

Inf

1.4203

1.4195

Inf

1.4400

1.3615

A7

0.0018

Inf

1.4197

1.4201

Inf

1.3894

1.4142

A8

0.1016

1.6151

7.0681

7.0752

0.7067

0.5133

0.9912

A9

0.0008

3.45E+05

0.1441

0.1473

3.84E+06

1.1091

1.4142

A10

0.0001

3.25E+05

0.1499

0.1473

3.87E+06

1.6643

1.4142

表2.3分而治之算法计算成果

ti