Lagrange_and_Spline_Interpolation.pdf

10/9/2007 1 Interpolation http://numericalmethods.eng.usf.edu 1 Topic: Lagrangian Interpolation Lagrangian Interpolation Lagrangian interpolating polynomial is given by ? = = n i iin xfxLxf 0 )()()( where ? n ?in )(xf stands for the th n order polynomial that approximates the function )(xfy http://numericalmethods.eng.usf.edu2 ? in n fo the that pproximate the = given at )1( +n data points as ()()( )() nnnn yxyxyxyx ,,,,......,,,, 111100 ?? , and ? ? = ? ? = n ij j ji j i xx xx xL 0 )( )(xL i is a weighting function that includes a product of )1( ?n terms with terms of ij = omitted. Example The upward velocity of a rocket is given as a function of time in Table 1. Find the velocity at t=16 seconds using the Lagrangian method for linear and quadratic interpolation. v(t)t http://numericalmethods.eng.usf.edu3 Table : Velocity as a function of time Figure : Velocity vs. time data for the rocket example 901.6730 602.9722.5 517.3520 362.7815 227.0410 00 m/ss Linear Interpolation 500 550 517.35 y s f( ) )()()( 1 0 ii i tvtLtv = ?= )()()()( 1100 tvtLtvtL += http://numericalmethods.eng.usf.edu4 10 12 14 16 18 20 22 24 350 400 450 362.78 range fxdesired() x s 1 10+x s 0 10? x s range, x desired, ( ) 78.362,15 00 == tt ? () 35.517,20 11 == tt ? Linear Interpolation (contd) ? ? = ? ? = 1 0 0 0 0 )( j j j j tt tt tL 10 1 tt tt ? ? = ? = ? ? = 1 0 1 1 )( j j j tt tt tL 01 0 tt tt ? ? = http://numericalmethods.eng.usf.edu5 ?1j )()()( 1 01 0 0 10 1 tv tt tt tv tt tt tv ? ? + ? ? = )35.517( 1520 15 )78.362( 2015 20 ? ? + ? ? = tt )35.517( 1520 1516 )78.362( 2015 2016 )16( ? ? + ? ? =v )35.517(2.0)78.362(8.0 += 7.393= m/s. Quadratic Interpolation For the second order polynomial interpolation (also called quadratic interpolation), we choose the velocity given by ? = 2 )()()( ii tvtLtv http://numericalmethods.eng.usf.edu6 =0i )()()()()()( 221100 tvtLtvtLtvtL ++= 10/9/2007 2 Quadratic Interpolation (contd) 450 500 550 517.35 ,10 0 =t 04.227)( 0 =tv ,15 1 =t 78.362)( 1 =tv ,20 2 =t 35.517)( 2 =tv http://numericalmethods.eng.usf.edu7 10 12 14 16 18 20 200 250 300 350 400 227.04 y s f range() fxdesired() 2010 x s range, x desired, ? ? = ? ? = 2 0 0 0 0 )( j j j j tt tt tL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 20 2 10 1 tt tt tt tt ? ? = ? ? = 2 1 0 1 1 )( j j j j tt tt tL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 21 2 01 0 tt tt tt tt ? ? = ? ? = 2 2 0 2 2 )( j j j j tt tt tL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 12 1 02 0 tt tt tt tt Quadratic Interpolation (contd) )()()()( 2 12 1 02 0 1 21 2 01 0 0 20 2 10 1 tv tt tt tt tt tv tt tt tt tt tv tt tt tt tt tv ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = )35.517( )1520)(1020( )1516)(1016( )78.362( )2015)(1015( )2016)(1016( )04.227( )2010)(1510( )2016)(1516( )16( ?? ?? + ?? ?? + ?? ?? =v http://numericalmethods.eng.usf.edu8 )35.517)(12.0()78.362)(96.0()04.227)(08.0( ++?= 19.392= m/s. The absolute relative approximate error a ? obtained between the results from the first and second order polynomial is 100 19.392 70.39319.392 × ? =? a %38502.0= Cubic Interpolation For the third order polynomial (also called cubic interpolation), we choose the velocity given by ? = = 3 0 )()()( i ii tvtLtv )()()()()()()()( 33221100 tvtLtvtLtvtLtvtL +++= http://numericalmethods.eng.usf.edu9 10 12 14 16 18 20 22 24 200 300 400 500 600 700 602.97 227.04 y s f range() fxdesired() 22.510 x s range, x desired, Cubic Interpolation (contd) ( ) 04.227,10 == oo tvt () 78.362,15 11 == tvt () 35.517,20 22 == tvt () 97.602,5.22 33 == tvt ?????? 700 602 97 http://numericalmethods.eng.usf.edu10 ? ? = ? ? = 3 0 0 0 0 )( j j j j tt tt tL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 30 3 20 2 10 1 tt tt tt tt tt tt ; ? ? = ? ? = 3 1 0 1 1 )( j j j j tt tt tL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 31 3 21 2 01 0 tt tt tt tt tt tt ? ? = ? ? = 3 2 0 2 2 )( j j j j tt tt tL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 32 3 12 1 02 0 tt tt tt tt tt tt ; ? ? = ? ? = 3 3 0 3 3 )( j j j j tt tt tL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 23 2 13 1 03 0 tt tt tt tt tt tt 10 12 14 16 18 20 22 24 200 300 400 500 600 . 227.04 y s f range() fxdesired() 22.510 x s range, x desired, Cubic Interpolation (contd) )()( )()()( 3 23 2 13 1 03 0 2 32 3 12 1 02 0 1 31 3 21 2 01 0 0 30 3 20 2 10 1 tv tt tt tt tt tt tt tv tt tt tt tt tt tt tv tt tt tt tt tt tt tv tt tt tt tt tt tt tv ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = )78.362( )5.2216)(2016)(1016( )04.227( )5.2216)(2016)(1516( )16( ??? + ??? =v http://numericalmethods.eng.usf.edu11 )97.602( )205.22)(155.22)(105.22( )2016)(1516)(1016( )35.517( )5.2220)(1520)(1020( )5.2216)(1516)(1016( )5.2215)(2015)(1015()5.2210)(2010)(1510( ??? ??? + ??? ??? + ?????? )97.602)(1024.0()35.517)(312.0()78.362)(832.0()04.227)(0416.0( ?+++?= 06.392= m/s The absolute percentage relative approximate error, a ? for the value obtained for v(16) between second and third order polynomial is 100 06.392 19.39206.392 × ? =? a %033427.0= Comparison Table Order of Pl il 1 2 3 http://numericalmethods.eng.usf.edu12 Polynom a v(t=16) m/s 393.69 392.19 392.06 Absolute Relative Approximate Error ---------- 0.38502 % 0.033427 % 10/9/2007 3 Interpolation http://numericalmethods.eng.usf.edu 13 Topic: Spline Interpolation Method Why Splines ? 2 251 1 )( x xf + = Table : Six equidistantly spaced points in [-1, 1] x 1 y = http://numericalmethods.eng.usf.edu14 Figure : 5 th order polynomial vs. exact function 2 251 x+ -1.0 0.038461 -0.6 0.1 -0.2 0.5 0.2 0.5 0.6 0.1 1.0 0.038461 Why Splines ? 0.4 0.8 1.2 http://numericalmethods.eng.usf.edu15 Figure : Higher order polynomial interpolation is a bad idea -0.8 -0.4 0 -1 -0.5 0 0.5 1 x y 19th Order Polynomial f (x) 5th Order Polynomial Linear Interpolation Given ( ) ( ) ( )( ) nnnn yxyxyxyx ,,,......,,,, 111100 ?? , fit linear splines to the data. This simply involves forming the consecutive data through straight lines. So if the above data is given in an ascending order, the linear splines are given by ())( ii xfy = Figure : Linear splines http://numericalmethods.eng.usf.edu16 Linea sp es Linear Interpolation (contd) ),( )()( )()( 0 01 01 0 xx xx xfxf xfxf ? ? ? += 10 xxx ?? ),( )()( )( 1 12 12 1 xx xx xfxf xf ? ? ? += 21 xxx ?? http://numericalmethods.eng.usf.edu17 . . . ),( )()( )( 1 1 1 1 ? ? ? ? ? ? ? += n nn nn n xx xx xfxf xf nn xxx ?? ?1 Note the terms of 1 1 )()( ? ? ? ? ii ii xx xfxf in the above function are simply slopes between 1?i x and i x . Example The upward velocity of a rocket is given as a function of time in Table 1. Find the velocity at t=16 seconds using linear and quadratic splines. t v(t) http://numericalmethods.eng.usf.edu18 sm/s 00 10 227.04 15 362.78 20 517.35 22.5 602.97 30 901.67 Table : Velocity as a function of time Figure : Velocity vs. time data for the rocket example 10/9/2007 4 Linear Interpolation 500 550 517.35 ,15 0 =t 78.362)( 0 =tv ,20 1 =t 35.517)( 1 =tv )( )()( )()( 0 01 0 tt tvtv tvtv ? ? += http://numericalmethods.eng.usf.edu19 10 12 14 16 18 20 22 24 350 400 450 362.78 y s f range() fxdesired() x s 1 10+x s 0 10? x s range, x desired, 01 tt ? )15( 1520 78.36235.517 78.362 ? ? ? += t )15(913.3078.362)( ?+= ttv At ,16=t )1516(913.3078.362)16( ?+=v 7.393= m/s Quadratic Interpolation Given ( )( ) ( )( ) nnnn yxyxyxyx ,,,,......,,,, 111100 ?? , fit quadratic splines through the data. The splines are given by ,)( 11 2 1 cxbxaxf ++= 10 xxx ?? http://numericalmethods.eng.usf.edu20 , 22 2 2 cxbxa ++= 21 xxx ?? . . . , 2 nnn cxbxa ++= nn xxx ?? ?1 Find , i a , i b , i c =i 1, 2, ?, n Quadratic Interpolation (contd) Each quadratic spline goes through two consecutive data points )( 0101 2 01 xfcxbxa =++ )( 1111 2 11 xfcxbxa =++ . . http://numericalmethods.eng.usf.edu21 . )( 11 2 1 ??? =++ iiiiii xfcxbxa )( 2 iiiiii xfcxbxa =++ . . . )( 11 2 1 ??? =++ nnnnnn xfcxbxa )( 2 nnnnnn xfcxbxa =++ This co nd itio n gives 2 n eq uatio ns Quadratic Splines (contd) The first derivatives of two quadratic splines are continuous at the interior points. For example, the derivative of the first spline 11 2 1 cxbxa ++ is 11 2 bxa + http://numericalmethods.eng.usf.edu22 The derivative of the second spline 22 2 2 cxbxa ++ is 22 2 bxa + and the two are equal at 1 xx = giving 212111 22 bxabxa +=+ 022 212111 =??+ bxabxa Quadratic Splines (contd) Similarly at the other interior points, 022 323222 =??+ bxabxa . . http://numericalmethods.eng.usf.edu23 . 022 11 =??+ ++ iiiiii bxabxa . . . 022 1111 =??+ ???? nnnnnn bxabxa We have (n-1) such equations. The total number of equations is )13()1()2( ?=?+ nnn . We can assume that the first spline is linear, that is 0 1 =a Quadratic Splines (contd) This gives us ?3n? equations and ?3n? unknowns. Once we find the ?3n? constants, we can find the function at any value of ?x? using the splines, ,)( 11 2 1 cxbxaxf ++= 10 xxx ?? http://numericalmethods.eng.usf.edu24 , 22 2 2 cxbxa ++= 21 xxx ?? . . . , 2 nnn cxbxa ++= nn xxx ?? ?1 10/9/2007 5 Solution Since there are six data points, five quadratic splines pass through them. )( 2 b 100 ?? http://numericalmethods.eng.usf.edu25 , 111 cttatv ++= t , 22 2 2 ctbta ++= 1510 ?? t , 33 2 3 ctbta ++= 2015 ?? t , 44 2 4 ctbta ++= 5.2220 ?? t , 55 2 5 ctbta ++= 305.22 ?? t Solution (contd) Setting up the equatio ns 1. Each quadratic spline passes through two consecutive data points giving 11 2 1 ctbta ++ passes through t = 0 and t = 10, 0)0()0( 11 2 1 =++ cba (1) 04227)10()10( 2 ++ b (2) http://numericalmethods.eng.usf.edu26 Similarly, 04.227)10()10( 22 2 2 =++ cba (3) 78.362)15()15( 22 2 2 =++ cba (4) 78.362)15()15( 33 2 3 =++ cba (5) 35.517)20()20( 33 2 3 =++ cba (6) 35.517)20()20( 44 2 4 =++ cba (7) 97.602)5.22()5.22( 44 2 4 =++ cba (8) 97.602)5.22()5.22( 55 2 5 =++ cba (9) 67.901)30()30( 55 2 5 =++ cba (10) . 111 =ca Solution (contd) Quadratic splines have continuous derivatives at the interior data points At t = 10 0)10(2)10(2 2211 =??+ baba (11) At t = 15 http://numericalmethods.eng.usf.edu27 0)15(2)15(2 3322 =??+ baba (12) At t = 20 0)20(2)20(2 4433 =??+ baba (13) At t = 22.5 0)5.22(2)5.22(2 5544 =??+ baba (14) And assuming the first spline 11 2 1 ctbta ++ is linear, 0 1 =a (15) Solution (contd) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 78362 78.362 04.227 04.227 0 000000115225000000 000000000115225000 000000000110100000 000000000000110100 000000000000100 2 2 1 1 1 b a c b a http://numericalmethods.eng.usf.edu28 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ?? ?? ?? ?? 0 0 0 0 0 67.901 97.602 97.602 35.517 35.517 . 000000000000001 01450145000000000 00001400140000000 00000001300130000 00000000001200120 130900000000000000 15.2225.506000000000000 00015.2225.506000000000 000120400000000000 000000120400000000 5 5 5 4 4 4 3 3 3 2 c b a c b a c b a c Solution (contd) Solving the above 15 equations gives the 15 unknowns as i i a i b i c 1 0 22 704 0 http://numericalmethods.eng.usf.edu29 . 2 0.8888 4.928 88.88 3 -0.1356 35.66 -141.61 4 1.6048 -33.956 554.55 5 0.20889 28.86 -152.13 Solution (contd) Therefore, the splines are given by ,704.22)( ttv = 100 ?? t ,88.88928.48888.0 2 ++= tt 1510 ?? t ,61.14166.351356.0 2 ?+?= tt 2015 ?? t 800 1000 1200 yl 0.05 h?+ y http://numericalmethods.eng.usf.edu30 ,55.554956.336048.1 2 +?= tt 5.2220 ?? t ,13.15286.2820889.0 2 ?+= tt 305.22 ?? t At t = 16 61.141)16(66.35)16(1356.0)16( 2 ?+?=v 24.394= m/s The absolute relative approximate error, a ? is =? a 100 24.394 7.39324.394 × ? = 0.1369% 0 5 10 15 20 25 30 0 200 400 600 y0 0.05 h?? f quadratic range() f quadratic x desired() xl 0.05 w?+x0 0.05 w?? x range, x desired, lietang Microsoft PowerPoint - Lagrangian & Spline Interpolation.ppt [Compatibility Mode]