MATH4141/MATH6651/PHYS5070

FW02

Assignment 1 Due date: Friday, Sept. 27

1. In the one dimensional search methods, the length of the interval at the k^th iteration, I_k, satisfies the equation I_k = I_k+1 + I_k+2.

(a) In the Fibonacci search, the stopping criterion is that I_n = I_n+1. Show that this implies that I₁/I_k = F_n/F_n-k+1 where F_n is the n^th Fibonacci number. The Fibonacci numbers are defined by the relations F₀ = 1, F₁ = 1, F_k+1 = F_k + F_k-1.

From the above relation show that I₁/I_n = F_n.

(b) In the golden search, the criterion is that I_k/I_k+1 = R. Show that R = (1+5^1/2)/2.

2. Use the Golden Search method to find the local minimum of cos(2x²) cos(x²) which lies in the interval [0.8, 1.2]. Locate the position of the minimum in an interval of length less than 0.1 by hand calculation. What can you say about the minimum value of the function in this interval?

3. The IMSL routines DUVMIF or imsl_d_min_uncon use a combination of the downhill search method with quadratic interpolation to find a minimum of a function of a single variable. Use one of these routines to find a minimum of the function given in question 2. You should be able to find a lower minimum than the one in the interval given in question 2.

Also find a minimum of the function cos(x) exp((x-1)²).

Use a tolerance of 10^-6 in these calculations. You are expected to do the necessary checks to ensure that you are getting sensible answers and not just treating these IMSL programs as black boxes. Marks will be awarded for carrying out and describing these checks.

4. You will need to use the IMSL routines from question 3 to carry out linear searches on functions in Rⁿ. However, since the IMSL routines expect a function of a single variable, this problem must be dealt with by providing a function subprogram for g(s) which is defined as

g(s) = f(x + su)

where x is the initial direction and u is the search direction. g is the function in the IMSL routine argument list. It in turn calculates the argument x + su and calls the function f. The difficulty arises in the fact that the argument list for g can only contain the single variable s but g must also have the current values for x and u. This can be accomplished in C by declaring x and u as global variables. In FORTRAN, these variable can be passed to g via a COMMON statement.

Write a subprogram for g which will carry out such a calculation for a function of n variables. The specific subprogram for f will have to be provided each time. Test it by finding the minimum of the function -xy exp(-(x+2y)²) starting each time from the point (1, 0.5) and searching in turn along the directions:

i) (1, 2);

ii) (2, -1);

iii) (0, 1).

5. Use the downhill simplex method to find a minimum of the function

-(x² + 2y²) exp(-2x² - y²).

Do two full iterations by hand on the function starting from the simplex (0, 0), (2, 0),

(0, 2).

Note that if the points of a simplex in n dimensions are x₁, x₂, ..., x_n, x_n+1 and x_n+1 = x_hi is the high point then the centre of the face of the simplex opposite to the high point is

x_c = (x₁ + x₂ + ... + x_n)/n

and the new point is

x_new = s(x_c - x_hi) + x_hi

where s = 2 for the first try, s = 3 if the new point is the lowest point, s = 3/2 if the new point is the second-higest and s = 1/2 if the new point is highest.