tutorial solutions 2005

EG5090: Mathematical Optimisation Tutorial Solutions 2005-06 1: 1a With reference to the figure: f x( )x = b1x = c = (a +b )2x = ax the algorithm operates by examining the value of f(x) at the centre point x = c of an interval x = a to x = b that is known to bracket at least one root: that is, as shown, signum(f(a)) ≠ signum(f(b)). Then, depending on the sign of f(c), it can be determined whether the root lies in the upper or lower half of the original range. The appropriate half is then bisected in the same fashion, and the process is continued to convergence. 1b Using PDL, this algorithm can be represented by: function x = root(f,a,b,tol) if f(a) != f(b) then error(“points do not bracket root”) if f(a) > f(b) then exchange a and b convgd = FALSE while(not convgd) c = (a+b)/2 if f(c) > 0 then b = c else a = c if c – a < tol then convgd = TRUE end while return x = c 11c Linear convergence: the solution interval h after k iterations is given by k h = ε h k k −1 k −1 where ε is either constant or weakly dependent on k. Thus the solution interval (or search k-1space) reduces by a constant, or nearly constant, fraction on each iteration. Each factor of 10 improvement in precision, for instance, will require a similar number of additional iterations. 1In the case of the bisection method, the interval is halved at each step: h = h . k k −12 100 4For a reduction of interval to 0.01%, exhaustive ...