Namespaces
Variants
Actions

Difference between revisions of "Orthogonalization"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (Undo revision 48082 by Ulf Rehmann (talk))
Tag: Undo
Line 1: Line 1:
−
<!--
 
−
o0704201.png
 
−
$#A+1 = 33 n = 0
 
−
$#C+1 = 33 : ~/encyclopedia/old_files/data/O070/O.0700420 Orthogonalization,
 
−
Automatically converted into TeX, above some diagnostics.
 
−
Please remove this comment and the {{TEX|auto}} line below,
 
−
if TeX found to be correct.
 
−
-->
 
−
 
−
{{TEX|auto}}
 
−
{{TEX|done}}
 
−
 
 
''orthogonalization process''
 
''orthogonalization process''
  
−
An algorithm to construct for a given linear independent system of vectors in a Euclidean or Hermitian space $  V $
+
An algorithm to construct for a given linear independent system of vectors in a Euclidean or Hermitian space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704201.png" /> an [[Orthogonal system|orthogonal system]] of non-zero vectors generating the same subspace in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704202.png" />. The most well-known is the Schmidt (or Gram–Schmidt) orthogonalization process, in which from a linear independent system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704203.png" />, an orthogonal system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704204.png" /> is constructed such that every vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704205.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704206.png" />) is linearly expressed in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704207.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704208.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o0704209.png" /> is an upper-triangular matrix. It is possible to construct the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042010.png" /> such that it is orthonormal and such that the diagonal entries <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042011.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042012.png" /> are positive; the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042013.png" /> and the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042014.png" /> are defined uniquely by these conditions.
−
an [[Orthogonal system|orthogonal system]] of non-zero vectors generating the same subspace in $  V $.  
 
−
The most well-known is the Schmidt (or Gram–Schmidt) orthogonalization process, in which from a linear independent system $  a _ {1} \dots a _ {k} $,  
 
−
an orthogonal system $  b _ {1} \dots b _ {k} $
 
−
is constructed such that every vector $  b _ {i} $(
 
−
$  i = 1 \dots k $)  
 
−
is linearly expressed in terms of $  a _ {1} \dots a _ {i} $,  
 
−
i.e. $  b _ {i} = \sum _ {j=} 1  ^ {i} \gamma _ {ij} a _ {j} $,  
 
−
where $  C = \| \gamma _ {ij} \| $
 
−
is an upper-triangular matrix. It is possible to construct the system $  \{ b _ {i} \} $
 
−
such that it is orthonormal and such that the diagonal entries $  \gamma _ {ii} $
 
−
of $  C $
 
−
are positive; the system $  \{ b _ {i} \} $
 
−
and the matrix $  C $
 
−
are defined uniquely by these conditions.
 
  
−
The Gram–Schmidt process is as follows. Put $  b _ {1} = a _ {1} $;  
+
The Gram–Schmidt process is as follows. Put <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042015.png" />; if the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042016.png" /> have already been constructed, then
−
if the vectors $  b _ {1} \dots b _ {i} $
 
−
have already been constructed, then
 
  
−
$$
+
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042017.png" /></td> </tr></table>
−
b _ {i+} 1  = a _ {i+} 1 + \sum _ { j= } 1 ^ { i }  \alpha _ {j} b _ {j} ,
 
−
$$
 
  
 
where
 
where
  
−
$$
+
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"> ''α''<sub>''j''</sub> = - (''a''<sub>''i''+1</sub> , ''b''<sub>''j''</sub>) / (''b''<sub>''j''</sub> , ''b''<sub>''j''</sub>), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042018.pngWRONGEQUATION" /></td> </tr></table>
−
\alpha _ {j}  = -  
 
−
\frac{( a _ {j+} 1 , b _ {j} ) }{( b _ {j} , b _ {j} ) }
 
−
  ,
 
−
$$
 
  
−
$  j = 1 \dots i $,  
+
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042019.png" />, are obtained from the condition of orthogonality of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042020.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042021.png" />. The geometric sense of this process comprises the fact that at every step, the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042022.png" /> is perpendicular to the linear hull of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042023.png" /> drawn to the end of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042024.png" />. The product of the lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042025.png" /> is equal to the volume of the parallelepiped constructed on the vectors of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042026.png" /> as edges. By normalizing the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042027.png" />, the required orthonormal system is obtained. An explicit expression of the vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042028.png" /> in terms of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042029.png" /> is given by the formula
−
are obtained from the condition of orthogonality of the vector $  b _ {i+} 1 $
 
−
to $  b _ {1} \dots b _ {i} $.  
 
−
The geometric sense of this process comprises the fact that at every step, the vector $  b _ {i+} 1 $
 
−
is perpendicular to the linear hull of $  a _ {1} \dots a _ {i} $
 
−
drawn to the end of the vector $  a _ {i+} 1 $.  
 
−
The product of the lengths $  | b _ {1} | \dots | b _ {k} | $
 
−
is equal to the volume of the parallelepiped constructed on the vectors of the system $  \{ a _ {i} \} $
 
−
as edges. By normalizing the vectors $  b _ {i} $,  
 
−
the required orthonormal system is obtained. An explicit expression of the vectors $  b _ {i} $
 
−
in terms of $  a _ {1} \dots a _ {k} $
 
−
is given by the formula
 
  
−
$$
+
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042030.png" />/''G''<sub>''i''-1</sub></td> </tr></table>
−
b _ {i}  =  \left |
 
  
−
where $$
+
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042032.png" /> is the [[Gram determinant|Gram determinant]] of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042033.png" />, with ''G''<sub>0</sub>=1 by definition. (The determinant at the right-hand side has to be formally expanded by the last column).
−
q _ {i}  =
 
−
\frac{b _ {i} }{\sqrt {G _ {i-} 1 G _ {i} } }
 
−
,
 
−
$$
 
−
is the [[Gram determinant|Gram determinant]] of the system $  G _ {i} $,  
 
−
with ''G''<sub>0</sub>=1 by definition. (The determinant at the right-hand side has to be formally expanded by the last column).
 
  
 
The norm of these orthogonal vectors is given by ||''b''<sub>''i''</sub>||=SQRT(''G''<sub>''i''</sub>/''G''<sub>''i''-1</sub>). Thus, the corresponding orthonormal system takes the form
 
The norm of these orthogonal vectors is given by ||''b''<sub>''i''</sub>||=SQRT(''G''<sub>''i''</sub>/''G''<sub>''i''-1</sub>). Thus, the corresponding orthonormal system takes the form
  
−
$  a _ {1} \dots a _ {i} $
+
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o070/o070420/o07042031.png" /> · ''G''<sub>''i''-1</sub> = ''b''<sub>''i''</sub> · SQRT(''G''<sub>''i''-1</sub> / ''G''<sub>''i''</sub>) </td> </tr></table>
 +
 
  
 
This process can also be used for a countable system of vectors.
 
This process can also be used for a countable system of vectors.

Revision as of 14:52, 7 June 2020

orthogonalization process

An algorithm to construct for a given linear independent system of vectors in a Euclidean or Hermitian space an orthogonal system of non-zero vectors generating the same subspace in . The most well-known is the Schmidt (or Gram–Schmidt) orthogonalization process, in which from a linear independent system , an orthogonal system is constructed such that every vector () is linearly expressed in terms of , i.e. , where is an upper-triangular matrix. It is possible to construct the system such that it is orthonormal and such that the diagonal entries of are positive; the system and the matrix are defined uniquely by these conditions.

The Gram–Schmidt process is as follows. Put ; if the vectors have already been constructed, then

where

αj = - (ai+1 , bj) / (bj , bj),

, are obtained from the condition of orthogonality of the vector to . The geometric sense of this process comprises the fact that at every step, the vector is perpendicular to the linear hull of drawn to the end of the vector . The product of the lengths is equal to the volume of the parallelepiped constructed on the vectors of the system as edges. By normalizing the vectors , the required orthonormal system is obtained. An explicit expression of the vectors in terms of is given by the formula

/Gi-1

where is the Gram determinant of the system , with G0=1 by definition. (The determinant at the right-hand side has to be formally expanded by the last column).

The norm of these orthogonal vectors is given by ||bi||=SQRT(Gi/Gi-1). Thus, the corresponding orthonormal system takes the form

· Gi-1 = bi · SQRT(Gi-1 / Gi)


This process can also be used for a countable system of vectors.

The Gram–Schmidt process can be interpreted as expansion of a non-singular square matrix in the product of an orthogonal (or unitary, in the case of a Hermitian space) and an upper-triangular matrix with positive diagonal entries, this product being a particular example of an Iwasawa decomposition.

References

[1] F.R. [F.R. Gantmakher] Gantmacher, "The theory of matrices" , 1 , Chelsea, reprint (1977) (Translated from Russian)
[2] A.G. Kurosh, "Higher algebra" , MIR (1972) (Translated from Russian)
How to Cite This Entry:
Orthogonalization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Orthogonalization&oldid=48082
This article was adapted from an original article by I.V. Proskuryakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article
Retrieved from "https://encyclopediaofmath.org/index.php?title=Orthogonalization&oldid=49350"