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

Beste Approximation der Quadrat­wurzel­funktion durch eine lineare Funktion: Die maximale Differenz 1/8 wird dreimal mit wechselndem Vorzeichen angenommen

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 {{\bigl (}r-{\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

1. 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.
2. 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.

Literatur

• Robert Mayans: The Chebyshev Equioscillation Theorem (Tschebyscheffs Alternantensatz)