MatrixComputations-3
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (168.66 KB, 11 trang )
cơ sở đại số tuyến tính cho giá trị
kỳ dị
1 Các khái niệm.
1.1 Chuẩn vector.
Định nghĩa 1.1.1 Cho a
1
, . . . , a
n
∈ R
m
, khi đó
span{a
1
, . . . , a
n
} = {
n
j=1
β
j
a
j
: β
j
∈ R}
Định nghĩa 1.1.2 (Chuẩn vector) Một chuẩn vector trên R
n
là một hàm f :
R
n
→ R thỏa:
(i)f(x) ≥ 0 x ∈ R
n
, (f(x) = 0, x = 0)
(ii)f(x + y) ≤ f(x) + f(y) x, y ∈ R
n
(iii)f(αx) = |α|f(x) α ∈ R, x ∈ R
n
Ký hiệu, x - chuẩn x.
x
p
= (|x
1
|
p
+ ··· + |x
n
|
p
)
1
p
p ≥ 1 : p-chuẩn của x.
Các chuẩn quan trọng:
x
1
= |x
1
| + ··· + |x
n
|
x
2
= (|x
1
|
2
+ ··· + |x
n
|
2
)
1
2
= (x
T
x)
1
2
x
∞
= max
1≤i≤n
|x
i
|
* Các tính chất của chuẩn vector.
(i) Bất đẳng thức Holder:
|x
T
y| ≤ x
p
y
q
,
1
p
+
1
q
= 1.
(ii) Bất đẳng thức Cauchy-Schwartz:
|x
T
y| ≤ x
2
y
2
.
(iii) Mọi chuẩn trên R
n
đều tương đương, i.e. nếu .
α
và .
β
là các chuẩn
trên R
n
, thì tồn tại c
1
và c
2
sao cho
c
1
x
α
≤ x
β
≤ c
2
x
α
.
Khi đó, một dãy hội tụ trong α - chuẩn thì cũng hội tụ trong β - chuẩn.
68
1.2 Chuẩn Ma trận.
Định nghĩa 1.2.1 Cho A là một ma trận cấp m× n, ta có các khái niệm sau
ran(A) = {y ∈ R
m
: y = Ax, x ∈ R
n
} - Miền giá trị (range) của A.
null(A) = {x ∈ R
n
: Ax = 0} - không gian rỗng (null space) của A.
Nếu A = {a
1
, . . . , a
n
} là một phân hoạch cột, thì
ran(A) = span{a
1
, . . . , a
n
}.
Định nghĩa 1.2.2 (Đạo hàm) Cho A(α) = (a
ij
(α))
m×n
. Nếu (a
ij
(α)) là các
hàm khả vi theo biến α, thì ma trận A(α) có đạo hàm
A
(α) =
d
dα
A(α) = (
d
dα
a
ij
(α)) = (a
ij
(α))
Giả sử A(α) ∈ R
m×r
, B(α) ∈ R
r×n
là các ma trận của các hàm khả vi theo
biến α, khi đó
d
dα
[A(α)B(α)] = [
d
dα
A(α)]B(α) + A(α)[
d
dα
B(α)]
Định nghĩa 1.2.3 (Chuẩn ma trận) Hàm f : R
m×n
→ R được gọi là một
chuẩn ma trận nếu thỏa:
(i) f(A) ≥ 0 A ∈ R
m×n
, (f(A) = 0, A = 0).
(ii) f(A + B) ≤ f(A) + f (B) A, B ∈ R
m×n
.
(iii) f(αA) = |α|f(A) α ∈ R, A ∈ R
m×n
.
Ký hiệu, A - chuẩn của ma trận A.
Chuẩn ma trận được dùng nhiều trong đại số tuyến tính số đó là Frobenius-
chuẩn:
A
F
=
m
i=1
n
j=1
|a
2
ij
|.
p - chuẩn:
A
p
= sup
x=0
Ax
p
x
p
= sup
x=0
A(
x
x
p
)
p
= max
x
p
=1
Ax
p
.
Nhận xét. AB
p
≤ A
p
B
p
.
Ta nói rằng các chuẩn f
1
, f
2
, f
3
trên R
m×q
, R
m×n
, R
n×q
là tương hỗ nhất quán
(mutually consistent) nếu với mọi A ∈ R
m×n
, B ∈ R
n×q
, ta có
f
1
(AB) ≤ f
2
(A)f
3
(B).
69
Nói chung, không phải tất cả các chuẩn đều thỏa: AB ≤ AB.
Chẳng hạn, nếu A
= max|a
ij
| và
A = B =
1 1
1 1
,
thì AB
> A
B
.
p - chuẩn có một tính chất quan trọng: với mọi A ∈ R
m×n
và x ∈ R
n
ta có
Ax
p
≤ A
p
x
p
. Tổng quát hơn, với mọi chuẩn vector .
α
trên R
n
và .
β
trên R
m
, ta có
Ax
β
≤ A
α,β
x
α
với
A
α,β
= sup
x=0
Ax
β
x
α
.
Khi đó, ta nói .
α,β
là phụ thuộc (subordinate) .
α
và .
β
. Do {x ∈ R
n
:
x
α
= 1} là compact và .
β
là liên tục, ta nhận được
A
α,β
= max
x
α
=1
Ax
β
= Ax
∗
β
với x
∗
∈ R
n
có α-chuẩn bằng 1.
1.2.1 Các tính chất.
Cho A ∈ R
m×n
ta có các tính chất sau:
A
2
≤ A
F
≤
√
nA
2
max
i,j
|a
ij
| ≤ A
2
≤
√
mn max
i,j
|a
ij
|
A
1
= max
1≤j≤n
m
j=1
|a
ij
|
A
∞
= max
1≤j≤m
n
j=1
|a
ij
|
1
√
n
A
∞
≤ A
2
≤
√
mA
∞
1
√
m
A
1
≤ A
2
≤
√
nA
1
.
70
Nếu 1 ≤ i
1
≤ i
2
≤ m, 1 ≤ ji
1
≤ j
2
≤ n, thì
A(i
1
: i
2
, j
1
: j
2
)
p
≤ A
p
.
Một dãy {A
(k)
} ∈ R
m×n
hội tụ nếu
lim
k→∞
A
(k)
− A = 0.
Định lý 1.2.1 Nếu A ∈ R
m×n
, thì tồn tại z ∈ R
n
,z
2
= 1 sao cho A
T
Az =
µ
2
z, µ = A
2
.
Chứng minh. Giả sử z ∈ R
n
,z
2
= 1 sao cho Az
2
= A
2
. Đặt
g(x) =
1
2
Ax
2
2
x
2
2
=
1
2
x
T
A
T
Ax
x
T
x
Khi đó, ∇g(z) = 0, nên ta nhận được
∂g(z)
∂z
i
= [(z
T
z
n
j=1
(A
T
A)
ij
z
j
− (z
T
A
T
Az)z
i
]/(z
T
z)
2
= 0
⇒
n
j=1
(A
T
A)
ij
z
j
= (z
T
A
T
Az)z
i
⇔
m
i=1
n
j=1
(A
T
A)
ij
z
j
=
m
i=1
(z
T
A
T
Az)z
i
⇔ A
T
Az = (z
T
A
T
Az)z = Az
2
2
Đặt µ = Az
2
= A
2
.
Chú ý. 1 Theo kết quả định lý, A
2
2
chính là nghiệm của phương trình đặc
trưng p(λ) = det(A
T
A − λI) = 0.
Hệ quả 1.2.1 Nếu A ∈ R
m×n
, thì A
2
≤
A
1
A
∞
.
Chứng minh. Nếu z = 0 sao cho A
T
Az = µ
2
z, µ = z
2
, thì
µ
2
z
1
= A
T
Az
1
≤ A
T
1
A
1
z
1
= A
∞
A
1
z
1
.
71
1.2.2 Phép nhiễu và nghịch đảo.
Bổ đề 1.2.1 Nếu F ∈ R
n×n
và F
p
< 1, thì I − F là không suy biến và
(I − F )
−1
=
∞
k=0
F
k
với
(I − F )
−1
p
≤
1
1 − F
p
.
Chứng minh. Giả sử I − F là suy biến. Khi đó, phương trình (I − F )x = 0
có nghiệm x = 0 và Ix
p
= F x
p
suy ra x
p
= F x
p
≤ F
p
x
p
, vậy
F
p
≥ 1 (mâu thuẩn). Vậy I − F là không suy biến.
Xét đồng nhất thức
(
N
k=0
F
k
)(I − F ) = I − F
N+1
.
Do F
p
< 1 và F
k
p
≤ F
k
p
nên lim
k→∞
F
k
= 0.
Như vậy,
( lim
N→∞
N
k=0
F
k
)(I − F ) = I.
Điều đó chỉ ra rằng
(I − F )
−1
= ( lim
N→∞
N
k=0
F
k
) =
∞
k=0
F
k
Và khi đó,
(I − F )
−1
p
=
∞
k=0
F
k
p
≤
∞
k=0
F
k
p
=
1
1 − F
p
.
Theo kết quả định lý, ta có (I − F )
−1
− I
p
≤
F
p
1−F
p
.
Định lý 1.2.2 Nếu A là không suy biến và r = A
−1
E
p
< 1, thì A + E là
không suy biến và (A + E)
−1
− A
−1
p
≤ E
p
A
−1
2
p
/(1 − r).
Chứng minh. Từ A là không suy biến suy ra A + E = A(I − F ), với F =
−A
−1
E. Khi đó, F
p
= r < 1, theo bổ đề trên I − F là không suy biến và
72
