The Rayleigh quotient trick

If $H$ is symmetric and the vector $p\neq 0$, then the scalar

$$\frac{\langle p, H p\rangle}{\langle p,p\rangle}$$

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

$$\lambda_{min}[H] \leq \frac{\langle p, H p\rangle}{\langle p,p\rangle} \leq \lambda_{max}[H]$$ (4.21)

During the Cholesky factorization of $H(\lambda)$, we have encountered a negative pivot at the $k^{\text{th}}$ stage of the decomposition for some $k\leq n$. The factorization has thus failed ($H$ is indefinite). It is then possible to add $\delta= \sum_{j=1}^{k-1} l_{kj}^2- h_{kk}(\lambda) \geq 0$ to the $k^{\text{th}}$ diagonal of $H(\lambda)$ so that the leading $k$ by $k$ submatrix of

$$H(\lambda)+ \delta e_k e_k^T$$

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

$$H(\lambda+ \delta e_k e_k^T)v=0$$ (4.22)

using the Cholesky factors accumulated up to step $k$. Setting $v_j=0$ for $j>k, v_k=1$, and back-solving:

$$v_j=- \frac{\sum_{i=j+1}^k l_{ij} v_i}{l_{jj}} \text{ for } j=k-1, \ldots, 1$$

gives the required vector. We then obtain a lower bound on $-\lambda_1$ by forming the inner product of 4.24 with $v$, using the identity $\langle e_k,v\rangle=v_k=1$ and recalling that the Rayleigh quotient is greater then $\lambda_{min}=\lambda_1$, we can write:

$$0= \frac{\langle v, (H+\lambda I) v\rangle}{\langle v,v\rangle} ... ...le v,v\rangle} \geq \lambda + \lambda_1 + \frac{\delta}{ \Vert v\Vert _2^2 }$$

This implies the bound on $\lambda_1$:

$$\lambda + \frac{\delta}{ \Vert v\Vert _2^2 } \leq - \lambda_1$$

In the algorithm, we set $$\lambda_L = \max [ \lambda_L, \lambda + \frac{\delta}{ \Vert v\Vert _2^2 } ]$$