Alternantensatz
# Alternantensatz

Der Alternantensatz in der Approximationstheorie gibt eine notwendige und hinreichende Bedingung für die beste Approximation einer stetigen Funktion durch Polynome. Er wird dem russischen Mathematiker Pafnuti Lwowitsch Tschebyschow zugeschrieben.

## Alternantensatz

Sei $[a,b]$ ein Intervall $\subset \mathbb {R}$ und $f\colon [a,b]\to \mathbb {R}$ eine stetige Funktion. Unter allen Polynomen eines Grades $\leq n$, minimiert das Polynom $p$ die Supremumsnorm $\|f-p\|_{\infty }$ dann und nur dann, wenn es $n+2$ Extremstellen $a\leq x_{0}<x_{1}<\cdots <x_{n+1}\leq b$ gibt, so dass

    $f(x_{i})-p(x_{i})=\sigma (-1)^{i}E$ für alle $i=0,\ldots ,n+1$

ist mit $E:=\|f-p\|_{\infty }$ und festem $\sigma =\pm 1$.

$E$ ist der Minimalabstand (oder Approximationsfehler) von $f$ zu ${\mathcal {P}}_{n}$, dem Raum der algebraischen Polynome vom Grad kleiner oder gleich $n$. Ein Polynom $p\in {\mathcal {P}}_{n}$ mit Minimalabstand zu $f$ heißt Proximum oder beste Approximation an $f$ bezüglich ${\mathcal {P}}_{n}$.

## Beispiel 1

Nach dem Alternantensatz ist das Polynom $p(x)=x+{\tfrac {1}{8}}$ dasjenige Polynom vom Grad kleiner oder gleich $n=1$, das die Quadratwurzelfunktion $f\colon [0,1]\to \mathbb {R}$, $f(x)={\sqrt {x}}$ auf dem Intervall $[a,b]=[0,1]$ bezüglich der Supremumsnorm am besten approximiert. Da nämlich $f$ und damit auch die Fehlerfunktion $f-p$ streng konkav ist, nimmt letztere an den Intervallgrenzen $x_{0}:=0$ und $x_{2}:=1$ jeweils ein lokales Minimum an, ferner ein Maximum $x_{1}$ im Inneren von $[0,1]$. Dieses bestimmt sich durch Nullsetzen der Ableitung $f'-p'={\tfrac {1}{2{\sqrt {x_{1}}}}}-1$ zu $x_{1}={\tfrac {1}{4}}$. Nun ist mit $E:={\tfrac {1}{8}}$ an diesen Extremstellen $f(0)-p(0)=-E,\ f({\tfrac {1}{4}})-p({\tfrac {1}{4}})=+E,\ f(1)-p(1)=-E$, ist also erstens $E=\max _{0\leq x\leq 1}|f(x)-p(x)|=\|f-p\|_{\infty }$ und zweitens $f(x_{i})-p(x_{i})=\sigma (-1)^{i}E$ mit $\sigma =-1$.

## Beispiel 2

Die Funktion $f(x)={\frac {1}{r-x}}$ mit einem $r>1$ wird im Intervall $[-1,1]$ für jedes $n\in \mathbb {N} _{0}$ durch das Polynom

    $p_{n}(x):={\frac {1}{r-x}}-E_{n}V_{n}$

vom Grad $n$ optimal approximiert.

       Dabei ist $E_{n}:={\frac {{\biglr-{\sqrt {r^{2}-1}}{\bigr )}^{n}}{r^{2}-1}}$ sowie $V_{n}(x):=\cos(n\varphi +\psi )$ gesetzt
       und $\varphi$ durch $\cos \varphi :=x$ sowie $\psi$ durch $\tan {\frac {\psi }{2}}:={\sqrt {\frac {r+1}{r-1}}}\tan {\frac {\varphi }{2}}$ implizit definiert.

Bemerkung Die (besten) Polynome $p_{n}(x)$ konvergieren für wachsendes $n$ (gleichmäßig und) mit linearer Konvergenzgeschwindigkeit gegen die Funktion $f$.

Beweisskizze

* Polynomeigenschaft: Durch Umrechnungen u. a. über Tschebyschow-Polynome erster und zweiter Art erweist sich die Funktion $q(x):=1-(r-x)\,E_{n}V_{n}$ im Zähler von $p_{n}(x)={\frac {1}{r-x}}-E_{n}V_{n}$ als ein Polynom vom Grade $n+1$. Damit ist $p_{n}(x)$ zunächst eine gebrochenrationale Funktion. Ferner hat $q(x)$ die Nullstelle $r$, so dass sich der Faktor $(x-r)$ von $q(x)$ abspalten und mit dem Nenner $(r-x)$ von $p_{n}(x)$ wegkürzen lässt. Am Ende ist $p_{n}(x)$ ein Polynom vom Grad $n$. Beste Approximation der Funktion ${\tfrac {1}{37/12-x}}$ (rot) durch Polynome vom Grad 0 , 1 und 2 . Die Maximalabweichungen sind durch senkrechte Balken dargestellt, die in alternierender Richtung von der Funktion abstehen. Beim Grad 3 würden die Fehlerbalken unter die Pixelgrenze fallen.
* Beste Approximation: Die angegebenen Relationen definieren eine monotone und bijektive Abbildung

          ${\begin{array}{clc}-1,1{\overleftarrow {}}\;\;&\to \;\;&{{\overrightarrow}}0,(n+1)\pi\\x&\mapsto &n\varphi +\psi \\\end{array}}$
       zwischen zwei offenen Intervallen, bei der unter den Vielfachen von $\pi$ (und damit den Extremstellen des Kosinus) genau die Werte $\pi ,2\pi ,\ldots ,n\pi$ getroffen werden. (Dabei sind die jeweiligen Hauptwerte der Arkusfunktionen genommen worden.) Fügt man die Intervallgrenzen $x_{0}=1$ mit $n\varphi +\psi =0$ und $x_{n+1}=-1$ mit $n\varphi +\psi =(n+1)\pi$ hinzu, dann hat man die $n+2$ Alternanten $x_{0}>\dots >x_{i}>\dots >x_{n+1}$, für die die Fehlerfunktion $f(x)-p_{n}(x)=E_{n}\cos(n\varphi +\psi )$ genau $n+2$ mal alternierend den jeweiligen Extremwert $(-1)^{i}E_{n}$ annimmt.

Die ersten 4 Approximationen für $r={\tfrac {37}{12}}$ :

| $n$ | bestes Polynom $p_{n}$ | Extremstellen | max. Fehler $E_{n}$ |
| - | - | - | - |
| $0$ | ${\tfrac {444}{1225}}$ | $1\qquad \qquad \qquad \qquad -\!1$ | ${\tfrac {1}{s^{2}}}={\tfrac {144}{1225}}\;\approx 0.1176$ |
| $1$ | ${\tfrac {144}{1225}}\;x+\;{\tfrac {12}{35}}$ | $1\qquad \qquad {\tfrac {1}{6}}\qquad \quad \;\;-\!1$ | ${\tfrac {r-s}{s^{2}}}={\tfrac {24}{1225}}\;\approx 0.0196$ |
| $2$ | ${\tfrac {48}{1225}}\,x^{2}+{\tfrac {4}{35}}\,x+{\tfrac {396}{105}}$ | $1\quad \;\;\;{\tfrac {7}{12}}\quad \;\;\;-\!{\tfrac {5}{12}}\quad \;\,-\!1$ | ${\tfrac {(r-s)^{2}}{s^{2}}}={\tfrac {4}{1225}}\approx 0.0033$ |
| $3$ | ${\tfrac {16}{1225}}\,x^{3}+{\tfrac {4}{105}}\,x^{2}+{\tfrac {128}{1225}}\,x+{\tfrac {34}{105}}$ | $1\quad \;{\tfrac {3}{4}}\quad \;{\tfrac {1}{12}}\quad -\!{\tfrac {2}{3}}\quad -\!1$ | ${\tfrac {(r-s)^{3}}{s^{2}}}={\tfrac {2}{3675}}\approx 0.0005$ |

## Algorithmen

Man nennt eine Approximation eine Minimax-Approximation, wenn sie

    $\max _{a\leq x\leq b}|f(x)-p(x)|$

minimiert. Es gibt einige Minimax-Approximationsalgorithmen, der gebräuchlichste ist der Remez-Algorithmus.

