Nonlinear eigenproblem

In mathematics, a nonlinear eigenproblem, sometimes nonlinear eigenvalue problem, is a generalization of the (ordinary) eigenvalue problem to equations that depend nonlinearly on the eigenvalue. Specifically, it refers to equations of the form

[math]\displaystyle{ M (\lambda) x = 0 , }[/math]

where [math]\displaystyle{ x\neq0 }[/math] is a vector, and [math]\displaystyle{ M }[/math] is a matrix-valued function of the number [math]\displaystyle{ \lambda }[/math]. The number [math]\displaystyle{ \lambda }[/math] is known as the (nonlinear) eigenvalue, the vector [math]\displaystyle{ x }[/math] as the (nonlinear) eigenvector, and [math]\displaystyle{ (\lambda,x) }[/math] as the eigenpair. The matrix [math]\displaystyle{ M (\lambda) }[/math] is singular at an eigenvalue [math]\displaystyle{ \lambda }[/math].

Definition

In the discipline of numerical linear algebra the following definition is typically used.^[1][2][3][4]

Let [math]\displaystyle{ \Omega \subseteq \Complex }[/math], and let [math]\displaystyle{ M : \Omega \rightarrow \Complex^{n\times n} }[/math] be a function that maps scalars to matrices. A scalar [math]\displaystyle{ \lambda \in \Complex }[/math] is called an eigenvalue, and a nonzero vector [math]\displaystyle{ x \in \Complex^n }[/math]is called a right eigevector if [math]\displaystyle{ M (\lambda) x = 0 }[/math]. Moreover, a nonzero vector [math]\displaystyle{ y \in \Complex^n }[/math]is called a left eigevector if [math]\displaystyle{ y^H M (\lambda) = 0^H }[/math], where the superscript [math]\displaystyle{ ^H }[/math] denotes the Hermitian transpose. The definition of the eigenvalue is equivalent to [math]\displaystyle{ \det(M (\lambda)) = 0 }[/math], where [math]\displaystyle{ \det() }[/math] denotes the determinant.^[1]

The function [math]\displaystyle{ M }[/math] is usually required to be a holomorphic function of [math]\displaystyle{ \lambda }[/math] (in some domain [math]\displaystyle{ \Omega }[/math]).

In general, [math]\displaystyle{ M (\lambda) }[/math] could be a linear map, but most commonly it is a finite-dimensional, usually square, matrix.

Definition: The problem is said to be regular if there exists a [math]\displaystyle{ z\in\Omega }[/math] such that [math]\displaystyle{ \det(M (z)) \neq 0 }[/math]. Otherwise it is said to be singular.^[1][4]

Definition: An eigenvalue [math]\displaystyle{ \lambda }[/math] is said to have algebraic multiplicity [math]\displaystyle{ k }[/math] if [math]\displaystyle{ k }[/math] is the smallest integer such that the [math]\displaystyle{ k }[/math]th derivative of [math]\displaystyle{ \det(M (z)) }[/math] with respect to [math]\displaystyle{ z }[/math], in [math]\displaystyle{ \lambda }[/math] is nonzero. In formulas that [math]\displaystyle{ \left.\frac{d^k \det(M (z))}{d z^k} \right|_{z=\lambda} \neq 0 }[/math] but [math]\displaystyle{ \left.\frac{d^\ell \det(M (z))}{d z^\ell} \right|_{z=\lambda} = 0 }[/math] for [math]\displaystyle{ \ell=0,1,2,\dots, k-1 }[/math].^[1][4]

Definition: The geometric multiplicity of an eigenvalue [math]\displaystyle{ \lambda }[/math] is the dimension of the nullspace of [math]\displaystyle{ M (\lambda) }[/math].^[1][4]

Special cases

The following examples are special cases of the nonlinear eigenproblem.

• The (ordinary) eigenvalue problem: [math]\displaystyle{ M (\lambda) = A-\lambda I. }[/math]
• The generalized eigenvalue problem: [math]\displaystyle{ M (\lambda) = A-\lambda B. }[/math]
• The quadratic eigenvalue problem: [math]\displaystyle{ M (\lambda) = A_0 + \lambda A_1 + \lambda^2 A_2. }[/math]
• The polynomial eigenvalue problem: [math]\displaystyle{ M (\lambda) = \sum_{i=0}^m \lambda^i A_i. }[/math]
• The rational eigenvalue problem: [math]\displaystyle{ M (\lambda) = \sum_{i=0}^{m_1} A_i \lambda^i + \sum_{i=1}^{m_2} B_i r_i(\lambda), }[/math] where [math]\displaystyle{ r_i(\lambda) }[/math] are rational functions.
• The delay eigenvalue problem: [math]\displaystyle{ M (\lambda) = -I\lambda + A_0 +\sum_{i=1}^m A_i e^{-\tau_i \lambda}, }[/math] where [math]\displaystyle{ \tau_1,\tau_2,\dots,\tau_m }[/math] are given scalars, known as delays.

Jordan chains

Definition: Let [math]\displaystyle{ (\lambda_0,x_0) }[/math] be an eigenpair. A tuple of vectors [math]\displaystyle{ (x_0,x_1,\dots, x_{r-1})\in\Complex^n\times\Complex^n\times\dots\times\Complex^n }[/math] is called a Jordan chain if[math]\displaystyle{ \sum_{k=0}^{\ell} M^{(k)} (\lambda_0) x_{\ell - k} = 0 , }[/math]for [math]\displaystyle{ \ell = 0,1,\dots , r-1 }[/math], where [math]\displaystyle{ M^{(k)}(\lambda_0) }[/math] denotes the [math]\displaystyle{ k }[/math]th derivative of [math]\displaystyle{ M }[/math] with respect to [math]\displaystyle{ \lambda }[/math] and evaluated in [math]\displaystyle{ \lambda=\lambda_0 }[/math]. The vectors [math]\displaystyle{ x_0,x_1,\dots, x_{r-1} }[/math] are called generalized eigenvectors, [math]\displaystyle{ r }[/math] is called the length of the Jordan chain, and the maximal length a Jordan chain starting with [math]\displaystyle{ x_0 }[/math] is called the rank of [math]\displaystyle{ x_0 }[/math].^[1][4]

Theorem:^[1] A tuple of vectors [math]\displaystyle{ (x_0,x_1,\dots, x_{r-1})\in\Complex^n\times\Complex^n\times\dots\times\Complex^n }[/math] is a Jordan chain if and only if the function [math]\displaystyle{ M(\lambda) \chi_\ell (\lambda) }[/math] has a root in [math]\displaystyle{ \lambda=\lambda_0 }[/math] and the root is of multiplicity at least [math]\displaystyle{ \ell }[/math] for [math]\displaystyle{ \ell=0,1,\dots,r-1 }[/math], where the vector valued function [math]\displaystyle{ \chi_\ell (\lambda) }[/math] is defined as[math]\displaystyle{ \chi_\ell(\lambda) = \sum_{k=0}^\ell x_k (\lambda-\lambda_0)^k. }[/math]

Mathematical software

• The eigenvalue solver package SLEPc contains C-implementations of many numerical methods for nonlinear eigenvalue problems.^[5]
• The NLEVP collection of nonlinear eigenvalue problems is a MATLAB package containing many nonlinear eigenvalue problems with various properties. ^[6]
• The FEAST eigenvalue solver is a software package for standard eigenvalue problems as well as nonlinear eigenvalue problems, designed from density-matrix representation in quantum mechanics combined with contour integration techniques.^[7]
• The MATLAB toolbox NLEIGS contains an implementation of fully rational Krylov with a dynamically constructed rational interpolant.^[8]
• The MATLAB toolbox CORK contains an implementation of the compact rational Krylov algorithm that exploits the Kronecker structure of the linearization pencils.^[9]
• The MATLAB toolbox AAA-EIGS contains an implementation of CORK with rational approximation by set-valued AAA.^[10]
• The MATLAB toolbox RKToolbox (Rational Krylov Toolbox) contains implementations of the rational Krylov method for nonlinear eigenvalue problems as well as features for rational approximation. ^[11]
• The Julia package NEP-PACK contains many implementations of various numerical methods for nonlinear eigenvalue problems, as well as many benchmark problems.^[12]
• The review paper of Güttel & Tisseur^[1] contains MATLAB code snippets implementing basic Newton-type methods and contour integration methods for nonlinear eigenproblems.

Eigenvector nonlinearity

Eigenvector nonlinearities is a related, but different, form of nonlinearity that is sometimes studied. In this case the function [math]\displaystyle{ M }[/math] maps vectors to matrices, or sometimes hermitian matrices to hermitian matrices.^[13][14]

References

Further reading

• Françoise Tisseur and Karl Meerbergen, "The quadratic eigenvalue problem," SIAM Review 43 (2), 235–286 (2001) (link).
• Gene H. Golub and Henk A. van der Vorst, "Eigenvalue computation in the 20th century," Journal of Computational and Applied Mathematics 123, 35–65 (2000).
• Philippe Guillaume, "Nonlinear eigenproblems," SIAM Journal on Matrix Analysis and Applications 20 (3), 575–595 (1999) (link).
• Cedric Effenberger, "Robust solution methods fornonlinear eigenvalue problems", PhD thesis EPFL (2013) (link)
• Roel Van Beeumen, "Rational Krylov methods fornonlinear eigenvalue problems", PhD thesis KU Leuven (2015) (link)

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Nonlinear eigenproblem. Read more