Square root using Taylor series

Question

I would like to compute square root using Taylor series. I'm just learning about the series and I wrote a bit of code but I don't know why it doesn't work, maybe I shouldn't feed `i` to it? Please can anyone explain to me what I'm doing wrong? I have the formula from http://en.wikipedia.org/wiki/Taylor_series#List_of_Maclaurin_series_of_some_common_functions ``` from math import sqrt def factorial(n): result = 1 for i in range(2, n+1): result *= i return result def binomical(alpha, n): result = 1 for i in range(0, n): result *= (alpha - i) return result / factorial(n) for i in range(1, 10): x = sum(binomical(0.5, k) * i ** k for k in range(10)) print x, sqrt(i) ```

Accepted Answer

There are two issues, one minor and one major. The minor is that the expansion is written in terms of `(1+x)^alpha`, not `x^alpha`, so your `i**k` should really be `(i-1)**k`. Doing this turns your output of

```
1.41920471191 1.0
5.234375 1.41421356237
```

where you can see how suspiciously close your answer for `sqrt(1)` is to `sqrt(2)` into

```
1.0 1.0
1.41920471191 1.41421356237
```

which is much better. Unfortunately the remaining terms still aren't very good:

```
5.234375 1.73205080757
155.677841187 2.0
2205.0 2.2360679775
17202.2201691 2.44948974278
91687.28125 2.64575131106
376029.066696 2.82842712475
1273853.0 3.0
```

and increasing the number of terms summed from 10 to 100 makes things even worse:

```
1.0 1.0
1.4143562059 1.41421356237
1.2085299569e+26 1.73205080757
3.68973817323e+43 2.0
9.21065601505e+55 2.2360679775
3.76991761647e+65 2.44948974278
2.67712017747e+73 2.64575131106
1.16004174256e+80 2.82842712475
6.49543428975e+85 3.0
```

But that's to be expected, because as the page you linked explains, this is only guaranteed to converge when the absolute value of x is less than 1. So we can do a good job of getting the roots of small numbers:

```
>>> i = 0.7
>>> sum(binomical(0.5, k) * (i-1) ** k for k in range(10))
0.8366601005565644
>>> i**0.5
0.8366600265340756
```

and we can try scaling things down to deal with other numbers:

```
>>> i0 = 123.0
>>> i = i0/(20**2)
>>> sum(binomical(0.5, k) * (i-1) ** k for k in range(50))
0.5545268253462641
>>> _*20
11.090536506925282
>>> i0**0.5
11.090536506409418
```

or take the Taylor series around a different point, etc.

The general take-away is that Taylor series have a radius of convergence -- possibly zero! -- within which they give the right results. The Wikipedia Taylor series page has a section on "Approximation and convergence" which covers this.

(P.S. No "c" in "binomial". :^)

Square root using Taylor series

Solution

Problem