Er zijn verschillende algoritmen voor het oplossen van een stelsel lineaire vergelijkingen.
De oplossing beschrijvenEd
Om een stelsel met een oneindig aantal oplossingen te beschrijven, worden doorgaans enkele van de variabelen als vrij (of onafhankelijk, of als parameters) aangeduid, wat betekent dat ze elke waarde mogen aannemen, terwijl de overige variabelen afhankelijk zijn van de waarden van de vrije variabelen.
Bedenk bijvoorbeeld het volgende stelsel:
x + 3 y – 2 z = 5 3 x + 5 y + 6 z = 7 {displaystyle {begin{alignedat}{7}x&&&&3y&&&&2z&&&&&3x&&&&5y&&&&6z&&&&&\end{alignedat}}}
De verzameling oplossingen van dit stelsel kan worden beschreven door de volgende vergelijkingen:
x = – 7 z – 1 en y = 3 z + 2 . {\displaystyle x=-7z-1\;\;\;\;{\text{and}}\;\;\;\;y=3z+2{\text{.}}}
Hier is z de vrije variabele, terwijl x en y afhankelijk zijn van z. Elk punt in de oplossingsverzameling kan worden verkregen door eerst een waarde voor z te kiezen, en dan de bijbehorende waarden voor x en y te berekenen.
Elke vrije variabele geeft de oplossingsruimte één vrijheidsgraad, waarvan het aantal gelijk is aan de dimensie van de oplossingsverzameling. Bijvoorbeeld, de oplossingsverzameling voor bovenstaande vergelijking is een lijn, omdat een punt in de oplossingsverzameling kan worden gekozen door de waarde van de parameter z op te geven. Een oneindige oplossing van hogere orde kan een vlak beschrijven, of een verzameling van hogere dimensies.
Verschillende keuzes voor de vrije variabelen kunnen leiden tot verschillende beschrijvingen van dezelfde oplossingsverzameling. De oplossing van bovenstaande vergelijkingen kan bijvoorbeeld ook als volgt worden beschreven:
y = – 3 7 x + 11 7 en z = – 1 7 x – 1 7 . {Displaystyle y=-{\frac {3}{7}}x+{\frac {11}{7}}};\;\;\;\;\text{en}};z=-{\frac {1}{7}}x-{\frac {1}{7}}}{\text{.}}
Hierbij is x de vrije variabele, en zijn y en z afhankelijk.
Eliminatie van variabelenEdit
De eenvoudigste methode om een stelsel lineaire vergelijkingen op te lossen is het herhaaldelijk elimineren van variabelen. Deze methode kan als volgt worden beschreven:
- Oplos in de eerste vergelijking één van de variabelen in termen van de andere.
- Voeg deze uitdrukking in de overige vergelijkingen in. Dit levert een stelsel vergelijkingen op met één vergelijking minder en één onbekende minder.
- Herhaal dit totdat het stelsel is teruggebracht tot één lineaire vergelijking.
- Volg deze vergelijking op, en substitueer dan terug totdat de volledige oplossing is gevonden.
Bedenk bijvoorbeeld het volgende stelsel:
x + 3 y – 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle {begin{alignedat}{7}x&&&&3y&&&&2z&&&&&3x&&&&5y&&&&6z&&&&&2x&&&&4y&&&&3z&&&&&\end{alignedat}}}
Oplossen van de eerste vergelijking voor x geeft x = 5 + 2z – 3y, en dit in de tweede en derde vergelijking stoppen geeft
– 4 y + 12 z = – 8 – 2 y + 7 z = – 2 {{alignedat}{5}-4y&&&&12z&&&&&2y&&&&7z&&&&&\end{alignedat}}}
Oplossen van de eerste van deze vergelijkingen voor y geeft y = 2 + 3z, en als je dit in de tweede vergelijking stopt, geeft z = 2. We hebben nu:
x = 5 + 2 z – 3 y y = 2 + 3 z z = 2 {displaystyle {begin{alignedat}{7}x&&&&&&&&2z&&&&3y&&&&&&&&&3z&&&&&\\z&&&&&&&&&&&&&\end{alignedat}}}
RijverkleiningEdit
Bij rij-reductie (ook bekend als Gaussische eliminatie) wordt het lineaire systeem voorgesteld als een vermeerderde matrix:
. {Displaystyle \left{text{.}}}
Deze matrix wordt dan gewijzigd met behulp van elementaire rijbewerkingen tot hij de gereduceerde rij-echelonvorm bereikt. Er zijn drie soorten elementaire rijbewerkingen:
Type 1: Verwissel de posities van twee rijen. Type 2: Vermenigvuldig een rij met een scalair niet nul. Type 3: Tel bij een rij een scalair veelvoud op van een andere rij.
Omdat deze bewerkingen omkeerbaar zijn, vertegenwoordigt de verkregen vergrote matrix altijd een lineair stelsel dat equivalent is aan het origineel.
Er zijn verschillende specifieke algoritmen om een vergrote matrix te rijen te verkleinen, waarvan de eenvoudigste Gaussiaanse eliminatie en Gauss-Jordaanse eliminatie zijn. De volgende berekening toont Gauss-Jordaanse eliminatie toegepast op bovenstaande matrix:
∼ ∼ ∼ ∼ ∼ ∼ ∼ . {\displaystyle}}&&&&&&}}}}}
De laatste matrix is in gereduceerde rij-echelonvorm, en stelt het stelsel x = -15, y = 8, z = 2 voor. Een vergelijking met het voorbeeld in het vorige hoofdstuk over de algebraïsche eliminatie van variabelen laat zien dat deze twee methoden in feite hetzelfde zijn; het verschil zit in de manier waarop de berekeningen worden opgeschreven.
Cramer’s ruleEdit
Cramer’s rule is een expliciete formule voor de oplossing van een stelsel lineaire vergelijkingen, waarbij elke variabele gegeven wordt door een quotiënt van twee determinanten. Bijvoorbeeld, de oplossing van het stelsel
x + 3 y – 2 z = 5 3 x + 5 y + 6 z = 7 2 x + 4 y + 3 z = 8 {\displaystyle {begin{alignedat}{7}x&&\;3y&&\;2z&&\;5\\3x&&\;5y&&\;6z&&\;7\\2x&&\;4y&&\;3z&&\;8\end{alignedat}}}
is gegeven door
x = | 5 3 – 2 7 5 6 8 4 3 | | 1 3 – 2 3 5 6 2 4 3 | , y = | 1 5 – 2 3 7 6 2 8 3 | 1 3 – 2 3 5 6 2 4 3 | 1 3 – 2 3 5 7 6 2 4 3 | , z = | 1 3 5 3 7 2 4 8 | 1 3 – 2 3 5 6 2 4 3 | . {\a6}Displaystyle x={\frac {\a6},\left|{\begin{matrix}5&&&&&&3\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}},\;\;\;\;y={\frac {\,\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}},\;\;\;\;z={\frac {\,\left|{\begin{matrix}1&&&&&&8\end{matrix}}\right|\,}{\,\left|{\begin{matrix}1&&&&&&3\end{matrix}}\right|\,}}.}
Voor elke variabele is de noemer de determinant van de coëfficiëntenmatrix, terwijl de teller de determinant is van een matrix waarin één kolom is vervangen door de vector van constante termen.
Hoewel de regel van Cramer theoretisch belangrijk is, heeft hij in de praktijk weinig waarde voor grote matrices, omdat de berekening van grote determinanten nogal omslachtig is. (Grote determinanten zijn het gemakkelijkst te berekenen met behulp van rijverkleining.)Verder heeft de regel van Cramer zeer slechte numerieke eigenschappen, waardoor hij ongeschikt is om zelfs kleine stelsels betrouwbaar op te lossen, tenzij de bewerkingen worden uitgevoerd in rationale rekenkunde met onbegrensde precisie.
MatrixoplossingEdit
Als het vergelijkingsstelsel wordt uitgedrukt in de matrixvorm A x = b {{displaystyle A\mathbf {x} =mathbf {b}} } kan de hele verzameling oplossingen ook in matrixvorm worden uitgedrukt. Als de matrix A vierkant is (met m rijen en n=m kolommen) en een volledige rang heeft (alle m rijen zijn onafhankelijk), dan heeft het stelsel een unieke oplossing gegeven door
x = A – 1 b {{{displaystyle \mathbf {x} =A^{-1}\mathbf {b} } } x = A + b + ( I – A + A ) w {Displaystyle \mathbf {x} =A^{+}\mathbf {b} +(I-A^{+}A)\mathbf {w} }
Andere methoden
Terwijl stelsels van drie of vier vergelijkingen gemakkelijk met de hand kunnen worden opgelost (zie Krakovisch), worden voor grotere stelsels vaak computers gebruikt. Het standaardalgoritme voor het oplossen van een stelsel lineaire vergelijkingen is gebaseerd op Gaussische eliminatie met enkele wijzigingen. Ten eerste is het essentieel om deling door kleine getallen te vermijden, wat tot onnauwkeurige resultaten kan leiden. Dit kan worden gedaan door zo nodig de volgorde van de vergelijkingen te wijzigen, een proces dat bekend staat als pivoteren. Ten tweede doet het algoritme niet precies Gaussische eliminatie, maar berekent het de LU-decompositie van de matrix A. Dit is vooral een organisatorisch hulpmiddel, maar het is veel sneller als men verschillende stelsels met dezelfde matrix A maar verschillende vectoren b moet oplossen.
Als de matrix A een speciale structuur heeft, kan hiervan gebruik worden gemaakt om snellere of nauwkeurigere algoritmen te krijgen. Systemen met een symmetrisch positief bepaalde matrix kunnen bijvoorbeeld twee keer zo snel worden opgelost met de Cholesky-decompositie. Levinson recursie is een snelle methode voor Toeplitz matrices. Er bestaan ook speciale methoden voor matrices met veel nul-elementen (zogenaamde sparse matrices), die vaak in toepassingen voorkomen.
Voor zeer grote stelsels, die anders te veel tijd of geheugen zouden vergen, wordt vaak een heel andere aanpak gekozen. Het idee is te beginnen met een eerste benadering van de oplossing (die helemaal niet nauwkeurig hoeft te zijn), en deze benadering in een aantal stappen te veranderen om haar dichter bij de werkelijke oplossing te brengen. Zodra de benadering voldoende nauwkeurig is, wordt deze beschouwd als de oplossing van het systeem. Dit leidt tot de klasse van de iteratieve methoden.
Er bestaat ook een kwantumalgoritme voor lineaire stelsels van vergelijkingen.