NUMERICAL ANALYSIS + MATLAB (Assignment)

MACM 316 – Computing Assignment 4

• Please read the Guidelines for Assignments first.

• Submit a one-page PDF report to Canvas and upload you Matlab scripts (as m-files). Do not use any other file formats.

• Keep in mind that Canvas discussions are open forums.

• Acknowledge any collaborations and assistance from colleagues, TAs, instructors etc.

Numerical optimization

An important problem in numerical computing is finding the minimum x∗ of a function f(x). This is very much related to the root-finding problem. Indeed, if f is differentiable, then a minimum x = x∗ of f(x) is a zero of the derivative f ′(x).

Unfortunately, an approach based on applying the bisection method to f ′(x) may not work, since the derivative values may not be available in practice. Fortunately, there is an algorithm similar to the bisection method can be used to find the minimum x∗ using values of f(x) only.

Recall that the bisection method produces pairs of numbers [an,bn]. For finding minima, we will instead produce a sequence of triples [an,bn,cn] that have the following bracketing property

f(an) > f(bn) and f(bn) < f(cn). (1)

Hence bn can be used as an approximation to the minimum x ∗ at step n. To compute such triples,

the algorithm proceeds in the following way:

1. Choose a new point x using the formula:

x =

{ bn + γ(cn − bn) if (cn − bn) > (bn − an) bn + γ(an − bn) if (cn − bn) < (bn − an)

2. Update the triple using the formula:

[an+1,bn+1,cn+1] =

 

[an,x,bn] if x < bn and f(x) < f(bn) [bn,x,cn] if x > bn and f(x) < f(bn) [x,bn,cn] if x < bn and f(x) > f(bn) [an,bn,x] if x > bn and f(x) > f(bn)

(2)

You may wish to verify that the update formula in (2) guarantees the bracketing property (1) holds at each step of the algorithm. Note that the choice of γ in (1) will affect the convergence rate. It

is possible to prove that the optimal choice is γ = 3− √ 5

2 . You should use this value throughout.

Your task in this assignment is to examine this algorithm. First, write a script to implement the algorithm. Once you have done this, run it for N = 100 iterations on the function

f(x) = − cos(x),

using the initial values [a0,b0,c0] = [−1, 1/2, 1]. Plot the error versus iteration number and comment on the observed accuracy, efficiency and robustness of the algorithm.

1

Next, replace f(x) by the function f(x) = − cos(xk),

where k ≥ 1 is an integer. Repeat the above experiment for several different values of k and comment on the accuracy, efficiency and robustness of the algorithm once more.

Finally, attempt to explain the observed robustness (or lack thereof) for the different functions. Hints: (i) consider the Taylor series

f(bn) = f(x ∗) + (bn − x∗)f ′(x∗) +

(bn − x∗)2

2 f ′′(x∗) +

(bn − x∗)3

3! f ′′′(x∗) + . . . .

(ii) note that f ′(x∗) = 0 at the minimum.

2