next up previous contents
Next: The Rayleigh quotient trick Up: The Trust-Region subproblem Previous: Initial values of and   Contents

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:

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

We will try to find a vector $ u$ which minimizes $ \displaystyle
\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:

$\displaystyle 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

$\displaystyle \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

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


next up previous contents
Next: The Rayleigh quotient trick Up: The Trust-Region subproblem Previous: Initial values of and   Contents
Frank Vanden Berghen 2004-04-19