Stelsels lineaire vergelijkingen

Inhoud

4. Stelsels lineaire vergelijkingen#

We hebben gezien dat een \(m\times n\)-matrix \(A\) een vector \(\vx\in\RR^n\) naar een vector \(A\vx\in\RR^m\) stuurt. In de praktijk blijken we heel vaak het volgende ‘omkeerprobleem’ tegen te komen: gegeven een \(m\times n\)-matrix \(A\) en een vector \(\vb\in\RR^m\), bepaal alle (nul, één of meer) vectoren \(\vx\in\RR^n\) die voldoen aan

(4.1)#\[ A\vx=\vb. \]

Dit type vergelijking heet een matrix-vectorvergelijking. We noemen de matrix \(A\) ook wel de coëfficiëntenmatrix en de vector \(b\) de constantenvector.

Nemen we voor de coëfficiënten van \(\vx\) nu onbekenden \(x_1,\ldots,x_n\), dan kunnen we de matrix-vectorvergelijking \(A\vx=\vb\) schrijven als \(m\) vergelijkingen in deze \(n\) onbekenden:

(4.2)#\[\begin{split} \left\{ \begin{aligned} a_{1,1}x_1 + a_{1,2}x_2 + \cdots + a_{1,n}x_n &= b_1\\ a_{2,1}x_1 + a_{2,2}x_2 + \cdots + a_{2,n}x_n &= b_2\\ &\enspace\vdots\\ a_{m,1}x_1 + a_{m,2}x_2 + \cdots + a_{m,n}x_n &= b_m \end{aligned} \right. \end{split}\]

Dit is een stelsel van \(m\) lineaire vergelijkingen, d.w.z. er komen geen hogere machten of producten van de \(x_i\) in voor.

Definitie 4.1 (Oplossingsverzameling)

Gegeven een \(m\times n\)-matrix \(A\) en een vector \(\vb\in\RR^m\) is de oplossingsverzameling van de vergelijking \(A\vx=\vb\) (of van het corresponderende stelsel lineaire vergelijkingen) de verzameling van alle vectoren \(\vx\in\RR^n\) met \(A\vx=\vb\). In verzamelingsnotatie:

\[ \{x\in\RR^n\mid A\vx=\vb\}. \]

We gaan ons nu richten op de vraag hoe we voor een gegeven matrix \(A\) en een gegeven vector \(\vb\) deze oplossingsverzameling kunnen bepalen.

Voorbeeld 4.1

In twee dimensies komt het oplossen van een stelsel lineaire vergelijkingen neer op het vinden van het snijpunt (of de snijpunten) van een aantal lijnen:

\[\begin{split} \left\{ \begin{aligned} x-y&=1,\\ x+2y&=4. \end{aligned} \right. \end{split}\]

Dit stelsel heeft precies één oplossing, namelijk

\[ x=2\quad\text{en}\quad y=1. \]

Het bovenstaande stelsel komt overeen met de matrix-vectorvergelijking

\[\begin{split} \begin{pmatrix} 1& -1\\ 1& 2 \end{pmatrix} \begin{pmatrix}x\\ y\end{pmatrix} = \begin{pmatrix}1\\ 4\end{pmatrix}. \end{split}\]

4.1. Oplossen van stelsels lineaire vergelijkingen#

We schrijven de matrix-vectorvergelijking (4.1) of het corresponderende stelsel (4.2) ook wel als een aangevulde matrix:

(4.3)#\[\begin{split} \left( \begin{array}{cccc|c} a_{1,1}& a_{1,2}& \cdots& a_{1,n}& b_1\\ a_{2,1}& a_{2,2}& \cdots& a_{2,n}& b_2\\ \vdots& \vdots& \ddots& \vdots& \vdots\\ a_{m,1}& a_{m,2}& \cdots& a_{m,n}& b_m\\ \end{array} \right) \end{split}\]

Dit is een handige notatie omdat we niet steeds de variabelen \(x_1,\ldots,x_n\) hoeven op te schrijven.

Er is een systematische en efficiënte manier om stelsels lineaire vergelijkingen op te lossen. Dit gaat in twee stappen:

breng het stelsel (in de praktijk: de aangevulde matrix) in rijtrapvorm
bepaal de oplossingen door terugsubstitutie.

Definitie 4.2 (Rijtrapvorm)

Een matrix (of aangevulde matrix) staat in rijtrapvorm (row echelon form) als in elke rij het eerste niet-nulelement verder naar rechts dan in alle rijen erboven, en eventuele nulrijen (rijen met alleen nullen) helemaal onderaan staan.

Het eerste niet-nulelement van een niet-nulrij noemen we een spil(element) (Engels: pivot).

Voorbeeld 4.2

De volgende matrix is in rijtrapvorm, met de spillen rood gekleurd:

\[\begin{split} \left( \begin{array}{cccc|c} \color{red}{1}& 0& -1& 0& 0\\ 0& 0& \color{red}{2}& 1& 2\\ 0& 0& 0& \color{red}{-2}& 4 \end{array} \right) \end{split}\]

Deze correspondeert met het stelsel

\[\begin{split} \left\{ \begin{array}{rcrcrcrcr} x_1&&&-& x_3& & &=&0,\\ &&& &2x_3&+& x_4&=&2,\\ &&& & &-&2x_4&=&4.\\ \end{array} \right. \end{split}\]

4.2. Terugsubstitutie, oplossingen in parametervorm#

Het blijkt dat wanneer de (aangevulde) matrix in rijtrapvorm staat, de oplossingsverzameling eenvoudig te bepalen is. Terugwerkend vanaf de laatste variabele zijn er steeds twee mogelijkheden: of deze ligt vast door één van de vergelijkingen, of de waarde is vrij te kiezen.

In het bovenstaande voorbeeld vinden we uit de laatste vergelijking

\[ x_4=-2. \]

Uit de tweede vergelijking volgt vervolgens

\[ x_3 = \frac{1}{2}(2-x_4) = 2. \]

Voor \(x_2\) is er geen vergelijking die de waarde vastlegt, dus we concluderen

\[ x_2\text{ is vrij}. \]

De eerste vergelijking geeft (gebruikmakend van de eerder gevonden waarde \(x_3=2\))

\[ x_1 = 2. \]

We kunnen dit in parametervorm schrijven door voor de vrije variabele \(x_2\) een parameter te introduceren, bijvoorbeeld \(t\):

\[ x_1 = 2,\quad x_2 = t,\quad x_3 = 2,\quad x_4 = -2. \]

In vectorvorm is dit

\[\begin{split} \vx=\begin{pmatrix}2\\ t\\ 2\\ -2\end{pmatrix} = \begin{pmatrix}2\\ 0\\ 2\\ -2\end{pmatrix} +t\begin{pmatrix}0\\ 1\\ 0\\ 0\end{pmatrix}. \end{split}\]

4.3. Vrije variabelen en spilvariabelen#

Gegeven een stelsel lineaire vergelijkingen waarvan de aangevulde matrix in rijtrapvorm staat, noemen we de variabelen die corresponderen met een kolom die een spil bevat de spilvariabelen van het stelsel. Voor deze variabelen is er steeds een vergelijking die de waarde vastlegt in termen van de variabelen die verder naar rechts staan. De andere variabelen kunnen we vrij kiezen; deze heten dan ook vrije variabelen.

Stelling 4.1 (Aantal oplossingen van een matrix-vectorvergelijking)

Gegeven een matrix-vectorvergelijking \(H\vx=\vc\) met aangevulde matrix \((H\mid\vc)\) in rijtrapvorm zijn er de volgende mogelijkheden voor de oplossingsverzameling:

Als er een spilelement in de constantenkolom staat (dus een rij met nullen in de coëfficiëntenmatrix en een getal ongelijk aan 0 in de constantenkolom), dan zijn er geen oplossingen. Zo’n rij staat namelijk voor een vergelijking \(0=c\) met \(c\) een constante ongelijk aan 0. Het stelsel heet dan strijdig of inconsistent.
Als het stelsel niet strijdig is (we noemen het stelsel dan consistent) en elke kolom van de coëfficiëntenmatrix een spil bevat, dan is er precies één oplossing. Elke variabele ligt dan namelijk vast door één van de vergelijkingen.
Als het stelsel niet strijdig is de coëfficiëntenmatrix een kolom zonder spil bevat, dan zijn er oneindig veel oplossingen. Er is dan namelijk minstens één vrije variabele.

We bekijken een aantal voorbeelden:

\(\left( \begin{array}{cc|c} 1& 0& 0\\ 0& 0& 1 \end{array} \right)\): geen oplossingen (de tweede rij geeft de vergelijking \(0=1\))
\(\left( \begin{array}{cc|c} 1& 2& 4\\ 0& 3& 5 \end{array} \right)\): precies één oplossing (\(x_1\) en \(x_2\) zijn spilvariabelen)
\(\left(\begin{array}{cc|c} 0& 1& 0\\ 0& 0& 0 \end{array} \right)\): oneindig veel oplossingen (vrije variabele \(x_1\))

Voor een consistent stelsel in rijtrapvorm kunnen we de oplossingsverzameling bepalen door terugsubstitutie.

Voorbeeld 4.3

De aangevulde matrix

\[\begin{split} \left(\begin{array}{ccccc|c} 1& 2& 1& -5& 1& 3\\ 0& 0& -2& 4& 2& -4\\ 0& 0& 0& 3& 0& 6 \end{array} \right) \end{split}\]

komt overeen met het stelsel

\[\begin{split} \left\{ \begin{array}{rcrcrcrcrcr} x_1 & + & 2x_2 & + & x_3 & - & 5x_4 & + & x_5 & = & 3\\ & & & & -2x_3 & + & 4x_4 & + & 2x_5 & = & -4\\ & & & & & & 3x_4 & & & = & 6 \end{array} \right. \end{split}\]

Er staat geen spil in de constantenkolom, dus het stelsel is consistent. De kolommen 1, 3 en 4 bevatten een spil, dus \(x_1\), \(x_3\) en \(x_4\) zijn spilvariabelen. De kolommen 2 en 5 bevatten geen spil, dus \(x_2\) en \(x_5\) zijn vrije variabelen. Het stelsel heeft oneindig veel oplossingen, die beschreven kunnen worden met twee parameters.

We bepalen opnieuw de oplossingsverzameling via terugsubstitutie. We introduceren de parameters \(s\) en \(t\) door \(x_5=s\) en \(x_2=t\), en vinden achtereenvolgens

\[\begin{split} \begin{aligned} x_5 &= s,\\ x_4 &= 2,\\ x_3 &= -\frac{1}{2}(-4-4x_4-2x_5) = 2+2x_4+x_5 = 6 + s,\\ x_2 &= t,\\ x_1 &= 3-2x_2-x_3+5x_4-x_5 = 3-2t-(6+s)+10-s = 7 - 2s - 2t. \end{aligned} \end{split}\]

In vectorvorm:

\[\begin{split} \vx = \begin{pmatrix}7-2s-2t\\ t\\ 6+s\\ 2\\ s\end{pmatrix} = \begin{pmatrix}7\\0 \\ 6\\ 2\\ 0\end{pmatrix} +s\begin{pmatrix}-2\\ 0\\ 1\\ 0\\ 1\end{pmatrix} +t\begin{pmatrix}-2\\ 1\\ 0\\ 0\\ 0\end{pmatrix}. \end{split}\]

4.4. Rij-operaties#

We hebben gezien hoe we de oplossingsverzameling kunnen bepalen wanneer het stelsel in rijtrapvorm staat. We gaan nu een methode geven om een stelsel in stappen (zogeheten elementaire rijoperaties) om te schrijven tot een stelsel in rijtrapvorm, op zo’n manier dat de oplossingsverzameling hetzelfde blijft.

Definitie 4.3 (Elementaire rijoperaties)

Verwissel twee rijen
Vermenigvuldig een rij met een scalar ongelijk aan 0
Tel een scalair veelvoud van een rij bij een andere rij op

We bekijken bijvoorbeeld de matrix

\[\begin{split} A=\begin{pmatrix} 2& 2& 2\\ 0& 1& 2\\ 1& -2& 2 \end{pmatrix}. \end{split}\]

De eerste en derde rij van \(A\) verwisselen geeft

\[\begin{split} \begin{pmatrix} 1& -2& 2\\ 0& 1& 2\\ 2& 2& 2 \end{pmatrix}. \end{split}\]

De eerste rij van \(A\) met de scalar \(-1/2\) vermenigvuldigen geeft

\[\begin{split} \begin{pmatrix} -1& -1& -1\\ 0& 1& 2\\ 1& -2& 2 \end{pmatrix}. \end{split}\]

De tweede rij van \(A\) \(2\) keer bij de derde rij optellen geeft

\[\begin{split} A=\begin{pmatrix} 2& 2& 2\\ 0& 1& 2\\ 1& 0& 6 \end{pmatrix}. \end{split}\]

Definitie 4.4 (Rij-equivalentie van matrices)

Twee (aangevulde) matrices \(A\) en \(B\) heten rij-equivalent (notatie \(A\sim B\)) als \(A\) in \(B\) omgezet kan worden door een reeks elementaire rij-operaties.

Stelling 4.2

Als \((A\mid\vb)\) en \((B\mid\vw)\) twee aangevulde matrices zijn die rij-equivalent met elkaar zijn, dan hebben de matrix-vectorvergelijkingen \(A\vx=\vb\) en \(B\vx=\vw\) dezelfde oplossingsverzameling.

Om dit te bewijzen, is het voldoende om te laten zien dat het uitvoeren van één rij-operatie de oplossingsverzameling niet verandert. We laten het als opgave over om dit na te gaan voor elk van de drie typen elementaire rij-operaties.

4.5. Gauss-eliminatie (‘matrixvegen’)#

Dit is een algoritme om een aangevulde matrix \((A\mid\vb)\) om te schrijven tot een aangevulde matrix \((H\mid\vc)\) in rijtrapvorm met dezelfde oplossingsverzameling.

Algoritme 4.1 (Gauss-eliminatie)

Gegeven een aangevulde matrix \((A\mid\vb)\):

Zorg ervoor (door eventueel twee rijen te verwisselen) dat er in de eerste niet-nulkolom een spil in de eerste rij staat.
Tel veelvouden van deze rij op bij alle rijen eronder zodat onder deze spil alleen nullen komen te staan.
Herhaal dit proces met de matrix bestaande uit de elementen rechts van èn onder dit spilelement, net zolang totdat er geen niet-nulelementen over zijn.

Het oplossen van lineaire stelsels met behulp van Gauss-eliminatie is een zeer belangrijke techniek. Deze is zowel theoretisch van belang als voor allerlei numerieke algoritmen.

Let op: alle operaties die je uitvoert, moeten zowel op de coëfficiëntenmatrix (links van de streep) als op de constantenvector (rechts van de streep) toegepast worden.

Voorbeeld 4.4

Bekijk de aangevulde matrix

\[\begin{split} (A\mid\vb) = \left( \begin{array}{rrrr|r} 0& 4& 2& 0& 8\\ 2& -6& -1& 2& -12\\ 1& -2& 0& 4& -4 \end{array} \right). \end{split}\]

We verwisselen de eerste en derde rij om linksboven een spil te creëren. Dit geeft

\[\begin{split} \left( \begin{array}{rrrr|r} 1& -2& 0& 4& -4\\ 2& -6& -1& 2& -12\\ 0& 4& 2& 0& 8 \end{array} \right). \end{split}\]

We trekken vervolgens twee keer de eerste rij van de tweede rij af; dit levert

\[\begin{split} \left( \begin{array}{rrrr|r} 1& -2& 0& 4& -4\\ 0& -2& -1& -6& -4\\ 0& 4& 2& 0& 8 \end{array} \right). \end{split}\]

We vermenigvuldigen vervolgens de derde rij met \(1/2\):

\[\begin{split} \left( \begin{array}{rrrr|r} 1& -2& 0& 4& -4\\ 0& -2& -1& -6& -4\\ 0& 2& 1& 0& 4 \end{array} \right). \end{split}\]

Nu tellen we de tweede rij bij de derde rij op:

\[\begin{split} \left( \begin{array}{rrrr|r} \color{red}{1}& -2& 0& 4& -4\\ 0& \color{red}{-2}& -1& -6& -4\\ 0& 0& 0& \color{red}{-6}& 0 \end{array} \right). \end{split}\]

Deze aangevulde matrix staat in rijtrapvorm en correspondeert met het stelsel

\[\begin{split} \left\{ \begin{array}{rcrcrcrcr} x_1 & - & 2x_2 & & & + & 4x_4 & = & -4\\ & - & 2x_2 & - & x_3 & - & 6x_4 & = & -4\\ & & & & & - & 6x_4 & = & 0. \end{array} \right. \end{split}\]

De oplossingen vinden we via terugsubstitutie:

\(x_4=0\)
\(x_3\) is vrij, zeg \(x_3=r\);
\(x_2 = 2-\frac{1}{2}r\);
\(x_1 = -r\)

We schrijven dit in vectorvorm als

\[\begin{split} \vx = \begin{pmatrix}-r\\ 2-\frac{1}{2}r\\ r\\ 0\end{pmatrix} = \begin{pmatrix}0\\ 2\\ 0\\ 0\end{pmatrix} + r\begin{pmatrix}-1\\ -1/2\\ 1\\ 0\end{pmatrix}. \end{split}\]

Dit geeft de algemene oplossing van het stelsel (of van de matrix-vectorvergelijking) in parametervorm.

4.6. Gauss-Jordan-eliminatie (vegen naar gereduceerde rijtrapvorm)#

Definitie 4.5 (Gereduceerde rijtrapvorm)

Een aangevulde matrix (of het bijbehorende stelsel lineaire vergelijkingen) staat in gereduceerde rijtrapvorm als aan de volgende twee voorwaarden voldaan is:

het stelsel staat in rijtrapvorm
in elke spilkolom is het spilelement gelijk aan 1 en staan er verder alleen nullen.

Het kan nuttig zijn om een stelsel, na het in rijtrapvorm gebracht te hebben, verder te ‘vegen’ tot gereduceerde rijtrapvorm.

Algoritme 4.2 (Gauss-Jordan-eliminatie)

Gegeven een aangevulde matrix \((A\mid\vb)\):

Breng \((A\mid\vb)\) in rijtrapvorm.
Voor elke spilkolom, van rechts naar links:
- Schaal de rij waarin de spil staat zodat de spil gelijk wordt aan 1.
- Tel veelvouden van deze rij op bij de rijen erboven zodat boven deze spil alleen nullen komen te staan.

Voorbeeld 4.5

Bekijk de volgende aangevulde matrix in rijtrapvorm:

\[\begin{split} \left( \begin{array}{rrrr|r} 1& 0& 1& 1& -1\\ 0& 2& 4& -2& 6\\ 0& 0& 0& 3& 3\\ 0& 0& 0& 0& 0 \end{array} \right). \end{split}\]

De laatste rij kunnen we weglaten. We vermenigvuldigen verder de tweede rij met \(1/2\) en de derde rij met \(1/3\). Dit geeft

\[\begin{split} \left( \begin{array}{rrrr|r} 1& 0& 1& 1& -1\\ 0& 1& 2& -1& 3\\ 0& 0& 0& 1& 1 \end{array} \right). \end{split}\]

We tellen vervolgens de derde rij bij de tweede rij op:

\[\begin{split} \left( \begin{array}{rrrr|r} 1& 0& 1& 1& -1\\ 0& 1& 2& 0& 4\\ 0& 0& 0& 1& 1 \end{array} \right). \end{split}\]

We trekken de derde rij van de eerste rij af:

\[\begin{split} \left( \begin{array}{rrrr|r} \color{red}{1}& 0& 1& 0& -2\\ 0& \color{red}{1}& 2& 0& 4\\ 0& 0& 0& \color{red}{1}& 1 \end{array} \right). \end{split}\]

Deze aangevulde matrix staat in gereduceerde rijtrapvorm en correspondeert met het stelsel

\[\begin{split} \left\{ \begin{array}{rcrcrcrcr} x_1 & & & + & x_3 & & & = & -2\\ & & x_2 & + & 2x_3 & & & = & 4\\ & & & & & & x_4 & = & 1. \end{array} \right. \end{split}\]

De variable \(x_3\) is vrij. We introduceren een parameter \(s\) en \(x_3=s\). De algemene oplossing van het stelsel is dan

\[\begin{split} \begin{aligned} x_1 &= -2-s,\\ x_2 &= 4-2s,\\ x_3 &= s,\\ x_4 &= 1.\\ \end{aligned} \end{split}\]

In vectorvorm:

\[\begin{split} \vx = \begin{pmatrix}-2\\ 4\\ 0\\ 1\end{pmatrix} + s\begin{pmatrix}-1\\ -2\\ 1\\ 0\end{pmatrix}. \end{split}\]

De gereduceerde rijtrapvorm heeft twee belangrijke voordelen: het geeft een unieke schrijfwijze van een stelsel lineaire vergelijkingen, en de oplossing is direct af te lezen uit de gereduceerde rijtrapvorm. Daar staat tegenover dat het vegen wat meer werk is.