Mueller's method is another root-finding method. It uses 3 points to approximate your function locally with a parabola, and then computes the intersection of the parabola with $y=0$ to update one of your points. The main advantage of Mueller's method with respect to Newton's method and its variant, is that it can compute complex roots.
1.a You will write a function rootMuellerMethod with inputs: $f$ a function handle, $p0$, $p1$, $p0$ the initial guesses, $\epsilon$ the tolerance, and $Nmax$ the maximum number of iterations.
Your function will raise an error if the convergence is not reached in the specified number of iterations.
The output of the function will depend on the optional parameter $history$. If $history$ is false, the function will output the last guess $p$; on the other hand, if $history$ is true the output will be vector $p$ with all the intermediate steps.
Hint: you may need to use complex arithmetic. In order to avoid errors, you need to force p0,p1 and p2 to be complex numbers.
In [ ]:
function rootMuellerMethod(f,p0,p1,p2, ϵ, Nmax; history = true )
p0, p1, p2 = (p0 + 0*im,p1 + 0*im,p2 + 0*im) # forcing p0,p1,p2 to be complex numbers
history && (hist = ([p0 p1 p2][:])) # hist vector for the succesive approximations
#write the body of the function in here
end
2.a You will write a script to find all the roots to within $10^{-6}$ of the following polynomials using Mueller's Method. You will use the function that you just wrote, with suitable initial guesses. If you can not find all the complex roots you may want to take a look at Theorem 2.20 in your textbook.
Hint: In Julia you can use the conj function to compute the conjugate of a complex number.
In [ ]:
p1(x) = x.^3 - 2*x.^2 - 5
p2(x) = x.^3 + 3*x.^2 - 1
p3(x) = x.^3 - x - 1
p4(x) = x.^4 + x.^2 - x - 3
p5(x) = x.^4 + 4.001*x.^2 + 4.002*x + 1.101
p6(x) = x.^5 - x.^4 + 2*x.^2 + x - 4
In order to make the correction of the Homework easier, you will print in the console (using the function print) the roots for each polynomial.
In [ ]:
# write your script here
# roots of p1
# roots of p2
# roots of p3
# roots of p4
# roots of p5
# roots of p6
2.c You will write a script that finds all the roots of the polynomials, using the Newton's Method. You will use the Newton's method you wrote in Question 2 from Homework 2. Can you find all roots? Why?
In [ ]:
# use this space to write your Newton's method
In order to make the correction of the Homework easier, you will print in the console (using the function print) the roots for each polynomial.
Hint: You need to define by hand the derivative of each polynomial in order to be passed as a function handle to your Newton's method.
In [ ]:
# write your script here
# roots of p1
# roots of p2
# roots of p3
# roots of p4
# roots of p5
# roots of p6
Answer:
2.c You will write a script that finds all the roots of the polynomials, using the Companion matrix method. You will use the companion matrix algorithm you wrote in Question 3 from Homework 2.
In [ ]:
# use this space to write your companion matrix root-finding method
In order to make the correction of the Homework easier, you will print in the console (using the function print) the roots for each polynomial.
In [ ]:
# write your script ro find the roots in here
# roots of p1
# roots of p2
# roots of p3
# roots of p4
# roots of p5
# roots of p6
2.d Compare the algorithms (Mueller's method, Newton's Method, and Companion matrix) in this three aspects:
memory footprint (how much memory is being allocated) with respect to the degree of the polynomial
complexity (how many operations are performed) with respect to the degree of the polynomail
implementation, which one is easier to implement and run.
Hints:
Answer: