Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Analysis of third-order methods
for secular equations

Author: A. Melman
Journal: Math. Comp. 67 (1998), 271-286
MathSciNet review: 1432130
Full-text PDF

Abstract | References | Additional Information

Abstract: Third-order numerical methods are analyzed for secular equations. These equations arise in several matrix problems and numerical linear algebra applications. A closer look at an existing method shows that it can be considered as a classical method for an equivalent problem. This not only leads to other third-order methods, it also provides the means for a unifying convergence analysis of these methods and for their comparisons. Finally, we consider approximated versions of the aforementioned methods.

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

  • 1. 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
  • 2. Brown G.H., Jr. (1978): On Halley's variation of Newton's method. Amer. Math. Monthly 84, pp. 726-728. MR 57:1866
  • 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. 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
  • 6. Dongarra, J.J., Sorensen, D.C. (1987): A fully parallel algorithm for the symmetric eigenvalue problem. SIAM J. Sci. Stat. Comput. 8, No.2, pp. s139-s154. MR 88f:65054
  • 7. Donoghue W.F., Jr. (1974): Monotone matrix functions and analytic continuation. Springer-Verlag, Berlin Heidelberg. MR 58:6279
  • 8. Fuhrmann, D.R. (1988): An algorithm for subspace computation with applications in signal processing. SIAM J. Matrix Anal. Appl. 9, No.2, pp. 213-220. MR 89f:65040
  • 9. Gander, W., Golub, G.H., von Matt, U. (1989): A constrained eigenvalue problem. Linear Algebra Appl. 114-115, pp. 815-839. MR 90e:15008
  • 10. 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, No.1, pp. 161-173. MR 91d:65058
  • 11. Golub, G.H. (1973): Some modified matrix eigenvalue problems. SIAM Rev. 15, No.2, pp. 318-334. MR 48:7569
  • 12. 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
  • 13. Gragg, W.B., Thornton, J.R., Warner, D.D. (1992): Parallel divide and conquer algorithms for the symmetric tridiagonal eigenproblem and the bidiagonal singular value problem. In Modeling and Simulation, W.G. Vogt and M.H. Mickle, eds., vol. 3, part 1, pp. 49-56. University of Pittsburgh School of Engineering, Pittsburgh, PA.
  • 14. 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, No.4, pp. 1266-1276. MR 96c:65057
  • 15. Henrici, P. (1964): Elements of numerical analysis. John Wiley & Sons, Inc., New York. MR 29:4173
  • 16. Li, R.C. (1994): Solving secular equations stably and efficiently. Technical Report UCB//CSD-94-851, Computer Science Division, University of California, Berkeley, CA. Also : LAPACK Working Notes 89.
  • 17. Melman, A. (1995): Numerical solution of a secular equation. Numer. Math. 69, pp. 483-493. MR 95j:65050
  • 18. Melman, A. (1997): A unifying convergence analysis of second-order methods for secular equations. Math. Comp. 66 (1997), 333-344. CMP 97:02
  • 19. Ostrowski A.M. (1973): Solution of equations in Euclidean and Banach Spaces. Academic Press, New York. MR 50:11760
  • 20. Salehov G.S. (1952): On the convergence of the process of tangent hyperbolas. Dokl. Akad. Nauk SSSR 82, pp. 525-528 (in Russian). MR 14:91f
  • 21. \v{S}afiev R.A. (1963): The method of tangent hyperbolas. Dokl. Akad. Nauk SSSR 149, pp. 788-791 (in Russian). Translation in Soviet Math. Dokl. 4, pp. 482-485. MR 28:734
  • 22. Scavo T.R. and Thoo J.B. (1995): On the geometry of Halley's method. Amer. Math. Monthly 102, pp. 417-426. MR 96f:01019
  • 23. Traub J.F. (1964): Iterative methods for the solution of equations. Prentice-Hall, Inc., Englewood Cliffs, New Jersey. MR 29:6607
  • 24. von Matt, U. (1993): Large constrained quadratic problems. Verlag der Fachvereine, Zürich.

Additional Information

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

Keywords: Secular equation, nonlinear approximation, third-order convergence
Received by editor(s): May 15, 1996
Received by editor(s) in revised form: September 16, 1996
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society