next up previous contents index
Next: An Introduction to Iterative Up: A Brief Tour of Previous: More Generalized Eigenproblems   Contents   Index


Nonlinear Eigenproblems
  J. Demmel

This chapter collects several examples of nonlinear eigenvalue problems for which effective algorithms exist. There is no single approach for all nonlinearities, so each example is treated differently.

The simplest kind of nonlinear eigenproblem is the quadratic eigenvalue problem (QEP)

\begin{displaymath}L( \lambda )x = (\lambda^2 M + \lambda B + K)x=0.\end{displaymath}

Here $\lambda$ is called an eigenvalue, and $x$ is a (right) eigenvector. It is called regular if ${\rm det}L( \lambda )$ is not zero for all $\lambda$, and singular otherwise. It can be converted to a generalized linear eigenvalue problem as illustrated in item 3 of §2.5.7 and §2.6.7. QEPs arise in the damped mass-spring system introduced in §2.2.8: the equations of motion $M \ddot{x}(t) + B \dot{x}(t) + Kx(t) =0$ can be solved by substituting $x(t) = e^{\lambda t} x$, where $x$ is a constant vector and $\lambda$ is a constant scalar to be determined. This yields $\lambda^2 Mx + \lambda B x + Kx = 0$ as above. See §9.2.

Higher degree polynomial eigenproblems $(\sum_{i=0}^m \lambda^i A_i)x=0$ can be similarly treated. See §9.3.

Finally, §9.4 considers nonlinear eigenproblems which can be expressed as maximizing a scalar function $F(Y)$ over the set of $n$ by $m$ orthonormal matrices $Y$. The simplest case is maximizing $F(Y) = Y^* AY$, where $A$ is Hermitian and $m=1$; the answer is the largest eigenvalue of $A$. If $F(Y) = {\rm tr} Y^*AY$, i.e., the trace or sum of diagonal entries of $Y^*AY$, then the answer is the sum of the $m$ largest eigenvalues of the Hermitian matrix $A$. For these problems more effective algorithms are available than the conjugate-gradient-based optimization scheme presented here, but its advantage is that it generalizes to far more functions $F$. We give two more examples. First, if $A_1,\ldots,A_m$ are $n$ by $n$ real symmetric matrices that should have a common set of eigenvectors but have been corrupted by noise so that this is no longer so, then we seek an orthogonal $Y$ that minimizes the sums of norms of the offdiagonal entries of all the $Y^*A_iY$. Second, in quantum mechanical calculations using the local density approximation, one wishes to maximize ${\rm tr}Y^*AY + g(Y)$, where $g(Y)$ is a complicated nonlinear term representing the energies of electron-electron interactions. The optimization approach presented here handles quite general functions $g(Y)$.


next up previous contents index
Next: An Introduction to Iterative Up: A Brief Tour of Previous: More Generalized Eigenproblems   Contents   Index
Susan Blackford 2000-11-20