Estimating roots

Feeds:: Posts; Comments

Estimating roots

December 5, 2011 by Qiaochu Yuan

In lieu of a real blog post, which will have to wait for at least another two weeks, let me offer an estimation exercise: bound, as best you can, the unique positive real root of the polynomial

$\displaystyle x^{10000} + x^{100} - 1$ .

The intermediate value theorem shows that $x \in (0, 1)$ , which was the subject of a recent math.SE question that provided the inspiration for this question. I provide a stronger lower bound on $x$ using elementary inequalities and entirely by hand in an answer to the linked question, although I don’t try to improve the upper bound.

Posted in math.CA, Uncategorized | 9 Comments

9 Responses

on February 16, 2012 at 12:57 am | Reply truyen sex

Upper bound comes from derivative: 10000x^9999+100x^99. It is increasing with x, so tangent line at x=1 would be lower then our polynomial. ??
on January 19, 2012 at 11:29 pm | Reply Luke G

Another alternative… (I’m not on mathSE so feel free to repost this there)

We have 1 = x^100+x^10000. By AM-GM, x^100+x^10000 >= 2x^5050. So x <= (1/2)^(1/5050) < .99987. You can bound it even better using weighted AM-GM; something like .99972 using 100:1 weighting for x^100 to x^10000. (In fact, with the right weights, you can recover the answer exactly, but to choose the weights you'd have to already know the answer.)

A reasonable lower bound comes from 1=x^100(1+x^9900) = .99939.
- on January 20, 2012 at 8:01 am | Reply Qiaochu Yuan
  
  Nice. I suppose you could alter the weights based on your previous estimates and get an iterative scheme for getting better upper bounds.
on January 19, 2012 at 11:55 am | Reply Christian Blatter

I have posted not so bad bounds at the stock exchange site where the problem originally appeared:

http://math.stackexchange.com/questions/88567/prove-that-the-equation-x10000-x100-1-0-has-a-solution-with-0-x/100552#100552
on January 3, 2012 at 2:30 pm | Reply Rasmus

Qiaochu, your link is not directing to the question itself but to your answer it.
- on January 3, 2012 at 3:10 pm | Reply Qiaochu Yuan
  
  I suppose that’s not ideal. Fixed.
on December 6, 2011 at 1:22 am | Reply mortid0

Upper bound comes from derivative: 10000x^9999+100x^99. It is increasing with x, so tangent line at x=1 would be lower then our polynomial.
Line equation is y = 10100x + b, where 10100 is value of derivative at 1. As line must go throw point (1,1) then b = -10099. And our tangent line intersects x-axis at 10099/10100.(This is just first iteration of Newton’s method).

Lower bound comes from observation that x^10000+x^100-1 looks like symmetric parabola. So we can find simple function g(x) = ax^100+b that is always greater than our polynomial on (0; 1). Let it go throw points (0; -1) and (1; 1). Than a = 2 and b = -1.
2*x^100 – 1 > x^10000+x^100-1 on (0; 1).

And g(x) crosses x-axis at (1/2)^(1/100).

So root is inside ((1/2)^(1/100); 10099/10100) or (0.993; 0.99991)

Drawing graphics can explain better 🙂
on December 5, 2011 at 10:30 pm | Reply bartogian

What counts as elementary? The function at hand is visibly convex, so its graph lies above the graph of any tangent. Taking the tangent at (1,1) gives a start on improving the upper bound. (this is of course just the first approximation in an application of Newton’s algorithm).
- on December 6, 2011 at 4:08 am | Reply Qiaochu Yuan
  
  Elementary is in the eye of the beholder, I suppose. It’s up to you.

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos