A new algorithm for computing the inverse and the determinant of a Hessenberg matrix

A new algorithm for computing the inverse and the determinant of a Hessenberg matrix

Applied Mathematics and Computation 218 (2011) 4433–4436 Contents lists available at SciVerse ScienceDirect Applied Mathematics and Computation jour...

144KB Sizes 3 Downloads 221 Views

Applied Mathematics and Computation 218 (2011) 4433–4436

Contents lists available at SciVerse ScienceDirect

Applied Mathematics and Computation journal homepage: www.elsevier.com/locate/amc

A new algorithm for computing the inverse and the determinant of a Hessenberg matrix q Yue-Hui Chen ⇑, Cheng-Yi Yu Department of Mathematics and Information Science, Zhangzhou Normal University, Zhangzhou, Fujian 363000, China

a r t i c l e

i n f o

a b s t r a c t In this paper, a new recursive symbolic computational Hessenberg matrix algorithm is presented to compute the inverse and the determinant of a Hessenberg matrix. Ó 2011 Elsevier Inc. All rights reserved.

Keywords: Hessenberg matrix Inverse Determinant

1. Introduction Hessenberg matrix is one of the important matrices in numerical analysis [1,2]. For example, the Hessenberg decomposition played an important role in the matrix eigenvalues computation [2]. In this article, we present a new recursive algorithm for computing the inverse and the determinant of an n-by-n lower Hessenberg matrix. It extends the work presented in [3].

2. Notations and preliminaries We consider the n-by-n lower Hessenberg matrix of the form

0

h11

B B B h21 B B B . H ¼ B .. B B B B hn1;1 @ hn;1

1

h12 h22

h23

.. .

..

hn1;2



hn1;n1

hn;2



hn;n1

.

..

.

C C C C C C C: C C C hn1;n C A hn;n

Assume that H is nonsingular. Without loss of generality, suppose that all elements of the super diagonal are non-zero, i.e., hi,i+1 – 0, i = 1, 2, . . . , n  1. If hi,i+1 = 0, H can be solved by partitioning. Let the (n + 1)-by-(n + 1) lower triangular matrix

q

Foundation item: The Foundation of Fujian Educational Committee (JB07147).

⇑ Corresponding author.

E-mail address: [email protected] (Y.-H. Chen). 0096-3003/$ - see front matter Ó 2011 Elsevier Inc. All rights reserved. doi:10.1016/j.amc.2011.10.022

4434

Y.-H. Chen, C.-Y. Yu / Applied Mathematics and Computation 218 (2011) 4433–4436

0

1

B  B B B h11 T B e1 j 0 B C B e ¼B H  A ¼ B h21 @  B B .. H j en B . B B @ hn1;1 0

0





0









1

h12

j j

h22 .. .

h23 .. .

..

hn1;2



hn1;n1

hn1;n

j

hn;2



hn;n1

hn;n

j

hn;1

j j

.

0

1

 C C C 0 C C .. C C . C; C .. C . C C C 0 A 1

where e1 and en are the first and the last column of matrix In respectively, and In denotes the identity matrix of order n.   e is nonsingular. Partition H e 1 into a LT , where a, L, h and b are matrices of size n  1, n  n, 1  1, It is clear that H h b n  1 respectively. By

e H e 1 ¼ H



eT1 H

0



en

a

L

h

T



 ¼

b

1

0

0 In



¼ Inþ1 ;

we have

Ha þ hen ¼ 0

ð2:1Þ

HL þ en bT ¼ In :

ð2:2Þ

and

e 1 is singular, which is It is easy to see h – 0. In fact, if h = 0, then it follows that a = 0 since Ha = 0 by (2.1). This implies that H a contradiction. From the (2.1), we know that en = h1Ha. Substitution of this equation into (2.2) that yields the following equation 1

HðL  h abT Þ ¼ In : Thus 1

H1 ¼ L  h abT : It is noticed that 1

In

h a

0

1

!

a

L

h

bT



1

¼

0 L  h abT bT

h

! :

ð2:3Þ

e is its associated lower triangular matrix as Lemma 1. Suppose that H is a nonsingular lower Hessenberg matrix of order n and H above. Then

e detðHÞ ¼ ð1Þn h  detð HÞ: Proof. From (2.3) it is easy to verify that

e 1 Þ ¼ ð1Þnþ1þ1 h  detðL  h abT Þ ¼ ð1Þn h  detðH1 Þ: detð H 1

Thus

e detðHÞ ¼ ð1Þn h  detð HÞ:



3. Main results

e be the Theorem 1. Let H be a nonsingular lower Hessenberg matrix and all elements of the super diagonal be non-zero, and H   e 1 as a LT , where a, L, h and b are as above. Then associated matrix as above. Partition H h b (1) H1 = L  h1abT, and (2) detðHÞ ¼ ð1Þn h  Pn1 i¼1 hi;iþ1 ,

Y.-H. Chen, C.-Y. Yu / Applied Mathematics and Computation 218 (2011) 4433–4436

4435

where hi,i+1 (i = 1,2, . . . , n  1) are the super diagonal elements of H. Proof (1) This is readily obtained above. e ¼ Pn1 hi;iþ1 , we can get it. (2) Using Lemma 1 and detð HÞ i¼1

h

e 1 . To find the inverse and the determinant of H, it is necessary to obtain the matrix a, L, h and b, i.e., to compute H e 1 . In the following we show how to determine the H Denote

e 1 ¼ ðc1 ; c2 ; . . . ; cnþ1 Þ; H e 1 . where cj is jth column of H e 1 H e ¼ Inþ1 , where In+1 denotes the identity matrix of order (n + 1), we have From the relation H n X

hij ciþ1 ¼ ej

for j ¼ 1; 2; . . . ; n

i¼j1

and

cnþ1 ¼ enþ1 ; where h01 = 1 and ej is the jth column of the In+1. Consequently, all cj can be calculated recursively as follows

8 c ¼ enþ1 > < nþ1 ! n  P > hj1;j c ¼ e  h c j ij iþ1 : j

j ¼ n; n  1; . . . ; 1

i¼j

e 1 is lower triangular matrix, we obtain the following algorithms: Combining this iteration with Theorem 1 when H e 1 , denoted as C Algorithm 1: Computing H e (1) input n and H; (2) C = zeros (n+1); C(n + 1, n + 1) = 1; (3) for j = n : 1: 2 e jÞ; C(j, j) = a; a ¼ 1= Hðj; for k = j + 1 : n + 1 e : n þ 1; jÞÞ Cðk; jÞ ¼ a  ðCðk; k : n þ 1Þ  Hðk end end; (4) C(1, 1) = 1; for k = 2 : n + 1 e : k; 1ÞÞ Cðk; jÞ ¼ ðCðk; 2 : kÞ  Hð2 end.

Algorithm 2: Computing H1 and det (H), denoted as V and D respectively (1) h = C(n + 1,1); b = 1/h; (2) V = C(1 : n, 2 : n + 1) + b ⁄ C(1:n, 1) ⁄ C(n + 1, 2 : n + 1); (3) D = (1)n ⁄ h for j = 2 : n e jÞ D ¼ D  Hðj; end. Let us now  have a look  at the number of multiplications and divisions executed by Algorithms  1 and 2.  For Algorithm 1, it takes about 16 n3 þ 12 n2 operations in Step3, and about 12 n2 operations in Step4. We need about 16 n3 þ n2 operations to com  e 1 . Algorithm 2 amounts to about n2 operations. Therefore, we need about 1 n3 þ 2n2 operations computing H1. Our pute H 6   algorithm is better than Elouafi’s algorithm[1] that needs about 12 n3 þ n2 operations in computing H1.

4436

Y.-H. Chen, C.-Y. Yu / Applied Mathematics and Computation 218 (2011) 4433–4436

4. An example Consider the Hessenberg matrix as

0

1

1 1

B B1 B H¼B B1 B @1

1

1

1

1

1

1

1

1

C C C C: 1 C C 1 1 A 1 1

1

By Algorithm 1, we have

0 B B B B C¼B B B B @

1

0

0

0

0

0

1

0C C C 2 1 1 0 0 0C C: 4 2 1 1 0 0 C C C 8 4 2 1 1 0 A 16 8 4 2 1 1 1

1

0

0

0

Using Algorithm 2, we obtain

h ¼ 16; 0 H

1

0:5

0:25

0:125 0:0625 0:0625

1

C B B 0:5 0:25 0:125 0:0625 0:0625 C C B ¼V¼B 0:5 0:25 0:125 0:125 C C B 0 C B 0 0:5 0:25 0:25 A @ 0 0 0 0 0:5 0:5

and

detðHÞ ¼ D ¼ 16: Acknowledgment The authors gratefully acknowledge the referees for valuable comments and suggestions. References [1] M. Elouafi, A.D. Aiat Hadj, A new recursive algorithm for inverting Hessenberg matrices, Appl. Math. Comput. 214 (2009) 497–499. [2] G.H. Golub, C.F. Van Loan, Matrix Computations, third ed., Johns Hopkins University Press, Baltimore and London, 1996. pp. 341–352. [3] X.G. Lv, T.Z. Huang, J. Le, A note on computing the inverse and the determinant of a pentadiagonal Toeplitz matrix, Appl. Math. Comput. 206 (2008) 327– 331.