Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа»




Скачать 111.79 Kb.
НазваниеПояснительная записка к курсовому проекту по дисциплине «Методы численного анализа»
Дата публикации24.05.2014
Размер111.79 Kb.
ТипПояснительная записка
literature-edu.ru > Математика > Пояснительная записка
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики

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

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

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

Выполнил: Бенько И.С.,

ст.гр. 852002

Принял: Хотеев А. Л.

Минск, 2010

Оглавление




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

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

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

1.3. Преобразование Гивенса 7

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

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

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

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

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

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

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

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


  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. Для



    1. , то переход к начала шага 3.

    2. , то , иначе





    3. Для :

      1. Для

      2. c

    4. для :

      1. для

      2. если , то , иначе



    5. Для

      1. Для



  2. При




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






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

,.

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

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

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


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



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

,

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

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



,

, ,

.

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

,

,

.

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

,

,

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




  1. Численные методы, Бахвалов Н.С. Минск, Лаборатория базовых знаний-2003

  2. Краткий курс численного анализа в двух частях, Минченко Л.И. Минск, БГУИР-2006

  3. Численные методы. Линейная алгебра и нелинейные уравнения, Вержбицкий В.М. Москва, 2005

  4. Язык программирования C# 2008 и платформа .NET 3.5 Эндрю Троелсен 2010

Добавить документ в свой блог или на сайт

Похожие:

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПояснительная записка к курсовому проекту на тему микропроцессорная...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПояснительная записка. К курсовому проекту
«Проектирование гравитационной подпорной стенки на естественном и искусственном основаниях и на сваях»

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПояснительная записка к курсовому проекту по дисциплине «Процессоры...
Стивен Смит. Научно-техническое руководство по цифровой обработке сигналов [Электронный ресурс] / Пер с англ фирмы «Автэкс». – С-пб,...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПояснительная записка к курсовому проекту по дисциплине «Схемотехника эвм»
Курсовой проект выполнен в целях закрепления теоретических знаний, полученных во время изучения курса «Схемотехника эвм», а также...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПрепроцессор пояснительная записка к курсовому проекту по курсу «Схемотехника эвм»
Графическая часть состоит из 4 документов: схема электрическая функциональная (Э2), схема электрическая принципиальная (Э3), диаграмма...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПрепроцессор пояснительная записка к курсовому проекту по курсу «Схемотехника эвм»
Графическая часть работы состоит из 4 документов: схема электрическая функциональная (Э2), схема электрическая принципиальная (Э3),...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПрепроцессор пояснительная записка к курсовому проекту по курсу «Схемотехника эвм»
Использовано 5 литературных источников. Графическая часть включает в себя 4 документа: схему электрическую функциональную (Э2), схему...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПрепроцессор пояснительная записка к курсовому проекту по курсу «Схемотехника эвм»
Использовано 5 литературных источников. Графическая часть включает в себя 4 документа: схему электрическую функциональную (Э2), схему...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПрепроцессор пояснительная записка к курсовому проекту по курсу «Схемотехника эвм»
Использовано 5 литературных источников. Графическая часть включает в себя 4 документа: схему электрическую функциональную (Э2), схему...

Пояснительная записка к курсовому проекту по дисциплине «Методы численного анализа» iconПояснительная записка к дипломному проекту на тему индивидуальный жилой дом в г. Тюмени
Исходные данные к проекту -задание на проектирование,рабочие чертежи марки ас,ГП. Материалы инженерно-геологических изысканий

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции