Gausselimination

Radoperationerna vi har tillgängliga är:

Radmultiplikation

När man multiplicerar en hel rad med samma tal. Om vi multiplicerar rad 2 med 4 i matrisen nedan får vi:

\begin{pmatrix} -1 & 0 & -2 \\ {\color{red}  1} & {\color{red}  2} & {\color{red}  8} \\ 4 & 0 & 2 \end{pmatrix} \to  \begin{pmatrix}-1 & 0 & -2 \\ 4 \cdot {\color{red}  1} & 4 \cdot {\color{red}  2} & 4 \cdot {\color{red}  8} \\ 4 & 0 & 2 \end{pmatrix} =  \begin{pmatrix} -1 & 0 & -2 \\ {\color{red}  4} & {\color{red}  8} & {\color{red}  32} \\ 4 & 0 & 2 \end{pmatrix}

Radbyte

När man byter plats på två rader. Om vi byter plats på rad två och tre i matrisen nedan får vi:

\begin{pmatrix} -1 & 0 & -2 \\ {\color{red}  1} & {\color{red}  2} & {\color{red}  8} \\ {\color{green}  4} & {\color{green}  0} & {\color{green}  2} \end{pmatrix} \to  \begin{pmatrix}-1 & 0 & -2 \\{\color{green}  4} & {\color{green}  0} & {\color{green}  2} \\  {\color{red}  1} & {\color{red}  2} & {\color{red}  8} \end{pmatrix}

Radaddition

Att addera en rad på en annan rad. Om vi adderar rad 1 till rad 2 i matrisen får vi: 

\begin{pmatrix} {\color{green}  -1} & {\color{green}  0} & {\color{green}  -2} \\ {\color{red}  1} & {\color{red}  2} & {\color{red}  8} \\ 4 & 0 & 2 \end{pmatrix} \to   \begin{pmatrix} {\color{green}  -1} & {\color{green}  0} & {\color{green}  -2} \\ {\color{red}  1} + {\color{green}  -1}  & {\color{red}  2} +  {\color{green}  0} & {\color{red}  8} +  {\color{green}  -2} \\ 4 & 0 & 2 \end{pmatrix} = \begin{pmatrix} {\color{green}  -1} & {\color{green}  0} & {\color{green}  -2} \\ {\color{red}  0} & {\color{red}  2} & {\color{red}  6} \\ 4 & 0 & 2 \end{pmatrix}

Låt oss se hur man använder de här radoperationerna i praktiken.

---

Räkneexempel och förklaringar för gausselimination:

Exempel: Lös ekvationssystemet

x + y = 10 , -x + y = 4

Svar: x = 3 , y = 7

Förklaring: För att kunna använda oss av gausselimination så måste vi först skriva om ekvationssystemet som en matris. Varje rad i matrisen blir då en ekvation, och elementen i varje rad är  koefficienterna framför varje variabel. Första ekvationen säger:

{\color{red} 1 \cdot }x + {\color{red} 1 \cdot } y = {\color{red} 10 }

Så matrisens första rad blir:

\begin{pmatrix}{\color{red} 1 } & {\color{red} 1 } & \bigm| &  {\color{red} 10 } \\ &  &\bigm| &  \end{pmatrix}

Där vi har satt ett vertikalt streck för att skilja ekvationens vänstra och högra sida. På samma sätt säger andra ekvationen:

{\color{red} -1 \cdot }x + {\color{red} 1 \cdot } y = {\color{red} 4}

Så matrisens andra rad blir:

\begin{pmatrix}1 & 1 & \bigm| & 10 \\ {\color{red} -1 } & {\color{red} 1 } & \bigm| &  {\color{red} 4 } \end{pmatrix}

Vi kan nu börja lösa ekvationen. Målet är att få matrisen till vänster om det vertikala strecket till formen nedan med hjälp av radoperationerna.

\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}

Det är målet för att om man i det läget översätter tillbaka till ekvationer så blir första raden x = (något tal) och andra raden blir y = (något tal).

Prio är då att få nollor på de ställen där 0 ska vara, eftersom vi sedan enkelt kan dividera de återstående elementen och på så sätt få 1or. Låt oss fokusera på elementet längst  nere till vänster, som vi vill sätta till 0. 

\begin{pmatrix}1 & 1 & \bigm| & 10 \\ {\color{red} -1 } & 1 & \bigm| & 4 \end{pmatrix}

Den allmänna strategin är att att addera en rad på den rad man vill ändra. Om vi använder radaddition för att addera rad 1 till rad 2 så ser vi att 1 i rad 1 kommer ta ut -1 i rad 2:

\begin{pmatrix}{\color{green} 1 } & {\color{green} 1 } & \bigm| &  {\color{green} 10 } \\{\color{red} -1 } & {\color{red} 1 } & \bigm| &  {\color{red} 4 } \end{pmatrix} \to  \begin{pmatrix} {\color{green} 1 } & {\color{green} 1 } & \bigm| &  {\color{green} 10 } \\{\color{red} -1 } + {\color{green} 1 } & {\color{red} 1 }+ {\color{green} 1 } & \bigm| &  {\color{red} 4 } + {\color{green} 10 } \end{pmatrix} =  \begin{pmatrix}{\color{green} 1 } & {\color{green} 1 } & \bigm| &  {\color{green} 10 } \\ {\color{red} 0 } & {\color{red} 2 } & \bigm| &  {\color{red} 14 } \end{pmatrix}

Bra! Nu vill vi att även elementet uppe till höger i vänsterledet ska sättas till 0. 

\begin{pmatrix}1 & {\color{red} 1 } & \bigm| & 10 \\ 0 & 2 & \bigm| & 14 \end{pmatrix}

Nu finns det ingen rad att addera till rad 1 så att det elementet blir 0. Det vi då först får göra är att använda radmultiplikation på rad 2 med något tal så att när vi lägger till den på rad 1 så får vi noll på det önskade elementet.

Elementet har värdet 1, så vi vill lägga till -1. Alltså vill vi ha -1 i samma kolonn i rad 2. För att uppnå detta använder vi radmultiplikation för att multiplicera rad 2 med -1/2:

\begin{pmatrix}1 & 1  & \bigm| & 10 \\ {\color{red} 0 } & {\color{red} 2 } & \bigm| &  {\color{red} 14 } \end{pmatrix} \to \begin{pmatrix}1 & 1  & \bigm| & 10 \\ -\frac{1}{2} \cdot {\color{red} 0 } & -\frac{1}{2} \cdot  {\color{red} 2 } & \bigm| &  -\frac{1}{2} \cdot {\color{red} 14 } \end{pmatrix} =  \begin{pmatrix} 1 & 1  & \bigm| & 10 \\ {\color{red} 0 } & {\color{red} -1 } & \bigm| &  {\color{red} -7} \end{pmatrix}

Nu kan vi addera rad 2 till rad 1 med radaddition!

\begin{pmatrix}{\color{green} 1 } & {\color{green} 1 } & \bigm| &  {\color{green} 10 } \\{\color{red} 0 } & {\color{red} -1 } & \bigm| &  {\color{red} -7 } \end{pmatrix} \to  \begin{pmatrix} {\color{green} 1 } + {\color{red} 0 } & {\color{green} 1 } + {\color{red} -1 }  & \bigm| &  {\color{green} 10 }  + {\color{red} -7 } \\ {\color{red} 0 } & {\color{red} -1 } & \bigm| &  {\color{red} -7 } \end{pmatrix} =  \begin{pmatrix}{\color{green} 1 } & {\color{green} 0 } & \bigm| &  {\color{green} 3} \\ {\color{red} 0 } & {\color{red} -1 } & \bigm| &  {\color{red} -7 } \end{pmatrix}

Fantastiskt! Nu har vi nästan uppnått formen vi vill ha på vänsterledet, vi saknar bara att -1 i nedre högra hörnet ska bli 1. Då kan vi radmultiplicera raden med -1:

\begin{pmatrix}1 & 0  & \bigm| & 3 \\ {\color{red} 0 } & {\color{red} -1 } & \bigm| &  {\color{red} -7 } \end{pmatrix} \to \begin{pmatrix}1 & 0  & \bigm| & 3 \\ -1 \cdot {\color{red} 0 } & -1 \cdot  {\color{red} -1 } & \bigm| &  -1 \cdot {\color{red} -7} \end{pmatrix} =  \begin{pmatrix} 1 & 0  & \bigm| & 3 \\ {\color{red} 0 } & {\color{red} 1 } & \bigm| &  {\color{red} 7} \end{pmatrix}

Nu har vi gjort färdigt gausseliminationen! Vi fick då resultatet:

\begin{pmatrix}1 & 0  & \bigm| & 3 \\ 0 & 1 & \bigm| & 7 \end{pmatrix}

Vi kan nu läsa av ekvationens lösningar. Första raden ger x och den andra ger y, så vi har att:

x = 3 och y = 7