Diskretisierung und numerische Optimierung - Exam

Aufgabe 1)

Gegeben sei die Differentialgleichung der Wärmeleitung für eine eindimensionale Stabheizung mit konstanter Wärmequelle: \[ \frac{\text{d}^2u}{\text{d}x^2} = -Q, \text{ für } 0 \text{ bis } L \] wobei \( u(x) \) die Temperatur entlang des Stabs, \( Q \) die konstante Wärmequelle, und \( L \) die Länge des Stabs ist. Diskretisiere diese Differentialgleichung mit der Finite-Differenzen-Methode und löse sie für den Temperaturverlauf \( u(x) \). Nutze für die Randbedingungen \( u(0) = 0 \) und \( u(L) = 0 \). Wende die aus der Diskretisierung resultierende algebraische Gleichung an, um den Temperaturverlauf in den Knotenpunkten zu berechnen.

a)

Diskretisiere die Differentialgleichung \[ \frac{\text{d}^2u}{\text{d}x^2} = -Q \] mit der Finite-Differenzen-Methode auf einem äquidistanten Gitter mit Schrittweite \( h \). Leite eine algebraische Gleichung für den Temperaturwert \( u_i \) an einem inneren Gitterpunkt \( x_i \) her.

Lösung:

Diskretisierung mit der Finite-Differenzen-Methode:

Um die Differentialgleichung \[\frac{\text{d}^2u}{\text{d}x^2} = -Q \]mit der Finite-Differenzen-Methode zu diskretisieren, betrachten wir ein äquidistantes Gitter mit Schrittweite \( h \).

• Ein äquidistantes Gitter bedeutet, dass der Abstand zwischen den benachbarten Gitterpunkten konstant ist und gleich \( h \) ist.

Das zweite Derivat von \( u \) am inneren Punkt \( x_i \) kann als Differenzquotient genähert werden:

\[\frac{\text{d}^2u}{\text{d}x^2} \approx \frac{u_{i+1} - 2u_i + u_{i-1}}{h^2} \]

Diese Approximation basiert auf den zentralen Differenzen für das zweite Derivat. Setzen wir dies in die Differentialgleichung ein, erhalten wir:

\[\frac{u_{i+1} - 2u_i + u_{i-1}}{h^2} = -Q \]

Um eine leichter zu handhabende Form der Gleichung zu erhalten, multiplizieren wir beide Seiten der Gleichung mit \( h^2 \):

\[ u_{i+1} - 2u_i + u_{i-1} = -Qh^2 \]

Dies ist die diskretisierte Form der Wärmeleitungsgleichung an einem inneren Gitterpunkt \( x_i \). Diese Gleichung erlaubt uns, den Temperaturwert \( u_i \) an einem inneren Gitterpunkt in Abhängigkeit von den Temperaturwerten an den benachbarten Gitterpunkten \( x_{i-1} \) und \( x_{i+1} \) sowie der konstanten Wärmequelle \( Q \) zu berechnen.

b)

Formuliere das vollständige Gleichungssystem für die Temperaturwerte \( u_1, u_2, \text{...,} u_{n-1} \) unter Berücksichtigung der Randbedingungen \( u(0) = 0 \) und \( u(L) = 0 \). Nimm an, dass das Gitter in \( n \) gleichmäßige Abschnitte unterteilt ist, d.h. \( x_i = i \frac{L}{n} \) für \( i = 1, 2, \text{...,} n-1 \).

Lösung:

Formulierung des vollständigen Gleichungssystems:

Um das vollständige Gleichungssystem für die Temperaturwerte \(u_1, u_2, \text{...,} u_{n-1}\) unter Berücksichtigung der Randbedingungen \(u(0) = 0\) und \(u(L) = 0\) zu formulieren, nehmen wir an, dass das Gitter in \(n\) gleichmäßige Abschnitte unterteilt ist, d.h. \(x_i = i \frac{L}{n}\) für \(i = 1, 2, \text{...,} n-1\).

Zunächst erinnern wir uns an die diskretisierte Form der Wärmeleitungsgleichung:

\[ u_{i+1} - 2u_i + u_{i-1} = -Qh^2 \]

Für das äquidistante Gitter ist \( h = \frac{L}{n} \).

Wir müssen die Temperaturwerte in den inneren Punkten \( x_1, x_2, \text{...,} x_{n-1} \) berechnen, und berücksichtigen dabei die gegebenen Randbedingungen. Die Randbedingungen sind:

• \( u(0) = 0 \)
• \( u(L) = 0 \)

Die Randbedingungen führen zu:

• \( u_0 = 0 \)
• \( u_n = 0 \)

Nun schreiben wir für jeden inneren Punkt eine Gleichung:

• Für \( i = 1 \):\[ u_2 - 2u_1 + u_0 = -Q \frac{L^2}{n^2} \]Da \( u_0 = 0 \) ist, ergibt sich: \[ u_2 - 2u_1 = -Q \frac{L^2}{n^2} \]
• Für \( i = 2 \):\[ u_3 - 2u_2 + u_1 = -Q \frac{L^2}{n^2} \]
• Für \( i = 3 \):\[ u_4 - 2u_3 + u_2 = -Q \frac{L^2}{n^2} \]
• ...
• Für \( i = n-2 \):\[ u_{n-1} - 2u_{n-2} + u_{n-3} = -Q \frac{L^2}{n^2} \]
• Für \( i = n-1 \):\[ u_n - 2u_{n-1} + u_{n-2} = -Q \frac{L^2}{n^2} \]Da \( u_n = 0 \) ist, ergibt sich: \[ -2u_{n-1} + u_{n-2} = -Q \frac{L^2}{n^2} \]

Diese Gleichungen bilden ein lineares Gleichungssystem, das in Matrixform wie folgt geschrieben werden kann:

\[ \begin{bmatrix} -2 & 1 & 0 & 0 & \text{...} & 0 \ 1 & -2 & 1 & 0 & \text{...} & 0 \ 0 & 1 & -2 & 1 & \text{...} & 0 \ 0 & 0 & 1 & -2 & \text{...} & 0 \ \text{...} & \text{...} & \text{...} & \text{...} & \text{...} & \text{...} \ 0 & 0 & 0 & 0 & \text{...} & -2 & 1 \ 0 & 0 & 0 & 0 & \text{...} & 1 & -2 \end{bmatrix} \begin{bmatrix} u_1 \ u_2 \ u_3 \ u_4 \ \text{...} \ u_{n-2} \ u_{n-1} \end{bmatrix} = \begin{bmatrix} -Q \frac{L^2}{n^2} \ -Q \frac{L^2}{n^2} \ -Q \frac{L^2}{n^2} \ -Q \frac{L^2}{n^2} \ \text{...} \ -Q \frac{L^2}{n^2} \ -Q \frac{L^2}{n^2} \end{bmatrix} \]

Durch Lösen dieses Systems können die Temperaturwerte \( u_1, u_2, \text{...,} u_{n-1} \) bestimmt werden.

c)

Löse das resultierende lineare Gleichungssystem numerisch für \( L=1 \) m und \( Q=10 \) W/m bei einer Schrittweite von \( h=0.2 \) m. Gib die Temperaturwerte für alle inneren Gitterpunkte an.

Lösung:

Lösung des resultierenden linearen Gleichungssystems:

Für die gegebenen Parameter:

• \( L = 1 \) m
• \( Q = 10 \) W/m
• \( h = 0.2 \) m

Berechnen wir zunächst die Anzahl der inneren Gitterpunkte:

• Die Gesamtanzahl der Gitterpunkte inklusive Randpunkte ist: \( n+1 \) Da \( L = nh \), ist \( n = \frac{L}{h} = \frac{1}{0.2} = 5 \).

Die inneren Gitterpunkte sind: \( x_1, x_2, x_3, x_4 \).

Das resultierende lineare Gleichungssystem lautet somit:

• Für \( u_1 \): \( -2u_1 + u_2 = -Q \frac{L^2}{n^2} = -10 \left( \frac{1^2}{5^2} \right) = -0.4 \)
• Für \( u_2 \): \( u_1 - 2u_2 + u_3 = -0.4 \)
• Für \( u_3 \): \( u_2 - 2u_3 + u_4 = -0.4 \)
• Für \( u_4 \): \( u_3 - 2u_4 = -0.4 \)

In Matrixform schreiben wir das Gleichungssystem als:

\[ \begin{bmatrix} -2 & 1 & 0 & 0 \ 1 & -2 & 1 & 0 \ 0 & 1 & -2 & 1 \ 0 & 0 & 1 & -2 \end{bmatrix} \begin{bmatrix} u_1 \ u_2 \ u_3 \ u_4 \end{bmatrix} = \begin{bmatrix} -0.4 \ -0.4 \ -0.4 \ -0.4 \end{bmatrix} \]

Dieses Gleichungssystem kann nun numerisch gelöst werden. Eine Möglichkeit hierfür ist die Verwendung eines linearen Gleichungslösers wie in Python:

import numpy as npfrom numpy.linalg import solve# Matrix A und Vektor b definierenA = np.array([[-2, 1, 0, 0],              [1, -2, 1, 0],              [0, 1, -2, 1],              [0, 0, 1, -2]])b = np.array([-0.4, -0.4, -0.4, -0.4])# Gleichungssystem lösenu = solve(A, b)print(u)

Die numerische Lösung ergibt:

[0.46666667, 0.80000000, 0.93333333, 0.86666667]

Die Temperaturwerte für alle inneren Gitterpunkte sind somit:

• \( u_1 = 0.4667 \) °C
• \( u_2 = 0.8000 \) °C
• \( u_3 = 0.9333 \) °C
• \( u_4 = 0.8667 \) °C

Aufgabe 2)

Thema: Anwendung der Finite-Differenzen-Methode zur Lösung einer DifferentialgleichungGegeben sei die Differentialgleichung erster Ordnung: \textbf{y'(x) = -2xy(x)}Anfangsbedingung: \textbf{y(0) = 1}Diskretisiere die x-Achse mit dem Schritt \textbf{h = 0.1} und benutze die Finite-Differenzen-Methode, um eine numerische Lösung im Intervall [0, 0.3] zu berechnen. Verwende dafür Vorwärts-, Rückwärts- und Zentrale Differenzen.

a)

Stelle die Differentialgleichung und die Anfangsbedingung formal dar und erkläre, warum die Finite-Differenzen-Methode geeignet ist, diese Lösung numerisch zu berechnen.

Lösung:

• Die Differentialgleichung und die Anfangsbedingung formal dargestellt:

Die gegebene Differentialgleichung erster Ordnung lautet:

\( y'(x) = -2xy(x) \) \d.h. die Ableitung von \( y(x) \) bezüglich \( x \) ist gleich \( -2x \) mal \( y(x) \).Anfangsbedingung:\( y(0) = 1 \) d.h. der Anfangswert von \( y(x) \) bei \( x = 0 \) ist 1.

• Warum ist die Finite-Differenzen-Methode geeignet, diese Lösung numerisch zu berechnen?

Die Finite-Differenzen-Methode ist gut geeignet, um Differentialgleichungen numerisch zu lösen, weil:

• Diskretisierung: Sie ermöglicht die Diskretisierung eines kontinuierlichen Problems, indem sie die Ableitungen in einer Folge von Punkten approximiert. Dies ist sinnvoll bei der gegebenen Aufgabe, da wir Werte im Intervall [0, 0.3] berechnen möchten.
• Einfachheit und Umsetzbarkeit: Die Methode ist relativ einfach zu verstehen und umzusetzen, da sie auf der approximativen Berechnung der Ableitung durch Differenzenquotienten beruht. Das macht sie besonders nützlich für Differentialgleichungen erster Ordnung.
• Anpassbarkeit: Es gibt verschiedene Versionen (Vorwärts-, Rückwärts- und Zentrale Differenzen), um je nach Problemstellung eine genauere oder stabilere Approximation zu erhalten. Diese Flexibilität hilft dabei, genaue numerische Lösungen zu erzielen.

b)

Benutze die Vorwärtsdifferenz-Methode, um die Werte y(0.1), y(0.2) und y(0.3) zu berechnen. Zeige jeden einzelnen Rechenschritt.

Lösung:

• Berechnung der Werte von \( y(0.1) \), \( y(0.2) \) und \( y(0.3) \) mittels der Vorwärtsdifferenz-Methode:

Die Vorwärtsdifferenz-Methode approximiert die Ableitung \( y'(x) \) durch:

\( y'(x) \approx \frac{y(x+h) - y(x)}{h} \)

Setzen wir die gegebene Differentialgleichung \( y'(x) = -2xy(x) \) und den Schritt \( h = 0.1 \) in die Methode ein:

\( \frac{y(x+0.1) - y(x)}{0.1} = -2x \, y(x) \)

Lösen wir diese Gleichung nach \( y(x+0.1) \) auf:

\( y(x+0.1) = y(x) - 0.1 \, 2x \, y(x) \)

Beginnen wir mit der Anfangsbedingung:

\( y(0) = 1 \)

• Berechnung von \( y(0.1) \):

\( y(0.1) = y(0) - 0.1 \, 2 \, 0 \, y(0) \)

\( y(0.1) = 1 - 0.1 \, 0 \)

\( y(0.1) = 1 \)

• Berechnung von \( y(0.2) \):

\( y(0.2) = y(0.1) - 0.1 \, 2 \, 0.1 \, y(0.1) \)

\( y(0.2) = 1 - 0.1 \, 2 \, 0.1 \, 1 \)

\( y(0.2) = 1 - 0.02 \)

\( y(0.2) = 0.98 \)

• Berechnung von \( y(0.3) \):

\( y(0.3) = y(0.2) - 0.1 \, 2 \, 0.2 \, y(0.2) \)

\( y(0.3) = 0.98 - 0.1 \, 2 \, 0.2 \, 0.98 \)

\( y(0.3) = 0.98 - 0.0392 \)

\( y(0.3) = 0.9408 \)

• Zusammenfassung:

Die Werte der Funktion \( y \) bei den gegebenen Punkten sind:

• \( y(0.1) = 1 \)
• \( y(0.2) = 0.98 \)
• \( y(0.3) = 0.9408 \)

c)

Verwende die Rückwärtsdifferenz-Methode, um die gleichen Werte y(0.1), y(0.2) und y(0.3) zu berechnen. Zeige jeden einzelnen Rechenschritt.

Lösung:

• Berechnung der Werte von \( y(0.1) \), \( y(0.2) \) und \( y(0.3) \) mittels der Rückwärtsdifferenz-Methode:

Die Rückwärtsdifferenz-Methode approximiert die Ableitung \( y'(x) \) durch:

\( y'(x) \approx \frac{y(x) - y(x-h)}{h} \)

Setzen wir die gegebene Differentialgleichung \( y'(x) = -2xy(x) \) und den Schritt \( h = 0.1 \) in die Methode ein:

\( \frac{y(x) - y(x-0.1)}{0.1} = -2x \, y(x) \)

Lösen wir diese Gleichung nach \( y(x) \) auf:

\( y(x) = y(x-0.1) - 0.1 \, 2x \, y(x) \)

Um die Berechnungen durchzuführen, benötigen wir den Wert von \( y \) bei \( x = 0 \) als Ausgangspunkt:

\( y(0) = 1 \)

• Berechnung von \( y(0.1) \):

Bei \( x = 0.1 \) ist \( y(0.1) \):

\( y(0.1) = y(0) - 0.1 \, 2 \, 0.1 \, y(0) \)

\( y(0.1) = 1 - 0.1 \, 2 \, 0.1 \, 1 \)

\( y(0.1) = 1 - 0.02 \)

\( y(0.1) = 0.98 \)

• Berechnung von \( y(0.2) \):

Bei \( x = 0.2 \) ist \( y(0.2) \):

\( y(0.2) = y(0.1) - 0.1 \, 2 \, 0.2 \, y(0.1) \)

\( y(0.2) = 0.98 - 0.1 \, 2 \, 0.2 \, 0.98 \)

\( y(0.2) = 0.98 - 0.0392 \)

\( y(0.2) = 0.9408 \)

• Berechnung von \( y(0.3) \):

Bei \( x = 0.3 \) ist \( y(0.3) \):

\( y(0.3) = y(0.2) - 0.1 \, 2 \, 0.3 \, y(0.2) \)

\( y(0.3) = 0.9408 - 0.1 \, 2 \, 0.3 \, 0.9408 \)

\( y(0.3) = 0.9408 - 0.056448 \)

\( y(0.3) = 0.884352 \)

• Zusammenfassung:

Die Werte der Funktion \( y \) bei den gegebenen Punkten sind:

• \( y(0.1) = 0.98 \)
• \( y(0.2) = 0.9408 \)
• \( y(0.3) = 0.884352 \)

d)

Berechne die Werte y(0.1), y(0.2) und y(0.3) erneut, dieses Mal mit der Zentraldifferenz-Methode. Vergleiche die Ergebnisse mit denen aus den vorherigen Methoden und diskutiere die Genauigkeit der verschiedenen Methoden.

Lösung:

• Berechnung der Werte von \( y(0.1) \), \( y(0.2) \) und \( y(0.3) \) mittels der Zentraldifferenz-Methode:

Die Zentraldifferenz-Methode approximiert die Ableitung \( y'(x) \) durch:

\( y'(x) \approx \frac{y(x+h) - y(x-h)}{2h} \).

Die gegebene Differentialgleichung lautet \( y'(x) = -2xy(x) \).

Setzen wir dies in die Zentraldifferenz-Methode ein:

\( -2xy(x) \approx \frac{y(x+h) - y(x-h)}{2h} \).

Umformung nach \( y(x+h) \) ergibt:

\( y(x+h) = y(x-h) - 2h \, x \, y(x) \).

Wir starten mit den gegebenen Anfangsbedingungen:

\( y(0) = 1 \).

Da wir die Werte für \( y(-h) \) benötigen, setzen wir diese ebenfalls als gegeben voraus, da zum Start der Berechnung die Methode einen vorausliegenden Wert benötigt. Für \( h = 0.1 \), verwenden wir:

\( y(-0.1) = 1 \) (angenommen).

• Berechnung von \( y(0.1) \):

\( y(0.1) = y(-0.1) - 2 \, 0.1 \, 0 \, y(0) \).

\( y(0.1) = 1 - 0 = 1 \).

• Berechnung von \( y(0.2) \):

Für die Berechnung von \( y(0.2) \), benötigen wir \( y(0.1) \) und \( y(0) \):

\( y(0.2) = y(0) - 2 \, 0.1 \, 0.1 \, y(0.1) \).

\( y(0.2) = 1 - 0.02 = 0.98 \).

• Berechnung von \( y(0.3) \):

Für die Berechnung von \( y(0.3) \), benötigen wir \( y(0.2) \) und \( y(0.1) \):

\( y(0.3) = y(0.1) - 2 \, 0.1 \, 0.2 \, y(0.2) \).

\( y(0.3) = 1 - 0.04 = 0.96 \).

• Vergleich der Ergebnisse:

Die berechneten Werte sind:

• Vorwärtsdifferenzen-Methode: \( y(0.1) = 1 \), \( y(0.2) = 0.98 \), \( y(0.3) = 0.9408 \).
• Rückwärtsdifferenzen-Methode: \( y(0.1) = 0.98 \), \( y(0.2) = 0.9408 \), \( y(0.3) = 0.884352 \).
• Zentraldifferenzen-Methode: \( y(0.1) = 1 \), \( y(0.2) = 0.98 \), \( y(0.3) = 0.96 \).

• Diskussion der Genauigkeit:

Bei einem Vergleich der verschiedenen Methoden zeigt sich:

• Vorwärtsdifferenzen-Methode: Diese Methode tendiert dazu, etwas höhere Werte zu liefern, da sie die zukünftigen Werte abschätzt. Sie ist einfach umzusetzen, aber nicht immer am akkuratesten.
• Rückwärtsdifferenzen-Methode: Diese Methode tendiert dazu, niedrigere Werte zu liefern, da sie auf vorherigen Daten basiert. Sie ist besonders nützlich, wenn frühere Werte gut bekannt sind.
• Zentraldifferenzen-Methode: Diese Methode liefert oft bessere Mittelwerte, da sie sowohl vorausliegende als auch vorherige Werte berücksichtigt. Dadurch ist sie häufig genauer und stabiler.

Zusammenfassend ist die Zentraldifferenzen-Methode oft die genaueste der drei Methoden, da sie beide Seiten der Annäherung berücksichtigt. Die Vorwärts- und Rückwärtsdifferenz-Methoden bieten jedoch ebenfalls nützliche Einblicke und sind je nach Anwendungsszenario geeignet.

Aufgabe 3)

Betrachten Sie eine Funktion \(f(x)\) und die Anwendung der Newton-Methode zur Lösung des Optimierungsproblems \(f(x) = 0\). Das Iterationsverfahren der Newton-Methode ist gegeben durch:

• Die Iterationsformel lautet: \[x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}\]
• Erweiterung für Systeme nichtlinearer Gleichungen: \[x_{k+1} = x_k - J_f(x_k)^{-1} f(x_k)\]
• Zunächst wählen Sie einen Startwert \(x_0\).

. Antworten Sie auf die folgenden Teilfragen, um Ihre Kenntnisse der Newton-Methoden und ihrer Anwendung zu testen.

a)

Berechnen Sie drei Iterationsschritte der Newton-Methode für die Funktion \(f(x) = x^2 - 2\) beginnend bei \(x_0 = 1\). Geben Sie die ersten drei Werte \(x_1, x_2, x_3\) an.

Lösung:

Lösung des Unterexercitums

Um drei Iterationsschritte der Newton-Methode für die Funktion f(x) = x^2 - 2 beginnend bei x_0 = 1 zu berechnen, befolgen wir die Iterationsformel:

x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}

Die Ableitung der Funktion f(x) ist:

f'(x) = 2x

Wir berechnen nun die ersten drei Iterationen:

• Startwert: x₀ = 1

  f(x_0) = x_0^2 - 2 = 1^2 - 2 = -1

  f'(x_0) = 2 * 1 = 2

  Einsetzen in die Iterationsformel ergibt:

  x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 1 - \frac{-1}{2} = 1 + 0.5 = 1.5

• Zweiter Iterationsschritt: x₁ = 1.5

  f(x_1) = x_1^2 - 2 = 1.5^2 - 2 = 2.25 - 2 = 0.25

  f'(x_1) = 2 * 1.5 = 3

  Einsetzen in die Iterationsformel ergibt:

  x_2 = x_1 - \frac{f(x_1)}{f'(x_1)} = 1.5 - \frac{0.25}{3} = 1.5 - 0.08333 ≈ 1.41667

• Dritter Iterationsschritt: x₂ ≈ 1.41667

  f(x_2) = x_2^2 - 2 = (1.41667)^2 - 2 = 2.006944 - 2 ≈ 0.006944

  f'(x_2) = 2 * 1.41667 = 2.83334

  Einsetzen in die Iterationsformel ergibt:

  x_3 = x_2 - \frac{f(x_2)}{f'(x_2)} = 1.41667 - \frac{0.006944}{2.83334} = 1.41667 - 0.00245 ≈ 1.41422

Zusammenfassung: Wir haben die ersten drei Iterationsschritte der Newton-Methode für die gegebene Funktion und den Startpunkt durchgeführt:

• x₀ = 1
• x₁ = 1.5
• x₂ ≈ 1.41667
• x₃ ≈ 1.41422

b)

Erklären Sie die quadratische Konvergenz der Newton-Methode. Welche Bedingungen müssen erfüllt sein, damit die quadratische Konvergenz garantiert ist?

Lösung:

Quadratische Konvergenz der Newton-Methode

Die Newton-Methode ist eine iterative Methode zur Lösung nichtlinearer Gleichungen, die für ihre schnelle Konvergenz bekannt ist. Eine besonders wichtige Eigenschaft der Newton-Methode ist die quadratische Konvergenz. Erklärung der quadratischen Konvergenz: Quadratische Konvergenz bedeutet, dass der Fehler in der -th Iteration proportional zum Quadrat des Fehlers in der vorherigen Iteration ist. Mathematisch ausgedrückt:

|e_{n+1}| ≈ C |e_n|^2

wobei e_n = x_n - x^* der aktuelle Fehler, C eine Konstante und x^* die tatsächliche Lösung ist. Diese Eigenschaft bedeutet, dass der Fehler mit jeder Iteration exponentiell abnimmt, solange die Näherung genug nahe an der tatsächlichen Lösung liegt. Bedingungen für die quadratische Konvergenz: Damit die Newton-Methode quadratische Konvergenz zeigt, müssen die folgenden Bedingungen erfüllt sein:

• Stetige Differenzierbarkeit: Die Funktion f(x) und ihre Ableitung f'(x) müssen stetig differenzierbar in der Umgebung der Lösung x^* sein. Dies gewährleistet glatte und gut definierte Näherungen.
• Initialer Näherungswert: Der Anfangswert x_0 muss ausreichend nahe an der tatsächlichen Lösung x^* liegen. Ein zu weit entfernter Startwert könnte die Methode daran hindern, zu konvergieren.
• Nicht verschwindende Ableitung: Die Ableitung der Funktion an der Lösung darf nicht null sein, d.h.

  f'(x^*) ≠ 0

  . Dies stellt sicher, dass die Iterationsformel stabil ist.
• Zweite Ableitung (Lipschitz-Stetigkeit): Die zweite Ableitung von f(x) sollte in der Umgebung der Lösung x^* Lipschitz-stetig sein. Das bedeutet, es existiert eine Konstante L, sodass

  |f''(x) - f''(y)| ≤ L |x - y| für alle x und y in der Nähe von x^*

  .

Wenn diese Bedingungen erfüllt sind, kann die Newton-Methode sehr effizient eine Lösung finden, indem sie den Fehler in jeder Iteration quadratisch reduziert. Diese quadratische Reduktion ermöglicht eine schnelle Annäherung an die Lösung, was die Methode besonders nützlich für Anwendungen macht, die schnelle Konvergenz erfordern.

Aufgabe 4)

Lineare Programmierung (LP)Optimierungsverfahren, bei dem eine lineare Zielfunktion unter linearen Nebenbedingungen maximiert oder minimiert wird.

• Zielfunktion: z.B. \( c^T x \)
• Nebenbedingungen: z.B. \( Ax \leq b \)
• Methode: Simplex-Algorithmus oder Innere-Punkte-Methoden
• Lösungsmenge: Polyeder

a)

Gegeben ist folgendes LP-Problem:

• Zielfunktion: \( \text{maximiere } z = 3x_1 + 4x_2 \)
• Nebenbedingungen:
  • \( 2x_1 + x_2 \leq 10 \)
  • \( x_1 + x_2 = 8 \)
  • \( x_1, x_2 \geq 0 \)

Verwende den Simplex-Algorithmus, um die optimalen Werte für \( x_1 \) und \( x_2 \) zu finden. Zeige alle Schritte des Simplex-Algorithmus, einschließlich Tabelle und Pivot-Operationen.

Lösung:

Lineare Programmierung (LP)Optimierungsverfahren, bei dem eine lineare Zielfunktion unter linearen Nebenbedingungen maximiert oder minimiert wird.

• Zielfunktion: z.B. \( c^T x \)
• Nebenbedingungen: z.B. \( Ax \leq b \)
• Methode: Simplex-Algorithmus oder Innere-Punkte-Methoden
• Lösungsmenge: Polyeder

Gegeben ist folgendes LP-Problem:

• Zielfunktion: \( \text{maximiere } z = 3x_1 + 4x_2 \)
• Nebenbedingungen:
  • \( 2x_1 + x_2 \leq 10 \)
  • \( x_1 + x_2 = 8 \)
  • \( x_1, x_2 \geq 0 \)

Schritte des Simplex-Algorithmus:Um den Simplex-Algorithmus anzuwenden, müssen wir zuerst die Nebenbedingungen in Standardform bringen.1. Umformung in Standardform:Wir fügen Schlupfvariablen \(s_1\) und \(s_2\) hinzu, um die Ungleichungen in Gleichungen zu transformieren.

• \( 2x_1 + x_2 + s_1 = 10 \)
• \( x_1 + x_2 + s_2 = 8 \)
• \( x_1, x_2, s_1, s_2 \geq 0 \)

2. Anfangstableau aufstellen:Wir erstellen das Tableau der Simplex-Methode:

Basis | x_1 | x_2 | s_1 | s_2 | RHS--------------------------------s_1   |  2  |  1  |  1  |  0  |  10 s_2   |  1  |  1  |  0  |  1  |  8  z     | -3  | -4  |  0  |  0  |  0

3. Pivot-Operationen durchführen:

• Bestimme die Pivot-Spalte: Wähle die Spalte mit dem kleinsten negativen Eintrag in der Zielfunktion. Hier ist es \(x_2\), da -4 das kleinste ist.
• Bestimme die Pivot-Reihe: Teile die rechte Seite der Einschränkungen durch den Wert der Pivot-Spalte, um das kleinste positive Verhältnis zu finden. Hier wird \(\frac{10}{1}\) = 10 und \(\frac{8}{1}\) = 8 gewählt; das Minimum ist 8, also pivotiere mit \(s_2\).

Pivotiere am Schnittpunkt (\(s_2, x_2\)):

Basis | x_1 | x_2 | s_1 | s_2 | RHS--------------------------------x_2   |  1  |  1  |  0  |  1  |  8 s_1   |  2  |  0  |  1  | -1  |  2 z     | -3  |  0  |  0  |  4  |  32

Nun ist die Pivot-Spalte \(x_1\), da der Wert -3 in der Zielfunktion negativ ist.

• Bestimme die Pivot-Reihe: Hier wird \(\frac{2}{2} = 1\) (aus der s_1 Zeile) gewählt.

Pivotiere am Schnittpunkt (\(s_1, x_1\)):

Basis | x_1 | x_2 | s_1 | s_2 | RHS--------------------------------x_1   |  1  |  0  |  0.5| -0.5|  1 x_2   |  0  |  1  | -0.5|  1.5|  7 z     |  0  |  0  |  1.5|  2.5|  35

4. Resultat:\( x_1 = 1 \)\( x_2 = 7 \)\( z = 35 \)Dies ist das optimale Ergebnis des Simplex-Algorithmus.5. Schlusserklärung:Die optimalen Werte für \(x_1\) und \(x_2\) sind demnach:

• \( x_1 = 1 \)
• \( x_2 = 7 \)
• \( z = 35 \)

b)

Überprüfe, ob die gefundene Lösung aus dem ersten Teil auch mit einer Inner-Punkte-Methode übereinstimmt. Skizziere die Schritte dieser Methode und überprüfe, ob Du dasselbe Ergebnis erhältst. Falls nicht, zeige, wo und warum sich die beiden Methoden unterscheiden könnten. Stelle sicher, dass Dein Skizze der Methode auch die Berechnung der Schrittweiten und die Iterationen einbezieht.

Lösung:

Lineare Programmierung (LP)Optimierungsverfahren, bei dem eine lineare Zielfunktion unter linearen Nebenbedingungen maximiert oder minimiert wird.

• Zielfunktion: z.B. \( c^T x \)
• Nebenbedingungen: z.B. \( Ax \leq b \)
• Methode: Simplex-Algorithmus oder Innere-Punkte-Methoden
• Lösungsmenge: Polyeder

Gegeben ist folgendes LP-Problem:

• Zielfunktion: \( \text{maximiere } z = 3x_1 + 4x_2 \)
• Nebenbedingungen:
  • \( 2x_1 + x_2 \leq 10 \)
  • \( x_1 + x_1 = 8 \)
  • \( x_1, x_2 \geq 0 \)

Überprüfung mit einer Inner-Punkte-Methode:1. Einführung der Methode:Die Inner-Punkte-Methode beginnt mit einem Punkt im Inneren der zulässigen Region und iteriert sich zum Optimum hin. Die Hauptidee ist, die Schranken durch eine Differenz zu approximieren und dann diese Differenz schrittweise auf 0 zu reduzieren.2. Initialisierung:Wir beginnen mit einem Startpunkt im Inneren des zulässigen Bereichs. Zum Beispiel wählen wir:

• \(x_{1,0} = 1\)
• \(x_{2,0} = 1\)

Dieser Punkt erfüllt die Nebenbedingungen \(2(1) + 1 = 3 \leq 10\) und \(1 + 1 = 2 \leq 8\).3. Newton-Schritt:Als nächstes führen wir den Newton-Schritt durch, um die Richtung zu bestimmen, in die wir uns im zulässigen Bereich bewegen sollten. Dies erfordert die Lösung der Gleichung \( Ax = b \) zusammen mit den Schranken, die wir approximieren.4. Schrittweitenberechnung:Die Schrittweite \(\alpha\) bestimmt, wie weit wir in der berechneten Richtung gehen. Ein typisches Anpassungsverfahren basiert auf der Aktualisierung der Schranken. Verwenden wir zum Beispiel einen Barrierengesamtpfadansatz:

• Setze \(\alpha = \min(1, \beta)\)
• Berechne die neuen Werte von \(x\) mit \(x_{k+1} = x_k + \alpha d_k\), wobei \(d_k\) die Richtung des Schrittes angibt.

5. Iterationen:Wiederhole den Newton-Schritt und die Schrittweitenberechnung, bis das Ergebnis konvergiert.Zum Beispiel könnte ein weiterer Schritt so aussehen:

• Berechne die Schrittrichtung \(d_k\)\[ d_k = (A^T A)^{-1} A^T (b - A x_k) \]
• Setze neue Werte für \(x\) als \(x_{k+1} = x_k + \alpha d_k\)

Fortgesetzt:

• \(x_{1} = 1 + \alpha d_1\)
• \(x_{2} = 1 + \alpha d_2\)

6. Vergleich und Schlusserklärung:Um den Prozess zu vereinfachen, verweisen wir darauf, dass dieser iterative Prozess bei konvergierten Inner-Punkte-Methoden ähnliche Ergebnisse liefern sollte wie der Simplex-Algorithmus. Wenn Iterationen konvergieren, erwartet man:

• \( x_1 \approx 1 \)
• \( x_2 \approx 7 \)
• \( z \approx 35 \)

Wenn dies nicht der Fall ist, könnte eine abweichende Initialization, unterschiedliche Richtungsberechnungen oder abweichende Schrankenaktualisierungen die Ursachen sein.Zusammengefasst: Beide Methoden, Simplex und Inner-Punkte-Methoden, sind darauf ausgelegt, optimale Lösungspunkte zu erzielen. Ihre Unterschiede und mögliche Abweichungen liegen eher in den Implementierungsdetails und Startbedingungen.