13796

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

Курсовая

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

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

Украинкский

2013-05-14

4.29 MB

237 чел.

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

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

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

Оглавление

[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


 

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

31340. ИНДОЕВРОПЕЙСКИЕ МИФОТРАДИЦИИ (НА МАТЕРИАЛАХ САКРАЛЬНЫХ ГЕНЕАЛОГИЙ) 2.04 MB
  Современная наука установила факт существования общеиндоевропейского языка праиндоевропейского этноса в виде племени или соплеменности праиндоевропейской культуры как реальности эпохи неолита....
31341. ПРОБЛЕМЫ ЛИНГВИСТИЧЕСКОЙ РЕКОНСТРУКЦИИ ГЕРМАНСКОЙ КОСМОГОНИИ 864.88 KB
  В синхронии основным методом семантической реконструкции является изучение контекста слова. Под контекстом имеется в виду не только непосредственное окружение слова, но и его дальние связи в пределах более крупных единств, например, строф, то есть объектом исследования оказываются как контактное, так и дистантное расположение лексем.
31342. ЛЕКСИКА КУХОННОЙ УТВАРИ И ПОСУДЫ В ОРЛОВСКИХ ГОВОРАХ 3.84 MB
  Комплексное исследование лексики кухонной утвари и посуды позволит предпринятому нами исследованию заполнить пустующую нишу в системе последовательных изысканий в области изучения различных тематических групп в орловских говорах: агентивной лексики Т. Наиболее изученной является эта область лексики в сибирских и северновеликорусских говорах. В разное время обращались к её описанию в томских говорах Ф.
31343. АНТИЧНЫЙ МИФ ОБ АТЛАНТЕ И АТЛАНТИДЕ: ОПЫТ ФОЛЬКЛОРИСТИЧЕСКОГО РАССМОТРЕНИЯ 2.61 MB
  Образ Атланта в античном мифе и эпосе - это ярчайший пример олицетворения в ми-фо-поэтической форме догреческой неведической культуры и культа, с которыми ведические греки вели ожесточенную борьбу, и от которых в то же время они заимствовали множество их достижений
31344. КУЛЬТ АРЕСА В РЕЛИГИОЗНЫХ ПРЕДСТАВЛЕНИЯХ СКИФСКИХ ПЛЕМЕН СЕВЕРНОГО ПРИЧЕРНОМОРЬЯ (V-III вв. до н.э.) 3.56 MB
  Неудивительно что у скифов главным занятием которых была война совершенно особое место занимал культ бога войны Ареса. С точки зрения марксистской концепции религии перед нами яркое подтверждение того что религиозные верования вызревают и принимают различные формы под воздействием определенных социальных условий достигнутой обществом степени развития. Здесь же отметим что важнейшие аспекты скифского военного культа остаются недостаточно разработанными. Считается что до нас не дошло ни одного скифского мифа связанного с Аресом.
31345. ГЕНЕЗИС И ЭВОЛЮЦИЯ СОЛЯРНЫХ АСПЕКТОВ МИФОЛОГИИ АПОЛЛОНА 9.61 MB
  Лосев писал что широкая публика а значительной мере также и наука отождествляет Аполлона и Солнце1. Цель предлагаемой им реконструкции состоит в том чтобы дать правдоподобное объяснение известному и довольно странному факту: по сравнению с восточными религиозными системами в Греции в историческую эпоху культ Солнца как и других астральных божеств был очень мало развит. Рапп объясняет это тем что известный нам греческий Гелиос был последним звеном цепи развития мифологических представлений и именно поэтому сохранил в своей мифологии...
31346. МЕТАФИЗИКА КУЛЬТУРЫ. ОПЫТ СИСТЕМАТИЗАЦИИ ИДЕЙ РУССКИХ РЕЛИГИОЗНЫХ МЫСЛИТЕЛЕЙ 9.52 MB
  Духовная скудость текущей повседневности российского социума ужасает. Сейчас уже мало кто сомневается в бесперспективности новейшего российского либерализма. Дело не только в его роковой беспочвенности, в отрыве от национальных культурно-исторических корней, но и в каком-то совершенно немыслимом ранее «либеральном варварстве», выражающемся и в переходе от преклонения перед Западом к расовой ненависти к Востоку
31347. Образ птицы Бену в контексте древнеегипетской религии и мифологии 3.8 MB
  Важность специального исследования образа Бену обусловлена не только стремлением подробнее осветить его значение, но, и уходит гораздо глубже. На наш взгляд, объяснив закономерности развития и функционирования этого образа в системе древнеегипетских религиозно-мифологических представлений, мы во многом приблизимся к решению проблем, касающихся некоторых аспектов культа животных; и шире, к выявлению закономерностей мифотворчества в древнем Египте.
31348. ЭКРАННАЯ КУЛЬТУРА КАК НОВАЯ МИФОЛОГИЯ (НА ПРИМЕРЕ КИНО) 6.3 MB
  Экранная культура: основные понятия история развития и специфика современного состояния Понятие экранной культуры и основные этапы ее развития Экранная культура и современное коммуникативное пространство Экранная культура в контексте средств массовой коммуникации. Мифы в экранной культуре: традиции и современность Понятие мифа применительно к экранной культуре Новая мифология как способ...