Equioscillation theorem

<h2 id="statement">Statement</h2>
<p>Let 
  
    
      
        f
      
    
    {\displaystyle f}
  
 be a continuous function from 
  
    
      
        [
        a
        ,
        b
        ]
      
    
    {\displaystyle [a,b]}
  
 to 
  
    
      
        
          R
        
      
    
    {\displaystyle \mathbb {R} }
  
. Among all the polynomials of degree 
  
    
      
        ≤
        n
      
    
    {\displaystyle \leq n}
  
, the polynomial 
  
    
      
        g
      
    
    {\displaystyle g}
  
 minimizes the uniform norm of the difference 
  
    
      
        ‖
        f
        −
        g
        
          ‖
          
            ∞
          
        
      
    
    {\displaystyle \|f-g\|_{\infty }}
  
 if and only if there are 
  
    
      
        n
        +
        2
      
    
    {\displaystyle n+2}
  
 points 
  
    
      
        a
        ≤
        
          x
          
            0
          
        
        <
        
          x
          
            1
          
        
        <
        ⋯
        <
        
          x
          
            n
            +
            1
          
        
        ≤
        b
      
    
    {\displaystyle a\leq x_{0}<x_{1}<\cdots <x_{n+1}\leq b}
  
 such that 
  
    
      
        f
        (
        
          x
          
            i
          
        
        )
        −
        g
        (
        
          x
          
            i
          
        
        )
        =
        σ
        (
        −
        1
        
          )
          
            i
          
        
        ‖
        f
        −
        g
        
          ‖
          
            ∞
          
        
      
    
    {\displaystyle f(x_{i})-g(x_{i})=\sigma (-1)^{i}\|f-g\|_{\infty }}
  
 where 
  
    
      
        σ
      
    
    {\displaystyle \sigma }
  
 is either -1 or +1.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="variants">Variants</h2>
<p>The equioscillation theorem is also valid when polynomials are replaced by rational functions: among all rational functions whose numerator has degree 
  
    
      
        ≤
        n
      
    
    {\displaystyle \leq n}
  
 and denominator has degree 
  
    
      
        ≤
        m
      
    
    {\displaystyle \leq m}
  
,  the rational function 
  
    
      
        g
        =
        p
        
          /
        
        q
      
    
    {\displaystyle g=p/q}
  
, with 
  
    
      
        p
      
    
    {\displaystyle p}
  
 and 
  
    
      
        q
      
    
    {\displaystyle q}
  
 being relatively prime polynomials of degree 
  
    
      
        n
        −
        ν
      
    
    {\displaystyle n-\nu }
  
 and 
  
    
      
        m
        −
        μ
      
    
    {\displaystyle m-\mu }
  
, minimizes the uniform norm of the difference 
  
    
      
        ‖
        f
        −
        g
        
          ‖
          
            ∞
          
        
      
    
    {\displaystyle \|f-g\|_{\infty }}
  
 if and only if there are 
  
    
      
        m
        +
        n
        +
        2
        −
        min
        {
        μ
        ,
        ν
        }
      
    
    {\displaystyle m+n+2-\min\{\mu ,\nu \}}
  
 points 
  
    
      
        a
        ≤
        
          x
          
            0
          
        
        <
        
          x
          
            1
          
        
        <
        ⋯
        <
        
          x
          
            m
            +
            n
            +
            1
            −
            min
            {
            μ
            ,
            ν
            }
          
        
        ≤
        b
      
    
    {\displaystyle a\leq x_{0}<x_{1}<\cdots <x_{m+n+1-\min\{\mu ,\nu \}}\leq b}
  
 such that 
  
    
      
        f
        (
        
          x
          
            i
          
        
        )
        −
        g
        (
        
          x
          
            i
          
        
        )
        =
        σ
        (
        −
        1
        
          )
          
            i
          
        
        ‖
        f
        −
        g
        
          ‖
          
            ∞
          
        
      
    
    {\displaystyle f(x_{i})-g(x_{i})=\sigma (-1)^{i}\|f-g\|_{\infty }}
  
 where 
  
    
      
        σ
      
    
    {\displaystyle \sigma }
  
 is either -1 or +1.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="algorithms">Algorithms</h2>
<p>Several <a href="/facts/Minimax_approximation_algorithm/A6EEMLwY">minimax approximation algorithms</a> are available, the most common being the <a href="/facts/Remez_algorithm/PcTjtFCs">Remez algorithm</a>.
</p>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20110702221651/http://www.math.uiowa.edu/~jeichhol/qual%20prep/Notes/cheb-equiosc-thm_2007.pdf">Notes on how to prove Chebyshev’s equioscillation theorem</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived July 2, 2011)</li>
<li><a href="http://www.maa.org/publications/periodicals/loci/joma/the-chebyshev-equioscillation-theorem">The Chebyshev Equioscillation Theorem by Robert Mayans</a></li>
<li><a href="http://encyclopediaofmath.org/index.php?title=De_la_Vall%C3%A9e-Poussin_theorem&oldid=44785">The de la Vallée-Poussin alternation theorem</a> at the Encyclopedia of Mathematics</li>
<li><a href="https://xn--2-umb.com/22/approximation/index.html">Approximation theory by Remco Bloemen</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Golomb, Michael (1962). Lectures on Theory of Approximation. <a href="https://books.google.com/books?id=DbnPAAAAMAAJ" target="_blank">https://books.google.com/books?id=DbnPAAAAMAAJ</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Golomb, Michael (1962). Lectures on Theory of Approximation. <a href="https://books.google.com/books?id=DbnPAAAAMAAJ" target="_blank">https://books.google.com/books?id=DbnPAAAAMAAJ</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>"Notes on how to prove Chebyshev's equioscillation theorem" (PDF). Archived from the original (PDF) on 2 July 2011. Retrieved 2022-04-22. <a href="https://web.archive.org/web/20110702221651/http://www.math.uiowa.edu/~jeichhol/qual%20prep/Notes/cheb-equiosc-thm_2007.pdf" target="_blank">https://web.archive.org/web/20110702221651/http://www.math.uiowa.edu/~jeichhol/qual%20prep/Notes/cheb-equiosc-thm_2007.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Golomb, Michael (1962). Lectures on Theory of Approximation. <a href="https://books.google.com/books?id=DbnPAAAAMAAJ" target="_blank">https://books.google.com/books?id=DbnPAAAAMAAJ</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Equioscillation theorem open-in-new

Equioscillation theorem