of 110 /110
Ausgleichungsrechnung I Gerhard Navratil Mathematische Grundlagen • Lineare Algebra • Matrizenalgebra • Einfaches Eigenwertproblem • Singulärwertzerlegung • Generalisierte Inverse • Iterative und numerische Verfahren • Differentialrechnung • Optimierung

Mathematische Grundlagen

  • Upload
    arissa

  • View
    72

  • Download
    2

Embed Size (px)

DESCRIPTION

Mathematische Grundlagen. Lineare Algebra Matrizenalgebra Einfaches Eigenwertproblem Singulärwertzerlegung Generalisierte Inverse Iterative und numerische Verfahren Differentialrechnung Optimierung. Unbekannte. Konstante. Koeffizienten. Lineare Algebra. - PowerPoint PPT Presentation

Citation preview

Page 1: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Mathematische Grundlagen

• Lineare Algebra• Matrizenalgebra• Einfaches Eigenwertproblem• Singulärwertzerlegung• Generalisierte Inverse• Iterative und numerische Verfahren• Differentialrechnung• Optimierung

Page 2: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Lineare Algebra

Lösen linearer Gleichungen und Gleichungssysteme

Werkzeug: Matrizenrechnung

15294

15753

15618

321

321

321

xxx

xxx

xxx

3333232131

2323222121

1313212111

bxaxaxa

bxaxaxa

bxaxaxa

Koeffizienten

Unbekannte

Konstante

Page 3: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Arten von linearen Gleichungssystemen

Homogenes Gleichungssystem: alle Konstanten gleich Null

Inhomogenes Gleichungssystem: mindestens eine Konstante ungleich Null

Beispielsystem:3 Gleichungen in 3 Unbekannten

Mehr Gleichungen als Unbekannte: Überbestimmt

Mehr Unbekannte als Gleichungen: Unterbestimmt

Page 4: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Begriff ‚Algebra‘

Abu Ja'far Muhammad ibn Musa Al-Chwarismi: ‚Hisab al-gabr w'al-muqabala‘ (Wiederherstellen und Zusammenführen) um 800 – Auflösen von Gleichungen

lat. Übersetzung: ‚Algoritmi‘ (Algorithmus)

Algebra später: Lehre vom Auflösen von Gleichungs- und Ungleichungssystemen

Page 5: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Moderne Algebra

Beziehungen mathematischer Größen zu-einander – formale Behandlung

Lineare Algebra: n-dimensionaler Vektor-raum und lineare Transformationen in ihm

Algebra auch: mathematische Struktur mit bestimmten Eigenschaften Menge der Matrizen und ihre Operationen sind eine Algebra

Page 6: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Matrizenalgebra

Eine (m,n)-Matrix ist eine rechteckige Anordnung von m x n Elementen in m Zeilen und n Spalten.

nm

mnmm

n

n

ik

aaa

aaa

aaa

a A

21

22221

11211

Page 7: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Dimension einer Matrix

Definiert durch Anzahl der Spalten und Zeilen

quadratisch, wenn Anzahl der Spalten und Zeilen gleich

rechteckig sonst

(m,1)-Matrix: Spaltenvektor

(1,n)-Matrix: Zeilenvektor

(1,1)-Matrix: Skalar

Page 8: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Elemente der Matrix

Können Variablen, Zahlen aus C (R, Z, N), Polynome, Matrizen etc. sein

Angesprochen über den Index– Zeilenindex: Nummer der Zeile– Spaltenindex: Nummer der Spalte

Index: Erst Zeile, dann Spalte angegeben

Page 9: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Gleichungssysteme mit Matrizen

Gleichungssystem von vorher: Ax=b

• Koeffizientenmatrix A

• Unbekanntenvektor x

• Konstantenvektor b

3

2

1

,

15

15

15

,

294

753

618

x

x

x

xbA

Page 10: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Schreibweise von Matrizen

Runde und eckige Klammern erlaubt

In der Lehrveranstaltung:Eckige Klammern für Matrizen mit Zahlen

Blockweise auftretende Nullen oft weggelassen (Lesbarkeit)

8300

0600

0250

0104

83

6

25

14

MM statt

Page 11: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Alter der Matrizenschreibweise

Albrecht Dürer: ‚Die Melancholie‘ (1514)

magischesQuadrat

Page 12: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Submatrizen

Jeder Teilblock einer Matrix kann wieder als Matrix aufgefasst werden

sr

qPA

294

753

618

P, q, r, s sind Submatrizen

Page 13: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Spezialformen

• Nullmatrix: Alle Elemente gleich Null

• Diagonalmatrix: Nur Hauptdiagonale besetzt

• Dreiecksmatrix: Dreieck besetzt– obere Dreiecksmatrix R oder U– untere Dreiecksmatrix L

• Treppenform: nicht-quadratische Matrizen in Dreiecksform

Page 14: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Symmetrie

• Symmetrische Matrix: quadratisch und

• Schief-symmetrische Matrix: quadratisch und Elemente der Hauptdiagonale gleich Null

njiaa jiij ...1,

njiaa jiij ...1,

Page 15: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Gleichheit von Matrizen

Zwei Matrizen sind gleich, wenn sie • vom gleichen Typ sind (die gleiche Dimension

haben) und• alle Elemente gleich sind, also wenn gilt

njmiba ijij ...1,...1

Page 16: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Spur einer Matrix

Nur für quadratische Matrizen

Summe der Hauptdiagonal-Elemente

abgekürzt mit ‚tr‘ (engl. ‚trace‘)

n

iiia

1

tr A

Page 17: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Determinante einer Matrix

Nur für quadratische Matrizen

Berechnet nach Entwicklungssatz von Laplace

abgekürzt mit ‚det A‘ oder |A|

n

k

ikkiik

n

i

ikkiik aa

11

11det AAA

Minor

Submatrix nach Streichen der i-ten Zeile und k-ten Spalte, auch StreichungsmatrixKofaktor, oder auch

algebraisches Komplement

Page 18: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Regeln über Determinanten

• Vertauschen zweier Zeilen (Spalten) wechselt das Vorzeichen

• Addition (Subtraktion) eines Vielfachen einer Zeile (Spalte) zu einer anderen Zeile (Spalte) lässt die Determinante unverändert

• Determinante einer Dreiecks- oder Diagonal-matrix ist das Produkt der Hauptdiagonal-Elemente

• verschwindende Determinante: Sind zwei Zeilen (Spalten) gleich oder proportional, so wird det(A)=0 (die Determinante verschwindet)

Page 19: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Reguläre und singuläre Matrizen

• Singuläre Matrix: Quadratische Matrix mit verschwindender Determinante – det(A)=0

• Reguläre Matrix: Quadratische Matrix, bei der die Determinante nicht verschwindet

Page 20: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

3231

2221

1211

333231

232221

131211

aa

aa

aa

aaa

aaa

aaa+ ++

- --

Spezialfälle

(2,2)-Matrix

(3,3)-Matrix: Regel von Sarrus

211222112221

1211 aaaaaa

aa

333231

232221

131211

aaa

aaa

aaa

Page 21: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Matrizenoperationen

• Transposition

• Addition/Subtraktion

• Multiplikation mit einem Skalar

• Multiplikation zweier Matrizen

Page 22: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Transposition

Elemente wechseln ihre Position durch Vertauschen des Zeilen- und Spaltenindex

Abgekürzt mit AT

Spaltenvektor wird zu Zeilenvektor und umgekehrt

njmiaa jiTij ...1,...1

Page 23: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Symmetrie und Transposition

• Symmetrische Matrix:

• Schiefsymmetrische Matrix:

TAA

TAA

Page 24: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Aufspaltung einer quadratischen Matrix

Jede quadratische Matrix kann aufgespalten werden in eine symmetrische und eine schiefsymmetrische Matrix:

T

ssym

Tsym

ssymsym

mit

AAC

AAB

CBA

2

12

1

Page 25: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Addition und Subtraktion

Elementweises addieren/subtrahieren

Addition ist assoziativ

Addition ist kommutativ

Addition hat Nullelement

Transposition einer Summe

ijik ba BA

CBACBA

ABBA

AA00A TTT BABA

Page 26: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Multiplikation Matrix-Skalar

Jedes Element wird mit dem Skalar multipliziert

Es gilt:

ijij aa A

BABA

AAA

AA

AA

Page 27: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Element an Position (i,j) ist Produkt aus Zeilenvektor ai und Spaltenvektor bj

Potenzen nur für quadratische Matrizen möglich

AB=0 bedeutet, dass mindestens eine Matrix singulär (nicht: Nullmatrix!)

Matrizenmultiplikation

ji

n

k

kj

ki

kj

ik

pmpnnm

bababa

1

BA

CBA

Page 28: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Eigenschaften der Multiplikation

Assoziativ: (AB)C = A (BC)

Neutrales Element ist Einheitsmatrix I (E) mit

Multiplikation mit Einheitsmatrix ist kommutativ

Sonst NICHT kommutativ (ABBA)

Multiplikation ist distributiv: A(B+C)=AB+AC

jifür

jifürmit ijijij 0

1I

Kroneckersymbol

Page 29: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Potenzieren von Matrizen

qpqp

qpqp

AA

AAA

Page 30: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Skalarmultiplikation

Mit Einheitsmatrix kann die Skalarmultiplikation in eine Matrizenmultiplikation rückgeführt werden:

AIA

Page 31: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Transponieren von Produkten

TTTTT ABCZZCBA

Page 32: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Falk‘sches Schema

C=ABA

B

m

n

n

p

ABCDA

BCDB

C CD

D

Page 33: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Determinante und Spur von Matrizenprodukten

• Determinante einer (n,n)-Matrix:

• Spur einer Matrix:

T

n

n

AA

BAAB

AA

AA

1

AA

BABA

AA

trtr

trtrtr

trtr

T

Page 34: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Gauß‘sche Transformation

Produkt

N ist quadratisch, symmetrisch

Elemente nij von N: Skalarprodukt der Spalten i und j von A

Diagonalelemente positiv (Quadrate!)

Matrix positiv definit (bzw. semidefinit wenn auch Null in Hauptdiagonale)

Auch für Produkte möglich:

AAN T

PAAPA T

Page 35: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Positiv definit

Alle Subdeterminanten, die durch Streichung der letzten k Zeilen und Spalten entstehen (Minoren) sind 0

Hinweise auf positive definite Matrix:– Diagonalelemente positive reelle Zahlen– Jede Untermatrix ist positiv definit– Spur, Determinante und Minoren positiv– A+B positiv definit, wenn A und B positiv definit– Symmetrische Matrix mit positiven Eigenwerten ist

positiv definit

Page 36: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Orthogonale Matrizen

Quadratische Matrix

Skalarprodukt aus beliebigen Spaltenvektoren (Zeilenvektoren) ist 0 oder 1 orthonormal

Es gilt

Determinante ist ±1

Determinante +1: eigentlich orthogonal

Determinante -1: uneigentlich orthogonal

Multiplikation orthogonaler Matrizen ist kommutativ

1. QQIQQ TT bzw

IQQQQ TT

Page 37: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Inversion

Inverse Matrix (Kehrmatrix) von A ist definiert über

Matrix A quadratisch mit Determinante 0

Inverse ist eindeutig

A*: Adjungierte Matrix zu A, transponierte Matrix der Kofaktoren von A

IAAAA 11

*1

det

1A

AA

Page 38: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Inversion einer (2,2)-Matrix

ac

bd

dc

ba

AAA

det

11

Page 39: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Weitere Regeln

orthogonale Matrizen

A symmetrisch A-1 symmetrisch

A Diagonalmatrix A-1 Diagonalmatrix mit

Diagonalmatrix mit weiterer Zeile/Spalte besetzt

TAA 1

iiii aq 1

jjii

ijij

iiii aa

aqaq

,1

Page 40: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Submatrizen

11111

111

111

11

1

~

~

~

~

~~

~~

QSRQSPRSSS

RQSPRSR

QSRQSPQ

RQSPP

SR

QPA

SR

QPA

ssps

sppp

ssps

sppp

Page 41: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Spezialfälle von Submatrizen

ID

0I

ID

0I

B0

0AB0

0A

C0

BCAAC0

BA

1

1

11

1

1111

Page 42: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Neumann‘sche Reihe

Matrizeninversion kann auch über Reihenentwicklung berechnet werden:

Beweis: Von links mit (I+A) multiplizieren

Konvergenz, wenn Ai bei wachsendem i gegen Nullmatrix strebt

4321 AAAAIAI

Page 43: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Auflösen von Gleichungssystemen

Gegeben: Ax=b

Multiplikation von links mit A-1:

A-1Ax= A-1b

ergibt: (I)x= A-1b

Voraussetzungen:

Anzahl der Zeilen in A = Anz. Zeilen in b

Anzahl der Spalten in A = Anz. Zeilen in x

A invertierbar (quadratisch, Determinante Null)

Page 44: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Auflösung wenn nicht quadratisch

Gauß‘sche Transformation:Multiplikation von links mit AT:ATAx=ATbAuch: Normalgleichungen

Jetzt quadratisch und symmetrisch, wenn regulär ist das System lösbar

Abkürzung N=ATA Normalgleichungsmatrix

Page 45: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Lineare Abhängigkeit

• Vektorrechnung: Ein k-Tupel von Vektoren heißt linear abhängig wenn gilt

mit (1, …, n) 0

• Matrizenrechnung: Lineare Abhängig-keiten zwischen Zeilenvektoren bzw. Spaltenvektoren

k

iiix

1

0

Page 46: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Rang

Rang: Anzahl der linear unabhängigen Vektoren – rank(A)

Zeilen- und Spaltenrang sind immer gleich

Es gilt: rank(A)=rank(AT)

Page 47: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Rangdefekt

Anzahl der linearen Abhängigkeiten: Rangdefizit oder Rangdefekt d

rank(A)=n-d

Page 48: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Rang einer Matrix

Maximaler Rang einer (n,n)-Matrix: nDann: d = 0 (voller Rang) und det(A)0Also: Matrix invertierbar!

Wenn d > 0, dann det(A)= 0

Maximaler Rang einer (n,m)-Matrix: min(n,m)

Page 49: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Rang bei Gleichungssystemen

Gleichungssystem Ax=b

(n,n)-Matrix A muss Rang n haben

Zusätzlich: rank(A)=rank(A,b)

Page 50: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Bestimmung des Ranges (1)

Gauß‘scher Algorithmus: Man bringt die Matrix auf Treppen-(Dreiecks-)Form

Erlaubte elementare Umformungen:– Vertauschen von Zeilen/Spalten– Multiplizieren mit Skalar– Addieren einer mit einem Skalar

multiplizierten Zeile/Spalte zu einer anderen Zeile/Spalte

Page 51: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Bestimmung des Ranges (2)

Zeilen/Spalten, die das Vielfache anderer Zeilen/Spalten sind, werden eliminiert

Anzahl der nicht verschwindenden Zeilen/ Spalten ist der Rang

Verschwindende Zeilen: Nullen in Hauptdiagonale Determinante wird Null

Algorithmus auch zur Lösung von Gleichungssystemen verwendbar

Page 52: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Elementare Umformungen

Sind auch über Matrizenmultiplikationen möglich: z.B. Vertauschung von Zeilen

neuik AAJ

294

618

753

294

753

618

100

001

010

Page 53: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Gauß-Jordan-Verfahren

Basiert auf Gauß‘schem Algorithmus

Nur Umformungen der Zeilen

Ziel ist Zeilennormalform:– Elemente unterhalb der Hauptdiagonale Null– Erstes nicht verschwindendes Element jeder

Zeile Eins– Oberhalb dieser nicht verschwindenden

Elemente stehen nur Nullen

Page 54: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Vorgangsweise

xxxx

xxxx

xxxx

xxxx

00

00

00

00

xxxx

xxxx

xxxx

xxx

00

00

00

100

xxx

xxx

xxx

xxx

000

000

000

100

100000

10000

1000

100

x

xx

xxx

100000

010000

001000

000100

Erste vom Nullvektor verschiedene Spaltegrößtes Element (Pivotelement)

Zeilenvertauschen

Zeile durch diesen Wert dividieren

Page 55: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Hinweis

Gauß-Jordan-Verfahren kann auch zur Matrizeninversion verwendet werden

Beginn: A | I

Umwandlung der Matrix A, wobei jede Umformung auf beide Matrizen angewendet wird

Resultat: I | A-1

Page 56: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Einfaches Eigenwertproblem (1)

Quadratische Matrix A, gesucht sind die Vektoren x, für die giltAx=xmit dem Skalar

Umgeformt: (A-x=0(charakteristische Gleichung)

Annahme: (A- ist invertierbar: (A-(A-x=(A-0 x=0 triviale Lösung

Page 57: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Einfaches Eigenwertproblem (2)

Nicht-triviale Lösungen, wenn (A- singulär, alsodet(A-=0

charakteristische Determinante von A

Page 58: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Eigenwertproblem

allgemeine Form des Eigenwertproblems:Ax=Bx (für uns nicht wichtig)

Außerdem existiert jeweils eine zweite Art (Multiplikation mit dem Vektor von links)

Für uns ist bei Eigenwertproblem immer das einfache Eigenwertproblem erster Art gemeint

Page 59: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Eigenwerte

Lösung der charakteristischen Gleichung für eine (n, n)-Matrix liefert n Werte 1 bis n (Eigenwerte)

Eigenwerte im Allgemeinen konjugiert komplex

n ungerade: mindestens ein reeller Eigenwert

einfache, zweifache und mehrfache Eigenwerte

Page 60: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Kontrolle der Eigenwerte

n

ii

n

ii

1

1

tr

det

A

A

Page 61: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Weitere Eigenschaften

det(A)=0 mindestens ein Eigenwert gleich Null

Rangdefizit d d Eigenwerte gleich NullDie Eigenwerte einer Dreiecks- oder

Diagonalmatrix sind die Hauptdiagonal-elemente

A und AT haben dieselben Eigenwerte

A, i An, (i) n (speziell: Inverse!)

A, i A+cI, i+c; cA, ci

Page 62: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Eigenvektoren

Zu den Werten gehörende nicht triviale Lösungen für x

Eigenvektor zum Eigenwert Da (A-i singulär, ist der Eigenvektor nicht

eindeutig!Rangdefizit von 1: Eigenrichtung (Vektor auf

Länge 1 bringen um einheitliche Lösung zu erhalten – Normieren liefert Eigenvektor)

Rangdefizit >1: Entsprechende Anzahl linear unabhängiger Eigenrichtungen

Page 63: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Begriffe

Menge aller Eigenwerte: Spektrum der Matrix

Betragsmäßig größter Eigenwert: Spektralradius

Eigenwerte werden in Spektralmatrix zusammengefasst (Diagonalmatrix)

Eigenvektoren als Spaltenvektoren in Modalmatrix X zusammengefasst

Page 64: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Eigenschaften von und X

A = XX-1 (Eigenwertzerlegung)X-1AX = (Hauptachsentransformation)AX = XA und sind ähnliche Matrizen:

Es gibt eine Matrix U für die gilt:A = U-1U oder allgemein: S = U-1RU (Ähnlichkeitstransformation)

A symmetrisch X orthogonal A = XXT und XTAX =

Page 65: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Weitere Eigenschaften

Ist A eine Diagonalmatrix, so gilt = A und X = I

A und Am haben dieselben Eigenvektoren

Bei einer symmetrischen Matrix A gilt:A2 = ATA, die Matrix ATA hat dieselben Eigenvektoren, die Eigenwerte sind die Quadrate der Eigenwerte von A

Page 66: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Geometrische Interpretation

Darstellung einer Ellipse ist möglich mit

Eigenvektoren von A:Richtung der Haupt- und Nebenachse

Eigenwerte von A:Länge von Haupt- und Nebenachse

Modalmatrix dreht die Ellipse in Hauptlage

1.1

AxxTbzw

y

x

dc

bayx

Page 67: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Singulärwertzerlegung

Ähnlich der Eigenwertzerlegung

Auch für rechteckige Matrizen definiert

Die (m,n)-Matrix A zerlegen wir in– eine orthogonale (m,m)-Matrix U,– eine orthogonale (n,n)-Matrix V und– eine (m,n)-Diagonalmatrix S.

Bedingung für die Zerlegung: A = USVT

Page 68: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Bestimmung der Matrizen (1)

Gauß‘sche Transformation

Weil U orthogonal gilt UTU=I

Mit der Abkürzung D=STS=S2 erhalten wir

Rechter Teil entspricht formal einer Eigenwertzerlegung von ATA.

TTTTTTT USVUVSUSVUSVAA

TT VDVAA

Page 69: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Bestimmung der Matrizen (2)

Somit D Diagonalmatrix mit Eigenwerten von ATA.

S hat die Wurzeln der Eigenwerte in der Hauptdiagonale, mit Nullen aufgefüllt zur richtigen Dimension

V aus Eigenvektoren von ATA.

U über AAT=USVT(USVT)T=USSTUT

D=SST=S2Singular Value Decomposition (SVD)

Page 70: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Inversion singulärer Matrizen (Generalisierte Inverse)

Moore-Penrose Inverse

Bestimmung über Singulärwertzerlegung:Da nur für reguläre Matrizen (i0) möglich, Eigenwerte gleich Null gestrichen

AAAA

AAAA

AAAA

AAAA

T

T

Page 71: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Numerische Lösung

Bisher gesehene Verfahren und Formeln sehr rechenintensiv und fehleranfällig

Im Allgemeinen sollte auf vorhandene, getestete Programme zurückgegriffen werden

Im Weiteren einige wichtige Methoden

Page 72: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Lösung von Gleichungssystemen

• Eliminationsverfahren nach Gauß

• Eliminationsverfahren nach Gauß-Jordan

• LU-Verfahren

• Cholesky-Verfahren

• Gauß-Seidel-Verfahren

Page 73: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Eliminationsverfahren nach Gauß

Koeffizientenmatrix durch elementare Umformungen in Dreiecks- oder Treppenform bringen liefert eine Unbekannte

Rückwärtseinsetzen in das umgeformte Gleichungssystem

Page 74: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Eliminationsverfahren nach Gauß-Jordan

Koeffizientenmatrix durch elementare Umformungen in Zeilennormalform gebracht

Direkte Ermittlung der Unbekannten

Page 75: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

LU-Verfahren (LR-Verfahren)

Lower-Upper-Decomposition

(n,n)-Matrix A in obere (U) und untere (L) Dreiecksmatrix zerlegt: A = LU

Ax = (LU)x = L(Ux) = b Ly = b

Vorteil: Zerlegte Matrix A kann mit jedem Konstantenvektor b ohne neuerliche Auflösung verwendet werden

Page 76: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Cholesky-Verfahren

Anwendung des LU-Verfahrens auf symmetrische, positiv definite Matrizen

A = UTU

Ax = b Ux = s mit

2,1

22

21

2

,1,12211

iiiiiiii

ii

kiiikikiikik

uuuau

u

uuuuuuau

ii

i

kkiki

i u

sub

s

1

1

Page 77: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Partielle Reduktion mit dem Cholesky-Verfahren (1)

Ax = b aufgespaltet in A11x1 + A12x2 = b1

A21x1 + A22x2 = b2

Erlaubt Aufspaltung der Dreiecksmatrix in

22

1211

U0

UUU

Page 78: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Partielle Reduktion mit dem Cholesky-Verfahren (2)

Aus A = UTU können wir ableiten:

2222221212

121211

111111

AUUUU

AUU

AUU

TT

T

T

Page 79: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Partielle Reduktion mit dem Cholesky-Verfahren (3)

2222221212

121211

111111

AUUUU

AUU

AUU

TT

T

T

2222121

1212111

:

:

bxAxA

bxAxA

II

I

111

11212111 sbUxUxU T

1

11TU

III 11121AA

11

11212)(

2

121

112122)(

22

)(22

)(22

bAAbb

AAAAA

bxA

p

p

pp

mit

Page 80: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Gauß-Seidel-Verfahren

Schwach besetzte Matrix: An vielen Stellen Null

Iterative Verfahren gut geeignetz.B. Gauß-Seidel-Verfahren

Näherungslösung so lange verbessert, bis gewünschte Genauigkeit erreicht

Nachteil: Iteration nicht immer konvergent

Page 81: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Bestimmung von Eigenwerten und –Vektoren

• QR-Algorithmus – Zerlegung in ortho-gonale Matrix Q und Dreiecksmatrix RA = QR, Iteration Ak+1 = RkQk, Haupt-diagonalelemente von Ak kovergieren zu Eigenwerten

• Jacobi-Verfahren – Symmetrische Matrix wird näherungsweise in eine Diagonal-matrix übergeführt (Eigenwerte in Hauptdiagonale)

Page 82: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Matrixnorm

Reelle Funktion der Elemente mit der Eigenschaft

||A||0 mit ||A|| = 0 für A=0

Unterschiedliche Normen vorhanden

BABA

BABA

AA

cc

… für quadratische Matrizen

Page 83: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Wichtige Matrixnormen

• Frobenius/Schur-Norm (Euklidische Norm)

• Spektral-/Hilbert-Norm

m

i

n

kikF

a1 1

2A

maxS

A

maximaler Eigenwert

Page 84: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Gestörte Gleichungssysteme

Störung eines Gleichungssystems durch kleine Abweichungen eines oder mehrerer Parameter

Frage: Wie wirken sich die Störungen auf die Lösung aus?

bbxxAA

Page 85: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Beispiel

20201

,1

1

1,,0

1

1

1

a

ay

ax

aRay

x

a

a

gestörtes System:

22 1,

1

1

1,,1

1

1

a

ay

a

ax

aRay

x

a

a

Differenz:2020

1

1,

1 ayy

a

axx

Bei a nahe 1 wirkt sich ein geringer Fehler bereits stark aus!

Page 86: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Allgemeine Behandlung

AxbAAx 1

Bestimmung von

x

x

Ergebnis: Für kleine Störungen wird der relativeFehler um den Faktor verstärkt.AA 1

Gut konditioniert: kleine Eingangsfehler bewirkenkleine ErgebnisfehlerSchlecht konditioniert: kleine Eingangsfehlerbewirken unverhältnismäßig große Ergebnisfehler

Kondition p der Matrix A

Page 87: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Kondition einer Matrix

(A)1

Große Konditionszahl weist auf unangenehme numerische Eigenschaften der Matrix hin eventuell Probleme beim Auflösen des Gleichungssystems

Singuläre Matrizen erhalten =Symmetrische Matrizen: (A)=|max|/|min|

Page 88: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Differentialrechnung

Funktion: Abbildung xf(x)

Differenzenquotient:Steigung der Sekante im Intervall [x,x0]

Differentialquotient (erste Ableitung)

Steigung der Funktion im Punkt x

Lineare Funktionen: Steigung und Sekante in jedem Punkt gleich

000 )()()(

xxxmitx

xfxxf

x

xf

h

xfhxfxf

h

)()(lim)(' 00

0

Page 89: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Rechenregeln

• Konstantenregel• Faktorregel• Potenzregel• Summenregel• Produktregel• Quotientenregel

• Kettenregel

0'c)('))'(( xfcxfc

1)'( nn xnx )(')('')()( xgxfxgxf ''')()( gfgfxgxf

2

'''

)(

)(

g

gfgf

xg

xf

)('))((''))(( xgxgfxgf

Page 90: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Numerische Differentiation

Wenn analytische Ableitung aufwendig

Differentialquotient durch Differenzen-quotient angenähert

oder (numerisch besser)

mit 10-8h 10-4

h

xfhxfxf

)()()('

h

hxfhxfxf

2

)()()('

Page 91: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Höhere Ableitungen

Zweite Ableitung: Erste Ableitung der ersten Ableitung – f‘‘(x)=(f‘(x))‘

Ebenso dritte Ableitung etc.

Allgemein:

n

nn

dx

xfdxf

)()()(

Page 92: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Taylorreihe (1)

Approximation durch Potenzreihenz.B.

Funktionswerte einer differenzierbaren Funktion f in der Umgebung der Stelle x0 näherungsweise berechenbar

unendliche Potenzreihe (n ): Taylorreihe

)(!

)()(

00

0)(

xRxxk

xfxf n

n

k

kk

n-tes Taylorpolynom

Page 93: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Taylorreihe (2)

Auch geschrieben als

Voraussetzung: Funktion (n+1)-fach differenzierbar

Entwicklung um x0=0: Maclaurin-Formel

Beispiele: Sinus-/Cosinusentwicklung

Ist x klein: Abbruch nach ersten beiden Gliedern - Linearisierung

nn xxfn

xxfxxfxfxxf )(!

1)(''

!2

1)(')()( 0

)(20000

Page 94: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Funktionen in mehreren Variablen

Abbildung, die jedem Vektor x eine (reelle) Zahl f(x) zuordnet

Funktion in n Variablen entsprechend der Dimension des Vektors

Page 95: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Partielle Ableitungen

Alle Parameter außer xi einer Funktion in n Variablen als Konstante angesehen

Ableitung nach diesem Parameter heißt partielle Ableitung (erster Ordnung) nach xi an der Stelle x

Analog partielle Ableitungen höherer Ordnung

Page 96: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Totales Differential

Totales Differential der Funktion f an der Stelle x:

nn

dxx

xfdx

x

xfdx

x

xfdf

)()()(

22

11

Page 97: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Taylorentwicklung für Funktion in zwei Variablen

y

y

yxfx

x

yxfyxfyyxxf

),(),(

!1

1),(),( 0000

0000

n

n

Ryy

yxfx

x

yxf

n

yy

yxfx

x

yxf

)(

0000

)2(

0000

),(),(

!

1

),(),(

!2

1

Wobei die Klammerausdrücke nach dem binomischen Lehrsatz aufzulösen sind:

n

k

kknn bak

nba

0

pmp

mpmp

yx

f

y

f

x

f

und folgendes gilt:

Page 98: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Linearisieren einer Funktion in mehreren Variablen

Taylorentwicklung

Abbruch nach der ersten Ableitung

Anwendbar nur in einer entsprechend kleinen Umgebung um x0 (Glieder höherer Ableitungen vernachlässigbar klein)

Page 99: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Differentiation von Matrizenfunktionen

Formal gleich bzw. ähnlich den gewöhnlichen Differentiationsregeln

Hier nur für Ausgleichung wichtige Fälle

Differentialvektor: dxT=(dx1 dx2 … dxn)

f=aTx df=aTdx

Page 100: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Ableitung der Bilinearform

Bilinearform: Produkt der FormZeilenvektor-Matrix-Spaltenvektor

f=xTAl df = dxTAl = lTATdx

Sonderfall: Vektoren identisch – Quadratische Form

f=xTAx df = dxTAx + xTAdx = xT(AT+A)dx

Symmetrische Matrizen: df = 2xTAdx

Page 101: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Optimierung

Festlegung von Parametern so, dass eine Funktion der Parameter einen extremen Wert annimmt (Maximum oder Minimum)

z.B. kürzester Weg zwischen zwei Punkten, maximale Fläche bei gegebenem Umfang

Eindimensionaler Fall: Erste Ableitung gleich Null setzen – liefert Extremwert

Mehrdimensionaler Fall: Ersten partiellen Ableitungen gleich Null gesetzt

Page 102: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Unterscheidung Maximum-Minimum

Zweite Ableitung

Bei Funktion in mehreren Variablen: Hesse-Matrix

• positiv definit: Minimum(alle Eigenwerte positiv)

• negativ definit: Maximum (alle Eigenwerte negativ)

22

2

12

221

2

21

2

x

f

xx

f

xx

f

x

f

H

Page 103: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Nebenbedingungen

Gesucht: lokale Extrema von f(x1…xn), Bedingung g(x1…xn) muss erfüllt sein

• f Zielfunktion• g Nebenbedingung

Page 104: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Beispiel (1)

f(x1,x2)=x12+2x2

2

g(x1,x2)=x1+x2-3=0

Lösung: x1 in g durch x2 ausdrücken und in f einsetzen – liefert quadratische Gleichung in einer Unbekannten

Diese einfache Lösung nicht immer möglich!

Page 105: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Beispiel (2)

Graphische Lösung: Nebenbedingung berührt Niveaulinie

Page 106: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Beispiel (3)

Mathematisch: Nebenbedingung und Niveaulinie in diesem Punkt parallel

Somit: Gradienten von f und g haben gleiche Richtung:

bzw.

)()( agaf

0)()( agaf

Page 107: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Beispiel (4)

Somit erhalten wir das Gleichungssystem

0,,

0

0

1

11

n

nn

xxg

x

g

x

f

x

g

x

f

Page 108: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Beispiel (5)

Formal gleiche Lösung: Lagrange-Funktion

nnn xxgxxfxxL ,,,,,,, 111 Lagrange-Multiplikator

Ableitung der Lagrange-Funktion nach allenVariablen x1, …, xn und und gleich Null setzen liefert dasselbe Gleichungssystem wie vorher.

Page 109: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Zusammenfassung (1)

Gleichungssysteme können mit Matrizen einfach angeschrieben und behandelt werden

Eigenschaften durch Kennzahlen beschrieben (Determinante, Rang, etc.)

Linearisieren von Funktionen geschieht mit Taylorreihen

Zum Optimieren mit Nebenbedingungen nimmt man die Lagrange-Funktion

Page 110: Mathematische Grundlagen

Ausgleichungsrechnung IGerhard Navratil

Zusammenfassung (2)

Vorsicht bei numerischen Problemen: Die Hälfte aller vom Computer darstellbarer Zahlen liegt zwischen -1 und 1

Schlechte Numerik kann den Rechengang empfindlich stören, daher die Ergebnisse IMMER kritisch hinterfragen