Ausgleichungsrechnung I Gerhard Navratil Ausgleichung ohne Linearisierung Problematik Lösen linearer, nicht überbestimmter Gleichungssysteme Lösen nicht

Embed Size (px)

Text of Ausgleichungsrechnung I Gerhard Navratil Ausgleichung ohne Linearisierung Problematik Lösen...

  • Folie 1
  • Ausgleichungsrechnung I Gerhard Navratil Ausgleichung ohne Linearisierung Problematik Lsen linearer, nicht berbestimmter Gleichungssysteme Lsen nicht linearer, nicht berbestimmter Gleichungssysteme Lsen nicht linearer, berbestimmter Gleichungssysteme
  • Folie 2
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: Tachymeter Zeiss Elta 2 Modell fr Fehler- korrektur: Sinusschwingung Vergleich mit Laser-Interferometer Messstelle d [m]Differenz c [mm] 2,0352,8 4,042-1,6 5,998-7,5 7,973-7,1 10,002 -0,7
  • Folie 3
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: Fortsetzung Nherungswerte: Gesucht: Wahrscheinlichste Werte der Parameter a 0 bis a 3 und ausgeglichene Beobachtungen d i bzw. c i
  • Folie 4
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: Lsung (1) Fehlender Nherungswert: Erstes Wertepaar: Fehlermeldung, da Ausdruck bei arcsin >1 2. Wertpaar verwendet: a 3 =3,6
  • Folie 5
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: Lsung (2) Ableitungen der Bedingungsgleichungen:
  • Folie 6
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: Lsung (3) B -Matrix: Ableitungen nach c und d A -Matrix: Ableitungen nach a 0 bis a 3 Widerspruchsvektor w Gewichtsmatrix Einheitsmatrix Gleichungssystem
  • Folie 7
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: Lsung (4) Auflsung liefert Unbekanntenzuschlge x und Verbesserungen v Hauptprobe: Geht nicht auf! Iteration notwendig
  • Folie 8
  • Ausgleichungsrechnung I Gerhard Navratil Einfach lsbar weil Einfache, geschlossen Berechnung der Nherungswerte Wie geht man vor, wenn keiner der vier Nherungswerte gegeben ist? Konvergierende Iteration
  • Folie 9
  • Ausgleichungsrechnung I Gerhard Navratil Lsen nicht berbestimmter Gleichungssysteme Gegeben: Gesucht: Lsung des Systems (gemein- same Nullstellen der Polynome) Lsung: Diagonalfom: Lsung direkt ablesbar!
  • Folie 10
  • Ausgleichungsrechnung I Gerhard Navratil Lsen nicht berbestimmter, nicht linearer Gleichungssysteme Gegeben: 2 Festpunkte, 2 Strecken zu Neupunkt Gesucht: Koordinaten des Neupunktes yx P155 P2155 vonnachs P1N8 P2N6
  • Folie 11
  • Ausgleichungsrechnung I Gerhard Navratil Lsung (1) Funktionaler Zusammenhang: Ausmultipliziert: mit den Unbekannten x N und y N
  • Folie 12
  • Ausgleichungsrechnung I Gerhard Navratil Lsung (2) Einsetzen der bekannten Werte Keine nette Form der Darstellung (Lsung nicht direkt ablesbar) Lsung direkt ablesbar aus (ohne Beweis):
  • Folie 13
  • Ausgleichungsrechnung I Gerhard Navratil Lsung (3) Gesuchte Lsung des Systems ist: Lsung der Aufgabe: yx Lsg 111,40,2 Lsg 211,49,8 Frage: Wie sind wir auf das nette Gleichungssystem gekommen? Grbner-Basis
  • Folie 14
  • Ausgleichungsrechnung I Gerhard Navratil Grbner-Basis Entwickelt von Buchberger in den 60er- Jahren des 20. Jahrhunderts Gegeben: System F von Polynomen Gesucht: Nullstellen von F F in System G transformiert, das nettere Eigenschaften hat F und G sind quivalent Lsung von G ist auch Lsung on F
  • Folie 15
  • Ausgleichungsrechnung I Gerhard Navratil Begriffe Multivariate Polynome: Polynom in mehreren Variablen Kombinationen von Variablen sind erlaubt (z.B. xy ) Bivariate Polynome: 2 Variable
  • Folie 16
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel Gegeben sind: bivariate Polynome System von Polynomen
  • Folie 17
  • Ausgleichungsrechnung I Gerhard Navratil Monomen Summanden: Monome Wichtigste Arten der Sortierung: Nach dem Lexikon (lexikographisch) Erst nach der Potenz, dann lexikographisch Im Beispiel: lexikographisch (erst nach y, dann nach x, dann absteigende Potenz) Erstes Monom: Fhrendes Monom
  • Folie 18
  • Ausgleichungsrechnung I Gerhard Navratil Division/Reduktion (1) Einzelne Monome von g werden mit Hilfe von f 1 und f 2 eliminiert Mgliche Division: Reduziert g modulo f 1 Das fhrende Monom von (3y)f 1 muss eines der Monome von g eliminieren Mathematisch: ( g reduziert sich zu h modulo f 1 )
  • Folie 19
  • Ausgleichungsrechnung I Gerhard Navratil Division/Reduktion (2) Im Allgemeinen viele verschiedene Reduktionen mglich In unserem Beispiel: Somit: und.
  • Folie 20
  • Ausgleichungsrechnung I Gerhard Navratil Division/Reduktion (3) bedeutet, dass sich g ber die Funktionen aus F zu h reduzieren lsst Reduktion ber eine endliche Anzahl von Schritten: Wenn nicht mehr weiter reduzierbar:
  • Folie 21
  • Ausgleichungsrechnung I Gerhard Navratil Eigenschaften der Reduktion Terminierung es gibt keine unendliche Kette von Reduktionsschritten Reduktion ist algorithmisch fr alle g und F gibt es einen Algorithmus, der eine reduzierte Form erzeugt Nicht-Eindeutigkeit aus g und F knnen unterschiedliche Ergebnisse h und k erzeugt werden:
  • Folie 22
  • Ausgleichungsrechnung I Gerhard Navratil Grbner-Basis Set von Polynomen mit eindeutiger Reduktion Definition: F ist eine Gbner-Basis F ist eindeutig, also
  • Folie 23
  • Ausgleichungsrechnung I Gerhard Navratil S-Polynom Gegeben 2 Polynome Mit einem solchen Monom multipliziert, sodass die fhrenden Monome gleich sind S-Polynom ist die Differenz der beiden Polynome
  • Folie 24
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: S-Polynom Gegeben: Gesucht: S-Polynom Ergebnis:
  • Folie 25
  • Ausgleichungsrechnung I Gerhard Navratil Bestimmung Grbner-Basis Gegeben: Beliebige Menge F von Polynomen Gesucht: Menge G von Polynomen, die eine Grbner-Basis bilden Berechnung: Buchberger-Algorithmus
  • Folie 26
  • Ausgleichungsrechnung I Gerhard Navratil Buchberger-Algorithmus (1) Setze G=F Fr jedes Paar von Polynomen f 1 und f 2 G : S[f 1,f 2 ] berechnen und zur reduzierten Form h vereinfachen Wenn h = 0 dann nchstes Paar Wenn h 0 dann zu G hinzufgen und iterieren
  • Folie 27
  • Ausgleichungsrechnung I Gerhard Navratil Buchberger-Algorithmus (2) Lineare Polynome: Ergebnis entspricht der Gauschen Elminiation Verallgemeinerung der Gauschen Elimination Nhere Beschreibung: Dissertation Bruno Buchberger: http://www.risc.uni-linz.ac.at/people/buchberg/ Berechnung: Software-Pakete
  • Folie 28
  • Ausgleichungsrechnung I Gerhard Navratil Was knnen wir jetzt? Lsen von linearen Gleichungssystemen: z.B. Gausche Elimination Lsen von nicht linearen Gleichungs- systemen: Grbner-Basis Lsen von berbestimmten, linearen Gleichungssystemen: Methode der kleinsten Quadrate
  • Folie 29
  • Ausgleichungsrechnung I Gerhard Navratil Lsen berbestimmter, nicht linearer Gleichungssysteme Direkte Anwendung der Grbner-Basis nicht mglich Lsung von Awange und Grafarend: Bestimmung der eindeutigen Lsungen ber Grbner-Basis Lsungen als Beobachtungen betrachten und Genauigkeit ber Fehlerfortpflanzung Lsung nach Ausgleichung direkter Beobachtungen
  • Folie 30
  • Ausgleichungsrechnung I Gerhard Navratil Vorteile dieser Lsung Keine Linearisierung Somit keine Nherungswerte notwendig Keine Iteration ntig Fr Detektion grober Fehler verwendbar (A 2)
  • Folie 31
  • Ausgleichungsrechnung I Gerhard Navratil Beispiel: berbestimmter Bogenschnitt Bogenschnitt von 3 Punkten 3 eindeutige Lsungen N12, N13, N23 Zufllige Fehler bewirken Abweichungen Vorschlag von Gau: Eindeutige Lsung ber gewichtetes arithmetisches Mittel, Gewichte aus Distanzen Jacobi: Gewichte aus Determinanten der Lsungen
  • Folie 32
  • Ausgleichungsrechnung I Gerhard Navratil Kombinationsansatz (1) Lineares Problem: Aus je 2 Gleichungen eine Lsung: Lsungen
  • Folie 33
  • Ausgleichungsrechnung I Gerhard Navratil Kombinationsansatz (2) Gewichtetes arithmetisches Mittel Gewichte aus
  • Folie 34
  • Ausgleichungsrechnung I Gerhard Navratil Kombinationsansatz (3) Nicht lineares Problem: Gewichte ber Fehlerfortpflanzung abzuleiten Liefert Varianz-Kovarianzmatrix Ausgleichung direkter Beobachtungen
  • Folie 35
  • Ausgleichungsrechnung I Gerhard Navratil Zusammenfassung Notwendige Linearisierung bei Ausgleichs- problemen kann zu Schwierigkeiten fhren Grbner-Basis ermglicht Lsung ohne Linearisierung (also auch ohne Nherungswerte) Vorteile: Rechenaufwand abschtzbar, Wiederholung einfach Nachteil: Mathematisch aufwndiger