In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, particularly
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices.
...
and
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, the Gram–Schmidt process is a method for
orthonormalizing a set of
vectors in an
inner product space
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often den ...
, most commonly the
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
equipped with the
standard inner product. The Gram–Schmidt process takes a
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
,
linearly independent
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts are ...
set of vectors for and generates an
orthogonal set that spans the same ''k''-dimensional subspace of R
''n'' as ''S''.
The method is named after
Jørgen Pedersen Gram
Jørgen Pedersen Gram (27 June 1850 – 29 April 1916) was a Danish actuary and mathematician who was born in Nustrup, Duchy of Schleswig, Denmark and died in Copenhagen, Denmark.
Important papers of his include ''On series expansions determin ...
and
Erhard Schmidt
Erhard Schmidt (13 January 1876 – 6 December 1959) was a Baltic German mathematician whose work significantly influenced the direction of mathematics in the twentieth century. Schmidt was born in Tartu (german: link=no, Dorpat), in the Govern ...
, but
Pierre-Simon Laplace
Pierre-Simon, marquis de Laplace (; ; 23 March 1749 – 5 March 1827) was a French scholar and polymath whose work was important to the development of engineering, mathematics, statistics, physics, astronomy, and philosophy. He summarized ...
had been familiar with it before Gram and Schmidt. In the theory of
Lie group decompositions {{unreferenced, date=September 2009
In mathematics, Lie group decompositions are used to analyse the structure of Lie groups and associated objects, by showing how they are built up out of subgroups. They are essential technical tools in the repre ...
it is generalized by the
Iwasawa decomposition In mathematics, the Iwasawa decomposition (aka KAN from its expression) of a semisimple Lie group generalises the way a square real matrix can be written as a product of an orthogonal matrix and an upper triangular matrix (QR decomposition, a conseq ...
.
The application of the Gram–Schmidt process to the column vectors of a full column
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
yields the
QR decomposition
In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix ''A'' into a product ''A'' = ''QR'' of an orthogonal matrix ''Q'' and an upper triangular matrix ''R''. QR decompo ...
(it is decomposed into an
orthogonal
In mathematics, orthogonality is the generalization of the geometric notion of ''perpendicularity''.
By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
and a
triangular matrix
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
).
The Gram–Schmidt process
We define the
projection
Projection, projections or projective may refer to:
Physics
* Projection (physics), the action/process of light, heat, or sound reflecting from a surface to another in a different direction
* The display of images by a projector
Optics, graphic ...
operator by
where
denotes the
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff space, Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation (mathematics), operation called an inner product. The inner product of two ve ...
of the vectors u and v. This operator projects the vector v orthogonally onto the line spanned by vector u. If u = 0, we define
, i.e., the projection map
is the zero map, sending every vector to the zero vector.
The Gram–Schmidt process then works as follows:
The sequence is the required system of orthogonal vectors, and the normalized vectors form an
ortho''normal'' set. The calculation of the sequence is known as ''Gram–Schmidt
orthogonalization
In linear algebra, orthogonalization is the process of finding a set of orthogonal vectors that span a particular subspace. Formally, starting with a linearly independent set of vectors in an inner product space (most commonly the Euclidean spa ...
'', while the calculation of the sequence is known as ''Gram–Schmidt
orthonormalization
In linear algebra, orthogonalization is the process of finding a set of orthogonal vectors that span a particular subspace. Formally, starting with a linearly independent set of vectors in an inner product space (most commonly the Euclidean sp ...
'' as the vectors are normalized.
To check that these formulas yield an orthogonal sequence, first compute
by substituting the above formula for u
2: we get zero. Then use this to compute
again by substituting the formula for u
3: we get zero. The general proof proceeds by
mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
.
Geometrically, this method proceeds as follows: to compute u
''i'', it projects v
''i'' orthogonally onto the subspace ''U'' generated by , which is the same as the subspace generated by . The vector u
''i'' is then defined to be the difference between v
''i'' and this projection, guaranteed to be orthogonal to all of the vectors in the subspace ''U''.
The Gram–Schmidt process also applies to a linearly independent
countably infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
sequence . The result is an orthogonal (or orthonormal) sequence such that for natural number :
the algebraic span of is the same as that of .
If the Gram–Schmidt process is applied to a linearly dependent sequence, it outputs the vector on the ''i''th step, assuming that is a linear combination of . If an orthonormal basis is to be produced, then the algorithm should test for zero vectors in the output and discard them because no multiple of a zero vector can have a length of 1. The number of vectors output by the algorithm will then be the dimension of the space spanned by the original inputs.
A variant of the Gram–Schmidt process using
transfinite recursion
Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC.
Induction by cases
Let P(\alpha) be a property defined for a ...
applied to a (possibly uncountably) infinite sequence of vectors
yields a set of orthonormal vectors
with
such that for any
, the
completion of the span of
is the same as that of In particular, when applied to a (algebraic) basis of a
Hilbert space
In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
(or, more generally, a basis of any dense subspace), it yields a (functional-analytic) orthonormal basis. Note that in the general case often the strict inequality
holds, even if the starting set was linearly independent, and the span of
need not be a subspace of the span of
(rather, it's a subspace of its completion).
Example
Euclidean space
Consider the following set of vectors in (with the conventional
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff space, Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation (mathematics), operation called an inner product. The inner product of two ve ...
)
Now, perform Gram–Schmidt, to obtain an orthogonal set of vectors:
We check that the vectors and are indeed orthogonal:
noting that if the dot product of two vectors is 0 then they are orthogonal.
For non-zero vectors, we can then normalize the vectors by dividing out their sizes as shown above:
Properties
Denote by
the result of applying the Gram–Schmidt process to a collection of vectors
. This yields a map
.
It has the following properties:
* It is continuous
* It is
orientation
Orientation may refer to:
Positioning in physical space
* Map orientation, the relationship between directions on a map and compass directions
* Orientation (housing), the position of a building with respect to the sun, a concept in building de ...
preserving in the sense that
.
* It commutes with orthogonal maps:
Let
be orthogonal (with respect to the given inner product). Then we have
Further a parametrized version of the Gram–Schmidt process yields a (strong)
deformation retraction
In topology, a branch of mathematics, a retraction is a continuous mapping from a topological space into a subspace that preserves the position of all points in that subspace. The subspace is then called a retract of the original space. A deformat ...
of the general linear group
onto the orthogonal group
.
Numerical stability
When this process is implemented on a computer, the vectors
are often not quite orthogonal, due to
rounding errors. For the Gram–Schmidt process as described above (sometimes referred to as "classical Gram–Schmidt") this loss of orthogonality is particularly bad; therefore, it is said that the (classical) Gram–Schmidt process is
numerically unstable
In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algorit ...
.
The Gram–Schmidt process can be stabilized by a small modification; this version is sometimes referred to as modified Gram-Schmidt or MGS. This approach gives the same result as the original formula in exact arithmetic and introduces smaller errors in finite-precision arithmetic.
Instead of computing the vector as
it is computed as
This method is used in the previous animation, when the intermediate vector is used when orthogonalizing the blue vector .
Here is another description of the modified algorithm. Given the vectors
, in our first step we produce vectors
by removing components along the direction of
. In formulas,
. After this step we already have two of our desired orthogonal vectors
, namely
, but we also made
already orthogonal to
. Next, we orthogonalize those remaining vectors against
. This means we compute
by subtraction
. Now we have stored the vectors
where the first three vectors are already
and the remaining vectors are already orthogonal to
. As should be clear now, the next step orthogonalizes
against
. Proceeding in this manner we find the full set of orthogonal vectors
. If orthonormal vectors are desired, then we normalize as we go, so that the denominators in the subtraction formulas turn into ones.
Algorithm
The following
MATLAB
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementation ...
algorithm implements the Gram–Schmidt orthonormalization for Euclidean Vectors. The vectors (columns of matrix
V
, so that
V(:,j)
is the ''j''th vector) are replaced by orthonormal vectors (columns of
U
) which span the same subspace.
function gramschmidt(V)
,k= size(V);
U = zeros(n,k);
U(:,1) = V(:,1)/norm(V(:,1));
for i = 2:k
U(:,i)=V(:,i);
for j=1:i-1
U(:,i)=U(:,i)-(U(:,j)'*U(:,i)) * U(:,j);
end
U(:,i) = U(:,i)/norm(U(:,i));
end
end
The cost of this algorithm is asymptotically floating point operations, where is the dimensionality of the vectors.
Via Gaussian elimination
If the rows are written as a matrix
, then applying
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
to the augmented matrix