13796

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

Курсовая

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

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

Украинкский

2013-05-14

4.29 MB

201 чел.

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

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

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

Оглавление

[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


 

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

21603. МЕНЕДЖМЕНТ ПРИ РАЗРАБОТКЕ РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ 181 KB
  Отбор и оценка проектов НИОКР. Стратегия НИОКР. Оценка проекта НИОКР. Финансовый анализ в процессе НИОКР.
21604. ПОРЯДОК И ЭТАПЫ РАЗРАБОТКИ РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ 552 KB
  Постановка продукции на производство. Постановка на производство продукции по лицензиям. Новая техника воплощая результаты последних научнотехнических достижений способствует развитию производительных сил общества и удовлетворению его потребностей в продукции более высокого качества. Величина этих расходов зависит от уровня новизны продукции и частоты смены моделей.
21605. СТАНДАРТИЗАЦИЯ РАЗРАБОТКИ РАДИОЭЛЕКТРОННОЙ АППАРАТУРЫ 512.5 KB
  Стандарты входящие в ЕСКД устанавливают единые правила и положения по порядку разработки оформления и обращения конструкторской документации на изделия разрабатываемые и выпускаемые предприятиями всех отраслей промышленности России. Различают изделия основного производства предназначенные для поставки реализации и изделия вспомогательного производства предназначенные для собственного потребления предприятиемизготовителем. К деталям относят также изделия изготовляемые с применением сварки пайки склеивания и т. К сборочным...
21606. ТРЕБОВАНИЯ К РАДИОЭЛЕКТРОННОЙ АППАРАТУРЕ ПО УСЛОВИЯМ ЭКСПЛУАТАЦИИ 259 KB
  Стационарная РЭА. Транспортируемая РЭА. Портативная РЭА. Значения воздействующих факторов на группы РЭА.
21607. ЗАЩИТА АППАРАТУРЫ ОТ ВЛИЯНИЯ КЛИМАТИЧЕСКИХ ФАКТОРОВ ЭКСПЛУАТАЦИИ 439 KB
  Protection from climatic conditions of the usages Тема 5: ЗАЩИТА АППАРАТУРЫ ОТ ВЛИЯНИЯ КЛИМАТИЧЕСКИХ ФАКТОРОВ ЭКСПЛУАТАЦИИ Естествоиспытатель не принимает в расчет невероятное. Тепловой режим аппаратуры. Охлаждение аппаратуры.
21608. ЗАЩИТА АППАРАТУРЫ ОТ МЕХАНИЧЕСКИХ ВОЗДЕЙСТВИЙ И ПОМЕХ 572.5 KB
  Виды механических воздействий на РЭА. Амортизация конструкции РЭА. Применение экранов в РЭА. Защита от механических воздействий [1 2] Виды механических воздействий на РЭА.
21609. ОБЕСПЕЧЕНИЕ НАДЕЖНОСТИ РАБОТЫ АППАРАТУРЫ 518.5 KB
  Вероятность безотказной работы РЭА. Повышение надежности РЭА резервированием. Информационные методы повышения надежности РЭА. Расчет надежности РЭА.
21610. Работа с данными. Поиск и замена данных 279.5 KB
  Для поиска данных необходимо выполнить команду Правка Найти и во вкладке Найти диалогового окна Найти и заменить рис. Поиск данных во вкладке Найти диалогового окна Найти и заменить При поиске можно использовать подстановочные знаки. Результаты поиска данных во вкладке Найти диалогового окна Найти и заменить Для более детального поиска во вкладке Найти диалогового окна Найти и заменить см.
21611. Работа с форматами Excel. Копирование форматов 252.5 KB
  Ко всем выделенным фрагментам будет применен выбранный стиль. Копирование формата с использованием специальной вставки в диалоговом окне Специальная вставка Использование стилей О стилях Использование стилей обеспечивает единообразие оформления данных и ячеек во всей книге позволяет быстро устанавливать выбранный набор параметров форматирования а также мгновенно изменять оформление всех ячеек к которым применен один стиль. Для просмотра доступных стилей необходимо выполнить команду Формат Стиль. Список основных стилей приведен в...