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

 

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

25524. Конструкционные сплавы черных металлов. Стали и чугуны 136 KB
  Легированная сталь — сталь, которая кроме обычных примесей содержит элементы, специально вводимые в определённых количествах для обеспечения требуемых физических или механических свойств. Эти элементы называются легирующими.
25526. Возможности устранения супружеских конфликтов 15.44 KB
  Как уже указывалось чтобы научиться управлять ссорой нужно научиться управлять собственным эмоциональным состоянием. Тогда получается что для того чтобы эффективно управлять ситуацией возникновения ссоры и попытаться предотвратить ее человек должен научиться управлять собственным раздражением недовольством уметь сводить их на нет. И для того чтобы эффективно управлять ситуацией возникновения ссоры и попытаться предотвратить ее человек должен научиться управлять собственным раздражением недовольством уметь сводить их на нет.
25527. Характеристика репродуктивного здоровья молодежи. Факторы, влияющие на его состояние 24.98 KB
  Поскольку желание мужчин при выборе методов контрацепции учитывают большинство женщин интересно исследование характера и особенностей контрацептивного поведения и информированности по этим вопросам юношейподростков и мужчин возраст 1545 лет – городских жителей проведенное в ряде территорий Российской Федерации . Несмотря на то что большинство опрошенных мужчин 815 знают о противозачаточных средствах 806 назвали презерватив 599 – ВМС 496 – гормональную контрацепцию 436 мужчин вообще не обсуждают 512 не...
25528. Репродуктивные установки и репродуктивное поведение молодежи и молодых семей 19.21 KB
  Браки и половая жизнь до вступления в брак В большинстве регионов мира средний возраст вступления в брак повышается и в настоящее время в подростковом возрасте в мире заключается браков меньше чем 10 лет назад. Рискованное поведение подростков В период взросления подростки часто оказываются в ситуациях риска. В тех случаях когда в результате раздоров в семье социальных изменений гражданских беспорядков или войн нарушены семейные связи или системы социального обеспечения положение подростков становится еще хуже. Опасность для...
25529. Роль членов семьи (матери, отца, бабушек, дедушек) в воспитании ребенка 16.31 KB
  Поэтому феномен матери всегда был есть и будет актуальным. Безусловная любовь матери дает ребенку: чувство защищенности; безопасность; убежище преображает опасный и незнакомый мир в нормальную сферу обитания; говорит о его важности и желанности в жизни; дает прочное ощущение надежности; питает не только физической но и душевной пищей; дарит способность доверять людям миру себе; вкладывает чувство принадлежности к роду нации устанавливает границы личностного пространства что позволяет ребенку брать ответственность на...
25530. Влияние ситуации развода на ребенка 15.78 KB
  Влияние ситуации развода на ребенка. Тащева на усугубление переживаний ребенка влияют следующие обстоятельства: предшествующие разводу ссоры родителей и неизбежное ухудшение обращения с ребенком в этой ситуации; ощущение ребенком эмоционального отсутствия ушедшего родителя восприятие его ухода как обесценивания самого ребенка; изменение интенсивности общения с оставшимся родителем; возможные ухудшения отношения ребенка со сверстниками. Бывшие супруги могут настраивать ребенка друг против друга внося еще больший психологический дискомфорт в...
25531. СИМПАТИЯ 18.58 KB
  Иногда как следствие избирательной положительной реакции на привлекательную внешность поведение черты характера другого человека аттракция. На первых этапах общения заметнее всего будет воздействие наиболее открытых для наблюдения характеристик человека не требующих для своего опознания скольконибудь длительного времени таких как социальнодемографическая принадлежность социальный статус и т. Но следует отметить что единого эталона красоты нет представления о красоте человека многообразны тем более для людей разных культур.