Reference no: EM132242096

Assignment -

1. Read

a. SPURS:

* Chapter 9

* Chapter 10

* Chapter 12 sections 1-2

2.An IEEE 754 Mini-Floating Point number.

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?

j. 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?).

3. Root Finding with Fixed Point Iteration

This is a modified version of SPURS chapter 10, section 6, 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.

4. Root Finding with Newton Raphson

Modified version of SPURS chapter 10, section 6, 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 x₀ = 2.

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

5. Root Finding with Secant Method

Modified version of SPURS chapter 10, section 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 finding 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'.

6. 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.

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

Back to Coordinate Descent

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.

Write code to perform coordinate descent to minimize the function (in attached file).

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 File.rar