The Rayleigh–Ritz method is a direct numerical method of approximating eigenvalues, which originated in the context of solving physical boundary-value problems. It is named after Lord Rayleigh and Walther Ritz. In this method, an infinite-dimensional linear operator is approximated by a finite-dimensional compression, enabling the use of a numerical eigenvalue algorithm. It is used in all applications that involve approximating eigenvalues and eigenvectors, often under different names. In quantum mechanics, where a system of particles is described using a Hamiltonian, it uses trial wave functions to approximate the ground-state eigenfunction. In the context of the finite-element method, it is mathematically the same as the Ritz-Galerkin method. In mechanical and structural engineering, it is used to approximate the eigenmodes and resonant frequencies of a structure. A related adaption of Rayleigh-Ritz known as Hamiltonian truncation can be used in quantum field theory.
Naming and attribution The origin of this technique has been debated by historians. It has been called Ritz method after Walther Ritz, who published the numerical procedure 1908 and 1909. Lord Rayleigh wrote a paper congratulating Ritz on his work in 1911, but stating that he himself had used Ritz's method in many places in his book, Theory of Sound (1877), and elsewhere. According to Richard Courant, both Lord Rayleigh and Walther Ritz independently invented the idea of utilizing the equivalence between the boundary-value problems of partial differential equations on the one hand and problems of the calculus of variations on the other to numerically compute the solutions, by substituting for the variational problems simpler approximating extremum problems in which only a finite number of parameters need to be determined. Historian Jesper Lützen, who had examined the unpublished manuscripts of Joseph Liouville, discovered that Liouville had already known of this method as early as 1845.
Method Let T {\displaystyle T} be a linear operator on a Hilbert space H {\displaystyle {\mathcal {H}}} , with inner product ( ⋅ , ⋅ ) {\displaystyle (\cdot ,\cdot )} . Now consider a finite set of functions L = { φ 1 , . . . , φ n } {\displaystyle {\mathcal {L}}=\{\varphi _{1},...,\varphi _{n}\}} . Depending on the application these functions may be:
A subset of the orthonormal basis of the original operator; A space of splines (as in the Galerkin method); A set of functions which approximate the eigenfunctions of the operator. One could use the orthonormal basis generated from the eigenfunctions of the operator, which will produce diagonal approximating matrices, but in this case we would have already had to calculate the spectrum. We now approximate T {\displaystyle T} by T L {\displaystyle T_{\mathcal {L}}} , which is defined as the matrix with entries
( T L ) i , j = ( T φ i , φ j ) . {\displaystyle (T_{\mathcal {L}})_{i,j}=(T\varphi _{i},\varphi _{j}).}
and solve the eigenvalue problem T L u = λ u {\displaystyle T_{\mathcal {L}}u=\lambda u} . It can be shown that the matrix T L {\displaystyle T_{\mathcal {L}}} is the compression of T {\displaystyle T} to L {\displaystyle {\mathcal {L}}} . For differential operators (such as Sturm-Liouville operators), the inner product ( ⋅ , ⋅ ) {\displaystyle (\cdot ,\cdot )} can be replaced by the weak formulation A ( ⋅ , ⋅ ) {\displaystyle {\mathcal {A}}(\cdot ,\cdot )} . If a subset of the orthonormal basis was used to find the matrix, the eigenvectors of T L {\displaystyle T_{\mathcal {L}}} will be linear combinations of orthonormal basis functions, and as a result they will be approximations of the eigenvectors of T {\displaystyle T} .
Properties
Spectral pollution It is possible for the Rayleigh–Ritz method to produce values which do not converge to actual values in the spectrum of the operator as the truncation gets large. These values are known as spectral pollution. In some cases (such as for the Schrödinger equation), there is no approximation which both includes all eigenvalues of the equation, and contains no pollution. The spectrum of the compression (and thus pollution) is bounded by the numerical range of the operator; in many cases it is bounded by a subset of the numerical range known as the essential numerical range.
For matrix eigenvalue problems In numerical linear algebra, the Rayleigh–Ritz method is commonly applied to approximate an eigenvalue problem
A x = λ x {\displaystyle A\mathbf {x} =\lambda \mathbf {x} }
for the matrix A ∈ C N × N {\displaystyle A\in \mathbb {C} ^{N\times N}} of size N {\displaystyle N} using a projected matrix of a smaller size m < N {\displaystyle m<N} , generated from a given matrix V ∈ C N × m {\displaystyle V\in \mathbb {C} ^{N\times m}} with orthonormal columns. The matrix version of the algorithm is the most simple:
Compute the m × m {\displaystyle m\times m} matrix V ∗ A V {\displaystyle V^{*}AV} , where V ∗ {\displaystyle V^{*}} denotes the complex-conjugate transpose of V {\displaystyle V}
Solve the eigenvalue problem V ∗ A V y i = μ i y i {\displaystyle V^{*}AV\mathbf {y} _{i}=\mu _{i}\mathbf {y} _{i}}
Compute the Ritz vectors x ~ i = V y i {\displaystyle {\tilde {\mathbf {x} }}_{i}=V\mathbf {y} _{i}} and the Ritz value λ ~ i = μ i {\displaystyle {\tilde {\lambda }}_{i}=\mu _{i}}
Output approximations ( λ ~ i , x ~ i ) {\displaystyle ({\tilde {\lambda }}_{i},{\tilde {\mathbf {x} }}_{i})} , called the Ritz pairs, to eigenvalues and eigenvectors of the original matrix A {\displaystyle A} . If the subspace with the orthonormal basis given by the columns of the matrix V ∈ C N × m {\displaystyle V\in \mathbb {C} ^{N\times m}} contains k ≤ m {\displaystyle k\leq m} vectors that are close to eigenvectors of the matrix A {\displaystyle A} , the Rayleigh–Ritz method above finds k {\displaystyle k} Ritz vectors that well approximate these eigenvectors. The easily computable quantity ‖ A x ~ i − λ ~ i x ~ i ‖ {\displaystyle \|A{\tilde {\mathbf {x} }}_{i}-{\tilde {\lambda }}_{i}{\tilde {\mathbf {x} }}_{i}\|} determines the accuracy of such an approximation for every Ritz pair. In the easiest case m = 1 {\displaystyle m=1} , the N × m {\displaystyle N\times m} matrix V {\displaystyle V} turns into a unit column-vector v {\displaystyle v} , the m × m {\displaystyle m\times m} matrix V ∗ A V {\displaystyle V^{*}AV} is a scalar that is equal to the Rayleigh quotient ρ ( v ) = v ∗ A v / v ∗ v {\displaystyle \rho (v)=v^{*}Av/v^{*}v} , the only i = 1 {\displaystyle i=1} solution to the eigenvalue problem is y i = 1 {\displaystyle y_{i}=1} and μ i = ρ ( v ) {\displaystyle \mu _{i}=\rho (v)} , and the only Ritz vector is v {\displaystyle v} itself. Thus, the Rayleigh–Ritz method turns into computing of the Rayleigh quotient if m = 1 {\displaystyle m=1} . Another useful connection to the Rayleigh quotient is that μ i = ρ ( v i ) {\displaystyle \mu _{i}=\rho (v_{i})} for every Ritz pair ( λ ~ i , x ~ i ) {\displaystyle ({\tilde {\lambda }}_{i},{\tilde {\mathbf {x} }}_{i})} , allowing to derive some properties of Ritz values μ i {\displaystyle \mu _{i}} from the corresponding theory for the Rayleigh quotient. For example, if A {\displaystyle A} is a Hermitian matrix, its Rayleigh quotient (and thus its every Ritz value) is real and takes values within the closed interval of the smallest and largest eigenvalues of A {\displaystyle A} .
Example The matrix
A = [ 2 0 0 0 2 1 0 1 2 ] {\displaystyle A={\begin{bmatrix}2&0&0\\0&2&1\\0&1&2\end{bmatrix}}}
has eigenvalues 1 , 2 , 3 {\displaystyle 1,2,3} and the corresponding eigenvectors
x λ = 1 = [ 0 1 − 1 ] , x λ = 2 = [ 1 0 0 ] , x λ = 3 = [ 0 1 1 ] . {\displaystyle \mathbf {x} _{\lambda =1}={\begin{bmatrix}0\\1\\-1\end{bmatrix}},\quad \mathbf {x} _{\lambda =2}={\begin{bmatrix}1\\0\\0\end{bmatrix}},\quad \mathbf {x} _{\lambda =3}={\begin{bmatrix}0\\1\\1\end{bmatrix}}.}
Let us take
V = [ 0 0 1 0 0 1 ] , {\displaystyle V={\begin{bmatrix}0&0\\1&0\\0&1\end{bmatrix}},}
then
V ∗ A V = [ 2 1 1 2 ] {\displaystyle V^{*}AV={\begin{bmatrix}2&1\\1&2\end{bmatrix}}}
with eigenvalues 1 , 3 {\displaystyle 1,3} and the corresponding eigenvectors
y μ = 1 = [ 1 − 1 ] , y μ = 3 = [ 1 1 ] , {\displaystyle \mathbf {y} _{\mu =1}={\begin{bmatrix}1\\-1\end{bmatrix}},\quad \mathbf {y} _{\mu =3}={\begin{bmatrix}1\\1\end{bmatrix}},}
so that the Ritz values are 1 , 3 {\displaystyle 1,3} and the Ritz vectors are
x ~ λ ~ = 1 = [ 0 1 − 1 ] , x ~ λ ~ = 3 = [ 0 1 1 ] . {\displaystyle \mathbf {\tilde {x}} _{{\tilde {\lambda }}=1}={\begin{bmatrix}0\\1\\-1\end{bmatrix}},\quad \mathbf {\tilde {x}} _{{\tilde {\lambda }}=3}={\begin{bmatrix}0\\1\\1\end{bmatrix}}.}
We observe that each one of the Ritz vectors is exactly one of the eigenvectors of A {\displaystyle A} for the given V {\displaystyle V} as well as the Ritz values give exactly two of the three eigenvalues of A {\displaystyle A} . A mathematical explanation for the exact approximation is based on the fact that the column space of the matrix V {\displaystyle V} happens to be exactly the same as the subspace spanned by the two eigenvectors x λ = 1 {\displaystyle \mathbf {x} _{\lambda =1}} and x λ = 3 {\displaystyle \mathbf {x} _{\lambda =3}} in this example.
For matrix singular value problems Truncated singular value decomposition (SVD) in numerical linear algebra can also use the Rayleigh–Ritz method to find approximations to left and right singular vectors of the matrix M ∈ C M × N {\displaystyle M\in \mathbb {C} ^{M\times N}} of size M × N {\displaystyle M\times N} in given subspaces by turning the singular value problem into an eigenvalue problem.
Using the normal matrix The definition of the singular value σ {\displaystyle \sigma } and the corresponding left and right singular vectors is M v = σ u {\displaystyle Mv=\sigma u} and M ∗ u = σ v {\displaystyle M^{*}u=\sigma v} . Having found one set (left of right) of approximate singular vectors and singular values by applying naively the Rayleigh–Ritz method to the Hermitian normal matrix M ∗ M ∈ C N × N {\displaystyle M^{*}M\in \mathbb {C} ^{N\times N}} or M M ∗ ∈ C M × M {\displaystyle MM^{*}\in \mathbb {C} ^{M\times M}} , whichever one is smaller size, one could determine the other set of left of right singular vectors simply by dividing by the singular values, i.e., u = M v / σ {\displaystyle u=Mv/\sigma } and v = M ∗ u / σ {\displaystyle v=M^{*}u/\sigma } . However, the division is unstable or fails for small or zero singular values. An alternative approach, e.g., defining the normal matrix as A = M ∗ M ∈ C N × N {\displaystyle A=M^{*}M\in \mathbb {C} ^{N\times N}} of size N × N {\displaystyle N\times N} , takes advantage of the fact that for a given N × m {\displaystyle N\times m} matrix W ∈ C N × m {\displaystyle W\in \mathbb {C} ^{N\times m}} with orthonormal columns the eigenvalue problem of the Rayleigh–Ritz method for the m × m {\displaystyle m\times m} matrix
W ∗ A W = W ∗ M ∗ M W = ( M W ) ∗ M W {\displaystyle W^{*}AW=W^{*}M^{*}MW=(MW)^{*}MW} can be interpreted as a singular value problem for the N × m {\displaystyle N\times m} matrix M W {\displaystyle MW} . This interpretation allows simple simultaneous calculation of both left and right approximate singular vectors as follows.
Compute the N × m {\displaystyle N\times m} matrix M W {\displaystyle MW} . Compute the thin, or economy-sized, SVD M W = U Σ V h , {\displaystyle MW=\mathbf {U} \Sigma \mathbf {V} _{h},} with N × m {\displaystyle N\times m} matrix U {\displaystyle \mathbf {U} } , m × m {\displaystyle m\times m} diagonal matrix Σ {\displaystyle \Sigma } , and m × m {\displaystyle m\times m} matrix V h {\displaystyle \mathbf {V} _{h}} . Compute the matrices of the Ritz left U = U {\displaystyle U=\mathbf {U} } and right V h = V h W ∗ {\displaystyle V_{h}=\mathbf {V} _{h}W^{*}} singular vectors. Output approximations U , Σ , V h {\displaystyle U,\Sigma ,V_{h}} , called the Ritz singular triplets, to selected singular values and the corresponding left and right singular vectors of the original matrix M {\displaystyle M} representing an approximate Truncated singular value decomposition (SVD) with left singular vectors restricted to the column-space of the matrix W {\displaystyle W} . The algorithm can be used as a post-processing step where the matrix W {\displaystyle W} is an output of an eigenvalue solver, e.g., such as LOBPCG, approximating numerically selected eigenvectors of the normal matrix A = M ∗ M {\displaystyle A=M^{*}M} .
Example The matrix
M = [ 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 4 0 0 0 0 ] {\displaystyle M={\begin{bmatrix}1&0&0&0\\0&2&0&0\\0&0&3&0\\0&0&0&4\\0&0&0&0\end{bmatrix}}}
has its normal matrix
A = M ∗ M = [ 1 0 0 0 0 4 0 0 0 0 9 0 0 0 0 16 ] , {\displaystyle A=M^{*}M={\begin{bmatrix}1&0&0&0\\0&4&0&0\\0&0&9&0\\0&0&0&16\\\end{bmatrix}},}
singular values 1 , 2 , 3 , 4 {\displaystyle 1,2,3,4} and the corresponding thin SVD
M = [ 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 ] [ 4 0 0 0 0 3 0 0 0 0 2 0 0 0 0 1 ] [ 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ] , {\displaystyle M={\begin{bmatrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\\0&0&0&0\end{bmatrix}}{\begin{bmatrix}4&0&0&0\\0&3&0&0\\0&0&2&0\\0&0&0&1\end{bmatrix}}{\begin{bmatrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\end{bmatrix}},}
where the columns of the first multiplier from the complete set of the left singular vectors of the matrix A {\displaystyle A} , the diagonal entries of the middle term are the singular values, and the columns of the last multiplier transposed (although the transposition does not change it)
[ 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ] ∗ = [ 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ] {\displaystyle {\begin{bmatrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\end{bmatrix}}^{*}\quad =\quad {\begin{bmatrix}0&0&0&1\\0&0&1&0\\0&1&0&0\\1&0&0&0\end{bmatrix}}}
are the corresponding right singular vectors. Let us take
W = [ 1 / 2 1 / 2 1 / 2 − 1 / 2 0 0