МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
Пояснительная записка к курсовому проекту по дисциплине
«Методы численного анализа»
на тему «Ортогональное разложение матриц и его применения»
Выполнил: Бенько И.С.,
ст.гр. 852002
Принял: Хотеев А. Л.
Минск, 2010
Оглавление
1.Теоретические сведения 3
1.1Преобразование Хаусхолдера. 3
1.2. QR-разложение матриц 5
1.3. Преобразование Гивенса 7
2.Практические применения 11
2.1. Метод отражений решения СЛАУ 11
3.Примеры и пояснение работы программы (язык C#) 13
3.1. Что реализовано в модулях программы? 13
3.2.Примеры работы программы 15
4.Решение СЛАУ методом отражений 17
4.1. Решение примера вручную 17
5.Список литературы 19
-
Теоретические сведения
В евклидовом n-мерном пространстве рассматриваются два ортогональных преобразования: преобразование отражения Хаусхолдера и преобразование плоских вращений Гивенса. В качестве примера применения преобразований Хаусхолдера изучается метод отражений для решения систем линейных алгебраических уравнений. Главный упор делается на использование ортогональных преобразований в задаче нахождения всех собственных числе (в том числе кратных и комплексны) произвольных квадратных матриц умеренных размеров с вещественными элементами.
-
Преобразование Хаусхолдера.
Пусть w – некоторый фиксированный вектор (столбец) евклидова пространства со скалярным произведением , такой, что
(1.1.1)
Образованная с его помощью – матрица
(1.1.2)
называется матрицей Хаусхолдера.
Чтобы выявить простейшие геометрические свойства преобразования Хаусхолдера, осуществляемого посредством матрицы , посмотрим, что представляет собой вектор , служащий при этом преобразовании образом произвольного вектора :
(1.1.3)
Если взять коллинеарным , т.е. , где , то в силу (1.1.1), имеем . В таком случае, согласно (1.1.3), получаем
Если же перпендикулярно , то и, значит, из (1.1.3) следует, что .
Итак, преобразование Хасхолдера действует на векторы -мерного евклидова пространства следующим образом: векторы, ортогональные определяющему матрицу Хасухолдера (1.1.2) вектору w, оно оставляет неизменными, а векторы, коллинеарные w, переводит в противоположные – отражает. Отсюда проистекают другие названия матрицы и соответствующего ей преобразования – матрица и преобразование отражения.
Непосредственным перемножением вектора на вектор находим:
Очевидная симметричность матрицы влечет симметричность матрицы . Пользуясь этим, имеем
(поскольку , в силу (1.1.1)). Полученное в итоге равенство означает, что матрица Хаусхолдера – ортогональная.
Одним из важнейших свойство ортогональных преобразований является сохранение длин преобразуемых векторов. Благодаря этому свойству, согласно вышепоказанному,, можно утверждать, что
, (1.1.4)
Равенство (1.1.4) играет существенную роль для конкретизации векторов при построении матриц Хаусхолдера, таких, чтобы преобразованиями с их помощью достичь определенных целей.
1.2. QR-разложение матриц
Поставим теперь следующую задачу: ортогональными преобразованиями привести -матрицу к треугольному виду. Иначе, осуществить -разложение матрицы , т.е. описать процедуру, посредством которой получается равенство
,
Где – ортогональная матрица, а – правая треугольная.
Будем решать эту задачу поэтапно.
На первом этапе отдадим роль преобразуемого вектора в предыдущих рассуждениях и формулах первому столбцу матрицы . Согласно им, построив матрицу Хасухолдерас помощью вектора
И скаляров
,
И применив ее к матрице , получим матрицу
Со столбцом нулей под первым диагональным элементом, т.е. матрицу вида
(где )
На втором этапе нужно поступить таким же образом с подматрицей матрицы , которая получается вычеркиванием в первой строки и первого столбца. Легко проверить, что это равносильно применению ко всей матрице преобразования Хаусхолдера, определяемого формулами
,
,
Для этого достаточно лишь убедиться, что матрица имеет структуру вида
Означающего неизменность первых строки и столбца при выполнении преобразования
Результат первых двух этапов – это матрица
Ясно, что для приведения данной -матрицы к треугольному виду потребуется таких этапов, причем -й этап определяется формулами:
,
Итог всей процедуры из этапов – матрица треугольного вида
Где через обозначена матрица, представляющая собой произведение ортогональных матриц Хаусхолдера . Так как произведением ортогональных матриц является матрица, тоже ортогональная, то равенство можно обратить умножением слева на .
Теорема (о QR-разложении). Преобразованиями Хаусхолдера любая квадратная матрица с вещественными элементами может быть представлена в виде произведения вещественных ортогональной и правой треугольной матриц.
1.3. Преобразование Гивенса
Преобразование Гивенса определяется матрицами плоских вращений вида
(1.3.1)
Матрица при фиксированном отличается от единичной -матрицы лишь тем, что в -подматрица . Занимающая клетку, образованную пересечением -х и -х строк и столбцов, заменяется подматрицей
С элементами и , удовлетворяющими условию
. (1.3.2)
С этим условием нормировка матрица и соответственно матрица являются ортогональными и, кроме того, оправдывают название выполняемого посредством преобразования – преобразования плоских вращений, поскольку элементы и можно интерпретировать как косинус и синус некоторого угла преобразования поворота.
Имя возможность наложить еще одно условие на и в преобразовании Гивенса, распорядимся этой свободой так, чтобы с помощью последовательности таких ортогональных преобразований матрицами вида (1.3.1) матрицу Хесенберга удалось привести к правому треугольному виду, последовательно аннулируя поддиагональные элементы в первом, второй, …, -м столбцах.
С этой целью предположим, что уже сделаны таких шагов, в результате чего получена матрица
Найдем произведение матрицы на матрицу полагая в из (1.3.1) . Приходим к матрице с измененными элементами по сравнению с матрицей только в -й и в -строках. Потребуем, чтобы единственный ненулевой поддиагональный элемент -го столбца матрицы обратился в нуль, т.е. подберем числа , связанные, согласно (1.3.2) соотношением так, что
Отсюда получаем
(1.3.3)
- значение тангенса угла поворота в плоскости, определяемой -м и -м ортами.
Очевидно, что если на -м шаге окажется , то можно принять , т.е. положить . В противном случае, учитывая (1.3.1), вычисляем по формулам:
Предварительно подсчитав с помощью (1.3.3). После пересчета диагональных и стоящих правее них элементов -й и -й строк по формулам
Матрица будет готова к выполнению следующего шага преобразований Гивенса.
Таким образом совокупность этих формул, в которых натуральной переменной последовательно придаются значения , полностью определяет процесс приведения матрицы Хессенберга к матрице правой треугольной формы, осуществляемый преобразованиями .
-
Практические применения
2.1. Метод отражений решения СЛАУ
Одним из возможных приложений полученного способа разложения квадратной матрицы в произведений ортогональной и треугольной матриц является метод решения систем линейных алгебраических уравнений, носящий название метод отражений.
Пусть дана система
(2.1.1)
С вещественным вектором правой части , вектором неизвестных и вещественной матрицей коэффициентов
Рассмотрим две ситуации.
-
Предположим, что уже известно ортогональное разложение матрицы :
, (2.1.2)
Где -ортогональная, а - правая треугольная матрицы. Тогда после его подстановки в (2.1.1) имеем эквивалентную систему
Которая, в свою очередь, ввиду ортогональности симметричной матрицы , равносильна системе
. (2.1.3)
Обозначив систему (2.1.3) можно переписать в виде
(2.1.4)
Из чего следует, что для получения искомого решения теперь достаточно выполнить обратный ход метода Гаусса.
-
Будем теперь исходить из того, что готового QR-разложения матрицы нет и, вообще говоря, оно в явном виде не требуется ,а нужно получить решение системы (2.1.1), используя преобразование отражения.
Промежуточной целью здесь опять является приведение данной СЛАУ к виду (2.1.4), служащему стартовым для обратного хода метода Гаусса. Это означает, что одинаковыми преобразованиями, сохраняющими эквивалентность систем, матицу нужно привести к верхней треугольной матрице , а вектор - к вектору , где и отвечают представлению (2.1.2) В другие терминах – расширенную матрицу системы (2.1.1) ортогональными преобразованиями нужно перевести в расширенную матрицу системы (2.1.3). Ясно, что это можно сделать, применяя последовательно к столбцам матрицы преобразования Хаусхолдера по схеме QR-факторизации.
Действительно, так как
,
и, значит, , то отсюда имеем следующее «технологичное» представление -матрицы :
,
Где – матрица Хаусхолдера -го этапа.
-
Примеры и пояснение работы программы (язык C#)
3.1. Что реализовано в модулях программы?
В данной программе реализуются следующие пункты:
-
Выполняется QR-разложение исходной матрицы.
-
Решение СЛАУ методом отражений.
Здесь реализован класс для работы с матрицами GausMatrixElimination, служащий основой для матричных преобразований и обратного хода метода Гаусса. QR-разложение матрицы проходит по следующему алгоритму:
-
-
-
Для
-
-
, то переход к начала шага 3.
-
, то , иначе
-
-
-
Для :
-
Для
-
c
-
для :
-
для
-
если , то , иначе
-
-
Для
-
Для
-
-
При
-
3.2.Примеры работы программы
В качестве исходных значений здесь использовалась матрица и вектор свободных членов:
,.
Полученное решение СЛАУ:
.
-
Решение СЛАУ методом отражений
4.1. Решение примера вручную
Решить систему:
Решение:
Выполним 2 этапа преобразований Хаусхолдера над расширенной матрицей
,
А затем сделать обратный ход:
На первом этапе имеем:
,
, ,
.
Результаты вычислений на втором этапе(округленные до третьего знака после запятой) следующие:
,
,
.
Далее при помощи обратного хода метода Гаусса по формулам получаем решение системы:
,
,
.
-
Список литературы
-
Численные методы, Бахвалов Н.С. Минск, Лаборатория базовых знаний-2003
-
Краткий курс численного анализа в двух частях, Минченко Л.И. Минск, БГУИР-2006
-
Численные методы. Линейная алгебра и нелинейные уравнения, Вержбицкий В.М. Москва, 2005
-
Язык программирования C# 2008 и платформа .NET 3.5 Эндрю Троелсен 2010
|
