Upload
lythuan
View
216
Download
0
Embed Size (px)
Citation preview
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)