It is in python coding HW 01: Newton\'s Method for nding roots of polynomials Fo
ID: 3879885 • Letter: I
Question
It is in python coding
HW 01: Newton's Method for nding roots of polynomials
For many people, their rst opportunity to do some "useful" programming was to make a program that computes roots of quadratic polynomials using the quadratic formula. For any of you who wished for such a method that works with other polynomials, I give you Newton's Method. Polynomials are very important to many areas of computer science. One of the most basic operations to do on a polynomial is to nd its roots. That is, nd the value such that . High school algebra classes spend a lot of time solving this problem on quadratic polynomials either by factoring or by the quadratic formula. More generally, there is a classic numerical method for nding roots of a polynomial. It called Newton's Method. It doesn't get the exact answer, rather it approximates the answer. The idea is to start with a guess and then update the guess based on the slope of the graph of the polynomial (i.e., it's derivative). Graphically, the idea is to imagine that the polynomial is linear and nd the root of the linear approximation at your current guess. Then repeat with the new guess. Technically, the algorithm starts with a guess and then repeatedly computes
where is the polynomial, and is the derivative of . You may have seen this in a calculus class. When you code it up, there is no reason to store the previous guesses. That is, if is assignment, one might as easily write:
Step 1: Compute Derivatives To compute the derivative of a polynomial is rather simple. First let's consider the case of monomials. For a constant monomial (the exponent is zero), the derivative is . Otherwise, for a monomial with , the derivative is . For example,
f x f(x) = 0
x0
x = x i+1 i
f (x ), i f(x ) i f f f
=
x = x
f (x), f(x)
0
axb b 0 abxb1
7 6
As another example,
Todo: Write a method called prime for the Monomial class that returns the derivative of the monomial (as a new Monomial). So, the following should work.
m = Monomial(3,7) assert(m.prime() == Monomial(21,6))
To compute the derivative of a polynomial, one merely adds up the derivatives of the (monomial) terms. So,
Todo: Next, write a method called prime in the Polynomial class that returns a new Polynomial that is the derivative of self . Step 2: Find the roots Start with a guess. It could be anything, but let's just try for simplicity. Store that guess in a variable. Then, repeatedly update the value of that variable using Newton's Method. Do some experiments to see what might be a good number of iterations for polynomials with integer roots. Todo: Write a method called root in the Polynomial class that computes a root of the polynomial. The method should take two parameters, a guess and a number of iterations . Set the default guess = 0 and the default iterations = 50 . Make some examples for yourself To make polynomials with xed roots , you can simply multiply together the polynomials . You can also check answers using Wolfram alpha. Note that Wolfram alpha will also give the complex roots. Watch out for division by zero A common problem is that you might get a ZeroDivisionError if you nd a value for which the
if f(x) = 3x then f (x) = 21x . 7 6
if g(x) = 2x then g (x) = 10x . 5 4
if p(x) = 3x +2x + x +135 then p (x) = 21x +10x +2x +0. 7 5 2 6 4
0
r ,…,r 1 k
(x r )(x r )(x r ) 1 2 k
derivative is zero. Sometimes, the function may also be equal to zero in which case you found the root. Otherwise, you will need to start over from a dierent guess. This is a tricky case, and you can just add one to the initial guess and start over if it happens. Just for fun: Calculate
The Taylor series expansion of is
The th term is . We can easily make a list of such terms using a list comprehension. Because , we can compute an approximation to by evaluating such a polynomial at and multiplying by 4. Here it is in code.
from polynomial import Polynomial terms = [((-1)**i/(2*i+1), 2*i+1) for i in range(10)] arctan = Polynomial(terms) print(4 * arctan(1))
It doesn't look very good. Maybe we need more terms.
from polynomial import Polynomial terms = [((-1)**i/(2*i+1), 2*i+1) for i in range(100)] arctan = Polynomial(terms) print(4 * arctan(1))
That's a little better, but not quite as good an approximation as . More terms!
from polynomial import Polynomial terms = [((-1)**i/(2*i+1), 2*i+1) for i in range(100000)] arctan = Polynomial(terms) print(4 * arctan(1))
Hmm... If you want to get really fancy...
arctan(x)
x + + 3 x3 5 x5 7 x7
i 2i+1 (1) x i 2i+1
arctan(1) = /4
1
22/7
For those of you who want an extra challenge, write a class for complex numbers that implements addition, multiplication, and division. Then, make polynomials with complex coecients. See if you can use Newton's method to nd complex roots. Maybe, take a look at http://www.polynomiography.com/ for inspiration.
Explanation / Answer
Run the file using python
def differential(func, x_var, h_step):
return (func(x_var+h_step) - func(x_var-h_step)) / (2.0*h_step) #Returns non-zero value if it is almost equal to zero
def function(x_var):
return 3*x_var*x_var-6*x_var+2 #Insert your test function here
def equationSolve(func, x0_initial, h_step):
X_last = x0_initial
X_next = X_last + 10* h_step #Different than x_last
while (abs(X_last - X_next) > h_step):
Y_new = func(X_next)
print "func(", X_next, ") = ", Y_new
X_last = X_next
X_next = X_last - Y_new / differential(func, X_last, h_step)
return X_next
x_found = equationSolve(function, 5, 0.01) # Function Call
print "Sol: x = ", x_found #Print result
#Result
func( 5.1 ) = 49.43
func( 3.0906504065 ) = 12.1124573666
func( 2.12504521103 ) = 2.79718018058
func( 1.71066480019 ) = 0.515133374672
func( 1.58985459202 ) = 0.0437853191898
func( 1.57748280871 ) = 0.000459183066984
Sol: x = 1.5773502844
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.