Method level

Difference between revisions of "Orthogonalization method"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][unchecked revision]
Line 3: Line 3:
 
The basic authors of the description: [[Участник:DVIN|Инжелевская Дарья Валерьевна]](text), [[Участник:Frolov|А.В.Фролов]](editing)  
 
The basic authors of the description: [[Участник:DVIN|Инжелевская Дарья Валерьевна]](text), [[Участник: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-разложения плотных неособенных матриц|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 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 представляют из себя набор полученных при ортогонализации векторов. Таким образом, в отличие от методов Гивенса (вращений) и Хаусхолдера (отражений), основанных на приведении матрицы левыми унитарными/ортогональными преобразованиями к треугольному виду, метод ортогонализации основан на приведении матрицы правыми неортогональными (можно сказать, треугольными) преобразованиями к унитарному/ортогональному виду.
 
  
 
== Математические основы метода ==
 
== Математические основы метода ==

Revision as of 17:56, 5 March 2018


The basic authors of the description: Инжелевская Дарья Валерьевна(text), А.В.Фролов(editing)

The Gram--Schmidt orthogonalization is a method that constructs a set of orthogonal vectors {\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}} or a set of orthonormal vectors {\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}} from a given set of linearly independent vectors {\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}. This is done in such a way that each vector {\displaystyle \mathbf {b} _{j}} or {\displaystyle \mathbf {e} _{j}} is a linear combination of the vectors {\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}. 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 matrix by right non-orthogonal (triangular) transformations to a unitary/orthogonal matrix.

Математические основы метода

Классический метод ортогонализации QR-разложения квадратной матрицы (вещественный вариант) довольно прост, однако из-за неустойчивости, проявляющейся в неортогональности получаемых систем, крайне редко применяется на практике.

Пусть имеются линейно независимые векторы \mathbf{a}_1,\;\ldots,\;\mathbf{a}_N. Пусть оператор проекции вектора \mathbf{a} на вектор \mathbf{b} определён следующим образом: \mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,

где \langle \mathbf{a}, \mathbf{b} \rangle — скалярное произведение векторов \mathbf{a} и \mathbf{b}.

Скалярное произведение для двух векторов \mathbf{ a= [a_1, a_2, ...,a_k]} и \mathbf{ b= [b_1, b_2, ..., b_k]} в k-мерном действительном пространстве определяется как:

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

Этот оператор проецирует вектор \mathbf{a} коллинеарно вектору \mathbf{b}.

Ортогональность векторов \mathbf{a} и \mathbf{b} достигается на шаге (2).

Классический процесс Грама — Шмидта выполняется следующим образом:

{\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}}


На основе каждого вектора \mathbf{b}_j \;(j = 1 \ldots N) может быть получен нормированный вектор: \mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|} (у нормированного вектора направление будет таким же, как у исходного, а норма — единичной). Норма в формуле - согласованная со скалярным произведением: \| x \| = \sqrt{\langle x, x \rangle}

Результаты процесса Грама — Шмидта:

\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N — система ортогональных векторов либо

\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N — система ортонормированных векторов.

Наиболее используемой на практике формой метода является вариант метода ортогонализации с переортогонализацией.