# How to best approximate higher-degree polynomial in space of lower-degree polynomials?

My question is: Find the best 1-degree approximating polynomial of $f(x)=2x^3+x^2+2x-1$ on $[-1,1]$ in the uniform norm(NOT in the least square sense please)?

Orginially, as the title of the post suggests, I'm asking the general problem: given an $n$-th degree polynomial $p(x)$ on $[-1,1]$, find the best approximation $q(x)$ in lower degree($j<n$) polynomial space: $\min_{\operatorname{deg}q(x)=j} \max_{x\in[-1,1]}\| p(x)-q(x)\|$. Now I realize it's too difficult. I woud be content if someone can give me answer to the question above.

-

This is called the minimax approximation problem and we will use some geometry to help us solve this problem. First define

$$\epsilon(x)=2x^3+x^2+2x-1-(ax+b)$$

So looking at this picture here, the blue curve is the cubic function we are trying to approximate. And the purple curve is what our minimax approximation should roughly looks like. Let us define the max absolute error

$$\rho=\max_{-1\leq x \leq1}|\epsilon(x)|$$

we also see here that this max error is achieved exactly at three points

$$\epsilon(-1)=\rho=\epsilon(1) \textrm{ and } \epsilon(x_1)=-\rho$$

where I have the fat red vertical line at $x=x_1$. In addition, $\epsilon(x)$ achieves its minimum at $x=x_1$ so we have $\epsilon'(x_1)=0$. So now we solve four equations with four unknowns (a nonlinear system in this case) and get

$$a=4,b=\frac{-35-13\sqrt{13}}{108},x_1=\frac{-1+\sqrt{13}}{6},\rho=\frac{35+13\sqrt{13}}{108}$$

or better yet

$$a=4,b=-0.758076,x_1=0.434259, \rho=0.758076$$

so we know what the minimax line is, what the max error is and where is it achieved. In case you get two solutions while trying to solve this system, then remember to pick the solution where $\rho$ is positive.

Oh and the algorithm you are looking for is Remez algorithm and you might also want to look at

-
Please note that max error is not achieved in three points... Actually in four points –  Occupy Gezi Jun 11 '13 at 14:16
Thanks for the answer and good references. It's interesting to know de la Valee-Poussin theorem. –  user33869 Jun 11 '13 at 14:22

I guess you can directly use least squares approximation in continous domain such as $$min\,\int_{-1}^{1}\big(f(x)-P^*(x)\big)^2dx$$ where $$\int_{-1}^{1}\big(2x^3+x^2+2x-1-(ax^2+bx+c)\big)^2dx$$ $$=\frac{848}{105}+\frac{8 a}{15}+\frac{2 a^2}{5}-\frac{64 b}{15}+\frac{2 b^2}{3}+\frac{8 c}{3}+\frac{4 a c}{3}+2 c^2$$ Minimizing w.r.t. $a,b,c$ yields following values $$a=1\,b=16/5\,c=-1$$ On below graph you can see the results. Blue is the original one; red your result and green the result from LS approximation.

Repeating same procedure for 1-degree with $P^*(x)=ax+b$ $$\int_{-1}^{1}\big(2x^3+x^2+2x-1-(ax+b)\big)^2dx=\frac{848}{105}-\frac{64 a}{15}+\frac{2 a^2}{3}+\frac{8 b}{3}+2 b^2$$ and the resulting function is $P^*(x)=\frac{16}5x-\frac 23$

------------EDIT--------------------

You are looking for minimax polynomials. In this case we want to minimize $||f(x)-P^*(x)||_\infty$ hence $$\text{min}_{a,b}\big(\text{max}_{[-1,1]}|2x^3+x^2+2x-1-(ax+b)|\big)$$ Since the derivative on $[-1,1]$ is positive maximum error can ocur in three possibilities $$x=-1\Rightarrow\quad -4-(-a+b)=e\qquad (1)$$ $$x=k\Rightarrow\quad 2k^3+k^2+2k-1-ak-b=-e\qquad (2)$$ $$x=1\Rightarrow\quad 4-(a+b)=e\qquad (3)$$ To find the point $x=k$ we have to maximize the error such as $$\frac{d}{dx}\big( 2x^3+x^2+2x-1-(ax+b)\big)_{x=k}=0\Rightarrow=a=6k^2+2k+2\qquad (4)$$ By solving equations $(1)$ and $3$ we find that $a=4$. Then we can solve equation $(4)$ to give $$k_1=-0.7676\text{ and }k_2=0.4343$$ If we set $k_1=-0.7676$ then $b=0.1099$ which produces below graph

If we set $k_2=0.4343$ then $b=-0.7581$ which produces below graph

For these results we can say the best uniform approximation can be given by $P^*(x)=4x-0.7581$

-
Thanks a lot for putting so many efforts in answering my question! However, my question is about uniform norm convergence, not $L^2$ convergence. The least square fit doesn't apply here. We need to invoke the minmax property of Chebyschev functions to get the desired result. –  user33869 Jun 10 '13 at 3:43
But I see the point here. The solution I gave can't be the best approximation. Let me think more about this one. –  user33869 Jun 10 '13 at 4:16
It turns out there is a typo in my post. The constant term in $P^*(x)$ should be -1 instead of +1. I've corrected that. –  user33869 Jun 10 '13 at 4:29
@user33869 please note that max error may occur in four points, not three. –  Occupy Gezi Jun 11 '13 at 14:19
Thanks for the perfect answer. I'm a little surprised to see inserting a line is not so simple, let alone quadratics. –  user33869 Jun 11 '13 at 14:20