Уровень метода

Метод ортогонализации: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[досмотренная версия][выверенная версия]
(Новая страница: «{{level-m}} '''Ортогонализация Грама-Шмидта''' — это один из методов, в которых на основе множес…»)
 
 
(не показано 7 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{level-m}}
 
{{level-m}}
 +
 +
Основные авторы описания: [[Участник:DVIN|Инжелевская Дарья Валерьевна]](текст), [[Участник:Frolov|А.В.Фролов]](общая редактура)
 +
 
'''Ортогонализация Грама-Шмидта''' — это один из методов, в которых на основе множества линейно независимых векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}</math> строится множество ортогональных векторов <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 представляют из себя набор полученных при ортогонализации векторов. Таким образом, в отличие от методов Гивенса (вращений) и Хаусхолдера (отражений), основанных на приведении матрицы левыми унитарными/ортогональными преобразованиями к треугольному виду, метод ортогонализации основан на приведении матрицы правыми неортогональными (можно сказать, треугольными) преобразованиями к унитарному/ортогональному виду.
 
'''Ортогонализация Грама-Шмидта''' — это один из методов, в которых на основе множества линейно независимых векторов <math>{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}</math> строится множество ортогональных векторов <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 представляют из себя набор полученных при ортогонализации векторов. Таким образом, в отличие от методов Гивенса (вращений) и Хаусхолдера (отражений), основанных на приведении матрицы левыми унитарными/ортогональными преобразованиями к треугольному виду, метод ортогонализации основан на приведении матрицы правыми неортогональными (можно сказать, треугольными) преобразованиями к унитарному/ортогональному виду.
 +
 +
== Математические основы метода ==
 +
 +
[[Классический метод ортогонализации|Классический метод ортогонализации QR-разложения квадратной матрицы (вещественный вариант)]] довольно прост, однако из-за неустойчивости, проявляющейся в неортогональности получаемых систем, крайне редко применяется на практике.
 +
 +
Пусть имеются линейно независимые векторы <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</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>.
 +
 +
Скалярное произведение для двух векторов  <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>\mathbf{a}</math> коллинеарно вектору <math>\mathbf{b}</math>.
 +
 +
Ортогональность векторов <math>\mathbf{a}</math> и <math>\mathbf{b}</math> достигается на шаге (2).
 +
 +
Классический процесс Грама — Шмидта выполняется следующим образом:
 +
 +
: <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>
 +
 +
 +
На основе каждого вектора <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>
 +
 +
Результаты процесса Грама — Шмидта:
 +
 +
<math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> — система ортогональных векторов либо
 +
 +
<math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — система ортонормированных векторов.
 +
 +
Наиболее используемой на практике формой метода является [[Метод ортогонализации с переортогонализацией|вариант метода ортогонализации с переортогонализацией]].
 +
 +
[[Категория:Законченные статьи]]
 +
 +
[[en:Orthogonalization method]]

Текущая версия на 16:59, 16 марта 2018


Основные авторы описания: Инжелевская Дарья Валерьевна(текст), А.В.Фролов(общая редактура)

Ортогонализация Грама-Шмидта — это один из методов, в которых на основе множества линейно независимых векторов [math]{\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}[/math] строится множество ортогональных векторов [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-разложения, в которой систему исходных векторов образуют столбцы исходной матрицы, а столбцы матрицы Q представляют из себя набор полученных при ортогонализации векторов. Таким образом, в отличие от методов Гивенса (вращений) и Хаусхолдера (отражений), основанных на приведении матрицы левыми унитарными/ортогональными преобразованиями к треугольному виду, метод ортогонализации основан на приведении матрицы правыми неортогональными (можно сказать, треугольными) преобразованиями к унитарному/ортогональному виду.

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

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

Пусть имеются линейно независимые векторы [math]\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N[/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].

Скалярное произведение для двух векторов [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]\mathbf{a}[/math] коллинеарно вектору [math]\mathbf{b}[/math].

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

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

[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]


На основе каждого вектора [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]

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

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

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

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