|
A unifying convergence analysis of second-order methods for secular equations
Author:
A. Melman
Journal:
Math. Comp. 66 (1997), 333-344
MSC (1991):
Primary 65F15, 65H05
MathSciNet review:
1370854
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
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.
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
(89c:15028), http://dx.doi.org/10.1137/0609004
- 2.
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
(94k:65051)
- 3.
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 (80g:65038), http://dx.doi.org/10.1007/BF01396012
- 4.
James
R. Bunch and Christopher
P. Nielsen, Updating the singular value decomposition, Numer.
Math. 31 (1978/79), no. 2, 111–129. MR 509670
(80m:65025), http://dx.doi.org/10.1007/BF01397471
- 5.
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
(93e:65091), http://dx.doi.org/10.1007/BF02074882
- 6.
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
(82d:65038), http://dx.doi.org/10.1007/BF01396757
- 7.
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
(88f:65054), http://dx.doi.org/10.1137/0908018
- 8.
V.
N. Faddeeva, Computational methods of linear algebra, Dover
Publications Inc., New York, 1959. MR 0100344
(20 #6777)
- 9.
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 0195250
(33 #3453)
- 10.
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
(89f:65040), http://dx.doi.org/10.1137/0609018
- 11.
Walter
Gander, Least squares with a quadratic constraint, Numer.
Math. 36 (1980/81), no. 3, 291–307. MR 613070
(82c:65026), http://dx.doi.org/10.1007/BF01396656
- 12.
Walter
Gander, Gene
H. Golub, and Urs
von Matt, A constrained eigenvalue problem, Linear Algebra
Appl. 114/115 (1989), 815–839. MR 986908
(90e:15008), http://dx.doi.org/10.1016/0024-3795(89)90494-1
- 13.
Doron
Gill and Eitan
Tadmor, An 𝑂(𝑁²) method for computing the
eigensystem of 𝑁×𝑁 symmetric tridiagonal matrices by
the divide and conquer approach, SIAM J. Sci. Statist. Comput.
11 (1990), no. 1, 161–173. MR 1032233
(91d:65058), http://dx.doi.org/10.1137/0911010
- 14.
Gene
H. Golub, Some modified matrix eigenvalue problems, SIAM Rev.
15 (1973), 318–334. MR 0329227
(48 #7569)
- 15.
Gene
H. Golub and Urs
von Matt, Quadratically constrained least squares and quadratic
problems, Numer. Math. 59 (1991), no. 6,
561–580. MR 1124128
(92f:65049), http://dx.doi.org/10.1007/BF01385796
- 16.
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
(91h:65052), http://dx.doi.org/10.1007/BF01386438
- 17.
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
(96c:65057), http://dx.doi.org/10.1137/S089547989223924X
- 18.
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
(94j:65053), http://dx.doi.org/10.1137/S0895479891196673
- 19.
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 0403269
(53 #7081)
- 20.
Peter
Henrici, Elements of numerical analysis, John Wiley & Sons
Inc., New York, 1964. MR 0166900
(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.
A.
Melman, Numerical solution of a secular equation, Numer. Math.
69 (1995), no. 4, 483–493. MR 1314599
(95j:65050), http://dx.doi.org/10.1007/s002110050104
- 23.
Christian
H. Reinsch, Smoothing by spline functions. I, II, Numer. Math.
10 (1967), 177–183; ibid. 16 (1970/71),
451–454. MR 0295532
(45 #4598)
- 24.
Christian
H. Reinsch, Smoothing by spline functions. I, II, Numer. Math.
10 (1967), 177–183; ibid. 16 (1970/71),
451–454. MR 0295532
(45 #4598)
- 25.
von Matt, U. (1993): Large constrained quadratic problems. Verlag der Fachvereine, Zürich.
- 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  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.
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
65F15,
65H05
Retrieve articles in all journals
with MSC (1991):
65F15,
65H05
Additional Information
A. Melman
Affiliation:
Department of Industrial Engineering and Management, Ben-Gurion University, Beer-Sheva 84105, Israel
Email:
melman@bgumail.bgu.ac.il
DOI:
http://dx.doi.org/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
Article copyright:
© Copyright 1997 American Mathematical Society
|
