Regenerative brake

2014-01-29T18:39:30Z

165.138.236.2: /* Limitations */ edited the location of the 1948 accident to match http://en.wikipedia.org/wiki/List_of_rail_accidents_%281930%E2%80%9349%29

In [[mathematics]], for a given complex [[Hermitian matrix]] <math>M</math> and nonzero [[vector (geometry)|vector]] <math>x</math>, the '''Rayleigh quotient'''<ref>Also known as the '''Rayleigh–Ritz ratio'''; named after [[Walther Ritz]] and [[Lord Rayleigh]].</ref> <math>R(M, x)</math>, is defined as:<ref>Horn, R. A. and C. A. Johnson. 1985. ''Matrix Analysis''. Cambridge University Press. pp. 176–180.</ref><ref>Parlet B. N. ''The symmetric eigenvalue problem'', SIAM, Classics in Applied Mathematics,1998</ref>

:<math>R(M,x) := {x^{*} M x \over x^{*} x}.</math>

For real matrices and vectors, the condition of being Hermitian reduces to that of being [[Symmetric matrix|symmetric]], and the [[conjugate transpose]] <math>x^{*}</math> to the usual [[transpose]] <math>x'</math>. Note that <math>R(M, c x) = R(M,x)</math> for any [[Real Numbers|real]] scalar <math>c \neq 0 </math>. Recall that a Hermitian (or real symmetric) matrix has real [[eigenvalues]]. It can be shown that, for a given matrix, the Rayleigh quotient reaches its minimum value <math>\lambda_\min</math> (the smallest [[eigenvalue]] of <math>M</math>) when <math>x</math> is <math>v_\min</math> (the corresponding [[eigenvector]]). Similarly, <math>R(M, x) \leq \lambda_\max</math> and <math>R(M, v_\max) = \lambda_\max</math>. The Rayleigh quotient is used in the [[min-max theorem]] to get exact values of all eigenvalues. It is also used in [[eigenvalue algorithm]]s to obtain an eigenvalue approximation from an eigenvector approximation. Specifically, this is the basis for [[Rayleigh quotient iteration]].

The range of the Rayleigh quotient is called a [[numerical range]].

==Special case of covariance matrices==
An empirical [[covariance matrix]] ''M'' can be represented as the product ''A''' ''A'' of the [[data matrix (multivariate statistics)|data matrix]] ''A'' pre-multiplied by its transpose ''A'''. Being a symmetrical real matrix, ''M'' has non-negative eigenvalues, and orthogonal (or othogonalisable) eigenvectors, which can be demonstrated as follows.

Firstly, that the eigenvalues <math>\lambda_i</math> are non-negative:

:<math>M v_i = A' A v_i = \lambda_i v_i</math>

:<math>\Rightarrow v_i' A' A v_i = v_i' \lambda_i v_i</math>

:<math>\Rightarrow \left\| A v_i \right\|^2 = \lambda_i \left\| v_i \right\|^2</math>

:<math>\Rightarrow \lambda_i = \frac{\left\| A v_i \right\|^2}{\left\| v_i \right\|^2} \geq 0.</math>

Secondly, that the eigenvectors <math>v_i</math> are orthogonal to one another:

:<math>M v_i = \lambda _i v_i</math>

:<math>\Rightarrow v_j' M v_i = \lambda _i v_j' v_i</math>

:<math>\Rightarrow (M v_j )' v_i = \lambda _i v_j' v_i</math>

:<math>\Rightarrow \lambda_j v_j ' v_i = \lambda _i v_j' v_i</math>

:<math>\Rightarrow (\lambda_j - \lambda_i) v_j ' v_i = 0</math>

:<math>\Rightarrow v_j ' v_i = 0</math> (if the eigenvalues are different – in the case of multiplicity, the basis can be orthogonalized).

To now establish that the Rayleigh quotient is maximised by the eigenvector with the largest eigenvalue, consider decomposing an arbitrary vector <math>x</math> on the basis of the eigenvectors ''v''<sub>''i''</sub>:
:<math>x = \sum _{i=1} ^n \alpha _i v_i</math>, where <math> \alpha_i = \frac{x'v_i}{v_i'v_i} = \frac{\langle x,v_i\rangle}{\left\| v_i \right\| ^2}</math> is the coordinate of x orthogonally projected onto <math>v_i</math>

so
:<math>R(M,x) = \frac{x' A' A x}{x' x}</math>

can be written
:<math>R(M,x) = \frac{(\sum _{j=1} ^n \alpha _j v_j)' A' A (\sum _{i=1} ^n \alpha _i v_i)}{(\sum _{j=1} ^n \alpha _j v_j)' (\sum _{i=1} ^n \alpha _i v_i)}</math>

which, by orthogonality of the eigenvectors, becomes:

:<math>R(M,x) = \frac{\sum _{i=1} ^n \alpha _i ^2 \lambda _i}{\sum _{i=1} ^n \alpha _i ^2} = \sum_{i=1}^n \lambda_i \frac{(x'v_i)^2}{ (x'x)( v_i' v_i)}
</math>

The last representation establishes that the Rayleigh quotient is the sum of the squared cosines of the angles formed by the vector <math>x</math> and each eigenvector <math>v_i</math>, weighted by corresponding eigenvalues.

If a vector <math>x</math> maximizes <math>R(M,x)</math>, then any scalar multiple <math>k x</math> (for <math>k \ne 0</math>) also maximizes ''R'', so the problem can be reduced to the [[Lagrange multipliers|Lagrange problem]] of maximizing <math>\sum _{i=1} ^n \alpha _i ^2 \lambda _i</math> under the constraint that <math>\sum _{i=1} ^n \alpha _i ^2 = 1</math>.

Let <math>\beta_i \overset{\text{def}}= \alpha_i^2</math>. This then becomes a [[linear program]], which always attains its maximum at one of the corners of the domain. A maximum point will have <math>\alpha _1 = \pm 1</math> and <math>\forall i > 1, \alpha _i = 0</math> (when the eigenvalues are ordered by decreasing magnitude).

Thus, as advertised, the Rayleigh quotient is maximised by the eigenvector with the largest eigenvalue.

=== Formulation using Lagrange multipliers ===
Alternatively, this result can be arrived at by the method of [[Lagrange multipliers]]. The problem is to find the [[critical point (mathematics)|critical points]] of the function

:<math>R(M,x) = x^T M x </math>,
subject to the constraint <math>\|x\|^2 = x^Tx = 1.</math>
I.e. to find the critical points of
:<math>\mathcal{L}(x) = x^T M x -\lambda (x^Tx - 1), </math>
where <math>\lambda </math> is a Lagrange multiplier. The stationary points of <math>\mathcal{L}(x)</math> occur at

:<math>\frac{d\mathcal{L}(x)}{dx} = 0 </math>
:<math>\therefore 2x^T M^T - 2\lambda x^T = 0 </math>
:<math>\therefore M x = \lambda x </math>
and <math> R(M,x) = \frac{x^T M x}{x^T x} = \lambda \frac{x^Tx}{x^T x} = \lambda.</math>

Therefore, the eigenvectors <math>x_1 \ldots x_n</math> of ''M'' are the critical points of the Rayleigh Quotient and their corresponding eigenvalues <math>\lambda_1 \ldots \lambda_n</math> are the stationary values of ''R''.

This property is the basis for [[principal components analysis]] and [[canonical correlation]].

==Use in Sturm–Liouville theory==
[[Sturm–Liouville theory]] concerns the action of the [[linear operator]]

:<math>L(y) = \frac{1}{w(x)}\left(-\frac{d}{dx}\left[p(x)\frac{dy}{dx}\right] + q(x)y\right)</math>

on the [[inner product space]] defined by

:<math>\langle{y_1,y_2}\rangle = \int_a^b w(x)y_1(x)y_2(x) \, dx</math>

of functions satisfying some specified [[boundary conditions]] at ''a'' and ''b''. In this case the Rayleigh quotient is

:<math>\frac{\langle{y,Ly}\rangle}{\langle{y,y}\rangle} = \frac{\int_a^b{y(x)\left(-\frac{d}{dx}\left[p(x)\frac{dy}{dx}\right] + q(x)y(x)\right)}dx}{\int_a^b{w(x)y(x)^2}dx}.</math>

This is sometimes presented in an equivalent form, obtained by separating the integral in the numerator and using [[integration by parts]]:

:<math>\frac{\langle{y,Ly}\rangle}{\langle{y,y}\rangle} = \frac{\int_a^b{y(x)\left(-\frac{d}{dx}\left[p(x)y'(x)\right]\right)}dx + \int_a^b{q(x)y(x)^2} \, dx}{\int_a^b{w(x)y(x)^2} \, dx}</math>

:<math>= \frac{-y(x)\left[p(x)y'(x)\right]|_a^b + \int_a^b{y'(x)\left[p(x)y'(x)\right]} \, dx + \int_a^b{q(x)y(x)^2} \, dx}{\int_a^b{w(x)y(x)^2} \, dx}</math>
:<math>= \frac{-p(x)y(x)y'(x)|_a^b + \int_a^b\left[p(x)y'(x)^2 + q(x)y(x)^2\right] \, dx}{\int_a^b{w(x)y(x)^2} \, dx}.</math>

==Generalization==
For a given pair <math>(A, B)</math> of matrices, and a given non-zero vector <math>x</math>, the '''generalized Rayleigh quotient''' is defined as:

:<math>R(A,B; x) := \frac{x^* A x}{x^* B x}.</math>

The Generalized Rayleigh Quotient can be reduced to the Rayleigh Quotient <math>R(D, C^*x)</math> through the transformation <math>D = C^{-1} A {C^*}^{-1}</math> where <math>CC^*</math> is the [[Cholesky decomposition]] of the Hermitian positive-definite matrix <math>B</math>.

==See also==
* [[Field of values]]

==References==
<references/>

==Further reading==
* Shi Yu, Léon-Charles Tranchevent, Bart Moor, Yves Moreau, ''[http://books.google.com/books?id=U6-ubGYgf7QC&dq='Rayleigh%E2%80%93Ritz+ratio%22+Rayleigh+quotient&source=gbs_navlinks_s Kernel-based Data Fusion for Machine Learning: Methods and Applications in Bioinformatics and Text Mining]'', Ch. 2, Springer, 2011.

{{DEFAULTSORT:Rayleigh Quotient}}
[[Category:Linear algebra]]

formulasearchengine - User contributions [en]

Regenerative brake