Macierze w C++ cz. 3

Wstęp

Artykuł przeprowadzi punkt po punkcie jak wprowadzoną przez użytkownika macierz odwrócić i pomnożyć dwie macierze. Uzupełnieniem kodu jest biblioteka matrix.h opracowana na podstawie wcześniejszych artykułów.

Implementacja

Kopiowanie

Przed przystąpieniem do pisania funkcji mnożenia i odwracania macierzy napiszemy funkcję kopiującą macierz.

1. Matrix* copyMatrix(Matrix* mat){
2.   Matrix* matrix = new Matrix();
3.   matrix->n = mat->n;
4.   matrix->m = mat->m;
5.   double** table = new double*[matrix->n];
6.   for(int i = 0; i < matrix->n; i++){
7.     double* row = new double[matrix->m];
8.     for(int j = 0; j < matrix->m; j++){
9.       row[j] = mat->data[i][j];
10.     }
11.     table[i] = row;
12.   }
13.   matrix->data = table;
14.   return matrix;
15. }

(1.) Nasz funkcja zwróci wskaźnik na nową macierz. Jako argument przyjmujemy macierz do skopiowania. (2.) Tworzymy nową macierz i (3. - 4.) ustalamy wymiary pobierając je z argumentu mat. (5. - 13) Kopiujemy dane z mat do nowej macierzy matrix. Na sam koniec (14.) zwracamy nowy wskaźnik.

Zapis można uprościć i użyć dostępnej funkcji createMatrix(), która tworzy nową macierz o wymiarach n x m. To podejście jednak zwiększa czas kopiowania. Najpierw tworzymy macierz i ustawiamy każdy lement na 0. Potem przypisujemy dopiero żądane wartości. Lepiej w tym przypadku niejako skopiować funkcję createMatrix() i ją zmodyfikować.

Mnożenie macierzy

Do wyznaczania macierzy odwrotnej wykorzystamy zredukowaną postać schodkową. Zadaną macierz rozszerzymy o macierz jednostkową. Następnie przeprowadzimy redukcję i macierz po prawej stronie będzie naszą macierzą odwrotną. Przykładowo:

Deklarujemy funkcje:

1. bool inverseMatrix(Matrix* matrix){
2.   if(matrix->m != matrix->n)
3.     return false;

Funkcja będzie zwrać prawdę, gdy odwracanie się powiedzie i fałsz kiedy nie jest to możliwe. Sprawdzamy warunek konieczny do odwrócenia czyli czy macierz jest nieosobliwa. To jak wyznacznik jest różny od 0 (implementacja tego w części 4) oraz czy macierz jest kwadratowa. Jeśli macierz nie spełnia warunku to zwracamy fałsz.

4.   Matrix* mat = new Matrix();
5.   mat->n = matrix->n;
6.   mat->m = matrix->m * 2;
7.   double** table = new double*[mat->n];
8.   for(int i = 0; i < mat->n; i++){
9.     double* row = new double[mat->m];
10.     for(int j = 0; j < matrix->m; j++)
11.       row[j] = matrix->data[i][j];
12.     for(int j = matrix->m; j < mat->m; j++)
13.       row[j] = 0;
14.     row[matrix->m+i]=1;
15.     table[i] = row;
16.   }
17.   mat->data = table;

Tworzymy nową macierz o wymiarach n x 2m. (8. 9.) Do pierwszej części przepisujemy wartości z zadanej macierzy. (10. 11.) Drugą część wypełniamy zerami pamiętając, żeby po prawej stronie była macierz jednostkowa. Jedynki wpisuje linijka (12.).

18.   reducedRowEchelonForm(mat);
19.   for(int i = 0; i < mat->n; i++){
20.     for(int j = 0; j < matrix->m; j++)
21.       matrix->data[i][j] = mat->data[i][matrix->m + j];
22.     delete[] mat->data[i];
23.   }
24.   delete[] mat->data;
25.   return true;
26. }

(18.) Wywołujemy funkcję reducedRowEchelonForm(), aby zredukować macierz to zredukowanej postaci schodkowej. Dzięki temu po prawej stronie tworzy się macierz odwrotna. (19. - 24.) Przepisujemy prawą macierz do oryginalnej macierzy podanej w argumencie. Po przepisaniu każdej linijki (22.) dealokujemy pamięć z tymczasowej macierzy. (23.) Usuwamy zadeklarowną macierz tymczasową do końca. (25.) Na sam koniec sygnalizujemy, że wszystko się udało i zwracamy true.

Mnożenie macierzy

Tym razem nasza funkcja będzie zwracać kompletnie nową macierz, więc nagłówek deklarujemy tak:

1. Matrix* multiplicationOfMatrixes(Matrix* matA, Matrix* matB){
2.   if(matA->n != matB->m)
3.     return NULL;
4.   Matrix* mat = createMatrix(matA->n, matB->m);
5.   for(int i = 0; i < mat->n; i++)
6.     for(int j = 0; j < mat->m; j++)
7.       for(int k = 0; k < matA->m; k++)
8.         mat->data[i][j] += matA->data[i][k] * matB->data[k][j];
9.   return mat;
10. }

Następnie sprawdzamy czy dane macierze da się pomnożyć czyli czy ilość wierszy w macierzy A nie jest różna od ilości kolumn macierzy B. Jeśli tak nie jest to zwracamy NULL. Będzie to sygnał, że danych macierzy nie da się pomnożyć. (4.) Tworzymy nową macierz o wymiarach n z A i m z B. (5.) Dla każdego wiersza i (6.) każdej kolumny (8.) obliczamy wartość pola i, j nowej macierzy. (9.) Na sam koniec zwracamy nową macierz.

Testowanie funkcji

Na sam koniec testujemy stworzone funkcje: użytkownik wprowadza poprawną macierz, kopiujemy ją, odwracamy i wypisujemy. Później mnożymy obie macierze. W rezultacie powinniśmy otrzymać macierz jednostkową.

Czasami funkcja nieco różni się od macierzy jednostkowej, ale jest to problem zaokrąglania mnożenia i dodawania spowodowane ograniczeniami przechowywania liczb rzeczywistych w komputerze.

1. int main () {
2.   setlocale(LC_ALL,"");
4.   Matrix* mat = readMatrix();
5.   cout << "Użytkownik wprowadził macierz M postaci: \n";
6.   writeMatrix(mat);
8.   Matrix* cmat = copyMatrix(mat);
10.   inverseMatrix(cmat);
11.   cout << "Wyliczamy wartość M^-1:\n";
12.   writeMatrix(cmat);
14.   Matrix* wmat = multiplicationOfMatrixes(mat, cmat);
15.   cout << "Wynik mnożenia M * M^-1:\n";
16.   writeMatrix(wmat);
18.   system("pause");
19.   return 0;
20. }

• Kod źródłowy Implementacja