Analysis of third-order methods for secular equations
HTML articles powered by AMS MathViewer
- by A. Melman PDF
- Math. Comp. 67 (1998), 271-286 Request permission
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
- Carlos F. Borges and William B. Gragg, A parallel divide and conquer algorithm for the generalized real symmetric definite tridiagonal eigenproblem, Numerical linear algebra (Kent, OH, 1992) de Gruyter, Berlin, 1993, pp. 11–29. MR 1244151
- George H. Brown Jr., On Halley’s variation of Newton’s method, Amer. Math. Monthly 84 (1977), no. 9, 726–728. MR 461884, DOI 10.2307/2321256
- James R. Bunch, Christopher P. Nielsen, and Danny C. Sorensen, Rank-one modification of the symmetric eigenproblem, Numer. Math. 31 (1978/79), no. 1, 31–48. MR 508586, DOI 10.1007/BF01396012
- James R. Bunch and Christopher P. Nielsen, Updating the singular value decomposition, Numer. Math. 31 (1978/79), no. 2, 111–129. MR 509670, DOI 10.1007/BF01397471
- J. J. M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math. 36 (1980/81), no. 2, 177–195. MR 611491, DOI 10.1007/BF01396757
- J. J. Dongarra and D. C. Sorensen, A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Statist. Comput. 8 (1987), no. 2, S139–S154. Parallel processing for scientific computing (Norfolk, Va., 1985). MR 879400, DOI 10.1137/0908018
- William F. Donoghue Jr., Monotone matrix functions and analytic continuation, Die Grundlehren der mathematischen Wissenschaften, Band 207, Springer-Verlag, New York-Heidelberg, 1974. MR 0486556, DOI 10.1007/978-3-642-65755-9
- Daniel R. Fuhrmann, An algorithm for subspace computation, with applications in signal processing, SIAM J. Matrix Anal. Appl. 9 (1988), no. 2, 213–220. SIAM Conference on Linear Algebra in Signals, Systems, and Control (Boston, Mass., 1986). MR 938557, DOI 10.1137/0609018
- Walter Gander, Gene H. Golub, and Urs von Matt, A constrained eigenvalue problem, Linear Algebra Appl. 114/115 (1989), 815–839. MR 986908, DOI 10.1016/0024-3795(89)90494-1
- Doron Gill and Eitan Tadmor, 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. Statist. Comput. 11 (1990), no. 1, 161–173. MR 1032233, DOI 10.1137/0911010
- Gene H. Golub, Some modified matrix eigenvalue problems, SIAM Rev. 15 (1973), 318–334. MR 329227, DOI 10.1137/1015032
- W. B. Gragg and L. Reichel, A divide and conquer method for unitary and orthogonal eigenproblems, Numer. Math. 57 (1990), no. 8, 695–718. MR 1065519, DOI 10.1007/BF01386438
- 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.
- Ming Gu and Stanley C. Eisenstat, A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM J. Matrix Anal. Appl. 15 (1994), no. 4, 1266–1276. MR 1293916, DOI 10.1137/S089547989223924X
- Peter Henrici, Elements of numerical analysis, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR 0166900
- 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.
- A. Melman, Numerical solution of a secular equation, Numer. Math. 69 (1995), no. 4, 483–493. MR 1314599, DOI 10.1007/s002110050104
- Melman, A. (1997): A unifying convergence analysis of second-order methods for secular equations. Math. Comp. 66 (1997), 333–344.
- A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Pure and Applied Mathematics, Vol. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations. MR 0359306
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- R. A. Šafiev, On the method of tangent hyperbolas, Dokl. Akad. Nauk SSSR 149 (1963), 788–791 (Russian). MR 0157501
- T. R. Scavo and J. B. Thoo, On the geometry of Halley’s method, Amer. Math. Monthly 102 (1995), no. 5, 417–426. MR 1327786, DOI 10.2307/2975033
- J. F. Traub, Iterative methods for the solution of equations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR 0169356
- 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
- MR Author ID: 293268
- Email: melman@bgumail.bgu.ac.il
- Received by editor(s): May 15, 1996
- Received by editor(s) in revised form: September 16, 1996
- © Copyright 1998 American Mathematical Society
- Journal: Math. Comp. 67 (1998), 271-286
- DOI: https://doi.org/10.1090/S0025-5718-98-00884-9
- MathSciNet review: 1432130