Summary
Using a new technique we derive sharp quadratic convergence bounds for the serial symmetric and SVD Jacobi methods. For the symmetric Jacobi method we consider the cases of well and poorely separated eigenvalues. Our result implies the result proposed, but not correctly proved, by Van Kempen. It also extends the well-known result of Wilkinson to the case of multiple eigenvalues.
Similar content being viewed by others
References
Brent, R.P., Luk, F.T. (1985): The Solution of Singular-value and Symmetric Eigenvalue Problems on Multiprocessor Arrays. SIAM J. Sci. Stat. Comput.6, 69–84
Charlier, J.-P., Vanbegin, M., Van Dooren, P. (1988): On Efficient Implementations of Kogbetliantz's Algorithm for Computing the Singular Value Decomposition. Numer. Math.52, 279–300
Charlier, J.-P., Van Dooren, P. (1987): On Kogbetliantz's SVD Algorithm in the Presence of Clusters. Linear Algebra Appl.95, 135–160
Drmač, Z., Hari, V. (1991): On the Quadratic Convergence Bounds for the Serial J-symmetric Jacobi Method. Technical Report. University of Zagreb
Vince Fernando, K. (1989): Linear Convergence of the Row Cyclic Jacobi and Kogbetliantz Methods. Numer. Math.56, 71–91
Hansen, E.R. (1960): On Jacobi Methods and Block Jacobi Methods for Computing Matrix Eigenvalues. Stanford University
Hansen, E.R. (1963): On Cyclic Jacobi Methods. SIAM J. Appl. Math.11, 449–459
Hari, V. (1986): On the Quadratic Convergence of Jacobi Algorithms Radovi Mathematički2, 127–146
Hari, V., Veselić, K. (1987): On Jacobi Methods for Singular Value Decompositions. SIAM J. Sci. Stat. Comput.8, 741–754
Hari, V. (1989): On the Quadratic Convergence of the Serial SVD Jacobi Methods for Triangular Matrices. SIAM J. Sci. Stat. Comput.10, 1076–1096
Hari, V.: On Pairs of Almost Diagonal Matrices. Linear Algebra Appl. (to appear)
Van Kempen, H.P.M. (1966): On the Quadratic Convergence of the Special Cyclic Jacobi Method. Numer. Math.9, 19–22
Kogbetliantz, E. (1954): Diagonalization of General Complex Matrices as a New Method for Solution of Linear Equations. Proc. Intern. Congr. Math. Amsterdam2, 356–357
Kogbetliantz, E. (1955): Solutions of Linear Equations by Diagonalization of Coefficient Matrices. Quart. Appl. Math.13, 123–132
Luk, F.T. (1986): A Triangular Processor Array for Computing Singular Values. Linear Algebra Appl.77, 259–273
Luk, F.T., Park, H. (1989): On Parallel Jacobi Orderings. SIAM J. Sci. Statist. Comput.10, 18–26
Luk, F.T., Park, H. (1989): A Proof of Convergence for Two Parallel Jacobi SVD Algorithms. IEEE Trans. Comput.38, 806–811
Paige, C.C., Van Dooren, P. (1986): On the Quadratic Convergence of Kogbetliantz's Algorithm for Computing the Singular Value Decomposition. Linear Algebra Appl.77, 301–313
Parlett, B.N. (1980): The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs, N.J.
Rhee, N., Hari, V. (1990): On the Global and Cubic Convergence of a Quasi-cyclic Jacobi Method. Technical Report, University of Missouri in Kansas City, 90–1
Ruhe, A. (1967): On the Quadratic Convergence of the Jacobi Method for Normal Matrices. BIT7, 305–313
Veselić, K. (1990): An Eigenreduction Algorithm for Definite Matrix Pairs and its Applications to Overdamped Linear Systems. Technical Report, University of Hagen
Wilkinson, J.H. (1962): Note on the Quadratic Convergence of the Cyclic Jacobi Process. Numer. Math.4, 296–300
Wilkinson, J.H. (1968): Almost Diagonal Matrices with Multiple or Close Eigenvalues. Linear Algebra Appl.1, 1–12
Golub, G.H., Van Loan, C.F. (1989): Matrix Computations. The Johns Hopkins University Press, 2nd ed. Baltimore, Md.
Author information
Authors and Affiliations
Additional information
This work was supported in part by the U.S. Army. Contract DAAL03-89-C-0038
Rights and permissions
About this article
Cite this article
Hari, V. On sharp quadratic convergence bounds for the serial Jacobi methods. Numer. Math. 60, 375–406 (1991). https://doi.org/10.1007/BF01385728
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01385728