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 0 (x). Unfortunately, an approach based on applying the bisection method to f 0 (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). (0.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) (0.2) You may wish to verify that the update formula in (0.2) guarantees the bracketing property (0.1) holds at each step of the algorithm. Note that the choice of in (0.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), 1 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. Next, replace f(x) by the function f(x) = cos(x k ), 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 0 (x ) + (bn x ) 2 2 f 00(x ) + (bn x ) 3 3! f 000(x ) + . . . . (ii) note that f 0 (x ) = 0 at the minimum.