Лабораторная работа 13

Вычисление обратной матрицы методом Гаусса-Жордана.

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

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

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

Цели работы:

- разработка программы, реализующей алгоритм вычисления обратной матрицы методом Гаусса-Жордана;

- исследование влияния ошибок округления на результаты вычисления.

Алгоритм вычисления обратной матрицы

Прежде чем приступать к программированию, разработаем численный пример получения обратной матрицы методом Гаусса-Жордана. Это позволит лучше понять алгоритм метода и использовать этот пример в качестве контрольного при разработке алгоритма программы.

Предположим, имеется матрица

Метод Гаусса-Жордана предполагает нахождение обратной матрицы путем решения следующей системы уравнений

(1)

относительно х, у и z с помощью обычной процедуры последователь­ного исключения (здесь символы х, у, z и а, b, с характеризуют скалярные величины).

Умножение обеих частей уравнения слева на А^-1 дает решение в виде

, (2)

если A^-1 существует.

Следовательно, если решение системы (1) относительно х, у и z выражено в явном виде через a, b и c и записано в матричной форме, то приводящая к решению матрица равна A^-1. Воспроизведем полно­стью этот процесс.

Допустим, что уравнения (1) имеют следующий вид:

2х + 5у + 7z = a, (3)

3х + 9у + 15z = b, (4)

5х + 16y + 20z = c. (5)

Деление (3) на 2 дает.

x + 2,5y + 3,5z = 0,5a. (6)

Умножим обе части уравнения (6) на три и вычтем их из (4), а затем, умножив обе части уравнения (6) на пять, вычтем их из (5). Тогда

1,5y + 4,5z = b - 1,5a (7)

и

3,5y + 2,5z = c - 2,5a. (8)

Разделив (7) на 1,5 и умножив (8) на 2, получим

у + 3z = b/1,5 - a, (9)

7y + 5z = 2c - 5a. (10)

Вычитая (9), умноженное на 7, из (10), мы получим

-16z = 2c - 5a - 7 (b/1,5 - a).

Следовательно,

z = (2a - 7b/1,5 + 2c)/(- 16) = (-3a + 7b - 3c)/24. (11)

Подстановка z в (9) приводит к следующему результату:

у = (—15a — 5b + 9c)/24, (12)

а подстановка y и z в (6) дает

x = (60a — 12b — 12c)/24. (13)

Последние три результата могут быть представлены в матричном виде следующим образом:

= . (14)

Сравнивая этот результат с (2), мы приходим к заключению, что

A^-1= .

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

Так как компьютер работает с числами (а не с переменными a, b, c), то для того чтобы решение системы (1) относительно x, у и z выразить в явном виде через a, b и c и записать в матричной форме, умножим правую часть системы уравнений (1) на единичную матрицу и будем выполнять над ней те же преобразования, что и над исходной матрицей.

Алгоритм преобразования состоит из двух шагов:

1. Прямой ход. В результате исходная матрица преобразуется в верхнюю треугольную матрицу.

2. Обратный ход. В результате исходная матрица преобразуется в единичную, а введенная единичная матрица – в матрицу, обратную исходной, то есть система уравнений (1) преобразуется в систему уравнений (2).

Выполним с помощью этого алгоритма рассмотренный выше пример:

= .

Шаг 1. Прямой ход.

Исключаем x из нижележащих строк:

.

Исключаем y:

.

Устанавливаем коэффициент при z равным 1:

.

Шаг 1. Обратный ход.

Исключаем z из всех вышележащих строк:

Исключаем y из всех вышележащих строк:

.

Представим результат в матричном виде:

= .

Сравнив результат с (14), убеждаемся, что все вычисления сделаны правильно.

Точность вычисления обратной матрицы.

Основной источник погрешностей при выполнении вычислений на ЭВМ – это ошибки округления. Ошибки округления всегда возникают в последнем значащем разряде. Однако накопление ошибок в связи с выполнением большого количества вычислений может повлиять на последние два и более разрядов.

Для уменьшения погрешностей округления нужно использовать более «длинные» типы данных для представления коэффициентов, например, double вместо float.

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

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

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

Прежде чем приступать к обращению матрицы, нужно исходную матрицу умно­жить справа или слева на некоторую диагональную матрицу для того, чтобы «исправить» элементы строки или столбца и привести их величину в со­ответствие с другими элементами. Разумеется, следует помнить о том, что если мы хотим получить матрицу, обратную к исходной, то в та­ком случае необходимо матрицу, обратную к «исправленной» исходной, умножить на матрицу, обратную к ис­пользованной в вычислениях диагональной матрице.

Пример. Рассмотрим матрицу

Элементы второго ее столбца по своей величине существенно превыша­ют элементы первого столбца. Поэтому выразим А в форме произведе­ния двух матриц В и D, где D — диагональная матрица:

и

Тогда, поскольку А = BD, то А^-1 = D^-1B^-1, или

= = = .

Задание. Создать функцию для вычисления обратной матрицы по методу Гаусса-Жордана. Размер матрицы передавать в функцию в качестве параметра.

Применить функцию для решения системы линейных алгебраических уравнений.
Исследовать влияние коэффициентов исходной матрицы на точность вычисления обратной матрицы.

Шаги выполнения задания.

Часть 1.

1. Разработать схему алгоритма для вычисления обратной матрицы методом Гаусса-Жордана.

2. Разработать программу, реализующую метод Гаусса-Жордана. Для ускорения процесса разработки программы на этом шаге следует сконцентрироваться на реализации алгоритма и не использовать динамическую память для хранения матриц и не оформлять реализацию алгоритма в виде функции.

3. Отладить программу, используя контрольный пример.

4. Оформить алгоритм в виде функции для вычисления обратной матрицы по методу Гаусса-Жордана. Размер матрицы передавать в функцию в качестве параметра.

Часть 2.

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

2. Применить функцию для решения системы линейных алгебраических уравнений.

3. Исследовать влияние коэффициентов исходной матрицы на точность вычисления обратной матрицы.