17
10. November, 2004 Anfang 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.

Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

Embed Size (px)

Citation preview

Page 1: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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.

Page 2: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

10. November, 2004Anfang Präsentation

Übersicht

• Nichtlineare Gleichungssysteme

• Newton Iteration

• Newton Iteration mit Aufschneiden

• Newton Iteration linearer Gleichungssysteme

Page 3: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

10. November, 2004Anfang Präsentation

Nichtlineares Gleichungssystem: Ein Beispiel I

Page 4: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 5: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 6: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 7: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 8: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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:

Page 9: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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) =

Page 10: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 11: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 12: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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 ))

Page 13: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 14: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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.

Page 15: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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.

Page 16: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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

Page 17: Anfang Präsentation 10. November, 2004 Lösung nichtlinear Gleichungssysteme In dieser Vorlesung werden wir uns mit der gemischt symbolischen und numerischen

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.