engleski

Robust numerical methods for nonlinear eigenvalue problems

In this thesis we study numerical methods for solving nonlinear eigenvalue problems of polynomial type. In particular, we are interested in the quadratic (k=2) and the quartic (k=4) eigenvalue problems. The methods are based on the corresponding linearization – the nonlinear problem is replaced with an equivalent linear problem of the type (A−λB)y=0, of dimension kn. We propose several modifications and improvements of the existing methods for both the complete and partial solution ; this results in new numerical algorithms that are a substantial improvement over the existing ones. In particular, as an improvement of the state of the art quadeig method of Hammarling, Munro and Tisseur, we develop a scheme to deflate all zero and infinite eigenvalues before calling the QZ algorithm for the linear problem. This provides numerically more robust procedure, which we illustrate by numerical examples. Further, we supplement the parameter scaling (designed to equilibrate the norms of the coefficient matrices) with a two– sided diagonal scaling to nearly equilibrate (in modulus) the nonzero matrix entries. In addition, we analyze the fine details of the rank revealing factorization used in the deflation process. We advocate to use complete pivoting in the QR factorization, and we also propose a LU based approach, which is shown to be competitive, or even better than the one based on the QR factorization. The new method is extended to the quartic problem. For the partial quadratic eigenvalue problem (computing only a part of the spectrum), the iterative Arnoldi–like methods are studied, especially the implicitly restarted two level orthogonal Arnoldi algorithm (TOAR). We propose several improvements of the method. In particular, new shift selection strategy is proposed for the implicit restart for the class of overdamped quadratic eigenvalue problems. Also, we show the benefit of choosing the starting vector for TOAR, based on spectral information of a nearby proportionally damped pencil. Finally, we provide some new ideas for the development of a Krylov–Schur like methods that is capable of using arbitrary polynomial filters in the implicit restarting.

polynomial eigenvalue problem ; quadratic eigenvalue problem ; quartic eigenvalue problem ; projection method ; Arnoldi like method ; linearization ; QZ ; quadeig ; deflation ; rank determination ; normwise backward error ; componentwise backward error ; TOAR ; SOAR

nije evidentirano