# Nonlinear eigenproblem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Nonlinear_eigenproblem
> Markdown URL: https://mediated.wiki/source/Nonlinear_eigenproblem.md
> Source: https://en.wikipedia.org/wiki/Nonlinear_eigenproblem
> Source revision: 1352953566
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Type of equation involving matrix-valued functions

In [mathematics](/source/Mathematics), a **nonlinear eigenproblem**, sometimes **nonlinear eigenvalue problem**, is a generalization of the (ordinary) [eigenvalue problem](/source/Eigenvalue%2C_eigenvector_and_eigenspace) to equations that depend [nonlinearly](/source/Nonlinearly) on the eigenvalue. Specifically, it refers to equations of the form

M ( λ ) x = 0 , {\displaystyle M(\lambda )x=0,}

where x ≠ 0 {\displaystyle x\neq 0} is a [vector](/source/Vector_(mathematics)), and *M {\displaystyle M}* is a [matrix](/source/Matrix_(mathematics))-valued [function](/source/Function_(mathematics)) of the number λ {\displaystyle \lambda } . The number λ {\displaystyle \lambda } is known as the (nonlinear) **eigenvalue**, the vector x {\displaystyle x} as the (nonlinear) **eigenvector**, and ( λ , x ) {\displaystyle (\lambda ,x)} as the **eigenpair**. The matrix M ( λ ) {\displaystyle M(\lambda )} is singular at an eigenvalue λ {\displaystyle \lambda } .

## Definition

In the discipline of [numerical linear algebra](/source/Numerical_linear_algebra) the following definition is typically used.[1][2][3][4]

Let Ω ⊆ C {\displaystyle \Omega \subseteq \mathbb {C} } , and let M : Ω → C n × n {\displaystyle M:\Omega \rightarrow \mathbb {C} ^{n\times n}} be a function that maps scalars to matrices. A scalar λ ∈ C {\displaystyle \lambda \in \mathbb {C} } is called an *eigenvalue*, and a nonzero vector x ∈ C n {\displaystyle x\in \mathbb {C} ^{n}} is called a *right eigenvector* if M ( λ ) x = 0 {\displaystyle M(\lambda )x=0} . Moreover, a nonzero vector y ∈ C n {\displaystyle y\in \mathbb {C} ^{n}} is called a *left eigenvector* if y H M ( λ ) = 0 H {\displaystyle y^{H}M(\lambda )=0^{H}} , where the superscript H {\displaystyle ^{H}} denotes the [Hermitian transpose](/source/Hermitian_Transpose). The definition of the eigenvalue is equivalent to det ( M ( λ ) ) = 0 {\displaystyle \det(M(\lambda ))=0} , where det ( ) {\displaystyle \det()} denotes the [determinant](/source/Determinant).[1]

The function *M {\displaystyle M}* is usually required to be a [holomorphic function](/source/Holomorphic_function) of λ {\displaystyle \lambda } (in some [domain](/source/Domain_(mathematical_analysis)) Ω {\displaystyle \Omega } ).

In general, M ( λ ) {\displaystyle M(\lambda )} could be a [linear map](/source/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 z ∈ Ω {\displaystyle z\in \Omega } such that det ( M ( z ) ) ≠ 0 {\displaystyle \det(M(z))\neq 0} . Otherwise it is said to be *singular*.[1][4]

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

**Definition:** The *[geometric multiplicity](/source/Eigenvalues_and_eigenvectors#Eigenspaces,_geometric_multiplicity,_and_the_eigenbasis_for_matrices)* of an eigenvalue λ {\displaystyle \lambda } is the dimension of the [nullspace](/source/Nullspace) of M ( λ ) {\displaystyle M(\lambda )} .[1][4]

## Special cases

The following examples are special cases of the nonlinear eigenproblem.

- The (ordinary) [eigenvalue problem](/source/Eigenvalue%2C_eigenvector_and_eigenspace): M ( λ ) = A − λ I . {\displaystyle M(\lambda )=A-\lambda I.}

- [The generalized eigenvalue problem](/source/Eigendecomposition_of_a_matrix#Generalized_eigenvalue_problem): M ( λ ) = A − λ B . {\displaystyle M(\lambda )=A-\lambda B.}

- [The quadratic eigenvalue problem](/source/Quadratic_eigenvalue_problem): M ( λ ) = A 0 + λ A 1 + λ 2 A 2 . {\displaystyle M(\lambda )=A_{0}+\lambda A_{1}+\lambda ^{2}A_{2}.}

- The polynomial eigenvalue problem: M ( λ ) = ∑ i = 0 m λ i A i . {\displaystyle M(\lambda )=\sum _{i=0}^{m}\lambda ^{i}A_{i}.}

- The rational eigenvalue problem: M ( λ ) = ∑ i = 0 m 1 A i λ i + ∑ i = 1 m 2 B i r i ( λ ) , {\displaystyle M(\lambda )=\sum _{i=0}^{m_{1}}A_{i}\lambda ^{i}+\sum _{i=1}^{m_{2}}B_{i}r_{i}(\lambda ),} where r i ( λ ) {\displaystyle r_{i}(\lambda )} are [rational functions](/source/Rational_function).

- [The delay eigenvalue problem](/source/Delay_differential_equation#The_characteristic_equation): M ( λ ) = − I λ + A 0 + ∑ i = 1 m A i e − τ i λ , {\displaystyle M(\lambda )=-I\lambda +A_{0}+\sum _{i=1}^{m}A_{i}e^{-\tau _{i}\lambda },} where τ 1 , τ 2 , … , τ m {\displaystyle \tau _{1},\tau _{2},\dots ,\tau _{m}} are given scalars, known as delays.

## Jordan chains

**Definition:** Let ( λ 0 , x 0 ) {\displaystyle (\lambda _{0},x_{0})} be an eigenpair. A [tuple](/source/Tuple) of vectors ( x 0 , x 1 , … , x r − 1 ) ∈ C n × C n × ⋯ × C n {\displaystyle (x_{0},x_{1},\dots ,x_{r-1})\in \mathbb {C} ^{n}\times \mathbb {C} ^{n}\times \dots \times \mathbb {C} ^{n}} is called a [*Jordan chain*](/source/Generalized_eigenvector#Jordan_chains) if ∑ k = 0 ℓ M ( k ) ( λ 0 ) x ℓ − k = 0 , {\displaystyle \sum _{k=0}^{\ell }M^{(k)}(\lambda _{0})x_{\ell -k}=0,} for ℓ = 0 , 1 , … , r − 1 {\displaystyle \ell =0,1,\dots ,r-1} , where M ( k ) ( λ 0 ) {\displaystyle M^{(k)}(\lambda _{0})} denotes the k {\displaystyle k} th [derivative](/source/Derivative) of M {\displaystyle M} with respect to λ {\displaystyle \lambda } and evaluated in λ = λ 0 {\displaystyle \lambda =\lambda _{0}} . The vectors x 0 , x 1 , … , x r − 1 {\displaystyle x_{0},x_{1},\dots ,x_{r-1}} are called [*generalized eigenvectors*](/source/Generalized_eigenvector), r {\displaystyle r} is called the *length* of the Jordan chain, and the maximal length a Jordan chain starting with x 0 {\displaystyle x_{0}} is called the *rank* of x 0 {\displaystyle x_{0}} .[1][4]

**Theorem:**[1] A tuple of vectors ( x 0 , x 1 , … , x r − 1 ) ∈ C n × C n × ⋯ × C n {\displaystyle (x_{0},x_{1},\dots ,x_{r-1})\in \mathbb {C} ^{n}\times \mathbb {C} ^{n}\times \dots \times \mathbb {C} ^{n}} is a Jordan chain if and only if the function M ( λ ) χ ℓ ( λ ) {\displaystyle M(\lambda )\chi _{\ell }(\lambda )} has a [root](/source/Zero_of_a_function) in λ = λ 0 {\displaystyle \lambda =\lambda _{0}} and the root is of [multiplicity](/source/Multiplicity_(mathematics)#Multiplicity_of_a_root_of_a_polynomial) at least ℓ {\displaystyle \ell } for ℓ = 0 , 1 , … , r − 1 {\displaystyle \ell =0,1,\dots ,r-1} , where the vector valued function χ ℓ ( λ ) {\displaystyle \chi _{\ell }(\lambda )} is defined as χ ℓ ( λ ) = ∑ k = 0 ℓ x k ( λ − λ 0 ) k . {\displaystyle \chi _{\ell }(\lambda )=\sum _{k=0}^{\ell }x_{k}(\lambda -\lambda _{0})^{k}.}

## Mathematical software

- The eigenvalue solver package [SLEPc](/source/SLEPc) contains C-implementations of many numerical methods for nonlinear eigenvalue problems.[5]

- The [NLEVP collection of nonlinear eigenvalue problems](https://github.com/ftisseur/nlevp) is a [MATLAB](/source/MATLAB) package containing many nonlinear eigenvalue problems with various properties. [6]

- The [FEAST eigenvalue solver](http://www.feast-solver.org/) is a software package for standard eigenvalue problems as well as nonlinear eigenvalue problems, designed from density-matrix representation in [quantum mechanics](/source/Quantum_mechanics) combined with contour integration techniques.[7]

- The [MATLAB](/source/MATLAB) toolbox [NLEIGS](https://bitbucket.org/roelvb/nleigs/) contains an implementation of fully rational Krylov with a dynamically constructed rational interpolant.[8]

- The [MATLAB](/source/MATLAB) toolbox [CORK](https://bitbucket.org/roelvb/cork/) contains an implementation of the compact rational Krylov algorithm that exploits the Kronecker structure of the linearization pencils.[9]

- The [MATLAB](/source/MATLAB) toolbox [AAA-EIGS](https://people.cs.kuleuven.be/~karl.meerbergen/files/aaa/autoCORK.zip) contains an implementation of CORK with rational approximation by set-valued AAA.[10]

- The [MATLAB](/source/MATLAB) toolbox [RKToolbox](http://guettel.com/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](/source/Julia_(programming_language)) package [NEP-PACK](https://nep-pack.github.io/NonlinearEigenproblems.jl/) 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](/source/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 M {\displaystyle M} maps vectors to matrices, or sometimes [hermitian matrices](/source/Hermitian_matrix) to hermitian matrices.[13][14]

## References

1. ^ [***a***](#cite_ref-:0_1-0) [***b***](#cite_ref-:0_1-1) [***c***](#cite_ref-:0_1-2) [***d***](#cite_ref-:0_1-3) [***e***](#cite_ref-:0_1-4) [***f***](#cite_ref-:0_1-5) [***g***](#cite_ref-:0_1-6) [***h***](#cite_ref-:0_1-7) Güttel, Stefan; [Tisseur, Françoise](/source/Fran%C3%A7oise_Tisseur) (2017). ["The nonlinear eigenvalue problem"](http://eprints.maths.manchester.ac.uk/2538/1/main.pdf) (PDF). *Acta Numerica*. **26**: 1–94. [doi](/source/Doi_(identifier)):[10.1017/S0962492917000034](https://doi.org/10.1017%2FS0962492917000034). [ISSN](/source/ISSN_(identifier)) [0962-4929](https://search.worldcat.org/issn/0962-4929). [S2CID](/source/S2CID_(identifier)) [46749298](https://api.semanticscholar.org/CorpusID:46749298).

1. **[^](#cite_ref-2)** Ruhe, Axel (1973). ["Algorithms for the Nonlinear Eigenvalue Problem"](https://epubs.siam.org/doi/10.1137/0710059). *SIAM Journal on Numerical Analysis*. **10** (4): 674–689. [Bibcode](/source/Bibcode_(identifier)):[1973SJNA...10..674R](https://ui.adsabs.harvard.edu/abs/1973SJNA...10..674R). [doi](/source/Doi_(identifier)):[10.1137/0710059](https://doi.org/10.1137%2F0710059). [ISSN](/source/ISSN_(identifier)) [0036-1429](https://search.worldcat.org/issn/0036-1429). [JSTOR](/source/JSTOR_(identifier)) [2156278](https://www.jstor.org/stable/2156278).

1. **[^](#cite_ref-3)** [Mehrmann, Volker](/source/Volker_Mehrmann); Voss, Heinrich (2004). ["Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods"](https://onlinelibrary.wiley.com/doi/abs/10.1002/gamm.201490007). *GAMM-Mitteilungen*. **27** (2): 121–152. [doi](/source/Doi_(identifier)):[10.1002/gamm.201490007](https://doi.org/10.1002%2Fgamm.201490007). [ISSN](/source/ISSN_(identifier)) [1522-2608](https://search.worldcat.org/issn/1522-2608). [S2CID](/source/S2CID_(identifier)) [14493456](https://api.semanticscholar.org/CorpusID:14493456).

1. ^ [***a***](#cite_ref-:1_4-0) [***b***](#cite_ref-:1_4-1) [***c***](#cite_ref-:1_4-2) [***d***](#cite_ref-:1_4-3) [***e***](#cite_ref-:1_4-4) Voss, Heinrich (2014). ["Nonlinear eigenvalue problems"](https://www.mat.tuhh.de/forschung/rep/rep174.pdf) (PDF). In [Hogben, Leslie](/source/Leslie_Hogben) (ed.). [*Handbook of Linear Algebra*](https://www.routledge.com/Handbook-of-Linear-Algebra/Hogben/p/book/9781138199897) (2 ed.). Boca Raton, FL: Chapman and Hall/CRC. [ISBN](/source/ISBN_(identifier)) [9781466507289](https://en.wikipedia.org/wiki/Special:BookSources/9781466507289).

1. **[^](#cite_ref-5)** Hernandez, Vicente; Roman, Jose E.; Vidal, Vicente (September 2005). "SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems". *ACM Transactions on Mathematical Software*. **31** (3): 351–362. [doi](/source/Doi_(identifier)):[10.1145/1089014.1089019](https://doi.org/10.1145%2F1089014.1089019). [S2CID](/source/S2CID_(identifier)) [14305707](https://api.semanticscholar.org/CorpusID:14305707).

1. **[^](#cite_ref-6)** Betcke, Timo; Higham, Nicholas J.; Mehrmann, Volker; Schröder, Christian; Tisseur, Françoise (February 2013). "NLEVP: A Collection of Nonlinear Eigenvalue Problems". *ACM Transactions on Mathematical Software*. **39** (2): 1–28. [doi](/source/Doi_(identifier)):[10.1145/2427023.2427024](https://doi.org/10.1145%2F2427023.2427024). [S2CID](/source/S2CID_(identifier)) [4271705](https://api.semanticscholar.org/CorpusID:4271705).

1. **[^](#cite_ref-7)** Polizzi, Eric (2020). "FEAST Eigenvalue Solver v4.0 User Guide". [arXiv](/source/ArXiv_(identifier)):[2002.04807](https://arxiv.org/abs/2002.04807) [[cs.MS](https://arxiv.org/archive/cs.MS)].

1. **[^](#cite_ref-8)** Güttel, Stefan; Van Beeumen, Roel; Meerbergen, Karl; Michiels, Wim (1 January 2014). "NLEIGS: A Class of Fully Rational Krylov Methods for Nonlinear Eigenvalue Problems". *SIAM Journal on Scientific Computing*. **36** (6): A2842–A2864. [Bibcode](/source/Bibcode_(identifier)):[2014SJSC...36A2842G](https://ui.adsabs.harvard.edu/abs/2014SJSC...36A2842G). [doi](/source/Doi_(identifier)):[10.1137/130935045](https://doi.org/10.1137%2F130935045).

1. **[^](#cite_ref-9)** Van Beeumen, Roel; Meerbergen, Karl; Michiels, Wim (2015). ["Compact rational Krylov methods for nonlinear eigenvalue problems"](https://lirias.kuleuven.be/handle/123456789/490706). *SIAM Journal on Matrix Analysis and Applications*. **36** (2): 820–838. [doi](/source/Doi_(identifier)):[10.1137/140976698](https://doi.org/10.1137%2F140976698). [S2CID](/source/S2CID_(identifier)) [18893623](https://api.semanticscholar.org/CorpusID:18893623).

1. **[^](#cite_ref-10)** Lietaert, Pieter; Meerbergen, Karl; Pérez, Javier; Vandereycken, Bart (13 April 2022). "Automatic rational approximation and linearization of nonlinear eigenvalue problems". *IMA Journal of Numerical Analysis*. **42** (2): 1087–1115. [arXiv](/source/ArXiv_(identifier)):[1801.08622](https://arxiv.org/abs/1801.08622). [doi](/source/Doi_(identifier)):[10.1093/imanum/draa098](https://doi.org/10.1093%2Fimanum%2Fdraa098).

1. **[^](#cite_ref-11)** Berljafa, Mario; Steven, Elsworth; Güttel, Stefan (15 July 2020). ["An overview of the example collection"](http://guettel.com/rktoolbox/examples/html/index.html#5). *index.m*. Retrieved 31 May 2022.

1. **[^](#cite_ref-12)** Jarlebring, Elias; Bennedich, Max; Mele, Giampaolo; Ringh, Emil; Upadhyaya, Parikshit (23 November 2018). "NEP-PACK: A Julia package for nonlinear eigenproblems". [arXiv](/source/ArXiv_(identifier)):[1811.09592](https://arxiv.org/abs/1811.09592) [[math.NA](https://arxiv.org/archive/math.NA)].

1. **[^](#cite_ref-13)** Jarlebring, Elias; Kvaal, Simen; Michiels, Wim (2014-01-01). ["An Inverse Iteration Method for Eigenvalue Problems with Eigenvector Nonlinearities"](https://epubs.siam.org/doi/10.1137/130910014). *SIAM Journal on Scientific Computing*. **36** (4): A1978–A2001. [arXiv](/source/ArXiv_(identifier)):[1212.0417](https://arxiv.org/abs/1212.0417). [Bibcode](/source/Bibcode_(identifier)):[2014SJSC...36A1978J](https://ui.adsabs.harvard.edu/abs/2014SJSC...36A1978J). [doi](/source/Doi_(identifier)):[10.1137/130910014](https://doi.org/10.1137%2F130910014). [ISSN](/source/ISSN_(identifier)) [1064-8275](https://search.worldcat.org/issn/1064-8275). [S2CID](/source/S2CID_(identifier)) [16959079](https://api.semanticscholar.org/CorpusID:16959079).

1. **[^](#cite_ref-14)** Upadhyaya, Parikshit; Jarlebring, Elias; Rubensson, Emanuel H. (2021). ["A density matrix approach to the convergence of the self-consistent field iteration"](https://doi.org/10.3934%2Fnaco.2020018). *Numerical Algebra, Control & Optimization*. **11** (1): 99. [arXiv](/source/ArXiv_(identifier)):[1809.02183](https://arxiv.org/abs/1809.02183). [doi](/source/Doi_(identifier)):[10.3934/naco.2020018](https://doi.org/10.3934%2Fnaco.2020018). [ISSN](/source/ISSN_(identifier)) [2155-3297](https://search.worldcat.org/issn/2155-3297).

## Further reading

- [Françoise Tisseur](/source/Fran%C3%A7oise_Tisseur) and Karl Meerbergen, "The quadratic eigenvalue problem," *[SIAM Review](/source/SIAM_Review)* **43** (2), 235–286 (2001) ([link](https://doi.org/10.1137/S0036144500381988)).

- [Gene H. Golub](/source/Gene_H._Golub) and Henk A. van der Vorst, "Eigenvalue computation in the 20th century," *[Journal of Computational and Applied Mathematics](/source/Journal_of_Computational_and_Applied_Mathematics)* **123**, 35–65 (2000).

- Philippe Guillaume, "Nonlinear eigenproblems," *[SIAM Journal on Matrix Analysis and Applications](/source/SIAM_Journal_on_Matrix_Analysis_and_Applications)* **20** (3), 575–595 (1999) ([link](https://dx.doi.org/10.1137/S0895479897324172)).

- Cedric Effenberger, "*Robust solution methods fornonlinear eigenvalue problems*", PhD thesis [EPFL](/source/EPFL) (2013) ([link](http://sma.epfl.ch/~anchpcommon/students/effenberger.pdf))

- Roel Van Beeumen, "*Rational Krylov methods fornonlinear eigenvalue problems*", PhD thesis [KU Leuven](/source/KU_Leuven) (2015) ([link](https://lirias.kuleuven.be/bitstream/123456789/487915/1/PhD%20thesis%20Roel%20Van%20Beeumen.pdf))

---
Adapted from the Wikipedia article [Nonlinear eigenproblem](https://en.wikipedia.org/wiki/Nonlinear_eigenproblem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Nonlinear_eigenproblem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.