Der RLS Algorithmus Recursive Least Squares Algorithmus basiert auf der Methode der kleinsten Quadrate Er wird zur Losung uberbestimmter linearer Gleichungssysteme und insbesondere zur Schatzung von Modellparametern bei der Identifikation linearer Systeme oder in der Neuroinformatik genutzt Die Rekursivitat erlaubt die Online Nutzung mit aktuell anfallenden Daten bei gleichbleibender Komplexitat in jedem Rekursionsschritt Inhaltsverzeichnis 1 Herleitung 1 1 Rekursion 1 2 Vergessensfaktor 1 3 Anwendung 2 Beispiel 3 LiteraturHerleitung BearbeitenDie Basis fur den rekursiven Algorithmus ist zunachst das formale quadratische Minimierungsproblem Im Beispiel der Systemidentifikation liegen Paare aus Ein und Ausgangsdaten in der Matrix X displaystyle mathbf X nbsp vor deren Zusammenhang durch ein lineares Modell mit den zu schatzenden Parametern 8 displaystyle underline hat Theta nbsp abgebildet werden soll Mit den zusatzlich im Vektor y displaystyle underline y nbsp vorliegenden gemessenen Ausgangswerten lasst sich das System beschreiben durch y X 8 displaystyle underline y mathbf X cdot underline hat Theta nbsp Das entsprechende Optimierungsproblem formuliert sich zu min 8 f 8 min 8 1 2 y X 8 2 min 8 1 2 y X 8 T y X 8 displaystyle underset underline hat Theta min f underline hat Theta underset underline hat Theta min frac 1 2 underline y mathbf X cdot underline hat Theta 2 underset underline hat Theta min left frac 1 2 left underline y mathbf X cdot underline hat Theta right T left underline y mathbf X cdot underline hat Theta right right nbsp Es soll das Quadrat der Differenz aus Mess und Modelldaten minimiert werden Dieses Vorgehen hat den Vorteil dass eine quadratische Funktion genau ein globales Extremum in ihrem Scheitelpunkt besitzt An dieser Stelle wird die erste Ableitung zu Null was zur Losung des Minimierungsproblems fuhrt f 8 8 X T y X 8 0 displaystyle frac partial f underline hat Theta partial underline hat Theta mathbf X T cdot left underline y mathbf X cdot underline hat Theta right overset 0 nbsp Umstellen liefert den gesuchten Parametervektor 8 X T X 1 X T y displaystyle underline hat Theta left mathbf X T cdot mathbf X right 1 cdot mathbf X T cdot underline y nbsp Zur Losung muss die Anzahl der Datenpaare mindestens der Anzahl der gesuchten Parameter entsprechen Je mehr Datenpaare vorliegen desto mehr Eintrage hat die Matrix X displaystyle mathbf X nbsp und desto schwieriger gestaltet sich die Berechnung Rekursion Bearbeiten Beim Ubergang zur rekursiven Berechnung bleibt auch bei Hinzukommen neuer Daten in jedem Schritt der Rechenaufwand gleich da das vorherige Ergebnis als Ausgangspunkt genutzt wird und so nur je ein neues Datenpaar in die Kalkulation involviert ist Im Rekursionsschritt k displaystyle k nbsp wobei k displaystyle k nbsp mindestens der Anzahl der Parameter entspricht ist das zu losende Gleichungssystem y k X k 8 k displaystyle underline y k mathbf X k cdot underline hat Theta k nbsp mit der zugehorigen Losung fur den Parametervektor 8 k displaystyle underline hat Theta k nbsp 8 k X T k X k 1 X T k y k displaystyle underline hat Theta k left mathbf X T k cdot mathbf X k right 1 cdot mathbf X T k cdot underline y k nbsp Fur k 1 displaystyle k 1 nbsp erweitert sich das Gleichungssystem zu y k 1 X k 1 8 k 1 displaystyle underline y k 1 mathbf X k 1 cdot underline hat Theta k 1 nbsp und fur die Losung gilt entsprechend 8 k 1 X T k 1 X k 1 1 X T k 1 y k 1 displaystyle underline hat Theta k 1 left mathbf X T k 1 cdot mathbf X k 1 right 1 cdot mathbf X T k 1 cdot y k 1 nbsp Die Daten im Schritt k 1 displaystyle k 1 nbsp lassen sich in bereits vorliegende und neu hinzugekommene Daten folgendermassen aufteilen y k 1 y k y k 1 X k 1 X k x T k 1 displaystyle underline y k 1 begin bmatrix underline y k y k 1 end bmatrix qquad mathbf X k 1 begin bmatrix mathbf X k underline x T k 1 end bmatrix nbsp Einsetzen in die Gleichung fur den Parametervektor liefert 8 k 1 X T k x k 1 X k x T k 1 1 X T k x k 1 y k y k 1 displaystyle underline hat Theta k 1 left begin bmatrix mathbf X T k amp underline x k 1 end bmatrix cdot begin bmatrix mathbf X k underline x T k 1 end bmatrix right 1 cdot begin bmatrix mathbf X T k amp underline x k 1 end bmatrix cdot begin bmatrix underline y k y k 1 end bmatrix nbsp Der Ausdruck lasst sich noch weiter ordnen zu 8 k 1 X T k X k x k 1 x T k 1 1 X T k X k 8 k x k 1 y k 1 displaystyle underline hat Theta k 1 left mathbf X T k cdot mathbf X k underline x k 1 cdot underline x T k 1 right 1 cdot left mathbf X T k cdot mathbf X k cdot underline hat Theta k underline x k 1 cdot y k 1 right nbsp Mit der Abkurzung P 1 X T k X k displaystyle mathbf P 1 mathbf X T k cdot mathbf X k nbsp und der Nutzung des Lemmas zur Matrixinversion ergibt sich die Rekursionsgleichung zu 8 k 1 P k P k x k 1 x T k 1 P k 1 x T k 1 P k x k 1 P 1 k 8 k x k 1 y k 1 displaystyle underline hat Theta k 1 left mathbf P k frac mathbf P k cdot underline x k 1 cdot underline x T k 1 cdot mathbf P k 1 underline x T k 1 cdot mathbf P k cdot underline x k 1 right cdot left mathbf P 1 k cdot underline hat Theta k underline x k 1 cdot y k 1 right nbsp Vereinfacht 8 k 1 8 k P k x k 1 1 x T k 1 P k x k 1 Verstarkungsterm g k y k 1 x T k 1 8 k Korrekturterm displaystyle underline hat Theta k 1 underline hat Theta k underbrace frac mathbf P k cdot underline x k 1 1 underline x T k 1 cdot mathbf P k cdot underline x k 1 text Verstarkungsterm underline gamma k cdot underbrace left y k 1 underline x T k 1 cdot underline hat Theta k right text Korrekturterm nbsp Die Aktualisierung der Matrix P displaystyle mathbf P nbsp kann ebenfalls rekursiv erfolgen P k 1 P k g k x T k 1 P k displaystyle mathbf P k 1 mathbf P k underline gamma k cdot underline x T k 1 cdot mathbf P k nbsp Im Vergleich zum nichtrekursiven Algorithmus ist ersichtlich dass keine Inversion der Matrix X T X displaystyle left mathbf X T cdot mathbf X right nbsp mehr notwendig ist sondern lediglich eine Division durch ein Skalar Vergessensfaktor Bearbeiten Durch die Einfuhrung eines Vergessensfaktors l lt 1 displaystyle lambda lt 1 nbsp verlieren die historischen Messdaten fur die Optimierung an Bedeutung und die aktuellen werden starker gewichtet Dies ist sinnvoll um Arbeitspunktwechsel Storungen oder Invarianzen des zu modellierenden Systems auszugleichen Ublicherweise wird Lambda im Bereich 0 95 lt l lt 1 displaystyle 0 95 lt lambda lt 1 nbsp gewahlt 8 k 1 8 k P k x k 1 l x T k 1 P k x k 1 Verstarkungsterm g k y k 1 x T k 1 8 k Korrekturterm displaystyle underline hat Theta k 1 underline hat Theta k underbrace frac mathbf P k cdot underline x k 1 lambda underline x T k 1 cdot mathbf P k cdot underline x k 1 text Verstarkungsterm underline gamma k cdot underbrace left y k 1 underline x T k 1 cdot underline hat Theta k right text Korrekturterm nbsp P k 1 1 l P k g k x T k 1 P k displaystyle mathbf P k 1 frac 1 lambda cdot left mathbf P k underline gamma k cdot underline x T k 1 cdot mathbf P k right nbsp Anwendung Bearbeiten Der RLS Algorithmus benotigt fur ein gutes Ergebnis maximal so viele Rekursionsschritte wie Parameter identifiziert werden sollen Diese Schnelligkeit und seine einfache Berechenbarkeit ermoglichen vielfaltige Online Anwendungsmoglichkeiten zur Systemidentifikation oder als adaptives Filter auch auf weniger potenten Mikroprozessorsystemen Zu Beginn der Rekursion mussen sowohl 8 displaystyle underline hat Theta nbsp als auch P displaystyle mathbf P nbsp initialisiert werden Liegen a priori Informationen zu den Parametern vor so konnen diese hier verwendet werden ansonsten werden die Parameter zu Null gesetzt Fur die Matrix P displaystyle mathbf P nbsp eignet sich in der Regel eine Initialisierung als Diagonalmatrix mit Werten grosser 100 Hohe Werte bedeuten geringes Vertrauen in die Parameter was zu starkeren Parameterkorrekturen fuhrt die anfanglich durchaus erwunscht sind Damit das Verfahren stabil bleibt muss die Matrix P displaystyle mathbf P nbsp positiv definit bleiben Durch numerische Ungenauigkeiten wahrend der Berechnung konnen jedoch negative Eigenwerte entstehen Deshalb wurden Implementierungen des RLS Algorithmus entwickelt die sich als numerisch stabiler erweisen was z B durch die Einbindung einer QR Zerlegung erreicht werden kann Allerdings steigt hierbei der Rechenaufwand Beispiel BearbeitenFur ein zu identifizierendes System wurde ein PT2 System als Modellfunktion gewahlt dessen zeitdiskrete Realisierung in Form der folgenden Rekursionsgleichung vorliegt y k a 1 y k 1 a 2 y k 2 a 3 u k 1 a 4 u k 2 displaystyle hat y k a 1 cdot hat y k 1 a 2 cdot hat y k 2 a 3 cdot u k 1 a 4 cdot u k 2 nbsp Mit der Zusammenfassung von Modellein und ausgang zu h T y k 1 y k 2 u k 1 u k 2 displaystyle underline h T begin bmatrix hat y k 1 amp hat y k 2 amp u k 1 amp u k 2 end bmatrix nbsp und dem Parametervektor 8 T a 1 a 2 a 3 a 4 displaystyle underline hat Theta T begin bmatrix a 1 amp a 2 amp a 3 amp a 4 end bmatrix nbsp folgt die matrizielle Schreibweise y k h T 8 displaystyle hat y k underline h T cdot underline hat Theta nbsp Fur den gewahlten Modellansatz ergibt sich nun folgende Realisierung des RLS Algorithmus 8 k 1 8 k P k h k 1 l h T k 1 P k h k 1 y k 1 h T k 1 8 k displaystyle underline hat Theta k 1 underline hat Theta k frac mathbf P k cdot underline h k 1 lambda underline h T k 1 cdot mathbf P k cdot underline h k 1 cdot left y k 1 underline h T k 1 cdot underline hat Theta k right nbsp P k 1 1 l P k g k h T k 1 P k displaystyle mathbf P k 1 frac 1 lambda cdot left mathbf P k underline gamma k cdot underline h T k 1 cdot mathbf P k right nbsp Literatur BearbeitenDierk Schroder Intelligente Verfahren Springer Verlag Berlin Heidelberg 2010 ISBN 978 3 642 11397 0 Martin Werner Digitale Signalverarbeitung mit MATLAB Praktikum Vieweg amp Sohn Verlag Wiesbaden 2008 ISBN 978 3 8348 0393 1 Abgerufen von https de wikipedia org w index php title RLS Algorithmus amp oldid 212463476
