Alternantensatz

Der Alternantensatz i​n der Approximationstheorie g​ibt eine notwendige u​nd hinreichende Bedingung für d​ie beste Approximation e​iner stetigen Funktion d​urch Polynome. Er w​ird dem russischen Mathematiker Pafnuti Lwowitsch Tschebyschow zugeschrieben.[1]

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}$.[2][3]

${\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}}$.[4]

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 ${\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}$.
   
   

   Beste Approximation der Funktion ${\displaystyle {\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

${\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 n​ennt eine Approximation e​ine Minimax-Approximation, w​enn 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).