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.

About these ads

Posted in analysis | Tagged estimation | 9 Comments

9 Responses

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

Comments RSS

Follow “Annoying Precision”

%d bloggers like this:

	Viliam Búr on Writing a blog post every day…
	Qiaochu Yuan on A puzzle about operations
	Omar on A puzzle about operations
	A puzzle about opera… on Operations and Lawvere th…
	Qiaochu Yuan on Operations and Lawvere th…

Annoying Precision

"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is." – John von Neumann