# Optimal Backward Perturbation Analysis for the Block Skew Circulant Linear Systems with Skew Circulant Blocks

Authors: Zhaolin Jiang; Juan Li; Jianwei Zhou
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We first give the block style spectral decomposition of arbitrary block skew circulant matrix with skew circulant blocks. Secondly, we obtain the singular value of block skew circulant matrix with skew circulant blocks as well. Finally, based on the block style spectral decomposition, we deal with the optimal backward perturbation analysis for the block skew circulant linear system with skew circulant blocks.


---

## Body

## 1. Introduction

A block skew circulant matrix with skew circulant blocks with the first row(
a
11
,
…
,
a
1
m
,
a
21
,
…
,
a
2
m
,
…
,
a
n
1
,
…
,
a
n
m
) is meant a square matrix of the following form:
(1)
(
A
1
A
2
⋯
A
n
-
1
A
n
-
A
n
A
1
A
2
⋯
A
n
-
1
⋮
⋱
⋱
⋱
⋮
-
A
3
⋯
-
A
n
A
1
A
2
-
A
2
-
A
3
⋯
-
A
n
A
1
)
,
and for any k
=
1,2
,
…
,
n,
(2)
A
k
=
(
a
k
1
a
k
2
⋯
a
k
(
m
-
1
)
a
k
m
-
a
k
m
a
k
1
a
k
2
⋯
a
k
(
m
-
1
)
⋮
⋱
⋱
⋱
⋮
-
a
k
3
⋯
-
a
k
m
a
k
1
a
k
2
-
a
k
2
-
a
k
3
⋯
-
a
k
m
a
k
1
)
,
denoted by B
C
-
1
,
-
1
n
,
m
(
a
11
,
…
,
a
1
m
,
…
,
a
n
1
,
…
,
a
n
m
). Note that in this paper all facts are based on real field.Skew circulant matrices have important applications in various disciplines including image processing, signal processing, solving Toeplitz matrix problems, preconditioner, and solving least squares problems in [1–10].Liu and Guo [11] gave the optimal backward perturbation analysis for a block circulant linear system. Li et al. [12] gave the style spectral decomposition of skew circulant matrix firstly and then dealt with the optimal backward perturbation analysis for the skew circulant linear system. The optimal backward perturbation bounds for underdetermined systems are studied by J.G. Sun and Z. Sun in [13]. Some new theorems generalizing a result of Oettli and Prager are applied to a posteriori analysis of the compatibility of a computed solution to the uncertain data of a linear system by Rigal and Gaches in [14]. Systems with BC structure appear in the context of multichannel signal estimation [15, 16], image restoration [17], cyclic convolution filter banks [18], texture synthesis and recognition [19], and so on.The block skew circulant matrix with skew circulant blocks is an extension of skew circulant matrix and we believe the block skew circulant linear system with skew circulant blocks can be used in those fields as well. In this paper, firstly, by using the style spectral decomposition of a special skew circulant matrixC in [12], we get the block style spectral decomposition of arbitrary block skew circulant matrix with skew circulant blocks. Secondly, we obtain the singular value of block skew circulant matrix with skew circulant blocks as well. Finally, we deal with the optimal backward perturbation analysis for the block skew circulant linear system with skew circulant blocks on the base of its block style spectral decomposition.


## 2. The Block Style Spectral Decomposition of Block Skew Circulant Matrix with Skew Circulant Blocks

Let matrixA be a block skew circulant matrix with skew circulant blocks as in the form of (1); then by using the properties of Kronecker products in [20], the matrix A can be decomposed as
(3)
A
=
∑
k
=
1
n
‍
(
C
n
×
n
k
-
1
⊗
A
k
)
,
where
(4)
C
n
×
n
=
(
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋱
⋱
⋱
⋮
0
⋯
0
0
1
-
1
0
⋯
0
0
)
n
×
n
.
According to the style spectral decomposition of basic skew circulant (please refer to equations (10) and (11) in [12]), the style spectral decomposition of the matrix C
n
×
n
k is
(5)
C
n
×
n
k
=
Q
C
0
k
Q
T
,
where Q is an orthogonal matrix, θ
j
=
(
(
2
j
-
1
)
/
n
)
π,
(6)
C
0
k
=
(
C
1
k
C
2
k
⋱
C
n
/
2
k
)
,
(
n
is
even
)
,
C
0
k
=
(
C
1
k
⋱
C
(
n
-
1
)
/
2
k
(
-
1
)
k
)
,
(
n
is
odd
)
,
C
j
k
=
(
cos
⁡
k
θ
j
sin
k
θ
j
-
sin
k
θ
j
cos
⁡
k
θ
j
)
,
(7)
j
=
{
1,2
,
…
,
n
2
,
when
n
is
even
,
1,2
,
…
,
n
-
1
2
,
when
n
is
odd
.
Consider (3) and (5); the matrix A can be decomposed as
(8)
A
=
∑
k
=
1
n
‍
(
C
n
×
n
k
-
1
⊗
A
k
)
=
∑
k
=
1
n
‍
(
Q
C
0
k
-
1
Q
T
)
⊗
A
k
=
∑
k
=
1
n
‍
(
Q
⊗
I
m
)
(
C
0
k
-
1
⊗
A
k
)
(
Q
T
⊗
I
m
)
=
(
Q
⊗
I
m
)
(
∑
k
=
1
n
‍
C
0
k
-
1
⊗
A
k
)
(
Q
T
⊗
I
m
)
.
Noticing that Q
⊗
I
m is an orthogonal matrix, so (8) is the block style spectral decomposition of the matrix A.


## 3. The Structured Perturbation Analysis

In this section, we give the structured perturbation analysis for the block skew circulant linear systems with skew circulant blocks.


### 3.1. Condition Number and Relative Error of Block Skew Circulant Linear System with Skew Circulant Blocks

Consider(9)
A
x
=
b
,
where A is defined in (1).From (8) and the property of Kronecker products in [20], we express the matrix A by using the elements in its first row as
(10)
A
=
∑
k
=
1
n
‍
(
C
n
×
n
k
-
1
⊗
A
k
)
=
∑
k
=
1
n
‍
[
C
n
×
n
k
-
1
⊗
(
∑
l
=
1
m
‍
a
k
l
C
m
×
m
l
-
1
)
]
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
(
C
n
×
n
k
-
1
⊗
C
m
×
m
l
-
1
)
,
where
(11)
C
m
×
m
=
(
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋱
⋱
⋱
⋮
0
⋯
0
0
1
-
1
0
⋯
0
0
)
m
×
m
.We denote the eigenvalues of matrixC
n
×
n as ε
i (i
=
1,2
,
…
,
n), and denote the eigenvalues of matrix C
m
×
m as δ
j (j
=
1,2
,
…
,
m); then the eigenvalues of A are (regarding more properties, please refer to [20, 21])
(12)
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
ε
i
k
-
1
δ
j
l
-
1
.Lemma 1.
A is an invertible matrix if and only if f
(
ε
i
,
δ
j
)
≠
0
(
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
), where
(13)
f
(
ε
i
,
δ
j
)
=
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
ε
i
k
-
1
δ
j
l
-
1
.Let(14)
σ
i
j
=
|
f
(
ε
i
,
δ
j
)
|
,
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
,
K
=
max
⁡
{
σ
i
j
}
min
⁡
{
σ
i
j
}
.Theorem 2.
IfA
=
B
C
-
1
,
-
1
n
,
m
(
a
11
,
…
,
a
1
m
,
…
,
a
n
1
,
…
,
a
n
m
) is a block skew circulant matrix with skew circulant blocks, then the singular values of matrix A are σ
11
,
…
,
σ
1
m
,
σ
21
,
…
,
σ
2
m
,
…
,
σ
n
1
,
…
,
σ
n
m.Proof.
Obviously, the matrixA has a form as (1) and the conjugate transpose of A is
(15)
A
*
=
(
A
1
*
-
A
n
*
⋯
-
A
3
*
-
A
2
*
A
2
*
A
1
*
⋱
⋮
-
A
3
*
⋮
A
2
*
⋱
-
A
n
*
⋮
A
n
-
1
*
⋮
⋱
A
1
*
-
A
n
*
A
n
*
A
n
-
1
*
⋯
A
2
*
A
1
*
)
.
Through a direct calculation, we can get A
A
*
=
A
*
A, and that means that A is a normal matrix. By using Theorem  2.5
.
4 in [22], we know that A is unitarily diagonalizable. That is, there is a unitary matrix U
∈
M
m
n such that
(16)
U
*
A
U
=
Λ
=
diag
⁡
(
λ
11
,
…
,
λ
1
m
,
…
,
λ
n
1
,
…
,
λ
n
m
)
.
where λ
i
j (i
=
1,2
,
…
,
n, j
=
1,2
,
…
,
m) are the eigenvalues of A. Taking a conjugate transpose at both sides of (16),
(17)
U
*
A
*
U
=
Λ
*
=
diag
⁡
(
λ
¯
11
,
…
,
λ
¯
1
m
,
…
,
λ
¯
n
1
,
…
,
λ
¯
n
m
)
,
and so, we have
(18)
U
*
(
A
*
A
)
U
=
(
U
*
A
*
U
)
(
U
*
A
U
)
=
diag
⁡
(
|
λ
11
|
2
,
…
,
|
λ
1
m
|
2
,
…
,
|
λ
n
1
|
2
,
…
,
|
λ
n
m
|
2
)
.
Hence, for any i
=
1,2
,
…
,
n, j
=
1,2
,
…
,
m, the eigenvalues of matrix A
*
A are
(19)
λ
i
j
(
A
*
A
)
=
|
λ
i
j
|
2
.
Therefore, we can get the singular value of A as
(20)
σ
i
j
(
A
)
=
[
λ
i
j
(
A
*
A
)
]
1
/
2
=
|
λ
i
j
|
.
Recalling (13) and (14), the proof is completed.Since the spectral norm of matrixA is defined as
(21)
∥
A
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
[
λ
i
j
(
A
*
A
)
]
1
/
2
,
by using Theorem 2, we have the following corollary.Corollary 3.
LetA
=
B
C
-
1
,
-
1
n
,
m
(
a
11
,
…
,
a
1
m
,
…
,
a
n
1
,
…
,
a
n
m
) be a block skew circulant matrix with skew circulant blocks; then the spectral norm of matrix A is
(22)
∥
A
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
.By using equations (10) and (11) in [12], we can express the matrix C
n
×
n and C
m
×
m as
(23)
C
n
×
n
=
Q
n
C
n
0
Q
n
T
,
C
m
×
m
=
Q
m
C
m
0
Q
m
T
,
where
(24)
C
n
0
=
(
C
11
C
22
⋱
C
t
t
)
,
C
m
0
=
(
D
11
D
22
⋱
D
s
s
)
,
C
h
h
=
(
cos
⁡
θ
h
sin
θ
h
-
sin
θ
h
cos
⁡
θ
h
)
,
h
=
1,2
,
…
,
t
.
D
r
r
=
(
cos
⁡
θ
r
sin
θ
r
-
sin
θ
r
cos
⁡
θ
r
)
,
r
=
1,2
,
…
,
s
.
t
=
{
n
2
,
when
n
is
even
,
n
-
1
2
+
1
,
when
n
is
odd
,
s
=
{
m
2
,
when
m
is
even
,
m
-
1
2
+
1
,
when
m
is
odd
.
So, we can get
(25)
A
=
Q
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
C
n
0
k
-
1
⊗
C
m
0
l
-
1
)
Q
T
,
where Q
=
(
Q
n
⊗
I
m
)
(
I
n
⊗
Q
m
),
(26)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
C
n
0
k
-
1
⊗
C
m
0
l
-
1
=
(
B
11
⋱
B
t
t
)
,
and B
p
p
=
∑
k
=
1
n
∑
l
=
1
m
a
k
l
C
p
p
⊗
C
m
0
l
-
1, p
=
1,2
,
…
,
t.LetΔ
A, Δ
b be the perturbation of the coefficient matrix A and vector b, respectively, where Δ
A
=
B
C
-
1
,
-
1
n
,
m
(
δ
a
11
,
…
,
δ
a
1
m
,
…
,
δ
a
n
1
,
…
,
δ
a
n
m
) is a block skew circulant matrix with skew circulant blocks, has the form as follows:
(27)
Δ
A
=
(
Δ
A
1
⋯
Δ
A
n
-
1
Δ
A
n
-
Δ
A
n
Δ
A
1
⋯
Δ
A
n
-
1
⋮
⋱
⋱
⋮
-
Δ
A
2
⋯
-
Δ
A
n
Δ
A
1
)
,
Δ
A
k
=
(
δ
a
k
1
⋯
δ
a
k
(
m
-
1
)
δ
a
k
m
-
δ
a
k
n
δ
a
k
1
⋯
δ
a
k
(
m
-
1
)
⋮
⋱
⋱
⋮
-
δ
a
k
2
⋯
-
δ
a
k
m
δ
a
k
1
)
,
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
k
=
1,2
,
…
,
n
.
Let
(28)
A
^
=
A
+
Δ
A
,
b
^
=
b
+
Δ
b
,
f
^
(
ε
i
,
δ
j
)
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
a
k
l
+
δ
a
k
l
)
ε
i
k
-
1
δ
j
l
-
1
.
If
(29)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
<
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
,
then
(30)
|
f
^
(
ε
i
,
δ
j
)
|
=
|
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
a
k
l
+
δ
a
k
l
)
ε
i
k
-
1
δ
j
k
-
1
|
≥
|
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
ε
i
k
-
1
δ
j
l
-
1
|
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
|
ε
i
|
k
-
1
|
δ
j
|
l
-
1
≥
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
>
0
.
By using Lemma 1, we know that A
^ is an invertible matrix. Let
(31)
σ
min
⁡
=
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
,
Δ
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
.
By A
x
=
b, A
^
x
^
=
b
^, we get
(32)
x
^
-
x
=
A
^
-
1
b
^
-
A
-
1
b
=
A
^
-
1
(
b
+
δ
b
)
-
A
-
1
b
=
A
^
-
1
δ
b
+
(
A
^
-
1
-
A
-
1
)
b
=
A
^
-
1
δ
b
+
(
A
^
-
1
-
A
-
1
)
A
x
=
A
^
-
1
δ
b
+
A
^
-
1
(
A
-
A
^
)
x
∥
x
^
-
x
∥
2
≤
∥
A
^
-
1
∥
2
∥
δ
b
∥
2
+
∥
A
^
-
1
∥
2
∥
A
^
-
A
∥
2
∥
x
∥
2
.SinceA
^
-
1
·
A
^
=
I
m
n and ∥
I
m
n
∥
2
=
1, so we have ∥
A
^
-
1
∥
2
∥
A
^
∥
2
≤
1. Besides, we know that
(33)
∥
A
^
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
|
f
^
(
ε
i
,
δ
j
)
|
≥
σ
min
⁡
-
Δ
>
0
.
So, we obtain
(34)
∥
A
^
-
1
∥
2
≤
1
∥
A
^
∥
2
≤
1
σ
min
⁡
-
Δ
.
Hence,
(35)
∥
x
^
-
x
∥
2
≤
∥
δ
b
∥
2
σ
min
⁡
-
Δ
+
∥
A
^
-
A
∥
2
∥
x
∥
2
σ
min
⁡
-
Δ
,
∥
x
^
-
x
∥
2
∥
x
∥
2
≤
∥
δ
b
∥
2
(
σ
min
⁡
-
Δ
)
∥
x
∥
2
+
∥
A
^
-
A
∥
2
σ
min
⁡
-
Δ
=
∥
A
∥
2
σ
min
⁡
-
Δ
[
∥
δ
b
∥
2
∥
A
∥
2
∥
x
∥
2
+
∥
A
^
-
A
∥
2
∥
A
∥
2
]
≤
∥
A
∥
2
σ
min
⁡
-
Δ
[
∥
δ
b
∥
2
∥
b
∥
2
+
∥
A
^
-
A
∥
2
∥
A
∥
2
]
,
where
(36)
∥
A
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
.
Notice that A
^
-
A
=
Δ
A is a block skew circulant matrix with skew circulant blocks, and ∥
A
^
-
A
∥
2
=
|
-
1
|
∥
A
^
-
A
∥
2
=
∥
A
^
-
A
∥
2. So, we get
(37)
∥
A
^
-
A
∥
2
=
max
⁡
1
≤
j
≤
n
1
≤
j
≤
m
⁡
|
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
ε
i
k
-
1
δ
j
l
-
1
|
≤
max
⁡
1
≤
j
≤
n
1
≤
j
≤
m
⁡
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
|
ε
i
|
k
-
1
|
δ
j
|
l
-
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
=
Δ
.
Hence, we have the following theorem.Theorem 4.
LetA
,
A
^
,
δ
b
,
Δ
,
σ
min
⁡ be defined as above. If Δ
<
σ
min
⁡, then
(38)
∥
x
^
-
x
∥
2
∥
x
∥
2
≤
σ
max
⁡
σ
min
⁡
-
Δ
(
∥
δ
b
∥
2
∥
b
∥
2
+
Δ
σ
max
⁡
)
,
where
(39)
σ
max
⁡
=
∥
A
∥
2
.Remark 5.
From (38) and (39), the condition number K of the block skew circulant linear system with skew circulant blocks can be easily computed, as well as the bound of perturbation (38).


### 3.2. Optimal Backward Perturbation Bound of the Block Skew Circulant Linear System with Skew Circulant Blocks

Letx
^ be an approximate solution to A
x
=
b and let
(40)
Ω
≡
{
(
Δ
A
,
Δ
b
)
∣
(
A
+
Δ
A
)
x
^
=
b
+
Δ
b
}
,
η
(
x
^
)
≡
inf
⁡
(
Δ
A
,
Δ
b
)
∈
Ω
∥
Δ
A
,
Δ
b
∥
,
(
A
+
Δ
A
)
x
^
=
b
+
Δ
b
,
which is equivalent to
(41)
(
Δ
A
,
Δ
b
)
(
x
^
-
1
)
=
b
-
A
x
^
.
Due to [14], we have
(42)
η
(
x
^
)
=
∥
b
-
A
x
^
∥
2
1
+
∥
x
^
∥
2
2
,
(
∥
∥
being
any
unitary
invariant
norm
⁡
)
.Letx
^ be an approximate solution to A
x
=
b, where A is defined in (1), as follows:
(43)
Ω
≡
{
(
Δ
A
,
Δ
b
)
∣
(
A
+
Δ
A
)
x
^
=
b
+
Δ
b
,
f
f
Δ
A
is
a
block
skew
circulant
matrix
i
f
with
skew
circulant
blocks
}
η
(
x
^
)
≡
inf
⁡
(
Δ
A
,
Δ
b
)
∈
Ω
{
∥
Δ
A
,
Δ
b
∥
F
}
.
Then Ω
≠
ϕ (such as Δ
A
=
0 is a block skew circulant matrix with skew circulant blocks, Δ
b
=
A
x
^
-
b)
(44)
η
2
(
x
^
)
=
inf
⁡
(
Δ
A
,
Δ
b
)
∈
Ω
{
∥
Δ
A
∥
F
2
+
∥
Δ
A
x
^
+
A
x
^
-
b
∥
F
2
}
.
Since
(45)
∥
Δ
A
∥
F
2
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
δ
a
k
l
)
2
,
Δ
A
=
Q
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
C
n
0
k
-
1
⊗
C
m
0
l
-
1
)
Q
T
,
so
(46)
∥
Δ
A
x
^
+
A
x
^
-
b
∥
F
2
=
∥
Q
(
δ
B
11
⋱
δ
B
t
t
)
Q
T
x
^
+
A
x
^
-
b
∥
F
2
=
∥
(
δ
B
11
⋱
δ
B
t
t
)
(
x
1
(
0
)
⋮
x
t
(
0
)
)
-
r
0
∥
F
2
=
∥
(
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
C
11
k
-
1
⊗
C
m
0
l
-
1
)
x
1
(
0
)
⋮
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
C
t
t
k
-
1
⊗
C
m
0
l
-
1
)
x
t
(
0
)
)
-
r
0
∥
F
2
=
∥
G
0
(
δ
a
11
,
…
,
δ
a
1
m
,
…
,
δ
a
n
1
,
…
,
δ
a
n
m
)
T
-
r
0
∥
F
2
,
where r
0
=
Q
T
(
b
-
A
x
^
), Q
T
x
^
=
(
x
1
(
0
)
⋮
x
t
(
0
)
), G
0
=
(
R
1
,
R
2
,
…
,
R
n
)
∈
R
m
n
×
m
n, and
(47)
R
k
=
(
P
1
,
k
,
1
⋯
P
1
,
k
,
m
⋮
⋱
⋮
P
t
,
k
,
1
⋯
P
t
,
k
,
m
)
,
P
p
,
k
,
l
=
C
p
p
k
-
1
⊗
C
m
0
l
-
1
x
p
(
0
)
,
p
=
1,2
,
…
,
t, k
=
1,2
,
…
,
n, and l
=
1,2
,
…
,
m.Let(48)
f
(
δ
a
11
,
…
,
δ
a
n
m
)
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
δ
a
k
l
)
2
+
∥
G
0
(
δ
a
11
⋮
δ
a
n
m
)
-
r
0
∥
F
2
,
then
(49)
∂
f
∂
δ
a
k
l
=
0
,
which is equivalent to
(50)
(
2
m
n
I
m
n
+
2
G
0
T
G
0
)
(
δ
a
11
⋮
δ
a
n
m
)
-
2
G
0
T
r
0
=
0
,
∂
2
f
∂
(
δ
a
k
l
)
2
=
2
m
n
I
m
n
+
2
G
0
T
G
0
>
0
.
Hence f is a convex function about (
δ
a
11
,
…
,
δ
a
n
m
), and the point of minimal value is
(51)
(
δ
a
11
⋮
δ
a
n
m
)
=
(
m
n
I
m
n
+
G
0
T
G
0
)
-
1
G
0
T
r
0
.
Substituting it into (48), we can get the following.Theorem 6.
Letr
0 and G
0 be defined as above; then we have
(52)
η
(
x
^
)
2
=
m
n
r
0
T
G
0
(
m
n
I
m
n
+
G
0
T
G
0
)
-
2
G
0
T
r
0
+
∥
[
G
0
(
m
n
I
m
n
+
G
0
T
G
0
)
-
1
G
0
T
-
I
m
n
]
r
0
∥
F
2
.LetG
0
=
U
Σ
V
T be the singular value decomposition of G
0, where U and V are real orthogonal matrices, Σ
=
diag
⁡
(
σ
1
′
,
…
,
σ
n
m
′
), σ
j
′
≥
0
(
j
=
1,2
,
…
,
n
m
), so
(53)
η
(
x
^
)
2
=
m
n
r
0
T
U
Σ
V
T
(
m
n
I
m
n
+
Σ
2
)
-
2
V
Σ
U
T
r
0
+
∥
[
U
Σ
V
T
(
m
n
I
m
n
+
Σ
2
)
-
1
V
Σ
U
T
-
I
m
n
]
r
0
∥
F
2
=
m
n
r
1
T
Σ
(
m
n
I
m
n
+
Σ
2
)
-
2
Σ
r
1
+
∥
[
Σ
(
m
n
I
m
n
+
Σ
2
)
-
1
Σ
-
I
m
n
]
r
0
∥
F
2
=
m
n
r
1
T
Σ
(
m
n
I
m
n
+
Σ
2
)
-
2
Σ
r
1
+
∥
[
Σ
(
m
n
I
m
n
+
Σ
2
)
-
1
Σ
-
I
m
n
]
r
1
∥
F
2
=
m
n
r
1
T
Σ
(
m
n
I
m
n
+
Σ
2
)
-
2
Σ
r
1
+
m
2
n
2
r
1
T
(
m
n
I
m
n
+
Σ
2
)
-
2
r
1
=
r
1
T
diag
⁡
(
d
1
,
d
2
,
…
,
d
m
n
)
r
1
,
where r
1
=
U
T
r
0, d
j
=
(
m
n
σ
j
′
2
+
m
2
n
2
)
/
(
m
n
+
σ
j
′
2
)
2
=
m
n
/
(
m
n
+
σ
j
′
2
), j
=
1,2
,
…
,
m
n.Remark 7.
Byσ
j
2
≤
∥
G
0
∥
F
2
=
m
n
∥
x
^
∥
2
2, we get 1
+
σ
j
′
2
/
m
n
≤
1
+
∥
x
^
∥
2
2, and hence m
n
/
(
m
n
+
σ
j
′
2
)
≥
1
/
(
1
+
∥
x
^
∥
2
2
).Algorithm 8.
Consider the following.
Step
1. Form the block style spectral decomposition of the matrix C
n
×
n and C
m
×
m,
(54)
C
n
×
n
=
Q
n
(
C
11
C
22
⋱
C
t
t
)
Q
n
T
,
C
m
×
m
=
Q
m
(
D
11
D
22
⋱
D
s
s
)
Q
m
T
.
Step
2. Compute Q
=
(
Q
n
⊗
I
m
)
(
I
n
⊗
Q
m
).
Step
3. Compute r
=
b
-
A
x
^.
Step
4. Compute r
0
=
Q
T
r.
Step
5. Compute Q
T
x
^
=
(
x
1
(
0
)
,
…
,
x
t
(
0
)
)
T.
Step
6. Form G
0.
Step
7. Compute η
2
(
x
^
).


### 3.3. Numerical Example

In this section, we give a simple numerical example to verify the conclusions above. Suppose thatn
=
3, m
=
2 in the following example.If the coefficient matrix of block skew circulant linear system with skew circulant blocks isA
=
B
C
-
1
,
-
1
3,2
(
1,2
,
4.5,3
,
4,2.5
), and the constant vector b
=
(
1,2
,
1,0
,
3,4
)
T. Now, for comparative analysis, we give three perturbations in the following:
(55)
Δ
A
1
=
B
C
-
1
,
-
1
3,2
(
0.01,0.03,0.02
,
-
0.05
,
-
0.03,0.01
)
,
Δ
b
1
=
(
0.1,0.3,0
,
-
0.2,0.01,0.04
)
T
,
Δ
A
2
=
B
C
-
1
,
-
1
3,2
(
0.01,0.01,0.01,0.01,0.01,0.01
)
,
Δ
b
2
=
(
0.01,0.01,0.01,0.01,0.01,0.01
)
T
,
Δ
A
3
=
B
C
-
1
,
-
1
3,2
(
0.001,0.001,0.001,0.001,0.001,0.001
)
,
Δ
b
3
=
(
0.001,0.001,0.001,0.001,0.001,0.001
)
T
,
then by equation A
^
x
^
=
b
^, we get the approximate solution of A
x
=
b correspondingly as
(56)
x
=
(
-
1.0505
,
0.6490
,
1.0280
,
-
1.1028
,
-
0.9215
,
1.2482
)
,
x
^
1
=
(
-
1.1526
,
0.6358
,
1.1192
,
-
1.0611
,
-
1.0158
,
1.2286
)
,
x
^
2
=
(
-
1.0396
,
0.6473
,
1.0178
,
-
1.1003
,
-
0.9109
,
1.2484
)
,
x
^
3
=
(
-
1.0494
,
0.6489
,
1.0270
,
-
1.1025
,
-
0.9204
,
1.2482
)
,
where x is the solution of A
x
=
b and x
i (i
=
1,2
,
3) is the solution of (
A
+
Δ
A
i
)
x
=
b
+
Δ
b.According to the Algorithm, we obtain Table1, where ϵ means relative error of block skew circulant linear system with skew circulant blocks, K
=
max
⁡
{
σ
i
j
}
/
min
⁡
{
σ
i
j
} is the condition number, η
1
(
x
^
)
=
∥
b
-
A
x
^
∥
2
/
1
+
∥
x
^
∥
2
2 and η
2 are obtained from the Algorithm.Table 1
ϵ
K
η
1
(
x
^
)
η
2
(
x
^
)
Case0
0
6.472
0
0
Case1
0.0694
6.193
0.1252
0.2487
Case2
0.0075
6.438
0.0127
0.0223
Case3
7.5122
×
1
0
-
4
6.468
0.0013
0.0022From the tabular, we know that the conclusions above are right and the Algorithm is efficient.


## 3.1. Condition Number and Relative Error of Block Skew Circulant Linear System with Skew Circulant Blocks

Consider(9)
A
x
=
b
,
where A is defined in (1).From (8) and the property of Kronecker products in [20], we express the matrix A by using the elements in its first row as
(10)
A
=
∑
k
=
1
n
‍
(
C
n
×
n
k
-
1
⊗
A
k
)
=
∑
k
=
1
n
‍
[
C
n
×
n
k
-
1
⊗
(
∑
l
=
1
m
‍
a
k
l
C
m
×
m
l
-
1
)
]
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
(
C
n
×
n
k
-
1
⊗
C
m
×
m
l
-
1
)
,
where
(11)
C
m
×
m
=
(
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋱
⋱
⋱
⋮
0
⋯
0
0
1
-
1
0
⋯
0
0
)
m
×
m
.We denote the eigenvalues of matrixC
n
×
n as ε
i (i
=
1,2
,
…
,
n), and denote the eigenvalues of matrix C
m
×
m as δ
j (j
=
1,2
,
…
,
m); then the eigenvalues of A are (regarding more properties, please refer to [20, 21])
(12)
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
ε
i
k
-
1
δ
j
l
-
1
.Lemma 1.
A is an invertible matrix if and only if f
(
ε
i
,
δ
j
)
≠
0
(
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
), where
(13)
f
(
ε
i
,
δ
j
)
=
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
ε
i
k
-
1
δ
j
l
-
1
.Let(14)
σ
i
j
=
|
f
(
ε
i
,
δ
j
)
|
,
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
,
K
=
max
⁡
{
σ
i
j
}
min
⁡
{
σ
i
j
}
.Theorem 2.
IfA
=
B
C
-
1
,
-
1
n
,
m
(
a
11
,
…
,
a
1
m
,
…
,
a
n
1
,
…
,
a
n
m
) is a block skew circulant matrix with skew circulant blocks, then the singular values of matrix A are σ
11
,
…
,
σ
1
m
,
σ
21
,
…
,
σ
2
m
,
…
,
σ
n
1
,
…
,
σ
n
m.Proof.
Obviously, the matrixA has a form as (1) and the conjugate transpose of A is
(15)
A
*
=
(
A
1
*
-
A
n
*
⋯
-
A
3
*
-
A
2
*
A
2
*
A
1
*
⋱
⋮
-
A
3
*
⋮
A
2
*
⋱
-
A
n
*
⋮
A
n
-
1
*
⋮
⋱
A
1
*
-
A
n
*
A
n
*
A
n
-
1
*
⋯
A
2
*
A
1
*
)
.
Through a direct calculation, we can get A
A
*
=
A
*
A, and that means that A is a normal matrix. By using Theorem  2.5
.
4 in [22], we know that A is unitarily diagonalizable. That is, there is a unitary matrix U
∈
M
m
n such that
(16)
U
*
A
U
=
Λ
=
diag
⁡
(
λ
11
,
…
,
λ
1
m
,
…
,
λ
n
1
,
…
,
λ
n
m
)
.
where λ
i
j (i
=
1,2
,
…
,
n, j
=
1,2
,
…
,
m) are the eigenvalues of A. Taking a conjugate transpose at both sides of (16),
(17)
U
*
A
*
U
=
Λ
*
=
diag
⁡
(
λ
¯
11
,
…
,
λ
¯
1
m
,
…
,
λ
¯
n
1
,
…
,
λ
¯
n
m
)
,
and so, we have
(18)
U
*
(
A
*
A
)
U
=
(
U
*
A
*
U
)
(
U
*
A
U
)
=
diag
⁡
(
|
λ
11
|
2
,
…
,
|
λ
1
m
|
2
,
…
,
|
λ
n
1
|
2
,
…
,
|
λ
n
m
|
2
)
.
Hence, for any i
=
1,2
,
…
,
n, j
=
1,2
,
…
,
m, the eigenvalues of matrix A
*
A are
(19)
λ
i
j
(
A
*
A
)
=
|
λ
i
j
|
2
.
Therefore, we can get the singular value of A as
(20)
σ
i
j
(
A
)
=
[
λ
i
j
(
A
*
A
)
]
1
/
2
=
|
λ
i
j
|
.
Recalling (13) and (14), the proof is completed.Since the spectral norm of matrixA is defined as
(21)
∥
A
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
[
λ
i
j
(
A
*
A
)
]
1
/
2
,
by using Theorem 2, we have the following corollary.Corollary 3.
LetA
=
B
C
-
1
,
-
1
n
,
m
(
a
11
,
…
,
a
1
m
,
…
,
a
n
1
,
…
,
a
n
m
) be a block skew circulant matrix with skew circulant blocks; then the spectral norm of matrix A is
(22)
∥
A
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
.By using equations (10) and (11) in [12], we can express the matrix C
n
×
n and C
m
×
m as
(23)
C
n
×
n
=
Q
n
C
n
0
Q
n
T
,
C
m
×
m
=
Q
m
C
m
0
Q
m
T
,
where
(24)
C
n
0
=
(
C
11
C
22
⋱
C
t
t
)
,
C
m
0
=
(
D
11
D
22
⋱
D
s
s
)
,
C
h
h
=
(
cos
⁡
θ
h
sin
θ
h
-
sin
θ
h
cos
⁡
θ
h
)
,
h
=
1,2
,
…
,
t
.
D
r
r
=
(
cos
⁡
θ
r
sin
θ
r
-
sin
θ
r
cos
⁡
θ
r
)
,
r
=
1,2
,
…
,
s
.
t
=
{
n
2
,
when
n
is
even
,
n
-
1
2
+
1
,
when
n
is
odd
,
s
=
{
m
2
,
when
m
is
even
,
m
-
1
2
+
1
,
when
m
is
odd
.
So, we can get
(25)
A
=
Q
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
C
n
0
k
-
1
⊗
C
m
0
l
-
1
)
Q
T
,
where Q
=
(
Q
n
⊗
I
m
)
(
I
n
⊗
Q
m
),
(26)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
C
n
0
k
-
1
⊗
C
m
0
l
-
1
=
(
B
11
⋱
B
t
t
)
,
and B
p
p
=
∑
k
=
1
n
∑
l
=
1
m
a
k
l
C
p
p
⊗
C
m
0
l
-
1, p
=
1,2
,
…
,
t.LetΔ
A, Δ
b be the perturbation of the coefficient matrix A and vector b, respectively, where Δ
A
=
B
C
-
1
,
-
1
n
,
m
(
δ
a
11
,
…
,
δ
a
1
m
,
…
,
δ
a
n
1
,
…
,
δ
a
n
m
) is a block skew circulant matrix with skew circulant blocks, has the form as follows:
(27)
Δ
A
=
(
Δ
A
1
⋯
Δ
A
n
-
1
Δ
A
n
-
Δ
A
n
Δ
A
1
⋯
Δ
A
n
-
1
⋮
⋱
⋱
⋮
-
Δ
A
2
⋯
-
Δ
A
n
Δ
A
1
)
,
Δ
A
k
=
(
δ
a
k
1
⋯
δ
a
k
(
m
-
1
)
δ
a
k
m
-
δ
a
k
n
δ
a
k
1
⋯
δ
a
k
(
m
-
1
)
⋮
⋱
⋱
⋮
-
δ
a
k
2
⋯
-
δ
a
k
m
δ
a
k
1
)
,
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
k
=
1,2
,
…
,
n
.
Let
(28)
A
^
=
A
+
Δ
A
,
b
^
=
b
+
Δ
b
,
f
^
(
ε
i
,
δ
j
)
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
a
k
l
+
δ
a
k
l
)
ε
i
k
-
1
δ
j
l
-
1
.
If
(29)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
<
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
,
then
(30)
|
f
^
(
ε
i
,
δ
j
)
|
=
|
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
a
k
l
+
δ
a
k
l
)
ε
i
k
-
1
δ
j
k
-
1
|
≥
|
∑
k
=
1
n
‍
∑
l
=
1
m
‍
a
k
l
ε
i
k
-
1
δ
j
l
-
1
|
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
|
ε
i
|
k
-
1
|
δ
j
|
l
-
1
≥
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
>
0
.
By using Lemma 1, we know that A
^ is an invertible matrix. Let
(31)
σ
min
⁡
=
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
,
Δ
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
.
By A
x
=
b, A
^
x
^
=
b
^, we get
(32)
x
^
-
x
=
A
^
-
1
b
^
-
A
-
1
b
=
A
^
-
1
(
b
+
δ
b
)
-
A
-
1
b
=
A
^
-
1
δ
b
+
(
A
^
-
1
-
A
-
1
)
b
=
A
^
-
1
δ
b
+
(
A
^
-
1
-
A
-
1
)
A
x
=
A
^
-
1
δ
b
+
A
^
-
1
(
A
-
A
^
)
x
∥
x
^
-
x
∥
2
≤
∥
A
^
-
1
∥
2
∥
δ
b
∥
2
+
∥
A
^
-
1
∥
2
∥
A
^
-
A
∥
2
∥
x
∥
2
.SinceA
^
-
1
·
A
^
=
I
m
n and ∥
I
m
n
∥
2
=
1, so we have ∥
A
^
-
1
∥
2
∥
A
^
∥
2
≤
1. Besides, we know that
(33)
∥
A
^
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
|
f
^
(
ε
i
,
δ
j
)
|
≥
σ
min
⁡
-
Δ
>
0
.
So, we obtain
(34)
∥
A
^
-
1
∥
2
≤
1
∥
A
^
∥
2
≤
1
σ
min
⁡
-
Δ
.
Hence,
(35)
∥
x
^
-
x
∥
2
≤
∥
δ
b
∥
2
σ
min
⁡
-
Δ
+
∥
A
^
-
A
∥
2
∥
x
∥
2
σ
min
⁡
-
Δ
,
∥
x
^
-
x
∥
2
∥
x
∥
2
≤
∥
δ
b
∥
2
(
σ
min
⁡
-
Δ
)
∥
x
∥
2
+
∥
A
^
-
A
∥
2
σ
min
⁡
-
Δ
=
∥
A
∥
2
σ
min
⁡
-
Δ
[
∥
δ
b
∥
2
∥
A
∥
2
∥
x
∥
2
+
∥
A
^
-
A
∥
2
∥
A
∥
2
]
≤
∥
A
∥
2
σ
min
⁡
-
Δ
[
∥
δ
b
∥
2
∥
b
∥
2
+
∥
A
^
-
A
∥
2
∥
A
∥
2
]
,
where
(36)
∥
A
∥
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
⁡
{
σ
i
j
}
.
Notice that A
^
-
A
=
Δ
A is a block skew circulant matrix with skew circulant blocks, and ∥
A
^
-
A
∥
2
=
|
-
1
|
∥
A
^
-
A
∥
2
=
∥
A
^
-
A
∥
2. So, we get
(37)
∥
A
^
-
A
∥
2
=
max
⁡
1
≤
j
≤
n
1
≤
j
≤
m
⁡
|
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
ε
i
k
-
1
δ
j
l
-
1
|
≤
max
⁡
1
≤
j
≤
n
1
≤
j
≤
m
⁡
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
|
ε
i
|
k
-
1
|
δ
j
|
l
-
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
|
δ
a
k
l
|
=
Δ
.
Hence, we have the following theorem.Theorem 4.
LetA
,
A
^
,
δ
b
,
Δ
,
σ
min
⁡ be defined as above. If Δ
<
σ
min
⁡, then
(38)
∥
x
^
-
x
∥
2
∥
x
∥
2
≤
σ
max
⁡
σ
min
⁡
-
Δ
(
∥
δ
b
∥
2
∥
b
∥
2
+
Δ
σ
max
⁡
)
,
where
(39)
σ
max
⁡
=
∥
A
∥
2
.Remark 5.
From (38) and (39), the condition number K of the block skew circulant linear system with skew circulant blocks can be easily computed, as well as the bound of perturbation (38).


## 3.2. Optimal Backward Perturbation Bound of the Block Skew Circulant Linear System with Skew Circulant Blocks

Letx
^ be an approximate solution to A
x
=
b and let
(40)
Ω
≡
{
(
Δ
A
,
Δ
b
)
∣
(
A
+
Δ
A
)
x
^
=
b
+
Δ
b
}
,
η
(
x
^
)
≡
inf
⁡
(
Δ
A
,
Δ
b
)
∈
Ω
∥
Δ
A
,
Δ
b
∥
,
(
A
+
Δ
A
)
x
^
=
b
+
Δ
b
,
which is equivalent to
(41)
(
Δ
A
,
Δ
b
)
(
x
^
-
1
)
=
b
-
A
x
^
.
Due to [14], we have
(42)
η
(
x
^
)
=
∥
b
-
A
x
^
∥
2
1
+
∥
x
^
∥
2
2
,
(
∥
∥
being
any
unitary
invariant
norm
⁡
)
.Letx
^ be an approximate solution to A
x
=
b, where A is defined in (1), as follows:
(43)
Ω
≡
{
(
Δ
A
,
Δ
b
)
∣
(
A
+
Δ
A
)
x
^
=
b
+
Δ
b
,
f
f
Δ
A
is
a
block
skew
circulant
matrix
i
f
with
skew
circulant
blocks
}
η
(
x
^
)
≡
inf
⁡
(
Δ
A
,
Δ
b
)
∈
Ω
{
∥
Δ
A
,
Δ
b
∥
F
}
.
Then Ω
≠
ϕ (such as Δ
A
=
0 is a block skew circulant matrix with skew circulant blocks, Δ
b
=
A
x
^
-
b)
(44)
η
2
(
x
^
)
=
inf
⁡
(
Δ
A
,
Δ
b
)
∈
Ω
{
∥
Δ
A
∥
F
2
+
∥
Δ
A
x
^
+
A
x
^
-
b
∥
F
2
}
.
Since
(45)
∥
Δ
A
∥
F
2
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
δ
a
k
l
)
2
,
Δ
A
=
Q
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
C
n
0
k
-
1
⊗
C
m
0
l
-
1
)
Q
T
,
so
(46)
∥
Δ
A
x
^
+
A
x
^
-
b
∥
F
2
=
∥
Q
(
δ
B
11
⋱
δ
B
t
t
)
Q
T
x
^
+
A
x
^
-
b
∥
F
2
=
∥
(
δ
B
11
⋱
δ
B
t
t
)
(
x
1
(
0
)
⋮
x
t
(
0
)
)
-
r
0
∥
F
2
=
∥
(
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
C
11
k
-
1
⊗
C
m
0
l
-
1
)
x
1
(
0
)
⋮
(
∑
k
=
1
n
‍
∑
l
=
1
m
‍
δ
a
k
l
C
t
t
k
-
1
⊗
C
m
0
l
-
1
)
x
t
(
0
)
)
-
r
0
∥
F
2
=
∥
G
0
(
δ
a
11
,
…
,
δ
a
1
m
,
…
,
δ
a
n
1
,
…
,
δ
a
n
m
)
T
-
r
0
∥
F
2
,
where r
0
=
Q
T
(
b
-
A
x
^
), Q
T
x
^
=
(
x
1
(
0
)
⋮
x
t
(
0
)
), G
0
=
(
R
1
,
R
2
,
…
,
R
n
)
∈
R
m
n
×
m
n, and
(47)
R
k
=
(
P
1
,
k
,
1
⋯
P
1
,
k
,
m
⋮
⋱
⋮
P
t
,
k
,
1
⋯
P
t
,
k
,
m
)
,
P
p
,
k
,
l
=
C
p
p
k
-
1
⊗
C
m
0
l
-
1
x
p
(
0
)
,
p
=
1,2
,
…
,
t, k
=
1,2
,
…
,
n, and l
=
1,2
,
…
,
m.Let(48)
f
(
δ
a
11
,
…
,
δ
a
n
m
)
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
(
δ
a
k
l
)
2
+
∥
G
0
(
δ
a
11
⋮
δ
a
n
m
)
-
r
0
∥
F
2
,
then
(49)
∂
f
∂
δ
a
k
l
=
0
,
which is equivalent to
(50)
(
2
m
n
I
m
n
+
2
G
0
T
G
0
)
(
δ
a
11
⋮
δ
a
n
m
)
-
2
G
0
T
r
0
=
0
,
∂
2
f
∂
(
δ
a
k
l
)
2
=
2
m
n
I
m
n
+
2
G
0
T
G
0
>
0
.
Hence f is a convex function about (
δ
a
11
,
…
,
δ
a
n
m
), and the point of minimal value is
(51)
(
δ
a
11
⋮
δ
a
n
m
)
=
(
m
n
I
m
n
+
G
0
T
G
0
)
-
1
G
0
T
r
0
.
Substituting it into (48), we can get the following.Theorem 6.
Letr
0 and G
0 be defined as above; then we have
(52)
η
(
x
^
)
2
=
m
n
r
0
T
G
0
(
m
n
I
m
n
+
G
0
T
G
0
)
-
2
G
0
T
r
0
+
∥
[
G
0
(
m
n
I
m
n
+
G
0
T
G
0
)
-
1
G
0
T
-
I
m
n
]
r
0
∥
F
2
.LetG
0
=
U
Σ
V
T be the singular value decomposition of G
0, where U and V are real orthogonal matrices, Σ
=
diag
⁡
(
σ
1
′
,
…
,
σ
n
m
′
), σ
j
′
≥
0
(
j
=
1,2
,
…
,
n
m
), so
(53)
η
(
x
^
)
2
=
m
n
r
0
T
U
Σ
V
T
(
m
n
I
m
n
+
Σ
2
)
-
2
V
Σ
U
T
r
0
+
∥
[
U
Σ
V
T
(
m
n
I
m
n
+
Σ
2
)
-
1
V
Σ
U
T
-
I
m
n
]
r
0
∥
F
2
=
m
n
r
1
T
Σ
(
m
n
I
m
n
+
Σ
2
)
-
2
Σ
r
1
+
∥
[
Σ
(
m
n
I
m
n
+
Σ
2
)
-
1
Σ
-
I
m
n
]
r
0
∥
F
2
=
m
n
r
1
T
Σ
(
m
n
I
m
n
+
Σ
2
)
-
2
Σ
r
1
+
∥
[
Σ
(
m
n
I
m
n
+
Σ
2
)
-
1
Σ
-
I
m
n
]
r
1
∥
F
2
=
m
n
r
1
T
Σ
(
m
n
I
m
n
+
Σ
2
)
-
2
Σ
r
1
+
m
2
n
2
r
1
T
(
m
n
I
m
n
+
Σ
2
)
-
2
r
1
=
r
1
T
diag
⁡
(
d
1
,
d
2
,
…
,
d
m
n
)
r
1
,
where r
1
=
U
T
r
0, d
j
=
(
m
n
σ
j
′
2
+
m
2
n
2
)
/
(
m
n
+
σ
j
′
2
)
2
=
m
n
/
(
m
n
+
σ
j
′
2
), j
=
1,2
,
…
,
m
n.Remark 7.
Byσ
j
2
≤
∥
G
0
∥
F
2
=
m
n
∥
x
^
∥
2
2, we get 1
+
σ
j
′
2
/
m
n
≤
1
+
∥
x
^
∥
2
2, and hence m
n
/
(
m
n
+
σ
j
′
2
)
≥
1
/
(
1
+
∥
x
^
∥
2
2
).Algorithm 8.
Consider the following.
Step
1. Form the block style spectral decomposition of the matrix C
n
×
n and C
m
×
m,
(54)
C
n
×
n
=
Q
n
(
C
11
C
22
⋱
C
t
t
)
Q
n
T
,
C
m
×
m
=
Q
m
(
D
11
D
22
⋱
D
s
s
)
Q
m
T
.
Step
2. Compute Q
=
(
Q
n
⊗
I
m
)
(
I
n
⊗
Q
m
).
Step
3. Compute r
=
b
-
A
x
^.
Step
4. Compute r
0
=
Q
T
r.
Step
5. Compute Q
T
x
^
=
(
x
1
(
0
)
,
…
,
x
t
(
0
)
)
T.
Step
6. Form G
0.
Step
7. Compute η
2
(
x
^
).


## 3.3. Numerical Example

In this section, we give a simple numerical example to verify the conclusions above. Suppose thatn
=
3, m
=
2 in the following example.If the coefficient matrix of block skew circulant linear system with skew circulant blocks isA
=
B
C
-
1
,
-
1
3,2
(
1,2
,
4.5,3
,
4,2.5
), and the constant vector b
=
(
1,2
,
1,0
,
3,4
)
T. Now, for comparative analysis, we give three perturbations in the following:
(55)
Δ
A
1
=
B
C
-
1
,
-
1
3,2
(
0.01,0.03,0.02
,
-
0.05
,
-
0.03,0.01
)
,
Δ
b
1
=
(
0.1,0.3,0
,
-
0.2,0.01,0.04
)
T
,
Δ
A
2
=
B
C
-
1
,
-
1
3,2
(
0.01,0.01,0.01,0.01,0.01,0.01
)
,
Δ
b
2
=
(
0.01,0.01,0.01,0.01,0.01,0.01
)
T
,
Δ
A
3
=
B
C
-
1
,
-
1
3,2
(
0.001,0.001,0.001,0.001,0.001,0.001
)
,
Δ
b
3
=
(
0.001,0.001,0.001,0.001,0.001,0.001
)
T
,
then by equation A
^
x
^
=
b
^, we get the approximate solution of A
x
=
b correspondingly as
(56)
x
=
(
-
1.0505
,
0.6490
,
1.0280
,
-
1.1028
,
-
0.9215
,
1.2482
)
,
x
^
1
=
(
-
1.1526
,
0.6358
,
1.1192
,
-
1.0611
,
-
1.0158
,
1.2286
)
,
x
^
2
=
(
-
1.0396
,
0.6473
,
1.0178
,
-
1.1003
,
-
0.9109
,
1.2484
)
,
x
^
3
=
(
-
1.0494
,
0.6489
,
1.0270
,
-
1.1025
,
-
0.9204
,
1.2482
)
,
where x is the solution of A
x
=
b and x
i (i
=
1,2
,
3) is the solution of (
A
+
Δ
A
i
)
x
=
b
+
Δ
b.According to the Algorithm, we obtain Table1, where ϵ means relative error of block skew circulant linear system with skew circulant blocks, K
=
max
⁡
{
σ
i
j
}
/
min
⁡
{
σ
i
j
} is the condition number, η
1
(
x
^
)
=
∥
b
-
A
x
^
∥
2
/
1
+
∥
x
^
∥
2
2 and η
2 are obtained from the Algorithm.Table 1
ϵ
K
η
1
(
x
^
)
η
2
(
x
^
)
Case0
0
6.472
0
0
Case1
0.0694
6.193
0.1252
0.2487
Case2
0.0075
6.438
0.0127
0.0223
Case3
7.5122
×
1
0
-
4
6.468
0.0013
0.0022From the tabular, we know that the conclusions above are right and the Algorithm is efficient.


## 4. Conclusion

The related problems of block skew circulant matrix with skew circulant blocks are considered in this paper. We not only present block style spectral decomposition and singular value, but also study backward perturbation analysis for the block skew circulant linear system with skew circulant blocks. The reason why we focus our attentions on block skew circulant matrix with skew circulant blocks is to explore the application of block skew circulant matrix with skew circulant blocks in the related field of medicine and real-time tracking. On the basis of existing application situation [23], we conjecture that SVD decomposition of block skew circulant matrix with skew circulant blocks will play an important role in CT-perfusion imaging of human brain. On the basis of method [7] and ideas of [24], we will exploit real-time tracking with kernel matrix of block skew circulant matrix with skew circulant blocks structure. The circulant singular value decomposition (cSVD) techniques with a block-circulant deconvolution matrix [25–29] were used to perform the deconvolution calculation to obtain the [rCBF.R
(
t
)] curve [25, 26]. The maximum value of the [rCBF.R
(
t
)] curve was used as the rCBF. We will exploit the skew circulant singular value decomposition (scSVD) techniques of a block skew circulant matrix with skew circulant blocks deconvolution matrix to obtain the [rCBF.R
(
t
)] curve.



---

*Source: 523102-2014-06-15.xml*