Remarks on some Newton and Chebyshev-type methods for approximation eigenvalues and eigenvectors of matrices

Abstract

We consider a square matrix \(A\) with real or complex elements. We denote \(\mathbb{K}=\mathbb{R}\) or \(\mathbb{C}\) and we are interested in computing \(\lambda \in \mathbb{K}\) such that there exists \(v\in \mathbb{K}^{n}\) such that \(Av-\lambda v=0\), i.e. we are interested in computing the eigenpairs (eigenvalue +eigenvector) of the matrix \(A\). In this sense, we consider the nonlinear system of equations \(F(x) =0\), where \(F(x) =\)\({Av-\lambda v}\choose{Gv-1}\), where \(G\) is a convenient mapping.

In order to solve this system we consider the Newton and the Chebyshev methods, and at each iteration step, the order 1 derivative is approximated by the Schultz method; such an approach does not require the solving of a linear system at each step.

We conditions for local convergence and errors evaluations for the r-convergence order.

Authors

Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)

Emil Cătinaş
(Tiberiu Popoviciu Institute of Numerical Analysis)

Keywords

eigenvalue and eigenvector of square matrix; eigenpair; Newton method; Chebyshev method; Schultz method; local convergence theorem; error estimation; linear systems solving-free iterative methods; r-convergence order.

Cite this paper as:

I. Păvăloiu, E. Cătinaş, Remarks on some Newton and Chebyshev-type methods for approximation eigenvalues and eigenvectors of matrices, Comput. Sci. J. Mold., 7 (1999) no. 1, pp. 3-15.

PDF

PDF here.

Latex version of the paper (soon).

About this paper

Print ISSN

1561-4042

Online ISSN

Not available yet.

Print ISSN

1561-4042

Online ISSN

Not available yet.

Google Scholar citations

[1] M.P. Anselone and L.B. Rall, The solution of characteristic value-vector problems by Newton method, Numer. Math., 11 (1968), pp. 38-45.

[2] E. Catinas and I. Pavaloiu, On the Chebyshev method for approximating the eigenvalues of linear operators, Rev. Anal. Numer. Theor. Approx. 25 (1996) 1-2, pp. 43-56.
Post

[3] E. Catinas and I. Pavaloiu, On the Chebyshev Method for Approximating the Eigenvalues of Linear Operators, Proceedings of International Conference on Approximation and Optimization, ClujNapoca, July 29 – August 1, 1996, Vol. 1, pp. 219-226.

[4] E. Catinas and I. Pavaloiu, On Approximating the Eigenvalues and Eigenvectors of Linear Continuous Operators, Rev. Anal. Numer. Theor. Approx. 25 (1996) 1-2, pp. 43-56.
post

[5] F. Chatelin, Valeurs propres de matrices, Mason, Paris, 1988.

[6] L. Collatz, Functionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, 1964.

[7] A. Diaconu and I. Pavaloiu, Sur quelque methodes iteratives pour la resolution des equations operationelles, Rev. Anal. Numer. Theor. Approx. 1, 1 (1972), pp. 45-61.

[8] A. Diaconu, On the Convergence of an Iterative Method of Chebyshev Type, Rev. Anal. Numer. Theor. Approx., 24 (1995) 1-2, pp. 91-102.

[9] J.J. Dongarra, C.B. Moler and J.H. Wilkinson, Improving the Accuracy of the Computed Eigenvalues and Eigenvectors, SIAM J. Numer. Anal., 20 (1983) no. 1, pp. 23-45.

[10] S.M. Grzegorski, On the Scaled Newton Method for the Symmetric Eigenvalue Problem, Computing, 45 (1990), pp. 277-282.

[11] V. S. Kartisov and F. L. Iuhno, O nekotorıh Modifikatiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci, J. Vicisl. matem. i matem. fiz. 33 (1973) 9, pp. 1403-1409.

[12] J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970.

[13] I. Pavaloiu, Sur les procedes iteratifs a un ordre eleve de convergence, Mathematica (Cluj) 12 (35) (1970) 2, pp. 309-324.

[14] I. Pavaloiu, Introduction to the Approximation Theory for the Solutions of Equations, Ed. Dacia, Cluj-Napoca, 1986 (in Romanian).

[15] I. Pavaloiu, Observations concerning some Approximation Methods for the Solutions of Operator Equations, Rev. Anal. Numer. Theor. Approx., 23 (1994) 2, pp. 185-196.

[16] G. Peters and J.H. Wilkinson, Inverse Iteration, Ill-Conditioned Equations and Newton’s Method, SIAM Review, 21 (1979) no. 3, pp. 339-360.

[17] M.C. Santos, A Note on the Newton Iteration for the Algebraic Eigenvalue Problem, SIAM J. Matrix Anal. Appl., 9 (1988) no. 4, pp. 561-569.

[18] R.A. Tapia and L.D. Whitley, The Projected Newton Method has Order 1 + √2 for the Symmetric Eigenvalue Problem, SIAM J. Numer. Anal., 25 (1988) 6, pp. 1376-1382.

[19] S. Ul’m, On the Iterative Method with Simultaneous Approximation of the Inverse of the Operator, Izv. Acad. Nauk. Estonskoi S.S.R., 16 (1967) 4, pp. 403-411.

[20] K. Wu, Y. Saad and A. Stathopoulos, Inexact Newton Preconditioning Techniques for Eigenvalue Problems, Lawrence Berkeley National Laboratory report number 41382 and Minnesota Supercomputing Institute report number UMSI 98-10, 1998.

[21] T. Yamamoto, Error Bounds for Computed Eigenvalues and Eigenvectors, Numer. Math. 34 (1980), pp. 189-199.

1999

Related Posts