Please give detailed solution, thank you. Suppose we are using a bracketing meth
ID: 2263618 • Letter: P
Question
Please give detailed solution, thank you.
Suppose we are using a bracketing method to seek a minimizer of f(x) such that x E -2,2 a) How many iterations are required if bracketing with derivatives is used? How many b) How many iterations are required if dichotomous search without derivatives is used? How c) How many iterations are required if golden search is used? How many evaluations of f d) If each evaluation of f' takes 5 seconds, and each evaluation of f takes 1 second, which to an accuracy of 10-9. evaluations of f' are required in this case? many evaluations of f are required in this case? are required in this case? is the fastest method to solve this problem?Explanation / Answer
A) In bracketing method, if c1 = a+b / 2 is the midpoint of the initial interval, and cn is the midpoint of the interval in the nth step, then the difference between cn and a solution c is bounded by = |cn - c | = (b-a) / 2n, thus we get number of iterations required as, n log2((ba)/) .
Putitng in a = 2 , b = -2 and = 10-9 we get n 31.89 , so n = 32 will just do.
With derivatives the bracketing is called newton's method (which has quadratic convergence, it means that the square of the error at one iteration is proportional to the error at the next iteration) hence = |b-a|2^n approx. Hence no. of iterations is given by n log2 (log2 /(b-a) ) , Putting in values we get, n 4.082, so n= 5.
B)In dichotomous search the no of iterations can be found out similarly as above so we get,
n log2((b-a )/t ) , where 0 < t < b-a, putting in values a,b and t = 10-9 we get n 31.89 , so n = 32.
C) Following similair pattern just that in golden serach interval is reduced by golden ratio whereas in bracketing it is reduced by half, so we get n log1.618034((ba)/) , here 1.618034 is the golden ratio. Plugging in values og a,b, we get n 45.94, so n = 46 is the answer.
D) Calculating time from no. of iterations in each method we get,
in A : n = 5 but at each iteration derivative is required so total time T = 5*5 + 1*5 = 30 sec.
in B : n = 32 but only f value required so T = 32*1 = 32 sec
in C : n = 46 and only f value required so T = 46*1 = 46 sec.
So the fastest is Quasi-Newton method