# Analysis of the Structured Perturbation for the BCSCB Linear System

Authors: Xia Tang; Zhaolin Jiang
Journal: Abstract and Applied Analysis
 (2015)

---

## Abstract

Circulant and block circulant type matrices are important tools in solving networked systems. In this paper, based on the style spectral decomposition of the basic circulant matrix and the basic skew circulant matrix, the block style spectral decomposition of the BCSCB matrix is obtained. And then, the structure perturbation is analysed, which includes the condition number and relative error of the BCSCB linear system. Then the optimal backward perturbation bound of the BCSCB linear system is discussed. Simultaneously, the algorithm for the optimal backward perturbation bound is given. Finally, a numerical example is provided to verify the effectiveness of the algorithm.


---

## Body

## 1. Introduction

It is an active objective that circulant and block circulant type matrices are applied to networks engineering. The stability region in the parameters space is extended by the breaking of a delayed ring neural network where the form of time-delay systems isx
˙
+
A
x
(
t
)
+
B
x
(
t
-
τ
)
=
0, where B is a circulant matrix, if the number of the neurons is sufficiently large in [1]. In [2], the question of when circulant quantum spin networks with nearest-neighbor couplings can give perfect state transfer is solved. The properties of linear diffusion algorithm are investigated both by a worst-case analysis and by a probabilistic analysis and are shown to depend on the spectral properties of the circulant matrix in [3]. A viable option for increasing the lifetime of the sensor network for a small loss in accuracy of the query results whose matrices are circulant is offered in [4]. In [5], the authors considered the kinetics of an autocatalytic reaction network in which replication and catalytic actions are separated by a translation step. They found that the behavior of such a system is closely related to second-order replicator equations, where the second-order replicator equations are circulant interaction matrices. In order to obtain the optimal routing in double loop networks, the problem of finding the shortest path in circulant graphs with an arbitrary number of jumps is studied in [6].A block circulant with skew circulant blocks matrix with the first row(
c
11
,
…
,
c
1
m
,
c
21
,
…
,
c
2
m
,
…
,
c
n
1
,
…
,
c
n
m
) has the following form:(1)
C
=
C
1
C
2
⋯
C
n
-
1
C
n
C
n
C
1
C
2
⋯
C
n
-
1
⋮
⋱
⋱
⋱
⋮
C
3
⋱
C
n
C
1
C
2
C
2
C
3
⋯
C
n
C
1
,and for any k
=
1,2
,
…
,
n, (2)
C
k
=
c
k
1
c
k
2
⋯
c
k
(
m
-
1
)
c
k
m
-
c
k
m
c
k
1
c
k
2
⋯
c
k
(
m
-
1
)
⋮
⋱
⋱
⋱
⋮
-
c
k
3
⋱
-
c
k
m
c
k
1
c
k
2
-
c
k
2
-
c
k
3
⋯
-
c
k
m
c
k
1
.The matrix C is denoted by BCSCB(
c
11
,
…
,
c
1
m
,
…
,
c
n
1
,
…
,
c
n
m
).Rigal and Gaches [7] considered a posteriori analysis of the compatibility of a computed solution to the uncertain data of a linear system by some new theorems generalizing a result of Oettli and Prager. In [8], the style spectral decomposition of the skew circulant matrix is given and the optimal backward perturbation analysis for the skew circulant linear system is discussed. Liu and Guo [9] obtained the bound of the optimal backward perturbation for a block circulant linear system. J.-G. Sun and Z. Sun [10] studied the optimal backward perturbation bounds for undetermined systems. In [11], the optimal backward perturbation analysis for the block skew circulant linear system with skew circulant blocks is given by Li et al.


## 2. The Block Style Spectral Decomposition of the BCSCB Matrix

Let matrixC be a BCSCB matrix as the form (1); then by using the properties of Kronecker products in [12], the C can be decomposed as (3)
C
=
∑
k
=
1
n
‍
Π
k
-
1
⊗
C
k
,where Π is a square matrix of order n, and it has the following form: (4)
Π
=
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋱
⋱
⋱
⋮
0
⋯
0
0
1
1
0
⋯
0
0
.Based on(
2.5
) and (
2.6
) in [9], the style spectral decomposition of the matrix Π is (5)
Π
=
Q
Π
0
Q
T
,where Q is an orthogonal matrix.Whenn is even, (6)
Π
0
=
π
1
π
2
⋱
π
n
/
2
,
π
n
/
2
=
-
1
0
0
1
,
π
j
=
cos
⁡
θ
j
sin
θ
j
-
sin
θ
j
cos
⁡
θ
j
,
θ
j
=
2
j
n
π
,
j
=
1,2
,
…
,
n
2
-
1
.Whenn is odd, (7)
Π
0
=
π
1
π
2
⋱
π
(
n
-
1
)
/
2
1
,
π
j
=
cos
⁡
θ
j
sin
θ
j
-
sin
θ
j
cos
⁡
θ
j
,
θ
j
=
2
j
n
π
,
j
=
1,2
,
…
,
n
-
1
2
.Taking (3) and (5) into consideration, the matrix C can be decomposed as (8)
C
=
∑
k
=
1
n
‍
Π
k
-
1
⊗
C
k
=
∑
k
=
1
n
‍
Q
Π
0
k
-
1
Q
T
⊗
C
k
=
∑
k
=
1
n
‍
Q
⊗
I
m
Π
0
k
-
1
⊗
C
k
Q
T
⊗
I
m
=
Q
⊗
I
m
∑
k
=
1
n
‍
Π
0
k
-
1
⊗
C
k
Q
T
⊗
I
m
.
Q
⊗
I
m is an orthogonal matrix obviously. So (8) is the block style spectral decomposition of the matrix C.


## 3. Analysis of the Structured Perturbation

The structured perturbation analysis for BCSCB linear system is given in this section. We discuss the condition number and the relative error of the BCSCB linear system. The optimal backward perturbation bound of the BCSCB linear system is analysed. And, at the end of the section, we give the algorithm for the optimal backward perturbation bound.


### 3.1. Condition Number and Relative Error of BCSCB Linear System

Consider(9)
C
x
=
b
,where C is defined in (1).From (8) and the property of Kronecker products in [12], the matrix C can be expressed by using the elements in its first row as (10)
C
=
∑
k
=
1
n
‍
Π
k
-
1
⊗
C
k
=
∑
k
=
1
n
‍
Π
k
-
1
⊗
∑
l
=
1
m
‍
c
k
l
Ψ
l
-
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
k
-
1
⊗
Ψ
l
-
1
,where Ψ is a square matrix of order m, and it has the following form: (11)
Ψ
=
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋱
⋱
⋱
⋮
0
⋯
0
0
1
-
1
0
⋯
0
0
.Based on(
10
) and (
11
) in [8], the style spectral decomposition of the matrix Ψ is (12)
Ψ
=
J
Ψ
0
J
T
,where J is an orthogonal matrix.Whenm is even, (13)
Ψ
0
=
ψ
1
ψ
2
⋱
ψ
m
/
2
.Whenm is odd, (14)
Ψ
0
=
ψ
1
ψ
2
⋱
ψ
(
m
-
1
)
/
2
-
1
,
ψ
h
=
cos
⁡
θ
h
sin
θ
h
-
sin
θ
h
cos
⁡
θ
h
,
θ
h
=
2
h
-
1
n
π
,
h
=
1,2
,
…
,
m
2
,
m
is
even
.
1,2
,
…
,
m
-
1
2
,
m
is
odd
.Furthermore, (10) can be expressed as follows: (15)
C
=
Q
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
Q
T
,and here Q
=
(
Q
⊗
I
m
)
(
I
n
⊗
J
), where I
n and I
m are identity matrices with orders n and m, respectively.The problem will be discussed at two different situations.(1) Whenn is even,(16)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
=
Λ
11
⋱
Λ
t
t
Υ
1
,
Λ
p
p
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
π
p
k
-
1
⊗
Ψ
0
l
-
1
,
t
=
n
2
-
1
,
p
=
1,2
,
…
,
t
,
Υ
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
diag
(
-
Ψ
0
l
-
1
,
Ψ
0
l
-
1
)
.(2) Whenn is odd, (17)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
=
Λ
11
⋱
Λ
t
t
Υ
2
,
Λ
p
p
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
π
p
k
-
1
⊗
Ψ
0
l
-
1
,
t
=
n
-
1
2
,
p
=
1,2
,
…
,
t
,
Υ
2
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Ψ
0
l
-
1
.We denote byω
i
(
i
=
1,2
,
…
,
n
) the eigenvalues of matrix Π [9], and δ
j
(
j
=
1,2
,
…
,
m
) are denoted as the eigenvalues of matrix Ψ [8], and then the eigenvalues of C are obtained (refer to [12, 13]). Consider(18)
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
ω
i
k
-
1
δ
j
l
-
1
.Lemma 1.
C is a nonsingular matrix if and only if f
(
ω
i
,
δ
j
)
≠
0
(
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
), where (19)
f
ω
i
,
δ
j
=
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
ω
i
k
-
1
δ
j
l
-
1
.Let(20)
σ
i
j
=
f
ω
i
,
δ
j
,
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
,
κ
=
max
⁡
{
σ
i
j
}
min
⁡
{
σ
i
j
}
.Theorem 2.
IfC
=
B
C
S
C
B
(
c
11
,
…
,
c
1
m
,
…
,
c
n
1
,
…
,
c
n
m
), then the singular values of the matrix C are σ
11
,
…
,
σ
1
m
,
σ
21
,
…
,
σ
2
m
,
…
,
σ
n
1
,
…
,
σ
n
m.Proof.
Assume the conjugate transpose ofC is (21)
C
*
=
C
1
*
C
n
*
⋯
C
3
*
C
2
*
C
2
*
C
1
*
⋯
⋮
C
3
*
⋮
C
2
*
⋯
C
n
*
⋮
C
n
-
1
*
⋮
⋱
C
1
*
C
n
*
C
n
*
C
n
-
1
*
⋯
C
2
*
C
1
*
.
By a direct calculation,C is a normal matrix as C
C
*
=
C
*
C. Then matrix C is a unitarily diagonalizable matrix based on Theorem 2.5
.
4 in [14]. Then there exists a unitary matrix U
∈
M
m
n, such that (22)
U
*
C
U
=
Λ
=
diag
λ
11
,
…
,
λ
1
m
,
…
,
λ
n
1
,
…
,
λ
n
m
,where λ
i
j
(
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
) are the eigenvalues of matrix C. Taking the conjugate transpose at both sides of (22), we get (23)
U
*
C
*
U
=
Λ
=
diag
λ
¯
11
,
…
,
λ
¯
1
m
,
…
,
λ
¯
n
1
,
…
,
λ
¯
n
m
;then (24)
U
*
C
*
C
U
=
U
*
C
*
U
U
*
C
U
=
diag
λ
11
2
,
…
,
λ
1
m
2
,
…
,
λ
n
1
2
,
…
,
λ
n
m
2
.
And|
λ
i
j
|
2 are the eigenvalues of the matrix C
*
C, for any i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m. Therefore, the singular values of C are (25)
σ
i
j
(
C
)
=
λ
i
j
C
*
C
1
/
2
=
λ
i
j
.Recall (19) and (20); the proof is completed.As the definition of the spectral norm of matrixC is (26)
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
λ
i
j
C
*
C
1
/
2
,via Theorem 2, the following corollary is obtained.Corollary 3.
LetC
=
B
C
S
C
B
(
c
11
,
…
,
c
1
m
,
…
,
c
n
1
,
…
,
c
n
m
); then the spectrum norm of matrix C is (27)
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
.LetΔ
C be a perturbation of the coefficient matrix C and let Δ
b be a perturbation of the vector b, where Δ
C
=
BCSCB
ε
c
11
,
…
,
ε
c
1
m
,
…
,
ε
c
n
1
,
…
,
ε
c
n
m has the following form: (28)
Δ
C
=
Δ
C
1
⋯
Δ
C
n
-
1
Δ
C
n
Δ
C
n
Δ
C
1
⋯
Δ
C
n
-
1
⋮
⋱
⋱
⋮
Δ
C
2
⋯
Δ
C
n
Δ
C
1
,and for any k
=
1,2
,
…
,
m, (29)
Δ
C
k
=
ε
c
k
1
⋯
ε
k
(
m
-
1
)
ε
c
k
m
-
ε
c
k
m
ε
c
k
1
⋯
ε
c
k
(
m
-
1
)
⋮
⋱
⋱
⋮
-
ε
c
k
2
⋯
-
ε
c
k
m
ε
c
k
1
.Let (30)
C
^
=
C
+
Δ
C
,
b
^
=
b
+
Δ
b
,
Δ
b
=
ε
b
,
f
^
ω
i
,
δ
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
+
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
.If (31)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
<
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
,then (32)
f
^
ω
i
,
δ
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
+
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
≥
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
ω
i
k
-
1
δ
j
l
-
1
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
≥
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
>
0
;through Lemma 1, C
^ is a nonsingular matrix. Let (33)
σ
min
⁡
=
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
,
ρ
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
.By C
x
=
b
,
C
^
x
^
=
b
^, we obtain (34)
x
^
-
x
=
C
^
-
1
b
^
-
C
-
1
b
=
C
^
-
1
b
+
ε
b
-
C
-
1
b
=
C
^
-
1
ε
b
+
C
^
-
1
-
C
-
1
b
=
C
^
-
1
ε
b
+
C
^
-
1
-
C
-
1
C
x
=
C
^
-
1
ε
b
+
C
^
-
1
(
C
-
C
^
)
x
,
∥
x
^
-
x
∥
2
≤
C
^
-
1
2
ε
b
2
+
C
^
-
1
2
C
^
-
C
2
x
2
≤
ε
b
2
σ
min
⁡
-
ρ
+
C
^
-
C
2
x
2
σ
min
⁡
-
ρ
,
x
^
-
x
2
x
2
≤
ε
b
2
σ
min
⁡
-
ρ
∥
x
∥
2
+
C
^
-
C
2
σ
min
⁡
-
ρ
=
C
2
σ
min
⁡
-
ρ
ε
b
2
C
2
x
2
+
C
^
-
C
2
C
2
≤
C
2
σ
min
⁡
-
ρ
ε
b
2
b
2
+
C
^
-
C
2
C
2
,where(35)
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
{
σ
i
j
}
.
C
^
-
C
=
Δ
C is a BCSCB matrix apparently, and C
-
C
^
2
=
|
-
1
|
C
^
-
C
2
=
C
^
-
C
2. So (36)
C
^
-
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
≤
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
=
ρ
.The following theorem can be obtained.Theorem 4.
LetC, C
^, Δ
b, ρ, and σ
min
⁡ be defined as above. If ρ
<
σ
min
⁡, then (37)
x
^
-
x
2
x
2
≤
σ
max
⁡
σ
min
⁡
-
ρ
ε
b
2
b
2
+
ρ
σ
max
⁡
,where (38)
σ
max
⁡
=
C
2
.Remark 5.
The condition numberκ of the BCSCB matrix can be easily computed with the basis of (37) and (38), the same as the bound of perturbation (37).


### 3.2. Optimal Backward Perturbation Bound of the BCSCB Linear System

In this part, a new method is given to obtain the minimal value of the perturbation bound, which is only related to the perturbation of the coefficient matrix and the vector. At the end of this part, the algorithm for the optimal backward perturbation bound is given.Letx
^ be an approximate solution to C
x
=
b and let (39)
Ω
≡
Δ
C
,
Δ
b
∣
C
+
Δ
C
x
^
=
b
+
Δ
b
,
ξ
(
x
^
)
≡
inf
⁡
(
Δ
C
,
Δ
b
)
∈
Ω
Δ
C
,
Δ
b
,
C
+
Δ
C
x
^
=
b
+
Δ
b
,which is equal to (40)
Δ
C
,
Δ
b
x
^
-
1
=
b
-
C
x
^
.According to [7], we can get (41)
ξ
(
x
^
)
=
b
-
C
x
^
2
1
+
x
^
2
2
·
is
unitary
invariant
norm
.Letx
^ be an approximate solution to C
x
=
b, where C is defined in (1): (42)
Ω
≡
Δ
C
,
Δ
b
∣
C
+
Δ
C
x
^
=
b
+
Δ
b
,
Δ
C
is
a
BCSCB
matrix
,
ξ
(
x
^
)
≡
inf
⁡
(
Δ
C
,
Δ
b
∈
Ω
)
{
∥
Δ
C
,
Δ
b
∥
F
}
.So Ω
≠
ϕ (as Δ
C
=
0 is a BCSCB matrix, Δ
b
=
C
^
x
^
-
b). Hence, (43)
ξ
2
x
^
=
inf
⁡
Δ
C
,
Δ
b
∈
Ω
Δ
C
F
2
+
Δ
C
x
^
+
C
x
^
-
b
F
2
.Since (44)
Δ
C
F
2
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
2
,
Δ
C
=
Q
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
Q
T
,the question will be analysed in two different conditions.(1) Whenn is even, (45)
Δ
C
x
^
+
C
x
^
-
b
F
2
=
Q
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
1
Q
T
x
^
+
C
x
^
-
b
F
2
=
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
1
x
1
(
0
)
⋮
x
t
(
0
)
x
t
+
1
(
0
)
-
r
0
F
2
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
1
k
-
1
⊗
Ψ
0
l
-
1
x
1
(
0
)
⋮
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
t
k
-
1
⊗
Ψ
0
l
-
1
x
t
(
0
)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
diag
-
Ψ
0
l
-
1
,
Ψ
0
l
-
1
x
t
+
1
(
0
)
-
r
0
F
2
,
=
Φ
ε
c
11
,
…
,
ε
c
1
m
,
…
,
ε
c
n
1
,
…
,
ε
c
n
m
T
-
r
0
F
2
,where (46)
r
0
=
Q
T
b
-
C
x
^
,
Q
T
x
^
=
x
1
(
0
)
⋯
x
t
(
0
)
x
t
+
1
(
0
)
T
,
Φ
=
Φ
1
,
Φ
2
,
…
,
Φ
n
-
1
,
∑
l
=
1
m
‍
diag
-
Ψ
0
l
-
1
,
Ψ
0
l
-
1
x
t
+
1
0
,
Φ
k
=
ϕ
1
,
k
,
1
⋯
ϕ
1
,
k
,
m
⋮
⋱
⋮
ϕ
t
,
k
,
1
⋯
ϕ
t
,
k
,
m
,
ϕ
p
,
k
,
l
=
π
p
k
-
1
⊗
Ψ
0
l
-
1
x
p
(
0
)
,
t
=
n
2
-
1
,
p
=
1,2
,
…
,
t
,
k
=
1,2
,
…
,
n
-
1
,
l
=
1,2
,
…
,
m
.(2) Whenn is odd, (47)
Δ
C
x
^
+
C
x
^
-
b
F
2
=
Q
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
2
Q
T
x
^
+
C
x
^
-
b
F
2
=
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
2
x
1
(
0
)
⋮
x
t
(
0
)
x
t
+
1
(
0
)
-
r
0
F
2
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
1
k
-
1
⊗
Ψ
0
l
-
1
x
1
(
0
)
⋮
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
t
k
-
1
⊗
Ψ
0
l
-
1
x
t
(
0
)
∑
k
=
1
n
‍
∑
l
=
1
n
‍
ε
c
k
l
Ψ
0
l
-
1
x
t
+
1
(
0
)
-
r
0
F
2
=
Φ
ε
c
11
,
…
,
ε
c
1
m
,
…
,
ε
c
n
1
,
…
,
ε
c
n
m
T
-
r
0
F
2
,where (48)
r
0
=
Q
T
b
-
C
x
^
,
Q
T
x
^
=
x
1
(
0
)
⋯
x
t
(
0
)
x
t
+
1
(
0
)
T
,
Φ
=
Φ
1
,
Φ
2
,
…
,
Φ
n
-
1
,
∑
l
=
1
m
‍
Ψ
0
l
-
1
x
t
+
1
0
,
Φ
k
=
ϕ
1
,
k
,
1
⋯
ϕ
1
,
k
,
m
⋮
⋱
⋮
ϕ
t
,
k
,
1
⋯
ϕ
t
,
k
,
m
,
ϕ
p
,
k
,
l
=
π
p
k
-
1
⊗
Ψ
0
l
-
1
x
p
(
0
)
,
t
=
n
-
1
2
,
p
=
1,2
,
…
,
t
,
k
=
1,2
,
…
,
n
-
1
,
l
=
1,2
,
…
,
m
.Let(49)
g
ε
c
11
,
…
,
ε
c
n
m
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
2
+
Φ
ε
c
11
⋮
ε
c
n
m
-
r
0
F
2
,and then (50)
∂
g
∂
ε
c
k
l
=
0
,which is equal to (51)
2
m
n
I
m
n
+
2
Φ
T
Φ
ε
c
11
⋮
ε
c
n
m
-
2
Φ
T
r
0
=
0
,
∂
2
g
∂
(
ε
c
k
l
)
2
=
2
m
n
I
m
n
+
2
Φ
T
Φ
>
0
.As g is a convex function of (
ε
c
11
,
…
,
ε
c
n
m
), the point of the minimal value is (52)
ε
c
11
⋮
ε
c
n
m
=
m
n
I
m
n
+
Φ
T
Φ
-
1
Φ
T
r
0
.Substituting it back into (49), we obtain the following.Theorem 6.
Consider(53)
ξ
2
x
=
m
n
r
0
T
Φ
m
n
I
m
n
+
Φ
T
Φ
-
2
Φ
T
r
0
=
Φ
m
n
I
m
n
+
Φ
T
Φ
-
1
Φ
T
-
I
m
n
r
0
F
2
.LetΦ
=
U
Σ
V
* be the singular value decomposition of Φ, where U and V are unitary matrices, Σ
=
diag
(
σ
1
′
,
…
,
σ
n
m
′
), and σ
j
′
≥
0
(
j
=
1,2
,
…
,
n
m
); then (54)
ξ
2
x
=
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
α
1
⋱
α
m
n
r
1
,where r
1
=
U
T
r
0, α
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.
Asσ
j
2
≤
Φ
F
2
=
m
n
∥
x
^
∥
2
2, then 1
+
x
^
2
2
≥
1
+
σ
j
′
2
/
m
n can be obtained; hence, m
n
/
(
m
n
+
σ
j
′
2
)
≥
1
/
(
1
+
x
^
2
2
).From what we analysed above, the following algorithm can be obtained.Algorithm 8.
We have the following steps.
Step 1. Form the style spectral decomposition of the matrixes Π and Ψ:(55)
Π
=
Q
Π
0
Q
T
,
Ψ
=
J
Ψ
0
J
T
.
Step 2. Form the block style spectral decomposition of the BCSCB matrix.
Step 3. Compute r
=
b
-
C
x
^.
Step 4. Compute r
0
=
Q
T
r.
Step 5. Compute (56)
Q
T
x
^
=
x
1
(
0
)
⋮
x
t
(
0
)
x
t
+
1
(
0
)
.
Step 6. Form Φ.
Step 7. Compute the singular value decomposition of Φ.
Step 8. Compute ξ
2
(
x
^
).


## 3.1. Condition Number and Relative Error of BCSCB Linear System

Consider(9)
C
x
=
b
,where C is defined in (1).From (8) and the property of Kronecker products in [12], the matrix C can be expressed by using the elements in its first row as (10)
C
=
∑
k
=
1
n
‍
Π
k
-
1
⊗
C
k
=
∑
k
=
1
n
‍
Π
k
-
1
⊗
∑
l
=
1
m
‍
c
k
l
Ψ
l
-
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
k
-
1
⊗
Ψ
l
-
1
,where Ψ is a square matrix of order m, and it has the following form: (11)
Ψ
=
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋱
⋱
⋱
⋮
0
⋯
0
0
1
-
1
0
⋯
0
0
.Based on(
10
) and (
11
) in [8], the style spectral decomposition of the matrix Ψ is (12)
Ψ
=
J
Ψ
0
J
T
,where J is an orthogonal matrix.Whenm is even, (13)
Ψ
0
=
ψ
1
ψ
2
⋱
ψ
m
/
2
.Whenm is odd, (14)
Ψ
0
=
ψ
1
ψ
2
⋱
ψ
(
m
-
1
)
/
2
-
1
,
ψ
h
=
cos
⁡
θ
h
sin
θ
h
-
sin
θ
h
cos
⁡
θ
h
,
θ
h
=
2
h
-
1
n
π
,
h
=
1,2
,
…
,
m
2
,
m
is
even
.
1,2
,
…
,
m
-
1
2
,
m
is
odd
.Furthermore, (10) can be expressed as follows: (15)
C
=
Q
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
Q
T
,and here Q
=
(
Q
⊗
I
m
)
(
I
n
⊗
J
), where I
n and I
m are identity matrices with orders n and m, respectively.The problem will be discussed at two different situations.(1) Whenn is even,(16)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
=
Λ
11
⋱
Λ
t
t
Υ
1
,
Λ
p
p
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
π
p
k
-
1
⊗
Ψ
0
l
-
1
,
t
=
n
2
-
1
,
p
=
1,2
,
…
,
t
,
Υ
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
diag
(
-
Ψ
0
l
-
1
,
Ψ
0
l
-
1
)
.(2) Whenn is odd, (17)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
=
Λ
11
⋱
Λ
t
t
Υ
2
,
Λ
p
p
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
π
p
k
-
1
⊗
Ψ
0
l
-
1
,
t
=
n
-
1
2
,
p
=
1,2
,
…
,
t
,
Υ
2
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
Ψ
0
l
-
1
.We denote byω
i
(
i
=
1,2
,
…
,
n
) the eigenvalues of matrix Π [9], and δ
j
(
j
=
1,2
,
…
,
m
) are denoted as the eigenvalues of matrix Ψ [8], and then the eigenvalues of C are obtained (refer to [12, 13]). Consider(18)
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
ω
i
k
-
1
δ
j
l
-
1
.Lemma 1.
C is a nonsingular matrix if and only if f
(
ω
i
,
δ
j
)
≠
0
(
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
), where (19)
f
ω
i
,
δ
j
=
λ
i
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
ω
i
k
-
1
δ
j
l
-
1
.Let(20)
σ
i
j
=
f
ω
i
,
δ
j
,
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
,
κ
=
max
⁡
{
σ
i
j
}
min
⁡
{
σ
i
j
}
.Theorem 2.
IfC
=
B
C
S
C
B
(
c
11
,
…
,
c
1
m
,
…
,
c
n
1
,
…
,
c
n
m
), then the singular values of the matrix C are σ
11
,
…
,
σ
1
m
,
σ
21
,
…
,
σ
2
m
,
…
,
σ
n
1
,
…
,
σ
n
m.Proof.
Assume the conjugate transpose ofC is (21)
C
*
=
C
1
*
C
n
*
⋯
C
3
*
C
2
*
C
2
*
C
1
*
⋯
⋮
C
3
*
⋮
C
2
*
⋯
C
n
*
⋮
C
n
-
1
*
⋮
⋱
C
1
*
C
n
*
C
n
*
C
n
-
1
*
⋯
C
2
*
C
1
*
.
By a direct calculation,C is a normal matrix as C
C
*
=
C
*
C. Then matrix C is a unitarily diagonalizable matrix based on Theorem 2.5
.
4 in [14]. Then there exists a unitary matrix U
∈
M
m
n, such that (22)
U
*
C
U
=
Λ
=
diag
λ
11
,
…
,
λ
1
m
,
…
,
λ
n
1
,
…
,
λ
n
m
,where λ
i
j
(
i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m
) are the eigenvalues of matrix C. Taking the conjugate transpose at both sides of (22), we get (23)
U
*
C
*
U
=
Λ
=
diag
λ
¯
11
,
…
,
λ
¯
1
m
,
…
,
λ
¯
n
1
,
…
,
λ
¯
n
m
;then (24)
U
*
C
*
C
U
=
U
*
C
*
U
U
*
C
U
=
diag
λ
11
2
,
…
,
λ
1
m
2
,
…
,
λ
n
1
2
,
…
,
λ
n
m
2
.
And|
λ
i
j
|
2 are the eigenvalues of the matrix C
*
C, for any i
=
1,2
,
…
,
n
,
j
=
1,2
,
…
,
m. Therefore, the singular values of C are (25)
σ
i
j
(
C
)
=
λ
i
j
C
*
C
1
/
2
=
λ
i
j
.Recall (19) and (20); the proof is completed.As the definition of the spectral norm of matrixC is (26)
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
λ
i
j
C
*
C
1
/
2
,via Theorem 2, the following corollary is obtained.Corollary 3.
LetC
=
B
C
S
C
B
(
c
11
,
…
,
c
1
m
,
…
,
c
n
1
,
…
,
c
n
m
); then the spectrum norm of matrix C is (27)
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
.LetΔ
C be a perturbation of the coefficient matrix C and let Δ
b be a perturbation of the vector b, where Δ
C
=
BCSCB
ε
c
11
,
…
,
ε
c
1
m
,
…
,
ε
c
n
1
,
…
,
ε
c
n
m has the following form: (28)
Δ
C
=
Δ
C
1
⋯
Δ
C
n
-
1
Δ
C
n
Δ
C
n
Δ
C
1
⋯
Δ
C
n
-
1
⋮
⋱
⋱
⋮
Δ
C
2
⋯
Δ
C
n
Δ
C
1
,and for any k
=
1,2
,
…
,
m, (29)
Δ
C
k
=
ε
c
k
1
⋯
ε
k
(
m
-
1
)
ε
c
k
m
-
ε
c
k
m
ε
c
k
1
⋯
ε
c
k
(
m
-
1
)
⋮
⋱
⋱
⋮
-
ε
c
k
2
⋯
-
ε
c
k
m
ε
c
k
1
.Let (30)
C
^
=
C
+
Δ
C
,
b
^
=
b
+
Δ
b
,
Δ
b
=
ε
b
,
f
^
ω
i
,
δ
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
+
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
.If (31)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
<
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
,then (32)
f
^
ω
i
,
δ
j
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
+
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
≥
∑
k
=
1
n
‍
∑
l
=
1
m
‍
c
k
l
ω
i
k
-
1
δ
j
l
-
1
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
≥
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
-
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
>
0
;through Lemma 1, C
^ is a nonsingular matrix. Let (33)
σ
min
⁡
=
min
⁡
1
≤
i
≤
n
1
≤
j
≤
m
σ
i
j
,
ρ
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
.By C
x
=
b
,
C
^
x
^
=
b
^, we obtain (34)
x
^
-
x
=
C
^
-
1
b
^
-
C
-
1
b
=
C
^
-
1
b
+
ε
b
-
C
-
1
b
=
C
^
-
1
ε
b
+
C
^
-
1
-
C
-
1
b
=
C
^
-
1
ε
b
+
C
^
-
1
-
C
-
1
C
x
=
C
^
-
1
ε
b
+
C
^
-
1
(
C
-
C
^
)
x
,
∥
x
^
-
x
∥
2
≤
C
^
-
1
2
ε
b
2
+
C
^
-
1
2
C
^
-
C
2
x
2
≤
ε
b
2
σ
min
⁡
-
ρ
+
C
^
-
C
2
x
2
σ
min
⁡
-
ρ
,
x
^
-
x
2
x
2
≤
ε
b
2
σ
min
⁡
-
ρ
∥
x
∥
2
+
C
^
-
C
2
σ
min
⁡
-
ρ
=
C
2
σ
min
⁡
-
ρ
ε
b
2
C
2
x
2
+
C
^
-
C
2
C
2
≤
C
2
σ
min
⁡
-
ρ
ε
b
2
b
2
+
C
^
-
C
2
C
2
,where(35)
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
{
σ
i
j
}
.
C
^
-
C
=
Δ
C is a BCSCB matrix apparently, and C
-
C
^
2
=
|
-
1
|
C
^
-
C
2
=
C
^
-
C
2. So (36)
C
^
-
C
2
=
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
≤
max
⁡
1
≤
i
≤
n
1
≤
j
≤
m
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
ω
i
k
-
1
δ
j
l
-
1
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
=
ρ
.The following theorem can be obtained.Theorem 4.
LetC, C
^, Δ
b, ρ, and σ
min
⁡ be defined as above. If ρ
<
σ
min
⁡, then (37)
x
^
-
x
2
x
2
≤
σ
max
⁡
σ
min
⁡
-
ρ
ε
b
2
b
2
+
ρ
σ
max
⁡
,where (38)
σ
max
⁡
=
C
2
.Remark 5.
The condition numberκ of the BCSCB matrix can be easily computed with the basis of (37) and (38), the same as the bound of perturbation (37).


## 3.2. Optimal Backward Perturbation Bound of the BCSCB Linear System

In this part, a new method is given to obtain the minimal value of the perturbation bound, which is only related to the perturbation of the coefficient matrix and the vector. At the end of this part, the algorithm for the optimal backward perturbation bound is given.Letx
^ be an approximate solution to C
x
=
b and let (39)
Ω
≡
Δ
C
,
Δ
b
∣
C
+
Δ
C
x
^
=
b
+
Δ
b
,
ξ
(
x
^
)
≡
inf
⁡
(
Δ
C
,
Δ
b
)
∈
Ω
Δ
C
,
Δ
b
,
C
+
Δ
C
x
^
=
b
+
Δ
b
,which is equal to (40)
Δ
C
,
Δ
b
x
^
-
1
=
b
-
C
x
^
.According to [7], we can get (41)
ξ
(
x
^
)
=
b
-
C
x
^
2
1
+
x
^
2
2
·
is
unitary
invariant
norm
.Letx
^ be an approximate solution to C
x
=
b, where C is defined in (1): (42)
Ω
≡
Δ
C
,
Δ
b
∣
C
+
Δ
C
x
^
=
b
+
Δ
b
,
Δ
C
is
a
BCSCB
matrix
,
ξ
(
x
^
)
≡
inf
⁡
(
Δ
C
,
Δ
b
∈
Ω
)
{
∥
Δ
C
,
Δ
b
∥
F
}
.So Ω
≠
ϕ (as Δ
C
=
0 is a BCSCB matrix, Δ
b
=
C
^
x
^
-
b). Hence, (43)
ξ
2
x
^
=
inf
⁡
Δ
C
,
Δ
b
∈
Ω
Δ
C
F
2
+
Δ
C
x
^
+
C
x
^
-
b
F
2
.Since (44)
Δ
C
F
2
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
2
,
Δ
C
=
Q
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
Π
0
k
-
1
⊗
Ψ
0
l
-
1
Q
T
,the question will be analysed in two different conditions.(1) Whenn is even, (45)
Δ
C
x
^
+
C
x
^
-
b
F
2
=
Q
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
1
Q
T
x
^
+
C
x
^
-
b
F
2
=
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
1
x
1
(
0
)
⋮
x
t
(
0
)
x
t
+
1
(
0
)
-
r
0
F
2
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
1
k
-
1
⊗
Ψ
0
l
-
1
x
1
(
0
)
⋮
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
t
k
-
1
⊗
Ψ
0
l
-
1
x
t
(
0
)
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
diag
-
Ψ
0
l
-
1
,
Ψ
0
l
-
1
x
t
+
1
(
0
)
-
r
0
F
2
,
=
Φ
ε
c
11
,
…
,
ε
c
1
m
,
…
,
ε
c
n
1
,
…
,
ε
c
n
m
T
-
r
0
F
2
,where (46)
r
0
=
Q
T
b
-
C
x
^
,
Q
T
x
^
=
x
1
(
0
)
⋯
x
t
(
0
)
x
t
+
1
(
0
)
T
,
Φ
=
Φ
1
,
Φ
2
,
…
,
Φ
n
-
1
,
∑
l
=
1
m
‍
diag
-
Ψ
0
l
-
1
,
Ψ
0
l
-
1
x
t
+
1
0
,
Φ
k
=
ϕ
1
,
k
,
1
⋯
ϕ
1
,
k
,
m
⋮
⋱
⋮
ϕ
t
,
k
,
1
⋯
ϕ
t
,
k
,
m
,
ϕ
p
,
k
,
l
=
π
p
k
-
1
⊗
Ψ
0
l
-
1
x
p
(
0
)
,
t
=
n
2
-
1
,
p
=
1,2
,
…
,
t
,
k
=
1,2
,
…
,
n
-
1
,
l
=
1,2
,
…
,
m
.(2) Whenn is odd, (47)
Δ
C
x
^
+
C
x
^
-
b
F
2
=
Q
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
2
Q
T
x
^
+
C
x
^
-
b
F
2
=
ε
Λ
11
⋱
ε
Λ
t
t
ε
Υ
2
x
1
(
0
)
⋮
x
t
(
0
)
x
t
+
1
(
0
)
-
r
0
F
2
=
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
1
k
-
1
⊗
Ψ
0
l
-
1
x
1
(
0
)
⋮
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
π
t
k
-
1
⊗
Ψ
0
l
-
1
x
t
(
0
)
∑
k
=
1
n
‍
∑
l
=
1
n
‍
ε
c
k
l
Ψ
0
l
-
1
x
t
+
1
(
0
)
-
r
0
F
2
=
Φ
ε
c
11
,
…
,
ε
c
1
m
,
…
,
ε
c
n
1
,
…
,
ε
c
n
m
T
-
r
0
F
2
,where (48)
r
0
=
Q
T
b
-
C
x
^
,
Q
T
x
^
=
x
1
(
0
)
⋯
x
t
(
0
)
x
t
+
1
(
0
)
T
,
Φ
=
Φ
1
,
Φ
2
,
…
,
Φ
n
-
1
,
∑
l
=
1
m
‍
Ψ
0
l
-
1
x
t
+
1
0
,
Φ
k
=
ϕ
1
,
k
,
1
⋯
ϕ
1
,
k
,
m
⋮
⋱
⋮
ϕ
t
,
k
,
1
⋯
ϕ
t
,
k
,
m
,
ϕ
p
,
k
,
l
=
π
p
k
-
1
⊗
Ψ
0
l
-
1
x
p
(
0
)
,
t
=
n
-
1
2
,
p
=
1,2
,
…
,
t
,
k
=
1,2
,
…
,
n
-
1
,
l
=
1,2
,
…
,
m
.Let(49)
g
ε
c
11
,
…
,
ε
c
n
m
=
m
n
∑
k
=
1
n
‍
∑
l
=
1
m
‍
ε
c
k
l
2
+
Φ
ε
c
11
⋮
ε
c
n
m
-
r
0
F
2
,and then (50)
∂
g
∂
ε
c
k
l
=
0
,which is equal to (51)
2
m
n
I
m
n
+
2
Φ
T
Φ
ε
c
11
⋮
ε
c
n
m
-
2
Φ
T
r
0
=
0
,
∂
2
g
∂
(
ε
c
k
l
)
2
=
2
m
n
I
m
n
+
2
Φ
T
Φ
>
0
.As g is a convex function of (
ε
c
11
,
…
,
ε
c
n
m
), the point of the minimal value is (52)
ε
c
11
⋮
ε
c
n
m
=
m
n
I
m
n
+
Φ
T
Φ
-
1
Φ
T
r
0
.Substituting it back into (49), we obtain the following.Theorem 6.
Consider(53)
ξ
2
x
=
m
n
r
0
T
Φ
m
n
I
m
n
+
Φ
T
Φ
-
2
Φ
T
r
0
=
Φ
m
n
I
m
n
+
Φ
T
Φ
-
1
Φ
T
-
I
m
n
r
0
F
2
.LetΦ
=
U
Σ
V
* be the singular value decomposition of Φ, where U and V are unitary matrices, Σ
=
diag
(
σ
1
′
,
…
,
σ
n
m
′
), and σ
j
′
≥
0
(
j
=
1,2
,
…
,
n
m
); then (54)
ξ
2
x
=
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
α
1
⋱
α
m
n
r
1
,where r
1
=
U
T
r
0, α
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.
Asσ
j
2
≤
Φ
F
2
=
m
n
∥
x
^
∥
2
2, then 1
+
x
^
2
2
≥
1
+
σ
j
′
2
/
m
n can be obtained; hence, m
n
/
(
m
n
+
σ
j
′
2
)
≥
1
/
(
1
+
x
^
2
2
).From what we analysed above, the following algorithm can be obtained.Algorithm 8.
We have the following steps.
Step 1. Form the style spectral decomposition of the matrixes Π and Ψ:(55)
Π
=
Q
Π
0
Q
T
,
Ψ
=
J
Ψ
0
J
T
.
Step 2. Form the block style spectral decomposition of the BCSCB matrix.
Step 3. Compute r
=
b
-
C
x
^.
Step 4. Compute r
0
=
Q
T
r.
Step 5. Compute (56)
Q
T
x
^
=
x
1
(
0
)
⋮
x
t
(
0
)
x
t
+
1
(
0
)
.
Step 6. Form Φ.
Step 7. Compute the singular value decomposition of Φ.
Step 8. Compute ξ
2
(
x
^
).


## 4. Numerical Example

In this section, a simple numerical example is given to verify the conclusion above. Suppose thatn
=
2, m
=
3 in the following example.If the coefficient matrix of the BCSCB linear system isC
=
BCSCB
(
3,5
,
2,7
,
9,8
) and the constant vector b
=
(
11,8
,
10
,
-
8,9
,
3
)
T, now, three perturbations are given as follows: (57)
Δ
C
1
=
0.01
BCSCB
3,5
,
2,7
,
9,8
,
Δ
b
1
=
0.01
1,3
,
2,3
,
1,5
T
,
Δ
C
2
=
BCSCB
0.01,0.02,0
,
0.015,0.033,0.01
,
Δ
b
2
=
0.012,0.03,0.02,0.015,0.01,0.021
T
,
Δ
C
3
=
BCSCB
0.01,0.02,0.015,0.01,0
,
0.01
,
Δ
b
3
=
0.012,0.035,0.02,0.01,0.021,0.015
T
.From the equation C
^
x
^
=
b
^, where C
^, b
^ are defined as above, the approximate solution of C
x
=
b can be obtained as follows:(58)
x
=
-
1.0556
0.3472
-
0.9306
0.4444
-
0.1528
1.5694
,
x
^
1
=
-
1.0556
0.3472
-
0.9306
0.4444
-
0.1528
1.5694
,
x
^
2
=
-
1.0553
0.3472
-
0.9303
0.4444
-
0.1528
1.5694
,
x
^
3
=
-
1.0531
0.3439
-
0.9297
0.4418
-
0.1492
1.5699
,where x is the solution of C
x
=
b and x
^
i, i
=
1,2
,
3, is the solution of (
C
+
Δ
C
i
)
x
=
b
+
Δ
b
i, i
=
1,2
,
3, respectively.Based on Algorithm8, we obtain Table 1, where ϵ is the relative error of the BCSCB linear system, κ
=
max
⁡
{
σ
i
j
}
/
min
⁡
{
σ
i
j
} is the condition number, ξ
1
(
x
^
)
=
b
-
C
x
^
2
/
1
+
x
^
2
2, and ξ
2
(
x
^
) can be obtained from the algorithm.Table 1
The related date of the algorithm.
ϵ
κ
ξ
1
(
x
^
)
ξ
2
(
x
^
)
Case  0
0
4.0000
0
0
Case  1
0
4.0000
2.2112
e
-
15
0.3796
Case  2
1.9396
e
-
4
4.0024
0.0028
0.1170
Case  3
0.0028
3.9971
0.0202
0.0899From the numerical example, the accuracy of the conclusion and the effectiveness of the algorithm are verified.


## 5. Conclusion

In this paper, we consider the problems associated with the BCSCB matrix. The BCSCB matrix is an extension of the circulant matrix and skew circulant matrix. We give the form of the BCSCB matrix and obtain its block style spectral decomposition. The algorithm of the optimal backward perturbation is given. Furthermore, by circulant matrices technology, we will develop solving problems in [15–17].



---

*Source: 471362-2015-03-22.xml*