A (2,3)-Pade approximation of secular function of Toeplitz matrix.

Kostic, Aleksandra ; Velic, Melisa

Abstract: In this note we present a (2,3)-Pade approximation of secular function for computing the smallest eigenvalue [[lambda].sub.1] of a real symmetric positive definite Toeplitz matrix (RSPDTM). This method is based on approximation of secular function by using the Taylor series characteristic polynomial of R SPDTM The characteristic polynomial has been approximated with the polynomial of the third order from the Taylor series because it is easy to calculate [p".sub.n-1] ([lambda]) from specific structure of Toeplitz matrix from Gohberg-Simencul formulae. It is very easy to calculate [p.sup.m.sub.n-1] ([lambda]) from the secular function.

Key words: eigenvalue problem, Toeplitz matrix, (2,3)-Pade approximation

1. INTRODUCTION

From Pisarenko's work (Pisarenko, 1973) the problem of finding the smallest eigenvalue of a real symmetric, positive definite Toeplitz matrix (RSPDTM) plays an important role in signal processing. The computation of the minimum eigenvalue of [T.sub.n] was studied in, e. g. in (Cybenko & Van Loan, 1986; Kostic, 2004; Kostic & Cohodar, 2008; Mackens & Voss, 1997, 2000; Melman, 2006; Mastronardi & Boley, 1999).

In this paper we propose a (2,3)-Pade approximation for the computation of the root of the secular function of a real symmetric positive definite Toeplitz matrix. This method is a combination of approximation for secular function and approximation for characteristic polynomial.

The paper is organized as follows. In Section 2 we present the basic properties of Toeplitz matrices and the notation we will use. In Section 3 we present (2,3)-Pade approximation for secular function. In Section 4 we present numerical results for Section 3. In Section 5 we present conclusion of the paper.

2. PRELIMINARIES

The Teoplitz matrix is quadratic matrix which has the same elements in its respective diagonals, which means that [a.sub.ij] = [a.sub.n+1-j,n+1-i]. Because we take in consideration symmetric matrices it also means that [a.sub.ij] = [a.sub.ji]. The Teoplitz matrix is defined with vector (1, [t.sub.1], ..., [t.sub.n-1]) [member of] [R.sup.n] so the (i,j)th element of an n x n symmetric Toeplitz matrix [T.sub.n] is given by [t.sub.[absolute value of i-j]]. We can conclude, form above given, that Teoplitz matrices are centrosymmetric and satisfy J[T.sub.n]J = [T.sub.n]. We use I for the identity matrix and J:= [([[delta].sub.i,n+1-i]).sub.i,j=1, ..., n] for the exchange, or "flip" matrix.

3. A (2, 3)-PADE APPROXIMATION

A Pade rational approximation to f(x) on [a,b] is the quotient of two polynomials [P.sub.n](x) and [Q.sub.m](x) of degrees n and m, respectively. We use the notation [R.sub.n,m](X) to denote this quotient:

[R.sub.n,m] (x) = [p.sub.n](x)/[Q.sub.m](x)

Pade approximation is based on theorem Theorem (Pade Approximation) Assume that f [member of] [C.sup.n+m], and that f(x)Maclaurin polynomial expansion of degree at least n + m. The

f(x) [approximately equal to] [R.sub.n,m](x) = [P.sub.n](x)/[Q.sub.m](x)

where [P.sub.n](x) and [Q.sub.m](x) are polynomials of degree n and m, respectively.

Melman (Melman 1999) considered rational approximations

[r.sub.j]([lambda]) = -1 + [lambda] + [[rho].sub.j]([lambda])

of f where

[[rho].sub.1]([lambda]):= a/b - [lambda], [[rho].sub.2]([lambda]):= a + b/c - [lambda], [[rho].sub.3]([lambda]):= a/b - [lambda] + c/d - [lambda]

And the parameters a, b, c, d are determined such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus [[rho].sub.1], [[rho].sub.2] and [[rho].sub.3], respectively, are the (0,1)-, (1,1)- and (1,2)- Pade approximations of [PHI]([lambda]):=[t.sup.T][([T.sub.n-1], - [lambda]I).sup.-1]t (Melman, 1999).

Here we present a new rational approximation of the secular function. This new rational approximation is actually (2, 3)-Pade approximation for secular function.

The secular function q([lambda]) = -1 + [lambda] + [t.sup.T] [([T.sub.n-1] - [lambda]I).sup.-1] t may be written as

q([lambda]) = - [p.sub.n]([lambda]/[p.sub.n-1]([lambda]) (1)

where [p.sub.n]([lambda]) and [p.sub.n-1]([lambda]) are characteristic polynomials of [T.sub.n] and Tn-1 respectively.

We consider a rational approximation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

of q, where d := [bar.[lambda]] - 1 and parameters [A.sub.2] and [B.sub.3] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

[bar.[lambda]] and [??] are not in the spectrum of [T.sub.n] and [T.sub.n-1]. Parameters [B.sub.0], [B.sub.1] and [B.sub.3] are given by to approximate characteristic polynomial of [T.sub.n-1] with the polynomial of the second order based on the Taylor series. Parameters [A.sub.0] and [A.sub.1] can be easily calculated by dividing characteristic polynomials [p.sub.n] and [p.sub.n-1]. We give

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

For easy calculation of given parameters we need theoretical base given in works (Kostic 2009, Kostic & Cohodar 2008 and Melman 2006).

4. NUMERICAL RESULTS

To test the method we considered the following class of Toeplitz matrices:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

where m is chosen such that the diagonal of [T.sub.n] is normalized to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are uniformly distributed random in the interval [0,1] (cf. Cybenko and Van Loan). Table 1 contains the average number of Durbin steps needed to determine in 100 test problem each of the dimension n=32,64,128,256,512 and 1024.

5. CONCLUSION

In this paper we present a (2,3)-Pade approximation of the secular function for computing the smallest eigenvalue [[lambda].sub.1] of a real symmetric positive definite Toeplitz matrix (RSPDTM) . This method is based on approximation of secular function by using the Taylor series characteristic polynomial of RSPDTM. In this way, we improved previously developed algorithm what we also have expected, because we used second derivative of characteristic polynomial. Calculation of second derivative of characteristic polynomial is interesting result witch enables new rational approximation for secular function. New rational approximation presented in this note is actually (2,3) - Pade approximation. It is proven that the Pade approximation is the best approximation of a rational function. In this paper we have also numerically check this contention. This is the main contribution of the paper.

It is very interesting to approximate the even and odd secular functions on above pointed out manner but with much more using properly of symmetry of the Toeplitz matrices. This will be further investigated in the next step of our future research plans.

6. REFERENCES

Cantoni A. & Butler F. (1976) Eigenvalues and eigenvectors of symmetric centrosymmetric matrices, Linear Algebra Appl., 13 pp. 275-288. MR0395514(53:476)

Cybenko, G. & Van Loan, C.F. (1986). Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Stat. Comput, Vol. 7, No. I, pp. 123-131. MRO819462(87b:65042)

Dembo, A. (1988) Bounds on the extreme eigenvalues of positive definite Toeplitz matrices. IEEE Trans. Inform. Theory,34, .352-355

Gohberg, I.C. & Semencul, A. A. (1972). The inversion of finite Toeplitz matrices and their continual analogues. (Russian), Mat. Issued. Vol. 7., No. 2(24), pp. 201-223. MR0353038 (50:5524)

Kostic A. (2004) Verfahren zur Bestimmung einiger extremaler Eienwerte einer symmetrischen Toeplitz Matrix, Shaker Verlag, ISBN 3-8322-3235-4, Aachen

Kostic A. (2009) Approximation of characteristic polynomial of SPDTM to appear in DAAAM International scientific book 2009.

Kostic A. & Cohodar M. (2008). Quadratic approximation of characteristic polynomial of symmetric positive definite Toeplitz matrix, Proceedings of l 9th International DAAAM Symposium, ISBN 978-3-901509-68-1,ISSN 1726-9679, pp 192

Mackens, W. & Voss, H. (2000). Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix by Newton-type methods, SIAMJ. Sci. Comput., Vol. 21. No. 4, pp. 1650-1656 MR1756049 (2001g:65043)

Mackens, W. & Voss, H. (1997). The minimum eigenvalue of a symmetric positive definite Toeplitz matrix and rational Hermitian interpolation, SIAM J. Matt. Anal. Appl, Vol. 18. pp. 523-534

Mastronardi, N & Boley, D.(1999). Computing the smallest eigenpair of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Comput., Vol. 20, No. 5, pp. 1921-1927. MR 1694690

Melman, A. (1999), Bounds on the extreme eigenvalues of real symmetric Teoplitz matrices, SIAM J. Matrix Anal. Appl., 21 (2):362-378

Melman, A. (2003), Computation of the smallest even and odd eigenvalues of symmetric positive indefinite Toplitz matrix. SIAM J. Matt. Anal. Appl.

Melman, A. (2006). Computation of the Newton step for the even and odd characteristic polynomials of a symmetric positive definite Toeplitz matrix, Mathematics of computation, Vol. 75, No 254, pp. 817-832, S 0255718(05)01796-5

Pisarenko, V. F. (1973). The retrieval of harmonics from a covariance function. Geophys, J. R. astr. Soc., Vol. 33., 347-366

Voss, H. (1999). Symmetric schemes for computing the minimum eigenvalue of a symmetric Toeplitz matrix, Lin. Alg. Appl., 287:377-385

Voss, H. (1999). Bounds for the minimum eigenvalue of symmetric Toeplitz matrix, Electronic Transactions on Numerical Analysis, Vol. 8, 127-138

Tab. 1. The average number of Durbin steps

Dim New method

32 4.8575
64 5.29
128 5.2925
256 5.72
512 6.38
1024 6.8