Hoe Werken Elementaire Rijbewerkingen bij het Oplossen van Lineaire Vergelijkingen?

In de lineaire algebra worden stelsels van lineaire vergelijkingen vaak opgelost met behulp van matrixoperaties. Het idee achter het gebruik van elementaire rijbewerkingen is dat we door het toepassen van een eindig aantal van deze bewerkingen een matrix in een vorm kunnen brengen die gemakkelijker op te lossen is, bijvoorbeeld de rij-echelonvorm of de gereduceerde rij-echelonvorm. Twee matrices die verwisselbare rijen hebben door een eindig aantal elementaire rijbewerkingen worden als rij-equivalent beschouwd.

Er zijn drie soorten elementaire rijbewerkingen die we kunnen toepassen: het verwisselen van twee rijen, het vermenigvuldigen van een rij met een niet-nul constante, en het optellen van een veelvoud van een rij bij een andere rij. De eerste twee bewerkingen spelen een rol bij het elimineren van elementen in een matrix, terwijl de derde bewerking essentieel is voor de Gaussian eliminatie, het proces dat vaak wordt gebruikt om lineaire stelsels op te lossen.

Een voorbeeld van het gebruik van elementaire rijbewerkingen is het oplossen van een systeem van lineaire vergelijkingen. Beschouw het volgende systeem van vier vergelijkingen in drie onbekenden:

Bij de teruggave van substitutie zien we dat we beginnen met de laatste niet-triviale rij, die in dit geval leidt tot de waarde $x_3 = -2$. Vervolgens kunnen we de waarde van $x_2$ berekenen uit de tweede rij en uiteindelijk $x_1$ uit de eerste rij. In dit specifieke voorbeeld hebben we een unieke oplossing voor het systeem van vergelijkingen.

Er zijn echter gevallen waarin het aantal vergelijkingen niet gelijk is aan het aantal onbekenden. Als er meer vergelijkingen dan onbekenden zijn, spreken we van een overgedetermineerd systeem. Dergelijke systemen zijn vaak inconsistent, wat betekent dat ze geen oplossing hebben. Dit kan bijvoorbeeld optreden wanneer de vergelijkingen beschrijven dat verschillende vlakken in een ruimte elkaar niet snijden, of wanneer sommige van de vlakken parallel zijn.

Wanneer het aantal vergelijkingen gelijk is aan het aantal onbekenden, noemen we het systeem bepaald, en in de meeste gevallen heeft het systeem een unieke oplossing. Er zijn echter uitzonderingen, zoals wanneer de vergelijkingen beschrijven dat de vlakken of lijnen parallel zijn en geen enkel punt van snijding hebben. In dergelijke gevallen is het systeem inconsistent.

Naast deze typische gevallen van inconsistentie en oneindige oplossingen, kunnen we systemen hebben waarin de oplossingen zich op een lijn, een vlak of een hypervlak bevinden. Bijvoorbeeld, een systeem van drie onbekenden met vier vergelijkingen kan leiden tot een oplossing die bestaat uit een lijn of zelfs een vlak van oplossingen. Het concept van vrije en basale variabelen komt hier in het spel: de vrije variabelen kunnen worden beschouwd als parameters die de vrijheid van de oplossing beschrijven.

In situaties waarin de vrije variabelen kunnen worden gekozen, kunnen de oplossingen als volgt worden gepresenteerd:

waarbij $\mathbf{x_0}$ een specifieke oplossing is en $t$ een parameter die de vrijheid in de oplossing weerspiegelt. Dit komt vaak voor in systemen die ondergedetermineerd zijn, zoals het geval is bij systemen van lineaire vergelijkingen die geometrisch gezien een lijn of een vlak van oplossingen vertegenwoordigen.

Hoe vermijd je fouten door afronding bij Gauss-eliminatie?

De Gauss-eliminatie omvat de stap waarbij je door middel van elementaire rijoperaties een matrix omzet naar een bovenste driehoekige vorm. Het totale aantal benodigde bewerkingen om dit proces te voltooien is van de orde $O(n^3)$, wat betekent dat de tijd die nodig is om de matrix te verwerken, snel toeneemt naarmate de afmetingen van de matrix groter worden. Wanneer we de matrix omzetten naar de vorm $LU = A$ via LU-factorisatie, is het aantal benodigde bewerkingen gelijk aan de bewerkingen die nodig zijn voor de voortgang van de eliminatie.

Echter, het zou te simplistisch zijn om te denken dat de Gauss-eliminatie altijd foutloos verloopt. In de praktijk is de volgorde van de pivot-keuze van cruciaal belang om grote afrondingsfouten te voorkomen. Dit wordt vaak geïllustreerd met een voorbeeld waarin afrondingsfouten de oplossingen van een klein systeem drastisch verstoren. Stel je voor dat we werken met een machine die slechts twee significante cijfers gebruikt voor afrondingen, zoals vaak het geval is in numerieke berekeningen. Wanneer we een systeem van lineaire vergelijkingen oplossen, kan de keuze van een ongeschikte pivot leiden tot fouten die snel kunnen oplopen in de verdere berekeningen. Als de verkeerde rij als pivot wordt gekozen, kan het resultaat een onjuiste oplossing geven, zelfs als de oorspronkelijke waarden bijna identiek zijn.

In een eenvoudig voorbeeld van een 2x2-systeem met een erg kleine waarde als pivot, zal de machine de waarde afronden naar een groter getal, wat het verschil tussen de juiste en verkeerde oplossing vergroot. Dit probleem kan opgelost worden door rijen te verwisselen op basis van de grootte van de elementaire waarden in elke rij, zodat de rij met de grootste waarde als pivot wordt gekozen. Dit wordt de geschaalde partiële pivotering genoemd.

Het proces van geschaalde partiële pivotering bestaat uit drie hoofdfasen:

1. Schaalfactoren berekenen: Voor elke rij van de matrix wordt de grootste absolute waarde van de elementen in die rij gevonden. Dit stelt ons in staat om de schaal van elke rij te bepalen en de invloed van kleinere getallen te minimaliseren.

2. Berekening van de ratio: Vervolgens berekenen we voor elke rij het quotiënt van de eerste waarde in de rij gedeeld door de schaalfactor van die rij. Dit geeft ons een maat voor de relative grootte van de elementen in die rij.

3. Pivotselectie: De rij met de grootste waarde voor deze ratio wordt als pivot gekozen, en we voeren de Gauss-eliminatie uit door de matrix te transformeren met deze rij bovenaan. Dit vermindert de kans op grote afrondingsfouten bij de verwerking van de matrix.

Wanneer we deze techniek toepassen, kunnen we de gevolgen van afrondingsfouten in de berekeningen minimaliseren en de nauwkeurigheid van de uiteindelijke oplossing vergroten. Dit blijkt vooral belangrijk wanneer we werken met grote matrices of wanneer de matrix slecht geconditioneerd is, wat betekent dat kleine veranderingen in de input leiden tot grote veranderingen in de output.

Het is belangrijk te begrijpen dat hoewel geschaalde partiële pivotering een significante verbetering biedt ten opzichte van eenvoudige Gauss-eliminatie, het de noodzaak van een goede numerieke analyse niet vervangt. De stabiliteit van de methode kan nog steeds variëren afhankelijk van de eigenschappen van de matrix die we verwerken. Het is essentieel om bij het ontwerpen van algoritmen en het oplossen van systemen niet alleen naar de bewerkingen zelf te kijken, maar ook naar de voorwaarden waaronder die bewerkingen plaatsvinden, zoals de conditionering van de matrix en de schaal van de elementen.