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

Question

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.

Answer 1

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

• a theorem due to de la Vallee-Poussin (slide 4) for approximating the minimax error without having to calculate the approximation itself (not to be confused with de la Vallee-Poussin's theorem on uniform integrability)

• Chebyshev's equioscillation theorem

• and Chebyshev polynomials of the first kind which are useful for near minimax approximations.

Answer 2

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$