Upload
hoangdan
View
220
Download
0
Embed Size (px)
Citation preview
1
Information Retrieval und Vektoriteration: Vektorraummodell für ‚Data Mining‘
Liste von Dokumenten D1 , ... , Dn , z.B. WWW-Seiten Liste von Suchtermen T1 , ... , Tm , z.B. alphabetisch geordnet: Aachen, ABC, Auto, Bar, ... , Zug
Jeder Suchbegriff erscheint in jedem Dokument mit einem Bestimmten Gewicht, z.B. Gewicht ∼ Häufigkeit.
Sammle diese Gewichte in der sog. Term-Dokument-Matrix (dünnbesetzte Matrix). j-ter Spaltenvektor dieser Matrix listet für das j-te Dokument Dj die darin enthaltenen Suchworte ! Vektor dj . k-ter Zeilenvektor tk listet für den k-ten Suchbegriff die relevanten Dokumente auf.
2
Vergleich zweier Dokumente auf Ähnlichkeit: Dokument Di repräsentiert durch Vektor der darin enthaltenen Suchbegriffe di , entsprechend dj .
D1 D2 D3 . . . .T1 . . T2 . .
nahe bei 1.
Vektoren ähnlich (kollinear), wenn Winkel zwischen ihnen sehr klein, d.h.
cos('(di, d j)) =dT
i d j
kdik2 · kd jk2
3
Eine Suchanfrage ist ein Spaltenvektor d und entspricht quasi einem Dokument, das mit anderen Dokumenten auf Ähnlichkeit verglichen werden soll. Berechne Vektor t = dT*D = (dT*D1 dT*D2 ..) . Große Komponenten tj entsprechen Dokumenten Dj , die mit der Suchanfrage am besten übereinstimmen.
di
dj ϕ
Matrix D enthält sehr viel ‚Rauschen’, (zufälliges Auftreten von Suchtermen in Dokumenten, Wortwahl, ...) Modellreduktion: Ersetze D durch System, das die wesentlichen Eigenschaften repräsentiert:
4
!!"
#$$%
&=
22
1211
0 RRR
R
Verbesserung durch Pivotsuche: D*P=Q*R mit allgemeiner QR-Zerlegung incl. Permutation liefert und neues tTTPRQD ⋅⋅= ~:~
Berechne QR-Zerlegung von D : D=QR Partitioniere R in der Form
dabei sei R22 gleich Null oder mit kleinen Einträgen. Dann repräsentieren die Zeilen von R22 ‚linear abhängige’ Such- begriffe, die eigentlich überflüssig sind.
Ddt TT ~⋅= DdT ⋅
( ) ( )121111211
211211
0000:~ RRQ
RRQQ
RRQD ⋅=""
#
$%%&
'=""
#
$%%&
'=
und untersuche anstatt
Ersetze D durch die Approximation kleinen Ranges:
5
Andere Methode des ‚Denoising’ mittels Eigenwerten: Betrachte Singulärwertzerlegung von A: A = U D V, dabei sind U und V Eigenvektormatrizen von ATA und AAT, und D ist eine rechteckige Diagonalmatrix, deren Diagonaleinträge >= 0 sind:
mit Singulärwerten σj >0, Rang(A)=k.
A = U
0BBBBBBBBBBBBB@
�1 0 · · · 0 · · · 0
0. . .
. . ..........
.... . . �k 0 · · · 0
1CCCCCCCCCCCCCA
V
6
D~Ersetze D durch , indem kleine σj durch 0 ersetzt werden.
Ergibt neue Matrix (Term-Dokument-Tabelle)
VDUA ~~ = mit kleinerem Rang:
Diese neue Matrix enthält wieder die wesentliche Information von A . A = UDV heißt Singulärwertzerlegung von A. Und ergibt sich aus der Eigenwert-Zerlegung von ATA, bzw. AAT .
Zusammenfassung
• Newton-Verfahren zur Nullstellenbestimmung / Minimierung • Nichtlineare Ausgleichsrechung • iterative Methoden zum Lösen von lin. Gleichungssystemen • Jacobi- und Gauß-Seidel-Verfahren • Gradientenabstieg und Conjugate Gradient • Vektoriteration • Anwendung: neuronale Netze
7
VII. Numerische Behandlung von Differentialgleichungen
Gewöhnliche Diff’gleichungen (erster Ordnung)
Diff’gleichungsproblem allgemein: Aus Beziehungen zwischen den Änderungen (Ableitungen) und den Funktionswerten soll eine gesuchte Funktion bestimmt werden!
),( xyy ϕ="
Aufgabe: Funktion y(x) nur implizit gegeben durch Bedingungen an die Ableitung y’ ! y ??
! y(x) ?
Ableitung von y(x) nach x in jedem möglichen Punkt (x,y) ist gegeben durch Funktion ϕ(x,y).
Frage: Warum Differentialgleichungen?
9
Beispiel: Freier Fall
Kugel wird aus Höhe h0 losgelassen zum Zeitpunkt t0 = 0 mit Anfangsgeschwindigkeit v0 = 0, Erdbeschleunigung g.
v(t) = s(t) =dsdt,
�g = v(t) =dvdt= s(t) =
d2sdt2 .
Diff’gleichung für v(t): v(t) = '1(v, t) = �g (= ¨s(t))
Integration ! v(t) =Z t
0v(⌧)d⌧ =
Z t
0(�g)d⌧ = �gt
10
Diff’gleichung für s(t):
Aus Anfangswerten t0 = 0 und h0, und aus der Bedingung für die Ableitung wird die Funktion selbst bestimmt.
In dieser einfachen Form explizit lösbar durch Quadratur!
Im Allgemeinen ist das Integral nicht direkt lösbar, oder Diff’gleichung kann nicht auf Integral zurückgeführt werden.
s(t) = '2(s, 1) = v(t) = �gt
Integration ! s(t) = h0 +
Z t
0(�g⌧)d⌧ = h0 �
12
gt2
11
Definition: Anfangswertproblem (AWP)
Aus Anfangswert y(x0 ) = y0 und Differentialgleichung y’(x) = ϕ(y,x) soll die Funktion y(x) für x > x0 bestimmt werden.
Dabei ist die Diff’gleichung hier in expliziter Form gegeben, d.h. in der Form: y’(x) = ...
Impliziter Fall: ϕ(y’,y,x) = 0 ! y ??? ( Beispiel implizit: y’*exp(y’) = y+x )
12
00 )(),()( yxyundyxyxy ===! αϕ
dtydy
dxydy
ydxdy
x
x
xy
xy ∫∫ =
⋅=⇔=
00
)(
)(α
αα
Beispiel für explizit lösbare Diff’gleichung:
Lösung durch Integration (“Separation”, ohne Beweis)
)())(ln())(ln( 00 xxxyxy −=− α
)(0
0)( xxeyxy −= αund daher
13
Geometrische Problemstellung:
Von einer Funktion sind alle möglichen Ableitungswerte an allen möglichen Stellen (x,y) bekannt (also an allen potentiellen Funktionswerten) Dies entspricht einem Vektorfeld von Tangentenrichtungen
Weiterhin bekannt ist der Funktionswert an einer Stelle x0 .
Gesucht: Kurve, deren Tangenten in allen Punkten dem vorgegebenen Vektorfeld entspricht!
14
Die Lösungskurve ist dann die Gerade mit Steigung -g durch den Nullpunkt, also v(t) = -gt .
Im Beispiel ‚Freier Fall’ ist dieses Vektorfeld trivial:
In der (t,v)-Ebene ist jede Tangentenrichtung durch den Vektor (1,v’)T gegeben, also hier durch den Vektor (1,-g)T .
v’=0: Tangentenvektor (1,0)T
Kurve (t,v)"!v(t)
Tangentenvektor (t,v)‘ = (1,v‘)
v(t) = �g, v(t0) = 0
15
00 )(),()( yxyundxyxy ==! ϕ
Das Eulerverfahren:
Gegeben AWP Anfangswertproblem
Gesucht: y(x) für x ≥ x0
),())(()()( 0000100111 xyhyxxxyyxgyxy ϕ⋅+=−$+==≈
Dadurch erhält man den Näherungswert
Wir wollen y(x) bei x0 lokal als lineare Funktion g(x) betrachten, und einen kleinen Schritt der Länge h zu x1 = x0 + h entlang dieser linearen Näherung gehen.
16
),(;);( 1100 kkkkkk xyhyyhxxxyy ϕ⋅+=+== ++
Ersetze wieder Funktion lokal durch Tangentengerade!
Dies ergibt die Iterationsvorschrift des Eulerverfahrens (Vorwärts-Euler):
Der Einfachheit halber wählen wir die Schrittweite h konstant (muss aber nicht sein).
für k=0,1,...
17
] ).,()()),(()()( 0001011
0
1
0
1
0xyxxdxxxydxxyxyyy x
xxx
xx ϕϕ ⋅−≈∫=∫ &==−
Euler aus Integration:
Betrachte die Diff’gleichung zwischen den Stellen x0 und x1 :
aus Rechteckregel, indem die Fläche unter der Kurve ϕ(y(x),x) angenähert wird durch die Fläche des Rechtecks mit den Ecken (x0,0), (x1,0), und (x1,ϕ(y0,x0)), (x0,ϕ(y0,x0)).
18
)(2
)()()()( 0
2
0001 zyh
xyhxyhxyxy !!+!+=+=
Eulerverfahren aus Taylorentwicklung :
Bekannt sind y(x0) = y0, y’(x0) = ϕ(y0,x0), mit Zwischenstelle z0. Der h2-Term ist klein und wird vernachlässigt ! Eulerverfahren.
hyy
xxyy
dxdy
yxyx
01
01
01000
0
),( −=
−
−≈#$
%=&=ϕ
ergibt wieder das Eulerverfahren!
Euler aus der Diskretisierung des Differentialquotienten:
19
hyy
xxyy
dxdyyxy
x
01
01
01111
1
),( −=
−−
≈#$
%=&=ϕ
Verbesserte Verfahren:
Rückwärts-Euler:
Der Diff’quotient kann natürlich mit derselben Berechtigung angenähert werden durch
),( 111 +++ ⋅+= kkkk xyhyy ϕDies führt zu der Vorschrift
Im Unterschied zum einfachen Euler taucht hier die Unbekannte yk+1 auch noch in der Funktion ϕ auf; das macht die Sache komplizierter.
20
0),()(!
1 =−⋅−= + kk yxzhzzf ϕ
Die berechnete Nullstelle z ist dann die nächste Näherung
)( 11 ++ ≈= kk xyyz
Um yk+1 zu erhalten, ist die Nullstelle einer Funktion zu bestimmen, nämlich von
Solche Verfahren heißen implizite Verfahren, im Gegensatz zum einfachen Eulerverfahren, das ein explizites Verfahren ist. Zur Bestimmung von yk+1 kann man iterative Verfahren wie z.B. das Newtonverfahren verwenden.
Explizites Euler als „Predictor“ liefert Startwert für implizites Euler / Newtonverfahren als „Corrector“
21
)(6
)(2
)()()()( 0
3
0
2
0001 zyhxyhxyhxyhxyxy !!!+!!+!+=+=
Weitere Taylorpolynom-Verfahren:
Berücksichtigung höherer Terme in der Taylorentwicklung:
xy
xyxdx
dyxy
yxxy
dxd
dxyd
xy
∂
∂+
∂
∂=
=∂
∂+⋅
∂
∂==
#=##
ϕϕ
ϕ
ϕϕϕ ),(),()),(()(
Hier taucht aber die unbekannte Ableitung y’’(x0) auf. Sie kann berechnet werden aus
Benötigt: Partielle Ableitungen, Nachdifferenzieren (Kettenregel)
mit Zwischenstelle z0.
22
] ] ),(00),(0 0000),(),(),()( xyxy xy
xxyxy
yxy ϕϕϕ
∂
∂+⋅
∂
∂=$$
!!"
#$$%
&
∂
∂+⋅
∂
∂++=+ ),(),(),(2
),(2
1 kkkkkkkkkk xyx
xyxyy
hxyhyy
ϕϕ
ϕϕ
Also
und damit
Auf diese Art können beliebig hohe Ableitungen der Lösungs- funktion y an einer Stelle (yk , xk) auf Ableitungen der Funktion ϕ zurückgeführt werden. Die nächste Iterierte erhält man aus dem Anfang der Taylorentwicklung an der letzten Stelle xk. Man spricht hier auch von Einschrittverfahren da stets yk!yk+1
23
Beispiel:
;0)0(;),()('
=
==
yyxxyxy ϕ
( ) ( )
( ) );1(')),((
;),(;),(
2 +=+=∂
∂+⋅
∂
∂=
=∂
∂=
∂
∂=
∂
∂=
∂
∂
xyyyxxx
yy
xxydxd
yyxx
xyx
xyxy
xyy
ϕϕϕ
ϕϕ
( )( ) ;22
112
),(),(),(2
),(
222
22
2
1
!!"
#$$%
&+++=+++=
=!!"
#$$%
&
∂
∂+⋅
∂
∂++=+
kkkkkkkk
kkkkkkkkkk
xhh
hxyxyh
xhyy
xyx
xyxyy
hxyhyy
ϕϕ
ϕϕ
Lösung:
;2
exp)()(
2))(ln())(ln(
20
2
0
2
0
0
!!"
#$$%
& −=⇒
)*
+=−⇒⋅=
xxxyxy
xxyxydxx
ydy
x
x
24
Mehrschrittverfahren
Hier wird aus mehreren schon berechneten Iterierten das nächste yk+1 gewonnen, also yk+1-m , … , yk-1 , yk ! yk+1 .
),(211 kkkk xyhyy ϕ+= −+Also
]
),()(
)),((
)()()()(
11
11
1
1
1
1
1
1
kkkk
x
x
x
x
xxkk
xyxx
dxxxy
dxxyxyxyxy
k
k
k
k
k
k
ϕ
ϕ
⋅−≈
≈=
=%==−
−+
−+
∫
∫+
−
+
−
+
−
Solche Verfahren können sehr einfach aus Quadraturregeln hergeleitet werden, z.B.
25
AWP für Diff’gleichungen erster Ordnung im Rn:
Also
mit vorgegebenem Startvektor
Sei y(x) = (y1(x) . . . y
n
(x))T
y
0(x) = (y01(x) . . . y0n
(x))T = '(y, x) =
= ('1(y1, . . . , yn
, x), . . . ,'n
(y1, . . . , yn
, x))T
y(x0) = (y1(x0) . . . yn
(x0))T
Lösung genauso durch Euler:
y
k+1 =
0BBBBBBBBBB@
y
k+11...
y
k+1n
1CCCCCCCCCCA=
0BBBBBBBBBB@
y
k
1...
y
k
n
1CCCCCCCCCCA+ h ·
0BBBBBBBBBB@
'1(yk
1, . . . , yk
n
, xk
)...
'n
(yk
1, . . . , yk
n
, xk
)
1CCCCCCCCCCA
26
AWP für Diff’gleichungen höherer Ordnung:
Gegeben eine Bedingung für die j-te Ableitung der Funktion y(x)
mit Anfangswerten0BBBBBBBBBB@
y
( j�1)(x0)...
y(x0)
1CCCCCCCCCCA=
0BBBBBBBBBBB@
y
( j�1)0...
y0
1CCCCCCCCCCCA
d
j
dx
j
y(x) = y
( j)(x) = (y( j�1), . . . , y, x)
27
Umformulieren in Diff’gleichung erster Ordnung im Rj :
Definiere dazu Vektorfunktion u(x) = ( u1(x), ... , uj(x) )T und setze u1(x) := y(x) , u2(x) := y’(x) , … uj(x) := y(j-1)(x) .
Damit erhalten wir für u(x)
u
0(x) =
0BBBBBBBBBBBBBBBB@
u
01(x)...
u
0j�1(x)u
0j
(x)
1CCCCCCCCCCCCCCCCA=
0BBBBBBBBBBBBBBB@
u2(x)...
u
j
(x) (u
j
, . . . , u1, x)
1CCCCCCCCCCCCCCCA= '(u, x)
28
),(1k
kkk xuhuu ϕ⋅+=+
mit Anfangsbedingungen
Insgesamt kann man nun wieder das Vektor-Euler-verfahren anwenden:
u(x0) =
0BBBBBBBBBB@
u1(x0)...
u
j
(x0)
1CCCCCCCCCCA=
0BBBBBBBBBB@
y(x0)...
y
( j�1)(x0)
1CCCCCCCCCCA=
0BBBBBBBBBBB@
y0...
y
( j�1)0
1CCCCCCCCCCCA
29
Fehleranalyse: Start bei a = x0 , Gesuchter Wert b = xn ,
Bei äquidistanter Einteilung ist Schrittweite h := (b-a)/n Damit xj = x0 + jh, j=0,1,...,n
Also der Fehler, der in einem Schritt von (y(xk), xk) nach (yk+1,xk+1) entsteht.
y(xk) ist dabei der exakte Wert einer Lösung, nicht yk!
kkk exyy =− ++ )( 11
Definition lokaler Diskretisierungsfehler:
An der Stelle xk ist der lokale Diskret.-Fehler gegeben durch
30
nnnn gxyybyy =−=− )()(
Definition globaler Diskretisierungsfehler:
Für das AWP zur Bestimmung der Lösung an der Stelle b ist der globale Diskret.-Fehler gegeben durch
)(lim,0
byynnh
=∞→→
Definition der Konvergenz:
Die durch unser Lösungsverfahren erzeugte Folge heißt konvergent, wenn gilt
31
Wenn also in exakter Arithmetik bei immer feineren Unterteilungen der Näherungswert gegen den exakten Wert konvergiert.
Das bedeutet natürlich auch, dass der globale Fehler gegen 0 gehen muss!
Lokaler Diskretisierungsfehler
a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8
h
y(x1)
y1
Lokaler Diskretisierungsfehler
a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8
h h
y(x2)
y2
Lokaler Diskretisierungsfehler
a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8
h h h
y(x3)
y3
Lokaler Diskretisierungsfehler
globaler Diskreti- sierungs- Fehler
a= x0 x1 x2 x3 x4 x5 x6 x7 b=x8
h h h
y(b)
y8
36
An jeder Stelle xk treten neue lokale Fehler auf und addieren sich zum globalen Fehler. Um insgesamt Konvergenz zu erhalten, muss also das Verfahren so sein, dass - lokal ein genügend kleiner Fehler entsteht (Konsistenz) und - sich diese lokalen Fehler nur zu einem kleinen globalen Fehler aufsummieren (Stabilität).
Nur so ist für den globalen Fehler O(h2)n = O(h) erreichbar!
)()( 211 hOxyy =−
Definition Konsistenz:
Ein Verfahren heißt konsistent, wenn der lokale Diskretisierungsfehler mindestens von der Ordnung h2 ist, also
Ist mit p≥1 ,
so heißt das Verfahren von der Ordnung p.
Offensichtlich ist das Eulerverfahren konsistent von Ordnung 1, da gilt
37
)()( 111
+=− phOxyy
)(21),()()( 2
000111 zyhxyhyxyyxy !!=−−=− ϕ
mit einer Zwischenstelle z.
Zur Untersuchung der Stabilität beschränken wir uns auf den ‚linearen’ Spezialfall y’ = ϕ(y,x) = λy mit Lösung y(x)=y0exp(λx)
Stabilität bei Diff’gleichungen im Rn:
38
.)1()1(
,)1()1(
,)1(),(
01
02
1112
00001
yhyhy
yhyhyhyy
yhxyhyy
kkk λλ
λλλ
λϕ
+=+=
+=+=+=
+=+=
−
Für |1+hλ|>1 wird daher die Näherungslösung yk immer größer.
mit Lösung :
00 )(),()( yxyundyxyxy ===! λϕ
)(0
0)( xxeyxy −= λ
Für die berechneten Näherungslösungen gilt beim Eulerver. auf
Problem: Divergenz bei zu großer Schrittweite h! Wie groß kann man h wählen?
39
Kritisch ist der Fall λ < 0 :
Die exakte Lösung geht gegen 0,
die Näherungslösung aber nur dann, wenn |1+hλ| < 1 gilt,
d.h. nur wenn h < 2 / |λ|
Für |1+hλ|<1 geht die Näherungslösung yk gegen 0. Stimmt dieses Verhalten mit der tatsächlichen Lösung überein?
Im Fall λ > 0 zeigen also exakte und Näherungslösung dasselbe Verhalten.
0)(:0
)(:0
limlim
=⇒<
∞=⇒>
∞→
∞→
xy
xy
x
x
λ
λ
Für die tatsächliche Lösung y(x) = y0 exp(λx) gilt
40
Dies ist die Stabilitätsbedingung, die garantiert, dass eine beschränkte exakte Lösung auch durch eine beschränkte Näherungslösung approximiert wird, und der globale Fehler nicht zu stark anwachsen kann.
kk hyy)1(
0
λ−=
Führen wir dieselbe Untersuchung für das implizite (Rückwärts) – Euler –Verfahren durch, so erhält man die Näherungslösungen von der Form
Also ist für λ < 0 das Eulerverfahren nur konvergent, wenn die Schrittweite h so klein gewählt ist, dass h < 2 / |λ| gilt !
41
Im kritischen Fall λ < 0 gilt hier unabhängig von h
0)1(
0limlim =−
=∞→∞→
kk
kk h
yyλ
Das implizite Eulerverfahren erfüllt für alle h die Stabililtätsbedingung, nämlich dass exakte und Näherungs-lösung für λ < 0 beschränkt bleiben!
42
Anwendungsbeispiel:
Räuber-Beute-Modell
Einfaches Modell, das die Populationsänderung in einem ‚Primitiv-Ökosystem’, bestehend aus genau einer Räuberspezies und einer Beutespezies, beschreibt.
Viele Räuber ! Beute nimmt ab Wenig Räuber ! Beute nimmt zu
Viel Beute ! Räuber nehmen zu Wenig Beute ! Räuber nehmen ab
43
Änderung der Anzahl Beutetiere x(t) ist zum einen durch die Geburtenrate a proportional der Anzahl Beutetiere, und zum anderen führt eine Begegnung eines Beutetiers mit einem Räuber (y(t)) zu einer Verringerung (mit Sterberate b):
Man erhält also zur Beschreibung der zeitlichen Änderung der Population von Räuber und Beute ein DGL-System:
x(t) = ax � byx
Andererseits erhöht sich die Räuber-Geburtenrate durch viele Beutetiere, während die Abnahme der Räuber von ihrer Sterberate d abhängt:
y(t) = cxy � dy
44
0000 )()( ytyundxtx ==mit Startwerten
Fixpunkte dieser Vektoriteration: (x,y)=( d/c, a/b )
iiiii
iiiii
dyycxyy
ybxaxxx
−=−
−=−
+
+
τ
τ1
1
Eulerverfahren mit Schrittweite τ liefert dafür die Formel:
oder( )( )iiiii
iiiii
dyycxyyybxaxxx
−+=
−+=
+
+
τ
τ
1
1
y(t) = cx(t)y(t) � dy(t)
x(t) = ax(t) � bx(t)y(t)fur t0 t tn
45
Beute
Räuber
Populationsverlauf: Parameter: a=.3, b=.025, c=.0015, d=.2
http://www.leinweb.com/snackbar/wator/
Fixpunkt
Fixpunkt