Vortrag zum Thema

Kleinste Quadrate von Christian Patitz

1. Geschichte

2. Lineare Ausgleichsprobleme

3. Das Kleinste Quadrate Problem

4. Lösung von linearen Ausgleichsproblemen

5. Logarithmische Kleinste Quadrate

1. Geschichte

Gauß beschreibt die „Methode der kleinsten Fehlerquadrate“ erstmals 1809.

Er stand vor dem Problem eine Anzahl von physikalischen Meßpunkten

durch eine lineare Funktion zu beschreiben.

Da diese Meßpunkte jedoch fehlerhaft waren und der Idealfall i.d.R. auch

unter „Laborbedingungen“ nicht zu erreichen war, blieb die Aufgabe, eine

Gerade so durch den Nullpunkt zu legen, daß sie dem Verlauf der

Messungen „möglichst nahe“ kommt.

2. Lineare Ausgleichsprobleme

Ausgangspunkt ist ein überbestimmtes lineares GleichungssystemAx = b

mit gegebener Matrix ARm x n , bRm , wobei m n.

Das heißt, die Anzahl m der Gleichungen ist im allgemeinen größerals die Anzahl n der Variablen.

Es kann also nicht von der Existenz einer exakten Lösung des linearen Gleichungssystems ( im Folgenden mit LGS bezeichnet )

Ax = bausgegangen werden.

Man fragt daher nach einer Lösung, die diesem LGS „möglichst gut“genügt.

3. Das Kleinste Quadrate Problem

Wenn der Defekt ( auch Residuum genannt ) Ax – b durch

die Euklidische Norm || . ||2 gemessen wird, spricht man von einem

linearen Ausgleich nach der „Methode der kleinsten Quadrate“ und

nennt

( LA ) minimiere || Ax – b ||2 mit xRn

ein lineares Ausgleichsproblem.

Eigenschaften

• x*Rn ist genau dann eine Lösung von ( LA ), wenn

ATAx* = ATb ,

d.h. wenn die Normalengleichungen erfüllt sind.

• Die Menge L der Lösungen von ( LA ) ist nicht leer.

• ( LA ) besitzt genau dann eine eindeutige Lösung, wenn

Rang ( A ) = n .

• Unter allen Lösungen aus L gibt es genau eine mit minimaler

Euklidischer Norm.

4. Lösung von linearen Ausgleichsproblemen

Um lineare Ausgleichsprobleme der Form

minimiere || Ax – b ||2 mit xRn

zu lösen, muß man 2 Fälle unterscheiden.

Fall I

Rang ( A ) = nLösung erfolgt mittels QR – Zerlegung

Eine alternative Lösung ist über die Normalengleichungen möglich.

Fall II

Rang ( A ) = r < n

Lösung mittels Singulärwertzerlegung

Lösung mittels QR - ZerlegungProblem: ( LA ) minimiere || Ax – b ||2 mit xRn

Es sei eine QR – Zerlegung der Matrix A gegeben!

A = QR ist eine QR – Zerlegung von A, wenn es eine orthogonale

Matrix QRmxm und eine Matrix R der Form R = gibt,

wobei R1Rnxn eine obere Dreiecksmatrix ist.

Es folgt die Anwendung von QT auf b.

Daraus ergibt sich der Vektor QTb =

Durch Rückwärtseinsetzen erhält man R1x = c

und kann dadurch die eindeutige Lösung des Problems ( LA ) bestimmen.

0

1R

d

c

Lösung mittels Normalengleichungen

Problem: ( LA ) minimiere || Ax – b ||2 mit xRn

x ist genau dann eine Lösung von ( LA ), wenn es

die Normalengleichung

ATAx = ATb

erfüllt.

Der „Kleinste Quadrate - Fehler“ errechnet sich aus

r = b – Ax .

Lösung mittels SingulärwertzerlegungProblem: ( LA ) minimiere || Ax – b ||2 mit xRn

Für ARmxn existieren orthogonale Matrizen

U = ( u1,...,um) Rmxm

V = ( v1,...,vn ) Rnxn derart,

UTAV =

wobei 1 2 ... r > 0

0000

0000

00

001

r

für beliebiges xRn gilt dann

|| Ax – b ||22 = (i ( VTx)i – uiTb )2 + ( ui

Tb )2

x löst ( LA ), wenn

VTx = mit r+1,..., nR

die minimale Lösung von ( LA )

x = V

Kennt man also die Singulärwertzerlegung von ARmxn,so kann man für beliebige bRm alle Lösungen von ( LA )angeben.

r

i 1

m

ri 1

T

nr

Tr

T bubu

,...,,,..., 1

11

1

T

r

Tr

T bubu

0,...,0,,...,

1

1

5. Logarithmische Kleinste Quadrategegeben sei eine Bewertungsmatrix mit

aij > 0

aii = 1

aij = 1 / aji

Diese Matrix A heißt widerspruchsfrei, wenn ein positiver Vektor

X = [ x1,x2,…,xn ] existiert, für den gilt:

Der Vektor x würde in diesem Fall die Rangordnung angeben.

Eine empirisch ermittelte Matrix ist aber i.a. nicht widerspruchsfrei.

Man nutzt nun die Logarithmischen Kleinsten Quadrate um zu einer

vorgegebenen Bewertungsmatrix A eine möglichst „nahe gelegene“

widerspruchsfreie Bewertungsmatrix zu ermitteln.

nxnRA

nji ,1

j

iij x

xa nji ,1

Man schreibt also aij

daraus folgt

log a12 = log x1 – log x2

log a13 = log x1 – log x3

log a1n = log x1 – log xn

log an-1,n = log xn-1 – log xn

Man erhält also wieder eine überbestimmte Matrix mit

Gleichungen für n Unbekannte yi.

j

i

x

x

2

1nn

ij

y

j

y

i axx

ji

logloglog

1100

10010

0

101

00110

1001

0

01

1001

0101

00011

ny

y

1

nn

n

n

a

a

a

a

a

a

,1

2

23

1

13

12

log

log

log

log

log

log

Benennt man die einzelnen Teile der Matrix A um, so kann man auch

schreiben

Daraus folgt

Oder

1

2

1

B

B

B

A n

n

j

n

j

Tj

T BBAA

1

1

11

11

111

1

1

111

nI

n

n

AAT

Die Lösung des Problems erfolgt nun über die Normalengleichung

ATA = ATb

Neues Problem: ATA besitzt keinen vollen Rang, sondern

Rang ( ATA ) = n-1.Es existiert keine eindeutige Lösung.

Man interpretiert die Lösung als x = y + N ( ATA )

Kleinste – Quadrate – Lösung zu ATA = ATb

= eine spezielle Lösung + alles aus N ( ATA )

= eine spezielle Lösung +

e R

Anwendung

der „e - Funktion“

Da der Faktor die Rangordnung nicht ändert, erhält man nun

einen Vektor , der eine „faire“ Rangordnung zur

gegebenen Matrix A angibt.

nx

x

log

log 1

exx

exx

nn

logexp

logexp 11

e

ex

ex

x

n

1

Quellen:

- Prof.Dr.rer.nat.habil. Michael Eiermann

( Technische Universität Bergakademie Freiberg )

- Jochen Werner „Numerische Mathematik 1“

( vieweg studium 32 )

- WorldWideWeb