How to find a good approximation of $u_1$ : LINPACK METHOD

$u_1$ is the unit eigenvector corresponding to $\lambda_1$. We need this vector in the hard case (see the paragraph containing equation 4.15 ). Since $u_1$ is the eigenvector corresponding to $\lambda_1$, we can write:

$$(H-\lambda_1 I) u_1 = 0 \Rightarrow H(\lambda_1) u_1=0$$

We will try to find a vector $u$ which minimizes $$\langle u, H(\lambda) u \rangle$$. This is equivalent to find a vector $v$ which maximize $\omega := H(\lambda)^{-1} v = L^{-T} L^{-1} v$. We will choose the component of $v$ between $+1$ and $-1$ in order to make $L^{-1} v$ large. This is achieved by ensuring that at each stage of the forward substitution $L \omega= v$, the sign of $v$ is chosen to make $\omega$ as large as possible. In particular, suppose we have determined the first $k-1$ components of $\omega$ during the forward substitution, then the $k^{\text{th}}$ component satisfies:

$$l_{kk} \omega_k= v_k - \sum_{i=1}^{k-1} l_{ki} \omega_i,$$

and we pick $v_k$ to be $\pm 1$ depending on which of

$$\frac{1- \sum_{i=1}^{k-1} l_{ki} \omega_i}{l_{kk}} \quad \text{ or }\quad \frac{- 1- \sum_{i=1}^{k-1} l_{ki} \omega_i}{l_{kk}}$$

is larger. Having found $\omega$, $u$ is simply $L^{-T} \omega / \Vert L^{-T} \omega \Vert _2$. The vector $u$ found this way has the useful property that

$$\langle u, H(\lambda) u \rangle \longrightarrow 0$$    as $$\lambda \longrightarrow -\lambda_1$$