Programming Assigment #1 – Root Finding Solved

Please submit a PDF file that includes all answers and code listings (even in questions that do not require to hand in a *.py file - your code should be in the PDF). This PDF file should be readable so that you could get constructive remarks (make sure you edit your code so that it looks nice). Please also submit a printed copy of this PDF file to the checkers box, 245, Schreiber building. In addition you should submit three *.py files (bisec.py; newton.py; Q6.py) and one *.csv file (TableQ3.csv). All five files should be packed into a single .zip file, who’s name is your I.D number, for example 254545454.zip and submitted to the moodle site through the ”matalot lehagasha” section. Make sure that the file names you use are EXACTLY as the ones specified in each question below.



1.   Implement a bisection root finding method. Your function should have the signaturebisec(f,a,b,tol) and return a 1 × 2 list named res where f       Function handle to f(x)


a, b       Endpoints of initial interval [a,b] tol           Tolerance res[0,0] Final approximation of the root. res[0,1] Number of iterations until convergence

•   The root should have relative precision of at least tol (unless the root close to zero, in which the absolute accuracy should be tol).

•   Provide a listing of the code and a source file named bisec.py



2.   Implement Newton’s root finding method. Your function should have the signaturenewton(f,fp,x0) and return a 1 × 2 list named res where f Function handle to f(x) fp     Function handle to the derivative of f.

x0        Initial guess res[0,0] Final approximation of the root. res[0,1] Number of iterations until convergence

•   The accuracy should be as high as possible in double precision.

•   Comment how you’ve determined that the root is sufficiently accurate.

•   Provide a listing of the code and a source file named newton.py

•   Make sure that you do not enter infinite loops!

3.   Here we wish to check your implementations of Bisection and Newton methods on the functions

f(x)
Newton’s x0
Bisection’s [a,b]
tanx − 2x
1.4
[1,1.4]
x3 − [1]x2 + 12x − 8
3.0
[1,3]
Use tol= 10−12 for the bisection method.

•   For each function, generate a table that shows at each iteration

–    the estimate of the root,

–    the value of the function at the estimated root, – the relative precision of the root.

–    Save the table in the file named TableQ3.csv - make sure that when you save it you keep the format *.csv

•   Approximate the rate of convergence of each method empirically by plotting the value   in the y-axis vs. n in the x-axis (see H.W assignment 2 question 1).

•   Make sure that Newton’s method results in the rate p = 2. If this is not the case, decide what is the multiplicity of the root empirically (see H.W 2 Question 2).



4.   Find the first 10 zeros of Bessel’s function J0(x) for x ≥ 0.

•   You may use Python’s function jv found in the scipy.special library to evaluate bessel functions as needed (see https://docs.scipy.org/doc/scipy/reference/special.html)

•   The function should generate a table of the zeros accurate to 10−12.

•   plot J0(x) with its zeros marked with symbols.



5.   Implement Newton’s Fractal for the complex function f(z) = z3 − 1.

•   Create an initial grid of [−1,1] × [−i,i] with 800 × 800 points.

•   Use Newton’s method to find the root of f(z) for each of the starting points.

•   Store the number of iterations needed to approximate a given root up to 10−10 in a 800 × 800 array. If you diverge use the maximal number of iterations. Normalize the array to values between 0 and 1. NOTICE: f(z) has 3 complex roots - so you should have 3 such arrays.

•   Concatenate the three arrays into a single array IM of size 800 × 800 × 3.

•   Use the command imshow(IM) (found in the library matplotlib.pyplot) to show the resulting image.

 

Figure 1: Finding w.


 
[1] . Calculate the length of w in Figure 1. Upload your script file with the name Q6.py. Remark: The lengths 12m and 10m refer to the whole sides of the right angle triangles.