Mathematics of Computation

Author(s): A. Melman.
Journal: Math. Comp. 66 (1997), 333-344.
MSC (1991): Primary 65F15, 65H05
Retrieve article in: PDF
This article is available free of charge

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.

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

A. Melman
Affiliation: Department of Industrial Engineering and Management, Ben-Gurion University, Beer-Sheva 84105, Israel
Email: melman@bgumail.bgu.ac.il

DOI: 10.1090/S0025-5718-97-00787-4
PII: S 0025-5718(97)00787-4
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
Copyright of article: Copyright 1997, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS