Computation of the Newton step for the even and odd characteristic polynomials of a symmetric positive definite Toeplitz matrix. (English) Zbl 1094.65028
The paper focuses on the computation of the Newton step for the Newton method for the numerical evaluation of the roots of the characteristic polynomial and the characteristic even and odd polynomials of a symmetric positive definite Toeplitz matrix.
The first part represents an introduction containing the actual methods used to solve this type of problems.
The second part contains some preliminaries. The main notations used are made explicit: the \((i,j)\)-th element of an \(n\times n\) symmetric Toeplitz matrix and the basic properties of this type of matrices, an even vector, an odd vector, the so-called Yule-Walker equations. The split-Durbin algorithm or the split-Levinson algorithm, and the Newton algorithm for solving a nonlinear equation \(f(x)=0,\) where \(f:\mathbb R\to \mathbb R\) are also presented.
The third part concerns the computation of the Newton step for the characteristic polynomial, starting with a result which allows us to replace the quotient between the characteristic polynomial and its derivative by the inverse of a trace of an appropriate matrix. A theorem is also presented which gives a characterization for the Newton step for the characteristic polynomial \(p_n(\lambda)\) of an \(n\times n\) symmetric positive definite Toeplitz matrix \(T_n,\) using the Gohberg-Semencul formula.
In the fourth section one presents the formula for the Newton step for the even and odd characteristic polynomial \(p_n^e(\lambda)\) and \(p_n^o(\lambda)\) of an \(n\times n\) symmetric positive definite Toeplitz matrix \(T_n.\) An analysis of the computational cost of the presented recursions is also provided, in comparison with the algorithm given by A. Melman [SIAM J. Matrix Anal. Appl. 25, No. 4, 947–963 (2004; Zbl 1065.65055)].
In the fifth section one compares the number of flops for the various methods, using numerical results from A. Melman [loc. cit.], providing only the change of the amount of work per iteration, not the number of iterations. One emphasizes that further improvements can be achieved by considering double Newton steps or methods other than Newton’s one, such as Laguerre-type methods.
The first part represents an introduction containing the actual methods used to solve this type of problems.
The second part contains some preliminaries. The main notations used are made explicit: the \((i,j)\)-th element of an \(n\times n\) symmetric Toeplitz matrix and the basic properties of this type of matrices, an even vector, an odd vector, the so-called Yule-Walker equations. The split-Durbin algorithm or the split-Levinson algorithm, and the Newton algorithm for solving a nonlinear equation \(f(x)=0,\) where \(f:\mathbb R\to \mathbb R\) are also presented.
The third part concerns the computation of the Newton step for the characteristic polynomial, starting with a result which allows us to replace the quotient between the characteristic polynomial and its derivative by the inverse of a trace of an appropriate matrix. A theorem is also presented which gives a characterization for the Newton step for the characteristic polynomial \(p_n(\lambda)\) of an \(n\times n\) symmetric positive definite Toeplitz matrix \(T_n,\) using the Gohberg-Semencul formula.
In the fourth section one presents the formula for the Newton step for the even and odd characteristic polynomial \(p_n^e(\lambda)\) and \(p_n^o(\lambda)\) of an \(n\times n\) symmetric positive definite Toeplitz matrix \(T_n.\) An analysis of the computational cost of the presented recursions is also provided, in comparison with the algorithm given by A. Melman [SIAM J. Matrix Anal. Appl. 25, No. 4, 947–963 (2004; Zbl 1065.65055)].
In the fifth section one compares the number of flops for the various methods, using numerical results from A. Melman [loc. cit.], providing only the change of the amount of work per iteration, not the number of iterations. One emphasizes that further improvements can be achieved by considering double Newton steps or methods other than Newton’s one, such as Laguerre-type methods.
Reviewer: R. Militaru (Craiova)
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15B57 | Hermitian, skew-Hermitian, and related matrices |
| 65H05 | Numerical computation of solutions to single equations |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 26C10 | Real polynomials: location of zeros |
Keywords:
characteristic polynomial; Newton’s method; Newton step; symmetric positive definite Toeplitz matrix; split-Durbin algorithm; split-Levinson algorithm; Gohberg-Semencul formulaCitations:
Zbl 1065.65055References:
| [1] | Gregory S. Ammar and William B. Gragg, The generalized Schur algorithm for the superfast solution of Toeplitz systems, Rational approximation and applications in mathematics and physics (Łańcut, 1985) Lecture Notes in Math., vol. 1237, Springer, Berlin, 1987, pp. 315 – 330. · Zbl 0614.65023 · doi:10.1007/BFb0072474 |
| [2] | Gregory S. Ammar and William B. Gragg, Numerical experience with a superfast real Toeplitz solver, Linear Algebra Appl. 121 (1989), 185 – 206. Linear algebra and applications (Valencia, 1987). · Zbl 0684.65021 · doi:10.1016/0024-3795(89)90701-5 |
| [3] | A. Cantoni and P. Butler, Eigenvalues and eigenvectors of symmetric centrosymmetric matrices, Linear Algebra and Appl. 13 (1976), no. 3, 275 – 288. · Zbl 0326.15007 |
| [4] | George Cybenko and Charles Van Loan, Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Statist. Comput. 7 (1986), no. 1, 123 – 131. · Zbl 0626.65030 · doi:10.1137/0907009 |
| [5] | P. Delsarte and Y. Genin, Spectral properties of finite Toeplitz matrices, Mathematical theory of networks and systems (Beer Sheva, 1983) Lect. Notes Control Inf. Sci., vol. 58, Springer, London, 1984, pp. 194 – 213. · Zbl 0559.15017 · doi:10.1007/BFb0031053 |
| [6] | Philippe Delsarte and Yves V. Genin, The split Levinson algorithm, IEEE Trans. Acoust. Speech Signal Process. 34 (1986), no. 3, 470 – 478. · doi:10.1109/TASSP.1986.1164830 |
| [7] | Durbin, J. (1960): The fitting of time series model. Rev. Inst. Int. Stat., 28, pp. 233-243. · Zbl 0101.35604 |
| [8] | I. C. Gohberg and A. A. Semencul, The inversion of finite Toeplitz matrices and their continual analogues, Mat. Issled. 7 (1972), no. 2(24), 201 – 223, 290 (Russian). · Zbl 0288.15004 |
| [9] | Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009 |
| [10] | Wolfgang Mackens and Heinrich Voss, Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix by Newton-type methods, SIAM J. Sci. Comput. 21 (1999/00), no. 4, 1650 – 1656. · Zbl 0956.65029 · doi:10.1137/S1064827598342195 |
| [11] | Nicola Mastronardi and Daniel Boley, Computing the smallest eigenpair of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Comput. 20 (1999), no. 5, 1921 – 1927. · Zbl 0936.65039 · doi:10.1137/S106482759732229X |
| [12] | A. Melman, Extreme eigenvalues of real symmetric Toeplitz matrices, Math. Comp. 70 (2001), no. 234, 649 – 669. · Zbl 0968.65018 |
| [13] | A. Melman, A two-step even-odd split Levinson algorithm for Toeplitz systems, Linear Algebra Appl. 338 (2001), 219 – 237. · Zbl 0991.65031 · doi:10.1016/S0024-3795(01)00386-X |
| [14] | A. Melman, Computation of the smallest even and odd eigenvalues of a symmetric positive-definite Toeplitz matrix, SIAM J. Matrix Anal. Appl. 25 (2004), no. 4, 947 – 963. · Zbl 1065.65055 · doi:10.1137/S0895479803423354 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
