Description:
<p>Suppose that the first <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m">
<mml:semantics>
<mml:mi>m</mml:mi>
<mml:annotation encoding="application/x-tex">m</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> Fourier coefficients of a piecewise analytic function are given. Direct expansion in a Fourier series suffers from the Gibbs phenomenon and lacks uniform convergence. Nonetheless, in this paper we show that, under very broad conditions, it is always possible to recover an <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n">
<mml:semantics>
<mml:mi>n</mml:mi>
<mml:annotation encoding="application/x-tex">n</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>-term expansion in a different system of functions using only these coefficients. Such an expansion can be made arbitrarily close to the best possible <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n">
<mml:semantics>
<mml:mi>n</mml:mi>
<mml:annotation encoding="application/x-tex">n</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>-term expansion in the given system. Thus, if a piecewise polynomial basis is employed, for example, exponential convergence can be restored. The resulting method is linear, numerically stable and can be implemented efficiently in only <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper O left-parenthesis n m right-parenthesis">
<mml:semantics>
<mml:mrow>
<mml:mrow class="MJX-TeXAtom-ORD">
<mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi>
</mml:mrow>
<mml:mrow>
<mml:mo>(</mml:mo>
<mml:mi>n</mml:mi>
<mml:mi>m</mml:mi>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
<mml:annotation encoding="application/x-tex">\mathcal {O} \left (n m\right )</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> operations.</p>
<p>A key issue is how the parameter <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m">
<mml:semantics>
<mml:mi>m</mml:mi>
<mml:annotation encoding="application/x-tex">m</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> must scale in comparison to <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n">
<mml:semantics>
<mml:mi>n</mml:mi>
<mml:annotation encoding="application/x-tex">n</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> to ensure such recovery. We derive analytical estimates for this scaling for large classes of polynomial and piecewise polynomial bases. In particular, we show that in many important cases, including the case of piecewise Chebyshev polynomials, this scaling is quadratic: <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m equals script upper O left-parenthesis n squared right-parenthesis">
<mml:semantics>
<mml:mrow>
<mml:mi>m</mml:mi>
<mml:mo>=</mml:mo>
<mml:mrow class="MJX-TeXAtom-ORD">
<mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi>
</mml:mrow>
<mml:mrow>
<mml:mo>(</mml:mo>
<mml:msup>
<mml:mi>n</mml:mi>
<mml:mn>2</mml:mn>
</mml:msup>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:mrow>
<mml:annotation encoding="application/x-tex">m=\mathcal {O}\left (n^2\right )</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>. Therefore, with a system of polynomials that the user is essentially free to choose, one can restore exponential accuracy in <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n">
<mml:semantics>
<mml:mi>n</mml:mi>
<mml:annotation encoding="application/x-tex">n</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula> and root-exponential accuracy in <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m">
<mml:semantics>
<mml:mi>m</mml:mi>
<mml:annotation encoding="application/x-tex">m</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>. This generalizes a result proved recently for piecewise Legendre polynomials.</p>