13796

Ортогональное разложение матриц и его применения

Курсовая

Математика и математический анализ

Пояснительная записка к курсовому проекту по дисциплине Методы численного анализа на тему Ортогональное разложение матриц и его применения Оглавление Оглавление Теоретические сведения Преобразование Хаусхол...

Украинкский

2013-05-14

4.29 MB

234 чел.

Пояснительная записка к курсовому проекту по дисциплине

«Методы численного анализа»

на тему «Ортогональное разложение матриц и его применения»

Оглавление

[1] Оглавление

[2]
Теоретические сведения

[2.1] Преобразование Хаусхолдера.

[2.2] 1.2. QR-разложение матриц

[2.3] 1.3. Преобразование Гивенса

[3] Практические применения

[3.1] 2.1. Метод отражений решения СЛАУ

[4]
Примеры и пояснение работы программы (язык C#)

[4.1] 3.1. Что реализовано в модулях программы?

[4.2] 3.2.Примеры работы программы

[5] Решение СЛАУ методом отражений

[5.1] 4.1. Решение примера вручную

[6] Список литературы

  1.  
    Теоретические сведения

В евклидовом n-мерном пространстве рассматриваются два ортогональных преобразования: преобразование отражения Хаусхолдера и преобразование плоских вращений Гивенса.  В качестве примера применения преобразований Хаусхолдера изучается метод отражений для решения систем линейных алгебраических уравнений. Главный упор делается на использование ортогональных преобразований в задаче нахождения всех собственных числе (в том числе кратных и комплексны) произвольных квадратных матриц умеренных размеров с вещественными элементами.

  1.  Преобразование Хаусхолдера.

Пусть 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). После пересчета диагональных и стоящих правее них элементов -й и -й строк по формулам

 

 

Матрица  будет готова к выполнению следующего шага преобразований Гивенса.

Таким образом совокупность этих формул, в которых натуральной переменной  последовательно придаются значения , полностью определяет процесс приведения матрицы Хессенберга  к матрице правой треугольной формы, осуществляемый преобразованиями .


  1.  Практические применения

2.1. Метод отражений решения СЛАУ

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

Пусть дана система

         (2.1.1)

С вещественным вектором правой части , вектором неизвестных  и вещественной матрицей коэффициентов

Рассмотрим две ситуации.

  1.  Предположим, что уже известно ортогональное разложение матрицы :

,        (2.1.2)

Где -ортогональная, а - правая треугольная матрицы. Тогда после его подстановки в (2.1.1) имеем эквивалентную систему

 

Которая, в свою очередь, ввиду ортогональности симметричной матрицы , равносильна системе

.        (2.1.3)

Обозначив  систему (2.1.3) можно переписать в виде

     (2.1.4)

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

  1.  Будем теперь исходить из того, что готового QR-разложения матрицы  нет и, вообще говоря, оно в явном виде не требуется ,а нужно получить решение системы (2.1.1), используя преобразование отражения.

Промежуточной целью здесь опять является приведение данной СЛАУ к виду  (2.1.4), служащему стартовым для обратного хода метода Гаусса. Это означает, что одинаковыми преобразованиями, сохраняющими эквивалентность систем, матицу  нужно привести к верхней треугольной матрице , а вектор - к вектору , где  и  отвечают представлению (2.1.2) В другие терминах – расширенную матрицу  системы (2.1.1) ортогональными преобразованиями нужно перевести в расширенную матрицу  системы (2.1.3). Ясно, что это можно сделать, применяя последовательно к столбцам матрицы  преобразования Хаусхолдера по схеме QR-факторизации.

Действительно, так как

,  

и, значит, , то отсюда имеем следующее «технологичное» представление -матрицы :

,

Где  – матрица Хаусхолдера -го этапа.

  1.  
    Примеры и пояснение работы программы (язык C#)

3.1. Что реализовано в модулях программы?

В данной программе реализуются следующие пункты:

  1.  Выполняется QR-разложение исходной матрицы.
  2.  Решение СЛАУ методом отражений.

Здесь реализован класс для работы с матрицами GausMatrixElimination, служащий основой для матричных преобразований и обратного хода метода Гаусса. QR-разложение матрицы проходит по следующему алгоритму:

  1.  
  2.  
  3.  Для
    1.  
    2.  , то переход к начала шага 3.
    3.  , то , иначе
    4.  
    5.  
    6.  Для :
      1.  Для
      2.  c
    7.  для :
      1.  для 
      2.  если , то , иначе
    8.  
    9.  Для
      1.  Для
      2.  
  4.  При
    1.  

            


3.2.Примеры работы программы

В качестве исходных значений здесь использовалась матрица и вектор свободных членов:

,.

Полученное решение СЛАУ:

.


  1.  Решение СЛАУ методом отражений

4.1. Решение примера вручную

Решить систему:

Решение:

Выполним 2 этапа преобразований Хаусхолдера над расширенной матрицей

,

А затем сделать обратный ход:

На первом этапе имеем:

,

, ,

.

Результаты вычислений на втором этапе(округленные до третьего знака после запятой) следующие:

,

,

.

Далее при помощи обратного хода метода Гаусса по формулам получаем решение системы:

,

,

.


  1.  Список литературы

  1.  Численные методы, Бахвалов Н.С. Минск, Лаборатория базовых знаний-2003
  2.  Краткий курс численного анализа в двух частях, Минченко Л.И. Минск, БГУИР-2006
  3.  Численные методы. Линейная алгебра и нелинейные уравнения, Вержбицкий В.М. Москва, 2005
  4.  Язык программирования C# 2008 и платформа .NET 3.5 Эндрю Троелсен 2010


 

А также другие работы, которые могут Вас заинтересовать

14. Философия познания как процесс приобретения, осмысления и усвоения знания 21.42 KB
  Важным понятием гносеологии выступает понятие познание. Под познанием принято понимать процесс приобретения, осмысления и усвоения знания об окружающем мире. Процесс познания – сложный процесс , имеющий свою внутреннюю структуру
15. Исследование характеристик линейных и нелинейных резисторов 43 KB
  Экспериментальное определение вольт-амперных характеристик (ВАХ) линейных и нелинейных резисторов и источников эклетромагнитной энергии. Исследовав ВАХ характеристики линейного и нелинейного резисторов.
16. Разработка программы реализующей организацию библиотечной деятельности 125 KB
  Разработка программы реализующей организацию системы выдачи, возврата книг в библиотеке является учебной задачей, и заключается в отработки навыков реализации ранее изученных структур данных и алгоритмов обработки данных.
17. Организация технического обслуживания автомобильного транспорта на предприятии ОДО 26.33 KB
  Выделение транспорта в процессе общественного разделения труда в самостоятельную отрасль материального производства, организация труда на предприятии, ее осуществление в соответствии с правилами приемки и выдачи легкового автомобиля СТО и правилами предоставления и пользования услугами СТО.
18. Выявление насаждений группы риска 35.74 KB
  Болезни растений – одна из главных проблем, мешающих получению качественного полнодревесного древостоя. Они наносят существенные вред растениям, препятствуют наращиванию посадочного материала, вызывают гибель семян древесных пород и кустарников.
19. Использование отсечения в пролог-программах. Определение возрастного статуса человека 34.73 KB
  Определение возрастного статуса человека по известному году рождения в соответствии с таблицей. Разработка двух вариантов программы: без отсечения и с использованием отсечения.
20. Административный процесс и административно-процессуальное право 44.05 KB
  Предмет, методы, источники и система административно-процессуального права. Дисциплинарное производство, производство по реализации материальной ответственности и контрольно-надзорное производство.
21. Снід - чума ХХІ століття. Виховний захід 38 KB
  Синдром набутого імунодефіциту – тяжке інфекційне захворювання, збудником якого є вірус імунодефіциту людини,епідемія СНІДу у найближчі 20-30 років знищить половину населення Земної кулі.