Lineare Ausgleichsprobleme (=überbestimmte Gleichungssysteme)dobro/num1/f9.pdf · n zu ﬁnden (=Methode der kleinsten Quadrate). Numerik von Eigenwertproble-men Das Lanczos-Verfahren

Numerik von

Eigenwertproble-

men

DasLanczos-Verfahren

Bestimmung derEigenwerte einerhermiteschenTridiagonalmatrix

Reduktion aufHessenberg-Gestalt

Bestimmung derEigenwerte einerHessenberg-Matrix

Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

9 Ausgleichsrechnung

◮ Lineare Ausgleichsprobleme (=überbestimmteGleichungssysteme)

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



◮ Pseudoinverse einer Matrix

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



◮ Pseudoinverse einer Matrix

◮ Nichtlineare Ausgleichsprobleme

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

9.1 Problemstelllung

Führe Experimente durch unter Versuchsbedingungenz ∈ Rm.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



Es sollen Größen x ∈ Rn bestimmt werden, für die ein Gesetz

y = f (z , x), f : Rm ×Rn → R,

gelten soll.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




y = f (z , x), f : Rm ×Rn → R,

gelten soll.

Führe m ≥ n Versuche durch,

yk = f (zk , x) =: fk(x), k = 1, . . . ,m.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




y = f (z , x), f : Rm ×Rn → R,

gelten soll.


yk = f (zk , x) =: fk(x), k = 1, . . . ,m.

Aufgrund von Messfehlern gilt aber nur yk ≈ fk(x),. so dassi.A. m > n Versuche durchgeführt werden.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




y = f (z , x), f : Rm ×Rn → R,

gelten soll.


yk = f (zk , x) =: fk(x), k = 1, . . . ,m.

Aufgrund von Messfehlern gilt aber nur yk ≈ fk(x),. so dassi.A. m > n Versuche durchgeführt werden.

Bestimme nun x aus den yk .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

Ein chemischer Prozess wird modelliert durch

y ′′ + a1y′ + a0y = 0, y (k)(0) = y

(k)0

mit k = 0, 1 bekannt.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel


y ′′ + a1y′ + a0y = 0, y (k)(0) = y

(k)0


Mit dem Ansatz y(z) = eωz folgt dann

ω2 + a1ω + a0 = 0.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel


y ′′ + a1y′ + a0y = 0, y (k)(0) = y

(k)0



ω2 + a1ω + a0 = 0.

Aus dem nichtoszillatorischen Verhalten der Lösung weißman, dass diese Gleichung zwei reelle Nullstellen α, β besitzt.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel


y ′′ + a1y′ + a0y = 0, y (k)(0) = y

(k)0



ω2 + a1ω + a0 = 0.

Aus dem nichtoszillatorischen Verhalten der Lösung weißman, dass diese Gleichung zwei reelle Nullstellen α, β besitzt.

Die allgemeine Lösung der Differentialgleichung ist dann

y(z) = c1eαz + c2e

βz .

Gesucht sind die Reaktionszeiten α und β.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

Aus y(0) = y0 erhalten wir

c1 + c2 = y0

und aus y ′(0) = y ′0

αc1 + βc2 = y ′0.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel


c1 + c2 = y0

und aus y ′(0) = y ′0

αc1 + βc2 = y ′0.

Das kann nicht ausgenutzt werden, weil die Unbekanntenα, β darin vorkommen.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel


c1 + c2 = y0

und aus y ′(0) = y ′0

αc1 + βc2 = y ′0.

Das kann nicht ausgenutzt werden, weil die Unbekanntenα, β darin vorkommen.

Daher ist

y(z) = c1eαz + (y0 − c1)e

βz = f (z , c1, α, β),

wobei c1, α, β gesucht sind.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

c1, α, β werden gesucht mit

y(z) = c1eαz + (y0 − c1)e

βz = f (z , c1, α, β).

Führe also für Zeiten z1, . . . , zm, m ≥ 3, Messungen durch,

yk = f (zk , c1, α, β).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

c1, α, β werden gesucht mit

y(z) = c1eαz + (y0 − c1)e

βz = f (z , c1, α, β).

Führe also für Zeiten z1, . . . , zm, m ≥ 3, Messungen durch,

yk = f (zk , c1, α, β).

Dies ist ein schwieriges und häufiges Problem, nämlich dieExponentialapproximation.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Allgemeine Ausgleichsprobleme

Kehren wir zum allgemeinen Problem zurück, ein x ∈ Rn zufinden mit

yk ≈ fk(x), k = 1, . . . ,m.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



yk ≈ fk(x), k = 1, . . . ,m.

Die mathematisch einfachste Möglichkeit besteht nun darin,ein Minimum der Funktion

F (x) =m∑

k=1

|yk − fk(x)|2

über x ∈ Rn zu finden (=Methode der kleinsten Quadrate).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



yk ≈ fk(x), k = 1, . . . ,m.

Die mathematisch einfachste Möglichkeit besteht nun darin,ein Minimum der Funktion

F (x) =m∑

k=1

|yk − fk(x)|2

über x ∈ Rn zu finden (=Methode der kleinsten Quadrate).

Schwieriger ist es, die Funktion

F (x) = maxk=1,...,m

|yk − fk(x)|

zu minimieren (=diskretes Tschebyscheff-Problem).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Lineare Ausgleichsprobleme

Ein wichtiger Spezialfall ist ein lineares f (x) = Ax mit einer(m × n)-Matrix A.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



Minimiere das Funktional

F (x) = |Ax − y |2, y ∈ Rm.

Dies ist das lineares Ausgleichsproblem.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




F (x) = |Ax − y |2, y ∈ Rm.


Die notwenige Bedingung für eine Lösung x dieses Problemsist

grad x |y − Ax |2 = 2ATAx − 2AT y = 0.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




F (x) = |Ax − y |2, y ∈ Rm.


Die notwenige Bedingung für eine Lösung x dieses Problemsist

grad x |y − Ax |2 = 2ATAx − 2AT y = 0.

Das System ATAx = AT y heißt Normalgleichungen zu|Ax − y |2 → Min.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Wie bestimmt man gradx|y − Ax |2?

Am einfachsten berechnet man die Ableitung von F (x) inRichtung z ,

d

dtF (x + tz) =

m∑

i=1

d

dt(y − A(x + tz))i (y − A(x + tz))i

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



d

dtF (x + tz) =

m∑

i=1

d


= 2m∑

i=1

(y − A(x + tz))i (−Az)i

= −2(y − A(x + tz),Az)

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



d

dtF (x + tz) =

m∑

i=1

d


= 2m∑

i=1

(y − A(x + tz))i (−Az)i

= −2(y − A(x + tz),Az)

d

dtF (x + tz)

∣

∣

t=0= −2(y − Ax ,Az).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


d

dtF (x + tz)

∣

∣

t=0= −2(y − Ax ,Az).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


d

dtF (x + tz)

∣

∣

t=0= −2(y − Ax ,Az).

Da im Minimum alle Richtungsableitungen verschwinden,folgt

−2(y − Ax ,Az) = 0 ∀z ⇒ (AT (y − Ax), z) = 0 ∀z

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


d

dtF (x + tz)

∣

∣

t=0= −2(y − Ax ,Az).

Da im Minimum alle Richtungsableitungen verschwinden,folgt

−2(y − Ax ,Az) = 0 ∀z ⇒ (AT (y − Ax), z) = 0 ∀z

⇒ ATAx = AT y .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

9.2 Das lineare Ausgleichsproblem

Satz Sei A ∈ Rm×n. Die Probleme

|Ax − y |2 → Min in x ∈ Rn, ATAx = AT y ,

sind äquivalent:

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




sind äquivalent:

Jede Lösung des einen Problems ist auch eine Lösung desanderen Problems.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




sind äquivalent:

Jede Lösung des einen Problems ist auch eine Lösung desanderen Problems.

Für je zwei Lösungen x1, x2 gilt Ax1 = Ax2 und für dasResiduuum r = y − Ax einer jeden Lösung x haben wirAT r = 0.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Wir haben bereits gezeigt, dass jedes Minimum x ∈ Rn vonF (x) = |y − Ax |2 die Beziehung

ATAx = AT y ⇒ AT r = 0 für r = y − Ax

erfüllt.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis



erfüllt.

Daher

(y − Ax ,Az) = 0 ∀z ∈ Rn ⇒ y − Ax ⊥ Bild (A).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis



erfüllt.

Daher

(y − Ax ,Az) = 0 ∀z ∈ Rn ⇒ y − Ax ⊥ Bild (A).

Also ist Ax die orthogonale Projektion von y auf Bild (A)und damit eindeutig bestimmt.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Für eine Lösung x0 der Normalgleichungen gilt mit derZerlegung

y = s + r , s ∈ L = Bild (A), r ∈ L⊥,

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Für eine Lösung x0 der Normalgleichungen gilt mit derZerlegung

y = s + r , s ∈ L = Bild (A), r ∈ L⊥,

dass

0 = (AT (Ax0 − y), z) = (Ax0 − y ,Az) ⇒ Ax0 − y ⊥ L

⇒ Ax0 = s wegen Ax0 ∈ L.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Für x ∈ Rn setze

z = Ax − Ax0, r = y − Ax0.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Für x ∈ Rn setze

z = Ax − Ax0, r = y − Ax0.

Mit z ∈ L und r ⊥ L folgt (r , z) = 0 und daher

|y − Ax |2 = |r − z |2 = |r |2 + |z |2 ≥ |r |2 = |y − Ax0|2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Für x ∈ Rn setze

z = Ax − Ax0, r = y − Ax0.

Mit z ∈ L und r ⊥ L folgt (r , z) = 0 und daher

|y − Ax |2 = |r − z |2 = |r |2 + |z |2 ≥ |r |2 = |y − Ax0|2.

Damit ist x0 ein Minimum von F .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Anwendung des Cholesky-Verfahrens

Wenn m ≥ n und rang A = n, so ist ATA symmetrischpositiv definit und die Gleichung

ATAx = AT y

kann mit dem Cholesky-Verfahren gelöst werden.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Anwendung des Cholesky-Verfahrens

Wenn m ≥ n und rang A = n, so ist ATA symmetrischpositiv definit und die Gleichung

ATAx = AT y

kann mit dem Cholesky-Verfahren gelöst werden.

Da ATA aber oft schlecht konditioniert ist, verwendet manbesser das im nächsten Abschnitt dargestellte Verfahren.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

9.3 Orthogonalisierungsverfahren

Wir wollen

|y − Ax |2 → Min mit A ∈ Rm×n, m ≥ n,

bestimmen.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

9.3 Orthogonalisierungsverfahren

Wir wollen

|y − Ax |2 → Min mit A ∈ Rm×n, m ≥ n,

bestimmen.

Dazu eliminieren wir die erste Spalte von A mit einer(m × m)-Householder-Matrix P1 und erhalten mit A(0) = A

A(1) = P1A(0) =

∗ ∗ · · · ∗0 ∗ · · · ∗...

......

0 ∗ · · · ∗

.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Householder-Verfahren

Der Householder-Algorithmus verläuft daher genauso wie beiquadratischen Matrizen. Nach n Schritten gilt mit einerunitären Matrix P ∈ Rm×m

A(n) = PA =

[

R

0

]

,

wobei R ∈ Rn×n eine rechte obere Dreiecksmatrix ist.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



A(n) = PA =

[

R

0

]

,


Da rangA = n, besitzt R nichtverschwindende Elemente aufder Hauptdiagonalen.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das



A(n) = PA =

[

R

0

]

,


Da rangA = n, besitzt R nichtverschwindende Elemente aufder Hauptdiagonalen.

Für die rechte Seite gilt analog

h = Py =

(

h1

h2

)

, h1 ∈ Rn, h2 ∈ Rm−n.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


h = Py =

(

h1

h2

)

, h1 ∈ Rn, h2 ∈ Rm−n.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


h = Py =

(

h1

h2

)

, h1 ∈ Rn, h2 ∈ Rm−n.

Da P unitär folgt |Pz | = |z | und daher

|y − Ax |2 = |P(y − Ax)|2 =

∣

∣

∣

∣

∣

(

h1 − Rx

h2

)∣

∣

∣

∣

∣

2

= |h1 − Rx |2 + |h2|2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


h = Py =

(

h1

h2

)

, h1 ∈ Rn, h2 ∈ Rm−n.

Da P unitär folgt |Pz | = |z | und daher

|y − Ax |2 = |P(y − Ax)|2 =

∣

∣

∣

∣

∣

(

h1 − Rx

h2

)∣

∣

∣

∣

∣

2

= |h1 − Rx |2 + |h2|2.

Die Lösung von Rx = h1 ist damit auch die eindeutigeLösung des Minimierungsproblems F (x) → Min.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

9.4 Die Pseudoinverse einer Matrix

Zu A ∈ Rm×n wollen wir eine Pseudoinverse A+ ∈ Rn×m

definieren, deren Eigenschaften wir an Hand des linearenGleichungssystems Ax = b für b ∈ Rm festlegen wollen.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




Da wir keinerlei Voraussetzungen an A stellen, kann dasGleichungssystem unlösbar oder mehrdeutig lösbar sein.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das





Die „Lösung“ x = A+b wird nach folgenden Kriterienfestgelegt:

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das






Zuerst wird y aus dem Bild von A bestimmt, das den Fehler|y − b| minimiert.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das






Zuerst wird y aus dem Bild von A bestimmt, das den Fehler|y − b| minimiert.

Anschließend wird unter allen x mit Ax = y dasjenigeausgewählt, dessen Norm |x | minimal wird.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen

Sei V ein endlich dimensionaler linearer Raum über C mitSkalarprodukt (·, ·).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen


Sei L ⊂ V ein Unterraum. Dann gilt für jedes x ∈ V dieeindeutige Zerlegung

x = x0 + x⊥ mit x0 ∈ L und x⊥ ∈ L⊥.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen



x = x0 + x⊥ mit x0 ∈ L und x⊥ ∈ L⊥.

P : V → L, Lx = x0 heißt orthogonale Projektion auf L undhat die Eigenschaft

‖x − Px‖ = minz∈L

‖x − z‖.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen



x = x0 + x⊥ mit x0 ∈ L und x⊥ ∈ L⊥.

P : V → L, Lx = x0 heißt orthogonale Projektion auf L undhat die Eigenschaft


‖x − z‖.

Also ist Px das Element bester Approximation in L zu x .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen


‖x − z‖.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen


‖x − z‖.

Dies gilt wegen

‖x − Px‖2 = ‖x − x0‖2 = ‖x⊥‖

2

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen


‖x − z‖.

Dies gilt wegen

‖x − Px‖2 = ‖x − x0‖2 = ‖x⊥‖

2

und, für z ∈ L,

‖x − z‖2 = ‖x0 + x⊥ − z‖2 = ‖x0 − z‖2 + ‖x⊥‖2 ≥ ‖x⊥‖

2

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen


‖x − z‖.

Dies gilt wegen

‖x − Px‖2 = ‖x − x0‖2 = ‖x⊥‖

2

und, für z ∈ L,

‖x − z‖2 = ‖x0 + x⊥ − z‖2 = ‖x0 − z‖2 + ‖x⊥‖2 ≥ ‖x⊥‖

2

Weiter gilt P2 = P (da Projektion) und PH = P wegen

(Px , y) = (x0, y0 + y⊥) = (x0, y0)

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Projektionen


‖x − z‖.

Dies gilt wegen

‖x − Px‖2 = ‖x − x0‖2 = ‖x⊥‖

2

und, für z ∈ L,

‖x − z‖2 = ‖x0 + x⊥ − z‖2 = ‖x0 − z‖2 + ‖x⊥‖2 ≥ ‖x⊥‖

2

Weiter gilt P2 = P (da Projektion) und PH = P wegen

(Px , y) = (x0, y0 + y⊥) = (x0, y0) = (x ,Py) = (PHx , y).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

Sei y ∈ Bild (A).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

Sei y ∈ Bild (A).

Aufgabe Bestimme unter allen Lösungen von Ax = y

diejenige mit minimaler Norm.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

Sei y ∈ Bild (A).



Es gilt Ax1 = y für ein x1 ∈ Cn und die Lösungsmenge istx1 + Kern (A).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

Sei y ∈ Bild (A).




Mit

x1 = x1,0 + x1,⊥, x1,0 ∈ Kern (A), x1,⊥ ∈ Kern (A)⊥

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

Sei y ∈ Bild (A).




Mit

x1 = x1,0 + x1,⊥, x1,0 ∈ Kern (A), x1,⊥ ∈ Kern (A)⊥

gilt für alle x ∈ Kern (A)

|x1 + x |2 = |x1,⊥ + x1,0 + x |2 = |x1,⊥|2 + |x1,0 + x |2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

Für alle x ∈ Kern (A) gilt

|x1 + x |2 = |x1,⊥ + x1,0 + x |2 = |x1,⊥|2 + |x1,0 + x |2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse


|x1 + x |2 = |x1,⊥ + x1,0 + x |2 = |x1,⊥|2 + |x1,0 + x |2.

Also hat

x1,⊥ = Px1, P = Projektion auf Kern (A)⊥

minimale Norm.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse


|x1 + x |2 = |x1,⊥ + x1,0 + x |2 = |x1,⊥|2 + |x1,0 + x |2.

Also hat


minimale Norm.

Px1 ist als minimale Lösung in x1 + Kern (A) eindeutigbestimmt.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse


|x1 + x |2 = |x1,⊥ + x1,0 + x |2 = |x1,⊥|2 + |x1,0 + x |2.

Also hat


minimale Norm.

Px1 ist als minimale Lösung in x1 + Kern (A) eindeutigbestimmt.

Demnach gibt es eine lineare Abbildung f : Bild (A) → C

n

mitAf (y) = y , f (y) ∈ Kern (A)⊥.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

SeiP ∈ Cm×m : Cm → Bild (A)

die orthogonale Projektion auf Bild (A).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse



Dann istf ◦ P : Cm → C

n.

der gesuchte „Pseudo-Lösungsoperator“.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse




n.


Die Darstellung von f ◦ P durch eine (n ×m)-Matrix ist danndie gesuchte Pseudo-Inverse A+.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse




n.


Die Darstellung von f ◦ P durch eine (n ×m)-Matrix ist danndie gesuchte Pseudo-Inverse A+.

Denn es wird das nächstgelegene y ∈ Bild (A) zu y bestimmtund anschließend die betragsmäßig kleinste Lösung vonAx = y .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse

Satz Die Pseudoinverse A+ hat die folgenden Eigenschaften:

(a) A+A = P , AA+ = P ,

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse


(a) A+A = P , AA+ = P ,

(b) (i) A+A = (A+A)H , (ii) AA+ = (AA+)H ,

(iii) AA+A = A, (iv) A+AA+ = A+.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse


(a) A+A = P , AA+ = P ,

(b) (i) A+A = (A+A)H , (ii) AA+ = (AA+)H ,


(c) Wenn Z ∈ Cn×m die Eigenschaften (b) (i)-(iv) besitzt(an Stelle von A+), so ist Z = A+.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Pseudoinverse


(a) A+A = P , AA+ = P ,

(b) (i) A+A = (A+A)H , (ii) AA+ = (AA+)H ,



(d) A++ = A, (A+)H = (AH)+.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(a) A+A = P , AA+ = P .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(a) A+A = P , AA+ = P .

Es giltA+Ax = f (P(Ax)) = f (Ax) = Px

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(a) A+A = P , AA+ = P .

Es giltA+Ax = f (P(Ax)) = f (Ax) = Px

sowieAA+y = A(f (Py)) = Py .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(b) (i) A+A = (A+A)H , (ii) AA+ = (AA+)H ,


Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(b) (i) A+A = (A+A)H , (ii) AA+ = (AA+)H ,


Wegen A+A = P , AA+ = P und P = PH , P = PH

folgen (i)und (ii).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(b) (i) A+A = (A+A)H , (ii) AA+ = (AA+)H ,



folgen (i)und (ii).

(iii) erhält man aus

(AA+)Ax = PAx = Ax

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(b) (i) A+A = (A+A)H , (ii) AA+ = (AA+)H ,



folgen (i)und (ii).

(iii) erhält man aus

(AA+)Ax = PAx = Ax

und (iv) aus

A+(AA+)y = A+Py = A+y .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis


Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis


Es gilt

Z(iii) für Z

= ZAZ(iii) für A

= ZAA+Az

(iv) für A= Z (AA+A)A+(AA+A)Z = (ZA)(A+A)A+(AA+)(AZ )

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis


Es gilt

Z(iii) für Z

= ZAZ(iii) für A

= ZAA+Az

(iv) für A= Z (AA+A)A+(AA+A)Z = (ZA)(A+A)A+(AA+)(AZ )

(i),(ii) für A,Z= (AHZH)(AH(A+)H)A+((A+)HAH)(ZHAH)

=(AHZHAH)(A+)HA+(A+)H(AHZHAH)

(iii) für Z= AH(A+)HA+(A+)HAH (i)

= A+AA+AA+ (iv)= A+AA+ = A.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(d) A++ = A, (A+)H = (AH)+.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

(d) A++ = A, (A+)H = (AH)+.

Setze in (c) A+ statt A. Die Matrix Z = A erfüllt dann(i)-(iv). Genauso argumentiert man bei (A+)H = (AH)+.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Korollar

Das Ausgleichsproblem

|Ax − y | → Min

wird durch x = A+y gelöst.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Korollar

Das Ausgleichsproblem

|Ax − y | → Min

wird durch x = A+y gelöst.

Unter allen Lösungen besitzt A+y die kleinste Norm.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Es giltmin |Ax − y |2 = min

y∈Bild (A)|y − y |2,

also y = Py .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis



also y = Py .

Wenn Ax = y , x ⊥ Kern (A), so folgt für beliebigesx ∈ Kern (A)

A(x + x) = y , |x + x |2 = |x |2 + |x |2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis



also y = Py .

Wenn Ax = y , x ⊥ Kern (A), so folgt für beliebigesx ∈ Kern (A)

A(x + x) = y , |x + x |2 = |x |2 + |x |2.

Also besitzt x unter allen Lösungen von Ax = y die kleinsteNorm.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Singulärwertzerlegung

A+ kann mit der Singulärwertzerlegung bestimmt werden. Sei

A = UΣV H

mit U ∈ Cm×m, V ∈ Cn×n unitär und Σ ∈ Cm×n mit

Σ =

[

D 0

0 0

]

, D = diag (σ1, . . . , σr ), σr > 0.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


A+ kann mit der Singulärwertzerlegung bestimmt werden. Sei

A = UΣV H

mit U ∈ Cm×m, V ∈ Cn×n unitär und Σ ∈ Cm×n mit

Σ =

[

D 0

0 0

]

, D = diag (σ1, . . . , σr ), σr > 0.

Setze

Σ+ =

[

D−1 0

0 0

]

∈ Cn×m, A+ = VΣ+UH ∈ Cn×m.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


Dann gilt

A+A = VΣ+UHUΣV H = V

[

Ir 0

0 0

]

V H ,

also (A+A)H = A+A.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


Dann gilt


[

Ir 0

0 0

]

V H ,

also (A+A)H = A+A.

Analog zeigt man AA+ = (AA+)H sowie

AA+A = UΣV HV

[

Ir 0

0 0

]

V H = A.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das


Dann gilt


[

Ir 0

0 0

]

V H ,

also (A+A)H = A+A.

Analog zeigt man AA+ = (AA+)H sowie

AA+A = UΣV HV

[

Ir 0

0 0

]

V H = A.

Damit sind die Bedingungen (b) (i)-(iv) des vorletzten Satzesalle erfüllt.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

9.5 Das nichtlineare Ausgleichsproblem

Sei m ≥ n und f : Rn → R

m stetig differenzierbar. Zuy ∈ Rn soll ein x ∈ Rn bestimmt werden mit

F (x) = |y − f (x)|2 → Min.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




F (x) = |y − f (x)|2 → Min.

Wir leiten ein Verfahren für dieses Problem durchLinearisierung her. Sei x eine Näherung. Aus derDifferenzierbarkeit von f folgt

f (x) = f (x) + fx(x)(x − x) + o(|x − x |).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




F (x) = |y − f (x)|2 → Min.

Wir leiten ein Verfahren für dieses Problem durchLinearisierung her. Sei x eine Näherung. Aus derDifferenzierbarkeit von f folgt

f (x) = f (x) + fx(x)(x − x) + o(|x − x |).

Wir bestimmen daher die Lösung von

minz∈Rn

|y − f (x)− fx(x)(z − x)|2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Abstiegsrichtung

minz∈Rn

|y − f (x)− fx(x)(z − x)|2.

Dies ist ein lineares Ausgleichsproblem.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Abstiegsrichtung

minz∈Rn

|y − f (x)− fx(x)(z − x)|2.


Beachte: Im Newton-Verfahren zur Bestimmung desMinimums von F (x) würde man eine Nullstelle von Fx(x)approximieren und bräuchte dazu die Hesse-Matrix Fxx .

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Abstiegsrichtung

minz∈Rn

|y − f (x)− fx(x)(z − x)|2.


Beachte: Im Newton-Verfahren zur Bestimmung desMinimums von F (x) würde man eine Nullstelle von Fx(x)approximieren und bräuchte dazu die Hesse-Matrix Fxx .

Ähnlich wie beim Newton-Verfahren können wir zeigen, dassdie Suchrichtung eine Abstiegsrichtung für das zuminimierende Funktional ist:

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Abstiegsrichtung

Lemma Sei rang fx(x) = n, z = x sei die eindeutigbestimmte Lösung des obigen linearen Ausgleichsproblemsund s = x − x die zugehörige Richtung.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Abstiegsrichtung

Lemma Sei rang fx(x) = n, z = x sei die eindeutigbestimmte Lösung des obigen linearen Ausgleichsproblemsund s = x − x die zugehörige Richtung.

Wenn s 6= 0, so gibt es ein λ0 > 0, so dass

φ(τ) = |y − f (x + τs)|2

in [0, λ0] streng monoton fallend ist.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Fast genauso wie im analogen Satz für das gewöhnlicheNewton-Verfahren erhalten wir

φ′(0) =d

dτ(y − f (x + τs)T (y − f (x + τs)

∣

∣

τ=0

= −(fx(x)s)T (y − f (x))− (y − f (x)T (fx(x)s)

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

Fast genauso wie im analogen Satz für das gewöhnlicheNewton-Verfahren erhalten wir

φ′(0) =d

dτ(y − f (x + τs)T (y − f (x + τs)

∣

∣

τ=0

= −(fx(x)s)T (y − f (x))− (y − f (x)T (fx(x)s)

= −2(fx(x)s)T (y − f (x))

= −2(fx(x)s)T r(x), r(x) = y − f (x).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

φ′(0) = −2(fx(x)s)T r(x), r(x) = y − f (x).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

φ′(0) = −2(fx(x)s)T r(x), r(x) = y − f (x).

Das lineare Ausgleichsproblem besitzt die Lösung s = x − x

mitfx(x)

T fx(x)s = fx(x)T r(x),

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beweis

φ′(0) = −2(fx(x)s)T r(x), r(x) = y − f (x).

Das lineare Ausgleichsproblem besitzt die Lösung s = x − x

mitfx(x)

T fx(x)s = fx(x)T r(x),

also

φ′(0) = −2sT fx(x)T r(x) = −2sT fx(x)fx(x)s

= −2|fx(x)s|2 < 0 falls rang fx(x) = n und s 6= 0.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Gauß-Newton Algorithmus

Wir erhalten damit den Gauß-Newton Algorithmus:

0) Sei x (0) ∈ Rn ein Startvektor. Sei x (i) bereits definiert.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das




1) Bestimme s(i) durch

mins∈Rn

|r(x (i))− fx(x(i))s|2, r(x (i)) = y − f (x (i)).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das





mins∈Rn


2) Seiφ(τ) = |y − f (x (i) + τs(i))|2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das





mins∈Rn


2) Seiφ(τ) = |y − f (x (i) + τs(i))|2.

Bestimme die kleinste Zahl k ∈ N0 mit φ(2−k) < φ(0)oder alternativ φ(τ) → Min für τ > 0 durch einLine-Search-Verfahren.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das





mins∈Rn


2) Seiφ(τ) = |y − f (x (i) + τs(i))|2.

Bestimme die kleinste Zahl k ∈ N0 mit φ(2−k) < φ(0)oder alternativ φ(τ) → Min für τ > 0 durch einLine-Search-Verfahren. Setze x (i+1) = x (i) + 2−ks(i)

oder alternativ = x (i) + τs(i).

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

Für Probleme der Art

yi =n∑

j=1

eαjxi , i = 1, . . . ,m

sind die Funktionalmatrizen meist sehr schlecht konditioniert.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

Für Probleme der Art

yi =n∑

j=1

eαjxi , i = 1, . . . ,m

sind die Funktionalmatrizen meist sehr schlecht konditioniert.

Für m = n = 2 erhalten wir beispielsweise

fα(α) =

[

x1eα1x1 x1e

α2x1

x2eα1x2 x2e

α2x2

]

.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

fα(α) =

[

x1eα1x1 x1e

α2x1

x2eα1x2 x2e

α2x2

]

.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

fα(α) =

[

x1eα1x1 x1e

α2x1

x2eα1x2 x2e

α2x2

]

.

Es ist

det fα(α) = x1x2

(

eα1x1+α2x2 − eα1x2+α2x1)

≈ 0 falls α1 ≈ α2 oder x1 ≈ x2.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Beispiel

fα(α) =

[

x1eα1x1 x1e

α2x1

x2eα1x2 x2e

α2x2

]

.

Es ist

det fα(α) = x1x2

(

eα1x1+α2x2 − eα1x2+α2x1)

≈ 0 falls α1 ≈ α2 oder x1 ≈ x2.

Die Normalgleichungen dürfen daher nicht mit einemVerfahren für f T

α fα gelöst werden.

Numerik von

Eigenwertproble-

men





Potenzmethoden

Grundlagen

Direkte Lösung

linearer Glei-

chungssysteme

Metrische und

normierte Räume

Nichtlineare Glei-

chungssysteme

Interpolation

Numerische

Integration

Theorie der Ei-

genwertprobleme

Das

Documents

Lineare Ausgleichsprobleme (=überbestimmte Gleichungssysteme)dobro/num1/f9.pdf · n zu ﬁnden (=Methode der kleinsten Quadrate). Numerik von Eigenwertproble-men Das Lanczos-Verfahren