title: Numerieke lineaire algebra
text: Numerieke lineaire algebra onderzoekt hoe matrixbewerkingen kunnen worden gebruikt om computeralgoritmen te creëren die efficiënt en nauwkeurig benaderende antwoorden geven op vragen binnen de continue wiskunde. Het is een deelgebied van de numerieke analyse en een soort lineaire algebra. Computers gebruiken drijvende-kommaberekeningen. Irrationale getallen kunnen niet exact op de computer weergeven worden. Toepassing van een computeralgoritme op een matrix kan soms het verschil vergroten tussen een resultaat dat in de computer is opgeslagen en het getal waarvan het een benadering is. Numerieke lineaire algebra gebruikt eigenschappen van vectoren en matrices om computeralgoritmen te ontwikkelen die de door de computer geïntroduceerde fouten minimaliseren. Het onderzoek is er ook op gericht om het algoritme zo efficiënt mogelijk te maken.
  
  Numerieke lineaire algebra is vaak een fundamenteel onderdeel van technische en computationele wetenschappelijke problemen, zoals beeld- en signaalverwerking, telecommunicatie, financiële wiskunde, materiaalkundesimulaties, structuurbiologie, datamining, bio-informatica en vloeistofmechanica. Matrixmethoden worden met name gebruikt in eindige differentie methoden, eindige elementen methoden en het modelleren van differentiaalvergelijkingen. Gezien de brede toepassingen van numerieke lineaire algebra, beweren Lloyd N. Trefethen en David Bau, III dat het "net zo fundamenteel is voor de wiskundige wetenschappen als de gebieden calculus en differentiaalvergelijkingen", ook al is het een relatief klein onderzoeksgebied. Omdat veel eigenschappen van matrices en vectoren ook van toepassing zijn op functies en operatoren, kan numerieke lineaire algebra ook worden gezien als een vorm van functionaalanalyse, die vooral nadruk legt op praktische algoritmen.
  
  Problemen die veel voorkomen bij numerieke lineaire algebra zijn gebaseerd op matrixontbindingen zoals de singulierenwaardenontbinding, de QR-factorisatie, de LU-factorisatie of de eigenwaardedecompositie. Deze ontbindingen kunnen vervolgens worden gebruikt voor algemene lineaire algebraïsche problemen, zoals het oplossen van stelsels van lineaire vergelijkingen, het lokaliseren van eigenwaarden, of kleinste kwadraten optimalisatie. Een belangrijk onderwerp binnen de numerieke lineaire algebra is het ontwikkelen van algoritmen die minimale fouten introduceren wanneer ze worden toegepast op gegevens op een computer. Dit wordt vaak bereikt door het gebruik van iteratieve methoden in plaats van directe methoden.
  
  Geschiedenis 
  Numerieke lineaire algebra is ontwikkeld door computerpioniers als John von Neumann, Alan Turing, James H. Wilkinson, Alston Scott Householder, George Forsythe en Heinz Rutishauser. Zij programmeerden de eerste computers met behulp van numerieke lineaire algebra om de oplossingen van problemen in de continue wiskunde te benaderen. Voorbeelden hiervan zijn ballistische problemen en de oplossingen van stelsels partiële differentiaalvergelijkingen. John von Neumann en Herman Goldstine deden in 1947 de eerste serieuze poging om computerfouten bij de toepassing van algoritmen op echte data tot een minimum te beperken. Het vakgebied is gegroeid doordat de technologie onderzoekers steeds meer in staat heeft gesteld complexe problemen op te lossen op extreem grote matrices met hoge precisie. Sommige numerieke algoritmen zijn bekender geworden omdat technologieën zoals parallel rekenen tot praktische benaderingen van wetenschappelijke problemen hebben geleid.
  
  Matrixontbindingen
  
  Blokmatrices 
  Voor veel problemen in de numerieke lineaire algebra is het nuttig om een matrix te beschouwen als een verzameling van kolomvectoren. Bijvoorbeeld: bij het oplossen van het lineaire stelsel  zien we  in plaats van het product van  als de vector van coëfficiënten in de lineaire ontbinding van  in de basis gevormd door de kolommen van .  Matrices beschouwen als een verzameling van kolommen geeft ook een goed inzicht voor veel matrixalgoritmen. Immers, matrixalgoritmen bevatten vaak twee geneste lussen: één over de kolommen van een matrix  en een andere over de rijen van . Bijvoorbeeld voor matrices  en vectoren  en , kunnen we het volgende kolomgeoriënteerde algoritme gebruiken om  te berekenen:
  
  for q = 1:n
    for p = 1:m
      y(p) = A(p,q)*x(q) + y(p)
    end
  end
  
  Singulierewaardenontbinding 
  De singulierewaardenontbinding van een matrix  kan geschreven worden als  waarbij de vierkante matrices  en  unitair zijn, en de  matrix  diagonaal is. De diagonaalelementen van  worden de singuliere waarden van  genoemd. Omdat singuliere waarden de vierkantswortels zijn van de eigenwaarden van , is er een nauw verband tussen de singulierewaardenontbinding en de eigenwaarde ontbinding. Dit betekent dat veel methoden voor het berekenen van de singulierewaardenontbinding vergelijkbaar zijn met eigenwaardemethoden.
  
  QR-factorisatie 
  De QR-factorisatie van een matrix  wordt bepaald door een matrix  en een matrix  te vinden zodat , waarbij  orthogonaal is en  een bovendriehoeksmatrix is.  De twee belangrijkste algoritmen voor het berekenen van QR-factorisaties zijn het Gram-Schmidt-proces en de Householdertransformatie. De QR-factorisatie wordt veel gebruikt om lineaire kleinste-kwadratenproblemen en eigenwaardeproblemen op te lossen. Hierbij wordt vaak het iteratieve QR-algoritme gebruikt.
  
  LU-factorisatie 
  Een LU-factorisatie van een niet-singuliere matrix  bestaat uit het product van een onderdriehoeksmatrix  met waarden 1 op de hoofddiagonaal en een bovendriehoeksmatrix  zodat . De matrix  wordt gevonden met behulp van een veegoperatie: hierbij wordt de matrix  links vermenigvuldigd met een reeks matrices  om tot de bovendriehoeksmatrix  te komen. De matrix  wordt nu gegeven door .
  
  Eigenwaarde ontbinding 
  De eigenwaarde ontbinding van een matrix  kan geschreven worden als , waarbij de kolommen van  de eigenvectoren zijn van , en  een diagonaalmatrix is waarvan de diagonaalelementen de corresponderende eigenwaarden van  zijn. Er is geen directe methode om de eigenwaarde ontbinding van een willekeurige matrix te bepalen. Het is immers onmogelijk een programma te schrijven dat de exacte wortels van een willekeurig polynoom in eindige tijd vindt. Dus moet elke methode om het algemene eigenwaardeprobleem op te lossen noodzakelijkerwijs iteratief zijn.
  
  Algoritmen
  
  Gauss-eliminatie 
  Vanuit het perspectief van de numerieke lineaire algebra is Gauss-eliminatie een procedure voor het ontbinden van een niet-singuliere matrix  in zijn LU-factorisatie. Gauss-eliminatie bereikt dit door  links te vermenigvuldigen met een aantal matrices  totdat  een bovendriehoeksmatrix is en  een onderdriehoekmatrix is, waar . Rechttoe-rechtaan programma's voor Gauss-eliminatie zijn notoir instabiel en produceren enorme fouten, wanneer ze worden toegepast op matrices met veel significante cijfers. De eenvoudigste oplossing is om kolompivoting te introduceren, wat een aangepast Gauss-eliminatiealgoritme oplevert dat wel stabiel is. Kolompivoting is een kolomverwisseling zodat het grootste element van die kolom op de diagonaal komt te staan.
  
  Oplossingen van lineaire systemen 
  Numerieke lineaire algebra beschouwt matrices als een aaneenschakeling van kolomvectoren. Om het lineaire stelsel   op te lossen, is de traditionele algebraïsche benadering om  te zien als het product van  met . Numerieke lineaire algebra interpreteert in plaats daarvan  als de vector van coëfficiënten van de lineaire expansie van  in de basis gevormd door de kolommen van . Er kunnen veel verschillende decomposities worden gebruikt om het lineaire probleem op te lossen, afhankelijk van de eigenschappen van de matrix  en de vectoren  en , waardoor de ene factorisatie veel gemakkelijker te verkrijgen is dan de andere. Als  een QR-factorisatie is van , dan geldt . Dit is eenvoudig te berekenen met deze matrixfactorisatie. Als  een eigendecompositie is van , en we zoeken  zodat , met  en , dan geldt . Dit hangt nauw samen met de oplossing van het lineaire systeem met behulp van de singulierewaardenontbinding, omdat de singuliere waarden van een matrix de vierkantswortels zijn van zijn eigenwaarden.
  
  Kleinste kwadraten optimalisatie 
  Matrixdecomposities kunnen gebruikt worden om over- en onderbepaalde stelsels  op te lossen. Een manier is om het residu  te minimaliseren, zoals in het regressieprobleem. Het QR-algoritme lost dit probleem op door eerst de gereduceerde QR-factorisatie van  te berekenen. De gereduceerde QR-factorisatie is een QR-factorisatie waarbij de 0-singuliere waarden weggelaten worden. Dtt leidt tot gereduceerde matrices  en .  Na herordening krijgen we dan . Dit bovendriehoeksstelsel kan dan worden opgelost voor . De SVD suggereert ook een algoritme voor het verkrijgen van de oplossing van een lineair kleinste kwadraten probleem. Door de gereduceerde SVD-ontbinding te berekenen  en dan de vector   te berekenen, reduceren we het kleinste-kwadratenprobleem tot een eenvoudig diagonaalstelsel.  Naast de klassieke methode voor normaalvergelijkingen voor het oplossen van de kleinste kwadraten problemen, kunnen deze problemen ook worden opgelost met behulp van methoden die gebruikmaken van het Gram-Schmidt-algoritme en de Householder-methode.
  
  Conditie en stabiliteit 
  Stel dat een probleem beschreven kan worden met een functie , waarbij  een genormeerde vectorruimte van data is en  een genormeerde vectorruimte van oplossingen is. Voor een bepaalde vector , is het probleem slecht geconditioneerd als een kleine verstoring in  een grote verandering in de waarde van  veroorzaakt. We kunnen dit kwantificeren door een conditiegetal te definiëren dat aangeeft hoe goed (of slecht) geconditioneerd een probleem is. Dit conditiegetal is gedefinieerd als
  
  We noemen een computeralgoritme, dat gebruikmaakt van drijvende-kommagetallen, instabiel als de benaderende oplossing veel verschilt van de exacte wiskundige oplossing. Wanneer een matrix getallen met veel significante cijfers bevat, kunnen veel algoritmen voor het oplossen van problemen, zoals stelsels van lineaire vergelijkingen of optimalisatie van de kleinste kwadraten, zeer onnauwkeurige resultaten opleveren. Het creëren van stabiele algoritmen voor slecht geconditioneerde problemen is een belangrijk onderzoeksgebied in de numerieke lineaire algebra. Een voorbeeld is dat de stabiliteit van triangularisatie met de Householdermethode een robuuste oplossingsmethode geeft voor lineaire stelsels. De instabiliteit van de normaalvergelijkingsmethode voor het oplossen van kleinste-kwadratenproblemen is een reden om de voorkeur te geven aan matrixontbindingsmethoden, zoals het gebruik van singulierewaardenontbinding. Sommige methoden voor matrixontbinding kunnen instabiel zijn, maar hebben eenvoudige aanpassingen die ze stabiel maken. Een voorbeeld is de instabiele Gram-Schmidt methode, die gemakkelijk kan worden gewijzigd in de stabiele gemodificeerde Gram-Schmidt methode. Een ander klassiek probleem in de numerieke lineaire algebra is het feit dat Gauss-eliminatie instabiel is, maar stabiel wordt met de introductie van pivoting.
  
  Iteratieve methoden 
  Er zijn twee redenen waarom iteratieve algoritmen een belangrijk onderdeel vormen van de numerieke lineaire algebra. Ten eerste hebben veel belangrijke numerieke problemen geen directe oplossing. Bijvoorbeeld: de eigenwaarden en eigenvectoren van een willekeurige matrix kunnen we alleen benaderen met een iteratieve methode. Ten tweede: directe oplosmethoden voor een probleem met een willekeurige  matrix vereisen  tijd, wat verrassend hoge kosten zijn aangezien de matrix slechts  getallen bevat. Iteratieve methoden kunnen profiteren van verschillende matrixeigenschappen om deze rekentijd te verminderen. Als een matrix bijvoorbeeld ijl is, kan een iteratief algoritme veel van de stappen overslaan die een directe methode noodzakelijkerwijs moet uitvoeren, zelfs als het onnodige stappen zijn bij een zeer ijle matrix.
  
  De kern van veel iteratieve methoden in de numerieke lineaire algebra is de projectie van een matrix op een laag-dimensionale Krylov-deelruimte. Bij toenemen van de dimensie van de Krylov-deelruimte komt er een steeds betere benadering tot stand. Wanneer  symmetrisch is en we het lineaire stelsel  willen oplossen, is de klassieke iteratieve methode de geconjugeerde gradiëntenmethode. Als  niet symmetrisch is, dan zijn voorbeelden van iteratieve oplosmethoden voor het lineaire probleem de gegeneraliseerde minimale residumethode (GMRES) en CG, toegepast op de normaalvergelijkingen. Als  symmetrisch is, kunnen we om het eigenwaarde- en eigenvectorprobleem op te lossen het Lanczos-algoritme gebruiken, en als  niet-symmetrisch is, dan kunnen we het Arnoldi-algoritme gebruiken.
  
  Software 
  Verschillende programmeertalen gebruiken numerieke lineaire algebra-optimalisatietechnieken en zijn ontworpen om numerieke lineaire algebra-algoritmen te implementeren. Deze talen omvatten MATLAB, Analytica, Maple en Mathematica. Andere programmeertalen die niet expliciet zijn ontworpen voor numerieke lineaire algebra, hebben bibliotheken die numerieke lineaire algebra-routines en -optimalisatie bieden; C en Fortran hebben pakketten zoals Basic Linear Algebra Subprograms (BLAS) en LAPACK, python heeft de bibliotheek NumPy en Perl heeft de Perl Data Language. Veel numerieke lineaire algebra-opdrachten in R gebruiken deze meer fundamentele bibliotheken zoals LAPACK.
  
  Referenties
  
  Externe links 
  
   Vrij beschikbare software voor numerieke algebra op het web, samengesteld door Jack Dongarra en Hatem Ltaief, Universiteit van Tennessee
   NAG Bibliotheek met numerieke lineaire algebra-routines
      (Onderzoeksgroep in het Verenigd Koninkrijk)
      (Activiteitsgroep over numerieke lineaire algebra in de Society for Industrial and Applied Mathematics )
   De GAMM-activiteitsgroep toegepaste en numerieke lineaire algebra
  
  Wiskunde