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

Melman, A.

doi:10.1090/S0025-5718-97-00787-4

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.