{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Programmieraufgabe 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# some setup\n",
    "%matplotlib inline\n",
    "import numpy as np \n",
    "import matplotlib.pyplot as plt "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Newtonsche Darstellung und Auswertung des Interpolationspolynoms\n",
    "\n",
    "Sei $I = [a,b]$ ein Interval und $f \\in C(I)$ eine stetige Funktion. \n",
    "Sei $x = \\{x_0, \\ldots, x_n\\}$  eine Liste von Stützstellen und $y = \\{y_0, \\ldots, y_n\\}$ eine Liste von Funktionsauswertungen, d.h. $y_i = f(x_i)$ für $i = 0, \\ldots, n$.\n",
    "\n",
    "a)  Implementieren Sie einen Algorithmus, der basierend auf den Listen $x$ und $y$ eine Liste $z = \\{ z_0, \\ldots, z_n \\}$ von dividierten Differenzen gemäss des Dreicksschemas berechnet, wobei\n",
    "\n",
    " \\begin{equation}\n",
    " z_i = f[x_0, \\ldots, x_i] \\, , \\quad i = 0, \\ldots, n\\, .\n",
    " \\end{equation}\n",
    "\n",
    "b) Implementieren Sie eine Funktion, die basierend auf einer Liste $x$ von Stützstellen und einer Liste $z$ von dividierten Differenzen die Auswertung des interpolierenden Polynoms $p \\in \\Pi_n$ an einer Stelle $t \\in [a,b]$ mit Hilfe des Horner-Schemas berechnet.\n",
    "\n",
    "c) Testen Sie Ihren Code mit der Funktion $f(t) = 1/(1+25t^2)$ auf $I = [-1,1]$. \n",
    "Benutzen Sie äquidistante Stützstellen mit n = 5, 10, 15, 20. \n",
    "Plotten Sie dazu die interpolierenden Polynome sowie die Funktion $f$ in eine Achse.\n",
    "\n",
    "d)Wiederholen Sie die Aufgabe mit denselben Werten für  $n$, aber unter Verwendung von Tschebyschevknoten \n",
    "$x_k = \\cos\\Big(\\frac{2k+1}{2n}\\pi\\Big)$, $k=0,...,n-1$, als Stützstellen.\n",
    "\n",
    "e) Berechnen und plotten Sie die $n$-ten Bernsteinpolynome $B_nf$. Beachten Sie, dass eine Reskalierung vorgenommen werden muss. Betrachten Sie $g(t) = f(2t-1)  $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#### dividierte Differenzen\n",
    "def computeDivDiff( x, y ) :\n",
    "    n = len(x); \n",
    "    z = np.zeros(n);\n",
    "    div = np.zeros(n);\n",
    "\n",
    "    #Insert code here\n",
    "    \n",
    "    return z;\n",
    "\n",
    "#### Horner schema fuer das Newton-Polynom ausgewertet an t\n",
    "#### Stuetzstellen x, dividierste Differenzen z\n",
    "def evalHorner( x, z, t ) :\n",
    "    \n",
    "    #Insert code here\n",
    "    \n",
    "\n",
    "\n",
    "### Runge-Funktion 1/(1+25x^2)\n",
    "def func( t ) :\n",
    "\n",
    "    #Insert code here\n",
    "    \n",
    "### Tschebyscheff Stuetzstellen\n",
    "def getTschebyschevNodes( a, b, n ) :\n",
    "    x = np.zeros(n);\n",
    "    for i in np.arange(0,n):\n",
    "        x[i] = (a-b) * np.cos( (2*i+1) * np.pi / (2*n) ) / 2 + (a+b)/2;\n",
    "    return(x);\n",
    "\n",
    "\n",
    "### $n$-tes Bernstein-Polynom auf [0,1] ausgewertet an t\n",
    "### y... Funktionswerte an den aequidistanten Stuetzstellen\n",
    "def evalBernstein(y,n,t):\n",
    "    \n",
    "    #Insert code here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Test\n",
    "\n",
    "## Variablen\n",
    "n = 15;\n",
    "a = -1;\n",
    "b = 1;\n",
    "\n",
    "# erzeuge aequidistantes Gitter bzw. berechne Chebychev-Knoten\n",
    "x = np.linspace(a,b,n+1);\n",
    "x = getTschebyschevNodes(a,b,n+1);\n",
    "\n",
    "# berechne die Funktionswerte\n",
    "y = np.zeros(n+1);\n",
    "for i in np.arange(0,n+1):\n",
    "    y[i] = func( x[i] );    \n",
    "    \n",
    "## berechne dividierte Differenzen    \n",
    "z = computeDivDiff( x , y);\n",
    "\n",
    "### plotte Funktion, Interpolierende und Bernsteinpolynom auf feinem Gitter\n",
    "eps = 0.0;\n",
    "N = 1000;\n",
    "\n",
    "r = np.linspace(a - eps, b + eps, N) ;   \n",
    "f = np.zeros(N);\n",
    "If = np.zeros(N);\n",
    "\n",
    "#Insert code here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}