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). 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) You may wish to verify that the update formula guarantees the bracketing property holds at each step. Note that the choice of ? will affect the convergence rate. It can be proven that ? = (3? ? 5)/2 is the optimal choice. Use this value throughout. 1 Implement the algorithm to find the minimum of the function f(x) = ? cos(x k ) for k = 1, 2, ..., 5. Use 100 iterations of the algorithm and the initial triple [a0, b0, c0] = [?1, 1/2, 1]. Plot error versus iteration number for each k. Discuss the accuracy of the algorithm. How would you characterize the error as a function of the iteration number? What effect, if any, does k have on the accuracy? How does the robustness of the algorithm depend on k? Explain your observations. Hint: expand f(x) in a Taylor series about x ? , noting that f 0 (x ? ) = 0. (Robustness refers to an algorithms ability to resist round-off error.)