Вычисление обратной матрицы методом исключения Гаусса

СОДЕРЖАНИЕ

Введение

1 Постановка задачи

• 2 Математические и алгоритмические основы решения задачи
• 2.1 Метод Гаусса для решения СЛАУ
• 2.2 Обращение матрицы
• 3 Функциональные модели и блок-схемы решения задачи
• 4 Программная реализация решения задачи
• 5 Пример выполнения программы
• Заключение
• Список использованных источников и литературы

ВВЕДЕНИЕ

В отличие от матричного метода и метода Крамера, метод Гаусса может быть применен к системам линейных уравнений с произвольным числом уравнений и неизвестных. Метод Гаусса - один из основных результатов линейной алгебры и аналитической геометрии, к нему сводятся множество других теорем и методов линейной алгебры (теория и вычисление определителей, решение систем линейных уравнений, вычисление ранга матрицы и обратной матрицы, теория базисов конечномерных векторных пространств и т.д.).

Задача поиска решений системы линейных уравнений имеет не только самостоятельное значение, но часто является составной частью алгоритма решения многих нелинейных задач. С помощью метода исключения Гаусса также вычисляется обратная матрица.

Вычисление обратной матрицы методом Гаусса заключается в том, что любую неособенную матрицу А путем элементарных преобразований только столбцов (или только строк) можно привести к единичной матрице Е, и если совершенные над матрицей А элементарные преобразования в том же порядке применить к единичной матрице Е, то в результате получится обратная матрица. Удобно совершать элементарные преобразования над матрицами А и Е одновременно, записывая обе матрицы рядом через черту. При отыскании канонического вида матрицы с целью нахождения ее ранга можно пользоваться преобразованиями строк и столбцов. Если нужно найти обратную матрицу, в процессе преобразований следует использовать только строки или только столбцы.

Целью данной курсовой работы является Лисп - реализация вычисления обратной матрицы методом исключения Гаусса.

1 Постановка задачи

Требуется найти для исходной матрицы А обратную матрицу А^-1

по методу исключения Гаусса.

Пример 1. Методом исключения Гаусса найдем матрицу, обратную к матрице

Решение:

К матрице А справа приписывается единичная матрица того же порядка (А|E)

Матрица (А|E) приводится элементарными преобразованиями первого и второго типов к ступенчатому виду

Последняя матрица имеет ступенчатый вид

3. Выписывается обратная матрица. Это матрица, стоящая справа в последней преобразованной матрице.

В последней матрице слева стоит единичная матрица E.

Пример 2.

Методом Гаусса найдем матрицу, обратную к матрице

.

Решение:

К матрице А справа приписывается единичная матрица того же порядка (А|E)

Матрица (А|E) приводится элементарными преобразованиями первого и второго типов к ступенчатому виду

поменяем местами вторую и третью строки

Последняя матрица имеет ступенчатый вид.

3. Полученная ступенчатая матрица элементарными преобразованиями 1-го, 2-го и 3-го типов приводится к виду, где слева будет матрица Е. Преобразования начинаются с последней строки.

К элементам второй строки прибавим элементы третьей, умноженные на 4, а к элементам первой строки прибавим элементы третьей, умноженные на 5:

Все элементы второй строки умножим на (-1)

Из элементов первой строки вычитаем элементы второй, умноженные на 2



4. Выписывается обратная матрица. Это матрица, стоящая справа в последней преобразованной матрице.

В последней матрице слева стоит единичная матрица E.

2 Математические и алгоритмические основы решения задачи

2.1 Метод Гаусса для решения СЛАУ

Метод Гаусса в математическом варианте состоит в следующем:

1. ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее. Если нашли ненулевой элемент в k-й строке, то при помощи элементарного преобразования первого рода меняем местами первую и k-ю строки, добиваясь того, чтобы первый элемент первой строки был отличен от нуля;

2. используя элементарные преобразования второго рода, обнуляем все элементы первого столбца, начиная со второго элемента. Для этого от строки с номером k вычитаем первую строку, умноженную на коэффициент a_k1/a₁₁ ;

3. переходим ко второму столбцу (или j-му, если все элементы первого столбца были нулевыми), и в дальнейшем рассматриваем только часть матрицы, начиная со второй строки и ниже. Снова повторяем пункты 1) и 2) до тех пор, пока не приведем матрицу к ступенчатому виду.

При программировании метода Гаусса нужно учитывать три отличия:

1. индексы строк и столбцов матрицы начинаются с нуля, а не с единицы;

2. недостаточно найти просто ненулевой элемент в столбце. В программировании все действия с вещественными числами производятся приближенно, поэтому можно считать, что точного равенства вещественных чисел вообще не бывает. Некоторые компиляторы даже выдают предупреждения на каждую операцию проверки равенства вещественных чисел. Поэтому вместо проверки на равенство нулю числа a_ij следует сравнивать его абсолютную величину a_ij с очень маленьким числом е (например, е = 0.00000001). Если a_ij =< е, то следует считать элемент a_ij нулевым;

3. при обнулении элементов j-го столбца, начиная со строки i + 1, мы к k-й строке, где k > i, прибавляем i-ю строку, умноженную на коэффициент r = -a_kj/a_ij.

Такая схема работает нормально только тогда, когда коэффициент r по абсолютной величине не превосходит единицы. В противном случае, ошибки округления умножаются на большой коэффициент и, таким образом, экспоненциально растут. Математики называют это явление неустойчивостью вычислительной схемы. Если вычислительная схема неустойчива, то полученные с ее помощью результаты не имеют никакого отношения к исходной задаче. В нашем случае схема устойчива, когда коэффициент r = -a_kj/a_ij не превосходит по модулю единицы. Отсюда следует, что при поиске разрешающего элемента в j-м столбце необходимо найти не первый попавшийся ненулевой элемент, а максимальный по абсолютной величине. Если он по модулю не превосходит е, то считаем, что все элементы столбца нулевые; иначе меняем местами строки, ставя его на вершину столбца, и затем обнуляем столбец элементарными преобразованиями второго рода.

Основная идея метода Гаусса - привести матрицу систему к диагональному виду, то есть все элементы главной диагонали - нули. Для приведения матрицы к такому виду, мы выбираем самую верхнюю строку матрицы, и вычитаем её из всех остальных строк, умножив её для каждой строки на некий коэффициент, так, что самый левый столбец ниже главной диагонали заполнен нулями. Вычитаемая с коэффициентом строка называется текущей строкой. Выбирая текущую строку вначале верхнюю, а потом всё ниже и ниже, мы добьёмся, что все элементы ниже главной диагонали будет равны нулю. Эту часть метода - обработка строк по текущей строке и предстоит распараллеливать.

Суть метода заключается в последовательном исключении неизвестных. Рассмотрим систему линейных уравнений:

Разделим обе части 1-го уравнения на a₁₁ > 0, затем: 1) умножим на а₂₁ и вычтем из второго уравнения 2) умножим на а₃₁ и вычтем из третьего уравнения и т.д. Получим:, где d_1j = a_1j/a₁₁, j = 2, 3, …, n+1. d_ij = a_ij - a_i1d_1j i = 2, 3, … , n; j = 2, 3, … , n+1. Далее повторяем эти же действия для второго уравнения системы, потом - для третьего и т.д.

2.2 Обращение матрицы

Обратная матрица -- такая матрица A^-1, при умножении на которую исходная матрица A даёт в результате единичную матрицу E:

AA ^{? 1} = A ^{? 1}A = E

Квадратная матрица обратима тогда и только тогда, когда она невырожденная, то есть её определитель не равен нулю. Для неквадратных матриц и сингулярных матриц обратных матриц не существует. Однако, возможно обобщить это понятие и ввести псевдообратные матрицы, похожие на обратные по многим свойствам.

Свойства обратной матрицы:

1) , где det обозначает определитель.

2) (AB) ^{? 1} = B ^{? 1}A ^{? 1} для любых двух обратимых матриц A и B.

3) (A^T) ^{? 1} = (A ^{? 1})^T где * ^T обозначает транспонированную матрицу.

4) (kA) ^{? 1} = k ^{? 1}A ^{? 1} для любого коэффициента.

5) Если необходимо решить систему линейных уравнений Ax = b, (b -- ненулевой вектор) где x -- искомый вектор, и если A ^{- 1} существует, то x = A ^{? 1}b. В противном случае либо размерность пространства решений больше нуля, либо их нет вовсе.

Пусть имеем матрицу A вида

и пусть B - единичная диагональная матрица такого же размера.

.

Создадим рабочую матрицу R размером просто присоединив матрицу B справа к матрице A :

.

Над строками такой расширенной матрицы будем производить преобразования, аналогичные тем, которые были описаны в п.2.1. Левую часть матрицы R будем называть подматрицей A, правую - подматрицей B. Весь процесс преобразования матрицы R разобьем на 3 этапа.

1 этап. Выполним преобразования строк матрицы так, чтобы все элементы, лежащие ниже диагональных элементов подматрицы A, обратились в нули. При этом может использоваться выбор главного элемента.

2 этап. Выполним преобразования так, чтобы все элементы, лежащие выше диагональных элементов подматрицы A, обратились в нули. Преобразования надо выполнять в обратном порядке: со столбца номер n и до столбца номер 2.

3 этап. Каждую строку расширенной матрицы R с номером i делим на диагональный элемент aii .

После завершения процедуры подматрица A превращается в единичную диагональную матрицу, а подматрица B будет равна искомой обратной матрице.

3 Функциональные модели и блок-схемы решения задачи

Блок-схема решения задачи представлена на рисунке 1.

Условные обозначения:

· MATR - матрица;

· B - вспомогательный столбец;

· ROW - текущая строка;

· X - обратная матрица;

· N - размерность матрицы;

· FLAG- флаг, определяющий являются ли элементы матрицы нулевыми;

· GET_B - функция, преобразует входную матрицу в диагональную;

· RES - флаг, определяющий возможно ли получить обратную матрицу;

· I - рабочая переменная;

· J - рабочая переменная;

· K - рабочая переменная;

· TMP - рабочая переменная.

Рисунок 1 - Блок-схема решения задачи для функции INVERS_MATRIX

4 Программная реализация решения задачи

;ФУНКЦИЯ ПРЕОБРАЗУЕТ ВХОДНУЮ МАТРИЦУ В ДИАГОНАЛЬНУЮ

(DEFUN GET_B (MTR B ROW N)

;ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ

(DECLARE (SPECIAL R))

(DECLARE (SPECIAL FLAG))

(DECLARE (SPECIAL ROW))

(DECLARE (SPECIAL TMP))

(SETQ FLAG T)

;ЕСЛИ В ТЕКУЩЕМ СТОЛБЦЕ ВСЕ ЭЛЕМЕНТЫ НИЖЕ ТЕКУЩЕЙ СТРОКИ РАВНЫ 0 - НЕТ РЕШЕНИЯ

(IF (= ROW (- N 1)) (SETQ R (/= (AREF MTR ROW ROW) 0))

(PROGN

(DO

((I ROW))

((>= I N))

;ЕСЛИ ЭЛЕМЕНТ НА ДИАГОНАЛИ - НУЛЕВОЙ,

;ПОИСК В ТЕКУЩЕМ СТОЛБЦЕ НЕНУЛЕВОЙ ЭЛЕМЕНТ В СТРОКАХ НИЖЕ ТЕКУЩЕЙ ДЛЯ ПЕРЕСТАНОВКИ

(IF (/= (AREF MTR I ROW) 0)

(PROGN

(SETQ FLAG NIL)

(SETQ ROW I)

(SETQ I N)

)

)

(SETQ I (+ I 1))

)

(IF FLAG (SETQ R NIL)

(PROGN

(IF (/= ROW ROW)

(PROGN

(DO

((I ROW))

((>= I N))

(SETQ TMP (AREF MTR ROW I))

(SETF (AREF MTR ROW I) (AREF MTR ROW I))

(SETF (AREF MTR ROW I) TMP)

(SETQ I (+ I 1))

)

(DO

((I 0))

((>= I N))

(SETQ TMP (AREF B ROW I))

(SETF (AREF B ROW I) (AREF B ROW I))

(SETF (AREF B ROW I) TMP)

(SETQ I (+ I 1))

)

)

)

;ПЕРЕСЧИТЫВАЕМ ЭЛЕМЕНТЫ В МАТРИЦАХ

(DO

((I (+ ROW 1)))

((>= I N))

(SETQ TMP (/ (* (AREF MTR I ROW) -1) (AREF MTR ROW ROW)))

(DO

((K ROW))

((>= K N))

(SETF (AREF MTR I K) (+ (AREF MTR I K) (* (AREF MTR ROW K) TMP)))

(SETQ K (+ K 1))

)

(DO

((K 0))

((>= K N))

(SETF (AREF B I K) (+ (AREF B I K) (* (AREF B ROW K) TMP)))

(SETQ K (+ K 1))

)

(SETQ I (+ I 1))

)

(SETQ R (GET_B MTR B (+ 1 ROW) N))

)

)

)

)

)

;ФУНКЦИЯ ОБРАЩАЕТ МАТРИЦУ

(DEFUN INVERS_MATRIX (MTR N X)

;ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ

(DECLARE (SPECIAL RESULT))

(DECLARE (SPECIAL B))

(DECLARE (SPECIAL CURROWANDCOL))

(SETQ B (MAKE-ARRAY (LIST N N) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))

(DO

((I 0))

((>= I N) B)

(DO

((K 0))

((>= K N) B)

(SETF (AREF B I K) (IF (= I K) 1 0))

(SETQ K (+ K 1))

)

(SETQ I (+ I 1))

)

;ПРЕОБРАЗУЕМ МАТРИЦУ В ДИАГОНАЛЬНУЮ

(SETQ RESULT (GET_B MTR B 0 N))

(WHEN RESULT

(DO

((J 0))

((>= J N))

(DO

((I (- N 1)))

((< I 0))

(SETF (AREF X I J) (AREF B I J))

(DO

((K (+ I 1)))

((>= K N))

(SETF (AREF X I J) ( - (AREF X I J) (* (AREF X K J) (AREF MTR I K))))

(SETQ K (+ K 1))

)

(SETF (AREF X I J) (FLOAT (/ (AREF X I J) (AREF MTR I I))))

(SETQ I (- I 1))

)

(SETQ J (+ J 1))

)

)

)

;СЧИТЫВАЕМ С ФАЙЛА МАТРИЦУ И ЕЕ РАЗМЕРНОСТЬ

(SETQ INPUT (OPEN " D:\\MATRIX.TXT" :DIRECTION :INPUT))

(SETF SIZE (READ INPUT))

(SETQ MATRIX (MAKE-ARRAY (LIST SIZE (+ SIZE 1)) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))

(SETF MATRIX (READ INPUT))

(CLOSE INPUT)

;ВЫЧИСЛЯЕМ ОБРАТНУЮ МАТРИЦУ

(SETQ RES (MAKE-ARRAY (LIST SIZE SIZE) :ELEMENT-TYPE 'INTEGER :INITIAL-ELEMENT 0))

;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ

(SETQ OUTPUT (OPEN " D:\\INVERS_MATRIX.TXT" :DIRECTION :OUTPUT))

(IF (INVERS_MATRIX MATRIX SIZE RES) (PRINT "Resheniya dlya dannoi matrizy ne suwestvuet" OUTPUT) (PRINT RES OUTPUT))

(TERPRI OUTPUT)

(CLOSE OUTPUT)

;КОНЕЦ

5 Пример выполнения программы

Пример 1.

Рисунок 2 - Входные данные

Рисунок 3 - Выходные данные

Пример 2.

Рисунок 4 - Входные данные

Рисунок 5 - Выходные данные

Пример 3.

Рисунок 6 - Входные данные

Рисунок 7 - Выходные данные

ЗАКЛЮЧЕНИЕ

Проблема повышения качества вычислений, как несоответствие между желаемым и действительным, существует и будет существовать в дальнейшем. Ее решению будет содействовать развитие информационных технологий, которое заключается как в совершенствовании методов организации информационных процессов, так и их реализации с помощью конкретных инструментов - сред и языков программирования.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы

Архангельский, Н.А. Вычислительные методы алгебры в приемах и задачах. [Текст] / Н.А. Архангельский - М.: МАИ, 2001. C. 812.

Калиткин, Н.Н. Численные методы. [Электронный ресурс] / Н.Н. Калиткин. - М.: Питер, 2001. С. 504.

Кремер, Н.Ш. Высшая математика для экономистов: учебник для студентов вузов. [Текст] / Н.Ш.Кремер, 3-е издание - М.:ЮНИТИ-ДАНА, 2006. C. 412.

Обратная матрица [Электронный ресурс] - Режим доступа: http://ru/wikipedia.org/wiki/Обратная _матрица.

Семакин, И.Г. Основы программирования. [Текст] / И.Г.Семакин, А.П.Шестаков. - М.: Мир, 2006. C. 346.

Симанков, В.С. Основы функционального программирования [Текст] / В.С. Симанков, Т.Т. Зангиев, И.В. Зайцев. - Краснодар: КубГТУ, 2002. - 160 с.

Степанов, П.А. Функциональное программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В. Бржезовский. - М.: ГУАП, 2003. С. 79.

Хювенен Э. Мир Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. - М.: Мир, 1990. - 460 с.