{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Programmieraufgabe 6: Das Newton-Verfahren " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# some setup\n", "%matplotlib inline\n", "import numpy as np \n", "import matplotlib.pyplot as plt " ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "In dieser Aufgabe werden wir das Newton-Verfahren (in einer Dimension) implementieren und an einigen Beispielen testen. Für eine differenzierbare Funktion $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ ist das Newtonverfahren mit Startwert $x_0$ durch folgende Iterationsvorschrift definiert: \n", "\n", "$x_{n+1} = N(x_n) := x_n - \\frac{f(x_n)}{f'(x_n)}$\n", "\n", "Zumindest die Aufgaben a),b),c),e) und f) sollten damit auch ohne theoretisches Vorwissen aus der Mittwochs-Vorlesung bearbeitet werden können. \n", "\n", "a) Implementieren Sie das Newton-Verfahren in einer Funktion \"newton\", die als Parameter eine Funktion $f$, deren Ableitung $f'$ sowie einen Startwert $x_0$, eine Schranke $itmax$ für die Anzahl der Iterationen sowie eine gewünschte Genauigkeit $\\varepsilon$ erhält. Ausgegeben werden soll die letzte Iterierte, ein array, das alle Iterierten enthält, sowie ein Boolwert, der \"Erfolg\" oder \"Nicht Erfolg\" anzeigt. Dabei soll das Verfahren erfolgreich abbrechen, wenn eine Iterierte $x_n$ die Bedingung $\\lvert f(x_n)/f'(x_n) \\rvert < \\varepsilon$ erfüllt bzw. andernfalls erfolglos abbrechen, wenn $itmax$-viele Iterationen durchgeführt wurden. " ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def newton(f, df, x0, itmax, epsilon):\n", " \n", " # to be done... \n", " \n", " return xfinal, xarray, success \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "b) Man implementiere eine Funktion, die für eine gegebene Funktion $f$ und ein array von Startwerten jeweils maximal $itmax$ Newton-Iterationen mit Abbruchgenauigkeit $\\epsilon$ für $f$ durchführt. Ausgegeben werden sollen zwei Arrays: eines, das jeweils die letzte Iterierte enthält, sowie eines, das \"1\" for Konvergenz bzw. \"0\" für Nicht-Konvergenz enthält. \n" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [], "source": [ "def p(x):\n", " return x**3 - 2*x + 2\n", "def dp(x):\n", " return 3*x**2 - 2 \n", "\n", "def newton_test(f, df, startarray, itmax, epsilon):\n", "\n", " # to be done ... \n", " \n", " return xfinalarray, successarray " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "c) Untersuchen Sie mit Hilfe Ihrer Funktion aus b) das Verhalten des Newton-Verfahrens für $p(x) = x^3 - 2x + 2$ für Startwerte aus dem Intervall $[-3,3]$. Veranschaulichen Sie Ihre Ergebnisse mit geeigneten Graphiken und beschreiben Sie das beobachtete Verhalten. " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "# Ein mögliches Array mit Startenwerten. Ggf. kann die Anzahl der Punkte noch erhöht werden... \n", "startarray = np.linspace(-3,3,250)\n", "itmax = 20\n", "epsilon = 1e-6\n", "\n", " # to be done ... \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "d) Untersuchen Sie für die folgenden Funktionen $f_i$ und Startwerte $x_0$ jeweils das Konvergenzverhalten des Newton-Verfahrens: Plotten Sie dazu jeweils den Verlauf der Fehler $\\lvert x_n - x^* \\rvert$, wobei $x_n$ die $n$-te Iterierte und $x^*$ die tatsächliche Nullstelle darstellt. Verwenden Sie eine Form der Darstellung, aus der sich die Konvergenzordnung ablesen lässt! Interpretieren Sie die Ergebnisse. \n", "\n", "d.i) $f_1(x) := x^3 - 2x^2 + x$, $x_0 = 2$, $x^* = 1$.\n", "\n", "d.ii) $f_1(x)$ aber mit $x_0 = -1$ und $x^* = 0$.\n", "\n", "d.iii) $f_2(x) := exp(-1/x^2)$, $x_0 = 1/2$, $x^* = 0$." ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [], "source": [ " # to be done... " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "e) Das Wilkonson-Polynom ist definiert als $w(x) = \\prod_{k=0}^{20} (x-k)$.\n", "\n", "Schreiben Sie funktionen \"w\" und \"dw\", die das Wilkinson-Polynom sowie seine erste Ableitung an der Stelle $x$ auswerten.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def w(x):\n", "\n", " # to be done ...\n", " \n", " \n", "def dw(x):\n", "\n", " # to be done ...\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "f) Finden Sie experimentell jeweils einen Startwert $x_0$, für den das Newton-Verfahren angewandt auf $w$ gegen $x^* = 20$ bzw. $x^* = 6$ konvergiert. Betrachten Sie anschließend $\\tilde{w} = w(x) + \\delta \\cdot x^{19}$ für kleines $\\delta > 0$. Wie verhält sich das Newton-Verfahren angewandt auf $\\tilde{w}$ für die beiden Startwerte? Was passiert wenn $\\delta$ immer kleiner wird?\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "## Bestimme x_0 sodass Konvergenz gegen x^* = 20 bzw. 6 eintritt... \n", "\n", " # to be done...\n", "\n", "## Definiere das gestörte Wilkinson-Polynom für Störungsparameter delta\n", "delta = 1e-4\n", "def wtilde(x): \n", " return w(x) + delta*x**19 \n", "\n", "def dwtilde(x): \n", " return dw(x) + 19*delta*x**18\n", "\n", "## Newton-Verfahren für gestörtes Wilkinson-Polynom: \n", "\n", " # to be done..." ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.12" } }, "nbformat": 4, "nbformat_minor": 1 }