Method level

Difference between revisions of "Orthogonalization method"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][quality revision]
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{level-m}}
 
{{level-m}}
  
The basic authors of the description: [[Участник:DVIN|Инжелевская Дарья Валерьевна]](text), [[Участник:Frolov|А.В.Фролов]](editing)  
+
The basic authors of the description: [[:ru:Участник:DVIN|Daria Inzhelevskaya]](text), [[:ru:Участник:Frolov|Alexey Frolov]](editing)  
  
'''Gram--Schmidt orthogonalization''' is a method that constructs a set of orthogonal vectors <math>{\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} </math> or a set of orthonormal vectors <math>{\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} </math> from a given set of linearly independent vectors <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}</math>.  
+
The '''Gram--Schmidt orthogonalization''' is a method that constructs a set of orthogonal vectors <math>{\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} </math> or a set of orthonormal vectors <math>{\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} </math> from a given set of linearly independent vectors <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}</math>. This is done in such a way that each vector
 +
<math>{\displaystyle \mathbf {b} _{j}} </math> or <math>{\displaystyle \mathbf {e} _{j}}</math> is a linear combination of the vectors <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}</math>. The process may be used for obtaining the [[QR decomposition of dense nonsingular matrices|QR decomposition]], where the system of original vectors is the columns of a given matrix, while the columns of Q are the result of orthogonalization. Thus, unlike the Givens (rotation) and Householder (reflection) methods, which are based on the left unitary/orthogonal reduction to triangular form, the orthogonalization method reduces the original matrix by right non-orthogonal (triangular) transformations to a unitary/orthogonal matrix.
  
строится множество ортогональных векторов <math>{\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} </math> или ортонормированных векторов <math>{\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} </math>, причём так, что каждый вектор <math>{\displaystyle \mathbf {b} _{j}} </math> или <math>{\displaystyle \mathbf {e} _{j}}</math> может быть выражен линейной комбинацией векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}</math>. Данный процесс может быть использован для получения [[QR-разложения плотных неособенных матриц|QR-разложения]], в которой систему исходных векторов образуют столбцы исходной матрицы, а столбцы матрицы Q представляют из себя набор полученных при ортогонализации векторов. Таким образом, в отличие от методов Гивенса (вращений) и Хаусхолдера (отражений), основанных на приведении матрицы левыми унитарными/ортогональными преобразованиями к треугольному виду, метод ортогонализации основан на приведении матрицы правыми неортогональными (можно сказать, треугольными) преобразованиями к унитарному/ортогональному виду.
+
== Mathematical foundations of the method ==
  
== Математические основы метода ==
+
The [[Classical orthogonalization method|classical orthogonalization method for the QR decomposition of a square matrix (real version)]] is fairly simple. However, due to its instability, which manifests itself in the non-orthogonality of resulting systems, the method is very rarely used in practice. 
  
[[Классический метод ортогонализации|Классический метод ортогонализации QR-разложения квадратной матрицы (вещественный вариант)]] довольно прост, однако из-за неустойчивости, проявляющейся в неортогональности получаемых систем, крайне редко применяется на практике.
+
Let <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math> be linearly independent vectors. Define the projection of a vector <math>\mathbf{a}</math> on (the direction of) a vector <math>\mathbf{b}</math> by the formula <math>\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,</math>
  
Пусть имеются линейно независимые векторы <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</math>.
+
where <math>\langle \mathbf{a}, \mathbf{b} \rangle</math> is the scalar product of the vectors <math>\mathbf{a}</math> and <math>\mathbf{b}</math>.
Пусть оператор проекции вектора <math>\mathbf{a}</math> на вектор <math>\mathbf{b}</math> определён следующим образом: <math>\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,</math>
 
  
где <math>\langle \mathbf{a}, \mathbf{b} \rangle</math> — скалярное произведение векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math>.
+
In the '''''k'''''-dimensional real space, the scalar product of the vectors <math>\mathbf{ a= [a_1, a_2, ...,a_k]}</math> and <math>\mathbf{ b= [b_1, b_2, ..., b_k]}</math> is defined as
 
 
Скалярное произведение для двух векторов  <math>\mathbf{ a= [a_1, a_2, ...,a_k]}</math> и <math>\mathbf{ b= [b_1, b_2, ..., b_k]}</math> в '''''k'''''-мерном действительном пространстве определяется как:
 
 
:<math>\langle \mathbf{a}, \mathbf{b} \rangle=\sum_{i=1}^k a_ib_i=a_1b_1+a_2b_2+\cdots+ a_kb_k</math>.
 
:<math>\langle \mathbf{a}, \mathbf{b} \rangle=\sum_{i=1}^k a_ib_i=a_1b_1+a_2b_2+\cdots+ a_kb_k</math>.
  
Этот оператор проецирует вектор <math>\mathbf{a}</math> коллинеарно вектору <math>\mathbf{b}</math>.
+
The above operator projects the vector <math>\mathbf{a}</math> on the direction of the vector <math>\mathbf{b}</math>.
  
Ортогональность векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math> достигается на шаге (2).
+
The orthogonality of the first two vectors in the orthogonalization process below is attained at Step (2).
  
Классический процесс Грама — Шмидта выполняется следующим образом:
+
The classical Gram--Schmidt process is performed as follows:
  
 
: <math>
 
: <math>
Line 36: Line 34:
  
  
На основе каждого вектора <math>\mathbf{b}_j \;(j = 1 \ldots N)</math> может быть получен нормированный вектор: <math>\mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|}</math> (у нормированного вектора направление будет таким же, как у исходного, а норма — единичной). Норма в формуле - согласованная со скалярным произведением: <math>\| x \| = \sqrt{\langle x, x \rangle}</math>
+
From each vector <math>\mathbf{b}_j \;(j = 1 \ldots N)</math>, one can obtain a normalized vector: <math>\mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|}</math> (the normalized vector has the same direction as the original one, while its norm is 1 ). Here, the norm is consistent with the scalar product: <math>\| x \| = \sqrt{\langle x, x \rangle}</math>
 
 
Результаты процесса Грама — Шмидта:
 
  
<math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> — система ортогональных векторов либо
+
The output of the Gram--Schmidt process:
  
<math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — система ортонормированных векторов.
+
The system <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> of orthogonal vectors or the system <math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> of orthonormal vectors.
  
Наиболее используемой на практике формой метода является [[Метод ортогонализации с переортогонализацией|вариант метода ортогонализации с переортогонализацией]].
+
In practice, the most often used form of the method is the [[Метод ортогонализации с переортогонализацией|orthogonalization method with re-orthogonalization]].
  
 
[[Category:Finished articles]]
 
[[Category:Finished articles]]
  
 
[[ru:Метод ортогонализации]]
 
[[ru:Метод ортогонализации]]

Latest revision as of 16:58, 16 March 2018


The basic authors of the description: Daria Inzhelevskaya(text), Alexey Frolov(editing)

The Gram--Schmidt orthogonalization is a method that constructs a set of orthogonal vectors [math]{\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} [/math] or a set of orthonormal vectors [math]{\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} [/math] from a given set of linearly independent vectors [math]{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}[/math]. This is done in such a way that each vector [math]{\displaystyle \mathbf {b} _{j}} [/math] or [math]{\displaystyle \mathbf {e} _{j}}[/math] is a linear combination of the vectors [math]{\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}[/math]. The process may be used for obtaining the QR decomposition, where the system of original vectors is the columns of a given matrix, while the columns of Q are the result of orthogonalization. Thus, unlike the Givens (rotation) and Householder (reflection) methods, which are based on the left unitary/orthogonal reduction to triangular form, the orthogonalization method reduces the original matrix by right non-orthogonal (triangular) transformations to a unitary/orthogonal matrix.

Mathematical foundations of the method

The classical orthogonalization method for the QR decomposition of a square matrix (real version) is fairly simple. However, due to its instability, which manifests itself in the non-orthogonality of resulting systems, the method is very rarely used in practice.

Let [math]\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N[/math] be linearly independent vectors. Define the projection of a vector [math]\mathbf{a}[/math] on (the direction of) a vector [math]\mathbf{b}[/math] by the formula [math]\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,[/math]

where [math]\langle \mathbf{a}, \mathbf{b} \rangle[/math] is the scalar product of the vectors [math]\mathbf{a}[/math] and [math]\mathbf{b}[/math].

In the k-dimensional real space, the scalar product of the vectors [math]\mathbf{ a= [a_1, a_2, ...,a_k]}[/math] and [math]\mathbf{ b= [b_1, b_2, ..., b_k]}[/math] is defined as

[math]\langle \mathbf{a}, \mathbf{b} \rangle=\sum_{i=1}^k a_ib_i=a_1b_1+a_2b_2+\cdots+ a_kb_k[/math].

The above operator projects the vector [math]\mathbf{a}[/math] on the direction of the vector [math]\mathbf{b}[/math].

The orthogonality of the first two vectors in the orthogonalization process below is attained at Step (2).

The classical Gram--Schmidt process is performed as follows:

[math] {\begin{array}{lclr} {\mathbf {b}}_{1}&=&{\mathbf {a}}_{1}&(1)\\ {\mathbf {b}}_{2}&=&{\mathbf {a}}_{2}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{2}&(2)\\ {\mathbf {b}}_{3}&=&{\mathbf {a}}_{3}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{3}-{\mathbf {proj}}_{{{\mathbf {b}}_{2}}}\,{\mathbf {a}}_{3}&(3)\\ {\mathbf {b}}_{4}&=&{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{2}}}\,{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{3}}}\,{\mathbf {a}}_{4}&(4)\\ &\vdots &&\\{\mathbf {b}}_{N}&=&{\mathbf {a}}_{N}-\displaystyle \sum _{{j=1}}^{{N-1}}{\mathbf {proj}}_{{{\mathbf {b}}_{j}}}\,{\mathbf {a}}_{N}&(N) \end{array}} [/math]


From each vector [math]\mathbf{b}_j \;(j = 1 \ldots N)[/math], one can obtain a normalized vector: [math]\mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|}[/math] (the normalized vector has the same direction as the original one, while its norm is 1 ). Here, the norm is consistent with the scalar product: [math]\| x \| = \sqrt{\langle x, x \rangle}[/math]

The output of the Gram--Schmidt process:

The system [math]\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N[/math] of orthogonal vectors or the system [math]\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N[/math] of orthonormal vectors.

In practice, the most often used form of the method is the orthogonalization method with re-orthogonalization.