## 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

.

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

### Like this:

Like Loading...

*Related*

on December 5, 2011 at 10:30 pm |bartogianWhat 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 |Qiaochu YuanElementary is in the eye of the beholder, I suppose. It’s up to you.

on December 6, 2011 at 1:22 am |mortid0Upper 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 |RasmusQiaochu, your link is not directing to the question itself but to your answer it.

on January 3, 2012 at 3:10 pm |Qiaochu YuanI suppose that’s not ideal. Fixed.

on January 19, 2012 at 11:55 am |Christian BlatterI 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 |Luke GAnother 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 |Qiaochu YuanNice. 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 |truyen sexUpper 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. ??