Вычисление определителя и обратной матрицы

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

При непосредственном раскрытии определителя квадратной матрицы n -го порядка надо найти сумму n! слагаемых, каждое из которых равно произведению n элементов матрицы, взятых по одному с каждого столбца и каждой строки, т.е. надо выполнить порядка n! n операций. Число операций для вычисления определителя 100-го порядка приблизительно равно 100!∙100 ≈ 100^157,9∙100. Такое число операций не способен выполнить ни один из существующих суперкомпьютеров. Тем не менее, современные компьютерные программы вычисления определителей справляются с матрицами и более высокого порядка, используя экономичные алгоритмы. Одним из таких алгоритмов является метод Гаусса.

Если матрица приведена к диагональному или треугольному виду, то её определитель равен произведению диагональных элементов.

Для преобразования матрицы к треугольному виду можно применить метод Гаусса, что потребует порядка 2 n ³/3 операций. Для n = 100 имеем 2 n ³/3 ≈ 0,67∙10⁶. На такой объем арифметических операций современный персональный компьютер тратит не более одной секунды.

Если внимательно проанализировать метод Гаусса, то можно увидеть, что он фактически позволяет одновременно с приведением матрицы коэффициентов к треугольному виду, вычислить определитель этой матрицы. Действительно, определитель матрицы коэффициентов системы уравнений (3.18) равен произведению диагональных элементов, т.е. равен единице. С другой стороны, если к любой строке матрицы прибавить другую строку, умноженную на число, то определитель не изменится. А если строку матрицы разделить на число, отличное от нуля, то определитель матрицы разделится на то же число. Отсюда следует, что в результате преобразований виду (3.18), определитель матрицы коэффициентов системы уравнений (3.9) изменился на множитель, который равен произведению ведущих элементов, т.е. мы получаем формулу для вычисления определителя

.

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

Пример 3.8. Для заданной матрицы вычислить определитель и обратную матрицу.

.

Решение. Используем рабочий лист решения примера 3.3. Введем элементы данной матрицы в диапазоне A 2: D 5.

В ячейке G 17 вычислим произведение ведущих элементов (т.е. тех чисел, на которые делили строки), для этого введем формулу =A2*B7*C12*D17. В ячейку F 17 введем формулу =МОПРЕД(A2:D5) и убедимся в правильности результата. Получим значение –190.

Для вычисления обратной матрицы используем новый рабочий лист.

Рассмотрим расширенную матрицу

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

Прямой ход метода Гаусса.

0. Запишем элементы матрицы в диапазоне A 2: D 5 и элементы единичной матрицы в диапазоне E 2: H 5.

1. В ячейку A 7 вводим формулу =A2/$A2; выделим A 7 и протянем маркер заполнения до ячейки H 7.

Затем в ячейку A 8 вводим формулу =A3-A$7*$A3; выделим A 8 и протянем маркер заполнения до H 8.

Выделим строку A 8: H 8 и протянем маркером заполнения вниз до строки 10.

В ячейках A 7: HE 10 появятся следующие значения:

2. Присвоим строке A 12: H 12 значения строки A 7: H 7:

Выделим диапазон A 12: H 12, введем формулу =A7:H7 и удерживая нажатыми клавиши Ctrl и Shift, нажимаем Enter (Ctrl + Shift + Enter).

В ячейку B 13 вводим формулу =B8/$B8; выделим B 13 и протянем маркер заполнения до H 13.

Затем в ячейку B 14 вводим формулу =B9-B$13*$B9; выделим B 14 и протянем мышью маркер заполнения до H 14.

Выделим диапазон B 14: H 14 и протянем маркер заполнения до H 15.

В ячейках A 12: H 15 появятся следующие значения:

3. Перепишем значения строк A 12: H 15 в строки A 17: H 18, для этого выделим диапазон A 12: H 15, введем формулу =A12:H13 и удерживая клавиши Ctrl и Shift нажатыми, нажимаем Enter.

В ячейку C 19 вводим формулу =C14/$C14; выделим C 19 и протянем мышью за правый нижний угол до H 19.

В ячейку C 20 вводим формулу =C15-C$19*$C15, выделим C 20 и протянем маркер заполнения до H 20. В ячейках A 17: H 20 получим значения:

4. Осталось разделить последнюю строку на ведущий элемент. Сформируем в диапазоне A 22: H 25 матрицы, которые получаются после применения прямого хода метода Гаусса.

Выделим диапазон A 22: H 24 и введем формулу =A17:H19 и, удерживая нажатыми клавиши Ctrl и Shift, нажимаем Enter. В ячейку D 25 вводим формулу =D20/$D20, выделим D 25 и протянем мышью за правый нижний угол до H 25. В диапазоне A 22: H 25 получим:

Далее применим обратный ход метода Гаусса.

5. Выделим A 30: H 30, введем =A25:H25 и нажмем комбинацию клавиш Ctrl + Shift + Enter. В ячейку D 29 введем =D24-D$25*$D24, выделим D 29 и протянем маркер заполнения вправо до H 29. А затем снова выделим D 29 и протянем маркер заполнения влево до A 29. Теперь выделим всю строку A 29: H 29 и протянем вверх до строки 27.

6. Выделим A 34: H 35, введем =A29:H30 и нажмем комбинацию клавиш Ctrl + Shift + Enter. В ячейку C 33 введем =C28-C$34*$C28, выделим C 33 и протянем маркер заполнения вправо до H 33. А затем снова выделим C 33 и протянем маркер заполнения влево до A 33. Теперь выделим всю строку A 33: H 33 и протянем маркером заполнения на одну строку вверх до строки 32.

7. Выделим A 38: H 40, введем формулу =A33:H35 и нажмем комбинацию клавиш Ctrl + Shift + Enter. В ячейку B 37 введем формулу =B32-B$38*$B32, выделим B 37 и протянем маркер заполнения вправо до H 37. Затем снова выделим B 37 и протянем маркер заполнения влево в ячейку A 37.

В диапазоне A 37: D 40 получена единичная матрица, а в диапазоне E 37: H 40 — обратная:

Для проверки полученного результата выделим диапазон A 43: D 46, введем формулу =МУМНОЖ(A2:D5;E37:H40) и нажмем комбинацию клавиш Ctrl + Shift + Enter. Получим единичную матрицу.

Приведем программу на языке C ++ для вычисления определителя матрицы методом Гаусса с выбором главного элемента.

#include <except.h>

#include <iostream.h>

long double detA(long double **a, const int n);

int main(){

long double **a; long double dA; int i,j,n;

cout <<" input n = "; cin >> n;

try {

a= new long double*[n]; for(i=0;i<n;i++) a[i]=new long double[n];

}

catch (xalloc){cout <<"\nCould not allocate\n"; exit(-1);}

cout <<"\n input matrix a \n";

for (i=0; i<n; i++)for (j=0; j<n; j++)cin >> a[i][j];

dA = detA(a, n);

cout << "\n matrix a: ";

for (i=0; i<n; i++){cout << "\n"; for (j=0; j<n; j++) cout <<" "<< a[i][j];}

cout << "\n determinant A = "; cout << dA;

cout << "\n Press Key and Enter to continue";

cin >> i; // for pause

for(i=0;i<n;i++)delete[] a[i];

delete a;

return 0;

}//end main

long double detA(long double **a, const int n){

long double **aa;

int i, k, m, im; long double amm, aim, r,d;

try {aa= new long double*[n];

for(i=0;i<n;i++) aa[i]=new long double[n]; }

catch (xalloc){cout <<"\nCould not allocate\n"; exit(-1);}

for (i = 0; i <= n-1; i++)

for (k = 0; k <= n-1; k++) aa[i][k] = a[i][k];

d = 1;

for (m = 0; m <= n-2; m++) {// m

amm = aa[m][m]; im = m;

for (i = m; i <= n-1; i++)

if(aa[i][m] > amm){amm = aa[i][m]; im = i; } d = d*amm;

if(im!= m)d = - d;

cout <<"\n amm = "<<amm;

if(im!= m)for (k = m; k <= n-1; k++)

{r = aa[im][k]; aa[im][k] = aa[m][k]; aa[m][k] = r;}

for (k = m; k <= n-1; k++)aa[m][k] = aa[m][k]/amm; // 3.16

for (i = m + 1; i <= n-1; i++){// i

aim = aa[i][m];

for (k = m; k <= n-1; k++)

aa[i][k] = aa[i][k] - aa[m][k]*aim; // 3.17

}// end i

}// end m

d = d* aa[n-1][n-1]; cout <<"\n amm = "<< aa[n-1][n-1];

for(i=0;i<n;i++)delete[] aa[i];

delete aa;

return d;

}// end detA

Отметим, что в данной программе исходная матрица a [][]сохраняется, так как для преобразований в подпрограмме-функции detA() используется дополнительный массив aa [][]. Все используемые массивы динамические, их размерность задается во время выполнения программы.

Приведем результат расчета определителя по этой программе:

input n = 4

input matrix a

4 5 2 1 3 5 -1 2 1 2 3 4 0 6 2 7 [столбец чисел ]

amm = 4

amm = 6

amm = 2.25

amm = 3.51852

matrix a:

4 5 2 1

3 5 -1 2

1 2 3 4

0 6 2 7

Determinant A = –190

Press key and Enter to continue

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

#include <except.h>

#include <iostream.h>

int Matr_inv(long double **a, long double **a1, const int n);

int main(){

long double **a; long double **ainv; int i,j,n;

cout <<" input n = "; cin >> n;

try {

ainv= new long double*[n]; for(i=0;i<n;i++) ainv[i]=new long double[n];

}

catch (xalloc){cout <<"\nCould not allocate\n"; exit(-1);}

try {

a= new long double*[n]; for(i=0;i<n;i++) a[i]=new long double[n];

}

catch (xalloc){cout <<"\nCould not allocate\n"; exit(-1);}

cout <<"\n input matrix a \n";

for (i=0; i<n; i++)for (j=0; j<n; j++)cin >> a[i][j];

cout << "\n matrix a: ";

for (i=0; i<n; i++){cout << "\n";

for (j=0; j<n; j++) cout <<" "<< a[i][j];}

Matr_inv(a, ainv, n);

cout << "\n ------------------- matr a: ";

for (i=0; i<n; i++){cout << "\n";

for (j=0; j<n; j++) cout <<" "<< a[i][j];}

cout << "\n -------------------- inv matr ainv: ";

for (i=0; i<n; i++){cout << "\n";

for (j=0; j<n; j++) cout <<" "<< ainv[i][j];}

cout << "\n Press Key and Enter to continue";

cin >> i; // for pause

for(i=0;i<n;i++)delete[] a[i];

delete a;

for(i=0;i<n;i++)delete[] ainv[i];

delete ainv;

return 0;

}//end main

int Matr_inv(long double **a, long double **a1, const int n){

int i, k, m, im; long double amm, aim, r;

for (i = 0; i <= n-1; i++)

for (k = 0; k <= n-1; k++){

if(i==k)a1[i][k] = 1; else a1[i][k] = 0;}

// 1.

for (m = 0; m <= n-2; m++) {// m

amm = a[m][m]; im = m;

for (i = m; i <= n-1; i++)

if(a[i][m] > amm){amm = a[i][m]; im = i; }

if(im!= m){

for (k = m; k <= n-1; k++){

r = a[im][k]; a[im][k] = a[m][k]; a[m][k] = r;}

for (k = 0; k <= n-1; k++){

r = a1[im][k]; a1[im][k] = a1[m][k]; a1[m][k] = r;}

}

for (k = m; k <= n-1; k++)a[m][k] = a[m][k]/amm;

for (k = 0; k <= n-1; k++) a1[m][k] = a1[m][k]/amm;

for (i = m + 1; i <= n-1; i++){// i

aim = a[i][m];

for (k = m; k <= n-1; k++)a[i][k] = a[i][k] - a[m][k]*aim;

for (k = 0; k <= n-1; k++)a1[i][k] = a1[i][k] - a1[m][k]*aim;

}// end i

}// end m

// 2.

amm = a[n-1][n-1]; a[n-1][n-1] = 1;

for (k = 0; k <= n-1; k++) a1[n-1][k] = a1[n-1][k]/amm;

for (m = n-1; m >= 0; m--){

for (i = m-1; i >= 0; i--){// i

aim = a[i][m]; a[i][m] = 0;

for (k = 0; k <= n-1; k++)a1[i][k] = a1[i][k] - a1[m][k]*aim;

}// end i

}// end m

return 0;

}// end Matr_inv

Подпрограмма Matr_inv(a, a1, n) не сохраняет исходную матрицу. В результате выполнения программы в массиве a формируется единичная матрица, а в массиве a 1 — обратная матрица. Приведем результат выполнения программы для примера 3.8:

input n = 4

input matrix a

4 5 2 1 3 5 -1 2 1 2 3 4 0 6 2 7 [столбец чисел ]

matrix a

4 5 2 1

3 5 -1 2

1 2 3 4

0 6 2 7

---------------------------- matr a

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 0

---------------------------- inv matr ainv

-0,142105 0,373684 0,447368 -0,342105

0,263158 -0,210526 -0,421053 0,263158

0,278947 -0,363158 -0,0263158 0,0789474

-0,305263 0,284211 0,368421 -0,105263

Press Key and Enter to continue

Как видим, результат совпадает с обратной матрицей, найденной в программе Excel обычным методом Гаусса.

Поиск по сайту: