[WS] Lineare Ausgleichprobleme

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Lineare Ausgleichprobleme
Gliederung

  1. Wahl der Norm

  2. Normalengleichungen

    2a. Existenz einer Lösung

    2b. Eindeutigkeit für Rang(A)=n


  3. Lösen mit Cholesky-Zerlegung


  4. QR-Zerlegungen

    4a. Eindeutigkeit der reduzierten QR-Zerlegung

    4b. Lösen der Normalengleichung - red. QR

    4c. Lösen des Ausgleichsproblems - volle QR


  5. Gram-Schmidt-Orthogonalisierung

    5a. Berechnung der red. QR-Zerlegung

    5b. Existenz der red. QR-Zerlegung

    5c. Implementierung - Modifiziertes Gram-Schmidt Verfahren


  6. Householder Spiegelungen

    6a. Eigenschaften

    6b. Konstruktion von Q

    6c. Implementierung

    6d. Geometrische Deutung


  7. Givens-Rotationen

    7a. Eigenschaften

    7b. Konstruktion von Q

    7c. Implementierung

    7d. Geometrische Deutung


  8. Gauß'sches Ausgleichsverfahren (Methode der kleinsten Quadrate)

    8a. Lineare Modellfunktion

    8b. Allgemeiner Linearer Fall


tigerbine Auf diesen Beitrag antworten »
1. Wahl der Norm
Im Gegensatz zur Lösung von regulären Systemen werden hier Systeme der Art mit betrachtet. Im Allgemeinen wird es nun kein x* geben mit:




Man könnte nun aber nach einer approximativen Lösung suchen. Natürlich nicht nach irgendeiner, sondern nach derjenigen, die den Ausdruck



minimiert. Es werden hier häufig die folgenden Normen verwendet:









Dabei hängt die Lösung eines Ausgleichsproblems von der verwendeten Norm ab. Ein Beispiel (Vorgriff):

Gegeben seien die sieben Punktepaare (Messreihe):




Gesucht in nun eine konstante Funktion g, welche die Paare auf dem Intervall [0,1] am besten approximiert. Mit der Bezeichnung g(t):=c, sucht man also c derart, dass der Ausdruck:



möglichst klein wird. Das soll nun für obige 3 Normen geschehen.






  • Offensichtlicht lautet die Lösung dann





  • Dieser Ausdruck wird minimal, wenn der Term unter der Wurzel minimal wird. Mit der notwendigen und da quadratische Funktion hinreichenden Bedingung folgt dann





  • Somit lautet hier die Lösung



Interpretation

Der letzte Wert ist wohl ein Ausreißer der Messreihe. Bei der Ausgleichsrechnung mittels Norm spielt dieser wohl keiner Rolle, bei der Norm fließt er nur geringfügig ein. Den größten Einfluss hat er wohl bei der Norm.


Lehrer
Im weiteren soll die Norm verwendet werden, denn in der nun äquivalenten Formulierung:



liegt ein stetig differenzierbares Optimierungsproblem vor. Die beiden anderen Normen würden nicht differenzierbare Probleme liefern.
tigerbine Auf diesen Beitrag antworten »
2. Normalengleichungen
Hier soll ein zum Minimierungsproblem äquivalentes aufgezeigt werden.




Beweis:



Es gilt nun . Damit folgt auch die Gültigkeit von . Es ist nun:







Sei nun x* die Lösung des lin. Ausgleichsproblems. Angenommen x^* genüge nicht der den Normalengleichungen, dann gilt:




Mit der Defintion folgt dann :




Ist nun t hinreichend klein gewählt, so gilt:




Damit folgt dann:



Dann ist aber x^* nicht die Lösung des lin. Ausgleichsproblems.
tigerbine Auf diesen Beitrag antworten »
2a. Existenz einer Lösung
Die Normalengleichung kann man nun dazu verwenden, die folgende Aussage zu beweisen:




Beweis:

Die Behauptung ist äquivlatent zu . Es ergibt sich:



Es gilt nun . Beweis folgt im Anschluss an diesen. Somit gilt:




Und schließlich die entscheidende Folgergung:




Beweis (Bildräume):

Hierzu muss man sich mit orthogonalen Räumen beschäftigen und es sind weitere Aussagen nötig. Zunächst einmal die Logikkette:





Gleichheit 1 folgt durch Elementenvergleich.






Somit gilt - Damit folgt auch sofort


Nun zur zweiten Gleichheit. Es gilt:







Somit folgt dann auch die gesuchte Behauptung.
tigerbine Auf diesen Beitrag antworten »
2b. Eindeutigkeit für Rang(A)=n


(Hierauf werden die theoretischen Aussagen angewandt)




(Dieser Fall wird im WS - Beispiele betrachtet)
tigerbine Auf diesen Beitrag antworten »
3. Lösen mit Cholesky-Zerlegung
Im Falle Rang(A)=n könnte man nun die Normalengleichung aufgrund der SPD-Eigenschaft von z.B. mit dem Cholesky-Verfahren lösen.

I.A. wird man dies aufgrund der schlechten Kondition jedoch nicht tun.
 
 
tigerbine Auf diesen Beitrag antworten »
4. QR-Zerlegungen
Betrachtet wird nun der Fall , nach (2b) existiert dann also eine eindeutige Lösung des Linearen Ausgleichsproblems.

reduzierte QR-Zerlegung




volle QR-Zerlegung






Dabei sind die Spalten von orthonormiert und eine obere Dreiecksmatrix.
tigerbine Auf diesen Beitrag antworten »
4a. Eindeutigkeit der reduzierten QR-Zerlegung
Sollte nun eine reduzierte QR-Zerlegung exisitieren, so ist sie im Wesentlichen eindeutig. Betrachtet man also 2 reduzierte QR-Zerlegungen, so existiert eine Diagonalmatrix D (mit Werten +/- 1), so dass gilt:






Beweis:

Es nun nach Voraussetzung . Da nun die Spalten der Qs orthonormiert sind, gilt:




Damit erhält man dann aus der ersten Gleichheit:



und




Es sind nun die Rs regulär, sonst wäre Rang(A) <n, gilt:






Nun definiert man und weist nach, dass es sich um eine orthogonale Diagonalmatrix handelt.

Mit dem Wissen über Dreiecksmatrizen folgt, dass auch die Inversen obere Dreiecksmatrizen sind. Es ist also auch D eine obere Dreiecksmatrix und ihre Transponierte somit eine untere Dreiecksmatrix.Es gilt weiter:



Somit muss D eine Diagonalmatrix sein. Nun folgt weiter



Womit nun auch die Orthogonalität von d gezeigt wurde, d.h. die Diagonalwerte sind +/- 1.


Mit folgt dann die Behauptung.


Im folgenden wird die Existenz der red. QR-Zerlegung erst einmal angenommen. Der Beweis folgt hier.
tigerbine Auf diesen Beitrag antworten »
4b. Lösen der Normalengleichung - red. QR
Sei also Rang (A) = n und es existiere eine red. QR-Zerlegung. Dann folgt:




Wie kann man nun also die eindeutige Lösung x* bestimmen?

  1. Bestimme die red. QR-Zerlegung



  2. Löse durch Rückwärtssubstitution
tigerbine Auf diesen Beitrag antworten »
4c. Lösen des Ausgleichsproblems - volle QR












Da der zweite Summand eine Konstante ist folgt:




Dies wird offensichtlich für minimal und wir sind wieder bei der Lösung mittels reduzierten QR-Zerlegung aus (4b).


Lehrer
Für m = n können QR-Zerlegungen auch zur Lösung von Linearen Gleichungssystemen verwendet werden.


Wie man nun eine QR-Zerlegung bestimmt wird in den Abschnitten (5),(6),(7) gezeigt.
tigerbine Auf diesen Beitrag antworten »
5. Gram-Schmidt-Orthogonalisierung
Gesucht ist nun die red. QR-Zerlegung. Zunächst notiert man:



Lehrer Die Potenzen Kennzeichen hier die Spaltenvektoren

ausgeschrieben bedeutet das:












allgemein:




Damit erhält man nun eine Berechnungsvorschrift für die orthonormalen Vektoren "q" und die zugehörigen Koeffizienten "r". Für j=1 ergibt sich:



Da Q orthogonal ist, gilt





Um nun eine eindeutige Lösung zu erhalten, sollen die Diagonalelemente von R positiv sein. Weiter erhält man durch Umstellen zunächst:






Nun die Orthogonalitätsbedingung:












Allgemein ergibt sich dann:






tigerbine Auf diesen Beitrag antworten »
5a. Berechnung der red. QR-Zerlegung
Fasst man nun die obige Konstruktion in einem Algorithmus zusammen, so erhält man das

Gram-Schmidtsche Orthogonalisierungsverfahren

tigerbine Auf diesen Beitrag antworten »
5b. Existenz der red. QR-Zerlegung
Mit dieser Vorschrift (Gram-Schmidt-Verfahren) ist die Existenz einer red. QR-Zerlegung konstruktiv (fast) bewiesen worden. Es ist noch zu zeigen, dass das Verfahren wohldefiniert ist. Dies ist dann der Fall, wenn für die Nenner gilt .

Wäre nun für ein kleinstes , so folgt aus (*):




Dies steht aber im Widerspruch zu Rang(A) = n.
tigerbine Auf diesen Beitrag antworten »
5c. Implementierung - Modifiziertes Gram-Schmidt Verfahren
Das Verfahren ist jedoch numerisch instabil, da aufgrund der Rechengenauigkeit die Orthogonalität der Vektoren schnell verloren geht. Ein Rechenbeispiel findet sich dazu im WS - Beispiele.

Zunächst einmal führt man einen Hilfsvektor ein, um das Überschreiben der Vektoren im Algorithmus zu vermeiden (siehe auch Rechenbeispiel)




Ausgeschrieben lautet die Berechnung der nicht normierten Vektoren




Wegen der Orthogonalität der Vektoren q folgt (Beweis am Ende des Posts):




Daher kann man die Vektoren p auch wie folgt berechnen:




Es gilt dann:










Speichert man die Hilfsvektoren nicht explizit ab und überschriebt stattdessen einen Vektor mit den entsprechenden Einträgen, so erhält man das modifizierte Gram-Schmidt-Verfahren.









Beweis:

Ist durch Induktion zu führen. Wir verifizieren hier nur den Induktionsanfang. Für n=2 gilt, aufgrund der Orthogonalität der Vektoren








Somit ist der Anfang gemacht. Viel Spass beim Rest der Indize-Schlacht Augenzwinkern
tigerbine Auf diesen Beitrag antworten »
6. Householder Spiegelungen
Nun soll eine volle QR-Zerlegung bestimmt werden. Wieder hat A den Rang n. Es ist dann




Ähnlich dem Prinzip beim Gaußalgorithmus ist es nun das Ziel die Matrix zu konstruieren, so dass eine obere Dreiecksmatrix ist. Man schreibt:




Dabei annulliert die Eintrage der j-ten Spalte unterhalb der Diagonalen.
tigerbine Auf diesen Beitrag antworten »
6a. Eigenschaften
Householder-Spiegelung (Definition)




Konstruktion von u

x sei nun der Teil des Spaltenvektors von "A", den es zu annullieren gilt, zzgl. des Diagonalelements.









Eigenschaften der Matrix H

  • H ist symmetrisch, dies folgt direkt aus der Symmetrie von I und der Dyade.

  • H ist orthogonal, denn


  • u ist ein Eigenvektor von H, denn

    Der Eigenraum von (-1) ist eindimensional.

  • H hat sonst nur noch den Eigenwert 1. Die Dimension seines Eigenraums ist (n-1). Da H symmetrisch und regulär ist, gibt es eine ONB aus Eigenvektoren von H, so dass H bzgl. dieser Diagonalagestalt hat .Sei v ein zu u orthogonaler Vektor. Dann gilt:


  • H ist eine Spiegelung, denn


  • Hx ist ein Vielfaches des ersten Einheitsvektors mit dem Faktor

    Beweis:

    Die Vektoren x und u unterscheiden sich nur im ersten Eintrag, d.h. es gilt . So kann man Dyade wie folgt schreiben:



    Nun ist

    .


    Für den Nenner des Faktors ß gilt:



    Für den j-ten Eintrag des Vektors Ux gilt:



    Für j=1 gilt:






    Für j =2,...,n gilt:





    Somit ist Hx ein Vielfaches des ersten Einheitsvektors mit obigem Faktor.







tigerbine Auf diesen Beitrag antworten »
6b. Konstruktion von Q
Wie hängen nun die eingangs erwähnten Matrizen und die Matrizen H zusammen? Mit entsprechenden Dimensionen gilt:




Auch die Matrizen sind symmetrisch. Es gilt:




Ebenso sind sie orthogonal:




Und mit der Rechenregel für Blockdiagonalmatrizen folgt auch sofort:





Handelt es sich auch um eine Householder-Matrix? Dazu muss man nur einen Vektor finden mit:



Wählt man nun:



Dann ist:





Damit ergibt:



Somit sind die auch Householder-Matrizen.
tigerbine Auf diesen Beitrag antworten »
6c. Implementierung
Wie im Beispiel Workshop angemerkt, muss hier nicht die Matrix Q explizit berechnet werden. Desweiteren reicht es sogar aus, nur die zur Konstruktion benötigten Vektoren u abzuspeichern. Im folgenden wird die Matrix A mit diesen Überschrieben. Im oberen Dreieck wird die Matrix R gespeichert. Ihre Diagonale speichert man im Vektor p.

tigerbine Auf diesen Beitrag antworten »
6d. Geometrische Deutung
Wir hatten festgestellt, dass gilt:

Hx ist ein Vielfaches des ersten Einheitsvektors mit dem Faktor

Zitat:


Die Konstruktion von u mittels Signum hat numersische Gründe. Es soll hier

Zitat:


eine Auslöschung der ersten Komponente von u vermieden werden. Theoretisch hätte man jedoch 2 Möglichkeiten, denn Vektor x (In der Skizze mit v benannt) abzubilden.

Links



rechts




tigerbine Auf diesen Beitrag antworten »
7. Givens-Rotationen
Nun soll eine volle QR-Zerlegung bestimmt werden. Wieder hat A den Rang n. Es ist dann




Ähnlich dem Prinzip beim Gaußalgorithmus ist es nun das Ziel die Matrix zu konstruieren, so dass eine obere Dreiecksmatrix ist. Man schreibt:




Dabei annulliert den Eintrag an der Stelle (i,j).
tigerbine Auf diesen Beitrag antworten »
7a. Eigenschaften
Givens-Rotation (Definition)




Konstruktion von c und s







Eigenschaften der Matrix G

  • G ist offensichtlich schiefsymmetrisch

  • , denn

  • G ist orthogonal, denn








    Somit ist offensichtlich

  • G ist eine Drehung, denn mit dem Entwicklungssatz von Laplace und der Determinantenregel für Blockdiagonalmatrizen folgt (mit einer kleinen Fallunterscheidung)



  • G besitzt den Eigenwert 1 und der zugehörige Eigenraum hat die Dimension (n-2). Eigenvektoren sind die (n-2) entsprechenden Standardeinheitsvektoren.

  • Die restlichen 2 Eigenwerte sind die (meist) komplexen Nullstellen des Polynoms

  • annulliert , denn (j < i)


tigerbine Auf diesen Beitrag antworten »
7b. Konstruktion von Q
Da die Menge der Drehungen eine Gruppe, die spezielle Orthogonale Gruppe bildet, ist auch Q eine Drehung. Eine Givens-Rotation wird Q i.A. jedoch nicht mehr sein.
tigerbine Auf diesen Beitrag antworten »
7c. Implementierung
tigerbine Auf diesen Beitrag antworten »
7d. Geometrische Deutung
Die Wahl der Variablen c und s erklärt sich mit der folgenden Skizze. Der Vekotr v wird in der durch die Einheitsvektoren aufgespannten Ebene um dem Winkel gedreht. Dabei gilt:



tigerbine Auf diesen Beitrag antworten »
8. Gauß'sches Ausgleichsverfahren (Methode der kleinsten Quadrate)
Hier möchte ich auf den Wikipedia Artikel verweisen:

http://de.wikipedia.org/wiki/Methode_der_kleinsten_Quadrate


Ähnlich wie im Workshop "Polynominterpolation" ist hier en Datengitter gegeben. Z.B. aus einer Messreihe.

jedoch sucht man nun nicht eine interpolierende Funktion (je mehr Knoten desto höher der Grad der Funktion), sondern eine Modellfunktion best. Gestalt soll so durch die Datenwolke gelegt werden, dass die Quadratsumme der senkrechten Abweichungen:



minimiert wird.

Dabei wirs je nach zugrunde liegendem Problem unterschiedlich bestimmt. Allgemein formuliert sich das Minimierungsproblem wie folgt:




Dies ist äquivalent zu Minimierung der euklidischen Norm des Differenzenvektors:

tigerbine Auf diesen Beitrag antworten »
8a. Lineare Modellfunktion
Machen wir uns einmal die erwähnte Äquivlanz bewußt. Gesucht ist eine lineare Modellfunktion . Das Optimierungsproblem lautet nun:



Vergleiche den Wikipedia Link für die in diesem Fall direkte Berechnung des Lösungsvekotrs x.
tigerbine Auf diesen Beitrag antworten »
8b. Allgemeiner Linearer Fall
Hängt die Modellfunktion von mehreren Variablen ab, so ergibt sich :



Das hieraus resultierende LGS führt zu der Darstellung:



Dies ist nun ein Problem, dessen Lösbarkeit wir bereits hier am Anfang besprochen haben. Lösungsverfahren sind das Normalengleichungsverfahren (Beachte! die Kondition der Matrizen) oder die QR-Zerlegung.
tigerbine Auf diesen Beitrag antworten »
Ausblick
[Workshop - Lineare Ausgleichsprobleme - Beispiele]
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »