42950

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

Курсовая

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

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

Русский

2013-11-03

194.67 KB

15 чел.

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

 

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

777. Заболевания ЖКТ (острый гастрит, гастродуоденит,панкреатит, лямблиоз) 179.5 KB
  Острое воспаление слизистой оболочки желудка, вызванное кратковременным действием сильных раздражителей. Хроническое рецидивирующее, склонное к прогрессированию воспалительно–дистрофическое поражение слизистой оболочки.
778. Особенности протекания кори и краснухи 46.5 KB
  Острое вирусное высокозаразное заболевание, вызываемое фильтрующимся вирусом и сопровождающееся лихорадкой, сыпью, воспалением слизистых оболочек. Острое инфекционное заболевание, вызываемое фильтрующимся вирусом, сопровождающееся появлением сыпи и увеличением затылочных лимфатических узлов.
779. Проект производственных подразделений АТП с детальной разработкой поста по ТР коробки передач автомобиля ГАЗ-3302 319.5 KB
  Определение количества рабочих на объекте проектирования. График межсменного времени и времени работы подвижного состава на линии с графиком работы основных подразделений АТП. Подбор технологического оборудования, организационной и технологической оснастки. Распределение трудоемкости работ ТО и ТР.
780. Підприємництво, його сутність та основні форми 257.5 KB
  Сутність підприємництва, його роль у ринковій економіці. Проблеми розвитку підприємництва в Україні: господарський та податковий кодекс. Особливий вид економічної активності (під якою ми розуміємо доцільну діяльність, направлену на отримання прибутку).
781. Бухгалтерский баланс: техника составления и анализ основных показателей 1.35 MB
  Теоретические основы бухгалтерского баланса, техники его составления и анализа основных показателей. Производственно-экономическая характеристика и организация учетного процесса и внутреннего контроля ОАО Курский завод Маяк. Анализ структуры и динамики имущества и источников финансирования. Методика проведения анализа бухгалтерского баланса.
782. Проблемы правоведения 234.5 KB
  Индивид как субъект права (в частном и публичном праве). Сущность юридического лица (общетеоретический аспект). Право и корпоративные нормы. Корпоративное право. Понятие правовой автономии. Различные аспекты понимания правотворчества. Принципы правотворчества. Правоотношения: различные аспекты понимания. Правоотношения и правовая связь.
783. Модернизация, предпосылки, условия и тенденции развития государственного управления современной России 256.5 KB
  Попытки реорганизации системы государственного управления в период «перестройки». Кризис власти и распад СССР. Конституция РФ 1993 г. становление новой системы органов государственной власти. Реорганизация системы местного управления. Формирование современного федерализма.
784. Формирование психофизиологических характеристик хоккейного вратаря в возрасте 12-14 лет 270.5 KB
  Особенности психологической характеристики вратарей в возрасте 12-14 лет. Методика специфической игровой деятельности и психологической характеристики юных вратарей-хоккеистов. Программа особенностей игровой деятельности и психологическая характеристика хоккейного вратаря 12-14 лет в годичном цикле подготовки.
785. Термодинаміка і статистична фізика 407 KB
  Основою термодинамічного підходу є встановлення зв’язків між безпосередньо вимірюваними в макроскопічних дослідах величинами. Внутрішня енергія або ентропія є однозначною функцією стану. Принцип Нернста стосовно абсолютного нуля температур. Правило рівноваги фаз Максфела.