A note on the complexity of an algorithm for Chebyshev approximation (Q2266346)

Es wird die Aufgabe betrachtet, eine auf T (kompaktes Intervall oder endliche Menge) stetige Funktion durch Polynome höchstens n-ten Grades im Sinne der Maximumnorm zu approximieren. Dazu wird der klassische Remes-Algorithmus (mit Einzelaustausch) in der folgenden Variante benutzt: bei der bei jedem Schritt erforderlichen Ermittlung des Betragsmaximums der Fehlerfunktion wird für den Funktionswert jeweils eine Toleranz von \(\eta >0\) zugelassen. Dann kann mit bekannten Methoden gezeigt werden: es gibt eine Zahl \(\vartheta >0\), so daß bei Wahl von \(\eta >\epsilon \vartheta /(1+\vartheta)\) nach höchstens \(c\cdot \vartheta^{-1}\log \vartheta^{-1}\) Schritten eine Näherung erreicht ist, deren Fehlernorm sich um höchstens \(\epsilon\) von der Minimalabweichung unterscheidet. Die Schwierigkeit liegt nun darin, Abschätzungen für \(\vartheta\) zu finden. Der Autor gibt Bedingungen an, unter welchen \(\lim_{n\to \infty}\vartheta^{-1}/Kn=1\) gilt, zeigt aber auch anhand eines Beispiels, daß \(\vartheta^{-1}\geq 2^ n\) vorkommen kann.