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

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

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

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

Beispiel 1

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

Beispiel 2

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

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

vom Grad ${\displaystyle n}$ optimal approximiert.

Dabei ist   ${\displaystyle E_{n}:={\frac {{\bigl (}r-{\sqrt {r^{2}-1}}{\bigr )}^{n}}{r^{2}-1}}}$   sowie   ${\displaystyle V_{n}(x):=\cos(n\varphi +\psi )}$   gesetzt

und   ${\displaystyle \varphi }$   durch   ${\displaystyle \cos \varphi$ :=x}   sowie   ${\displaystyle \psi }$   durch   ${\displaystyle \tan {\frac {\psi }{2}}:={\sqrt {\frac {r+1}{r-1}}}\tan {\frac {\varphi }{2}}}$   implizit definiert.

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

Beweisskizze

1. Polynomeigenschaft: Durch Umrechnungen u. a. über Tschebyschow-Polynome erster und zweiter Art erweist sich die Funktion ${\displaystyle q(x):=1-(r-x)\,E_{n}V_{n}}$ im Zähler von ${\displaystyle p_{n}(x)={\frac {1}{r-x}}-E_{n}V_{n}}$ als ein Polynom vom Grade ${\displaystyle n+1}$. Damit ist ${\displaystyle p_{n}(x)}$ zunächst eine gebrochenrationale Funktion. Ferner hat ${\displaystyle q(x)}$ die Nullstelle ${\displaystyle r}$, so dass sich der Faktor ${\displaystyle (x-r)}$ von ${\displaystyle q(x)}$ abspalten und mit dem Nenner ${\displaystyle (r-x)}$ von ${\displaystyle p_{n}(x)}$ wegkürzen lässt. Am Ende ist ${\displaystyle p_{n}(x)}$ ein Polynom vom Grad ${\displaystyle n}$.
   
2. Beste Approximation: Die angegebenen Relationen definieren eine monotone und bijektive Abbildung

${\displaystyle {\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 ${\displaystyle \pi }$ (und damit den Extremstellen des Kosinus) genau die Werte ${\displaystyle \pi ,2\pi ,\ldots ,n\pi }$ getroffen werden. (Dabei sind die jeweiligen Hauptwerte der Arkusfunktionen genommen worden.) Fügt man die Intervallgrenzen ${\displaystyle x_{0}=1}$ mit ${\displaystyle n\varphi +\psi =0}$ und ${\displaystyle x_{n+1}=-1}$ mit ${\displaystyle n\varphi +\psi =(n+1)\pi }$ hinzu, dann hat man die ${\displaystyle n+2}$ Alternanten ${\displaystyle x_{0}>\dots >x_{i}>\dots >x_{n+1}}$, für die die Fehlerfunktion ${\displaystyle f(x)-p_{n}(x)=E_{n}\cos(n\varphi +\psi )}$ genau ${\displaystyle n+2}$ mal alternierend den jeweiligen Extremwert ${\displaystyle (-1)^{i}E_{n}}$ annimmt.

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

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

Algorithmen

Man nennt eine Approximation eine Minimax-Approximation, wenn sie

${\displaystyle \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)

Anmerkungen und Einzelnachweise

1. ↑ Leçons sur l’approximation des fonctions d’une variable réelle. Gauthier-Villars, Paris 1919, 1952, S. 75, archive.org
2. ↑ Aus der Stetigkeit auf dem Kompaktum folgt auch die Beschränktheit.
3. ↑ René Grothmann: Skriptum Approximationstheorie 1.38 Satz (mit Beweis) (PDF)
4. ↑ Der Alternantensatz gilt auch für wesentlich allgemeinere Räume, bspw. für trigonometrische Polynome (s. a. Proximum#Alternanten-Kriterium in Tschebyschow-Systemen).