METHOD OF QUADRATIC INTERPOLATION

1 METHOD OF QUADRATIC INTERPOLATIONKELLER methods are a common approach to the more generalarea of line search for optimization. In the case of QUADRATIC inter-polation, the function s critical value is bracketed, and a quadraticinterpolant is fitted to the arc contained in the interval. Then, theinterpolant is minimized, and the new interval is determined based onthe relation of the minimizer to the original endpoints of the more formally, letx* maximize (or minimize)f(x). Ifx* isnot easily found through analytic methods , then it is significantly eas-ier to bracket the interval over which this critical point occurs. Letq(x) denote the QUADRATIC interpolant off(x). Minimizing a quadraticfunction is trivial, and so the critical point ofqis easily obtained.

2 Wethen form a new bracketing interval by throwing away the worst point, which for our purposes would be the point that is the largest orsmallest, depending on whether we want to approximate a maximumor minimum. The process is then iterated until a desired precision : September 3, of InterpolationIn practice there are 3 methods of INTERPOLATION . There are 2 typesof 2-point INTERPOLATION methods , and a 3-point INTERPOLATION 2-point methods require knowledge of the derivative of the func-tionfin which we are interested in optimizing. The 3-point methoddoes not require any derivatives, but of course requires an extra , knowingf gives a better sense of the function s behavior,and will hence provide a faster rate of (x) denote the QUADRATIC interpolant off(x).Then, by definition:q(x) =ax2+bx+cFora,b,c R.

3 Then, we can find our constants by bracketing thecritical point off, whose endpoints arex1andx2. We have:( )f(x1) =ax21+bx1+c=q(x1)f(x2) =ax22+bx2+c=q(x2)f (x1) = 2ax1+b=q (x1)This is a system of 3 equations with 3 unknowns, which are ourconstants. Letfi=f(xi), andf i=f (xi). Then we can solve ( ) foraandb.( )a=f1 f2 f 1(x1 x2) (x1 x2)2b=f 1+ 2f1 f2 f 1(x1 x2)(x1 x2)2x1 METHOD OF QUADRATIC INTERPOLATION3 The minimizer ofqis easily found to be b/2aby settingq (x) = ( ), our minimizerxmincan be found:( )xmin= b2a=x1 12(x1 x2)f 1f 1 f1 f2x1 x2 This of course readily yields an explicit iteration formula by lettingxmin=x3. We have from ( ):( )xk+1=xk 1 12(xk 1 xk)f k 1f k 1 fk 1 fkxk 1 xkWith ( ), we generatexk+1and compare it with the previous twopoints to find our new bracketing interval, and then continue the METHOD is very similar to our first METHOD butinstead generatesq(x) by solving a different set of equations.

4 We have:( )f(x1) =ax21+bx1+c=q(x1)f (x1) = 2ax1+b=q (x1)f (x2) = 2ax2+b=q (x2)We can of course solve these foraandbin the same way as in We find the explicit form of the minimizer ofq(x) to be:( )xmin=x1 x1 x2f 1 f 2f 1In an identical manner to ( ), we generate a recursion by definingxmin=x3, and we have:4 KELLER VANDEBOGERT( )xk+1=xk 1 xk 1 xkf k 1 f kf k 1 Which is commonly called thesecant 1 xkin ( ), and assuming thatf (xk)exists, ( ) becomes:xk+1=xk f kf kBut this is precisely the iteration defined by Newton s METHOD . Thismotivates calling ( ) the secant METHOD , because it is just Newton smethod with the secant approximation off (xk) third METHOD is the 3 point METHOD . Choose3 points, 2 endpoints to bracket our critical point, and then a pointwithin the interval as theLagrange INTERPOLATION formula, we can easily find ourinterpolantq(x).

5 We have:( )q(x) =(x x2)(x x3)(x1 x2)(x1 x3)f1+(x x1)(x x3)(x2 x1)(x2 x3)f2+(x x1)(x x2)(x3 x1)(x3 x2)f3To find the minimum, we of course take the derivative of ( ) andset it to 0. By doing this, we obtain:( )xmin=12(x1+x2) +12(f1 f2)(f2 f3)(f3 f1)(x2 x3)f1+ (x3 x1)f2+ (x1 x2)f3 And the iteration scheme is easily deduced: METHOD OF QUADRATIC INTERPOLATION5( )xk+2=12(xk 1+xk)+12(fk 1 fk)(fk fk+1)(fk+1 fk 1)(xk xk+1)fk 1+ (xk+1 xk 1)fk+ (xk 1 xk)fk+1 This METHOD differs slightly from the previous two methods , becauseit is not as simple to determine the new bracketing interval. Ifxminlies betweenx1andx3, then we want to compare the distance betweenxminandx2. If|xmin x2|< Where is the prescribed tolerance, then we are done. Otherwisewe create the new interval by checking which point is the largest orsmallest, depending on the nature of our critical outside of our bracketing interval [x1,x3], then we im-mediately create a new bracketing interval in the same way as we RatesIn the beginning of Section 2, we made a comment on the convergencerates of the 2-point versus 3-point METHOD .

6 In this section, we intendto make this comment x . Then, the sequence{xn}is said toconverge tox* with order if||xn x || M||xn 1 x || For some constantM VANDEBOGERTWe will also need the following result, which we shall state withoutproof:Lemma Cn+1[a,b], and letpbe the polynomial of degree nthat interpolatesfatn+ 1distinct pointsx0,x1, ..,xn [a,b].Then, to eachx [a,b]there exists a x (a,b)such thatf(x) p(x) =f(n+1)( x)(n+ 1)!k i=0(x xi)Wheref(n)(x)denotes the nth derivative off. This remainder termwill often be denotedRn+ :R Rbe 3 times continuously * be such thatf (x ) = 0andf (x )6= 0. Then the sequence{xn}generated by( )converges tox with order1+ first want to prove that ( ) does indeed converge to ourminimizer,x .LetL(x) be the 2 point interpolant forf (x). Then, with , we have:f (x) L(x) =f ( )2(x xk 1)(x xk)Sincexk+1is generated by maximizingq(x), we have thatL(xk+1) =0.

7 Thus,f (xk+1) =f ( )2(xk+1 xk 1)(xk+1 xk)If we substitute the recursion forxk+1given by ( ) into the aboveequation, we can simplify this into: METHOD OF QUADRATIC INTERPOLATION7( )f (xk+1) =12f ( )f kf k 1(xk xk 1)2(f k f k 1)2We now want to take advantage of the Mean Value Theorem. Wehave:f k f k 1xk xk 1=f 0 Where 0 (xk,xk 1). Also note that sincef (x ) = 0, we have:( )f i=f (xi) f (x ) = (xi x )f ( i)For some i (xi,x ),i=k 1,k,k+ 1. Using ( ) and theprevious line , we can rewrite ( ) as so:( )xk+1 x =12f ( )f ( k)f ( k 1)f ( k+1)[f( 0)]2(xk x )(xk 1 x )Now, letei=|xi x |,i=k 1,k,k+ 1. Find constantsm1,m2,M1,M2such that0< m1 |f (x)| M10< m2 |f (x)| M2wherexis any value in the bracketing interval considered. Then, wecan bound ( ):( )m1m222M32ekek 1 ek+1 M1M222m32ekek 1 However, using ( ):8 KELLER VANDEBOGERTek+1ekek 1=12f ( )f ( k)f ( k 1)f ( k+1)[f( 0)]2 Now if we let eachxi x , each iwill tend towardx as well sincethey are contained within their respective bracketing intervals andf ,f are continuous.

8 Thus we see:( )ek+1ekek 1 f (x )2f (x )This is well-defined sincef (x )6= 0 by assumption. DefineM= f (x )2f (x ) , and using ( ) and ( ), we have that( )ek+1 Mekek 1In which case if = max{ek,ek 1},ek+1 M 2 0So our sequence converges tox whenx06=x1. Now we seek todetermine the rate of convergence. To do this, we defineyk= log(Mek).We then have, using ( ):yk+1=yk+yk 1 This is of course a simple a recurrence relation. Let =1+ 52and =1 52. We easily find the closed form ofykto be:( )yk= k+ kWhere , are to be determined from our initial conditions. Since <1, forksufficiently large,yk k. We then have, ask : METHOD OF QUADRATIC INTERPOLATION9 Mek+1M e k exp( k+1)exp( k ) 1 With this:|xk+1 x ||xk x | M 1 And with Definition , this implies thatxk x with order =1+ 52.

9 See that the secant METHOD converges at a superlinearrate, whereas Newton s METHOD converges quadratically under now seek to find the rate of convergence of the 3-point following result answers this question:Theorem C4. Suppose thatx satisfiesf (x ) = 0andf (x )6= 0. Then the sequence{xk}generated by( )converges tox of to Theorem , we begin by writing our functionfinthe following form:( )f(x) =L(x) +R3(x)WhereR3in the third degree remainder term for the Lagrange inter-polant. Now, sincex is a critical point, we clearly have thatf (x ) = this and ( ):10 KELLER VANDEBOGERTL (x ) +R 3(x ) = 0L (x ) can be easily computed, we have:( )f12x (x2+x3)(x1 x2)(x1 x3)+f22x (x1+x3)(x2 x1)(x2 x3)+f32x (x1+x2)(x3 x1)(x3 x2)+R 3(x ) = 0We now use ( ) to solve forx :2x (f1(x1 x2)(x1 x3)+f2(x2 x1)(x2 x3)+f3(x3 x1)(x3 x1))+R 3(x )=f1(x2+x3)(x1 x2)(x1 x3)+f2(x1+x3)(x2 x1)(x2 x3)+f3(x1+x2)(x3 x1)(x3 x2)Which then gives:( )x = 12R 3(x )f1(x1 x2)(x1 x3)+f2(x2 x1)(x2 x3)+f3(x3 x1)(x3 x1)+12(f1(x2+x3)(x1 x2)(x1 x3)+f2(x1+x3)(x2 x1)(x2 x3)+f3(x1+x2)(x3 x1)(x3 x2)f1(x1 x2)(x1 x3)+f2(x2 x1)(x2 x3)+f3(x3 x1)(x3 x1))However, it is easy to see that we can use ( ) and rewrite it in anawfully convenient form.

10 X4=12f1(x2+x3)(x1 x2)(x1 x3)+f2(x1+x3)(x2 x1)(x2 x3)+f3(x1+x2)(x3 x1)(x3 x2)f1(x1 x2)(x1 x3)+f2(x2 x1)(x2 x3)+f3(x3 x1)(x3 x1)But this is precisely the rightmost term of ( ), so we easily deduce:( )x x4= 12R 3(x )f1(x1 x2)(x1 x3)+f2(x2 x1)(x2 x3)+f3(x3 x1)(x3 x1) METHOD OF QUADRATIC INTERPOLATION11 Now, similar to the proof of Theorem , letei=x xi, wherei= 1, 2, 3, 4. With elementary manipulations of ( ), we find thefollowing form:( )e4(f1(e2 e3)+f2(e3 e1)+f3(e1 e2))= 12R 3(x )(e1 e2)(e2 e3)(e3 e1)By means of the Taylor expansion aboutx , it is clear thatfi=f(x ) +12e2if (x ) +O(e3i)Where we ve used the fact thatf (x ) = 0. Now, foreisufficientlysmall, we have neglect the third order term of the Taylor each respective Taylor expansion into ( ), we get thefollowing:e4((f(x )+12e21f (x ))(e2 e3)+(f(x )+12e22f (x ))(e3 e1)+(f(x )+12e23f (x ))(e1 e2))= 12R 3(x )(e1 e2)(e2 e3)(e3 e1)Now examine the coefficient ofe4in the above expression.