**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_{1}/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_{0} = 1, F_{1} = 1, F_{k+1} = F_{k}
+ F_{k-1}.

From the above relation
show that I_{1}/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^{2}) cos(x^{2}) 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)^{2}).

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 ^{n}**. 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** + s**u**)

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** + s**u** 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)^{2}) 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^{2} + 2y^{2})
exp(-2x^{2} - y^{2}).

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**_{1}, **x _{2}**, ...,

**x**_{c} = (**x**_{1 }+ **x _{2 }+** ... +

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.