13796

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

Курсовая

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

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

Украинкский

2013-05-14

4.29 MB

211 чел.

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

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

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

Оглавление

[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


 

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

50769. Создание динамических Web-страниц 31.5 KB
  Цель: Научиться создавать динамические web-страницы. Разобрать на примерах их достоинства и недостатки. Создадим шаблон страницы следующего вида.
50770. Использование динамических переменных 27.5 KB
  Цель: Научиться использовать переменные разных типов. Задание 1. Создадим первую типовую программу на PHP
50771. Программирование циклов в РНР 31.5 KB
  Цель: Научиться использовать различные циклы. Задание 1. Проверить работоспособность кода программ из 3 примеров.
50772. Работа с массивами РНР 25.5 KB
  Цель: Научиться использовать массивы при написании программ. Разобрать особенности каждого вида массивов. Задание 1. Создать массив A 1-10 из десяти целых чисел.
50773. Работа с датой и временем 25 KB
  Цель: Научиться работать с датой и временем. Разобрать основные функции даты и времени. Задание 1. Проработать фрагменты кода из теоритической части. Задание 2. Вывести дату и время в различных форматах. Задание 3. Вывести дату и время на другой странице при помощи форм.
50774. Разработка макета динамических страниц 30 KB
  С страницу следующего примерного содержания Заголовок сайта Навигация Страница1 Страница2 Страница3 Содержание страницы 1 Информация об авторе...
50775. Использование метода GET 28 KB
  Создать форму и результат передачи методом GET поместить в тот же файл. Создать форму. Поместить на нее 4 текстовых поля(Фамилию, Имя, Отчество, Группу). Передать значения этих полей другому файлу. Поместить на форму стандартные кнопки, проверить работу данных кнопок.
50776. Передача данных методом POST 25.5 KB
  Получить данные при помощи метода POST. Создать форму для ввода Фамилии, Имени, Отчества, Группы. Получить данные при помощи метода POST.Расположить в одной webстранице 2 формы с методом Get и Post.
50777. Разработка страниц с формами 32 KB
  Цель: Научиться создавать формы содержащие различные элементы. Задание 1. Создать форму содержащую 10 различных элементов.