Gram-schmidt Process Website Links For
Process 		 

Information About

Gram-schmidt Process
  CATEGORIES ABOUT GRAM–SCHMIDT PROCESS
   
linear algebra
   
functional analysis
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



The method is named for Jørgen Pedersen Gram and Erhard Schmidt but it appeared earlier in the work of Laplace and Cauchy . In the theory of Lie Group Decompositions it is generalized by the Iwasawa Decomposition .

The application of the Gram–Schmidt process to the column vectors of a full column Rank Matrix yields the QR Decomposition (it is decomposed into an Orthogonal and a Triangular Matrix ).


THE GRAM–SCHMIDT PROCESS


We define the Projection Operator by
:\mathrm{proj}_{\mathbf{u}}\,\mathbf{v} = {\langle \mathbf{v}, \mathbf{u} angle\over\langle \mathbf{u}, \mathbf{u} angle}\mathbf{u}.
It projects the vector v orthogonally onto the vector '''u'''.

The Gram–Schmidt process then works as follows:

  <math>\mathbf{u} 2 \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_2, </math>


  <math>\mathbf{u} 3 \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_3, </math>


  align "center"<math> dots</math>
  align "center"<math> dots</math>
  <math>\mathbf{u} K \mathbf{v}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{u}_j}\,\mathbf{v}_k, </math>







We check that the vectors u1 and u2 are indeed orthogonal:
:\langle\mathbf{u}_1,\mathbf{u}_2 angle = \left\langle \begin{pmatrix}3\1\end{pmatrix}, \begin{pmatrix}-2/5\6/5\end{pmatrix} ight angle = - rac65 + rac65 = 0.

We can then normalize the vectors by dividing out their sizes as shown above:
:\mathbf{e}_1 = {1 \over \sqrt {10}}\begin{pmatrix}3\1\end{pmatrix}
:\mathbf{e}_2 = {1 \over \sqrt{40 \over 25}} \begin{pmatrix}-2/5\6/5\end{pmatrix}
= {1\over\sqrt{10}} \begin{pmatrix}-1\3\end{pmatrix}.


NUMERICAL STABILITY


When this process is implemented on a computer, then the vectors u''k'' are not quite orthogonal because of Rounding Errors . For the Gram–Schmidt process as described above this loss of orthogonality is particularly bad; therefore, it is said that the (naive) Gram–Schmidt process is Numerically Unstable .

The Gram–Schmidt process can be stabilized by a small modification. Instead of computing the vector u''k'' as
: \mathbf{u}_k = \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_2}\,\mathbf{v}_k - \cdots - \mathrm{proj}_{\mathbf{u}_{k-1}}\,\mathbf{v}_k,
it is computed as
: \mathbf{u}_k^{(1)} = \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,\mathbf{v}_k,
: \mathbf{u}_k^{(2)} = \mathbf{u}_k^{(1)} - \mathrm{proj}_{\mathbf{u}_2} \, \mathbf{u}_k^{(1)},
::: dots
: \mathbf{u}_k^{(k-2)} = \mathbf{u}_k^{(k-3)} - \mathrm{proj}_{\mathbf{u}_{k-2}} \, \mathbf{u}_k^{(k-3)},
: \mathbf{u}_k = \mathbf{u}_k^{(k-2)} - \mathrm{proj}_{\mathbf{u}_{k-1}} \, \mathbf{u}_k^{(k-2)}.
This series of computations gives the same result as the original formula in exact arithmetic, but it introduces smaller errors in finite-precision arithmetic.


ALGORITHM


The following algorithm implements the stabilized Gram–Schmidt process. The vectors v1, …, v''k'' are replaced by orthonormal vectors which span the same subspace.
: for ''j'' '''from''' 1 '''to''' ''k'' '''do'''
:: for ''i'' '''from''' 1 '''to''' ''j'' − 1 '''do'''
::: \mathbf{v}_j \leftarrow \mathbf{v}_j - \langle \mathbf{v}_j, \mathbf{v}_i angle \mathbf{v}_i (''remove component in direction'' v''i'')
:: end for