Strona główna » Algorytmy » Artykuły » Macierze w C++ cz. 3
1011

Macierze w C++ cz. 3

· część 1 · część 2 · część 3 · Wyznacznik ·

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.

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

  1.   reducedRowEchelonForm(mat);
  2.   for(int i = 0; i < mat->n; i++){
  3.     for(int j = 0; j < matrix->m; j++)
  4.       matrix->data[i][j] = mat->data[i][matrix->m + j];
  5.     delete[] mat->data[i];
  6.   }
  7.   delete[] mat->data;
  8.   return true;
  9. }

(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,"");
  3.   Matrix* mat = readMatrix();
  4.   cout << "Użytkownik wprowadził macierz M postaci: \n";
  5.   writeMatrix(mat);
  6.   Matrix* cmat = copyMatrix(mat);
  7.   inverseMatrix(cmat);
  8.   cout << "Wyliczamy wartość M^-1:\n";
  9.   writeMatrix(cmat);
  10.   Matrix* wmat = multiplicationOfMatrixes(mat, cmat);
  11.   cout << "Wynik mnożenia M * M^-1:\n";
  12.   writeMatrix(wmat);
  13.   system("pause");
  14.   return 0;
  15. }