QRalgoritme

Het QR-algoritme is een numerieke methode voor het berekenen van de eigenwaarden (en vaak ook de eigenvectoren) van een vierkante matrix A. Het neemt A als uitgangspunt en voert een reeks QR-transformaties uit die A geleidelijk aan transformeren tot een vorm waarin de eigenwaarden op de diagonaal staan.

In elke iteratie wordt een QR-decompositie uitgevoerd. Voor een verschuiving μ_k wordt A_k − μ_k I gefactoriseerd als Q_k R_k, waarbij Q_k orthogonaal is en R_k reektangulair. Vervolgens wordt A_{k+1} = R_k Q_k + μ_k I. Een alternatief zonder verschuiving is A_{k+1} = Q_k^T A_k Q_k. In beide gevallen is A_{k+1} gelijkwaardig aan A_k via een orthogonale overeenkomst, en hebben ze dezelfde eigenwaarden.

Het doel is dat na veel iteraties de elementen buiten de hoofddiagonaal afnemen en A_k convergeert naar een vorm waarin de diagonaal de eigenwaarden benadert. Voor reële matrices eindigt dit meestal in een driehoekige of quasi-driehoekige vorm (real Schur-form), waarbij complexe eigenwaardeparen worden weergegeven door 2x2-blokken. Voor symmetrische matrices convergeert het algoritme naar een diagonale matrix met echte eigenwaarden. Bij niet-symmetrische matrices wordt meestal eerst A gereduceerd tot upper Hessenberg-form om rekenkosten te beperken; voor veel toepassingen geldt ook de verschuivingsvariant (bijv. Wilkinson-verschuiving) om de convergentie te versnellen.

Toepassingen bevinden zich in wetenschappelijke berekeningen, technologie en engineering waar de eigenwaarden van grote matrices nodig zijn. Het QR-algoritme is wijdverbreid geïmplementeerd in lineaire-algebra packages zoals LAPACK.