Macierze w C++ cz. 2

Wstęp

Artykuł przeprowadzi punkt po punkcie jak wprowadzoną przez użytkownika macierz sprowadzić to postaci schodkowej, a potem do postaci schodkowej zredukowanej. Jest to kontynuacja części 1 na podstawie której opracowałem bibliotekę matrix.h z której będę korzystać podczas testowania kodu.

Implementacja

Operacja elementarna 1

Pierwsza operacja na wierszach macierzy, którą zadeklarujemy to będzie zamiana wierszy. Zgodnie z przekazywaną strukturą macierz jest przechowywana w tablicy wskaźników, która wskazuje na początki tablic liczb rzeczywistych. Innymi słowy nie musimy przepisywać całych wierszy. Wystarczy, ze zmienimy pod jaki adres ma przejść aplikacja w poszukiwaniu wiersza. Pozwoli to zaoszczędzić czas i pamięć.

1. void elementalType1(Matrix* mat, int row_1, int row_2){
2.   double* lista = mat->data[row_1];
3.   mat->data[row_1] = mat->data[row_2];
4.   mat->data[row_2] = lista;
5. }

Rozwiązanie to dostosowanie funkcji swap() do kopiowania odpowiedniej części struktury.

Operacja elementarna 2

Druga operacja polega na dodaniu do i-tego wiersza j-oty wiersz pomnożony przez jakąś stałą C.

1. void elementalType2(Matrix* mat, int row_1, double c, int row_2){
2.   for(int j = 0; j < mat->m; j++)
3.       mat->data[row_1][j] += c * mat->data[row_2][j];
4. }

Dla podanego wiersza row_1 do j-tej liczby dodajemy j-otą wartość z wiersza row_2 pomnożoną przez daną stałą c.

Operacja elementarna 3

Ostatnia i chyba najprostsza operacja polega na pomnożeniu danego wiersza przez stałą C.

1. void elementalType3(Matrix* mat, int row_1, double c){
2.   for(int j = 0; j < mat->m; j++)
3.       mat->data[row_1][j] = c * mat->data[row_1][j];
4. }

Jak przy operacji elementarnej 2 musimy przejść przez każdą liczbę z podanego wiersza z tą różnicą, że nie dodajemy, a przypisujemy odpowiednią wartość.

Postać schodkowa

Postać schodkowa to postać w której w każdym wierszu pierwszy element niezerowy jest jedynką, a wszystkie wyrazu w kolumnie pod jedynką są zerami.

Na początek zadeklarujemy dwie zmienne (2.) row i (3.) col, które będą pamiętały gdzie obecnie jesteśmy w macierzy:

1. void rowEchelonForm(Matrix* mat){
2.   int row = 0;
3.   int col = 0;

Wszystkie obliczenia będziemy wykonywać w (4.) pętli while, która będzie wykonywane dopóki dana pozycja istnieje w macierzy. Na potrzeby funkcji przyjmujemy, że w macierzy pierwszy wiersz ma indeks 0. To samo tyczy się kolumny.

4.   while(row < mat->n && col < mat->m){
5.     int j = 0;
6.     while(j + row < mat->n && mat->data[j + row][col] == 0)
7.       j++;
8.     if(j + row == mat->n){
9.       col++;

(5.) Zmienna j posłużymy nam do chodzenia po wierszach macierzy. (7.) Kolejną pętla while ma za zadanie znaleźć w kolumnie o indeksie col pierwszy wiersz począwszy od row, którego wyraz na pozycji i+row, col nie będzie zerem. (9.) Jeśli po zakończeniu pętli wskazany wiersz w macierzy nie istnieje to oznacza to, że (10.) musimy przejrzeć następną kolumnę, ponieważ w tej wszystkie wartości w kolumnie col we wszystkich wierszach począwszy od row są zerowe.

11.     } else {
12.       if(j != 0)
13.         elementalType1(mat, row, j+row);
14.       if(mat->data[row][col] != 1)
15.         elementalType3(mat, row, 1/mat->data[row][col]);

Jeśli jednak istnieje wiersz, którym będziemy mogli zerować wszystkie poniżej to (13.) przestawiamy go na pozycję row (12.) pod warunkiem, że nie istnieje taka potrzeba, ponieważ wiersz jest już na odpowiedniej pozycji. W myśl założenia pierwszym elementem wiersza ma być jeden. Z tego powodu (14.) jeśli nie jest to (15.) dany wiersz mnożymy przez 1 dzielone przez wartość wiersza w kolumnie j. Nie musimy sprawdzać czy nie dzielimy przez zero, ponieważ do tej części kodu przechodzimy tylko, gdy na pozycji row, col nie ma zera.

16.       for(j = 1; j + row < mat->n; j++)
17.         if(mat->data[j + row][col] != 0)
18.           elementalType2(mat, j + row, -mat->data[j + row][col], row);
19.       row++;
20.       col++;
21.     }
22.   }
23. }

(16. - 18.) Kolejny etap polega na wyzerowaniu wszystkich wierszy poniżej wiersza row. Oczywiście należy upewnić się, że dany wiersz w kolumnie col nie ma zera co by oznaczało niepotrzebną operację, ponieważ nie uzyskalibyśmy wtedy postaci schodkowej (w przypadku tego algorytmu). Po zakończeniu zerowania wystarczy zwiększyć wartości col i row. Można to przetłumaczy jako: wiersze od 1 do row i kolumny od 1 do col mają już odpowiednią postać. Przeprowadź proces redukcji w macierzy m-1 x n-1.

Postać schodkowa zredukowana

Implementacja tej części kodu jest bardzo podobna do funkcji sprowadzającej do postaci schodkowej:

1. void reducedRowEchelonForm(Matrix* mat){
2.   int row = 0;
3.   int col = 0;
4.   while(row < mat->n && col < mat->m){
5.     int j = 0;
6.     while(j + row < mat->n && mat->data[j + row][col] == 0)
7.       j++;
8.     if(j + row == mat->n){
9.       col++;
10.     } else {
11.       if(j != 0)
12.         elementalType1(mat, row, j+row);
13.       if(mat->data[row][col] != 1)
14.         elementalType3(mat, row, 1/mat->data[row][col]);
16.       for(j = 0; j < mat->n; j++)
17.         if(j != row && mat->data[j][col] != 0)
18.           elementalType2(mat, j, -mat->data[j][col], row);
19.       row++;
20.       col++;
21.     }
22.   }
23. }

Zmiany zachodzą w linijkach 15. - 17., gdzie zerowanie wykonujemy dla wszystkich wierszy prócz wiersza którym zerujemy.

Testowanie funkcji

Poniższe testy testują zaimplementowane funkcje. Niezbędne jest dodanie biblioteki matrix.h. Test polega na wczytywaniu od użytkownika macierzy, a następnie wykonania na niej różnych operacji elementarnych, a na sam koniec zamianę do zredukowanej postaci schodkowej.

1. char* writeBool(bool a){
2.   return (a ? "TAK" : "NIE");
3. }
5. int main () {
6.   setlocale(LC_ALL,"");
8.   Matrix* mat = readMatrix();
9.   cout << "Użytkownik wprowadził macierz: \n";
10.   writeMatrix(mat);
12.   cout << "Czy jest macierzą diagonalną? " << writeBool(isDiag(mat));
13.   cout << endl;
15.   elementalType1(mat, 0, mat->m - 1);
16.   cout << "Zamieniamy pierwszy wiersz z ostatnim:\n";
17.   writeMatrix(mat);
19.   elementalType2(mat, 0, -1, mat->m - 1);
20.   cout << "Od pierwszego wiersza odejmiemy ostatni:\n";
21.   writeMatrix(mat);
23.   elementalType3(mat, 0, 5);
24.   cout << "Pomnożymy pierwszy wiersz przez 5:\n";
25.   writeMatrix(mat);
27.   reducedRowEchelonForm(mat);
28.   cout << "Sprowadzamy do postaci schodkowej:\n";
29.   writeMatrix(mat);
31.   system("pause");
32.   return 0;
33. }

• Kod źródłowy Implementacja