3
$\begingroup$

Let's say we have some polynomial of degree 2: $P(x) = 2x^2 - 7x + 6$. How can I find polynomial $Q(x)$ of degree at most 1 such that maximum value of $|P(x) - Q(x)|$ in range $x\in[0,1]$ is minimum.

Is there any trick for this kind of problems?

I have tried to set $Q(x) = ax + b$, then I can see that $b$ just shifts the range of $P(x) - Q(x)$. Since values of $x$ are positive, it kind of make sense to set $a=7$, but I am not sure.

$\endgroup$
3
  • $\begingroup$ I guess the Hilbert matrix would play a critical role in this problem since you have the desired coefficients for it. But, I am not sure how the procedure for determining polynomial $Q$ could be translated to the solution of the Hilbert matrix. $\endgroup$ – Snowflake Jun 14 at 23:41
  • $\begingroup$ Or maybe, the major idea could be the application of Chebyschev's polynomials and their involved inequalities?! $\endgroup$ – Snowflake Jun 14 at 23:58
  • 3
    $\begingroup$ Hints: * show that if you can solve it for one quadratic polynomial then you can solve it for any quadratic polynomial; * solve the problem instead for $P(x) = x(1-x)$—the symmetry with respect to $[0,1]$ should make this simpler. $\endgroup$ – Greg Martin Jun 15 at 0:11
4
$\begingroup$

Your problem is a straightforward application of Chebyshev's Equioscillation Theorem.

Since $P$ is convex, all you have to do is:

  1. Draw the secant through $(0,P(0))$ and $(1,P(1))$ i.e. $y=-5x+6$
  2. Calculate maximum $y$-distance between the secant and $P$ i.e. $\max\{-5 x + 6 - (2 x^2 - 7 x + 6)\} = 1/2$ at $x = 1/2$
  3. Bring the secant halfway down: $y=-5x+6-\frac{1}{4}=-5x+\frac{23}{4}$
  4. Use Equioscillation Theorem to prove that $Q(x)=-5x+\frac{23}{4}$ is the linear approximation you are looking for ($x_0=0, x_1=1/2$ and $x_2=1$).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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