0
$\begingroup$

In connection with a CompSciSE question about largest eigenvalue of PSD matrics, I'd like to know which (nonzero) quadratic polynomial $f(x)$ minimizes the ratio:

$\frac{\max_{0 \le x \le 0.8} |f(x)|}{|f(1)|}$

[The goal is making a robust improvement on the simple power method's rate of convergence without having to code a Lanczos-like algorithm.]

Of course the method of solution is of greater interest than the specific polynomial. I see that the answer is not unique, insofar as any nonzero multiple of $f(x)$ gives the same ratio. So perhaps one wants to restrict attention to the cases $f(1) = 1$.

1 Answers 1

2

You want to minimize $t$ such that $-t \le f(x) = a_0 + a_1 x + a_2 x^2 \le t$ for all $x \in [0,0.8]$ and $f(1)=1$. Think of this as a linear programming problem with infinitely many constraints and four (sign-free) variables $t$, $a_0$, $a_1$, $a_2$. At an optimal solution, four of the constraints should be binding. One must be $f(1) = 1$ (otherwise we could scale everything), so there should be three points $x_1 < x_2 with $f(x_i) = \pm t$. Since the graph of your quadratic is a parabola, it's clear that $x_1 = 0$, $x_2 = 0.4$, $x_3 = 0.8$, and $f(x) = - t + 2 t (x - 0.4)^2/0.4^2$. This would have $f(1) = 3.5 t$, so the optimal answer is $t = 1/3.5 = 2/7$, and the quadratic is $-2/7 + 4/7 (x - 0.4)^2/0.4^2 = (25 x^2 - 20 x + 2)/7$.

  • 0
    It is obvious *if* one knows $L^\infty$ approximation theory for polynomials. Nice job!2012-06-29