Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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 <x_3 \in [0,0.8]$ 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$.

share|improve this answer
    
It is obvious if one knows $L^\infty$ approximation theory for polynomials. Nice job! –  hardmath Jun 29 '12 at 21:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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