<<

. 15
( 31 .)



>>

˜˜ ˜
Qj A(j) = A(j) ’ uj sTj
˜
sT = βj uT A(j) .
j j
m
(uj sT )i,k
d.h. = aij βj alj alk
j
l=j

Programm QR(A,d)
Die uj stehen spaltenweise im linken Teil von A, R\diag(R) steht im rechten Teil
von A, diag(R) steht auf d = (d1 , . . . , dn ).
fur j = 1, . . . , n :
¨
1/2
m
a2
xnorm = ij
i=j
falls xnorm=0: ST OP
dj = ’sign(ajj ) · xnorm
beta = 1/(xnorm(|ajj | + xnorm))
ajj = ajj ’ dj
fur k = j + 1, . . . , n :
¨
m
s = beta · aij aik
i=j
fur i = j, . . . , m :
¨
aik = aik ’ aij · s.

3.6 Lineare Ausgleichsrechnung, diskrete Appro-
ximation
3.6.1 Normalgleichung
Ausgleichrechnungen sind fur viele praktische Zwecke besonders wichtig.
¨
Beispiel 3.41. Wir haben bei einem Experiment fur die Eingabewerte t1 , . . . , tm
¨
¨
Messwerte s1 , . . . , sm erhalten. Aufgrund theoretischer Uberlegungen (etwa phy-
sikalische Gesetze) kennt man eine Funktion f (t), fur die f (ti ) = si gelten soll.
¨
Lineare Ausgleichsrechnung 63




Die Funktion f h¨ngt aber in der Regel von unbekannten Parametern x1 , . . . , xn
a
ab; wir schreiben f (t; x) fur x = (x1 , . . . , xn )T um dies zu betonen. Beispielsweise
¨
k¨nnte f durch eine Parabel
o

f (t; x) = x1 + x2 t + x3 t2
(3.35)

gegeben sein. In der Regel hat man mehr Messwerte als Parameter (m > n) und
es liegen Messfehler vor, so dass der naheliegende Versuch durch L¨sen des m
o
dimensionalen (i.A. nichtlinearen) Gleichungssystems

f (t1 ; x) = s1
.
.
(3.36) .
f (tm ; x) = sm

den n dimensionalen L¨sungsvektor zu bestimmen scheitern muß.
o

In vielen praktischen F¨llen ist das Gleichungssystem (3.36) linear, so z.B. auch
a
fur die obige Parabel und wir erhalten aus (3.36) ein uberbestimmtes (i.A. nicht
¨ ¨
l¨sbares) LGS
o
Cx = s ,
mit C ∈ IRm—n , m ≥ n und s ∈ IRm .

Beispiel 3.42. Fur unser Beispiel einer Parabel in (3.35) erhalten wir etwa
¨
«  « 
1 t1 t2 s1
1
¬. . .· ¬.·
¬. . .· s = ¬ . ·.
C= . . und
. .
1 tm t2 sm
m


Anstelle also den (vermutlich vergeblichen Versuch) zu unternehmen, eine exakte
L¨sung x des Systems Cx = s zu ¬nden, begnugen wir uns damit, ein x zu
o ¨
¬nden, so daß Cx ˜m¨glichst nahe™ bei s liegt. Als Ersatzproblem betrachtet man
o
das Optimierungsproblem
2
(3.37) min s ’ Cx 2
n
x∈IR


Um eine L¨sung von (3.37) zu bestimmen, bildet man die erste Ableitung, die in
o
einem Minimum zwangsweise gleich Null sein muß.

‚ (s ’ Cx)T (s ’ Cx)
2
‚ s ’ Cx 2
= 2C T Cx ’ 2C T s.
0= =
‚x ‚x
64 Lineare Gleichungssysteme




Dies ergibt die Normalgleichung
C T Cx = C T s ,
(3.38)
die nach De¬nition von A := C T C und b := C T s dem LGS
Ax = b
entspricht.
Fur eine beliebige Matrix C ist die Losung von (3.38) nicht eindeutig und es gilt:
¨ ¨
Satz 3.43. Das lineare Ausgleichsproblem (3.37) besitzt mindestens eine L¨sung
o
x0 , d.h. C T Cx0 = C T s.
Beweisidee: Bild(C)

m
Cx 0
IR


s




o




Abbildung 3.5: Losung im Unterraum.
¨

Nach linearer Algebra gilt die Zerlegung IRm = Bild(C)•Kern(C T ). Daher kann
s ∈ IRm zerlegt werden in
C T r = 0,
s = y + r, y = Cx0 ,
und es folgt
C T s = C T y = C T Cx0 ,
d.h. x0 ist eine Losung des linearen Ausgleichsproblems. Wegen Kern(C T C) =
¨
Kern(C) pruft man nun leicht nach, dass
¨
x0 + Kern(C)
die Gesamtheit der Losungen ist:
¨
C T C(x0 + Kern(C)) = C T s
C T C(x0 + w) = C T s mit Cw = 0

C T Cx0 = C T s

Lineare Ausgleichsrechnung 65




3.6.2 Numerische Losung
¨
Von nun an sei rang (C) = n < m: Die Matrix C T C ist dann positiv de¬nit, und
die Normalgleichung C T Cx = C T s kann im Prinzip mit dem Cholesky“Verfahren
gel¨st werden. Dieses Verfahren hat jedoch zwei Nachteile:
o
(1) C T C ist schwierig auszurechnen, z. B.:
« 
11
1 + µ2 1
¬ ·
CT C =
C =  µ 0 , .
1 + µ2
1


Mit µ = 1 eps ist auf der Maschine
2

11
rd(C T C) = singular.
¨
11

(2) Die Kondition und damit die Emp¬ndlichkeit gegenuber St¨rungen in C, y
o
¨
betragt
¨
cond(C T C).

Beide Nachteile k¨nnen mit der Householder“Transformation vermieden werden.
o
Nach (3.34) gibt es eine QR-Zerlegung mit
R }n
QC =
} m’n
0
n

R obere regul¨re (n, n)-Dreiecksmatrix
a
Q orthogonale (m, m)-Matrix
Mit
h1
, h1 ∈ IRn , h2 ∈ IRm’n
Qs =
h2
berechnet man
2 2
s ’ Cx = Q(s ’ Cx)
2 2
2 2
= h1 ’ Rx + h2 .
2 2

Dieser Ausdruck wird minimal fur x ∈ IRn mit Rx = h1 . Die L¨sung des linearen
o
¨
Ausgleichsproblems ist also
x = R’1 h1 , s ’ Cx
(3.39) = h2 .
2 2

Die Kondition bei Anwendung der Householder-Transformation betr¨gt i.W. cond2 (R);
a
(vergleiche Stoer I, §4.8.3).
66 Lineare Gleichungssysteme




3.6.3 Diskrete Approximation
Als eine Anwendung der linearen Ausgleichsrechnung betrachten wir die diskrete
Approximation.
Zu n + 1 Basisfunktionen
f0 (t), f1 (t), . . . , fn (t)
und m ≥ n + 2 Meßpunkten

(ti , si ), i = 1, . . . , m

wird eine Linearkombination
n
f (t) = xk fk (t)
k=0


gesucht, die die Werte si in den Punkten ti m¨glichst gut ann¨hert. Dies fuhrt
o a ¨
(vergleichbar zu linearen Ausgleichsrechnung) auf das Optimierungsproblem
2
m n

<<

. 15
( 31 .)



>>