If I have a $n+1$ degree polynomial $f(x)$ that approximate the function $g(x)$ on the interval $[-1,1]$. After that, if I lose $g(x)$, just know $f(x)$, how to find a $n$ degree polynomial that is closest to $g$ in maximum norm?
Asked
Active
Viewed 207 times
2
-
What norm do you have in mind? – vonbrand Mar 02 '13 at 01:06
-
@vonbrand Max|g(x)-h(x)| – 89085731 Mar 02 '13 at 01:14
-
2I like the question and upvoted it, but it's regrettable that after asking $80$ questions you still haven't made the effort to learn how to format them. Here's a tutorial that covers all the basics. Also please note that for someone used to reading text with standard punctuation, it's rather visually jarring to read a text without spaces after punctuation marks, so if you don't mind it would be great if you could add them in the future. – joriki Mar 02 '13 at 01:27
-
1By triangle inequality it seems reasonable to minimize $h-f$ in the maximum norm, where $h$ is an $n$ degree polynomial, and $f$ is the original $(n+1)$ degree approximation. – Shuhao Cao Mar 02 '13 at 01:31
-
I did your formatting for you. Don't let this happen again! – Gerry Myerson Mar 02 '13 at 05:30
1 Answers
5
In view of the triangle inequality, we just have to approximate $f$ by another polynomial (which I'll call $h$) of degree $n$. Suppose $s$ is any other polynomial of degree $n+1$ that has the same leading coefficient as $f$. Then $h = f - s$ will have degree $n$, so it's a step in the right direction. The trick is to choose an $s$ with a small norm, so that $h$ is as close to $f$ as possible. The polynomials with smallest max norms are the Chebyshev polynomials, so the optimal choice is:
$$h(x) = f(x) - \frac{c}{2^{n}}T_{n+1}(x)$$
where $c$ is the leading coefficient of $f$, and $T_{n+1}(x)$ is the Chebyshev polynomial of the first kind of degree $n+1$.
You can read about Chebyshev polynomials (including their minimum norm properties) on the wikipedia page
bubba
- 43,483
- 3
- 61
- 122