Next: Termination Test. Up: The Trust-Region subproblem Previous: How to find a   Contents

# The Rayleigh quotient trick

If is symmetric and the vector , then the scalar

is known as the Rayleigh quotient of p. The Rayleigh quotient is important because it has the following property:

 (4.21)

During the Cholesky factorization of , we have encountered a negative pivot at the stage of the decomposition for some . The factorization has thus failed ( is indefinite). It is then possible to add to the diagonal of so that the leading by submatrix of

is singular. It's also easy to find a vector for which

 (4.22)

using the Cholesky factors accumulated up to step . Setting for , and back-solving:

gives the required vector. We then obtain a lower bound on by forming the inner product of 4.24 with , using the identity and recalling that the Rayleigh quotient is greater then , we can write:

This implies the bound on :

In the algorithm, we set

Next: Termination Test. Up: The Trust-Region subproblem Previous: How to find a   Contents
Frank Vanden Berghen 2004-04-19