×

Convergence factors of Newton methods for nonlinear eigenvalue problems. (English) Zbl 1250.65072

Author’s abstract: Consider a complex sequence \(\{\lambda_k\}_{k=0}^{\infty}\) convergent to \(\lambda _{\ast }\in \mathbb{C}\) with order \(p\in N\). The convergence factor is typically defined as the fraction \(c_{k}:=(\lambda _{k+1}-\lambda _{\ast })/(\lambda _{k}-\lambda _{\ast })^{p}\) in the limit \(k\to \infty \). In this paper, we prove formulas characterizing \(c_{k}\) in the limit \(k\to \infty \) for two different Newton-type methods for nonlinear eigenvalue problems. The formulas are expressed in terms of the left and right eigenvectors.
The two treated methods are called the method of successive linear problems (MSLP) and augmented Newton and are widely used in the literature. We prove several explicit formulas for \(c_{k}\) for both methods. Formulas for both methods are found for simple as well as double eigenvalues. In some cases, we observe in examples that the limit \(c_{k}\) as k\(\to \infty \) does not exist. For cases where this limit does not appear to exist, we prove other limiting expressions such that a characterization of \(c_{k}\) in the limit is still possible.

MSC:

65H17 Numerical solution of nonlinear eigenvalue and eigenvector problems

Software:

DDE-BIFTOOL; NLEVP
Full Text: DOI

References:

[1] Anselone, P.; Rall, L., The solution of characteristic value-vector problems by Newton’s method, Numer. Math., 11, 38-45 (1968) · Zbl 0162.46602
[2] T. Betcke, N.J. Higham, V. Mehrmann, C. Schröder, F. Tisseur, NLEVP: a collection of nonlinear eigenvalue problems, Tech. Rep., Manchester Institute for Mathematical Sciences, 2008.; T. Betcke, N.J. Higham, V. Mehrmann, C. Schröder, F. Tisseur, NLEVP: a collection of nonlinear eigenvalue problems, Tech. Rep., Manchester Institute for Mathematical Sciences, 2008. · Zbl 1295.65140
[3] Betcke, T.; Voss, H., A Jacobi-Davidson type projection method for nonlinear eigenvalue problems, Future Gener. Comput. Systems, 20, 3, 363-372 (2004)
[4] Engelborghs, K.; Luzyanina, T.; Roose, D., Numerical bifurcation analysis of delay differential equations using DDE-BIFTOOL, ACM Trans. Math. Software, 28, 1, 1-24 (2002) · Zbl 1070.65556
[5] Freitag, M.; Spence, A., Convergence of inexact inverse iteration with application to preconditioned iterative solves, BIT, 47, 27-44 (2007) · Zbl 1121.65038
[6] Gohberg, I.; Lancaster, P.; Rodman, L., Matrix Polynomials (1982), Academic Press · Zbl 0482.15001
[7] Hryniv, R.; Lancaster, P., On the perturbation of analytic matrix functions, Integral Equations Operator Theory, 34, 3, 325-338 (1999) · Zbl 0940.47008
[8] Ipsen, I. C.F., Computing an eigenvector with inverse iteration, SIAM Rev., 39, 2, 254-291 (1997) · Zbl 0874.65029
[9] Jain, N. K.; Singhal, K., On Kublanovskaya’s approach to the solution of the generalized latent value problem for functional lambda-matrices, SIAM J. Numer. Anal., 20, 1062-1070 (1983) · Zbl 0528.65019
[10] E. Jarlebring, The spectrum of delay-differential equations: numerical methods, stability and perturbation, Ph.D. Thesis, TU Braunschweig, 2008.; E. Jarlebring, The spectrum of delay-differential equations: numerical methods, stability and perturbation, Ph.D. Thesis, TU Braunschweig, 2008. · Zbl 1183.34001
[11] Jarlebring, E.; Michiels, W., Invariance properties in the root sensitivity of time-delay systems with double imaginary roots, Automatica, 46, 1112-1115 (2010) · Zbl 1191.93049
[12] Kressner, D., A block Newton method for nonlinear eigenvalue problems, Numer. Math., 114, 2, 355-372 (2009) · Zbl 1191.65054
[13] Kublanovskaya, V., On an approach to the solution of the generalized latent value problem for \(\lambda \)-matrices, SIAM J. Numer. Anal., 7, 532-537 (1970) · Zbl 0225.65048
[14] Lancaster, P., A generalized Rayleigh quotient iteration for lambda-matrices, Arch. Ration. Mech. Anal., 8, 309-322 (1961) · Zbl 0105.31705
[15] Lancaster, P., Lambda-matrices and Vibrating Systems (2002), Dover Publications: Dover Publications Mineola, NY · Zbl 1048.34002
[16] Li, R.-C., Compute multiply nonlinear eigenvalues, J. Comput. Math., 10, 1, 1-20 (1992) · Zbl 0752.65042
[17] Mehrmann, V.; Voss, H., Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods, GAMM Mitt., 27, 121-152 (2004) · Zbl 1071.65074
[18] Michiels, W.; Niculescu, S.-I., Stability and stabilization of time-delay systems: an eigenvalue-based approach, (Advances in Design and Control, vol. 12 (2007), SIAM Publications: SIAM Publications Philadelphia) · Zbl 1052.93029
[19] Neumaier, A., Residual inverse iteration for the nonlinear eigenvalue problem, SIAM J. Numer. Anal., 22, 914-923 (1985) · Zbl 0594.65026
[20] J. Ortega, W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, 2000, ISBN: 0-89871-461-3.; J. Ortega, W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, 2000, ISBN: 0-89871-461-3. · Zbl 0949.65053
[21] Ostrowski, A., On the convergence of the Rayleigh quotient iteration for the computation of the characteristic roots and vectors. I, II, Arch. Ration. Mech. Anal., 1, 233-241 (1959) · Zbl 0083.12002
[22] Peters, G.; Wilkinson, J., Inverse iterations, ill-conditioned equations and Newton’s method, SIAM Rev., 21, 339-360 (1979) · Zbl 0424.65021
[23] Rall, L., A note on the convergence of Newton’s method, SIAM J. Numer. Anal., 11, 34-36 (1974) · Zbl 0239.65052
[24] Ruhe, A., Algorithms for the nonlinear eigenvalue problem, SIAM J. Numer. Anal., 10, 674-689 (1973) · Zbl 0261.65032
[25] K. Schreiber, Nonlinear eigenvalue problems: Newton-type methods and nonlinear Rayleigh functionals, Ph.D. Thesis, TU Berlin, 2008.; K. Schreiber, Nonlinear eigenvalue problems: Newton-type methods and nonlinear Rayleigh functionals, Ph.D. Thesis, TU Berlin, 2008. · Zbl 1213.65064
[26] Schröder, J., Über das Newtonsche Verfahren, Arch. Ration. Mech. Anal., 1, 154-180 (1957) · Zbl 0079.13605
[27] H. Schwetlick, K. Schreiber, A primal-dual Jacobi-Davidson-like method for nonlinear eigenvalue problems, Tech. Rep. ZIH-IR-0613, Techn. Univ. Dresden, Zentrum für Informationsdienste und Hochleistungsrechnen, 2006, pp. 1-20.; H. Schwetlick, K. Schreiber, A primal-dual Jacobi-Davidson-like method for nonlinear eigenvalue problems, Tech. Rep. ZIH-IR-0613, Techn. Univ. Dresden, Zentrum für Informationsdienste und Hochleistungsrechnen, 2006, pp. 1-20.
[28] Sleijpen, G. L.; Booten, A. G.; Fokkema, D. R.; van der Vorst, H. A., Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT, 36, 3, 595-633 (1996) · Zbl 0861.65035
[29] Tisseur, F.; Meerbergen, K., The quadratic eigenvalue problem, SIAM Rev., 43, 2, 235-286 (2001) · Zbl 0985.65028
[30] Unger, H., Nichtlineare Behandlung von Eigenwertaufgaben, Z. Angew. Math. Mech., 30, 281-282 (1950), English Trans. Available from: <http://www.math.tu-dresden.de/∼schwetli/Unger.html> · Zbl 0040.06602
[31] H. Voss, Numerical methods for sparse nonlinear eigenvalue problems, in: Proceedings of the XVth Summer School on Software and Algorithms of Numerical Mathematics, Hejnice, Czech Republic, 2004, Report 70, Arbeitsbereich Mathematik, TU Hamburg-Harburg.; H. Voss, Numerical methods for sparse nonlinear eigenvalue problems, in: Proceedings of the XVth Summer School on Software and Algorithms of Numerical Mathematics, Hejnice, Czech Republic, 2004, Report 70, Arbeitsbereich Mathematik, TU Hamburg-Harburg.
[32] Yang, W. H., A method for eigenvalues of sparse lambda-matrices, Int. J. Numer. Methods Eng., 19, 943-948 (1983) · Zbl 0517.65018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.