Eliminacja Gaussa

Na pewnym etapie nauki matematyki na studiach natrafisz na układy równań, które posiadają na przykład cztery równania i cztery niewiadome ($x, y, z, t$). Rozwiązywanie ich tradycyjną, znaną ze szkoły podstawowej metodą podstawiania pochłonęłoby nieproporcjonalnie dużo czasu i prowadziłoby do błędów obliczeniowych. W tym momencie z pomocą przychodzi jedno z najpotężniejszych narzędzi algebry liniowej: Eliminacja Gaussa (potocznie nazywana schodkowaniem macierzy).

Metoda ta polega na przetworzeniu wyjściowego układu równań na specjalną macierz, a następnie na przekształcaniu jej tak, by w lewym dolnym rogu (pod główną przekątną) wygenerować same zera.

1. Operacje elementarne na wierszach

Aby wyzerować wybrane komórki, możemy przekształcać macierz traktując każdy jej wiersz dokładnie tak, jak pojedyncze, niezależne równanie matematyczne. Z tego powodu dozwolone są wyłącznie trzy specyficzne operacje, zwane operacjami elementarnymi:

1. Zamiana wierszy miejscami: Dokładnie tak samo, jak w układzie równań, fizyczna kolejność wierszy z równaniami nie wpływa na ostateczne rozwiązanie i możemy je swobodnie zamieniać.
2. Mnożenie wiersza przez skalar: Cały wybrany wiersz możemy pomnożyć przez dowolną liczbę różną od zera (np. przemnożyć wiersz przez 3, aby celowo pozbyć się ułamków z komórek).
3. Dodanie wiersza do innego wiersza: To zdecydowanie najważniejsza operacja w tej metodzie. Dowolny wiersz możemy bez żadnych obaw dodać (lub odjąć) wprost do drugiego wiersza. Możemy też przed dodaniem go do innego wiersza swobodnie pomnożyć go w pamięci przez dowolną liczbę. Właśnie dzięki temu mechanizmowi doprowadzamy do zerowania konkretnych komórek!

2. Proces schodkowania

Naszym nadrzędnym celem jest przekształcenie macierzy do postaci, w której pod przekątną zostają same zera. Rozważmy klasyczny układ dwóch równań liniowych: $x + y = 3$ $2x + 4y = 8$

Krok 1: Wpisanie układu w macierz. Równania układamy jedno pod drugim i wyciągamy z nich wyłącznie same liczby (współczynniki liczbowe). Ostatnią kolumnę, prezentującą prawe strony równań (wyniki), odgradzamy wewnątrz macierzy pionową kreską dla zwiększenia czytelności. $$ \begin{bmatrix} 1 & 1 & \big| & 3 \ 2 & 4 & \big| & 8 \end{bmatrix} $$

Krok 2: Generowanie zera pod pierwszą pozycją. Patrzymy w lewy górny róg macierzy – znajduje się tam bardzo dla nas wygodna cyfra $1$ (nazywamy ją elementem wiodącym). Poniżej niej leży cyfra $2$, którą celowo chcemy zlikwidować i zamienić w zero. Bierzemy zatem cały pierwszy wiersz, mnożymy go matematycznie w głowie przez $-2$ i dodajemy pozycjami w dół do wiersza drugiego. Zmodyfikowany zostanie w tej sytuacji tylko i wyłącznie wiersz drugi! (Pierwszy wiersz zostaje u góry po staremu, służył on tylko do operacji na drugim wierszu).

Wyliczamy wartości drugiego wiersza z pamięci. Pierwszy wiersz w pamięci to teraz $(-2, -2, -6)$. Dodajemy to po kolei na dół do komórek z drugiego wiersza $(2, 4, 8)$: Pierwsza kolumna: $2 + (-2) = 0$ Druga kolumna: $4 + (-2) = 2$ Trzecia kolumna z prawą stroną: $8 + (-6) = 2$

Nasza nowa, przekształcona macierz schodkowa prezentuje się następująco: $$ \begin{bmatrix} 1 & 1 & \big| & 3 \ 0 & 2 & \big| & 2 \end{bmatrix} $$

Krok 3: Odczytanie uzyskanego wyniku od dołu. Doprowadziliśmy macierz do poprawnej postaci schodkowej (poniżej głównej przekątnej znajdują się same zera). Teraz odbudowujemy fizycznie układ równań zaczynając od najniższego szczebla (od dołu macierzy). Drugi wiersz informuje nas teraz, że: $0x + 2y = 2$. Z czego momentalnie wyprowadzamy rozwiązanie $y = 1$.

Posiadając już gotowego igreka, przeskakujemy wiersz wyżej do góry (czyli w naszej macierzy do pierwszego wiersza) i podstawiamy go w odpowiednie miejsce: $1x + 1 \cdot (1) = 3$. Po przeniesieniu: $x = 3 - 1$, więc $x = 2$.

Udało się rozwiązać układ równań całkowicie eliminując etap mozolnych podstawień na wczesnym etapie! Ta sama zasada obowiązuje przy układach zbudowanych z dziesięciu równań, idziemy sukcesywnie rzędem w dół, niszcząc kolejne numery.

[!TIP] Jeśli na samym początku pierwsza komórka z lewego górnego rogu nie posiada pożądanej wartości równej jeden, najlepiej całkowicie zamienić cały ten wiersz miejscami z jakimś innym rzędem, który już jedynkę z lewej strony posiada, lub ewentualnie podzielić cały problematyczny wiersz na siłę przez jego główną wartość, tak aby ta jedynka powstała na krawędzi sztucznie. Używanie "jedynki" do niszczenia i wyzerowywania wierszy pod spodem to najbardziej efektywna metoda!

Dla dociekliwych: Skąd to się wzięło?

Na pierwszy rzut oka, macierz wygląda jak proste tabelki Excela, a operacje na nich (np. dodawanie całych wierszy do siebie w pamięci) przypominają sztuczki optyczne. Skąd mamy pewność matematyczną, że tak agresywne modyfikacje w tabelce nie "popsują" ostatecznych wyników układu równań, od którego zaczynaliśmy?

Odpowiedź staje się jasna, kiedy uświadomimy sobie jeden, żelazny fakt – wszystkie macierze reprezentujące równania to w rzeczywistości absolutnie nic innego, jak skondensowany zapis algebraiczny pozbawiony literek i znaków dodawania, stworzony po to by zmniejszyć zmęczenie dłoni matematyka od pisania iksów i igreków po papierze!

Rozważmy operację dodawania pierwszego wiersza do drugiego. Gdybyśmy mieli na kartce standardowe dwa równania: (1) $x + y = 3$ (2) $x - y = 1$ W szkole średniej często stosowano tzw. "metodę przeciwnych współczynników". Nauczyciel nakazywał narysować pod kreską długą poziomą linię i po prostu fizycznie dodać pionowo lewe strony równań oraz ich strony prawe. W powyższym przypadku: $(x + x) + (y - y) = 3 + 1$, z czego automatycznie redukuje nam się $2x = 4$.

Metoda dodawania wierszy wewnątrz eliminacji Gaussa (macierzy) to po prostu ta sama szkolna zasada matematyczna działająca na algebraicznych układach równań obustronnych! Kiedy dodajesz wiersz jeden (w głowie pomnożony przez cokolwiek) do drugiego, w rzeczywistości algebraicznie dodajesz po prostu równe i wyważone wartości lewych stron szali do prawych stron szali w sposób, który nie narusza kruchego balansu żadnego z równań. Macierze sprawiają, że cały ten proces wygląda jak proste dodawanie liczb w kolumnach na tabelce.

Przykładowe zadania