Воеводин Вл. В. Численные методы, параллельные вычисления и информационные технологии
Подождите немного. Документ загружается.
A ∈ C
m×n
U,V
k
U ∈ C
m×k
V ∈ C
n×k
kA−UV
∗
k
F
6 ε
A
k m n
m n
O(mn)
A
A ∈ C
m×n
A = UΣV
∗
, U
∗
U = V
∗
V = I, Σ = (σ
1
, . . . , σ
p
),
p = (m, n) U ∈ C
m×p
V ∈ C
n×p
{σ
k
} U
k
V
k
k U V
Σ
k
Σ k
B: B=k
kA − Bk
2
F
= kA − U
k
Σ
k
V
k
∗
k
2
F
= σ
2
k+1
+ ··· + σ
2
p
. (1)
k
k σ
2
k+1
+···+
σ
2
p
6 ε
A
A
∗
A
A
∗
A
A
q
1
q
2
, . . . , q
k
, . . .
Q
k
k
ε
T
k
=
ω
1
t
∗
1
t
1
t
∗
k−1
t
k−1
ω
k
A
∗
AQ
k
= Q
k
T
k
+ q
k+1
t
k
e
T
k
, (2)
Q
∗
k
Q
k
= I Q
∗
k
q
k+1
= 0
T
k
= R
∗
k
R
k
R
k
=
ρ
1
τ
∗
1
τ
∗
k−1
ρ
k
P
k
= AQ
k
R
−1
k
(2) P
k
P
k
(2) R
−1
k
AQ
k
= P
k
R
k
,
A
∗
P
k
= Q
k
R
k
∗
+ q
k+1
τ
k
e
k
∗
,
(3)
τ
k
= t
k
ρ
−1
k
(3) (2)
τ
k
q
k+1
A
∗
p
k
− q
k
ρ
k
∗
ρ
k
p
k
Aq
k
− p
k−1
τ
∗
k−1
t
k
τ
k
ρ
k
A
kA − P
k
R
k
Q
k
∗
k
2
F
= kAk
2
F
− kR
k
k
2
F
. (4)
(3)
A − P
k
R
k
Q
k
∗
= A − AQ
k
Q
k
∗
= AQ
kO
Q
∗
kO
,
Q
kO
Q
k
Q
n P
k
A [ Q
k
Q
kO
] = [ P
k
P
kO
]
R
k
S
0 T
,
S = P
∗
k
AQ
kO
T = P
∗
kO
AQ
kO
kA − P
k
R
k
Q
k
∗
k
2
F
= kAQ
kO
Q
∗
kO
k
2
F
= (AQ
kO
Q
∗
kO
Q
kO
Q
∗
kO
A
∗
)
= kAQ
kO
k
2
F
= kP
k
S + P
kO
Tk
2
F
=
(P
k
S + P
kO
T)
∗
(P
k
S + P
kO
T)
= kSk
2
F
+ kT k
2
F
= k
R
k
S
0 T
k
2
F
− kR
k
k
2
F
.
kA − P
k
R
k
Q
k
∗
k
2
F
= (A
∗
A) − T
k
. (4
′
)
T
k
(4
′
)
λ
1
λ
2
, . . . , λ
n
A
∗
A
µ
1
µ
2
, . . . , µ
ps
T
s
p
v
1
∈ C
n×p
p
A
∗
A λ
p
> λ
p+1
θ := σ (q
∗
1
v
1
) >
0
T
s
λ
k
> µ
k
> λ
k
− ε
k
2
, k = 1, . . . , p,
ε
2
k
= (λ
k
− λ
n
)
2
θ
T
2
s−1
1+γ
k
1−γ
k
, γ
k
=
λ
k
− λ
p+1
λ
k
− λ
n
.
(5)
T
s−1
s − 1
T
k
q
k
p
k
q
k
= p
k−1
(A
∗
A)q
1
A
∗
A V
Λ ϕ = V
∗
q
1
Q
k
= V [ ϕ p
1
(Λ)ϕ . . . p
k−1
(Λ)ϕ ] ,
n
X
µ=1
|ϕ
µ
|
2
p
j
(λ
µ
) p
k
(λ
µ
) = q
∗
j
q
k
= δ
kj
.
S
{p(x)} K
p(x) > 0 ∀x ∈ K p(x) 6≡ 0
S(p) > 0
|ϕ
1
|
2
+ ··· + |ϕ
n
|
2
= 1 S(p) ≡
P
n
µ=1
|ϕ
µ
|
2
p(λ
µ
)
[λ
n
, λ
1
]
2n − 2
ρ
k
(z)
{p
k
}
S ρ
k
(z)
−1
=
P
k
j=1
|p
j
(z)|
2
ρ
k
(z) =
P
k
6k
P
k
(z)=1
S(|P
k
|
2
).
ρ
j
(λ) 6
P
n
µ=1
|ϕ
µ
|
2
P
2
j
(λ
µ
)
P
j
j
1 λ
T
k
=
k
X
µ=1
n
X
j=1
|ϕ
j
|
2
λ
j
|p
µ−1
(λ
j
)|
2
=
n
X
j=1
|ϕ
j
|
2
λ
j
ρ
k−1
(λ
j
)
>
k
X
j=1
|ϕ
j
|
2
λ
j
ρ
k−1
(λ
j
)
>
k
X
j=1
|ϕ
j
|
2
λ
j
P
n
µ=1
|ϕ
µ
|
2
P
2
k,j
(λ
µ
)
,
P
k,j
(λ) j = 1, . . . , k k − 1
λ
j
1
n
X
µ=1
|ϕ
µ
|
2
P
2
k,j
(λ
µ
) 6 |ϕ
j
|
2
+
n
X
µ=1, µ6=j
|ϕ
µ
|
2
λ∈K
j
|P
k,j
(λ)|
2
,
K
j
= [λ
n
, λ
j+1
] ∪ [λ
j−1
, λ
1
]
P
k,j
k 1 λ
j
Z
k,j,n
T
k
>
k
X
j=1
λ
j
|ϕ
j
|
2
|ϕ
j
|
2
+ (1 − |ϕ
j
|
2
)Z
2
k,j,n
.
ε
⋆
k
=
P
n
j=k+1
λ
j
k A
kA − P
k
R
k
Q
k
∗
k
2
F
6 ε
⋆
k
+
k
X
j=1
λ
j
Z
2
k,j,n
|ϕ
j
|
2
. (6)
q
1
A
A
k A
(6)
//
//