PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (197)
Orphanage
Unclass'd
Unproven (498)
Corrections (22)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
Gram-Schmidt orthogonalization (Algorithm)

Any set of linearly independent vectors $ v_1,\ldots,v_n$ can be converted into a set of orthogonal vectors $ q_1,\ldots,q_n$ by the Gram-Schmidt process. In three dimensions, $ v_1$ determines a line; the vectors $ v_1$ and $ v_2$ determine a plane. The vector $ q_1$ is the unit vector in the direction $ v_1$. The (unit) vector $ q_2$ lies in the plane of $ v_1, v_2$, and is normal to $ v_1$ (on the same side as $ v_2$. The (unit) vector $ q_3$ is normal to the plane of $ v_1, v_2$, on the same side as $ v_3$, etc.

In general, first set $ u_1 = v_1$, and then each $ u_i$ is made orthogonal to the preceding $ u_1,\ldots u_{i-1}$ by subtraction of the projections of $ v_i$ in the directions of $ u_1,\ldots,u_{i-1}$ :

$\displaystyle u_i = v_i - \sum_{j=1}^{i-1} \frac{u_j^Tv_i}{u_j^Tu_j} u_j$

The $ i$ vectors $ u_i$ span the same subspace as the $ v_i$. The vectors $ q_i=u_i/\vert\vert u_i\vert\vert$ are orthonormal. This leads to the following theorem:

Theorem.

Any $ m \times n$ matrix $ A$ with linearly independent columns can be factorized into a product, $ A = QR$. The columns of $ Q$ are orthonormal and $ R$ is upper triangular and invertible.

This “classical” Gram-Schmidt method is often numerically unstable, see [Golub89] for a “modified” Gram-Schmidt method.

References

Golub89
Gene H. Golub and Charles F. van Loan: Matrix Computations, 2nd edn., The John Hopkins University Press, 1989.



"Gram-Schmidt orthogonalization" is owned by akrowne.
(view preamble)

View style:

See Also: Householder transformation, Givens rotation, QR decomposition, an example for Schur decomposition

Other names:  Gram-Schmidt decomposition, Gram-Schmidt orthonormalization, Gram-Schmidt process

Attachments:
example of Gram-Schmidt orthogonalization (Example) by drini
proof of Gram-Schmidt orthogonalization procedure (Proof) by rspuzio
Log in to rate this entry.
(view current ratings)

Cross-references: unstable, Gram-Schmidt, invertible, upper triangular, product, columns, matrix, orthonormal, subspace, span, projections, subtraction, orthogonal, side, normal, unit, unit vector, plane, line, dimensions, orthogonal vectors, vectors, linearly independent
There are 4 references to this entry.

This is version 5 of Gram-Schmidt orthogonalization, born on 2002-01-04, modified 2007-02-14.
Object id is 1216, canonical name is GramSchmidtOrthogonalization.
Accessed 60128 times total.

Classification:
AMS MSC: 65F25 (Numerical analysis :: Numerical linear algebra :: Orthogonalization)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)