13796

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

Курсовая

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

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

Украинкский

2013-05-14

4.29 MB

208 чел.

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

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

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

Оглавление

[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


 

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

73628. Статистика результатов экономической деятельности 101.5 KB
  Понятие промышленной продукции и ее видов по степени готовности. Стоимостные показатели объема производства продукции. Факторный анализ изменения объема производства продукции. Анализ динамики производства продукции индексным методом.
73630. Риск-менеджмент в организации 144.78 KB
  Рискменеджмент в организации Система управления риском. Развитие концепции управления риском. Общая характеристика системы управления риском. Свойства системы управления риском.
73631. СВІТОВА ВАЛЮТНА СИСТЕМА 376 KB
  Ця мета потребує щоб: окремі країни проводили економічну та фінансову політику яка б сприяла підтриманню збалансованої міжнародної системи платежів; фінансові механізми забезпечували регулювання платіжного балансу; уряди сприяли збереженню рівноваги на ринках іноземної валюти. Основні елементи національної і світової валютних систем Національна валютна система Світова та міжнародна валютні системи Національна валюта Резервні валюти міжнародні рахункові валютні одиниці Умови конвертування національної валюти Умови взаємного конвертування...
73632. Міжнародна міграція робочої сили 206.5 KB
  Міжнародна міграція робочої сили. Регулювання міжнародної міграції робочої сили. Сутність структура та основні риси світового ринку праці Одним із важливих елементів глобальної економічної системи на яку перетворився світ наприкінці другого тисячоліття є міжнародний ринок праці з його уніфікованою шкалою критеріїв щодо якості трудових ресурсів розвитком нових форм зайнятості гнучкістю та надзвичайною мобільністю сукупної робочої сили. Світовий міжнародний ринок праці це система відносин що виникають між державами з приводу...
73633. Міжнародні розрахунки і платіжний баланс 121.5 KB
  Економічний зміст платіжного балансу та методологія складання. Економічний зміст платіжного балансу та методологія складання. Стан платіжного балансу визначає попит і пропозицію національної й іноземної валюти в цей момент і він є одним із факторів формування валютного курсу. Прибуткові та витратні статті балансу міжнародних рахунків Прибуткові статті Джерела грошових коштів Витратні статті Способи використання грошових коштів Експорт товарів та послуг Імпорт товарів та послуг Приток капіталу Вивіз капіталу Приватні та...
73634. Реформы А.Н. Косыгина и причины их неудач 73.1 KB
  Для изучения этой системы и хода реформы дают материал интервью взятые у министра легкой промышленности СССР 1965 1980 гг. начальника главного управления трикотажной и текстильногалантерейной промышленности Софьи Николаевны Чупрыгиной. Министерство легкой промышленности СССР являлось такой же частью системы государственного управления как другие министерства и принципы его работы были такими же как у них. он прошел путь от сменного мастера на Ореховозуевском хлопчатобумажном комбинате до министра легкой промышленности СССР.
73635. Ответственность организаций и исполнителей за нарушение метрологического обеспечения 75.5 KB
  Дисциплинарная и материальная ответственность исполнителей за нарушение законодательства о метрологическом обеспечении производства и испытаний продукции Федеральный закон Российской федерации О техническом регклировании постатейный коментарий...