WIXLIB

Interpolation & Polynomial ApproximationLagrange Interpolating Polynomials INumerical Analysis (9th Edition)R L Burden & J D FairesBeamer Presentation Slidesprepared byJohn CarrollDublin City Universityc 2011 Brooks/Cole, Cengage Learning

WeierstrassTaylor PolynomialsLagrange PolynomialExampleOutline1Weierstrass Approximation Theorem2Inaccuracy of Taylor Polynomials3Constructing the Lagrange Polynomial4Example: Second-Degree Lagrange Interpolating PolynomialNumerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires2 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleOutline1Weierstrass Approximation Theorem2Inaccuracy of Taylor Polynomials3Constructing the Lagrange Polynomial4Example: Second-Degree Lagrange Interpolating PolynomialNumerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires3 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleWeierstrass Approximation TheoremAlgebraic PolynomialsOne of the most useful and well-known classes of functions mappingthe set of real numbers into itself is the algebraic polynomials, the setof functions of the formPn (x) an x n an 1 x n 1 · · · a1 x a0where n is a nonnegative integer and a0 , . . . , an are real constants.Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires4 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleWeierstrass Approximation TheoremPn (x) an x n an 1 x n 1 · · · a1 x a0 ,Algebraic Polynomials (Cont’d)One reason for their importance is that they uniformly approximatecontinuous functions.By this we mean that given any function, defined and continuouson a closed and bounded interval, there exists a polynomial that isas “close” to the given function as desired.This result is expressed precisely in the WeierstrassApproximation Theorem.Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires5 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialyExampley 5 f (x) 1 ey 5 P (x)y 5 f (x)y 5 f (x) 2 eabxWeierstrass Approximation TheoremSuppose that f is defined and continuous on [a, b]. For each ǫ 0,there exists a polynomial P(x), with the property that f (x) P(x) ǫ,Numerical Analysis (Chapter 3)for all x in [a, b].Lagrange Interpolating Polynomials IR L Burden & J D Faires6 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleBenefits of Algebraic PolynomialsAnother important reason for considering the class of polynomialsin the approximation of functions is that the derivative andindefinite integral of a polynomial are easy to determine and arealso polynomials.For these reasons, polynomials are often used for approximatingcontinuous functions.Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires7 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleOutline1Weierstrass Approximation Theorem2Inaccuracy of Taylor Polynomials3Constructing the Lagrange Polynomial4Example: Second-Degree Lagrange Interpolating PolynomialNumerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires8 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: Taylor PolynomialsInterpolating with Taylor PolynomialsThe Taylor polynomials are described as one of the fundamentalbuilding blocks of numerical analysis.Given this prominence, you might expect that polynomialinterpolation would make heavy use of these functions.However this is not the case.The Taylor polynomials agree as closely as possible with a givenfunction at a specific point, but they concentrate their accuracynear that point.A good interpolation polynomial needs to provide a relativelyaccurate approximation over an entire interval, and Taylorpolynomials do not generally do this.Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires9 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: Taylor PolynomialsExample: f (x) exWe will calculate the first six Taylor polynomials about x0 0 forf (x) ex .NoteSince the derivatives of f (x) are all ex , which evaluated at x0 0 gives1.The Taylor polynomials are as follows:Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires10 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleTaylor Polynomials for f (x) ex about x0 0P0 (x) 1P1 (x) 1 xx22x2 x3P3 (x) 1 x 26P2 (x) 1 x P4 (x) 1 x x2 x3x4 2624P5 (x) 1 x x4x5x2 x3 2624 120Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires11 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleTaylor Polynomials for f (x) ex about x0 0y20y 5 P5(x)y 5 exy 5 P4(x)15y 5 P3(x)10y 5 P2(x)5y 5 P1(x)y 5 P0(x)21123xNotice that even for the higher-degree polynomials, the error becomesprogressively worse as we move away from zero.Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires12 / 33

WeierstrassTaylor PolynomialsTaylor Polynomials for f (x) Lagrange Polynomial1xExampleabout x0 1Example: A more extreme caseAlthough better approximations are obtained for f (x) ex ifhigher-degree Taylor polynomials are used, this is not true for allfunctions.Consider, as an extreme example, using Taylor polynomials ofvarious degrees for f (x) x1 expanded about x0 1 toapproximate f (3) 31 .Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires13 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialTaylor Polynomials for f (x) 1xExampleabout x0 1CalculationsSincef (x) x 1 , f ′ (x) x 2 , f ′′ (x) ( 1)2 2 · x 3 ,and, in general,f (k ) (x) ( 1)k k !x k 1 ,the Taylor polynomials arePn (x) nXf (k ) (1)k 0Numerical Analysis (Chapter 3)k!(x 1)k nX( 1)k (x 1)k .k 0Lagrange Interpolating Polynomials IR L Burden & J D Faires14 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialTaylor Polynomials for f (x) 13To Approximate f (3) 1xExampleabout x0 1by Pn (3)To approximate f (3) 31 by Pn (3) for increasing values of n, weobtain the values shown below — rather a dramatic failure!When we approximate f (3) 13 by Pn (3) for larger values of n, theapproximations become increasingly inaccurate.n01234567Pn (3)1 13 511 2143 85Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires15 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: Taylor PolynomialsFootnotesFor the Taylor polynomials, all the information used in theapproximation is concentrated at the single number x0 , so thesepolynomials will generally give inaccurate approximations as wemove away from x0 .This limits Taylor polynomial approximation to the situation inwhich approximations are needed only at numbers close to x0 .For ordinary computational purposes, it is more efficient to usemethods that include information at various points.The primary use of Taylor polynomials in numerical analysis is notfor approximation purposes, but for the derivation of numericaltechniques and error estimation.Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires16 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleOutline1Weierstrass Approximation Theorem2Inaccuracy of Taylor Polynomials3Constructing the Lagrange Polynomial4Example: Second-Degree Lagrange Interpolating PolynomialNumerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires17 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The Linear CasePolynomial InterpolationThe problem of determining a polynomial of degree one thatpasses through the distinct points(x0 , y0 )and(x1 , y1 )is the same as approximating a function f for whichf (x0 ) y0andf (x1 ) y1by means of a first-degree polynomial interpolating, or agreeingwith, the values of f at the given points.Using this polynomial for approximation within the interval given bythe endpoints is called polynomial interpolation.Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires18 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The Linear CaseDefine the functionsL0 (x) x x1x0 x1and L1 (x) x x0.x1 x0DefinitionThe linear Lagrange interpolating polynomial though (x0 , y0 ) and(x1 , y1 ) isP(x) L0 (x)f (x0 ) L1 (x)f (x1 ) Numerical Analysis (Chapter 3)x x1x x0f (x0 ) f (x1 ).x 0 x1x1 x0Lagrange Interpolating Polynomials IR L Burden & J D Faires19 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The Linear CaseP(x) L0 (x)f (x0 ) L1 (x)f (x1 ) x x1x x0f (x0 ) f (x1 ).x 0 x1x1 x0Note thatL0 (x0 ) 1,L0 (x1 ) 0,L1 (x0 ) 0,and L1 (x1 ) 1,which implies thatP(x0 ) 1 · f (x0 ) 0 · f (x1 ) f (x0 ) y0andP(x1 ) 0 · f (x0 ) 1 · f (x1 ) f (x1 ) y1 .So P is the unique polynomial of degree at most 1 that passes through(x0 , y0 ) and (x1 , y1 ).Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires20 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The Linear CaseExample: Linear InterpolationDetermine the linear Lagrange interpolating polynomial that passesthrough the points (2, 4) and (5, 1).SolutionIn this case we haveL0 (x) x 51x 21 (x 5) and L1 (x) (x 2),2 535 23so11420 12P(x) (x 5) · 4 (x 2) · 1 x x x 6.333333Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires21 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The Linear Casey(2,4)432y 5 P(x) 2x 1 6(5,1)112345xThe linear Lagrange interpolating polynomial that passes through thepoints (2, 4) and (5, 1).Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires22 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: Degree n Constructionyy 5 f (x)y 5 P(x)x0x1x2xnxTo generalize the concept of linear interpolation, consider theconstruction of a polynomial of degree at most n that passes throughthe n 1 points(x0 , f (x0 )), (x1 , f (x1 )), . . . , (xn , f (xn )).Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires23 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The General CaseConstructing the Degree n PolynomialWe first construct, for each k 0, 1, . . . , n, a function Ln,k (x) withthe property that Ln,k (xi ) 0 when i 6 k and Ln,k (xk ) 1.To satisfy Ln,k (xi ) 0 for each i 6 k requires that the numerator ofLn,k (x) contain the term(x x0 )(x x1 ) · · · (x xk 1 )(x xk 1 ) · · · (x xn ).To satisfy Ln,k (xk ) 1, the denominator of Ln,k (x) must be thissame term but evaluated at x xk .ThusLn,k (x) (x x0 ) · · · (x xk 1 )(x xk 1 ) · · · (x xn ).(xk x0 ) · · · (xk xk 1 )(xk xk 1 ) · · · (xk xn )Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires24 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The General CaseLn,k (x) (x x0 ) · · · (x xk 1 )(x xk 1 ) · · · (x xn ).(xk x0 ) · · · (xk xk 1 )(xk xk 1 ) · · · (xk xn )L n,k(x)1x0Numerical Analysis (Chapter 3)x1.x k21xkx k11Lagrange Interpolating Polynomials I.x n21xnR L Burden & J D Fairesx25 / 33

WeierstrassTaylor PolynomialsLagrange PolynomialExampleThe Lagrange Polynomial: The General CaseTheorem: n-th Lagrange interpolating polynomialIf x0 , x1 , . . . , xn are n 1 distinct numbers and f is a function whosevalues are given at these numbers, then a unique polynomial P(x) ofdegree at most n exists withf (xk ) P(xk ),for each k 0, 1, . . . , n.This polynomial is given byP(x) f (x0 )Ln,0 (x) · · · f (xn )Ln,n (x) nXf (xk )Ln,k (x)k 0where, for each k 0, 1, . . . , n, Ln,k (x) is defined as follows:Numerical Analysis (Chapter 3)Lagrange Interpolating Polynomials IR L Burden & J D Faires26 / 33