5
$\begingroup$

The problem comes in two parts:

  1. Find an $\epsilon > 0$ such that for every $x\in[0,1]$ $$\left\lvert \sqrt{x}-\sqrt{x+\epsilon}\right\rvert \le \frac{1}{200}$$

We can show that $\left\lvert \sqrt{x}-\sqrt{x+\epsilon}\right\rvert $ decreases as $x$ increases to 1, so it's enough to consider the case where $x=0$ and we see that we can use $\epsilon = 1/200^2$.

  1. (The part I didn't get or at least am not satisfied with.) Find a polynomial $P(x)$ such that for every $x\in[0,1]$ $$\left\lvert \sqrt{x}-P(x)\right\rvert \le \frac{1}{100}$$

Hint: Use the power series expansion of $\sqrt{x+\epsilon}$ around $x=1$.

Here's my work so far

First note that $$\left\lvert \sqrt{x}-P(x)\right\rvert \le \left\lvert \sqrt{x}-\sqrt{x+\epsilon}\right\rvert + \left\lvert \sqrt{x+\epsilon} - P(x)\right\rvert $$

If we can find a P(x) such that $\left\lvert \sqrt{x+\epsilon} - P(x)\right\rvert \le 1/200$, then we can use part 1 and be done. So then I tried using the hint:

$$\sqrt{x+\epsilon} = \sqrt{1+\epsilon} + \frac{1}{2}(1+\epsilon)^{-1/2}(x-1)- \frac{1}{8}(1+\epsilon)^{-3/2}(x-1)^2 + \ldots$$

The tricky part here is that we can't get a nice uniform bound on $f^{(k)}(\xi), \xi\in[0,1]$, where $f(x) = \sqrt{x+\epsilon}$, because around $x=0$ it blows up. Note for the remainder term we have

$$\left\lvert \frac{f^{k}(\xi)}{k!}(x-1)^k\right\rvert \le \left\lvert \frac{f^{k}(\xi)}{k!}\right\rvert $$

In other words, the remainder is largest in abs. value when $x=0$, so we can just focus on the Taylor series expansion after substituting $x=0$. The expansion becomes

$$\sqrt{1+\epsilon} - \frac{1}{2}(1+\epsilon)^{-1/2} - \frac{1}{8}(1+\epsilon)^{-3/2} - \ldots$$

Note that $$\frac{1}{(1+\epsilon)^{(2k-1)/2}}\le 1$$ so $$\sqrt{1+\epsilon} - \frac{1}{2}(1+\epsilon)^{-1/2} - \frac{1}{8}(1+\epsilon)^{-3/2} - \ldots \ge \sqrt{1+\epsilon} - \frac{1}{2}-\frac{1}{8} - \ldots$$

and the coefficients are monotonically decreasing. The form of the coefficients is $$a_k=\frac{1}{2^k k!}\prod_{n=1}^{k-1} (2n-1)$$ Recall that we should be converging to 0, so each new term we add moves us closer to 0.

That's as far as I've gotten. I don't know if that was the right route, and also how to proceed from here. Maybe I've just stared at this for too long, but either way I'd like to get some feedback. Maybe there's a better way to go about this.

Thanks!

Update I tried out my solution with Mathematica, and it seems to work. The problem is that I had to expand the Taylor series to ~12800th order. This question should be answerable without Mathematica (it is taken from an old exam).

$\endgroup$
3
  • $\begingroup$ Is that in regard to the first part? Anyways, looks like it's maximized at x=0, and going from there we see that it's less than or equal to $\sqrt{\epsilon}$, which leads us to the same answer I posted for the first part. $\endgroup$
    – Kurt
    Jul 1, 2016 at 23:29
  • $\begingroup$ No problem, I made it bold now so it's more obvious what I'm actually asking. $\endgroup$
    – Kurt
    Jul 1, 2016 at 23:31
  • $\begingroup$ For polynomial approximation with a given accuracy, look into Chebyshev polynomials, eg embeddedrelated.com/showarticle/152.php. Its a pretty standard method in numerical analysis. $\endgroup$
    – Chip
    Jul 7, 2016 at 3:18

2 Answers 2

3
+50
$\begingroup$

Your approach looks good and the only missing piece is to bound the remainder of the Taylor polynomial to get an explict bound on $N$ (the degree of the polynomial) such that the bound $|\sqrt{x+\epsilon} - P(x)| < \frac{1}{200}$ holds. This is what I will show here.


The $N$th derivative of $\sqrt{x}$ is given by

$$\frac{d^n}{dx^n}\sqrt{x} = x^{\frac{1}{2}-n}\frac{1}{2}\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right)\cdots \left(-\frac{2n-3}{2}\right) = x^{\frac{1}{2}-n}\frac{(2n)!}{n!4^n}\frac{(-1)^{n-1}}{2n-1}$$

If we let $P(x)$ be the $N$th order Taylor polynomial of $\sqrt{x+\epsilon}$ about $x=1$ then using the result above we get

$$\sqrt{x+\epsilon} - P(x) = \sqrt{1+\epsilon}\sum_{n=N}^\infty {2n\choose n}\frac{(-1)^{n+1}}{2n-1}\left(\frac{x-1}{4(1+\epsilon)}\right)^n$$

Since $\epsilon > 0$ and $x\in[0,1]$ we therefore have

$$|\sqrt{x+\epsilon} - P(x)| < \sqrt{1+\epsilon}\sum_{n=N}^\infty {2n\choose n}\frac{1}{(2n-1)4^n}$$

From Stirlings approximation it follows that $${2n \choose n}\frac{1}{4^n} = \frac{1}{\sqrt{\pi n}}\left(1 - \frac{1}{8n} + O(n^{-2})\right) < \frac{1}{\sqrt{\pi n}}$$ so the sum above is bounded by

$$|\sqrt{x+\epsilon} - P(x)| < \frac{\sqrt{1+\epsilon}}{\sqrt{\pi}}\sum_{n=N}^\infty \frac{1}{(2n-1)\sqrt{n}} < \frac{\sqrt{1+\epsilon}}{\sqrt{\pi}}\sum_{n=N-1}^\infty \frac{1}{2n^{3/2}}$$

Since $n^{-3/2}$ is monotonically decreasing we have

$$\sum_{n=N-1}^\infty \frac{1}{2n^{3/2}} < \int_{N-2}^\infty\frac{{\rm d}x}{2x^{3/2}} = \frac{1}{\sqrt{N-2}}$$

which gives us

$$|\sqrt{x+\epsilon} - P(x)| < \left(\frac{1+\epsilon}{\pi(N-2)}\right)^{1/2}$$

which is less than $\frac{1}{200}$ when $N > \frac{200^2(1+\epsilon)}{\pi}+2 \approx 12735$. This is a fairly large value of $N$ - and such an approximation would not be very useful in practice - however it does solve the problem as stated and the approach is in line with the given hint. This is largely an effect of us trying to approximating a function that has a very non-polynomial behavior at a point in the interval (in this case $x=0$). There should however exist lower order polynomials that does the job here so I guess another take-home message here is that Taylor polynomials is not always the best ones to use to approximate a function over a larger interval.

$\endgroup$
10
  • $\begingroup$ Thanks I'll take a look at this later today. $\endgroup$
    – Kurt
    Jul 12, 2016 at 16:04
  • $\begingroup$ I'm going to post comments as I work through this. Here's the first one. I tried to prove your first expression for the derivative. I started with the right-hand side and and basically showed that it's equal to the left-hand side, except I end up with a 2^n in the numerator, even though the left-hand side should have 2^n in the denominator. Nevertheless, that's a clever way of expressing that large product in terms of factorials. $\endgroup$
    – Kurt
    Jul 14, 2016 at 18:48
  • $\begingroup$ I used Wolfram Alpha to calculate $\frac{d^{10}}{dx^{10}} \sqrt{x}$, and I think what I said was correct. If I used what you wrote but change it slightly to $$\frac{(2n)!}{2^{2n}(n!)}\frac{(-1)^{n-1}}{2n-1}x^{1/2-n}$$, then I get the right answer. $\endgroup$
    – Kurt
    Jul 14, 2016 at 18:51
  • $\begingroup$ In your second equation you have $(1+\epsilon)^{-n}$. I believe that should be $(1+\epsilon)^{-1/2}$. And as for my above comment, I see that in the second equation the factor of $2^{-2n}$ appears as $4^{-n}$. It's not in the first equation though, but at least it doesn't affect anything down the line. The same thing goes for this comment about the $(1+\epsilon)$ term. It doesn't change anything. $\endgroup$
    – Kurt
    Jul 14, 2016 at 19:05
  • $\begingroup$ I think the bound for Stirling's isn't quite right. It's really more of an approximation than a bound. I ended up with $$\binom{2n}{n} \frac{1}{4^n} \le \frac{e}{\pi\sqrt{2n}}$$, which is close to what you got, but a little larger. $\endgroup$
    – Kurt
    Jul 14, 2016 at 19:32
2
$\begingroup$

Take any $k\geq \sqrt 2$ and $e= k^{-2}.\;$ For $x\in [0,1] $ let $y= x+e-1.$ Then $$\sqrt {x+e} =\sqrt {1+y} .$$ And for all $x\in [0,1]$ we have $$|\sqrt x-\sqrt{1+y}|=|\sqrt x -\sqrt {x+e}|\leq 1/k.$$ $$\text {Now we have }\quad e-1\leq y\leq e$$ $$\text {so }\quad |y|\leq 1-e<1 \text { because } 0<e\leq 1/2.$$ $$ \text {Since } |y|<1 \text { we have }\quad \sqrt {1+y}=\sum_{n=0}^{\infty}y^n \binom {1/2}{n}.$$ Since $|\binom {1/2}{n}|\leq 1$ (by induction on $n$), an upper bound for the absolute value of the remainder of the infinite series, after the term of degree $n,$ is $$U_{n.k}=\sum_{j=n+1}^{\infty}|y|^j.$$ $$\text { We have }\quad U_{n,k}=|y|^{-n-1}/(1-|y|)\leq |y|^{-n-1}/e\leq (1-e)^{-n-1}/e.$$ The partial sum of the series ,up to the term of degree $n,$ is a polynomial $P_{n,k}(y) ,$ which is a polynomial $Q_{n,k}(x).$ If $n$ is large enough that $(1-e)^{-n-1}/e<1/k,$ then for all $x\in [0,1]$ we have $|Q_{n.k}(x)-\sqrt {x+e}|<1/k$ and also $|\sqrt {x+e}-\sqrt x|\leq 1/k , $ so $$|\sqrt x- Q_{n,k}(x)|\leq 2/k.$$ And $k$ can be arbitrarily large.

Remark:$\binom {1/2}{0}=1,$ and $\binom {1/2}{1}=1/2, $ and for $n\geq 1:\;$ $\;\binom {1/2}{n+1}=\binom {1/2}{n}(1/2-n)/(n+1).$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .