Definicja 1: Układ równań liniowych
Układ równań postaci
\( \left\{ \begin{array}{c} a_{11}x_{1}+a_{12}x_{2}+\cdots+a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\cdots+a_{2n}x_{n}=b_{2}\\\vdots\\a_{m1}x_{1}+a_{m2}x_{2}+\cdots+a_{mn}x_{n}=b_{m}\end{array}\right. \)
nazywamy układem \( m \) równań liniowych o \( n \) niewiadomych \( x_{1},\ldots,x_{n} \). Liczby rzeczywiste (lub zespolone) \( a_{ij} \) oraz \( b_{i} \) nazywamy współczynnikami układu.
Definicja 2: Układ równań jednorodny
Układ równań liniowych
( 1 ), dla którego \( b_{i}=0 \), dla \( i=1,\ldots,m \), nazywamy
układem jednorodnym.
Układ równań, który nie jest układem jednorodnym nazywamy układem niejednorodnym.
Zapis macierzowy układu równań liniowych
Z układem równań liniowych ( 1 ) można powiązać macierz wymiaru \( m\times n \)
\( A=\left( \begin{array}{llll}a_{11} & a_{12} & \ldots & a_{1n}\\a_{21} & a_{22} & \ldots & a_{2n}\\\ldots & \ldots & \ldots & \ldots\\a_{m1} & a_{m2} & \ldots & a_{mn} \end{array} \right), \)
nazywaną macierzą współczynników układu równań ( 1 ), oraz dwie macierze kolumnowe (które, dla ułatwienia, nazywać będziemy wektorami):
\( x=\left( \begin{array}{c} x_{1}\\ x_{2}\\ \vdots\\ x_{n} \end{array} \right), \hspace{2em} b=\left( \begin{array}{c} b_{1}\\ b_{2}\\ \vdots\\ b_{m} \end{array} \right); \)
wektor \( x \) nazywany wektorem niewiadomych, wektor \( b \) to tzw. wektor prawej strony.
Przy przyjętych oznaczeniach, układ równań ( 1 ) możemy zapisać w postaci macierzowej:
Twierdzenie Cramera
W przypadku, gdy liczba równań układu ( 1 ) jest równa liczbie niewiadomych, macierz układu jest macierzą kwadratową. Jeżeli dodatkowo jest to macierz nieosobliwa (czyli kwadratowa o wyznaczniku różnym od zera), wówczas układ równań ( 1 ) nazywamy układem Cramera. Rozwiązanie równania macierzowego ( 2 ) - a więc i układu ( 1 ) - można wówczas wyznaczyć wykorzystując odwrotność macierzy układu.
Jeżeli macierz \( A \) jest kwadratowa i nieosobliwa, to równanie \( Ax=b \) posiada dokładnie jedno rozwiązanie; rozwiązaniem tym jest \( x=A^{-1}b \).
Uwaga 1:
Rozwiązanie zerowe \( \left( x_{1},\ldots,x_{n}\right) =\left(0,\ldots,0\right) \) jest rozwiązaniem każdego układu jednorodnego. Jeżeli jednorodny układ równań liniowych jest układem Cramera, to rozwiązanie zerowe \( \left(0,\ldots,0\right) \) jest jego jedynym rozwiązaniem.
Dla układu równań
\( \left\{\begin{array}{l}x+y-z=1\\2x+y-2z=0\\x-y+2z=2\end{array}\right. \)
mamy
\( A=\left(\begin{array}{ccc}1 & 1 & -1\\2 & 1 & -2\\1 & -1 & 2\end{array}\right) \hspace{1em} \text{oraz } \hspace{1em}b=\left(\begin{array}{c}1\\0\\2\end{array}\right) \)
. Ponieważ \( \det A=-3 \), zatem rozważany układ równań jest układem Cramera. Łatwo sprawdzić, że
\( A^{-1}=\frac{1}{3}\left( \begin{array}{ccc}0 & 1 & 1\\ 6 & -3 & 0\\ 3 & -2 & 1 \end{array}\right) ; \)
stąd, na podstawie twierdzenia Rozwiązanie układu Cramera, otrzymujemy
\( \left( \begin{array}{c} x\\ y\\ z \end{array} \right) =\frac{1}{3}\left( \begin{array}{ccc} 0 & 1 & 1\\ 6 & -3 & 0\\ 3 & -2 & 1 \end{array} \right) \left( \begin{array}{c} 1\\ 0\\ 2 \end{array} \right) =\left( \begin{array}{c} \frac{2}{3}\\ 2\\ \frac{5}{3} \end{array} \right) . \)
Oznacza to, że rozwiązaniem układu równań jest \( x=\frac{2}{3} \), \( y=2 \), \( z=\frac{5}{3} \).
Metoda rozwiązywania układu równań liniowych oparta na twierdzeniu Rozwiązanie układu Cramera i zilustrowana w przykładzie Rozwiązywanie układu równań liniowych metodą macierzy odwrotnej wymaga znajomości (lub wyznaczenia) macierzy odwrotnej układu. To praktycznie dyskwalifikuje tę metodę, gdyż w przypadku ogólnym nie istnieje algorytm dobrze radzący sobie z zadaniem odwracania macierzy. Stąd potrzeba metody rozwiązywania układów równań liniowych nie wymagającej znajomości macierzy odwrotnej. Jedna z takich metod oparta jest na tzw. wzorach Cramera.
Jeżeli macierz \( A \) układu równań
( 1 ) jest kwadratowa i nieosobliwa, to jedyne rozwiązanie \( \left( x_{1},\ldots,x_{n}\right) \) tego układu wyraża się wzorem:
\( x_{i}=\frac{\det A_{i}}{\det A} \hspace{3em} \left( i=1,\ldots,n\right), \)
w którym macierz \( A_{i} \) oznacza macierz powstałą z macierzy \( A \) przez zastąpienie jej \( i \)-tej kolumny wektorem \( b \).
Dla układu równań rozważanego w przykładzie
Rozwiązywanie układu równań liniowych metodą macierzy odwrotnej mamy
\( A_{1}=\left(\begin{array}{ccc}1 & 1 & -1\\0 & 1 & -2\\2 & -1 & 2\end{array}\right) ,\hspace{1em}A_{2}=\left(\begin{array}{ccc}1 & 1 & -1\\2 & 0 & -2\\1 & 2 & 2\end{array}\right) ,\hspace{1em} A_{3}=\left(\begin{array}{ccc}1 & 1 & 1\\2 & 1 & 0\\1 & -1 & 2\end{array}\right) \)
Na podstawie wzorów Cramera otrzymujemy:
\( x=\frac{\left\vert \begin{array}{ccc} 1 & 1 & -1\\ 0 & 1 & -2\\ 2 & -1 & 2 \end{array}\right\vert}{-3}=\frac{2}{3}, \hspace{1em} y=\frac{\left\vert \begin{array}{ccc}1 & 1 & -1\\ 2 & 0 & -2\\ 1 & 2 & 2 \end{array} \right\vert }{-3}=2, \hspace{1em} z=\frac{\left\vert \begin{array}{ccc} 1 & 1 & 1\\ 2 & 1 & 0\\ 1 & -1 & 2 \end{array} \right\vert }{-3}=\frac{5}{3}\text{.} \)
Przedstawiona w przykładzie Wzory Cramera metoda rozwiązywania układu równań liniowych oparta na wzorach Cramera nie wykorzystuje macierzy odwrotnej układu. W przypadku układów \( n \) równań liniowych o \( n \) niewiadomych wymaga ona obliczenia \( n+1 \) wyznaczników macierzy stopnia \( n \). Wybranie niewłaściwej metody obliczania tych wyznaczników (np. w oparciu o rozwinięcie Laplace'a) spowoduje, że ze względu na olbrzymią liczbę operacji niezbędnych do przeprowadzenia w celu uzyskania wyniku, i ta metoda okaże się być bezużyteczna.
Twierdzenie Kroneckera-Capelliego
Rozważmy układ równań liniowych postaci ( 1 ). Niech \( U \) będzie macierzą o wymiarze \( m\times\left( n+1\right) \) powstałą z macierzy \( A \) wymiaru \( m\times n \) układu ( 1 ) przez dołączenie do macierzy \( A \) dodatkowej kolumny - wektora prawej strony \( b \), tj.
\( U=\left( \begin{array}{ll} \left. \begin{array}{llll} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \ldots & \ldots & \ldots & \ldots\\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{array} \right\vert & \begin{array}{c} b_{1}\\ b_{2}\\ \ldots\\ b_{m} \end{array} \end{array}\right). \)
Tak utworzoną macierz \( U \) nazywamy macierzą uzupełnioną układu ( 1 ).
Twierdzenie 3: Kroneckera-Capelliego
Układ równań
( 1 ) posiada rozwiązanie wtedy i tylko wtedy, gdy rzędy macierzy \( A \) oraz \( U \) są równe, tj. \( \operatorname*{rz}A=\operatorname*{rz}U \). Ponadto:
- jeżeli \( \operatorname*{rz}A=\operatorname*{rz}U=n \) ( \( n \) - liczba niewiadomych), to rozwiązanie to jest jedyne;
- jeżeli \( \operatorname*{rz}A=\operatorname*{rz}U=r \lt n \), to rozwiązań jest nieskończenie wiele i zależą one od \( n-r \) parametrów.
Z twierdzenia Kroneckera-Capelliego wynika, że dla każdego układu równań liniowych zachodzi jedna z trzech możliwości:
- nie posiada rozwiązań, układ taki nazywamy układem sprzecznym;
- posiada jedno rozwiązanie, układ taki nazywamy układem oznaczonym ;
- posiada nieskończenie wiele rozwiązań, układ taki nazywamy układem nieoznaczonym.
Przykład 3: Układ sprzeczny
Rozważmy układ równań:
\( \left\{\begin{array}{l}x+y+z+w=1\\2x-y+2z-w=-1\\x-2y+z-2w=2\end{array}\right. \hspace{1em}. \)
Liczba niewiadomych to \( n=4 \); macierz uzupełniona ma postać
\( U=\left( A|b\right) =\left(\begin{array}{lc}\left.\begin{array}{cccc}1 & 1 & 1 & 1\\2 & -1 & 2 & -1\\1 & -2 & 1 & -2\end{array}\right\vert &\begin{array}{c}1\\-1\\2\end{array}\end{array}\right) \)
Ponieważ wszystkie minory stopnia trzeciego macierzy \( A \) są zerowe:
\( \left\vert\begin{array}{ccc}1 & 1 & 1\\2 & -1 & 2\\1 & -2 & 1\end{array}\right\vert =\left\vert\begin{array}{ccc}1 & 1 & 1\\2 & -1 & -1\\1 & -2 & -2\end{array}\right\vert =\left\vert\begin{array}{ccc}1 & 1 & 1\\2 & 2 & -1\\1 & 1 & -2\end{array}\right\vert =\left\vert\begin{array}{ccc}1 & 1 & 1\\-1 & 2 & -1\\-2 & 1 & -2\end{array}\right\vert =0 \)
oraz
\( \left\vert\begin{array}{cc}1 & 1\\2 & -1\end{array}\right\vert =-3\neq0, \)
zatem \( \operatorname*{rz}A=2. \) Ponadto, ponieważ
\( \left\vert\begin{array}{ccc}1 & 1 & 1\\2 & -1 & -1\\1 & -2 & 2\end{array}\right\vert =-12\neq0, \)
to \( \operatorname*{rz}U=3. \) Oznacza to, na podstawie twierdzenia Kroneckera - Capelliego, że rozważany układ równań jest sprzeczny (gdyż \( \operatorname*{rz}A\neq\operatorname*{rz}U \)).
Przykład 4: Rozwiązywanie układu oznaczonego
Rozważmy układ czterech równań liniowych z trzema niewiadomymi
\( \left\{\begin{array}{l}x-y+z=1\\-2x-y-z=1\\2x-y=2\\-x-y-2z=2\end{array}\right. \hspace{1em}. \)
Liczba kolumn macierzy układu (równa liczbie niewiadomych) wynosi \( n=3 \); macierz uzupełniona ma postać
\( U=\left(\begin{array}{lr}\left.\begin{array}{ccc}1 & -1 & 1\\-2 & -1 & -1\\2 & -1 & 0\\-1 & -1 & -2\end{array}\right\vert &\begin{array}{c}1\\1\\2\\2\end{array}\end{array}\right). \)
Jak łatwo sprawdzić \( \det U=0 \), zatem \( \operatorname*{rz} U \leq 3 \), gdyż macierz \( U \) nie zawiera żadnej nieosobliwej podmacierzy wymiaru \( 4\times 4 \). Ponieważ w macierzy \( A \) istnieje nieosobliwa podmacierz wymiaru \( 3\times3 \):
\( \left\vert\begin{array}{ccc}1 & -1 & 1\\-2 & -1 & -1\\2 & -1 & 0\end{array}\right\vert =5, \)
zatem \( \operatorname*{rz}A=\operatorname*{rz}U=3 \). Z twierdzenia Kroneckera-Capelliego wynika więc, że rozważany układ równań jest układem oznaczonym. Aby znaleźć jego rozwiązanie wystarczy rozwiązać równoważny wyjściowemu układ Cramera, powstały z wyjściowego układu przez odrzucenie czwartego równania (równanie to odpowiada temu wierszowi macierzy \( A \), który nie występuje w nieosobliwej podmacierzy
( 4 ) decydującej o równości rzędów macierzy \( A \) oraz \( U \)):
\( \left\{\begin{array}{l}x-y+z=1\\-2x-y-z=1\\2x-y=2\end{array}\right. \hspace{1em} \text{.} \)
Na podstawie wzorów Cramera otrzymujemy
\( x=\frac{\left\vert\begin{array}{ccc}1 & -1 & 1\\1 & -1 & -1\\2 & -1 & 0\end{array}\right\vert }{5}=\frac{2}{5}, \hspace{1em} y=\frac{\left\vert\begin{array}{ccc}1 & 1 & 1\\-2 & 1 & -1\\2 & 2 & 0\end{array}\right\vert }{5}=-\frac{6}{5},\hspace{1em} z=\frac{\left\vert\begin{array}{ccc}1 & -1 & 1\\-2 & -1 & 1\\2 & -1 & 2\end{array}\right\vert }{5}=-\frac{3}{5}. \)
Przykład 5: Rozwiązywanie układu nieoznaczonego
Rozważmy układ równań:
\( \left\{\begin{array}{l}x+y+z=1\\2x-y+2z=-1\\x-2y+z=-2\end{array}\right. \hspace{1em} \)
Liczba niewiadomych to \( n=3 \), macierz uzupełniona ma postać
\( U=\left( A|b\right) =\left(\begin{array}{lc}\left.\begin{array}{ccc}1 & 1 & 1\\2 & -1 & 2\\1 & -2 & 1\end{array}\right\vert &\begin{array}{c}1\\-1\\-2\end{array}\end{array}\right). \)
Druga i czwarta kolumna macierzy \( U \) są identyczne, zatem \( \operatorname*{rz}A=\operatorname*{rz}U \). Z postaci macierzy \( A \) wynika z kolei, że \( \operatorname*{rz}A\leq2 \) (pierwsza i trzecia kolumna macierzy A są identyczne, więc \( \det(A)=0 \)).
Ponieważ jednak macierz \( A \) zawiera nieosobliwą podmacierz wymiaru \( 2\times 2 \):
\( \left\vert\begin{array}{cc}1 & 1\\2 & -1\end{array}\right\vert =-3\neq0, \)
zatem \( \operatorname*{rz}A=\operatorname*{rz}U=2 \). Z twierdzenia Kroneckera-Capelliego wynika więc, że rozważany układ równań posiada nieskończenie wiele rozwiązań zależnych od \( n-\operatorname*{rz}A=3-2=1 \) parametru. Wyznaczymy te rozwiązania. Skoro \( \operatorname*{rz}A=2 \) to, na podstawie definicji rzędu macierzy, macierz \( A \) zawiera nieosobliwą podmacierz wymiaru \( 2\times2 \); odnajdujemy tę macierz w rozwiązywanym układzie równań. Równania, których współczynniki nie wchodzą w skład tej macierzy odrzucamy, z kolei niewiadome, których wybrana podmacierz nie obejmuje, przerzucamy na drugą stronę równania i traktujemy jako parametry. Układ równań, jaki w ten sposób otrzymujemy, jest układem Cramera (sposób wyboru macierzy tego układu gwarantuje, że jej wyznacznik jest różny od zera) - do jego rozwiązania stosujemy wzory
( 3 ). W naszym przypadku, jako nieosobliwą podmacierz wymiaru \( 2\times2 \) zawartą w macierzy \( A \) możemy wybrać macierz
\( \left(\begin{array}{cc}1 & 1\\2 & -1\end{array}\right). \)
Oznacza to, że układy równań
\( \left\{\begin{array}{l}x+y+z=1\\2x-y+2z=-1\\x-2y+z=-2\end{array}\right.\hspace{1em} \text{oraz } \hspace{1em} \left\{\begin{array}{l}x+y+z=1\\2x-y+2z=-1\end{array}\right. \)
są równoważne. Traktując niewiadomą \( z \) jako parametr, otrzymujemy do rozwiązania układ Cramera
\( \left\{\begin{array}{l}x+y=1-z\\2x-y=-1-2z\end{array}\right. \hspace{1em} . \)
Zastosowanie do tego ostatniego układu wzorów
( 3 ) prowadzi do rozwiązania:
\( x=\frac{\left\vert\begin{array}{cc}1-z & 1\\-1-2z & -1\end{array}\right\vert }{-3}=-z, \hspace{1em} y=\frac{\left\vert\begin{array}{cc}1 & 1-z\\2 & -1-2z\end{array}\right\vert }{-3}=1, \hspace{1em} z\in\mathbb{R}, \)
które można również zapisać jako
\( \left\{\begin{array}{l}x=-t\\y=1\\z=t\end{array}\right., \hspace{0.5em}\text{gdzie } t\in\mathbb{R}. \)