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

HTML articles powered by AMS MathViewer

- by A. Melman PDF
- Math. Comp.
**66**(1997), 333-344 Request permission

## 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

- Peter Arbenz and Gene H. Golub,
*On the spectral decomposition of Hermitian matrices modified by low rank perturbations with applications*, SIAM J. Matrix Anal. Appl.**9**(1988), no. 1, 40–58. MR**938057**, DOI 10.1137/0609004 - 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** - 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 - Tony F. Chan, Julia A. Olkin, and Donald W. Cooley,
*Solving quadratically constrained least squares using black box solvers*, BIT**32**(1992), no. 3, 481–494. MR**1179234**, DOI 10.1007/BF02074882 - 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 - V. N. Faddeeva,
*Computational methods of linear algebra*, Dover Publications, Inc., New York, 1959. MR**0100344** - George E. Forsythe and Gene H. Golub,
*On the stationary values of a second-degree polynomial on the unit sphere*, J. Soc. Indust. Appl. Math.**13**(1965), 1050–1068. MR**195250** - 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,
*Least squares with a quadratic constraint*, Numer. Math.**36**(1980/81), no. 3, 291–307. MR**613070**, DOI 10.1007/BF01396656 - 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 - Gene H. Golub and Urs von Matt,
*Quadratically constrained least squares and quadratic problems*, Numer. Math.**59**(1991), no. 6, 561–580. MR**1124128**, DOI 10.1007/BF01385796 - 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 - 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 - Susan L. Handy and Jesse L. Barlow,
*Numerical solution of the eigenproblem for banded, symmetric Toeplitz matrices*, SIAM J. Matrix Anal. Appl.**15**(1994), no. 1, 205–214. MR**1257630**, DOI 10.1137/S0895479891196673 - Richard J. Hanson and James L. Phillips,
*An adaptive numerical method for solving linear Fredholm integral equations of the first kind*, Numer. Math.**24**(1975), no. 4, 291–307. MR**403269**, DOI 10.1007/BF01397370 - 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, Department of EECS, University of California at Berkeley. (LAPACK working note No. 93).
- A. Melman,
*Numerical solution of a secular equation*, Numer. Math.**69**(1995), no. 4, 483–493. MR**1314599**, DOI 10.1007/s002110050104 - Christian H. Reinsch,
*Smoothing by spline functions. I, II*, Numer. Math.**10**(1967), 177–183; ibid. 16 (1970/71), 451–454. MR**295532**, DOI 10.1007/BF02162161 - Christian H. Reinsch,
*Smoothing by spline functions. I, II*, Numer. Math.**10**(1967), 177–183; ibid. 16 (1970/71), 451–454. MR**295532**, DOI 10.1007/BF02162161 - von Matt, U. (1993): Large constrained quadratic problems. Verlag der Fachvereine, Zürich.

## Additional Information

**A. Melman**- Affiliation: Department of Industrial Engineering and Management, Ben-Gurion University, Beer-Sheva 84105, Israel
- MR Author ID: 293268
- Email: melman@bgumail.bgu.ac.il
- Received by editor(s): February 12, 1995
- Received by editor(s) in revised form: November 13, 1995
- © Copyright 1997 American Mathematical Society
- Journal: Math. Comp.
**66**(1997), 333-344 - MSC (1991): Primary 65F15, 65H05
- DOI: https://doi.org/10.1090/S0025-5718-97-00787-4
- MathSciNet review: 1370854