Воеводин Вл. В. Численные методы, параллельные вычисления и информационные технологии
Подождите немного. Документ загружается.
0
l×l
a
l×(n−l)
0
(n−l)×l
b
(n−l)×(n−l)
Ω,
l
L a
1
, . . . , a
l
C
n
. Ω
Ω l
l L.
L l.
A
1
, . . . , A
s
, s = (Ω).
Ω
A
i
=
"
0
l×l
a
i
l×(n−l)
0
(n−l)×l
b
i
(n−l)×(n−l)
#
, i = 1, . . . , s.
A =
a
1
···
a
s
∈ C
(ls)×(n−l)
,
a
i
A
i
,
(A) = n − l.
(A) = r < n − l. n − l − r
∃ F : F
−1
AF =
h
0
(n−l)×(n−l−r)
,
e
A
i
e
A =
a
1
···
a
s
∈ C
(ls)×r
.
Ω
A
i
=
I 0
0 F
−1
A
i
I 0
0 F
=
=
0
l×l
0
l×(n−l−r)
a
i
l×r
0
(n−l−r)×l
b
i
11
(n−l−r)×(n−l−r)
b
i
12
(n−l−r)×r
0
r×l
b
i
21
r×(n−l−r)
b
i
22
r×r
i = 1, . . . , s.
A
1
, . . . , A
s
A
1
, . . . , A
s
a
i
b
21
= 0 i = 1, . . . , s.
a
1
···
a
s
b
21
= 0
A b
21
= 0.
0 0 a
i
0 b
i
11
b
i
12
0 0 b
i
22
b
11
, b
22
.
b
11
Ω l + 1,
(L) = l.
(A) = n − l,
a b
Ω
a
b
0 0
0 b
0 a
i
0 b
i
=
0 a
i
0 b
i
0 0
0 b
=
0 0
0 bb
i
=
0 a
i
b
0 b
i
b
.
a
i
b = 0, i = 1, . . . , s.
a
1
···
a
s
b =
e
Ab = 0
e
A
b = 0.
a b.
0 a
0 b
1
,
0 a
0 b
2
∈ Ω,
0 a
0 b
1
−
0 a
0 b
2
=
0 0
0 b
1
− b
2
∈ Ω.
b
1
− b
2
= 0.
Ω
a.
l
l(n − l).
Ω
0 a
0 b
.
b
a. a l × (n − l),
a l(n − l).
l,
[n
2
/4] l = [n/2].
(Ω) 6 [n
2
/4] + 1.
Ω X,
(Ω) 6 (X). Ω
X
Ω ⊆ X.
Ω
X.
k = 1 Ω
A, λ
A
Ω
′
,
A Ω
′
A
′
− λ
A
I = J n
Ω
′
.
e
Ω
J. Ω
′
⊆
e
Ω,
Ω
′
=
e
Ω.
J,
b
0
b
1
··· b
t−1
b
0
··· b
t−2
0 b
0
n, I, J, J
2
, . . . , J
n−1
Ω
′
,
(
f
Ω
′
) =
n.
Ω ⊆
R
n×n
,
n.
k = 2 Ω
A λ
A
= 0
A J =
D
−1
AD
s
t J = (J
s
, J
t
). s 6 t. k = 1,
Ω
′
= {D
−1
CD|C ∈ Ω}.
J ∈ Ω
′
Ω
′
B
0
, . . . , B
m−1
. I, J, J
2
, . . . , J
t−1
Ω
′
i > t J
i
=
0
t
B
i
= J
i
, i = 0, . . . , t − 1.
B
0
B
1
= J, B
2
, . . . , B
t−1
.
{C ∈ C
n×n
|CJ−JC = 0}, (Ω
′
).
Ω
′
K, B
0
, . . . , B
t−1
,
e
Ω = {C ∈ C
n×n
| CJ−JC = CK−KC =
0}.
Ω
′
⊆
e
Ω,
Ω
′
=
e
Ω,
s = t = n/2.
B
1
= J B
t
, . . . , B
m−1
B
i
=
B
i1
B
i2
B
i3
B
i4
,
B
ij
i = t, . . . , m − 1
B
i
i = t, . . . , m − 1
I, J, . . . , J
t−1
B
′
i
=
B
′
i1
B
′
i2
B
′
i3
0
=
B
i1
− B
i4
B
i2
B
i3
0
,
B
′
ij
B
′
i
K
e
Ω.
B
′
ij
i = t, . . . , m −
1; j = 1, 2, 3
(B
′
ij
)
0
= (B
′
ij
)
1
= . . . = (B
′
ij
)
h−1
= 0 ∀i, j, ∃i
0
, j
0
(B
′
i
0
j
0
)
h
6= 0
(B
′
ij
)
l
B
′
ij
, l
B
′
ij
h > 1.
K B
i
0
.
e
Ω = {C | CJ − JC = CK − KC = 0}.
C =
C
1
C
2
C
3
0
B
′
i
0
J
C
B
′
i
0
C = CB
′
i
0
B
′
i
0
3
C
2
= B
′
i
0
2
C
3
B
′
i
0
1
C
3
= B
′
i
0
3
C
1
B
′
i
0
2
C
1
= B
′
i
0
1
C
2
h > t/2,
C 3(t − h),
3/4n. I, J, J
2
, . . . , J
t−1
,
n/2. (
e
Ω) 6 5/4n.
h < t/2.
c
1
t−h
, . . . , c
1
t−1
,
c
2
t−h
, . . . , c
2
t−1
c
3
t−h
, . . . , c
3
t−1
c
1
h
, . . . , c
1
t−h−1
, c
2
h
, . . . , c
2
t−h−1
c
3
h
, . . . , c
3
t−h−1
c
j
0
h
, . . . , c
j
0
t−h−1
.
B
′
i
0
j
(t − h) × (t − h)
B
′
i
0
j
=
"
0
c
B
j
0 0
#
j = 1, 2, 3
c
B
1
,
c
B
2
c
B
3
,
d
B
j
0
,
c
B
j
=
b
j
h
b
j
h+1
. . . b
j
t−2
b
j
t−1
0 b
j
h
. . . b
j
t−3
b
j
t−2
. . .
. . . . . . b
j
h
b
j
h+1
0 . . . . . . 0 b
j
h
, j = 1, 2, 3
c
B
j
C
j
, (t −h) ×(t −h)
C
j
=
"
. . . . . .
0
c
C
j
#
, j = 1, 2, 3
c
C
j
c
C
j
=
0 . . . 0 c
j
h
c
j
h+1
. . . c
j
t−h−1
0 . . . 0 0 c
j
h
. . . c
j
t−h−2
. . . . . . . . . . . .
0 . . . . . . . . . . . . . . . c
j
h
. . . . . . . . . . . . . . .
0 . . . . . . . . . . . . . . . 0
, j = 1, 2, 3
c
B
3
c
C
2
=
c
B
2
c
C
3
,
c
B
1
c
C
3
=
c
B
3
c
C
1
c
B
2
c
C
1
=
c
B
1
c
C
2
.
d
B
j
0
d
C
j
0
c
C
j
.
((t − h − 1) − (h − 1)) + 3(t − 1 − (t − h − 1)) = t + h 6 3/4n
C. I, J, J
2
, . . . , J
t−1
(
e
Ω) 6 5/4n.
s < t, s + t = n.
B
1
= J B
t
, . . . , B
m−1
B
i
=
B
i1
B
i2
B
i3
B
i4
,
B
i1
, B
i4
i = t, . . . , m − 1
s ×s t×t B
i1
, B
i4
B
i2
=
h
0
g
B
i2
i
, B
i3
=
"
g
B
i3
0
#
,
g
B
i1
,
g
B
i3
s × s.
B
i
i = t, . . . , m−1 I, J, . . . , J
t−1
B
i4
,
B
′
i
=
B
′
i1
B
′
i2
B
′
i3
0
,
B
′
i2
=
h
0
g
B
′
i2
i
=
h
0
g
B
i2
i
, B
i3
=
"
g
B
′
i3
0
#
=
"
g
B
i3
0
#
B
′
i
, B
′
j
i j t
m − 1
B
′
i2
B
′
j3
= B
′
j2
B
′
i3
B
′
i1
B
′
j2
= B
′
j1
B
′
i2
B
′
i3
B
′
j1
= B
′
j3
B
′
i1
B
′
i3
B
′
j2
= B
′
j3
B
′
i2
t = s, B
′
i
, B
′
j
t ×t,
B
i1
, B
i4
, B
j1
, B
j4
s × s
B
′
i1
g
B
′
j2
= B
′
j1
g
B
′
i2
g
B
′
i3
B
′
j1
=
g
B
′
j3
B
′
i1
g
B
′
i3
g
B
′
j2
=
g
B
′
j3
g
B
′
i2
c
B
i
,
c
B
j
∈ C
2s×2s
c
B
′
i
=
"
B
′
i1
g
B
′
i2
g
B
′
i3
0
#
,
c
B
′
j
=
"
B
′
j1
g
B
′
j2
g
B
′
j3
0
#
B
′
i
, B
′
j
c
B
i
,
c
B
j
B
′
t
, . . . , B
′
m−1
c
B
′
t
, . . . ,
\
B
′
m−1
b
K
c
B
′
t
, . . . ,
\
B
′
m−1
b
K,
b
n = 2s.
3/4
b
n = 3/2s. I, J, J
2
, . . . , J
t−1
(
e
Ω) 6 3/2s + t = 3/4n − 1/4(t − s) < 5/4n
(Ω) 6 5/4n
k Ω
A, G = (J, . . . , J
|
{z }
k
) =
DAD
−1
,
J t ×t n = kt
Ω
′
=
C
′
|C
′
= DCD
−1
, C ∈ Ω
,
G (Ω) = (Ω
′
)
Ω
′
. I, G, . . . , G
t−1
Ω
′
A
0
, A
1
, . . . , A
m−1
,
A
i
= A
i
, i = 0, . . . , t − 1.
G A
l
l = 0, . . . , m − 1
k
2
t×t
A
l
=
A
l
11
A
l
12
. . . A
l
1k
A
l
21
A
l
22
. . . A
l
2k
. . . . . . . . . . . .
A
l
k1
A
l
k2
. . . A
l
kk
A
i
A
i
11
, A
i
22
, . . . , A
i
kk
h
i
A
i
h
i