Reference no: EM132244006

Assignment Questions -

Note - There are 5 questions from Q2 to Q6. And, when it comes to the Q3 to Q5, there is a 'sample solution.pdf' file for the output. Your answer should be the same as that.

Q2. An IEEE 754 Mini-Floating Point number

Demonstrated the use of a mini-floating point number system using 8 bits. In my class demo, used 1 bit for the sign, 3 bits for the exponent, and 4 bits for the mantissa. For this problem, imagine I had used 10 bits - 1 bit for the sign, 4 bits for the exponent, and 5 bits for the mantissa.

Answer the following questions under this new system.

a. What is the bias that would be used for the exponent? What is the largest positive exponent? What is the most negative exponent?

b. How would the value 5.5 be stored in this system?

c. What value would the following bit sequence represent '0 0111 00000'?

d. What value would the following bit sequence represent '0 0111 00001'? (Express as a fraction and also in decimal.)

e. What is the smallest positive normalized value that can be expressed? (Fill in the bits. Express as a fraction and also in decimal.)

'0 0000 00000'

f. What is the smallest positive (denormalized) non-zero value that can be expressed? (Fill in the bits. Express as a fraction and also in decimal.)

'0 0000 00000'

g. What is the largest denormalized value that can be expressed? (Fill in the bits. Express as a fraction and also in decimal.)

'0 0000 00000'

h. What is the largest finite value that can be expressed with this sytem? (Fill in the bits. Express as a fraction and also in decimal.)

'0 0000 00000'

i. The machine epsilon is the size of the smallest increment that we can differentiate between two adjacent values in the mantissa (regardless of the exponent). Values with a difference smaller than machine epsilon are seen as equivalent in floating point. For our system, it is equivalent to the difference between your answer to parts c and d above: 1/32. If you ask R for '.Machine$double.eps', you get 2.220446e-16. What power of 2 is that equal to?

h. With our 10 bit floating point system, the machine epsilon is 1/32. What will the following return? (Hint: can you represent the left-hand side with a sequence of bits that is different from the right-hand side?).

(1 + 1/64) == 1

(1 - 1/64) == 1

Q3. Root Finding with Fixed Point Iteration

This is a modified version of SPURS chapter 10, section 6, exercise 4.

Exercise 4 - A picture is worth a thousand words.

The function fixedpoint_show.r below is a modification of fixedpoint that plots intermediate results. Instead of using the variables tol and max.iter to determine when the algorithm stops, at each step you will be prompted to enter "y" at the keyboard if you want to continue. There are also two new inputs, xmin and xmax, which are used to determine the range of the plot. xmin and xmax have defaults x0 - 1 and x0 + 1, respectively.

Use fixedpoint_show to investigate the fixed points of the following functions:

(a) cos(x) using x₀ = 1, 3, 6

(b) exp(exp(-x)) using x₀ = 2

(c) x - log(x) + exp(-x) using x₀ = 2

(d) x + log(x) - exp(-x) using x₀ = 2

Q4. Root Finding with Newton Raphson

Modified version of SPURS chapter 10, section 6, exercise 5.

For this problem, we are implementing the Newton Raphson method for root finding.

Exercise 5 - Below is a modification of newtonraphson that plots intermediate results, analogous to fixedpoint_show above. Use it to investigate the roots of the following functions:

(a) cos(x) - x using x₀ = 1, 3, 6

(b) log(x) - exp(-x) using x₀ = 2

(c) x³ - x - 3 using x₀ = 0

(d) x³ - 7x² + 14x - 8 using x₀ = 1.1, 1.2, . . . , 1.9

(e) log(x) exp(-x) using x0 = 2.

Write the code so it can use ggplot to show the function and lines for each iteration.

You'll probably want to refer to the code for the fixed point iteration. Also pay attention to the example used in the textbook for how the function should be programmed. The function takes a value of x and returns two values: the value of the function, and the value of the derivative at that point. Refer to section 10.3, especially page 176.

Once you have it running, produce graphs for:

part (a) using x0 = 1, 3, 6 Results should be similar to finding fixed point of cos(x).

part (b) using x0 = 2 Results should be similar to finding fixed point of exp(exp(-x)).

part (c) using x0 = 0.

part (d) using x0 = 1.1, 1.3, 1.4, 1.5, 1.6, 1.7 (should be simple. just repeat the command several times).

Q5. Root Finding with Secant Method

Modified version of SPURS chapter 10, section 6, exercise 6.

Exercise 6 - Write a program, using both newtonraphson.r and fixedpoint.r for guidance, to implement the secant root-finding method:

x_n+1 = x_n - f(x_n)((x_n - x_n-1)/(f(x_n) - f(x_n-1))).

First test your program by ?nding the root of the function cos x - x. Next see how the secant method performs in finding the root of log x- exp(-x) using x₀ = 1 and x₁ = 2. Compare its performance with that of the other two methods.

Write a function secant_show.r that plots the sequence of iterates produced by the secant algorithm.

Implement the secant method for root finding. Write a function called 'secant_show' similar to the 'newtonraphson_show' and 'fixedpoint_show' functions. In your function, perform iterations of the algorithm and plot the results. It should behave in a very similar fashion to 'newtonraphson_show'.

Q6. Coordinate Descent Algorithm for Optimization

Coordinate descent is an optimization algorithm. The algorithm attempts to find a local minimum of a function. We perform a search in one direction to find the value that minimizes the function in that direction while the other values are held constant. Once the value for that direction is updated, you perform the same operation for the other coordinate directions. This repeats until it has been updated for all coordinate directions, at which point the cycle repeats.

Thus for a function of two variables $f(x,y)$, a simple version of the algorithm can be described as follows:

1) Start with some initial values of $x$ and $y$. This is time 0, so we have $x^{(0)}$ and $y^{(0)}$.

2) Iterate:

1) Update $x^{(t+1)}$ to be the value of $x$ that minimizes $f(x,y = y^{(t)})$

2) Update $y^{(t+1)}$ to be the value of $y$ that minimizes $f(x = x^{(t+1)},y)$

3) Stop when some convergence criterion has been met.

The "tricky" part of the algorithm is finding the value that minimizes the function along one of the directions.

Golden Section Search Method (with Video)

This unidimensional minimization be done in one of many ways, but for our purposes, we will use the golden section search method.

With our golden search function, we can now create our coordinate descent algorithm:

1) Start with some initial values of $x$ and $y$. This is time 0, so we have $x^{(0)}$ and $y^{(0)}$.

2) Iterate:

1) Update $x$:

a. Find the function $f(x) = f(x,y = y^{(t)})$

b. Use golden search to minimize $f(x)$

c. Set $x^{(t+1)}$ be the result of the search.

2) Update $y$

a. Find the function $f(y) = f(x = x^{(t+1)},y)$

b. Use golden search to minimize $f(y)$

c. Set $y^{(t+1)}$ be the result of the search.

3) Stop when some convergence criterion has been met.

Requirements for this task:

1) Your search space for the golden search can be limited to the range -1.5 to 1.5 for both the x and y directions.

2) For your starting point, use x = -1.5, and y = -1.5.

3) For the first step, hold y constant, and find the minimum in the x direction.

4) Plot the segments showing each 'step' of the algorithm onto the contour plot.

5) After each full iteration, print out the current values of x and y. Hint: after your first full iteration, the next location should be (-0.9, -0.54).

6) Stop after 15 full iterations, or if the difference between one x and the next is less then '1e-5'. The true minimum is at (0,0). Your code should come close to that.

Textbook - INTRODUCTION TO Scientifi­c Programming and Simulation Using R. Author - Owen Jones, Robert Maillardet, and Andrew Robinson. International Standard Book Number-13: 978-1-4200-6874-0 (eBook - PDF).

Attachment:- Assignment Files.rar