Upload
heinrich-katch
View
105
Download
2
Embed Size (px)
Citation preview
10. November, 2004Anfang Präsentation
Lösung nichtlinear Gleichungssysteme
• In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen Lösung algebraisch gekoppelter nichtlinear Gleichungs- systeme befassen.
• Die Aufschneidemethode eignet sich auch zur effizienten Behandlung nichtlinear Gleichungs- systeme.
• Die numerische Iteration nichtlinear Gleichungs- systeme kann auf die Schnittvariablen begrenzt werden.
10. November, 2004Anfang Präsentation
Übersicht
• Nichtlineare Gleichungssysteme
• Newton Iteration
• Newton Iteration mit Aufschneiden
• Newton Iteration linearer Gleichungssysteme
10. November, 2004Anfang Präsentation
Nichtlineares Gleichungssystem: Ein Beispiel I
10. November, 2004Anfang Präsentation
Nichtlineares Gleichungssystem: Ein Beispiel II
p2
p0
Stausee Schleuse
Verbrau-cher I
Verbrau- cher II
Umgebungs- druck
p1
q1
q3
q2
10. November, 2004Anfang Präsentation
Nichtlineares Gleichungssystem: Ein Beispiel III
q
p
q: Durchflussratep: Druckabfall
q
p
q = k · sign(p ) · p
p = sign(q) · q2 / k
10. November, 2004Anfang Präsentation
Nichtlineares Gleichungssystem: Ein Beispiel IV
p2
p0
Stausee Schleuse
Verbrau-cher I
Verbrau -cher II
Umgebungs-druck
p1
q1
q3
q2
p2 = 100
p0 = 1fS(q1 ,p1 ,p2) = 0fI(q2 ,p0 ,p1) = 0fII(q3 ,p0 ,p1) = 0q1 = q2 + q3
10. November, 2004Anfang Präsentation
Nichtlineares Gleichungssystem: Ein Beispiel V
p2 = 100
p0 = 1fS (q1 ,p1 ,p2 ) = 0fI (q2 ,p0 ,p1 ) = 0fII (q3 ,p0 ,p1 ) = 0q1 - q2 - q3 = 0
p2 = 100
p0 = 1fS (q1 ,p1 ,p2 ) = 0fI (q2 ,p0 ,p1 ) = 0fII (q3 ,p0 ,p1 ) = 0q1 - q2 - q3 = 0
Nichtlineares Gleichungssystem in 4 Unbekannten
10. November, 2004Anfang Präsentation
Newton’sches Iterationsverfahren I
f(x) = 0 x n f n
x 0
x i+1 = x i - x i
H n
n
x i = H(x i )-1 · f(x i )
x n
H(x) =f(x)x
Nichtlineares Gleichungssystem:
Anfangsschätzwert:
Iterationsformel:
Inkrement:
Hess’sche Matrix:
10. November, 2004Anfang Präsentation
Newton’sches Iterationsverfahren: Beispiel I
x =
p1
q1
q2
q3
p2 - p1 - sign(q1) · q12 / k1
p1 – p0 - sign(q2) · q22 / k2
p1 – p0 - sign(q3) · q32 / k3
q1 - q2 - q3
f(x) = = 0
- 2|q1 |/k1
- 2|q2 |/k2
- 2|q3 |/k3
-1110
001
0
0-1
00
-1
H(x) =
10. November, 2004Anfang Präsentation
Newton’sches Iterationsverfahren II
x i = H(x i )-1 · f(x i )
H(x i ) · x i = f(x i )
x n
Bestimmung des Inkrements:
Lineares Gleichungssystem
in den Unbekannten x
10. November, 2004Anfang Präsentation
Newton Iteration mit Schneideverfahren I
Wahl
p2 = 100
p0 = 1fS (q1 ,p1 ,p2 ) = 0fI (q2 ,p0 ,p1 ) = 0fII (q3 ,p0 ,p1 ) = 0q1 - q2 - q3 = 0
p2 = 100
p0 = 1fS (q1 ,p1 ,p2 ) = 0fI (q2 ,p0 ,p1 ) = 0fII (q3 ,p0 ,p1 ) = 0q1 - q2 - q3 = 0
p2 = 100
p0 = 1fS (q1 ,p1 ,p2 ) = 0fI (q2 ,p0 ,p1 ) = 0fII (q3 ,p0 ,p1 ) = 0q1 - q2 - q3 = 0
10. November, 2004Anfang Präsentation
Newton Iteration mit Schneideverfahren II
p2 = 100
p0 = 1fS (q1 ,p1 ,p2 ) = 0fI (q2 ,p0 ,p1 ) = 0fII (q3 ,p0 ,p1 ) = 0q1 - q2 - q3 = 0
p2 = 100
p0 = 1q1 = q2 + q3
p1 = f1 (q1 ,p2 )q2 = f2 (p0 ,p1 )q3 = f3 (p0 ,p1 )
q1 = f2 (p0 ,p1 ) + f3 (p0 ,p1 )= f2 (p0 , f1 (q1 ,p2 ) ) + f3 (p0 , f1 (q1 ,p2 ))
10. November, 2004Anfang Präsentation
Newton Iteration mit Schneideverfahren III
q1 = f2 (p0 ,p1 ) + f3 (p0 ,p1 )= f2 (p0 , f1 (q1 ,p2 ) ) + f3 (p0 , f1 (q1 ,p2 ))
x = q1 f(x) = q1 - f2 (p0 , f1 (q1 ,p2 ) ) - f3 (p0 , f1 (q1 ,p2 )) = 0
H(x i ) · x i = f(x i )
Lineares Gleichungssystem
in den Unbekannten x x
1
10. November, 2004Anfang Präsentation
Newton’sches Iterationsverfahren: Beispiel IIp2 = 100
p0 = 1q1 = q2 + q3
p1 = p2 - sign(q1 ) · q12 / k1
q2 = k2 · sign(p1 - p0 ) · p1 - p0
q3 = k3 · sign(p1 - p0 ) · p1 - p0
pq1q1 = 1pp1q1 = - 2|q1| / k1
pq2q1 = k2 / ( 2 · p1 - p0 ) · pp1q1
pq3q1 = k3 / ( 2 · p1 - p0 ) · pp1q1
f = q1 - q2 - q3
h = pq1q1 - pq2q1 - pq3q1
Das Substituieren von Aus-drücken lohnt sich kaum je. Es ist besser, über alle Glei-chungen zu iterieren und bei der Ermittlung der partiellen Ableitungen jede Gleichung separat abzuleiten.
10. November, 2004Anfang Präsentation
Newton’sches Iterationsverfahren: Beispiel III
q1 = Anfangsschätzwertdx = 1while dx > dxmin p1 = p2 - sign(q1 ) · q1
2 / k1
q2 = k2 · sign(p1 - p0 ) · p1 - p0
q3 = k3 · sign(p1 - p0 ) · p1 - p0
pp1 = - 2|q1| / k1
pq2 = k2 / ( 2 · p1 - p0 ) · pp1
pq3 = k3 / ( 2 · p1 - p0 ) · pp1
f = q1 - q2 - q3
h = 1 - pq2 - pq3
dx = h \ f q1 = q1 – dxend
Es wird über alle Gleichungen iteriert. Das interne lineare Gleichungssystem muss jedoch nur für die Schnittvariablen gelöst werden.
10. November, 2004Anfang Präsentation
Newton Iteration für lineare Systeme
Lineares System: A·x = b
f(x) = A·x – b = 0
H(x) = f(x)/ x = A
A·x = A·x – b
x = x – A-1·b
x 1 = x 0 – (x 0 – A-1·b) = A-1·b
Die Newton Iteration konvergiert in einem Schritt
10. November, 2004Anfang Präsentation
Zusammenfassung• Das Schneideverfahren eignet sich genau so gut für nichtlineare
wie für lineare Systeme.• Die Νewton’sche Iteration eines nichtlinearen Gleichungs-
systems führt intern zur Lösung eines linearen Gleichungssystems. Die Hess’sche Matrix dieses Glei-chungssystems erstreckt sich nur über die Schnittvariablen.
• Die Νewton’sche Iteration kann auch sehr effizient im Falle grösserer linearer Systeme eingesetzt werden, da sie (bei korrekter Berechnung der H(x) Matrix) in einem einzigen Schritt konvergiert.
• In Praxis wird die H(x) Matrix jedoch häufig numerisch ermittelt und nur angenähert.
• Es ist aber möglich, symbolische Formelmanipulations- techniken zu entwickelt, welche symbolische Ausdrücke für die Elemente der Hess’schen Matrix ermitteln.