特征值与特征向量

1 幂法 2

2 实对称矩阵的 Jacobi 方法 3

3 镜像对称 Householder 变换 5

3.1 HouseHolder 矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.2 上三角变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.3 QR 方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1

1 幂法

幂法可以计算矩阵按模最大的特征值和对应的特征向量. 假定 𝐴 是要求解的矩阵, 它有特征值和对应的

特征向量

𝐴v

i

= 𝜆

𝑖

v

i

其中假定特征值有大小关系

|𝜆

1

| > |𝜆

2

| > ··· > |𝜆

𝑛

|

如果 𝐴 的特征子空间是完备的, 那么任意一个向量 x 都可以表示为特征向量的线性组合

x =

𝑛

Õ

𝑖=1

𝑐

𝑖

v

i

用矩阵 𝐴 的幂次作用于 x, 可以得到

𝐴

𝑘

x =

𝑛

Õ

𝑖=1

𝑐

𝑖

𝜆

𝑘

𝑖

v

i

若提出 𝜆

𝑘

1

, 则有

𝐴

𝑘

x

𝜆

𝑘

1

=

𝑛

Õ

𝑖=1

𝑐

𝑖



𝜆

𝑖

𝜆

1



𝑘

v

i

当 𝑘 → ∞ 时, 由于 |𝜆

1

| > |𝜆

2

| > · ·· > |𝜆

𝑛

|, 所以



𝜆

𝑖

𝜆

1



< 1, 所以

lim

𝑘→∞

𝐴

𝑘

x

𝜆

𝑘

1

= 𝑐

1

v

1

随便选取一个初始向量 x

0

, 假定它可以写为

x

0

=

𝑛

Õ

𝑖=1

𝑐

𝑖

v

i

那么在迭代次数 𝑘 足够大时, 应有

x

k

= 𝐴

𝑘

x

0

≈ 𝜆

𝑘

1

𝑐

1

v

1

那么

𝜆

1

≈

x

𝒌+1

x

k

若有两个互为相反数的特征值, 即

|

𝜆

1

|

=

|

𝜆

2

|

>

|

𝜆

3

|

>

···

>

|

𝜆

𝑛

|

那么在迭代次数 𝑘 足够大时, 应有

x

k

= 𝐴

𝑘

x

0

≈ 𝜆

𝑘

1

𝑐

1

v

1

+ (−1)

𝑘

𝜆

𝑘

1

𝑐

2

v

2

则有方程组











x

𝒌+1

= 𝜆

𝑘+1

1

𝑐

1

v

1

+ (−1)

𝑘+1

𝜆

𝑘+1

1

𝑐

2

v

2

x

k

= 𝜆

𝑘

1

𝑐

1

v

1

+ (−1)

𝑘

𝜆

𝑘

1

𝑐

2

v

2

求解方程组即可得到 𝜆

1

和 v

1

, v

2

2 实对称矩阵的 Jacobi 方法

假定 𝐴 是一个实对称矩阵, 总可以找到一个正交矩阵 𝑄, 使它对角化

𝑄

𝑇

𝐴𝑄 = Λ =

©



«

𝜆

1

𝜆

2

.

𝜆

𝑛

ª

®

¬

其中 Λ 是一个对角矩阵

假定矩阵有形式

𝑄 = (

˜

e

1

,

˜

e

2

, ··· ,

˜

e

𝑛

)

其中

˜

e

𝑝

= (0, ··· , (第 p 个) cos 𝜃, ··· , (第 q 个) − sin 𝜃, ··· , 0)

𝑇

˜

e

𝑞

= (0, ··· , (第 p 个) sin 𝜃, ··· , (第 q 个) cos 𝜃, ··· , 0)

𝑇

其他均为单位向量. 将 𝐴 写为

𝐴 = (A

1

, A

2

, ··· , A

n

)

那么

𝑄

𝑇

𝐴 =

©



«

e

𝑇

1

A

1

e

𝑇

1

A

2

··· e

𝑇

1

A

n

.

e

𝑇

p

A

1

e

𝑇

p

A

2

··· e

𝑇

p

A

n

.

e

𝑇

q

A

1

e

𝑇

q

A

2

··· e

𝑇

q

A

n

.

e

𝑇

n

A

1

e

𝑇

n

A

2

··· e

𝑇

n

A

n

ª

®

¬

其中

e

𝑇

p

A

j

= cos 𝜃𝑎

𝑝 𝑗

− sin 𝜃𝑎

𝑞 𝑗

e

𝑇

q

A

j

= sin 𝜃𝑎

𝑝 𝑗

+ cos 𝜃𝑎

𝑞 𝑗

那么

𝑄

𝑇

𝐴 =

©



«

𝑎

11

𝑎

12

··· 𝑎

1𝑛

.

𝑎

𝑝1

cos 𝜃 − 𝑎

𝑞1

sin 𝜃 𝑎

𝑝2

cos 𝜃 − 𝑎

𝑞2

sin 𝜃 ··· 𝑎

𝑝𝑛

cos 𝜃 − 𝑎

𝑞𝑛

sin 𝜃

.

𝑎

𝑝1

sin 𝜃 + 𝑎

𝑞1

cos 𝜃 𝑎

𝑝2

sin 𝜃 + 𝑎

𝑞2

cos 𝜃 ··· 𝑎

𝑝𝑛

sin 𝜃 + 𝑎

𝑞𝑛

cos 𝜃

.

𝑎

𝑛1

𝑎

𝑛2

··· 𝑎

𝑛𝑛

ª

®

¬

同样再乘上 𝑄, 第 𝑝 列与第 𝑞 列的元素会同样变化, 而其他元素不变. 记得到的矩阵为 𝐵, 那么

𝑏

𝑖 𝑝

= 𝑏

𝑝𝑖

= 𝑎

𝑝𝑖

cos 𝜃 − 𝑎

𝑞𝑖

sin 𝜃, 𝑖 ≠ 𝑝, 𝑞

𝑏

𝑖𝑞

= 𝑏

𝑞𝑖

= 𝑎

𝑝𝑖

sin 𝜃 + 𝑎

𝑞𝑖

cos 𝜃, 𝑖 ≠ 𝑝, 𝑞

四个交叉点的元素为

𝑏

𝑝 𝑝

= 𝑎

𝑝 𝑝

cos

2

𝜃 + 𝑎

𝑞𝑞

sin

2

𝜃 − 𝑎

𝑝𝑞

sin 2𝜃

𝑏

𝑞𝑞

= 𝑎

𝑝 𝑝

sin

2

𝜃 + 𝑎

𝑞𝑞

cos

2

𝜃 + 𝑎

𝑝𝑞

sin 2𝜃

𝑏

𝑝𝑞

= 𝑏

𝑞 𝑝

= 𝑎

𝑝𝑞

cos 2𝜃 +

𝑎

𝑞𝑞

− 𝑎

𝑝 𝑝

2

sin 2𝜃

希望使得非对角元为零, 即

𝑎

𝑝𝑞

cos 2𝜃 +

𝑎

𝑞𝑞

− 𝑎

𝑝 𝑝

2

sin 2𝜃 = 0

也就是

𝑠 = cot 2𝜃 =

𝑎

𝑞𝑞

− 𝑎

𝑝 𝑝

2𝑎

𝑝𝑞

令 𝑡 = tan 𝜃, 则有

𝑡

2

+ 2𝑠𝑡 − 1 = 0

解之即可, 那么

cos 𝜃 =

1

√

1 + 𝑡

2

, sin 𝜃 =

𝑡

√

1 + 𝑡

2

令

𝑐 =

1

√

1 + 𝑡

2

, 𝑑 =

𝑡

√

1 + 𝑡

2

那么得到的矩阵 𝐵 改变的元素就可以写为

𝑏

𝑖 𝑝

= 𝑏

𝑝𝑖

= 𝑐𝑎

𝑝𝑖

− 𝑑𝑎

𝑞𝑖

, 𝑖 ≠ 𝑝, 𝑞

𝑏

𝑖𝑞

= 𝑏

𝑞𝑖

= 𝑑𝑎

𝑝𝑖

+ 𝑐𝑎

𝑞𝑖

, 𝑖 ≠ 𝑝, 𝑞

𝑏

𝑝 𝑝

= 𝑎

𝑝 𝑝

− 𝑡𝑎

𝑝𝑞

𝑏

𝑞𝑞

= 𝑎

𝑞𝑞

+ 𝑡𝑎

𝑝𝑞

因而

Õ

𝑖

𝑏

2

𝑖𝑖

=

Õ

𝑖

𝑎

2

𝑖𝑖

+ 2𝑎

2

𝑝𝑞

,

Õ

𝑖≠ 𝑗

𝑏

2

𝑖 𝑗

=

Õ

𝑖≠ 𝑗

𝑎

2

𝑖 𝑗

− 2𝑎

2

𝑝𝑞

这说明随着迭代次数的增加

,

对角线上的元素比重会越来越大

,

非对角元其平方和会趋近于零

.

为了使得

效率最高,每次应选择最大的非对角元消去

3 镜像对称 Householder 变换

3.1 HouseHolder 矩阵

𝐻 = 𝐼 − 2𝜔𝜔

𝑇

其中 𝜔 每一列是归一的

3.2 上三角变换

对于一个任意的矩阵

𝐴 = (A

1

, A

2

, ··· , A

n

)

希望有

𝐻

1

𝐴 =

©



«

𝛼

1

∗ ··· ∗

0

𝐴

′

.

0

ª

®

¬

那么对于剩下的部分, 可以再找到一个 𝐻

2

𝐻

2

=

1

𝐻

′

!

它应当消去 𝐴

′

的第一列

𝐻

2

𝐴 =

©



«

𝛼

1

∗ ∗ ··· ∗

0 𝛼

2

∗ ··· ∗

0 0

𝐴

′

.

0 0

ª

®

¬

那么即寻找 𝐻 使得

𝐻x = (𝑥

1

, ··· , 𝑥

−𝑚

, 𝛼, 0, ··· , 0)

𝑇

一直这样下去就能把 𝐴 变为上三角矩阵

𝐻

𝑛−1

𝐻

𝑛−2

···𝐻

1

𝐴 = 𝑅

由于 𝐻 是正交阵, 那么令

𝑄 = (𝐻

𝑛−1

𝐻

𝑛−2

···𝐻

1

)

𝑇

得

𝐴 = 𝑄𝑅

若略加修改 𝑄, 即可将 𝐴 消为 Hessenberg 矩阵

𝐴 = 𝑄𝐻

𝑒

=

©



«

∗ ∗ ∗ ∗ ∗

0 ∗ ∗ ∗ ∗

0 0 ∗ ∗ ∗

0 0 0 ∗ ∗

ª

®

¬

若 𝐴 是一个实对称矩阵, 那么 𝐻

𝑒

将变为一个三对角矩阵

3.3 QR 方法

设 𝐴 是一个 𝑛 阶实矩阵, 对其进行 QR 分解

𝐴 = 𝑄𝑅

做完第一步后, 得到

𝐴

1

= 𝑄

1

𝑅

1

⇒ 𝑅

1

= 𝑄

𝑇

1

𝐴

1

那么令 𝐴

2

为

𝐴

2

= 𝑄

𝑇

1

𝐴

1

𝑄

1

再进行一步 QR 分解, 得到

𝐴

2

= 𝑄

2

𝑅

2

依次进行下去, 即

𝐴

1

= 𝐴,











𝐴

𝑘

= 𝑄

𝑘

𝑅

𝑘

𝐴

𝑘+1

= 𝑄

𝑇

𝑘

𝐴

𝑘

𝑄

𝑘

得到矩阵序列 {𝐴

𝑘

}, 显然它们都是正交相似的, 并且

𝐴

𝑘+1

= 𝑄

𝑇

𝑘

𝑄

𝑇

𝑘−1

···𝑄

𝑇

1

𝐴𝑄

1

𝑄

2

···𝑄

𝑘

记

˜

𝑄

𝑘

= 𝑄

1

𝑄

2

···𝑄

𝑘

,

˜

𝑅

𝑘

= 𝑅

1

𝑅

2

··· 𝑅

𝑘

那么

𝐴

𝑘+1

=

˜

𝑄

𝑘

𝑇

𝐴

˜

𝑄

𝑘

因而

˜

𝑄

𝑘

𝐴

𝑘+1

= 𝐴

˜

𝑄

𝑘

⇒

˜

𝑄

𝑘

𝑇

𝑄

𝑘+1

𝑅

𝑘+1

= 𝐴

˜

𝑄

𝑘

鉴于

˜

𝑄

𝑘

𝑄

𝑘+1

=

˜

𝑄

𝑘+1

, 那么

˜

𝑄

𝑘+1

𝑅

𝑘+1

= 𝐴

˜

𝑄

𝑘

再于两边同乘以

˜

𝑅

𝑘

得到

˜

𝑄

𝑘+1

𝑅

𝑘+1

˜

𝑅

𝑘

= 𝐴

˜

𝑄

𝑘

˜

𝑅

𝑘

⇒

˜

𝑄

𝑘+1

˜

𝑅

𝑘+1

= 𝐴

˜

𝑅

𝑘+1

鉴于

˜

𝑄

𝑘

˜

𝑅

𝑘

= 𝐴

˜

𝑄

𝑘−1

˜

𝑅

𝑘−1

, 那么

˜

𝑄

𝑘+1

˜

𝑅

𝑘+1

= 𝐴

2

˜

𝑄

𝑘−1

˜

𝑅

𝑘−1

以此类推, 得到

𝐴

𝑘

=

˜

𝑄

𝑘

˜

𝑅

𝑘

假定 𝐴 的特征值满足

|

𝜆

1

|

>

|

𝜆

2

|

> ··· >

|

𝜆

𝑛

|

𝐴 可以对角化为

𝐴 = 𝑋 𝐷𝑋

−1

, 𝐷 =

©



«

𝜆

1

𝜆

2

.

𝜆

𝑛

ª

®

¬

这意味着当 𝑘 足够大时, 有矩阵 𝐴

𝑘

的对角元素会趋近于 𝜆

𝑘

. 若 𝐴 是实对称矩阵, 那么 𝐴

𝑘

会收敛到对角

阵

𝐷

.

将

𝑋

写为

LU

分解

𝑋 = 𝐿𝑈