Wenn Euler und Newton gemeinsam Nullstellen gesucht hätten · Newton-Raphson Methode Traditionelle...

Wenn Euler und Newton gemeinsam Nullstellen

gesucht hätten

Thomas P. Wihler Mathematisches Institut

Universität Bern

Eine klassische Aufgabe

Gegeben: Eine differenzierbare Funktion

mit Nullstelle .

Gesucht: Eine numerische Näherung von .

f : [a, b] ! R

x

x 2 (a, b)

Newton-Raphson MethodeTraditionelle Sicht

Newton-Raphson-Methode:

a b

x

f

x0x1

Thomas Wihler Euler und Newton beim Kochen

xn+1 = xn � f(xn)

f

0(xn), n = 0, 1, 2, . . .

Effizienz und Zuverlässigkeit

Zwei wichtige Merkmale:

• Lokal: Quadratische Konvergenz in der Nähe der Nullstellen

• Global: Chaotisches Verhalten

Klassisches Beispiel: in . f(z) = z3 � 1 C

Chaotisches Verhalten

Nichtlineare SystemeBetrachte das nichtlineare Gleichungssystem

Beispiel: Die Gleichung in entspricht dem 2x2-System

d.h.

F : Rn ! Rn, F (x) = 0

z3 � 1 = 0 C

x

31 � 3x1x

22 � 1 = 0

3x21x2 � x

32 = 0.

F (x1, x2) =

✓x

31 � 3x1x

22 � 1

3x21x2 � x

32

◆.

Jede Funktion beschreibt eine Strömung in (Vektorfeld)

Die Nullstellen von sind die Fixpunkte der Strömung

Eine neue Sicht: Vektorfelder

F : Rn ! Rn

Rn

F

Klassisches Beispiel: Vektorfeld

−3 −2 −1 0 1 2 3−3

−2

−1

0

1

2

3

z3 � 1 = 0

Klassisches Beispiel: Richtungsfeld

−3 −2 −1 0 1 2 3−3

−2

−1

0

1

2

3

z3 � 1 = 0

Trajektorien

in der Strömung sind Lösungskurven des Differenzialgleichungssystems

Differenzialgleichungen und Vektorfelder

x : t 7! x(t)

x(t) = F (x(t))

Tangential-vektor

Vektorfeld

• Wähle einen Startwert in der Nähe einer Nullstelle von .

• Finde die Lösung des Systems

• Berechne den Grenzwert

Problem: Die Fixpunkte sind typischerweise nicht anziehend!

Ein (theoretischer) Nullstellenlöser

x1 = limt!1

x(t)

x(t) = F (x(t)), x(0) = x0

Fx0

Linearisiere das Vektorfeld beim Fixpunkt

=> Das Verhalten von in der Nähe des Fixpunktes wird wesentlich durch die Jacobimatrix beschrieben:

Ein Fixpunkt ist genau dann anziehend, wenn alle Eigenwerte von negativen Realteil haben.

Wann ist ein Fixpunkt anziehend?

F

x

F

DF

F (x) ⇡ F (x)| {z }=0

+DF (x) · (x� x)

DF

Modifikation: Transformiere das System so, dass

• alle Fixpunkte erhalten bleiben

• alle Fixpunkte anziehend sind

Newton-Raphson-Transformation

x(t) = F (x(t))

Newton-Raphson-Transformation (NRT):

Eigenschaften:

• Für lineare Vektorfelder gilt:

• Bei einem Fixpunkt gilt:

Newton-Raphson-Transformation

NF = �Id

D(NF )(x) = �Idx

N : F 7! NF := �DF�1 · F

Klassisches Beispiel: Richtungsfeld

−1.5 −1 −0.5 0 0.5 1

−1

−0.5

0

0.5

1

• Wähle einen Startwert in der Nähe einer Nullstelle von .

• Finde die Lösung des Systems

• Berechne den Grenzwert

“Continuous Newton-Raphson Method”

x1 = limt!1

x(t)

F

x0

x(t) = NF (x(t)), x(0) = x0

Explizites Euler-Verfahren

• Löse das Newton-Raphson-System mithilfe einer elementaren Approximationsmethode (hohe Genauigkeit ist nicht erforderlich)

• Wähle einen diskreten Zeitschritt sowie diskrete Zeitpunkte

• Approximiere mittels Differenzialquotient:

h > 0

x(tn)

x(tn) ⇡x(tn + h)� x(tn)

h

t0 = 0, t1 = h, t2 = 2h, . . . , tn = nh

Explizites Euler-Verfahren

• Es gilt:

• Definiere die diskrete Iteration:

• Für erhalten wir die klassische Newton-Raphson-Methode:

x(tn + h)� x(tn)

h⇡ NF (x(tn)), n = 0, 1, 2, . . .

xn+1 = xn + h ·NF (xn), n = 0, 1, 2, . . .

h = 1

xn+1 = xn �DF

�1(xn) · F (xn), n = 0, 1, 2, . . .

Newton-Raphson-Methode

• Vorteile:— alle regulären Nullstellen sind anziehend — für liegt typischerweise quadratische Konvergenz vor

• Nachteile:— durch die NRT können neue Singularitäten in der diskreten Iteration erzeugt werden— Chaotisches Verhalten wegen grosser “Updates”:

xn+1 = xn � h ·DF

�1(xn) · F (xn), n = 0, 1, 2, . . .

h = 1

Klassisches Beispiel: Vektorfeld

−1.5 −1 −0.5 0 0.5 1

−1

−0.5

0

0.5

1

Klassisches Beispiel: Attraktorwechsel

x1

x2

x3

x4x0 = (�0.5, 0.1)

“Gedämpfte” Newton-Raphson-Methode

• Abhilfe: Wähle den Zeitschritt klein genug, sodass das Updatevon kontrollierbarer Grösse ist.

• Beachte: — Wähle wenn immer möglich (quad. Konvergenz)— Reduziere nur dort wo (und so stark wie) nötig, um Singularitäten in zu berücksichtigen.

h = 1

�h ·DF

�1(xn) · F (xn)

h = hn

hDF

Adaptive Newton-Raphson-Methode

• Newton-Raphson-Methode mit Schrittweiten-steuerung:

• Wie wird automatisch gewählt? Die diskrete (numerische) Trajektorie soll der exakten Trajektorie “nahe genug” folgen.

xn+1 = xn � hn ·DF

�1(xn) · F (xn), n = 0, 1, 2, . . .

hn

Klassisches Beispiel: Adaptive Lösung

−0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 1.2−0.1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9Reference solution (h<<1)Adaptive Newton methodStandard Newton method

starting point

Adaptive Newton-Raphson-Methode

• Newton-Raphson-Methode mit “Zwischen-schritt”:

• A posteriori Fehlerschranke:

x(tn + hn)� xn+1| {z }lokaler num. Fehler

⇡ 2(exn+1

� xn+1

)| {z }berechenbar

.

xn+ 12= xn � hn

2·NF (xn)

exn+1 = xn+ 1

2� hn

2·NF (xn+ 1

2)

A posteriori FehlerschrankeA posteriori Fehlerschatzung

xn = x(tn)

x∞

xn+1/2

xn+1

!xn+1

x(tn + hn)

Thomas Wihler Euler und Newton beim Kochen

Adaptive Newton-Raphson-Methode• Fixiere eine Toleranz , wähle einen Startwert sowie

die anfängliche Schrittweite

• In jedem Schritt berechne (aus ):

• Fallsdann reduziere und berechne denselben Schritt nochmals; ansonsten setze

⌧ > 0x0

h0 = 1

xn

xn+1, exn+1

kxn+1 � exn+1k � ⌧

hn hn

2

hn+1 = min(2hn, 1)

Klassisches Beispiel mit Adaptivität

⌧ = 0.1

Klassisches Beispiel mit Adaptivität

traditionelle NR-Methode

adaptive NR-Methode

durschnittliche Rate 1.73 1.91

durchschnittliche # Iterationen 17.14 9.13% konvergente Iterationen 90.40% 99.64%

Statistik im Bereich [�5, 5]⇥ [�5, 5]

Ein “Benchmark” Problem

Die nichtlineare Funktion

hat 6 Nullstellen im Bereich .

F : R2 ! R2, F (x, y) =

✓exp(x

2+ y

2)� 3

x+ y � sin(3(x+ y))

◆

[�1.5, 1.5]2

Ein “Benchmark” Problem

!1.5 !1.0 !0.5 0.0 0.5 1.0 1.5

!1.5

!1.0

!0.5

0.0

0.5

1.0

1.5

!1.5 !1.0 !0.5 0.0 0.5 1.0 1.5

!1.5

!1.0

!0.5

0.0

0.5

1.0

1.5

Ein “Benchmark” Problem

⌧ = 0.1

Für Experten: Abstraktere Anwendungen

• Adaptive Newton-Methoden lassen sich auch in abstrakten Banachräumen formulieren (z.B. für nichtlineare Differenzialgleichungen)

• In Kombination mit numerischen Diskretisierungsverfahren entstehen zuverlässige praktische Löser für praxis- relevante Anwendungen

A1654 MARIO AMREIN AND THOMAS P. WIHLER

102

103

104

105

10−2

10−1

100

101

degrees of freedom

error estimatorN−1/2

103

104

105

10−2

10−1

100

101

degrees of freedom

error estimatorN−1/2

Fig. 5. Example 4.10: Two different numerical solutions of the Ginzburg–Landau prob-lem (4.19) (top) and the corresponding performances of the fully adaptive Newton–Galerkin method(bottom) with ε = 0.00025 for different initial guesses.

global number of iterations5 10 15 20 25

step

siz

es

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

global number of iterations5 10 15 20 25 30 35

step

siz

es

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Fig. 6. Example 4.10: The step size ∆t versus the global number of iterations for the twodifferent solutions displayed in Figure 5.

indicate (optimal) convergence of order 1/2 with respect to the number of degrees offreedom, N , as expected.

Again we depict in Figure 6 the step size factors versus the total number ofNewton iterations. Furthermore, in this example, the ratio between the number ofrefinements and the global number of Newton iterations is approximately 3/2. As inExample 4.9 we notice that the Newton step size is 1 close to the solution.

5. Conclusions. The aim of this paper was to introduce a reliable and compu-tationally feasible procedure for the numerical solution of general, semilinear ellipticboundary value problems with possible singular perturbations. The key idea is to

"�u(x, y)� u(x, y)3 + u(x, y) = 0 �1 x, y 1

Abstraktere Anwendungen

Ginzburg-Landau-Gleichung:

Schlussbemerkungen• “Continuous Newton Method”: Nullstellensuche mit Differenzialgleichungen

• Vektorfelder: Qualitatives Verständnis

• Numerische Lösung: Quantitative Berechnungen mithilfe von diskreten Iterationen

• Analytische Lösungsmethoden: weder anwendbar noch notwendig

Vektorfelder und diskrete Iterationen sind schultauglich!

Schülerforschung• Was passiert, wenn Heun und Newton

gemeinsam Nullstellen suchen?

• Wie misst man Effizienz und Zuverlässigkeit?

• Wie ist die Toleranz zu wählen (z.B. in Bezug auf die Lage der Nullstellen)?

• Nullstellen höherer Ordnung oder Nullstellen mit Co-Dimension 1?

• Matlab/Octave-Implementierung

⌧ > 0

Literatur• H.R. Schneebeli & TW The Newton-Raphson Method and Adaptive ODE Solvers Fractals (2011)

• M. Amrein & TWAn adaptive Newton-method based on a dynamical systems approach Commun. Nonlinear Sci. Numer. Simul. (2014)

• M. Amrein & TWFully adaptive Newton-Galerkin methods for semilinear elliptic partial differential equations SIAM J. Sci. Comput. (2015)

• M. Amrein & TWAn Adaptive Space-Time Newton-Galerkin Approach for Semilinear Singularly Perturbed Parabolic Evolution Equations IMA JNA (2016)