Воеводин Вл. В. Численные методы, параллельные вычисления и информационные технологии
Подождите немного. Документ загружается.
A
l
I, J, . . . , J
t−1
A
i
h
i
> 1 B
0
, . . . , B
t−1
, B
t
, . . . , B
m−1
,
B
0
= A
0
= I, B
1
= A
1
= G, . . . , B
t−1
= A
t−1
= G
t−1
h
B
i
i = t, . . . , m − 1; 1 6 h 6 t
(B
l
ij
)|
1s
= 0 ∀l, i, j, s 6 h ∃l
0
, i
0
, j
0
(B
l
0
i
0
j
0
)
1,h+1
6= 0.
r
0
A
t
, . . . , A
m−1
, h = t − r
0
B
l
0
, h
K.
h
I
h
K.
h > t/2 = n/2k
K KB
l
= B
l
K = 0
G
h
, . . . , G
t−1
.
(Ω
′
) = t − h + k
2
t
2
6
t
2
+
kn
2
=
n
2
k +
1
k
h < t/2.
KB
l
= B
l
K
k
2
(K
1i
B
l
j1
+ . . . + K
ki
B
l
jk
) − (K
j1
B
l
1i
+ . . . + K
jk
B
l
ki
) = 0
i, j = 1, . . . , k.
B
l
ij
B
l
ij
b
l
ij
∈ C
t
B
l
ij
b
l
ij
(K
1i
b
l
j1
+ . . . + K
ki
b
l
jk
) − (K
j1
b
l
1i
+ . . . + K
jk
b
l
ki
) = 0
k
2
.
h, h
b
l
ij
k
2
h
h b
l
ij
K
hk
2
b
l
ij
,
h b
l
ij
′
∈ C
t−h
.
h − 1 b
l
ij
′
0
h
K
ij
K
′
ij
∈ C
(t−h)×(t−h)
.
K
′
.
K
′
ij
b
l
ij
′
(K
′
1i
b
l
j1
′
+ . . . + K
′
ki
b
l
jk
′
) − (K
′
j1
b
l
1i
′
+ . . . + K
′
jk
b
l
ki
′
) = 0
Ki
0
j
0
2k 2k − 1
2k − 2
2k − 1 b
l
ki
′
b
l
11
′
, . . . , b
l
1k
′
, b
l
21
′
, . . . . . . , b
l
kk
′
b
l
∈
C
k
2
(t−h)
.
Xb
l
= 0, X
X =
−K
′BT
+
[K
′
11
] [K
′
12
] . . . [K
′
1k
]
[K
′
21
] −K
′BT
+ [K
′
22
] . . . [K
′
2k
]
. . . . . . . . . . . .
[K
′
k1
] [K
′
k2
] . . . −K
′BT
+ [K
′
kk
]
K
′BT
[K
′
ij
] = (K
′
ij
, . . . , K
′
ij
| {z }
k
) ∈ C
(k(t−h))×(k(t−h))
= C
(n−kh)×(n−kh)
K (X) > (2k−2)(t−
h) 6 2n − 2kh + 2t − 2h.
(2k − 1)(t − 2h + 1)
k
2
(t − 2h) − (2k − 2)(t − 2h) = (k − 1)
2
(t − 2h + 1)
hk
2
I, J, . . . , J
t−h
(Ω
′
) = hk
2
+ t − h + (k
2
− 2k − 2)(t − 2h) 6 n (k − 1/k)
k
(Ω) <
n
2
k +
1
k
; n
k −
1
k
k,
k
(Ω) <
n
2
k
+
1
k
; n
k
−
1
k
Ω
G k ,
Ω
G K,
Ω
k.
k = n n
2
−1,
n
2
/4.
k
k = 2,
l k
l, k
G =
(J, J) J n/2
Ω = (G, G
2
, . . . , G
n/2−1
)
2n − 4 l 5/4n k
(Ω) = n/2− 1.
l k .
l
l 6 k 6 k l(n − l)
l 6 n/2, k 6 n/2.
k > n/2,
l = n/2, l(n − l) > k(n − k). k > n/2
n > 2 k
n
2
/4
k > n/2 => n
k −
1
k
> n
n
2
−
2
n
=
n
2
2
− 2 >
n
2
4
k(n − k) n(k − 1/k) k =
3
√
n,
(Ω) 6 f(k), f(k) =
n, k = 1
5/4n, k = 2
n (k − 1/k) , 2 < k 6 [
3
√
n]
k (n − k) , [
3
√
n] < k < n/2
n
2
/4, n/2 6 k
k
min
.
k
//
⋆
⋆
