Gausselimination

Gausselimination, uppkallad efter "matematikernas konung" Carl Friedrich Gauss (1777-1855), är en algoritm som används för att lösa linjära ekvationssystem, beräkna inversen av en matris eller beräkna rangen av en matris. Denna algoritm är effektiv, med detta menas att den är snabb och enkel att använda (i alla fall för datorer).

Innan vi går igenom hur vi använder oss av Gausselimination måste vi lära oss några elementära radoperationer.

Radbyten

Den första elementära radoperationen är radbyte. Radbyte innebär att vi byter rad \(i\) med rad \(j\). Vi kan till exempel byta rad 2 med rad 3 i matrisen nedan:

$$A=\begin{pmatrix}3 & 2 & -17\\ {\color{red} 7} & {\color{red} 8} & {\color{red} 4}\\{\color{blue} 6} & {\color{blue} 3} & {\color{blue} \pi}\end{pmatrix}\to \begin{pmatrix}3 & 2 & -17\\{\color{blue} 6} & {\color{blue} 3} & {\color{blue} \pi}\\ {\color{red} 7} & {\color{red} 8} & {\color{red} 4}\end{pmatrix}$$

Radmultiplikation

Den andra radoperationen är radmultiplikation. Som namnet antyder innebär radmultiplikation att vi multiplicerar en rad med en skalär. Det är viktigt att notera att talet vi multiplicerar med inte får vara lika med 0. Till exempel kan vi multiplicera rad tre med 1/2 i matrisen:

$$A'=\begin{pmatrix}3 & 2 & -17\\ 6 & 3 & \pi \\ {\color{red} 7} & {\color{red} 8} & {\color{red} 4}\end{pmatrix}\to \begin{pmatrix}3 & 2 & -17\\ 6 & 3 & \pi\\ \frac{{\color{red}7}}{{\color{red}2}} & {\color{red} 4} & {\color{red} 2}\end{pmatrix} $$

Radaddition

Radaddition fungerar genom att vi multiplicerar en rad i matrisen och sedan adderar den till en annan rad. Till exempel kan vi i nedanstående matris multiplicera rad 1 med 4 och addera den till rad 2:

$$\begin{align}B&=\begin{pmatrix}{\color{blue}1} & {\color{red}-}{\color{red}2}\\ -4 & 9\end{pmatrix}\to \begin{pmatrix}1 & -2\\ (-4)+{\color{green}4}\cdot{\color{blue}1} & 9+{\color{green}4}\cdot{\color{red}(}{\color{red}-}{\color{red}2}{\color{red})} \end{pmatrix}\\&\to\begin{pmatrix}1 & -2\\ 0 & 1\end{pmatrix}\end{align}$$

Vi är nu redo att lösa ett ekvationssystem med hjälp av Gausseliminering.

Gausselimination

Det första vi behöver göra är att se hur vi kan översätta ett linjärt ekvationssystem till matrisform. Det är enklast att illustrera detta med ett exempel.

$$\begin{align}\begin{cases} 2x-y+z&=11\\3x + 2y + 2z &=8\\4x+4y-4z&=-20\end{cases}\end{align}$$

Denna ekvation kan vi skriva på formen Ax=b där A är en \(3\times 3\)-matris och x och b är kolumnvektorer. Vi skriver om det på följande sätt:

$$\begin{pmatrix}2 & -1 & 1\\ 3 & 2 & 2\\ 4 & 4 & -4\end{pmatrix}\begin{pmatrix}x \\ y \\ z\end{pmatrix}=\begin{pmatrix}11 \\ 8 \\ -20\end{pmatrix}$$

Att denna form representerar ekvationssystemet ovan går att se genom att utföra matrismultiplikationen i vänsterledet.

För att underlätta brukar vi hoppa över att skriva kolumnvektorn x, och istället för ett likhetstecken skriver vi på följande sätt:

$$\left(\begin{array}{ccc|c}2 & -1 & 1 & 11\\ 3 & 2 & 2 & 8\\ 4 & 4 & -4 & -20\end{array}\right)$$

Idén med Gausselimination är att vi vill reducera matrisen A med hjälp av elementära radoperationer. Reduceringen ska leda till att det enbart är ettor i huvuddiagonalen och nollor under. När vi har åstadkommit det utför vi "bakåtsubstitution" för att lösa ut de obekanta variablerna.

I slutändan kommer vi alltså ha en enhetsmatris till vänster om det lodräta strecket, vilket innebär att ekvationssystemet är löst.

Vi börjar med sortera raderna. Sorteringen går till så att vi först letar efter pivotelementet i kolumn ett, det vill säga det element i den kolumnen med störst absolutbelopp. När vi har hittat det utför vi radbyte och lägger denna rad högst upp.

I exemplet ovan har rad tre pivotelementet, alltså byter vi plats på rad 1 och rad 3:

$$\left(\begin{array}{ccc|c}2 & -1 & 1 & 11\\ 3 & 2 & 2 & 8\\ 4 & 4 & -4 & -20\end{array}\right)\to\left(\begin{array}{ccc|c} 4 & 4 & -4 & -20\\3 & 2 & 2 & 8\\2 & -1 & 1 & 11\end{array}\right)$$

Nu ser vi till att rad 1 får en etta i första kolumnen med hjälp av radmultiplikation. I det här fallet multiplicerar vi med 1/4:

$$\left(\begin{array}{ccc|c} 4 & 4 & -4 & -20\\3 & 2 & 2 & 8\\2 & -1 & 1 & 11\end{array}\right)\to\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\3 & 2 & 2 & 8\\2 & -1 & 1 & 11\end{array}\right)$$

Nu ska vi med hjälp av radaddition reducera så att vi får nollor i kolumn 1, förutom på den första raden. I exemplet adderas rad 2 med \((-3)\cdot\)rad 1 och rad 3 med \((-2)\cdot\)rad 1:

$$\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\3 & 2 & 2 & 8\\2 & -1 & 1 & 11\end{array}\right)\to \left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & -1 & 5 & 23\\0 & -3 & 3 & 21\end{array}\right)$$

Nu leter vi efter pivotelementet i kolumn två (rad 1 är redan använd, så vi kollar bara på raderna under)

Även i det här fallet har rad 3 pivotelementet, så vi byter plats på rad 2 och rad 3:

$$\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & -1 & 5 & 23\\0 & -3 & 3 & 21\end{array}\right)\to\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & -3 & 3 & 21\\0 & -1 & 5 & 23 \end{array}\right)$$

Nu multiplicerar vi rad 2 med -1/3 för att få en etta i kolumn 2:

$$\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & -3 & 3 & 21\\0 & -1 & 5 & 23 \end{array}\right)\to\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & 1 & -1 & -7\\0 & -1 & 5 & 23 \end{array}\right)$$

För att göra kolumn 2 i rad 3 till en nolla adderar vi rad 3 med rad 2:

$$\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & 1 & -1 & -7\\0 & -1 & 5 & 23 \end{array}\right)\to\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & 1 & -1 & -7\\0 & 0 & 4 & 16 \end{array}\right)$$

Nu kan vi få en etta i sista raden genom att radmultiplikation med 1/4:

$$\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & 1 & -1 & -7\\0 & 0 & 4 & 16 \end{array}\right)\to\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & 1 & -1 & -7\\0 & 0 & 1 & 4 \end{array}\right)$$

Nu börjar vi med "bakåtsubstitueringen". Vi gör det genom att utföra radaddition så att vi får nollor i kolumn 3 ovanför rad 3. Alltså adderar vi rad 1 och rad 2 med rad 3:

$$\left(\begin{array}{ccc|c} 1 & 1 & -1 & -5\\0 & 1 & -1 & -7\\0 & 0 & 1 & 4 \end{array}\right)\to\left(\begin{array}{ccc|c} 1 & 1 & 0 & -1\\0 & 1 & 0 & -3\\0 & 0 & 1 & 4 \end{array}\right)$$

Nu använder vi rad 2 för att få en nolla i kolumn 2 på rad 1. Detta gör vi genom att addera \((-1)\cdot\)rad 2 med rad 1.

$$\left(\begin{array}{ccc|c} 1 & 1 & 0 & -1\\0 & 1 & 0 & -3\\0 & 0 & 1 & 4 \end{array}\right)\to \left(\begin{array}{ccc|c} 1 & 0 & 0 & 2\\0 & 1 & 0 & -3\\0 & 0 & 1 & 4 \end{array}\right)$$

Ekvationssystemet är nu löst! 

$$\begin{cases} x &= 2\\y&=-3\\z&=4\end{cases}$$

Som ni kanske märker tar Gausselimination ganska lång tid att utföra för hand och det krävs även mycket papper. För datorer går det här snabbt och vi kan även, med hjälp av Gausselimination, se om ett linjärt ekvationssystem har en entydig lösning, oändligt många lösningar eller inga lösningar. 

Dagens miniräknare och datorprogram använder den här algoritmen för att lösa linjära ekvationssystem.