Участник:DVIN - История изменений

DVIN: Полностью удалено содержимое страницы

2016-10-12T10:18:55Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 10:18, 12 октября 2016
Строка 1:		Строка 1:
	~~''' Ортогонализация Грамма-Шмидта '''~~

	~~== Свойства и структура алгоритмов ==~~
	~~=== Общее описание алгоритма ===~~
	~~=== Вычислительное ядро алгоритма ===~~
	~~=== Макроструктура алгоритма ===~~
	~~=== Схема реализации последовательного алгоритма ===~~
	~~=== Последовательная сложность алгоритма ===~~
	~~=== Информационный граф ===~~
	~~=== Ресурс параллелизма алгоритма ===~~
	~~=== Входные и выходные данные алгоритма ===~~
	~~=== Свойства алгоритма ===~~

	~~== Программная реализация алгоритма ==~~
	~~=== Особенности реализации последовательного алгоритма ===~~
	~~=== Локальность данных и вычислений ===~~
	~~=== Возможные способы и особенности параллельной реализации алгоритма ===~~
	~~=== Масштабируемость алгоритма и его реализации ===~~
	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~
	~~=== Выводы для классов архитектур ===~~
	~~=== Существующие реализации алгоритма ===~~

	~~== Литература ==~~

DVIN в 22:18, 13 сентября 2016

2016-09-13T22:18:03Z

@@ Строка 3: / Строка 3: @@
 == Свойства и структура алгоритмов ==
 === Общее описание алгоритма ===
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===

DVIN: Новая страница: «''' Ортогонализация Грамма-Шмидта ''' == Свойства и структура алгоритмов == === Общее описани…»

2016-09-13T21:57:35Z

Новая страница: «''' Ортогонализация Грамма-Шмидта ''' == Свойства и структура алгоритмов == === Общее описани…»

Новая страница

''' Ортогонализация Грамма-Шмидта '''

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===
Процесс Грама-Шмидта — это один из алгоритмов, в которых на основе счётного множества линейно независимых векторов <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>.
=== Математическое описание алгоритма ===
Пусть имеются линейно независимые векторы <math>\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N</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}</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}_1 & (2) \\
\mathbf{b}_3 & = & \mathbf{a}_3-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_1-\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_2 & (3) \\
\mathbf{b}_4 & = & \mathbf{a}_4-\mathbf{proj}_{\mathbf{b}_1}\,\mathbf{a}_1-\mathbf{proj}_{\mathbf{b}_2}\,\mathbf{a}_2-\mathbf{proj}_{\mathbf{b}_3}\,\mathbf{a}_3 & (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>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> — система ортогональных векторов либо

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

Вычисление <math>\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N</math> носит название ортогонализации Грама — Шмидта, а <math>\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N</math> — ортонормализации Грама — Шмидта.

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==