42950

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

Курсовая

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

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

Русский

2013-11-03

194.67 KB

19 чел.

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с.

 

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

43166. Тепловой расчет конвективной туннельной сушильной установки для зимнего (январь) и летнего (июль) периода 1.57 MB
  Выполнить тепловой расчет конвективной туннельной сушильной установки, определить длительность сушки, размеры установки, выбрать вентилятор для подачи наружного воздуха, дымосос, циклон и сожигательное устройство, на основании следующих данных.
43167. ОСКОРБЛЕНИЕ КАК ИЛЛОКУТИВНЫЙ ЛИНГВОКУЛЬТУРНЫЙ КОНЦЕПТ 194 KB
  Научная новизна данной работы заключается в применении концептологического подхода к рассмотрению лингвистических проблем права и в историко-этимологическом описании социальных явлений, которые стали основой современного толкования концепта «оскорбление». В работе была исследована дискурсная реализация этого концепта и выделена типовая базовая структура иллокутивных концептов, объясняющая прагматическую природу лингвосоциальных явлений
43168. ОБРАЗ ШЕРЛОКА ХОЛМСА В ПРОИЗВЕДЕНИЯХ СЭРА АРТУРА КОНАН ДОЙЛА 248.5 KB
  При этом мироощущение и fin de siècle и неоромантизма было подчеркнуто инаким особенным что не устраивало консервативное викторианское общество и образ Шерлока Холмса начал меняться под воздействием такого экстралитературного фактора как цензура: образ редактировался и упрощался чтобы умещаться в строгие рамки жанра семейного чтения. Таким образом образ Шерлока Холмса прошел в процессе своего формирование через влияние fin de siècle и неоромантизма чтобы прийти к викторианским традиционным ценностям. В данной работе...
43169. Дистанционное зондирование Земли из космоса 412.04 KB
  Система правового регулирования ДЗЗ в России и в мире 9 Глава 1. Общие понятия ДЗЗ 9 Глава 2. Международноправовые акты регулирующие ДЗЗ 10 Глава 3. Ранее являясь исключительно прерогативой военных структур сегодня ДЗЗ решает множество гражданских задач и является крайне важной для обеспечения защиты окружающей природной среды разведки полезных ископаемых кадастрового учета и иных направлений деятельности.
43171. Продвижение Шри-Ланки, как туристической зоны 213 KB
  Остров ШриЛанка удивителен и разносторонен на нём прекрасная природа древняя интересная культура насыщенная история и разные религии. Столицей считается Коломбо хотя на самом деле она коммерческий центр страны и крупный развивающийся город административная столица же ШриДжайяварданапура. На ШриЛанке можно отдохнуть просто пролежав под тёплым солнцем но на самом деле на этом острове есть что посмотреть и если предлагать хотя бы лёгкий вариант экскурсий туристам то они увлекутся и вернуться ещё раз и на этот раз не...
43172. Анализ и изучение налоговой системы России 255.5 KB
  Особенность налоговой системы Российской Федерации состоит еще и в том что законодательство регулирующее эту область жизни общества ещё не обрело необходимой стабильности поскольку не достигло сбалансированности чёткости и обоснованности способной удовлетворить все нужды современного российского общества. Актуальность выбранной темы характеризуется тем что одним из важнейших условий стабилизации финансовой системы любого государства является обеспечение устойчивого сбора налогов надлежащей дисциплины налогоплательщиков. В современных...
43173. Разработка 3D модели манипулятора в MASM32 1.36 MB
  В данной работе используются WinApi (Application Programming Interface) функции. Они позволяют пользователю в полной мере использовать все функции предоставленные операционной системой. Одними из областей применения этих функций являются консоли, операции с буфером обмена, управление памятью, управление окнами, файлами, процессами и потоками и т.д. Для построения модели манипулятора с помощью этих функций используется алгоритм видового преобразования, выполняющий умножение матриц и векторов.
43174. Логгер температуры 3.06 MB
  На практике для измерения температуры используют жидкостные и механические термометры термопару термометр сопротивления газовый термометр пирометр термометр сопротивления логгер температуры Так как тема дпнного курсового проекта о логгере то далее рассказ пойдет о них. Существуют несколько видов логгеров: а логгер температуры; б логгер влажности и температуры; в логгер со встроенными сенсорами; г логгер напряжения и тока; д логгер с гнездом для внешних зондов; елоггер температуры с расчетом точки росы; жлоггер для...