42950

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

Курсовая

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

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

Русский

2013-11-03

194.67 KB

18 чел.

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

 

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

74404. КОНУС НАРАСТАНИЯ СТЕБЛЯ 32.5 KB
  Теория справедливая для споровых растений мхов плаунов хвощей и папоротников см. 83 оказалась неверной для голосеменных и покрытосеменных растений. Ганштейн показал что у этих растений единственной апикальной клетки нет конус нарастания их побега массивный многоклеточный и слоистый. По теории гистогенов сформулированной Ганштейном конус нарастания голосеменных и цветковых растений состоит из трех слоев клеток: 1 наружного однослойного дерматогена1 из него возникает кожица эпидермис;2 периблемы состоящей из одного или...
74405. Ксилема 40 KB
  По характеру утолщения стенок различают трахеиды кольчатые спиральные лестничные сетчатые и пористые рис. Пористые трахерды имеют всегда окаймленные поры рис. 101 у хвойных обычно с торусом рис. Трахеиды приспособлены к выполнению двух функций: проведения воды и механического укрепления органа.
74406. Вторичная ксилема 67.5 KB
  Многолетняя деятельность камбия приводит к коренным изменениям в строении древесины и луба. Вторичная ксилема или вторичная древесина Строение древесины хвойных. В трахеидах поздней древесины образованной камбием в конце лета и осенью радиальный размер значительно меньше тангентального; оболочка сильно утолщена а клеточный просвет мал. Трахеиды ранней древесины в соответствии с их строением являются преимущественно элементами проводящей системы; поздние же трахеиды по строению принадлежащие к типу волокнистых трахеид функционируют в...
74407. Вторичная флоэма, или вторичный луб 44.5 KB
  Продольная лубяная паренхима образуется в виде цепочек тяжей лубяной паренхимы или в виде длинных не поделившихся поперечными перегородками клеток камбиформ аналогичных клеткам древесинной паренхимы. Оболочки клеток паренхимы луба обычно одревесневают позже и слабее чем в древесине. Паренхима располагается в лубе в виде тангентальных прослоек у липы радиальными рядами у бузины группами из нескольких клеток у сосен. В паренхиме скопляются запасы в виде крахмала а также в виде гемицеллюлоз откладывающихся в оболочках клеток.
74408. Вторичное утолщение корней 30 KB
  В результате образуется замкнутое камбиальное кольцо с лопастным и только в диархных корнях овальным очертанием на поперечных срезах. У многих многолетних растений деятельность камбия в корнях так же как и в стеблях периодична и часто можно видеть кольца прироста рис. У древесных пород относящихся к двудольным гистологическое различие между древесиной корня и ствола выражено еще более резко: в корнях трахеи и трахеиды более многочисленны и более тесно расположены более тонкостенны а обычно и более широкопросветны1 снабжены более...
74409. Гинецей 59.5 KB
  У некоторых растений столбик не развит рыльце находится непосредственно на завязи и называется сидячим. Так как семяпочки заключены внутри завязи то на них не могут непосредственно как у голосеменных переноситься пылинки.
74410. Половое размножение голосеменных растений 48.5 KB
  Покров вырастает из основания нуцеллуса так называемой халацы обрастает нуцеллус постепенно снизу вверх но на вершине не смыкается оставляя отверстие так называемый пыльцевход или семявход илимикропиле. Из получающихся четырех клеток одна сильно разрастается вытесняя три остальные и большую часть нуцеллуса; это и будет мегаспора...
74411. Заложение и развитие листа 29.5 KB
  Сначала его клетки делятся во всех трех направлениях и зачаток листа растет в толщину и высоту. Довольно рано рост в толщину прекращается и зачаток листа становится плоским. Вначале зачаток листа не разделен на части но вскоре можно различить две части верхнюю и нижнюю причем верхняя апикальная первое время растет быстрее нижней базальной.
74412. Заложение прокамбия и типы строения стеблей 46.5 KB
  Закладывается замкнутое кольцо прокамбия. Довольно часто внутрь от первичной ксилемы часть прокамбия дифференцируется в дополнительные участки внутренней флоэмы барвинок Vinc вьюнок Convolvulus и др. При таком заложении прокамбия листовые следы могут быть совсем незаметны а могут быть хорошо выражены.