Ausgleichungsrechnung IGerhard Navratil

Ausgleichung ohne Linearisierung

• Problematik

• Lösen linearer, nicht überbestimmter Gleichungssysteme

• Lösen nicht linearer, nicht überbestimmter Gleichungssysteme

• Lösen nicht linearer, überbestimmter Gleichungssysteme

Ausgleichungsrechnung IGerhard Navratil

Beispiel: Tachymeter Zeiss Elta 2

Modell für Fehler-korrektur:Sinusschwingung

Vergleich mitLaser-Interferometer

Messstelle d [m] Differenz c [mm]

2,035 2,8

4,042 -1,6

5,998 -7,5

7,973 -7,1

10,002 -0,7

3210 ][

2sin][][ amd

Uamdaammc

Ausgleichungsrechnung IGerhard Navratil

Beispiel: Fortsetzung

Näherungswerte:

Gesucht: Wahrscheinlichste Werte der Parameter a0 bis a3 und ausgeglichene Beobachtungen di bzw. ci

mmam

mmamma 6,5,0,3 0

201

00

Ausgleichungsrechnung IGerhard Navratil

Beispiel: Lösung (1)

Fehlender Näherungswert:

Erstes Wertepaar: Fehlermeldung, da Ausdruck bei arcsin >1 2. Wertpaar verwendet: a3=3,6

2

103 arcsin

2 a

daacUda

Ausgleichungsrechnung IGerhard Navratil

Beispiel: Lösung (2)

Ableitungen der Bedingungsgleichungen:

U

adU

aa

adUa

da

a

c

Uad

Uaa

d

22cos

2sin

1

1

22cos

323

32

1

0

321

Ausgleichungsrechnung IGerhard Navratil

Beispiel: Lösung (3)

B-Matrix: Ableitungen nach c und d

A-Matrix: Ableitungen nach a0 bis a3

Widerspruchsvektor w

Gewichtsmatrix Einheitsmatrix

Gleichungssystem

0

w

x

k

0A

ABBT

T

Ausgleichungsrechnung IGerhard Navratil

Beispiel: Lösung (4)

Auflösung liefert Unbekanntenzuschläge x und Verbesserungen v

Hauptprobe:

Geht nicht auf!

Iteration notwendig

7,2,

4,4,

1,0,

3,4,

9,2,

5

4

3

2

1

lx

lx

lx

lx

lx

Ausgleichungsrechnung IGerhard Navratil

Einfach lösbar weil …

Einfache, geschlossen Berechnung der NäherungswerteWie geht man vor, wenn keiner der vier Näherungswerte gegeben ist?

Konvergierende Iteration

Ausgleichungsrechnung IGerhard Navratil

Lösen nicht überbestimmter Gleichungssysteme

Gegeben:

Gesucht: Lösung des Systems (gemein-same Nullstellen der Polynome)

Lösung:

Diagonalfom:

0

0132

yx

yx

0

1

11

32

y

x

1

1

10

01

y

x Lösung direktablesbar!

Ausgleichungsrechnung IGerhard Navratil

Lösen nicht überbestimmter, nicht linearer Gleichungssysteme

Gegeben: 2 Festpunkte,2 Strecken zu Neupunkt

Gesucht: Koordinatendes Neupunktes

y x

P1 5 5

P2 15 5

von nach s

P1 N 8

P2 N 6

Ausgleichungsrechnung IGerhard Navratil

Lösung (1)

Funktionaler Zusammenhang:

Ausmultipliziert:

mit den Unbekannten xN und yN

0

02

22

22

2

21

21

21

NNN

NNN

yyxxs

yyxxs

022

02222

22

2222

22

21

21

2111

22

xxsyyxxyx

xxsyyxxyx

NNNNN

NNNNN

Ausgleichungsrechnung IGerhard Navratil

Lösung (2)

Einsetzen der bekannten Werte

Keine ‚nette‘ Form der Darstellung (Lösung nicht direkt ablesbar)

Lösung direkt ablesbar aus (ohne Beweis):

02143010

014101022

22

NNNN

NNNN

yxyx

yxyx

05

57014101022

N

NNNN

y

yxyx

Ausgleichungsrechnung IGerhard Navratil

Lösung (3)

Gesuchte Lösung des Systems ist:

Lösung der Aufgabe:

8,92,005

4910

5

57

2,1,2

NNNN

N

xxxx

y

y x

Lsg 1 11,4 0,2

Lsg 2 11,4 9,8

Frage: Wie sind wirauf das ‚nette‘Gleichungssystemgekommen?Gröbner-Basis

Ausgleichungsrechnung IGerhard Navratil

Gröbner-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 Lösung von G ist auch Lösung on F

Ausgleichungsrechnung IGerhard Navratil

Begriffe

• Multivariate Polynome: Polynom in mehreren Variablen – Kombinationen von Variablen sind erlaubt (z.B. xy)

• Bivariate Polynome: 2 Variable

Ausgleichungsrechnung IGerhard Navratil

Beispiel

Gegeben sind:bivariate Polynome

System von Polynomen 21

222

1

232

,

2

2

53

ffF

xyf

yxyf

xxyyxg

Ausgleichungsrechnung IGerhard 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: Führendes Monom

Ausgleichungsrechnung IGerhard Navratil

Division/Reduktion (1)

Einzelne Monome von g werden mit Hilfe von f1 und f2 eliminiert

Mögliche Division:Reduziert g modulo f1

Das führende Monom von (3y)f1 muss eines der Monome von g eliminieren

Mathematisch:(„g reduziert sich zu h modulo f1“)

3221 653 yxyxfygh

hg f1

Ausgleichungsrechnung IGerhard Navratil

Division/Reduktion (2)

Im Allgemeinen viele verschiedene Reduktionen möglich

In unserem Beispiel:

Somit: und .

2

4

22

3

321

22

32

52

1

235

xyyx

xfyxgh

xyxyxfxygh

21hg f 32

hg f

Ausgleichungsrechnung IGerhard Navratil

Division/Reduktion (3)

bedeutet, dass sich g über die Funktionen aus F zu h reduzieren lässt

Reduktion über eine endliche Anzahl von Schritten:

Wenn nicht mehr weiter reduzierbar:

hg F

hg F*

Fh

Ausgleichungsrechnung IGerhard Navratil

Eigenschaften der Reduktion

Terminierung – es gibt keine unendliche Kette von Reduktionsschritten

Reduktion ist algorithmisch – für alle g und F gibt es einen Algorithmus, der eine reduzierte Form erzeugt

Nicht-Eindeutigkeit – aus g und F können unterschiedliche Ergebnisse h und k erzeugt werden:

FFFF kgh **

Ausgleichungsrechnung IGerhard Navratil

Gröbner-Basis

Set von Polynomen mit eindeutiger Reduktion

Definition:

F ist eine Göbner-Basis F ist eindeutig, also

khkghkhg FFFF **,,

Ausgleichungsrechnung IGerhard Navratil

S-Polynom

Gegeben 2 Polynome

Mit einem solchen Monom multipliziert, sodass die führenden Monome gleich sind

S-Polynom ist die Differenz der beiden Polynome

Ausgleichungsrechnung IGerhard Navratil

Beispiel: S-Polynom

Gegeben:

Gesucht: S-Polynom

Ergebnis:

222

1

2

2

xyf

yxyf

2121 2

1, fxfyffS

2321 2

2

1, yxffS

Ausgleichungsrechnung IGerhard Navratil

Bestimmung Gröbner-Basis

Gegeben: Beliebige Menge F von Polynomen

Gesucht: Menge G von Polynomen, die eine Gröbner-Basis bilden

Berechnung: Buchberger-Algorithmus

Ausgleichungsrechnung IGerhard Navratil

Buchberger-Algorithmus (1)

Setze G=F

Für jedes Paar von Polynomen f1 und f2 G:

– S[f1,f2] berechnen und zur reduzierten Form h vereinfachen

– Wenn h = 0 dann nächstes Paar– Wenn h ≠ 0 dann zu G hinzufügen und

iterieren

Ausgleichungsrechnung IGerhard Navratil

Buchberger-Algorithmus (2)

Lineare Polynome: Ergebnis entspricht der Gauß‘schen Elminiation Verallgemeinerung der Gauß‘schen Elimination

Nähere Beschreibung: Dissertation Bruno Buchberger:http://www.risc.uni-linz.ac.at/people/buchberg/

Berechnung: Software-Pakete

Ausgleichungsrechnung IGerhard Navratil

Was können wir jetzt?

• Lösen von linearen Gleichungssystemen: z.B. Gauß‘sche Elimination

• Lösen von nicht linearen Gleichungs-systemen: Gröbner-Basis

• Lösen von überbestimmten, linearen Gleichungssystemen: Methode der kleinsten Quadrate

Ausgleichungsrechnung IGerhard Navratil

Lösen überbestimmter, nicht linearer Gleichungssysteme

Direkte Anwendung der Gröbner-Basis nicht möglich

Lösung von Awange und Grafarend:– Bestimmung der eindeutigen Lösungen über

Gröbner-Basis– Lösungen als Beobachtungen betrachten und

Genauigkeit über Fehlerfortpflanzung– Lösung nach Ausgleichung direkter

Beobachtungen

Ausgleichungsrechnung IGerhard Navratil

Vorteile dieser Lösung

• Keine LinearisierungSomit keine Näherungswerte notwendig

• Keine Iteration nötig

• Für Detektion grober Fehler verwendbar (A 2)

Ausgleichungsrechnung IGerhard Navratil

Beispiel: Überbestimmter Bogenschnitt

Bogenschnitt von 3 Punkten 3 eindeutige Lösungen N12, N13, N23

Zufällige Fehler bewirken Abweichungen

Vorschlag von Gauß: Eindeutige Lösung über gewichtetes arithmetisches Mittel, Gewichte aus Distanzen

Jacobi: Gewichte aus Determinanten der Lösungen

Ausgleichungsrechnung IGerhard Navratil

Kombinationsansatz (1)

Lineares Problem:

Aus je 2 Gleichungen eine Lösung: Lösungen

0

0

0

333

222

111

yybxa

yybxa

yybxa

2

n

Ausgleichungsrechnung IGerhard Navratil

Kombinationsansatz (2)

Gewichtetes arithmetisches Mittel

Gewichte aus

2312

23231212

2312

23231212

yyy

xxx

2233223

2122112

baba

baba

Ausgleichungsrechnung IGerhard Navratil

Kombinationsansatz (3)

Nicht lineares Problem: Gewichte über Fehlerfortpflanzung abzuleiten

Liefert Varianz-Kovarianzmatrix

Ausgleichung direkter Beobachtungen

Ausgleichungsrechnung IGerhard Navratil

Zusammenfassung

• Notwendige Linearisierung bei Ausgleichs-problemen kann zu Schwierigkeiten führen

• Gröbner-Basis ermöglicht Lösung ohne Linearisierung (also auch ohne Näherungswerte)

• Vorteile: Rechenaufwand abschätzbar, Wiederholung einfach

• Nachteil: Mathematisch aufwändiger