42950

Исследование QR метода на основе преобразований вращения и отражения

Курсовая

Информатика, кибернетика и программирование

Рассмотрим два метода исключение обладающих в отличие от метода Гаусса гарантированной хорошей обусловленностью метод вращений и метод отражений. Оба эти метода позволяют получить представление исходной матрицы в вид произведения ортогональной матрицы Q на верхнюю треугольную матрицу R: =QR. 1 Теория метода вращения Пусть дана система линейных алгебраических уравнений содержащая n уравнений с n неизвестными. Идея метода заключается в том что матрицу А приводим к верхней треугольной умножая ее на коэффициенты c и s а потом с помощью...

Русский

2013-11-03

194.67 KB

16 чел.

11

Введение

Метод Гаусса не является единственным методом исключения, используемым для решения систем линейных уравнений и приведения матриц к треугольному виду. Рассмотрим два метода исключение обладающих в отличие от метода Гаусса гарантированной хорошей обусловленностью — метод вращений и метод отражений. Где метод вращения имеет сложность алгоритма N≈2m3 арифметических операций, а метод отражения имеет сложность N ≈ 2/3m3 арифметических операций. Оба эти метода позволяют получить представление исходной матрицы A в вид произведения ортогональной матрицы Q на верхнюю треугольную матрицу R: A=QR. Напомним, что матрица Q называется ортогональной, если для нее выполнено условие QT=Q-1, что эквивалентно равенству QQT=E, где QT – транспонированная матрица, Q-1 – обратная матрица Q, E – единичная матрица.


1 Теория метода вращения

Пусть дана система линейных алгебраических уравнений, содержащая n уравнений с n неизвестными.

+  + … +  =

+  + … +  =

  …          …       …       …       …

+  + … +  =

или в матричной форме AX = B, где

             …  

A =    …    …    …   …     – матрица коэффициентов системы,

             …  

 

X =    ...    – вектор – столбец из неизвестных,

 

 

B =    ...    – вектор – столбец из свободных членов.

 

Идея метода заключается в том, что матрицу А приводим к верхней треугольной умножая ее на коэффициенты c и s, а потом с помощью обратного хода метода Гаусса находим корни уравнения.

Опишем прямой ход метода. На 1-м шаге неизвестное X1 исключают из всех уравнений, кроме первого. Для исключения X1 из второго уравнения вычисляют числа

               

Обладающими следующими свойствами:

 ,  

Затем первое уравнение системы заменяют линейной комбинацией первого и второго уравнений с коэффициентами с12и s12, а второе уравнение — аналогичной линейной комбинацией с коэффициентами s12 и c12. В результате получают систему

                                                                     (1)

……………………………………………………

в которой

 , (1≤ jm),                         (2)

 ,

Заметим, что в силу  специального выбора чисел  с12  и s12

Естественно, что в случае а21=0 исходная система уже имеет вид (1) и в исключении неизвестного x1 из второго уравнения нет необходимости. В этом случае полагают c21=1 и s21=0.

Как нетрудно видеть, преобразование исходной системы к виду (1) эквивалентно умножению слева матрицы А и правой части b на матрицу T12 имеющую вид.

       c12 s12  0    0 … 0

      -s12 c12  0    0 …0

T12=             0      0    1   0 …0

                   0      0    0    1…0

         …………………

         0      0     0    0 …1

Для исключения неизвестного x1 из третьего уравнения вычисляют числа

,                                                                     (3)

такие, что

 

Затем первое уравнение системы (1) заменяют линейной комбинацией первого и третьего уравнений с коэффициентами c13 и s13 ,а третье уравнение — аналогичной комбинацией с коэффициентами — s13 и c13.Это преобразование системы эквивалентно умножению слева на матрицу.

       c13    0   s13    0 …0

          0    1    0    0… 0

T12=          -s13    0    c13  0 …0

                   0     0     0    1…0

         …………………

         0      0     0    0 …1

и приводит к тому, что коэффициент при x1 в преобразованном третьем уравнении обращается в нуль.

Таким же образом x1 исключают из уравнений с номерами i = 4, ..., m. В результате 1-го шага (состоящего, как мы видели, из m – 1 "малых" шагов) система приводится к виду

,

 ,                                                                 (4)

……………………………………………………

В матричной записи получаем

A(1)x=b(1), где A(1)=T1m…T13T12A, b(1)=T1m…T13T12b.

Здесь и далее через Tkl обозначена матрица элементарного преобразования, отличающаяся от единичной матрицы Е только четырьмя элементами. В ней элементы с индексами (k,k) и (l,l) равны сkl, элемент с индексами (к, l) равен  skl, а элемент с индексами (l, k) равен -skl, причем выполнено условие

                                                                                                (5)

Действие матрицы Тkl на вектор x эквивалентно его повороту вокруг оси, перпендикулярной плоскости Oxkx1 на угол φkl такой, что сkl= cos φkl , skl=sin φkl (существование такого угла гарантируется равенством (5)). Эта геометрическая интерпретация и дала название методу вращений. Операцию умножения на матрицу Тkl часто называют плоским  вращением (или  преобразованием Гивенса). Заметим,  что и, следовательно, матрица Тkl ортогональная.

На 2-а шаге метода вращений, состоящем из m–  2 "малых" шагов, из уравнений системы (4) с номерами i = 3, 4, ..., т исключают неизвестное x2. Для этого каждое i-oe уравнение комбинируют со вторым уравнением. В результате приходим к системе

,

,    

……………………………………………………

В матричной форме записи получаем A(2)x=b(2). После завершения
(
m– 1)-го шага система принимает вид

,

,          

…………………………………………………………………

Или в матричной записи A(m-1)x=b(m-1). Введем обозначение R для полученной верхней треугольной матрицы A(m-1). Она связана с исходной матрицей A равенством

R=TA,

где T=Tm-1,mT2mT23T1mT13T12 – матрица результирующего вращения. Заметим, что матрица Т ортогональна как произведение ортогональных матриц. Обозначая Q = Т-1 = ТT , получаем QR-разложение матрицы А.

Обратный ход метода вращений проводится точно так же, как и для метода Гаусса.

Метод вращений обладает замечательной численной устойчивостью. Однако этот метод существенно более трудоемок по сравнению с методом Гаусса. Получение QR-разложения для квадратной матрицы А общего вида требует примерно 2m3 арифметических операций.


2 Теория метода отражения

Пусть дана система линейных алгебраических уравнений, содержащая n уравнений с n неизвестными.

+  + … +  =

+  + … +  =

  …          …       …       …       …

+  + … +  =

или в матричной форме AX = B, где

             …  

A =    …    …    …   …     – матрица коэффициентов системы,

             …  

 

X =    ...    – вектор – столбец из неизвестных,

 

 

B =    ...    – вектор – столбец из свободных членов.

 

Идея метода заключается в следующем: матрица A системы раскладывается в произведение двух матриц – унитарной матрицы и правой треугольной матрицы: A = WT, где W – унитарная матрица, T – правая треугольная матрица.

Унитарная матрица W – такая матрица, для которой выполнено:  

,

где E – единичная матрица, – унитарная транспонированная матрица.

Унитарную матрицу W можно получить как произведение специальных матриц, называемых матрицами отражения : .

Разложение матрицы A системы в произведение унитарной и правой треугольной происходит в несколько этапов:

1) Задаем вектор s. В качестве данного вектора выбираем первый столбец матрицы A системы: s = (). Находим вектор w по формуле:

,

где е – единичный вектор,  – норма вектора s.

За единичный вектор возьмем вектор равный e = (1, 0, …, 0). Строим матрицу отражения по формуле:

,

где E – единичная матрица, w – вектор,  – транспонированный вектор w.

Домножаем матрицу A слева на , получаем матрицу , которая имеет следующий вид:

 

Домножаем также вектор свободный членов B, слева на , получаем . Получаем новую систему  .

2) Теперь в качестве вектора s выбираем вектор s = (). В качестве же e возьмем вектор e = (0, 1, 0, …, 0). С помощью приведенных выше формул находим вектор  и строим матрицу . Находим матрицу , которая имеет следующий вид:
           

Домножаем  слева на . Получаем новую систему .

3) Продолжая описанный процесс построения, на (n – 1) шаге получим матрицу , которая имеет вид:

 

В итоге, получим систему . Далее решение можно легко найти, используя обратный ход метода Гаусса.


3 Анализ данных и алгоритмов

В программе предусмотрены типы matrix = array [0..100, 0..100] of real для хранения элементов матриц и sequence = array [0..100] of real для хранения одномерных массивов. В программе переменная ma отвечает за хранение матрицы А, переменная mb за хранение столбца свободных членов В. Указанные переменные являются глобальными. Кроме них в программе определены переменные, отвечающие за ответ X, копию матриц и вспомогательные переменные, определенные алгоритмом.

В работе реализовано два метода. За метод вращения отвечает процедура  vrashen(a:matrix; b:sequence;sizeofsystem: integer; accuracy: real; var memo: trichedit); в которую передается расширенная матрица А, вектор столбец свободных членов b, размерность системы и поле вывода. В указанное поле записывается результат работы процедуры, а именно коэффициенты с и s, преобразованные матрицы, решение системы и невязки. Процедура преобразовывает матрицу А в верхнюю треугольную с помощью метода вращения и решает ее обратным ходом метода Гаусса.

За метод отражения отвечает процедура procedure otrazhen(a: matrix; b: sequence; sizeofsystem: integer; accuracy: real; var memo: trichedit); в которую передаются также расширенная матрица а, вектор столбец b, размерность системы. Процедура преобразовывает матрицу А в верхнюю треугольную с помощью метода отражения и решает ее с помощью обратного хода метода Гаусса.

Для того чтобы найти решение системы из треугольной матрицы требуется применить обратный ход метода Гаусса для этого в программе реализована процедура обратный ход obrxod(a: matrix; b:sequence; sizeofsystem:integer; var x:sequence). В нее передается верхняя треугольная матрица А, столбец свободных членов b, размерность системы sizeofsystem. Процедура возвращает решение системы в столбце X.


4 Руководство пользователя

Для того чтобы выполнить программу нужно запустить файл PKurs.exe. На экране появится окно в соответствии с рисунком 1.

Рисунок 1 – Главное окно программы

Вкладка «Отражение» предназначена для решения системы методом отражения. На вкладке предполагается указать размерность матрицы заполнить матрицу с коэффициентами и столбец свободных членов. Указанную матрицу можно заполнить случайными числами, нажав кнопку «Random». После нажатия на кнопку «Отражение» произойдет расчет. Результат будет помещен в правой части окна.

Вкладка «Вращение» предназначена для решения системы методом вращения. Основные элементы управления на ней аналогичны вкладке «Отражение».

На вкладке «Проверка» можно сравнить результаты работы двух методов.


5 Примеры расчета и анализ результата

5.1 Ручной счет метода вращения

Решить систему линейных алгебраических уравнений методом отражения:

  2x1               – 9x2+    5x3= – 4,

1.2x1– 5.3999x2+     6x3=0.6001,

    x1                   x2– 7.5x3= –8.5.

Прямой   ход.  1-й   шаг.  Исключим x1 из второго уравнения. Для этого вычислим с12 и s12 по формулам (2):

0.857493, 0.514495

Преобразуя  коэффициенты  первого  и   второго  уравнений   по  формулам (2), приходим к системе

  2.33238x1               – 10.4957x2+    7.37444x3= – 3.12122,

                     7.85493*10-5x2+     2.57248x3=2.57256,

               x1                                   x2–             7.5x3= –8.5.

Далее вычислим коэффициенты с13 и s13 по формулам (2):

0.919087, 0.394055

Заменяя первое и третье уравнения их линейными комбинациями с коэффициентами c13,s13 и –s13, c13 соответственно, получим систему

  2.53772x1               – 10.0405x2+    3.82234x3= – 6.21814,

                     7.85493*10-5x2+     2.57248x3=2.57256,

                             3.21680x2–      9.79909x3= –6.58231.

2-й    ш а г.   В  полученной  системе  имеем      —  7.85493-10-5,  3.21680. Поэтому

 s23

Заменяя второе и третье уравнения системы их линейными комбинациями с коэффициентами с23,s23 и –s23, c23 соответственно, приходим к системе

 2.53772x1               – 10.0405x2+    3.82234x3= – 6.21814,

                              3.21680x2+     9.79903x3= – 6.58225,

                                                     -2.57272x3= –2.57272.

Обратный    ход    дает   последовательно  значения   x3  =1,   x2 = 0.999994,   x3 = -1.58579*10-5.

5.2 Ручной счет метода отражения

Решить систему линейных алгебраических уравнений методом отражения:

 

 

 

Шаг 1:

, ;

, , e = (1, 0, 0);

, ;

;

, ;

В результате получили преобразованную матрицу:

.

Умножив вторую строку на 20, а третью на 3, получим:

.

Шаг 2:

, ;

, , e = (0, 1);

, ;

;

, .

В результате, мы получили систему, из которой находим решение:

 

 

 

Ответ:

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

Рассмотрим произвольную систему уравнений.

Результаты работы программы приведены в соответствии с рисунком 2. Анализируя полученные данные, можно сделать вывод, что оба метода работают корректно. Ответ, полученный первым методом, совпадает с ответом, полученным вторым. Невязки нулевые.

Рисунок 2 – Результаты работы программы

Рассмотрим систему уравнений, у которой определитель матрицы А близок к нулю.

Результаты работы программы приведены в соответствии с рисунком 3.

Рисунок 3 – Результаты работы программы

Анализируя полученные результаты, можно сделать вывод, что методы работают с такими системами, погрешность вычислений незначительная. Ответ, полученный первым методом, совпадает с ответом, полученным вторым. Невязки нулевые.

Заключение

В данной курсовой работе исследован QR метод на основе преобразований вращения и отражения. Указанные методы реализованы для решения систем линейных алгебраических уравнений. Данная программа позволяет решать системы уравнений порядка, не превосходящего 100 уравнений. Программа не имеет существенных недостатков, однако для удобства пользователя в дальнейшем можно снабдить ее встроенной системой помощи.


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

  1.  Молчанов И.Н. Машинные методы решения прикладных задач. – Киев: Наук. думка, 1987. – 288 с.
  2.  Воеводин В.В. Вычислительные основы линейной алгебры. – М.: МГУ, 2006. – 112 с.
  3.  Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. – М.: Высш.шк., 1994. – 544с.

 

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

44202. Специфика работы в сети Internet 45.43 KB
  Современный человек вряд ли представляет свою профессиональную деятельность без применения ресурсов, доступных при помощи Internet. Интернет – это совокупность государственных, региональных, корпоративных и других компьютерных сетей, а также отдельных компьютеров, объединенных между собой разнообразными каналами передачи данных и унификацией применяемых технологий, таким образом, по своей структуре это полностью децентрализованная сеть.
44203. Стальной каркас промышленного здания 1.19 MB
  При определении горизонтальных размеров учитываются унифицированные привязки колонн ак к разбивочным осям, требования прочности и жесткости, предъявляемые к колоннам, а так же эксплуатационные требования.
44204. Разработка среды поддержки сценариев для генерации графических текстов 1.2 MB
  В нашем проекте мы будет работать с информационно-справочным классом, так как это один из самых распространенных и широко используемых классов информационных систем. Примером информационной системы этого класса будет мануал. Руководство пользователя (англ. user guide или user manual), руководство по эксплуатации - документ
44205. Автоматизация подготовки расписания учебных занятий в общеобразовательной школе 1.26 MB
  Расчет единовременных затрат на разработку программного продукта Срок разработки программного продукта Расписание составляет 1 месяц таблица 1. Программа Расписание поможет школе: соблюдать все основные требования для обучающихся и учителей; оптимально использовать кабинеты; снизить нагрузку работы администрации; устранить возможные ошибки и субъективные факторы при составлении расписаний в школе. Руководство пользователя Программный продукт Расписание позволяет автоматизировать работу по составлению учебных занятий в...
44206. Понятие социального обеспечения и права социального обеспечения 49 KB
  Социальным обеспечением в узком смысле называется только обеспечение престарелых и нетрудоспособных граждан, осуществляемое управомоченными государственными органами за счет прямых ассигнований из государственного бюджета
44207. Основные возможности Microsoft Office Outlook 1.69 MB
  Outlook представляет собой программу управления данными. Outlook может использоваться для документооборота формирования задач и заданий группы управления электронной почтой планирования дел и собраний ведения списка контактных лиц и дневника выполняемых действий. Некоторые возможности Outlook можно использовать с другими приложениями Office.
44208. Разработка мероприятий по развитию ООО «Клиника профилактики» 1.2 MB
  Инвестирование средств в прогрессивное оборудование новых специалистов и внедрение новых видов услуг. Планирование выручки от реализации услуг и затрат. Составление карты привлекательности услуг и разработка рекламной компании. Не следует путать экономику здоровья с экономикой здравоохранения которая ориентирована на производство лекарств и оказание медицинских услуг.
44209. Розробка програмного забезпечення: підбір зачіски та кольору волосся 2.87 MB
  ПРОГРАМАПОМІЧНИК ПІДБІР ЗАЧІСКИ КОЛЬОРУ СУБД БАЗА ДАНИХ. Також була створена база даних в середовищі MуSQL 5. Список скорочень БД база даних; СУКБД система управліннякерування базами даних; ПК персональний компютер; ПЗ програмне забезпечення; ПО предметна область.1 Огляд сучасних СУБД Бази даних це сукупність даних між якими існують зв'язки.