Square root using Taylor series
I would like to calculate the square root using the Taylor series. I just found out about the show and I wrote some code but I don't know why it doesn't work, maybe I shouldn't feed it i
? Please, can anyone explain to me what I am doing wrong?
I have a formula 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)
source to share
There are two questions: one junior and one major. The downside is that the decomposition is written in terms (1+x)^alpha
, not x^alpha
, so yours i**k
should really be (i-1)**k
. This will exit
1.41920471191 1.0
5.234375 1.41421356237
where you can see how to suspiciously close your answer for sqrt(1)
on sqrt(2)
in
1.0 1.0
1.41920471191 1.41421356237
which is much better. Unfortunately, the remaining conditions are still not 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 summarized 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 as you'd expect, because as the page you linked explains, it's only guaranteed by convergence 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 to scale everything 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 a Taylor series around another point, etc.
The general gap is that the Taylor series has a convergence radius - perhaps zero! - within which they give correct results. The Taylor Wikipedia series page has an Approximation and Convergence section that covers this.
(PS No "c" in "binomial" .: ^)
source to share