16
$\begingroup$

For teaching purposes I'd need a continuous function of a single variable that is "difficult" to approximate with polynomials, i.e. one would need very high powers in a power series to "fit" this function well. I intend to show my students the "limits" of what can be achieved with power series.

I thought about concocting something "noisy", but instead of rolling my own I am just wondering whether there is a kind of standard "difficult function" that people use for testing approximation / interpolation algorithms, somewhat similarly to those optimisation test functions that have numerous local minima where naive algorithms get stuck easily.

Apologies if this question is not well-formed; please have mercy on a non-mathematician.

Improve this question
$\endgroup$

6 Answers 6

Reset to default
14
$\begingroup$

Why not simply show the absolute value function?

Approximation with e.g. Legendre-polynomial expansion works, but pretty badly:

Sequential approximation of the absolute-value function by polynomials

Taylor expansion is of course completely useless here, always giving only a linear function, either always decreasing or always increasing (depending on whether the point you expand around is negative or positive).

Improve this answer
$\endgroup$
6
  • $\begingroup$ You can interpolate |x| using Chebyshev interpolation, see nbviewer.jupyter.org/github/cpraveen/na/blob/master/… which converges quite fast. E.g., you can change N=2*i in the code to N=15+i and test larger degree. It is not an expansion method but still based on polynomials. $\endgroup$
    – cfdlab
    Commented Sep 7, 2018 at 2:26
  • $\begingroup$ @PraveenChandrashekar Chebyshev works “better” because it puts more weight on the outer parts of the interval, where the function is smooth. Thus the excessive oscillation is avoided, but saying it approximates the function better is dubious – it does in particular capture the sharp turn at $x=0$ even worse than uniform-discrete-points or $L^2$-minimisation. If your goal is avoiding high-frequency components, better use an integral transformation that properly damps these components. $\endgroup$
    – leftaroundabout
    Commented Sep 7, 2018 at 9:59
  • $\begingroup$ It is perfectly fine to have non-uniform points as in Chebyshev interpolation. With degree about 20, it gives a lot more accurate approximation than Legendre that you show in your post. Measure the errors to be more quantitative. You can also do Chebyshev series approximation of |x| which is more accurate than Legendre expansion. $\endgroup$
    – cfdlab
    Commented Sep 7, 2018 at 16:02
  • $\begingroup$ @PraveenChandrashekar the point is that polynomials are in principle not able to approximate a function like $x \mapsto |x|$ properly. There are different methods each of which fails a bit more or less spectacularly, but none of them work well in the sense of “only a few terms give something that could be mistaken for the original function”. If you must use polynomials, you need to consider which kinds of error are more problematic, Legendre and Chebyshev both have their use cases but there's no silver bullet. Ultimately, an approach with e.g. splines is typically more effective. $\endgroup$
    – leftaroundabout
    Commented Sep 7, 2018 at 17:52
  • $\begingroup$ We know there is no perfect method. The question is what functions are difficult for polynomials to approximate. So one has to see all possible methods involving polynomials to conclude none of them do a good job. The Legendre is not the best way to approximate |x| and hence it gives a rather false impression that polynomials are too bad for |x|. With Chebyshev you have convergence and far better approximations than Legendre, they dont oscillate so badly as Legendre, though converge slowly near x=0, where function is not smooth enough. $\endgroup$
    – cfdlab
    Commented Sep 8, 2018 at 2:42
10
$\begingroup$

It's a pathological case, but you can always resort to the Weierstrass monster function. It illustrates a broader point, namely that functions that are not smooth -- e.g., that have a kink -- are difficult to approximate because the interpolation error estimates require the function being interpolated to be differentiable a number of times. In other words, if you don't like the Weierstrass function too much, you can always just choose $|x|$.

Improve this answer
$\endgroup$
0
6
$\begingroup$

Approximation is not only made hard by the function to be approximated but by the interval in which the approximation should be a "good fit". And you should define the measure for a "good fit", i.e. what is the maximum (absolute or relative) error you wish to tolerate?

For example, you will need a huge number of terms in the Taylor series of $\exp(x)$ to have a reasonable fit on the interval $[0,10]$. The same holds for periodic functions. Take $\sin(x)$, for example, on the interval $[0,2\pi]$. See pictures below... enter image description hereenter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ I show such examples in my course to make the point that Taylor expansion is not a good method to approximate functions. $\endgroup$
    – cfdlab
    Commented Sep 7, 2018 at 16:16
6
$\begingroup$

Polynomials are surprisingly effective at function approximation [1]. If you have at least Lipschitz continuity, then Chebyshev approximations will converge. Of course, convergence may be slow, and that is the price we pay for dealing with a non-smooth function.

Today, computers are much faster than the days in which many numerical analysis books were written, and clever algorithms have increased the speed further, so that having to use more terms may not be as bad as it used to be.

The pathological examples like Weierstrass monster function are interesting from a theoretical point of view, but they are not representative of most real application contexts.

I think we should be careful not to give a pessimistic view to our students. Ok, there is no method that works for all problems. But we can build adaptive methods, say even based on polynomials, that can deal with such cases. For example, Chebfun [2] can easily approximate $|x|$ by automatically splitting the domain at $x=0$.

It is important to teach the difficulties in approximation with polynomials, but it also important to tell the students that we can build error estimates and adaptive algorithms that can deal with these issues.

[1] https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf

[2] http://www.chebfun.org

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for linking the "myth paper" by Lloyd Trefethen, a very good survey of the topic IMO, thanks. $\endgroup$
    – András Aszódi
    Commented Sep 18, 2018 at 11:32
2
$\begingroup$

$f(x) = \frac{1}{x^2+1}$ has this Maclaurin series expansion:

$\frac{1}{x^2+1} = 1-x^2+x^4-x^6+x^8-x^{10}+x^{12} - \ldots$

This converges for $-1<x<1$, but it diverges everywhere else. A polynomial approximation around $x=0$ will never get you anywhere near the right answer for $x=2$.

Improve this answer
$\endgroup$
0
$\begingroup$

$y = sin(x)$? Periodic functions should be difficult to approximate using polynomials, unless there is an option to restrict the polynomials to finite intervals.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Or even $y=\sin(\frac{1}{x})$ if you want to get wild around the origin. $\endgroup$
    – sfmiller940
    Commented Jan 22, 2019 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.