Участник:Pandvik/Ортогонализация Грама - Шмидта - История изменений

Frolov в 06:41, 15 декабря 2016

2016-12-15T06:41:17Z

← Предыдущая версия		Версия от 06:41, 15 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|ASA}}		{{Assignment\|ASA\|Frolov}}

	Авторы описания алгоритма: [[Участник:Pandvik\|Павлов Андрей]] (разделы [1.7], [1.8], [2.4], [2.7], [3] - поиск и изучение литературы), [[Участник:Vvf63\|Филимонов Владимир]] (разделы [1.1]-[1.6], [1.9], [1.10], [2.7], [3] - поиск и изучение литературы).		Авторы описания алгоритма: [[Участник:Pandvik\|Павлов Андрей]] (разделы [1.7], [1.8], [2.4], [2.7], [3] - поиск и изучение литературы), [[Участник:Vvf63\|Филимонов Владимир]] (разделы [1.1]-[1.6], [1.9], [1.10], [2.7], [3] - поиск и изучение литературы).

Vvf63: /* Масштабируемость реализации алгоритма */

2016-12-14T20:42:59Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 20:42, 14 декабря 2016
Строка 200:		Строка 200:
	Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].		Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл. В., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. В., Практика суперкомпьютера «Ломоносов», Москва: «Открытые системы», 2012~~, N 7, С. 36-39.~~</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл. В., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. В., Практика суперкомпьютера «Ломоносов», Москва: «Открытые системы», 2012</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Vvf63: /* Общее описание алгоритма */

2016-12-14T20:38:22Z

Общее описание алгоритма

← Предыдущая версия		Версия от 20:38, 14 декабря 2016
Строка 18:		Строка 18:
	Процесс ортогонализации Грама-Шмидта используется для квадратных невырожденных матриц, которые преобразуются, либо уже преобразованы, к верхнему(нижнему) треугольному виду.		Процесс ортогонализации Грама-Шмидта используется для квадратных невырожденных матриц, которые преобразуются, либо уже преобразованы, к верхнему(нижнему) треугольному виду.

	Процесс ортогонализации Грама-Шмидта нашёл применение в оптимизации оценивания параметров моделей управления объектом<ref>А.Е. Карелин, А.А. Светлаков, Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления, Томск: Томский политехнический университет, 2006</ref>, в протоколах безопасности<ref>А.В. Пискова, А. А. Менщиков, А.Г. Коробейников, Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решётки для протоколов безопасности, Санкт-Петербург: НИУ ИТМО, 2016</ref>, в обработке сигналов<ref>~~МГУ ВМК,~~ Ф.Ф. Дедус, Л.И. Куликова, А.Н. Панкратов, Р.К. Тетуев, Классические ортогональные базисы в задачах аналитического описания и обработки информационных сигналов, Москва: МГУ ВМК, 2009</ref>, в вычислении локальных минимумов целочисленных решёток и многом другом.		Процесс ортогонализации Грама-Шмидта нашёл применение в оптимизации оценивания параметров моделей управления объектом<ref>А.Е. Карелин, А.А. Светлаков, Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления, Томск: Томский политехнический университет, 2006</ref>, в протоколах безопасности<ref>А.В. Пискова, А. А. Менщиков, А.Г. Коробейников, Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решётки для протоколов безопасности, Санкт-Петербург: НИУ ИТМО, 2016</ref>, в обработке сигналов<ref>Ф.Ф. Дедус, Л.И. Куликова, А.Н. Панкратов, Р.К. Тетуев, Классические ортогональные базисы в задачах аналитического описания и обработки информационных сигналов, Москва: МГУ ВМК, 2009</ref>, в вычислении локальных минимумов целочисленных решёток и многом другом.

	Обычно, процесс ортогонализации используется как промежуточный шаг в других алгоритмах для уменьшения количества вычислений.		Обычно, процесс ортогонализации используется как промежуточный шаг в других алгоритмах для уменьшения количества вычислений.

Vvf63: /* Математическое описание алгоритма */

2016-12-14T20:31:42Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 20:31, 14 декабря 2016
Строка 43:		Строка 43:
	Результаты процесса ортогонализации Грама-Шмидта: <math>\mathbf{b}_1\cdots\mathbf{b}_N</math> - система ортогональных векторов либо система ортонормированных векторов <math>\mathbf{e}_1\cdots\mathbf{e}_N</math>.		Результаты процесса ортогонализации Грама-Шмидта: <math>\mathbf{b}_1\cdots\mathbf{b}_N</math> - система ортогональных векторов либо система ортонормированных векторов <math>\mathbf{e}_1\cdots\mathbf{e}_N</math>.

	Подробное описание можно найти в <ref>А.Н. Канатников, А.П.Крищенко, Линейная Алгебра, Москва: ~~Изд-во~~ МГТУ им. Н.Э. Баумана, 2002</ref> <ref>Jim Lambers, Gram-Schmidt Orthogonalization, The University of Southern Mississippi, Department of Mathematics, 2014</ref>.		Подробное описание можно найти в <ref>А.Н. Канатников, А.П.Крищенко, Линейная Алгебра, Москва: МГТУ им. Н.Э. Баумана, 2002</ref> <ref>Jim Lambers, Gram-Schmidt Orthogonalization, The University of Southern Mississippi, Department of Mathematics, 2014</ref>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

Vvf63: /* Масштабируемость реализации алгоритма */

2016-12-14T20:30:41Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 20:30, 14 декабря 2016
Строка 200:		Строка 200:
	Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].		Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл. В., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. В. Практика суперкомпьютера «Ломоносов», Москва: «Открытые системы», 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл. В., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. В., Практика суперкомпьютера «Ломоносов», Москва: «Открытые системы», 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Vvf63: /* Масштабируемость реализации алгоритма */

2016-12-14T20:30:04Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 20:30, 14 декабря 2016
Строка 200:		Строка 200:
	Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].		Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл. В., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. В. Практика суперкомпьютера «Ломоносов», Москва: ~~"Открытые системы"~~, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл. В., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. В. Практика суперкомпьютера «Ломоносов», Москва: «Открытые системы», 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Vvf63: /* Масштабируемость реализации алгоритма */

2016-12-14T20:29:18Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 20:29, 14 декабря 2016
Строка 200:		Строка 200:
	Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].		Теоретические оценки предела масштабируемости алгоритма были рассмотрены в разделе [[#Ресурс параллелизма алгоритма]].
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл. В., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. В. Практика суперкомпьютера «Ломоносов», Москва: "Открытые системы", 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Vvf63: /* Математическое описание алгоритма */

2016-12-14T20:24:01Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 20:24, 14 декабря 2016
Строка 43:		Строка 43:
	Результаты процесса ортогонализации Грама-Шмидта: <math>\mathbf{b}_1\cdots\mathbf{b}_N</math> - система ортогональных векторов либо система ортонормированных векторов <math>\mathbf{e}_1\cdots\mathbf{e}_N</math>.		Результаты процесса ортогонализации Грама-Шмидта: <math>\mathbf{b}_1\cdots\mathbf{b}_N</math> - система ортогональных векторов либо система ортонормированных векторов <math>\mathbf{e}_1\cdots\mathbf{e}_N</math>.

	Подробное описание можно найти в <ref>А.Н. Канатников, А.П.Крищенко, Линейная Алгебра, М.: Изд-во МГТУ им. Н.Э. Баумана, 2002</ref> <ref>Jim Lambers, Gram-Schmidt Orthogonalization, The University of Southern Mississippi, Department of Mathematics, 2014</ref>.		Подробное описание можно найти в <ref>А.Н. Канатников, А.П.Крищенко, Линейная Алгебра, Москва: Изд-во МГТУ им. Н.Э. Баумана, 2002</ref> <ref>Jim Lambers, Gram-Schmidt Orthogonalization, The University of Southern Mississippi, Department of Mathematics, 2014</ref>.

	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

Vvf63: /* Общее описание алгоритма */

2016-12-14T20:22:35Z

Общее описание алгоритма

← Предыдущая версия		Версия от 20:22, 14 декабря 2016
Строка 18:		Строка 18:
	Процесс ортогонализации Грама-Шмидта используется для квадратных невырожденных матриц, которые преобразуются, либо уже преобразованы, к верхнему(нижнему) треугольному виду.		Процесс ортогонализации Грама-Шмидта используется для квадратных невырожденных матриц, которые преобразуются, либо уже преобразованы, к верхнему(нижнему) треугольному виду.

	Процесс ортогонализации Грама-Шмидта нашёл применение в оптимизации оценивания параметров моделей управления объектом<ref>А.Е. Карелин, А.А. Светлаков, Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления, Томский политехнический университет, 2006</ref>, в протоколах безопасности<ref>А.В. Пискова, А. А. Менщиков, А.Г. Коробейников, Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решётки для протоколов безопасности, Санкт-Петербург: НИУ ИТМО, 2016</ref>, в обработке сигналов<ref>МГУ ВМК, Ф.Ф. Дедус, Л.И. Куликова, А.Н. Панкратов, Р.К. Тетуев, Классические ортогональные базисы в задачах аналитического описания и обработки информационных сигналов, Москва: МГУ ВМК, 2009</ref>, в вычислении локальных минимумов целочисленных решёток и многом другом.		Процесс ортогонализации Грама-Шмидта нашёл применение в оптимизации оценивания параметров моделей управления объектом<ref>А.Е. Карелин, А.А. Светлаков, Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления, Томск: Томский политехнический университет, 2006</ref>, в протоколах безопасности<ref>А.В. Пискова, А. А. Менщиков, А.Г. Коробейников, Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решётки для протоколов безопасности, Санкт-Петербург: НИУ ИТМО, 2016</ref>, в обработке сигналов<ref>МГУ ВМК, Ф.Ф. Дедус, Л.И. Куликова, А.Н. Панкратов, Р.К. Тетуев, Классические ортогональные базисы в задачах аналитического описания и обработки информационных сигналов, Москва: МГУ ВМК, 2009</ref>, в вычислении локальных минимумов целочисленных решёток и многом другом.

	Обычно, процесс ортогонализации используется как промежуточный шаг в других алгоритмах для уменьшения количества вычислений.		Обычно, процесс ортогонализации используется как промежуточный шаг в других алгоритмах для уменьшения количества вычислений.

Vvf63: /* Общее описание алгоритма */

2016-12-14T20:20:38Z

Общее описание алгоритма

← Предыдущая версия		Версия от 20:20, 14 декабря 2016
Строка 14:		Строка 14:
	В конечномерном евклидовом пространстве существует ортонормированный базис.		В конечномерном евклидовом пространстве существует ортонормированный базис.

	Для доказательства этого факта требуется находить и строить такие базисы. Построить ортонормированный базис можно, отталкиваясь от некоторого исходного базиса, при помощи алгоритма, который называют процессом ортогонализации Грама — Шмидта<ref>А.А. Самарский, А.В. Гулин, Численные методы, Москва «НАУКА», 1989</ref>.		Для доказательства этого факта требуется находить и строить такие базисы. Построить ортонормированный базис можно, отталкиваясь от некоторого исходного базиса, при помощи алгоритма, который называют процессом ортогонализации Грама — Шмидта<ref>А.А. Самарский, А.В. Гулин, Численные методы, Москва: «НАУКА», 1989</ref>.

	Процесс ортогонализации Грама-Шмидта используется для квадратных невырожденных матриц, которые преобразуются, либо уже преобразованы, к верхнему(нижнему) треугольному виду.		Процесс ортогонализации Грама-Шмидта используется для квадратных невырожденных матриц, которые преобразуются, либо уже преобразованы, к верхнему(нижнему) треугольному виду.