A note on the complexity of an algorithm for Chebyshev approximation

DOI10.1007/BF01934908MaRDI QIDQ2266346zbMATH OpenOpenAlexFDO

Authors Allen A. Goldstein

Publication date 1984

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934908

zbMATH Keywords

Chebyshev approximationcomplexitycontinuous functionexchange algorithmRemes algorithmsimplex methoduniform approximation

Mathematics Subject Classification ID

Approximation by polynomials (41A10) Best approximation, Chebyshev systems (41A50) Algorithms for approximation of functions (65D15) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Cites work

• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3258269 (Why is no real title available?)
• The Average number of pivot steps required by the Simplex-Method is polynomial

Cited in

(9)

• Using a computer to obtain Chebotarev bounds in the nonhomogeneous Minkowski's conjecture
• On the computational complexity of best Chebyshev approximations
• scientific article; zbMATH DE number 5080397 (Why is no real title available?)
• A Fast Algorithm for Linear Complex Chebyshev Approximations
• scientific article; zbMATH DE number 3911563 (Why is no real title available?)
• scientific article; zbMATH DE number 3942139 (Why is no real title available?)
• scientific article; zbMATH DE number 19426 (Why is no real title available?)
• scientific article; zbMATH DE number 646755 (Why is no real title available?)
• Chebyshev's approximation algorithms and applications

This page was built for publication: A note on the complexity of an algorithm for Chebyshev approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2266346)