{%hackmd @themes/dracula %}

> Pratscher
> Schledorn
> Sergeyeva

| **1** | **2** | **3** | **4** |**5**| $\Sigma$ |
| :---: | :---: | :---: | :---: | :---: | :---:|
|</br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ | </br></br></br>__ __ __ __ |

# Aufgabe 4.1

Sei $f$ eine zweimal stetig differenzierbare Funktion, sei $p_1$ die lineare Interpolierende von $f$ Stützstellen $x_0<x_1\in\mathbb{R}$ und sei $e(x):=f(x)-p_1(x)$ der Interpolationsfehler.

## a)

Betrachten Sie für festes $x\in(x_0,x_1)$ die Funktion

$g(t)=e(t)-\frac{e(x)}{w_2(x)}w_2(t)$, $t\in[x_0,x_1]$ mit $w_2(x)=(x-x_0)(x-x_1)$.

Zeigen Sie, dass $g$ in drei Punkten in $[x_0,x_1]$ verschwindet. Folgern Sie daraus durch mehrmaliges Anwenden des Satzes von Rolle, dass es ein $\xi\in(x_0,x_1)$ gibt, sodass

$e(x)=\frac{f''(\xi)}{2}w_2(x)$.

---

Da $p_1$ Interpolierende von $f$
$\Rightarrow p_1(x_0)=f(x_0)~\land~p_1(x_1)=f(x_1)$

$\begin{split}
\implies &e(x_0)=f(x_0)-p_1(x_0)&=0 \\
&e(x_1)=f(x_1)-p_1(x_1)&=0 \\
\implies &g(x_0)=e(x_0)-\frac{e(x)}{w_2(x)}w_2(x_0)=0-\frac{e(x)}{w_2(x)}\cdot 0&=0 \\
&g(x_1)=e(x_1)-\frac{e(x)}{w_2(x)}w_2(x_1)=0-\frac{e(x)}{w_2(x)}\cdot 0&=0
\end{split}$

Außerdem gilt: $g(x)=e(x)-\frac{e(x)}{w_2(x)}w_2(x)=e(x)-e(x)=0$

$\implies g(t)$ verschwindet in den Punkten $x,x_0,x_1$.

**Satz von Rolle Anwendung**

Ableitung von $g(t)$:

$g'(t) = e'(t)-\frac{e(x)}{w_2(x)}((t-x_0)+(t-x_1))$
$g''(t) = e''(t)-\frac{e(x)}{w_2(x)}\cdot 2$

Sei $g''(\xi):=0$

$\implies e(x) = \frac{f''(\xi)}{2}w_2(x)$

mit $\xi\in(x_0,x_1)$.

## b)

Sei $x_0=-1$, $x_1=1$ und $f(x)=\sin{x}$. Berechnen Sie die lineare Interpolierende $p_1(x)$. Benutzen Sie das Ergebnis aus Teil (a) um zu zeigen, dass

$||e||_{\infty,[-1,1]}:=\underset{x\in[-1,1]}{\max}|e(x)|\leq\frac{1}{2}\sin(1)$

---

$\begin{split}
p_1(x)&=\sin(-1)+\frac{\sin(1)-\sin(-1)}{1-(-1)}(x-(-1)) \\
&=-\sin(1)+\frac{2\sin(1)}{2}(x+1) \\
&=\sin(1)+\sin(1)(x+1) \\
&=\sin(1)\cdot x
\end{split}$

Interpolationsfehler: $e(x)=f(x)-p_1(x)=\sin(x)-sin(1)\cdot x$

Für $f(x)=\sin(x)\Rightarrow f''(x)=-\sin(x)$

Mit a) folgt:

$\begin{split}
e(x)&=\frac{-\sin(\xi)}{2}(x+1)(x-1) \\
&=\frac{-\sin(\xi)}{2}(x^2-1)
\end{split}$

Wir betrachten nun
$||e||_{\infty,[-1,1]}:=\underset{x\in[-1,1]}{\max}|e(x)|$

$||e||_{\infty,[-1,1]}=\underset{x\in[-1,1]}{\max}|\frac{-\sin(\xi)}{2}(x^2-1)|$

Da $x^2-1$ in $[-1,1]$ nur Werte zw. $0,-1$ hat

$\implies ||e||_{\infty,[-1,1]}=|\frac{-\sin(\xi)}{2}(-1)|=\frac{\sin(\xi)}{2}$

$\xi\in(-1,1)\implies\sin(\xi)\leq\sin(1)$

$\implies ||e||_{\infty,[-1,1]}\leq\frac{1}{2}\sin(1)$

# Aufgabe 4.2
## a)

Tschebyscheff-Polynome der zweiten Art:

$U_n(\cos \theta) = \frac{\sin ((n + 1) \theta)}{\sin \theta}.$

### Basisfall:

Für $n = 0$:

$$U_0(\cos \theta) = \frac{\sin ((0 + 1) \theta)}{\sin \theta} = \frac{\sin \theta}{\sin \theta} = 1.$$

Für \( n = 1 \):

$$U_1(\cos \theta) = \frac{\sin ((1 + 1) \theta)}{\sin \theta} = \frac{\sin (2 \theta)}{\sin \theta} = 2 \cos \theta.$$

Da $x = \cos \theta$, haben wir:

$$U_0(x) = 1 \quad und \quad U_1(x) = 2x.$$

### Induktionsschritt:

Angenommen, die Formel gilt für $U_n(x)$ und $U_{n-1}(x)$:

$$U_n(\cos \theta) = \frac{\sin ((n + 1) \theta)}{\sin \theta} \quad und \quad U_{n-1}(\cos \theta) = \frac{\sin (n \theta)}{\sin \theta}.$$

Nun zeigen wir, dass die Rekursionsformel auch für $U_{n+1}(x)$ gilt:

$$U_{n+1}(\cos \theta) = \frac{\sin ((n + 2) \theta)}{\sin \theta}.$$

Verwenden wir die Additionstheoreme der trigonometrischen Funktionen:

$$\sin ((n + 2) \theta) = \sin ((n + 1) \theta + \theta) = \sin ((n + 1) \theta) \cos \theta + \cos ((n + 1) \theta) \sin \theta.$$

Daraus folgt:

$$\sin ((n + 2) \theta) = \sin ((n + 1) \theta) \cos \theta + \cos ((n + 1) \theta) \sin \theta.$$

Da $$\cos ((n + 1) \theta) = \cos (n \theta + \theta) = \cos (n \theta) \cos (\theta) - \sin (n \theta) \sin (\theta)$$, ergibt sich:

$$\sin ((n + 2) \theta) = \sin ((n + 1) \theta) \cos \theta + (\cos (n \theta) \cos (\theta) - \sin (n \theta) \sin (\theta)) \sin \theta.$$

Teilen wir durch $\sin \theta$:

$$U_{n+1}(\cos \theta) = \frac{\sin ((n + 2) \theta)}{\sin \theta} = \frac{\sin ((n + 1) \theta) \cos \theta + (\cos (n \theta) \cos (\theta) - \sin (n \theta) \sin (\theta)) \sin \theta}{\sin \theta}.$$

Da $x = \cos \theta$ und $\sin \theta \neq 0$, können wir die Terme zusammenfassen:

$$U_{n+1}(\cos \theta) = \frac{\sin ((n + 1) \theta) \cos \theta}{\sin \theta} + \cos (n \theta) \cos (\theta) - \sin (n \theta).$$

Dies vereinfacht sich zu:

$$U_{n+1}(x) = 2x U_n(x) - U_{n-1}(x).$$

Somit haben wir gezeigt, dass die Rekursionsformel gilt:

$$U_{n+1}(x) = 2x U_n(x) - U_{n-1}(x).$$

## b)
Definition der Tschebyscheff-Polynome der ersten Art:

$$ T_n(x) := \cos(n \arccos x). $$

Wir leiten $T_n(x)$ nach $x$ ab. Sei $\theta = \arccos(x)$, dann gilt $x = \cos(\theta)$.

$$ T_n(x) = \cos(n \theta). $$

Die Ableitung von $T_n(x)$ nach $x$ ist:

$$ T_n'(x) = \frac{d}{dx} \cos(n \theta). $$

Anwenden der Kettenregel:

$$ T_n'(x) = \frac{d}{d\theta} \cos(n \theta) \cdot \frac{d\theta}{dx}. $$

Die Ableitung von $\cos(n \theta)$ nach $\theta$ ist:

$$ \frac{d}{d\theta} \cos(n \theta) = -n \sin(n \theta). $$

Die Ableitung von $\theta = \arccos(x)$ nach $x$ ist:

$$ \frac{d\theta}{dx} = -\frac{1}{\sqrt{1 - x^2}}. $$

Somit ergibt sich:

$$ T_n'(x) = -n \sin(n \theta) \cdot -\frac{1}{\sqrt{1 - x^2}} = \frac{n \sin(n \theta)}{\sqrt{1 - x^2}}. $$

Erinnern wir uns nun an die Definition der Tschebyscheff-Polynome der zweiten Art:

$$ U_{n-1}(\cos \theta) = \frac{\sin(n \theta)}{\sin \theta}. $$

Da $\sin(\theta) = \sqrt{1 - \cos^2(\theta)} = \sqrt{1 - x^2}$ für $x = \cos(\theta)$, ergibt sich:

$$ U_{n-1}(x) = \frac{\sin(n \theta)}{\sqrt{1 - x^2}}. $$

Setzen wir dies in die Gleichung für $T_n'(x)$ ein:

$$ T_n'(x) = \frac{n \sin(n \theta)}{\sqrt{1 - x^2}} = n U_{n-1}(x). $$

Damit haben wir gezeigt, dass:

$$ T_n'(x) = n U_{n-1}(x). $$

## c)
Definition der Tschebyscheff-Polynome der zweiten Art:

$$ U_n(\cos \theta) = \frac{\sin((n+1) \theta)}{\sin \theta}. $$

Um den Grad und den führenden Koeffizienten von $U_n(x)$ zu bestimmen, setzen wir $x = \cos \theta$. Dann gilt:

$$ U_n(x) = \frac{\sin((n+1) \theta)}{\sin \theta}, \quad \text{wobei} \quad x = \cos \theta. $$

Wir untersuchen $U_n(x)$ für große Werte von $x$. Dazu verwenden wir die trigonometrische Identität:

$$ \sin((n+1) \theta) = \sin(n \theta + \theta) = \sin(n \theta) \cos(\theta) + \cos(n \theta) \sin(\theta). $$

Setzen wir diese Identität in die Definition von $U_n(x)$ ein:

$$ U_n(\cos \theta) = \frac{\sin(n \theta) \cos(\theta) + \cos(n \theta) \sin(\theta)}{\sin(\theta)}. $$

Dies vereinfacht sich zu:

$$ U_n(\cos \theta) = \sin(n \theta) \cot(\theta) + \cos(n \theta). $$

Da $\cot(\theta) = \frac{\cos(\theta)}{\sin(\theta)}$, ergibt sich:

$$ U_n(\cos \theta) = \sin(n \theta) \frac{\cos(\theta)}{\sin(\theta)} + \cos(n \theta). $$

Dies vereinfacht sich weiter zu:

$$ U_n(\cos \theta) = \frac{\sin(n \theta) \cos(\theta)}{\sin(\theta)} + \cos(n \theta). $$

Nun betrachten wir die asymptotische Form für große $x$. Da $\theta = \arccos(x)$, verwenden wir die Beziehung $\cos(\theta) = x$ und $\sin(\theta) = \sqrt{1 - x^2}$:

$$ U_n(x) = \frac{\sin((n+1) \arccos(x))}{\sqrt{1 - x^2}}. $$

Für große $x$ nähert sich $\arccos(x)$ der Funktion $\frac{\pi}{2} - \frac{1}{x}$ an. Daher können wir $\sin((n+1) \arccos(x))$ als $\sin((n+1)(\frac{\pi}{2} - \frac{1}{x}))$ schreiben. Da $\sin(\frac{\pi}{2} - y) = \cos(y)$, ergibt sich:

$$ \sin((n+1)(\frac{\pi}{2} - \frac{1}{x})) \approx \cos((n+1) \frac{1}{x}) \approx 1 - \frac{((n+1) \frac{1}{x})^2}{2} = 1 - \frac{(n+1)^2}{2x^2}. $$

Für große $x$ dominiert der lineare Term:

$$ U_n(x) \approx 2^n x^n. $$

Daher ergibt sich, dass der führende Koeffizient von $U_n(x)$ tatsächlich $2^n$ ist und $U_n(x)$ ein Polynom vom Grad $n$ ist.

# Aufgabe 4.3
Sei $f\in C^3([a,b])$ eine dreimal stetig differenzierbare Funktion auf dem Intervall $[a,b]$. Ein numerisches Verfahren zur näherungsweisen Berechnung von $f'(x)$ besteht darin, eine möglichst kleine Schrittweite $h$ zu wählen und den zentralen Differenzenquotienten

$d_h(x)=\frac{f(x+h)-f(x-h)}{2h}$
zu berechnen.

## a
Der Differenzenquotient $d_h$ werde exakt berechnet, ohne Runden. Zeigen Sie, dass für den dabei gemachten Diskretisierungsfehler gilt:

$|d_h(x)- f'(x)|\leq c\cdot h^2$

Dabei darf $c$ von $f$ abhängen, aber nicht von $h$.

Wir erweitern $f$ um $x$ bis zur dritten Ordnung mithilfe der Taylor-Reihenentwicklung:

$f(x+h) = f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \frac{f'''(\xi_1)}{6}h^3$

$f(x-h) = f(x) - f'(x)h + \frac{f''(x)}{2}h^2 - \frac{f'''(\xi_2)}{6}h^3$

wobei $\xi_1$ und $\xi_2$ Punkte in den Intervallen $[x, x+h]$ bzw. $[x-h, x]$ sind.

Nun berechnen wir die zentrale Differenz $d_h(x)$:

$d_h(x) = \frac{f(x+h) - f(x-h)}{2h}$

Wir setzen ein:

$d_h(x) = \frac{\left( f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \frac{f'''(\xi_1)}{6}h^3 \right) - \left( f(x) - f'(x)h + \frac{f''(x)}{2}h^2 - \frac{f'''(\xi_2)}{6}h^3 \right)}{2h}$

$d_h(x) = \frac{f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \frac{f'''(\xi_1)}{6}h^3 - f(x) + f'(x)h - \frac{f''(x)}{2}h^2 + \frac{f'''(\xi_2)}{6}h^3}{2h}$

$d_h(x) = \frac{2f'(x)h + \left(\frac{f'''(\xi_1)}{6}h^3 + \frac{f'''(\xi_2)}{6}h^3\right)}{2h}$

$d_h(x) = f'(x) + \frac{f'''(\xi_1) + f'''(\xi_2)}{12}h^2$

Der Fehlerterm zwischen $d_h(x)$ und der exakten Ableitung $f'(x)$ ist daher:

$|d_h(x) - f'(x)| = \left| \frac{f'''(\xi_1) + f'''(\xi_2)}{12} \right| h^2$

Setzen wir $c = \frac{1}{12} \max_{\xi \in [a, b]} |f'''(\xi)|$ , da $f'''(\xi)\) in \([a, b]$ beschränkt ist, erhalten wir:

$|d_h(x) - f'(x)| \leq c h^2$

wobei $c$ eine Konstante ist, die von $f$ (insbesondere von der maximalen dritten Ableitung von $f$ in $[a, b]$) abhängt, aber nicht von $h$.

Dies zeigt, dass der Diskretisierungsfehler des zentralen Differenzenquotienten $d_h(x)$ eine Ordnung von $h^2$ hat und somit gilt:

$|d_h(x) - f'(x)| \leq c \cdot h^2$

wobei $c$ von $f$ abhängt, aber nicht von $h$.

## b

$d(h, x) = \frac{f(x + h) - f(x - h)}{2h}$

Zunächst berechnen wir die Ableitung von $d(h, x)$ nach $h$:

$\frac{\partial d(h, x)}{\partial h} = \frac{\partial}{\partial h} \left( \frac{f(x + h) - f(x - h)}{2h} \right)$

$\frac{\partial d(h, x)}{\partial h} = \frac{1}{2h} \left( f'(x + h) + f'(x - h) \right) - \frac{f(x + h) - f(x - h)}{2h^2}$

Für $h \approx 0$ können wir $f(x + h)$ und $f(x - h)$ mit Taylor-Reihenentwicklungen um $x$ darstellen:

$f(x + h) = f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \frac{f'''(\xi_1)}{6}h^3$

$f(x - h) = f(x) - f'(x)h + \frac{f''(x)}{2}h^2 - \frac{f'''(\xi_2)}{6}h^3$

Substituieren wir diese in $d(h, x)$:

$d(h, x) = \frac{\left( f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \frac{f'''(\xi_1)}{6}h^3 \right) - \left( f(x) - f'(x)h + \frac{f''(x)}{2}h^2 - \frac{f'''(\xi_2)}{6}h^3 \right)}{2h}$

$d(h, x) = \frac{2f'(x)h + \left( \frac{f'''(\xi_1)}{6}h^3 + \frac{f'''(\xi_2)}{6}h^3 \right)}{2h} = f'(x) + \frac{f'''(\xi_1) + f'''(\xi_2)}{12}h^2$

Betrachten wir die numerische Berechnung von $d(h, x)$. Wenn $h$ sehr klein wird, führen zwei Hauptprobleme zur numerischen Instabilität:

1. **Rundungsfehler bei der Berechnung von $f(x + h)$ und $f(x - h)$**:
- Wenn $h$ sehr klein ist, sind $x + h$ und $x - h$ numerisch nahe bei $x$. Dies bedeutet, dass die Berechnungen von $f(x + h)$ und $f(x - h)$ aufgrund der begrenzten Präzision der Gleitkommaarithmetik fehleranfällig sind. Die Differenz $f(x + h) - f(x - h)$ könnte sehr klein sein und durch Rundungsfehler beeinträchtigt werden.

2. **Verstärkung der Fehler durch Division durch $2h$**:
- Der zentrale Differenzenquotient enthält eine Division durch $2h$. Wenn $h$ sehr klein ist, kann diese Division Fehler verstärken, die bereits in der Berechnung von $f(x + h) - f(x - h)$ aufgetreten sind.

Formell ausgedrückt, sei $\epsilon$ die Maschinengenauigkeit und betrachte man die Fehler bei der Berechnung von $f(x + h)$ und $f(x - h)$ als:

$\tilde{f}(x + h) = f(x + h) + \delta_1$
$\tilde{f}(x - h) = f(x - h) + \delta_2$

wobei $|\delta_1| \leq \epsilon |f(x + h)|$ und $|\delta_2| \leq \epsilon |f(x - h)|$. Dann ist der berechnete Differenzenquotient:

$\tilde{d}(h, x) = \frac{\tilde{f}(x + h) - \tilde{f}(x - h)}{2h} = \frac{f(x + h) - f(x - h) + \delta_1 - \delta_2}{2h}$

Der Fehler in der Berechnung von $d(h, x)$ beträgt:

$|\tilde{d}(h, x) - d(h, x)| = \left| \frac{\delta_1 - \delta_2}{2h} \right|$

Da $\delta_1$ und $\delta_2$ proportional zu $\epsilon$ sind, und die Division durch $2h$ bei kleinem $h$ den Fehler verstärkt, ergibt sich:

$|\tilde{d}(h, x) - d(h, x)| \approx \frac{\epsilon}{h}$

Dies zeigt, dass der Fehler term $\frac{\epsilon}{h}$ bei $h \to 0$ unbeschränkt wächst, was numerische Instabilität bedeutet. Daher ist die numerische Berechnung von $d(h, x)$ für sehr kleine $h$ instabil.