Perturbation and error analyses of partitioned LU factorization for block tridiagonal linear systems
The perturbation and backward error analyses of the partitioned LU factorization for block tridiagonal matrices are presented. Moreover, we consider the perturbation bounds for the partitioned LU factorization for block tridiagonal linear systems. Finally, numerical examples are given to verify our...
Saved in:
| Date: | 2016 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematics, NAS of Ukraine
2016
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/1953 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860507852521603072 |
|---|---|
| author | Huang, Ting-Zhu Wu, Chi-Yе Хуан, Тінг-Жу Ву, Чи-Йе |
| author_facet | Huang, Ting-Zhu Wu, Chi-Yе Хуан, Тінг-Жу Ву, Чи-Йе |
| author_sort | Huang, Ting-Zhu |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T09:32:42Z |
| description | The perturbation and backward error analyses of the partitioned LU factorization for block tridiagonal matrices are
presented. Moreover, we consider the perturbation bounds for the partitioned LU factorization for block tridiagonal linear
systems. Finally, numerical examples are given to verify our results. |
| first_indexed | 2026-03-24T02:15:54Z |
| format | Article |
| fulltext |
UDC 519.62
Chi-Ye Wu (Jinan Univ. and School Math. Sci., Univ. Electron. Sci. and Technology, China),
Ting-Zhu Huang (School Math. Sci., Univ. Electron. Sci. and Technology, China)
PERTURBATION AND ERROR ANALYSES
OF PARTITIONED \bfitL \bfitU FACTORIZATION
FOR BLOCK TRIDIAGONAL LINEAR SYSTEMS*
АНАЛIЗ ЗБУРЕНЬ ТА ПОХИБОК РОЗБИТОЇ НА ЧАСТИНИ \bfitL \bfitU
ФАКТОРИЗАЦIЇ ДЛЯ БЛОЧНО-ТРИДIАГОНАЛЬНИХ ЛIНIЙНИХ СИСТЕМ
The perturbation and backward error analyses of the partitioned LU factorization for block tridiagonal matrices are
presented. Moreover, we consider the perturbation bounds for the partitioned LU factorization for block tridiagonal linear
systems. Finally, numerical examples are given to verify our results.
Наведено аналiз збурень та зворотний аналiз похибок для розбитої на частини LU факторизацiї блочно-тридi-
агональних матриць. Крiм того, вивчаються границi збурень для розбитої на частини LU факторизацiї блочно-
тридiагональних лiнiйних систем. Також наведено числoвi експерименти, якi пiдтверджують справедливiсть даних
результатiв.
1. Introduction. We consider the linear system Ax = b when A is a nonsingular block tridiagonal
matrix as follows:
A =
\left(
A1 C1
B2 A2 C2
. . . . . . . . .
. . . . . . Cs - 1
Bs As
\right) , (1.1)
where Ai \in \BbbR ki\times ki , Bi \in \BbbR ki\times ki - 1 , and Ci \in \BbbR ki\times ki+1 for all 1 \leq i \leq s.
For a nonsingular block tridiagonal matrix as above, our interest is to solve the linear system
Ax = b efficiently and accurately. Applying partitioned LU factorization for a general matrix, the
representation of partitioned LU factorization for nonsingular block tridiagonal matrices is as follows:
A =
\left(
L11
B2U
- 1
11 I2
. . .
Is
\right)
\biggl(
I1
S1
\biggr) \left(
U11 L - 1
11 C1
I2
. . .
Is
\right) = L1D1U1,
where
S1 =
\left(
A2 - B2U
- 1
11 L - 1
11 C1 C2
B3 A3 C3
. . . . . . . . .
. . . . . . Cs - 1
Bs As
\right) .
* This research was supported by NSFC (No. 11301223), GDNSF (No. S2012040007333), financial engineering and
algorithm research center of Jinan University, high level university construction and overall planning project of Jinan
University (Shenzhen Tourism College) (No. 88015201) and teaching reform research project of Jinan University
(No. 55610196).
c\bigcirc CHI-YE WU, TING-ZHU HUANG, 2016
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12 1683
1684 CHI-YE WU, TING-ZHU HUANG
If A2 - B2U
- 1
11 L - 1
11 can be factorized as follows:
A2 - B2U
- 1
11 L - 1
11 = L22U22,
then D1 satisfies
D1 = L2D2U2 =
\left(
I1
L22
B3U
- 1
22 I3
. . .
Is
\right) \times
\times
\left( I1
I2
S2
\right)
\left(
I1
U22 L - 1
11 C2
I3
. . .
Is
\right) ,
where the form of S2 is similar to that of S1 so that we here ignore it. For a given i, if the first
block of Si can be factorized, then the partitioned LU factorization can run to the (i + 1)st step.
Otherwise, the factorization must break down in the ith step. Suppose that the factorization can run
to completion. Then we have
A = L1 . . . Ls - 1LsUsUs - 1 . . . U1,
where
Ds - 1 = LsUs.
Note that there are different form and content between the partitioned LU factorization and the general
block LU factorization, because every step in process the former is more one LU factorization than
the latter, and the factors both Li and Ui of the former are triangular forms which are not satisfied
for the latter.
In the literature there are lots of papers dealing with the perturbation bounds for usual, or
pointwise, LU, Cholesky or QR factorizations. References relevant to this problem include Barrlund
[1], Stewart [2 – 4], Chang and Paige [5], and Dopico and Molera [6], etc. First-order perturbation
bounds are frequently used, such as Chang, Paige and Stewart [7], and Stewart [2, 3]. Dopico
and Molera [6] presented expressions for the terms of any order in the series expressions of the
perturbed LU and Cholesky factors. When the above factorization for the original matrix A in (1.1)
runs to completion, the question is whether the perturbed matrix A + E exists the partitioned LU
factorization. If E satisfies
| E| \leq \epsilon | A| ,
where \epsilon is small sufficiently and | A| stands for a matrix of absolute values of entries of A, then
the partitioned LU factorization for the perturbed matrix A + E exists. The relations between
S
(k)
ij (A+E), D
(k)
ij (A+E) and S
(k)
ij (A), D
(k)
ij (A), respectively, are considered, where S
(k)
ij (A) and
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
PERTURBATION AND ERROR ANALYSES OF PARTITIONED LU FACTORIZATION . . . 1685
D
(k)
ij (A) stand for block (i, j) of Sk and Dk, respectively. Moreover, perturbation bounds for the
factors are also proposed.
The error analysis is one of the most powerful tools for studying the accuracy and stability
of numerical algorithms. References relevant to this problem include Higham [8 – 10], Amodio and
Mazzia [11], Demmel, Higham, and Shreiber [12], Zhao, Wang, and Ren [13], Mattheij [14], Forsgren,
Gill, and Shinnerl [15], and Bueno and Dopico [16], etc. In this paper, applying the special property
that the factors Li and Ui are triangular forms, then some assumptions on the BLAS3 that can not be
applied in the error analysis of general block LU factorization can be used in that of the partitioned
LU factorization. Hence, error analysis of the partitioned LU factorization for block tridiagonal
linear systems can be considered. Comparing the results of Higham [8], Demmel and Higham [17]
with those of this paper, the distinction between the former and the latter is conspicuous. Based on
the assumptions, the latter conditions are weaker than those of the former. Finally, two numerical
examples are considered to illustrate our theory results, where the mentioned matrices generated from
the discretization of partial differential equation - \Delta u = f and random block tridiagonal matrices by
MATLAB 6.5, respectively.
2. Perturbation theory. In this section our interest is to present perturbation analysis of the
factors of the partitioned LU factorization.
2.1. Some properties. We first consider the relation between the first block of Sk(A + E) and
that of Sk(A).
Theorem 2.1. Let the partitioned LU factorization for the block tridiagonal matrix A in (1.1)
run to completion. Assume that \epsilon is small enough that | E| \leq \epsilon | A| . Then
S
(k)
11 (A+ E) = S
(k)
11 (A) + Tk +O(\epsilon 2),
where Tk, 1 \leq k \leq s, satisfy
T1 = E11, Tk =
\biggl(
Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
Ik
\biggr) \Biggl( - Tk - 1 - Ek - 1,k
- Ek,k - 1 Ek,k
\Biggr) \left( \Bigl( S(k - 1)
11
\Bigr) - 1
Ck
Ik
\right) .
Proof. To save clutter we will omit “+O(\epsilon 2)”. The proof is essentially inductive. For k = 1, we
have
S
(1)
11 (A+ E) = (A2 + E22) - (B2 + E21)U
- 1
11 (A+ E)L - 1
11 (A+ E)(C1 + E12).
Since A - 1 = U - 1L - 1 and | E| \leq \epsilon | A| . Then
S
(1)
11 (A+ E) = (A2 + E22) - (B2 + E21)(A
- 1
1 +A - 1
1 E11A
- 1
1 )(C1 + E12) =
= A2 - B2A
- 1
1 C1 + E22 - E21A
- 1
1 C1 - B2A
- 1
1 E11A
- 1
1 C1 - B2A
- 1
1 E12 =
= S
(1)
11 (A) +
\bigl(
B2A
- 1
1 I2
\bigr) \Biggl( - E11 - E12
- E21 E22
\Biggr) \Biggl(
A - 1
1 C1
I2
\Biggr)
.
For k = i - 1, by the assumption, it follows that
S
(i - 1)
11 (A+ E) = S
(i - 1)
11 (A) + Ti,
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
1686 CHI-YE WU, TING-ZHU HUANG
where, from the structure of Ti, we obtain Ti = O(\epsilon ). For k = i, we get
S
(i)
11 (A+ E) = (Ai+1 + Ei+1,i+1) - (Bi+1 + Ei+1,i)
\Bigl(
S
(i - 1)
11 + Ti
\Bigr) - 1
(Ci + Ei,i+1) =
= Ai+1 - Bi+1U
- 1
ii Ci + Ei+1,i+1 - Ei+1,i
\Bigl(
S
(i - 1)
11
\Bigr) - 1
Ci - Bi+1
\Bigl(
S
(i - 1)
11
\Bigr) - 1
Ti
\Bigl(
S
(i - 1)
11
\Bigr) - 1
Ci =
= S
(i)
11 (A) +
\Bigl(
Bi+1
\Bigl(
S
(i - 1)
11
\Bigr) - 1
Ii+1
\Bigr) \biggl( - Ti - Ei,i+1
- Ei+1,i Ei+1,i+1
\biggr) \Biggl( \Bigl(
S
(i - 1)
11
\Bigr) - 1
Ci
Ii+1
\Biggr)
.
Theorem 2.1 is proved.
From the result as above, we have the following theorem.
Theorem 2.2. Let the partitioned LU factorization for the block tridiagonal matrix A in (1.1)
run to completion. Assume that \epsilon is small enough that | E| \leq \epsilon | A| . Then
S
(k)
ij (A+ E) = S
(k)
ij (A) + \alpha ij(Tk +O(\epsilon 2)) + (1 - \alpha ij)Eij ,
D
(k)
ij (A+ E) = D
(k)
ij (A) + \beta i(\alpha ij(Tk +O(\epsilon 2)) + (1 - \alpha ij)Eij),
where
\beta i =
\left\{ 1, k \leq i \leq s - 1,
0, 1 \leq i < k,
\alpha ij =
\left\{ 1, i = j = 1,
0, others.
Proof. By the partitioned LU factorization, we have
S
(k)
ij (A+ E) = S
(k)
ij (A) + Eij , i, j \not = 1. (2.1)
Combining (2.1) with Theorem 2.1 gives
S
(k)
ij (A+ E) = S
(k)
ij (A) + \alpha ij(Tk +O(\epsilon 2)) + (1 - \alpha ij)Eij , (2.2)
where
\alpha ij =
\left\{ 1, i = j = 1,
0, others.
By the form of Dk, it follows that
D
(k)
ij (A+ E) = D
(k)
ij (A), 1 \leq i < k. (2.3)
From (2.2), we have
D
(k)
ij (A+ E) = D
(k)
ij (A) + \alpha ij(Tk +O(\epsilon 2)) + (1 - \alpha ij)Eij , k \leq i \leq s - 1. (2.4)
For (2.3) and (2.4), it follows that
D
(k)
ij (A+ E) = D
(k)
ij (A) + \beta i
\bigl(
\alpha ij(Tk +O(\epsilon 2)) + (1 - \alpha ij)Eij
\bigr)
,
where
\beta i =
\left\{ 1, k \leq i \leq s - 1,
0, 1 \leq i < k.
Theorem 2.2 is proved.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
PERTURBATION AND ERROR ANALYSES OF PARTITIONED LU FACTORIZATION . . . 1687
Corollary 2.1. Let the partitioned LU factorization for the block tridiagonal matrix A in (1.1)
run to completion. Assume that \epsilon is small enough that | E| \leq \epsilon | A| . Then
S
(k)
ij (A+ E) = S
(k)
ij (A) +O(\epsilon ), D
(k)
ij (A+ E) = D
(k)
ij (A) +O(\epsilon ).
Proof. From the proof of Theorem 2.1 and the form of Tk, it follows that Tk = O(\epsilon ), then
Tk + Eij +O(\epsilon 2) = O(\epsilon ). Therefore
S
(k)
ij (A+ E) = S
(k)
ij (A) +O(\epsilon ), D
(k)
ij (A+ E) = D
(k)
ij (A) +O(\epsilon ).
From | E| \leq \epsilon | A| , if \epsilon is sufficiently small, then the spectral radius \rho (L - 1EU - 1) < 1 holds.
Therefore it has a unique block LU factorization (see Theorem 12.1 in [8] for details). In this case
the question is whether the matrices S
(k)
11 , 1 \leq k \leq s - 1, exist the LU factorization, that is, whether
the perturbed matrix A+E exists the partitioned LU factorization. By Theorem 2.1, it follows that
S
(k)
11 (A+ E) = S
(k)
11 (A) + Tk +O(\epsilon 2).
For the assumption of Theorem 2.1, we have
S
(k)
11 (A+ E) = Lk+1,k+1Uk+1,k+1 + Tk +O(\epsilon 2) =
= Lk+1,k+1
\Bigl(
Ik+1 + L - 1
k+1,k+1(Tk +O(\epsilon 2))U - 1
k+1,k+1
\Bigr)
Uk+1,k+1.
Since
Tk +O(\epsilon 2) = O(\epsilon ), \rho
\bigl(
L - 1EU - 1
\bigr)
< 1.
Then
\rho
\Bigl(
L - 1
k+1,k+1(Tk +O(\epsilon 2))U - 1
k+1,k+1
\Bigr)
< 1,
that is, Ik+1 + L - 1
k+1,k+1(Tk + O(\epsilon 2))U - 1
k+1,k+1 exists the LU factorization. Thus S
(k)
11 (A + E)
(1 \leq k \leq s - 1) have the LU factorization. Hence the perturbed matrix A+E exists the partitioned
LU factorization. Based on the above mentioned, we have the following theorem.
Theorem 2.3. Let the partitioned LU factorization for the block tridiagonal matrix A in (1.1)
run to completion. Assume that \epsilon is small enough that | E| \leq \epsilon | A| . Then the perturbed matrix A+E
has the partitioned LU factorization.
2.2. Perturbation bounds for the factors. In this subsection we present the bounds for the
factors. First of all, we consider the bound for S
(k)
ij . Obviously, we are easy to get the following
componentwise perturbation bound for S(1)
11 by applying Theorem 2.1:\bigm| \bigm| \bigm| S(1)
11 (A+ E) - S
(1)
11 (A)
\bigm| \bigm| \bigm| \leq \epsilon | A1| .
Unless otherwise stated, let in this section an unsubscripted norm \| .\| be an arbitrary subordinate and
monotone matrix norm. For S(k)
11 , we have the following theorem.
Theorem 2.4. Let the partitioned LU factorization for the block tridiagonal matrix A in (1.1)
run to completion, and let
\chi = \mathrm{m}\mathrm{a}\mathrm{x}
k
\biggl\{ \bigm\| \bigm\| \bigm\| \bigm\| \Bigl( S(k - 1)
11
\Bigr) - 1
Ck
\bigm\| \bigm\| \bigm\| \bigm\| \| Ak,k - 1\| +
\bigm\| \bigm\| \bigm\| \bigm\| Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
\bigm\| \bigm\| \bigm\| \bigm\| \| Ak - 1,k\| + \| Akk\|
\biggr\}
,
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
1688 CHI-YE WU, TING-ZHU HUANG
\omega = \mathrm{m}\mathrm{a}\mathrm{x}
k
\biggl\{ \bigm\| \bigm\| \bigm\| \bigm\| Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
\bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \Bigl( S(k - 1)
11
\Bigr) - 1
Ck
\bigm\| \bigm\| \bigm\| \bigm\| \biggr\}
with \bigm\| \bigm\| \bigm\| \bigm\| Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
\bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \Bigl( S(k - 1)
11
\Bigr) - 1
Ck
\bigm\| \bigm\| \bigm\| \bigm\| \not = 1.
Assume that \epsilon is small enough that | E| \leq \epsilon | A| . Then\bigm\| \bigm\| \bigm\| S(k)
11 (A+ E) - S
(k)
11 (A)
\bigm\| \bigm\| \bigm\| \leq \omega k - 1
\biggl(
\| A1\| +
\chi (\omega k - 1 - 1)
\omega k - 1(\omega - 1)
\biggr)
\epsilon +O(\epsilon 2).
Proof. We first consider the bound for Tk. From Theorem 2.1 it follows that
Tk =
\biggl(
Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
Ik
\biggr) \Biggl( - Tk - 1 - Ek - 1,k
- Ek,k - 1 Ek,k
\Biggr) \left( \Bigl( S(k - 1)
11
\Bigr) - 1
Ck
Ik
\right) =
= - Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
Tk - 1
\Bigl(
S
(k - 1)
11
\Bigr) - 1
Ck - Ek,k - 1
\Bigl(
S
(k - 1)
11
\Bigr) - 1
Ck -
- Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
Ek - 1,k + Ek,k.
Taking the monotone norm on both sides yields
\| Tk\| \leq
\bigm\| \bigm\| \bigm\| \bigm\| Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
\bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \bigm\| \Bigl( S(k - 1)
11
\Bigr) - 1
Ck
\bigm\| \bigm\| \bigm\| \bigm\| \| Tk - 1\| + \epsilon
\bigm\| \bigm\| \bigm\| \bigm\| \Bigl( S(k - 1)
11
\Bigr) - 1
Ck
\bigm\| \bigm\| \bigm\| \bigm\| \| Ak,k - 1\| +
+\epsilon
\bigm\| \bigm\| \bigm\| \bigm\| Bk
\Bigl(
S
(k - 1)
11
\Bigr) - 1
\bigm\| \bigm\| \bigm\| \bigm\| \| Ak - 1,k\| + \epsilon \| Akk\| .
Rearranging the above inequality, we have
\| Tk\| +
\chi \epsilon
\omega - 1
\leq \omega
\biggl(
\| Tk - 1\| +
\chi \epsilon
\omega - 1
\biggr)
\leq
\leq \omega k - 1
\biggl(
\| T1\| +
\chi \epsilon
\omega - 1
\biggr)
\leq
\leq \omega k - 1
\biggl(
\| A1\| +
\chi
\omega - 1
\biggr)
\epsilon .
Then
\| Tk\| \leq \omega k - 1
\biggl(
\| A1\| +
\chi (\omega k - 1 - 1)
\omega k - 1(\omega - 1)
\biggr)
\epsilon .
Theorem 2.4 is proved.
From Theorems 2.2 and 2.4, it is easy to propose the perturbation bounds for Sk
ij(A) and Dk
ij(A),
i.e., \bigm\| \bigm\| \bigm\| S(k)
ij (A+ E) - S
(k)
ij (A)
\bigm\| \bigm\| \bigm\| \leq \omega k - 1
\biggl(
\| A1\| +
\chi (\omega k - 1 - 1)
\omega k - 1(\omega - 1)
\biggr)
\epsilon + 2\| Aij\| \epsilon +O(\epsilon 2),
\bigm\| \bigm\| \bigm\| D(k)
ij (A+ E) - D
(k)
ij (A)
\bigm\| \bigm\| \bigm\| \leq \omega k - 1
\biggl(
\| A1\| +
\chi (\omega k - 1 - 1)
\omega k - 1(\omega - 1)
\biggr)
\epsilon + 2\| Aij\| \epsilon +O(\epsilon 2).
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
PERTURBATION AND ERROR ANALYSES OF PARTITIONED LU FACTORIZATION . . . 1689
3. Error analysis. Throughout, we use the conventional error model of floating-point arithmetic
in which the evaluation of an expression in floating-point arithmetic is denoted by fl(\cdot ), with
fl(a o b) = (a o b)(1 + \delta ), | \delta | \leq u, o = +, - , \ast , /
(see, for example, [8]). Here u is the unit roundoff of the machine being employed.
Unless otherwise mentioned, in this section an unsubscripted norm denotes
\| A\| := maxi,j | aij | .
Note that for this norm, the best inequality is
\| AB\| \leq n\| A\| \| B\| ,
where A \in \BbbR m\times n and B \in \BbbR n\times p. It is well known that this norm is not consistent, but for sparse
matrices it is simple and proper choice.
Based on fast matrix multiplication techniques, the use of BLAS3 affects the stability only insofar
as it increases the constant terms in the normwise backward error bounds (see [17] for details). We
have the following assumptions about the underlying level-3 BLAS.
(a) The computed approximation \^C to C = AB, where A \in \BbbR m\times n and B \in \BbbR n\times p, satisfies
\^C = AB +\Delta C, \| \Delta C\| \leq c1(m,n, p)u\| A\| \| B\| +O(u2),
where c1(m,n, p) denotes a constant depending on m, n, and p.
(b) If T \in \BbbR m\times m and B \in \BbbR m\times p, then computed solution \^X to the triangular systems TX = B
satisfies
T \^X = B +\Delta B, \| \Delta B\| \leq c2(m, p)u\| T\| \| \^X\| +O(u2),
where c2(m, p) denotes a constant depending on m and p.
Assumption (b) on the BLAS3 can not be applied in the error analysis of general block LU
factorization because the factor U is not triangular form. In view of this consideration, the partitioned
LU for block tridiagonal matrices is presented because the factors L and U are triangular form, i.e.,
errors incurred at the process of the partitioned LU factorization and substitution can be presented
by applying assumption (b). We first recall error analyses of the partitioned LU factorization for a
general partitioned matrix A \in \BbbR n\times nand of the corresponding computed solution to Ax = b.
Lemma 3.1 [17]. Under assumptions (a), (b) and
\^L11
\^U11 = A1 +\Delta A1, \| \Delta A1\| \leq c3(k1)u\| \^L11\| \| \^U11\| +O(u2),
the LU factors of A \in \BbbR n\times n computed using the partitioned outer product form of LU factorization
with block size k1 satisfy \^L \^U = A+\Delta A, where
\| \Delta A\| \leq u
\Bigl(
\delta (n, k1)\| A\| + \theta (n, k1)\| \^L\| \| \^U\|
\Bigr)
+O(u2),
and where
\delta (n, k1) = 1 + \delta (n - k1, k1), \delta (k1, k1) = 0,
\theta (n, k1) = \mathrm{m}\mathrm{a}\mathrm{x} \{ c3(k1), c2(k1, n - k1), 1 + c1(n - k1, k1, n - k1)+
+\delta (n - k1, k1) + \theta (n - k1, k1)\} , \theta (k1, k1) = 0.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
1690 CHI-YE WU, TING-ZHU HUANG
The following lemma is Problem 12.6 in [8].
Lemma 3.2 [8]. Under the conditions of Lemma 3.1 the computed solution to Ax = b satisfies
(A+ \delta A)\^x = b, \| \delta A\| \leq cnu(\| A\| + \| \^L\| \| \^U\| ) +O(u2),
where cn is a constant depending on n and the block size.
The corresponding error analyses of block tridiagonal matrix A in (1.1) and its linear systems are
presented as follows.
Theorem 3.1. Let the partitioned LU factorization for the block tridiagonal matrix A in (1.1)
run to completion. Then, under assumptions (a) and (b),
A+\Delta A = \^L \^U, \| \Delta A\| \leq (\xi ij\| A\| + \zeta ij\| L\| \| U\| )u+O(u2),
where
\xi ij =
\left\{
0, i = j = 1,
1, i = j \not = 1,
c2(ki, ki)ki\kappa (Lii), i = j - 1,
c2(ki, ki)ki\kappa (Uii), i = j + 1,
\zeta ij =
\left\{
c2(k1, k1), i = j = 1,
ci, i = j \not = 1,
0, others,
ci = \mathrm{m}\mathrm{a}\mathrm{x} \{ 1 + c1(ki - 1, ki - 1, ki), c2(ki, ki)\} .
Proof. To save clutter we will omit “+O(u2)”. By the assumption (b), we have
\^\^U - 1
ii
\^Uii = Ii +\Delta Ii, \| \Delta Ii\| \leq c2(ki, ki)u\| \^\^U - 1
ii \| \| \^Uii\| , (3.1)
where \^\^U - 1
ii is the computed quantities for inverting \^Uii. Thus,
\^\^U - 1
ii = (Ii +\Delta Ii) \^U
- 1
ii .
Then
\| \^\^U - 1
ii \| \leq \| \^U - 1
ii \| +O(u).
By representation (3.1), it follows that
\| \Delta Ii\| \leq c2(ki, ki)u\| \^U - 1
ii \| \| \^Uii\| ,
Similarly, we get
\^\^U - 1
ii
\^Uii = Ii +\Delta Ii, \| \Delta Ii\| \leq c2(ki, ki)u\| U - 1
ii \| \| Uii\| = c2(ki, ki)\kappa (Uii)u. (3.2)
A similar assertion holds for the following case:
\^Lii
\^\^L - 1
ii = Ii +\Delta Ii, \| \Delta Ii\| \leq c2(ki, ki)u\| Lii\| \| L - 1
ii \| = c2(ki, ki)\kappa (Lii)u. (3.3)
By the process of partitioned factorization gives
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
PERTURBATION AND ERROR ANALYSES OF PARTITIONED LU FACTORIZATION . . . 1691
B2
\^\^U - 1
11
\^U11 = B2 +\Delta B2,
\^L11
\^\^L - 1
11 C1 = C1 +\Delta C1.
(3.4)
From representations (2.2) – (2.4), we obtain
\| \Delta B2\| \leq c2(k1, k1)k1\kappa (U11)\| B22\| u,
\| \Delta C1\| \leq c2(k1, k1)k1\kappa (L11)\| C1\| u.
By assumption (b), we can get the bound for \Delta Ai as follows:
\| \Delta A1\| \leq c2(k1, k1)u\| L11\| \| U11\| .
For \Delta B3, \Delta A2 and \Delta C2, because of some errors incurred at the process of multiplication and
subtraction of the matrices and the LU factorization for A2 - B
\^\^U - 1
11
\^\^L - 1C1, they are different from
\Delta B2, \Delta A1 and \Delta C1, respectively. Let
L21U12 = B2U
- 1
11 L - 1
11 C1 = H.
Then the computed approximate \^H satisfies
B2
\^\^U - 1
11
\^\^L - 1
11 C1 +\Delta H = \^H, \| \Delta H\| \leq c1(k1, k1, k2)u\| B2U
- 1
11 \| \| L - 1
11 C1\| .
Let
A2 - H = G.
Then the computed approximate \^G to G satisfies
A2 - \^H +\Delta G\prime = \^G, \| \Delta G\prime \| \leq u(\| A2\| + \| \^H\| ).
That is,
A2 - B2
\^\^U - 1
11
\^\^L - 1
11 C1 +\Delta G = \^G,
\| \Delta G\| \leq u(\| A2\| + (1 + c1(k1, k1, k2))\| B2U
- 1
11 \| \| L - 1
11 C1\| ).
(3.5)
Applying the LU factorization for \^G gives
\^G+\Delta G\prime \prime = \^L22
\^U22, \| \Delta G\prime \prime \| \leq c2(k2, k2)u\| L22\| \| U22\| .
Combining (3.1) with (3.2), it follows that
A2 +\Delta A2 = \^L22
\^U22 +B2
\^\^U - 1
11
\^\^L - 1
11 C1,
\| \Delta A2\| \leq u(\| A2\| + (1 + c1(k1, k1, k2))\| B2U
- 1
11 \| \| L - 1
11 C1\| + c2(k2, k2)\| L22\| \| U22\| ).
From the factors \^L11, \^U11, \^L22 and \^U22 obtained in the process of the factorization, it is conspicuous
that \^L11 and \^U11 are different from \^L22 and \^U22, respectively. For the latter contain the errors
incurred at multiplication and subtraction beside the course of factorization. For \Delta Ai, 3 \leq i \leq s,
the similar results hold
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
1692 CHI-YE WU, TING-ZHU HUANG
\| \Delta Ai\| \leq u(\| Ai\| + (1 + c1(ki - 1, ki - 1, ki))\| BiU
- 1
i - 1,i - 1\| \times
\times \| L - 1
i - 1,i - 1Ci - 1\| + c2(ki, ki)\| Lii\| \| Uii\| ) \leq
\leq u(\| Ai\| + c(\| Li,i - 1\| \| Ui - 1,i - 1\| + \| Lii\| \| Uii\| )),
where ci = \mathrm{m}\mathrm{a}\mathrm{x} \{ 1 + c1(ki - 1, ki - 1, ki), c2(ki, ki)\} . For \Delta Bi+1 and \Delta Ci for all 2 \leq i \leq s - 1, we
have
\| \Delta Bi+1\| \leq c2(ki, ki)ki\kappa (Uii)\| Bi+1,i+1\| u,
\| \Delta Ci\| \leq c2(ki, ki)ki\kappa (Lii)\| Ci\| u.
Therefore
\| \Delta A\| \leq (\xi ij\| A\| + \zeta ij\| L\| \| U\| )u,
where
\xi ij =
\left\{
0, i = j = 1,
1, i = j \not = 1,
c2(ki, ki)ki\kappa (Lii), i = j - 1,
c2(ki, ki)ki\kappa (Uii), i = j + 1,
\zeta ij =
\left\{
c2(k1, k1), i = j = 1,
c, i = j \not = 1,
0, others.
Theorem 3.1 is proved.
Remark 3.1. Comparing Lemma 3.1 with Theorem 3.1, we know the following comments.
1) The assumption of Lemma 3.1
\^L11
\^U11 = A1 +\Delta A1, \| \Delta A1\| \leq c3(k1)u\| \^L11\| \| \^U11\| +O(u2),
is omitted in Theorem 3.1. Based on this point, the assumptions of the latter are weaker than those
of the former.
2) It is conspicuous that the proof of the latter is different from that of the former.
3) In the result of the former, the computed approximate \^L and \^U are applied, however, the exact
quantities L and U are used in that of the latter.
From Theorem 3.1, we have the following assertion on block tridiagonal linear systems. Note
that \Delta L and \Delta U are produced in solving Ly = b and Ux = y, respectively.
Theorem 3.2. Let A be as in (1.1), and suppose that the partitioned LU factorization computes
an approximate solution \^x to Ax = b, where \^x is the exact solution of the system (A + \delta A)\^x = b.
Then
\| \delta A\| \leq (\xi ij\| A\| + \delta ij\| L\| \| U\| )u+O(u2),
\| \^x - x\|
\| \^x\|
\leq n
\Bigl( \Bigl(
\xi ij\kappa (A) +
\gamma ns
u
\kappa (U)
\Bigr)
+
\Bigl(
\zeta ij +
n\gamma ns
u
\Bigr)
\| L\| \| U\| \| A - 1\|
\Bigr)
u+O(u2),
where \delta ij = \zeta ij + \gamma 2ns/u.
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
PERTURBATION AND ERROR ANALYSES OF PARTITIONED LU FACTORIZATION . . . 1693
Proof. By the assumption, it follows that
(\^L+\Delta L)( \^U +\Delta U)\^x = b.
Then
\delta A = \Delta A+\Delta L \^U + \^L\Delta U +\Delta L\Delta U. (3.6)
In the following proof we need the bounds for \Delta L and \Delta U. Applying the factorization and the result
of [18], it follows that
( \^U1 +\Delta U1)x = y(1), | \Delta U1| \leq
nu
1 - nu
| \^U1| .
For a given i, we have
( \^Ui +\Delta Ui)y
(i - 1) = y(i), | \Delta Ui| \leq
nu
1 - nu
| \^Ui| .
Thus,
( \^Us +\Delta Us) . . . ( \^U1 +\Delta U1)x = y,
| \Delta U | \leq nsu
1 - nu
| \^Us| . . . | \^U1| \leq \gamma ns| \^U | ,
where \gamma ns = nsu/(1 - nsu). By the definition of norm, we get
\| \Delta U\| \leq \gamma ns\| \^U\| . (3.7)
On the other hand, we obtain
(\^L1 +\Delta L1) . . . (\^Ls +\Delta Ls)y = b, \| \Delta L\| \leq \gamma ns\| \^L\| . (3.8)
Combining (3.6), (3.7) with (3.8), by Theorem 3.1, it follows that
\| \delta A\| \leq (\xi ij\| A\| + \zeta ij\| L\| \| U\| )u+ (2\gamma ns + \gamma 2ns)n\| \^L\| \| \^U\| \leq
\leq (\xi ij\| A\| + \delta ij\| L\| \| U\| )u,
where \delta ij = \zeta ij + \gamma 2nsn/u and 2\gamma ns + \gamma 2ns \leq \gamma 2ns [8, 9]. The following proof refers to the relative
error. By Higham [10], we have
\| \^x - x\| \leq \| A - 1(\Delta A+\Delta L \^U) + \^U - 1\Delta U\| \| \^x\| . (3.9)
Applying Theorem 3.1, from (3.7) and (3.8), it follows that
\| \^x - x\|
\| \^x\|
\leq n
\Bigl( \Bigl(
\xi ij\kappa (A) +
\gamma ns
u
\kappa (U)
\Bigr)
+
\Bigl(
\zeta ij +
n\gamma ns
u
\Bigr)
\| L\| \| U\| \| A - 1\|
\Bigr)
u.
Theorem 3.2 is proved.
Actually, for ki = 1, 1 \leq i \leq s, there exists a relationship between \kappa (U) and \kappa (A) and \| L\| \leq 1
holds when the partial pivoting strategy is applied during the factorization, then the relative error
mentioned above can be O(\kappa (A)u). On the other hand, the triangular form of the factors Li and Ui
of the partitioned LU factorization in this paper advantages the relative error \| \^x - x\| /\| \^x\| .
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
1694 CHI-YE WU, TING-ZHU HUANG
Remark 3.2. Comparing Lemma 3.2 with Theorem 3.2, we have the following comments besides
the first comment in Remark 3.1.
1. The coefficient cn of Lemma 3.2 is a faint constant, however, those of Theorem 3.2 are given
exactly.
2. In the latter the relative error of solution is also considered, however, the form is not referred
to.
4. Numerical experiments. In this section, applying MATLAB 6.5, we illustrate theory results
on backward error generated from the partitioned LU factorization for block tridiagonal matrices and
on the relative error of solution to linear systems.
Example 4.1. Let block tridiagonal matrices be generated from the discretization of partial
differential equation - \Delta u = f, where Ai = \mathrm{t}\mathrm{r}\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}( - 1, 4, - 1)ki\times ki . Some results corresponding to
the example are listed in Table 4.1.
Table 4.1
Size \| A - \^L \ast \^U\| \| x - \^x\| /\| \^x\|
900\times 900 1.7764e - 015 2.2204e - 015
1600\times 1600 2.6645e - 015 1.0880e - 014
3600\times 3600 3.5527e - 015 1.4655e - 014
Example 4.2. Let A be random block tridiagonal matrices, where Ai , Bi and Ci are random
matrices with approximately 0.8\times ki\times ki , 0.2\times ki\times ki - 1 and 0.2\times ki - 1\times ki uniformly distributed
nonzero entries, respectively. The results listed in Table 2.
Table 4.2
Size \| A - \^L \ast \^U\| \| x - \^x\| /\| \^x\|
900\times 900 5.6843e - 014 3.4195e - 013
1600\times 1600 1.2967e - 013 1.2765e - 012
3600\times 3600 8.1712e - 014 3.3598e - 012
From the results as above, it shows that the errors \| A - \^L \ast \^U\| and \| x - \^x\| /\| \^x\| are very small.
However, we can not say that the partitioned LU factorization must be stable, because the backward
error contains \| L\| . For example,
A =
\left(
\epsilon 0 1 0
0 \epsilon 0 1
1 0 \epsilon 0 1 0
0 1 0 \epsilon 0 1
1 0 1 0
0 1 0 1
\right)
,
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
PERTURBATION AND ERROR ANALYSES OF PARTITIONED LU FACTORIZATION . . . 1695
where \epsilon is sufficient small. Applying the partitioned LU factorization in this paper gives
L = L1L2L3 =
\left(
1
1
1
\epsilon
1
1
\epsilon
1
\epsilon
\epsilon 2 - 1
1
\epsilon
\epsilon 2 - 1
1
\right)
.
Hence, \| L\| is boundless when \epsilon is sufficient small.
References
1. Barrland A. Perturbation bounds for the LDLH and the LU factorizations // BIT. – 1991. – 31. – P. 358 – 363.
2. Stewart G. W. Perturbation bounds for the QR factorizaton of a matrix // SIAM J. Numer. Anal. – 1977. – 14. –
P. 509 – 518.
3. Stewart G. W. On the perturbation of LU, Cholesky, and QR factorizations // SIAM J. Numer. Anal. – 1993. – 14. –
P. 1141 – 1145.
4. Stewart G. W. On the perturbation of LU and Cholesky factors // SIAM J. Numer. Anal. – 1997. – 17. – P. 1 – 6.
5. Xiao-Wen Chang, Christopher C. Paige. On the sensitivity of the LU factorization // BIT. – 1998. – 38. – P. 486 – 501.
6. Dopico F. M., Molera J. M. Perturbation theory of factorizations of LUF type through series expansions // SIAM J.
Matrix Anal. and Appl. – 2005. – 27. – P. 561 – 581.
7. Xiao-Wen Chang, Christopher C. Paige, Stewart G. W. Perturbation analyses for the QR factorization // SIAM J.
Matrix Anal. and Appl. – 1997. – 18. – P. 775 – 791.
8. Higham N. J. Accuracy and stability of numerical algorithm. – Philadelphia: SIAM, 1996.
9. Higham N. J. Accuracy and stability of algorithms in numerical linear algebra // Manchester Center Comput. Math.
Numer. Anal. Rept. – 1998. – № 333.
10. Higham N. J. The accuracy of solutions to triangular systems // SIAM J. Numer. Anal. – 1989. – 26. – P. 1252 – 1256.
11. Amodio P., Mazzia F. A new approach to the backward error analysis in the LU factorization algorithm // BIT. –
1999. – 39. – P. 385 – 402.
12. Demmel J. W., Higham N. J., Shreiber R. S. Stability of block LU factorization // Numer. Linear Algebra and Appl. –
1995. – 2. – P. 173 – 190.
13. Jinxi Zhao, Weiguo Wang, Weiqing Ren. Stability of the matrix factorization for solving block tridiagonal symmetric
indefinite linear systems // BIT Numer. Math. – 2004. – 44. – P. 181 – 188.
14. Mattheij R. M. M. The stability of LU -decompostions of block tridiagonal matrices // Bull. Austral. Math. Soc. –
1984. – 29. – P. 177 – 205.
15. Forsgren A., Gill P. E., Shinnerl J. R. Stability of symmetric ill-conditioned systems arising in interior methods for
constrained optimization // SIAM J. Matrix Anal. and Appl. – 1996. – 17. – P. 187 – 211.
16. Bueno M. I., Dopico F. M. Stability and sensitivity of tridiagonal LU factorization without pivoting // BIT Numer.
Math. – 2004. – 44. – P. 651 – 673.
17. Demmel J. W., Higham N. J. Stability of block algorithms with fast level-3 BLAS // ACM Math. Software. – 1992. –
18. – P. 274 – 291.
18. Stoer J., Bulirsch R. Introduction to numerical analysis: – 2nd ed. – New York: Springer-Verlag, 1993.
Received 25.04.13
ISSN 1027-3190. Укр. мат. журн., 2016, т. 68, № 12
|
| id | umjimathkievua-article-1953 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:15:54Z |
| publishDate | 2016 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/e9/8a1bfbf4006cd0a0d0e38f9ebcfe75e9.pdf |
| spelling | umjimathkievua-article-19532019-12-05T09:32:42Z Perturbation and error analyses of partitioned LU factorization for block tridiagonal linear systems Аналiз збурень та похибок розбитої на частини LU факторизацiї для блочно-тридiагональних лiнiйних систем Huang, Ting-Zhu Wu, Chi-Yе Хуан, Тінг-Жу Ву, Чи-Йе The perturbation and backward error analyses of the partitioned LU factorization for block tridiagonal matrices are presented. Moreover, we consider the perturbation bounds for the partitioned LU factorization for block tridiagonal linear systems. Finally, numerical examples are given to verify our results. Наведено аналiз збурень та зворотний аналiз похибок для розбитої на частини LU факторизацiї блочно-тридiагональних матриць. Крiм того, вивчаються границi збурень для розбитої на частини LU факторизацiї блочно- тридiагональних лiнiйних систем. Також наведено числoвi експерименти, якi пiдтверджують справедливiсть даних результатiв. Institute of Mathematics, NAS of Ukraine 2016-12-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/1953 Ukrains’kyi Matematychnyi Zhurnal; Vol. 68 No. 12 (2016); 1683-1695 Український математичний журнал; Том 68 № 12 (2016); 1683-1695 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/1953/935 Copyright (c) 2016 Huang Ting-Zhu; Wu Chi-Yе |
| spellingShingle | Huang, Ting-Zhu Wu, Chi-Yе Хуан, Тінг-Жу Ву, Чи-Йе Perturbation and error analyses of partitioned LU factorization for block tridiagonal linear systems |
| title | Perturbation and error analyses of partitioned LU factorization
for block tridiagonal linear systems |
| title_alt | Аналiз збурень та похибок розбитої на частини LU
факторизацiї для блочно-тридiагональних лiнiйних систем |
| title_full | Perturbation and error analyses of partitioned LU factorization
for block tridiagonal linear systems |
| title_fullStr | Perturbation and error analyses of partitioned LU factorization
for block tridiagonal linear systems |
| title_full_unstemmed | Perturbation and error analyses of partitioned LU factorization
for block tridiagonal linear systems |
| title_short | Perturbation and error analyses of partitioned LU factorization
for block tridiagonal linear systems |
| title_sort | perturbation and error analyses of partitioned lu factorization
for block tridiagonal linear systems |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/1953 |
| work_keys_str_mv | AT huangtingzhu perturbationanderroranalysesofpartitionedlufactorizationforblocktridiagonallinearsystems AT wuchiye perturbationanderroranalysesofpartitionedlufactorizationforblocktridiagonallinearsystems AT huantíngžu perturbationanderroranalysesofpartitionedlufactorizationforblocktridiagonallinearsystems AT vučije perturbationanderroranalysesofpartitionedlufactorizationforblocktridiagonallinearsystems AT huangtingzhu analizzburenʹtapohibokrozbitoínačastinilufaktorizaciídlâbločnotridiagonalʹnihlinijnihsistem AT wuchiye analizzburenʹtapohibokrozbitoínačastinilufaktorizaciídlâbločnotridiagonalʹnihlinijnihsistem AT huantíngžu analizzburenʹtapohibokrozbitoínačastinilufaktorizaciídlâbločnotridiagonalʹnihlinijnihsistem AT vučije analizzburenʹtapohibokrozbitoínačastinilufaktorizaciídlâbločnotridiagonalʹnihlinijnihsistem |