Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A unifying convergence analysis of second-order methods for secular equations

Author: A. Melman
Journal: Math. Comp. 66 (1997), 333-344
MSC (1991): Primary 65F15, 65H05
MathSciNet review: 1370854
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Existing numerical methods of second-order are considered for a so-called secular equation. We give a brief description of the most important of these methods and show that all of them can be interpreted as improvements of Newton's method for an equivalent problem for which Newton's method exhibits convergence from any point in a given interval. This interpretation unifies the convergence analysis of these methods, provides convergence proofs where they were lacking and furnishes ways to construct improved methods. In addition, we show that some of these methods are, in fact, equivalent. A second secular equation is also briefly considered.

References [Enhancements On Off] (What's this?)

  • 1. Arbenz, P., Golub, G.H. (1988): On the spectral decomposition of Hermitian matrices modified by low rank perturbations with applications. SIAM J. Matrix Anal. Appl. 9, pp. 40-58. MR 89c:15028
  • 2. Borges, C.F., Gragg, W.B. (1993): A parallel divide and conquer algorithm for the generalized real symmetric definite tridiagonal eigenproblem. In Numerical Linear Algebra and Scientific Computing, L. Reichel, A. Ruttan and R.S. Varga, eds., pp. 10-28. de Gruyter, Berlin. MR 94k:65051
  • 3. Bunch, J.R., Nielsen, C.P., Sorensen, D.C. (1978): Rank-one modification of the symmetric eigenproblem. Numer. Math. 31, pp. 31-48. MR 80g:65038
  • 4. Bunch, J.R., Nielsen, C.P. (1978): Updating the singular value decomposition. Numer. Math. 31, pp. 111-129. MR 80m:65025
  • 5. Chan, T.F., Olkin, J.A., Cooley, D.W. (1992): Solving quadratically constrained least squares using black box solvers. BIT 32, pp. 481-495. MR 93e:65091
  • 6. Cuppen, J.J.M. (1981): A divide and conquer method for the symmetric tridiagonal eigenvalue problem. Numer. Math. 36, pp. 177-195. MR 82d:65038
  • 7. Dongarra, J.J., Sorensen, D.C. (1987): A fully parallel algorithm for the symmetric eigenvalue problem. SIAM J. Sci. Stat. Comput. 8, pp. s139-s154. MR 88f:65054
  • 8. Faddeeva, V.N. (1959): Computational Methods of Linear Algebra. Dover Publications, New York. MR 20:6777
  • 9. Forsythe, G.E., Golub, G.H. (1965): On the stationary values of a second-degree polynomial on the unit sphere, J. Soc. Indust. Appl. Math. 13, pp. 1050-1068. MR 33:3453
  • 10. Fuhrmann, D.R. (1988): An algorithm for subspace computation with applications in signal processing. SIAM J. Matrix Anal. Appl. 9, pp. 213-220. MR 89f:65040
  • 11. Gander, W. (1981): Least squares with a quadratic constraint. Numer. Math. 36, pp. 291-307. MR 82c:65026
  • 12. Gander, W., Golub, G.H., von Matt, U. (1989): A constrained eigenvalue problem. Linear Algebra Appl. 114-115, pp. 815-839. MR 90e:15008
  • 13. Gill, D., Tadmor, E. (1990): An $O(N^2)$ method for computing the eigensystem of $N \times N$ symmetric tridiagonal matrices by the divide and conquer approach. SIAM J. Sci. Stat. Comput. 11, pp. 161-173. MR 91d:65058
  • 14. Golub, G.H. (1973): Some modified matrix eigenvalue problems. SIAM Rev. 15, pp. 318-334. MR 48:7569
  • 15. Golub, G.H., von Matt, U. (1991): Quadratically constrained least squares and quadratic problems. Numer. Math. 59, pp. 561-580. MR 92f:65049
  • 16. Gragg, W.B., Reichel, L. (1990): A divide and conquer method for unitary and orthogonal eigenproblems. Numer. Math. 57, pp. 695-718. MR 91h:65052
  • 17. Gu M., Eisenstat S.C. (1994): A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem. SIAM J. Matrix Anal. Appl. 15, pp. 1266-1276. MR 96c:65057
  • 18. Handy, S.L., Barlow, J.L. (1994): Numerical solution of the eigenproblem for banded, symmetric Toeplitz matrices. SIAM J. Matrix Anal. Appl. 15, pp. 205-214. MR 94j:65053
  • 19. Hanson, R., Phillips, J. (1975): An adaptive numerical method for solving linear Fredholm integral equations of the first kind. Numer. Math. 24, pp. 291-307. MR 53:7081
  • 20. Henrici, P. (1964): Elements of numerical analysis. John Wiley & Sons, Inc., New York. MR 29:4173
  • 21. Li, R.C. (1994): Solving secular equations stably and efficiently. Technical Report UCB//CSD-94-851, Computer Science Division, Department of EECS, University of California at Berkeley. (LAPACK working note No. 93).
  • 22. Melman, A. (1995): Numerical solution of a secular equation. Numer. Math. 69, pp. 483-493. MR 95j:65050
  • 23. Reinsch, C.H. (1967): Smoothing by spline functions. Numer. Math. 10, pp. 177-183. MR 45:4598
  • 24. Reinsch, C.H. (1971): Smoothing by spline functions II. Numer. Math. 16, pp. 451-454. MR 45:4598
  • 25. von Matt, U. (1993): Large constrained quadratic problems. Verlag der Fachvereine, Zürich.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65F15, 65H05

Retrieve articles in all journals with MSC (1991): 65F15, 65H05

Additional Information

A. Melman
Affiliation: Department of Industrial Engineering and Management, Ben-Gurion University, Beer-Sheva 84105, Israel

Keywords: Symmetric eigenvalues, secular equation, nonlinear approximation, global convergence
Received by editor(s): February 12, 1995
Received by editor(s) in revised form: November 13, 1995
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society