Lecture Note 3:Polynomial Interpolation Xiaoqun Zhang Shanghai Jiao Tong University Last updated:October 16,2012
Lecture Note 3: Polynomial Interpolation Xiaoqun Zhang Shanghai Jiao Tong University Last updated: October 16, 2012
Lecture note 3 Numerical Analysis 1.1 Introduction We first look at some examples. Lookup table for f(r)=e-dr f(0.520)=0.53790,f(0.521)=0.53876 f(0.522)=0.53962,f(0.523)=0.54048 No f(0.52136)or f(0.52218).How should we do? Census of population: 1940132165 1950151326 1960179323 19702033021980226542 1960249633 There is no record for 1965.How to predict it? General questions:Let (xo,yo),(1,),...,(n,Un)be given.Given a x which is not in fro,x1,...,n},what is the corresponding y? Find a function f(r)such that yo f(o),y1=f(r1),...,Un=f(n). It's hard.There are too "many"functions.One solution is to use polynomials since polynomials have nice properties. Polynomial Interpolation:find a polynomial p(x)such that p(xo)=0,p(r1)=1,,p(rn)=yn 1.1.1 Existence and Uniqueness of polynomial interpolation Questions on polynomial interpolation: Does such a polynomial exist? -Generally,you can not find a linear function to interpolate 3 points. If yes,what is the degree? -2 points,linear;3 points,quadratic;4 points cubic;.. ·Is it unique? -2 points,linear;3 points,quadratic;4 points cubic;... What is a formula for producing p(z)from the given coordinates? -2 points,linear;3 points,quadratic;4 points cubic;... (x0,0):·,(xn,n) 2
Lecture note 3 Numerical Analysis 1.1 Introduction We first look at some examples. • Lookup table for f(x) = √ 2 π R x 0 e −x 2 dx f(0.520) = 0.53790, f(0.521) = 0.53876 f(0.522) = 0.53962, f(0.523) = 0.54048 No f(0.52136) or f(0.52218). How should we do? • Census of population: 1940 132165 1950 151326 1960 179323 1970 203302 1980 226542 1960 249633 There is no record for 1965. How to predict it? General questions: Let (x0, y0), (x1, y1), . . . , (xn, yn) be given. Given a x which is not in {x0, x1, . . . , xn}, what is the corresponding y? • Find a function f(x) such that y0 = f(x0), y1 = f(x1), . . . , yn = f(xn). • It’s hard. There are too “many” functions. One solution is to use polynomials since polynomials have nice properties. • Polynomial Interpolation: find a polynomial p(x) such that p(x0) = y0, p(x1) = y1, . . . , p(xn) = yn 1.1.1 Existence and Uniqueness of polynomial interpolation Questions on polynomial interpolation: • Does such a polynomial exist? – Generally, you can not find a linear function to interpolate 3 points. • If yes, what is the degree? – 2 points, linear; 3 points, quadratic; 4 points cubic;... • Is it unique? – 2 points, linear; 3 points, quadratic; 4 points cubic;... • What is a formula for producing p(x) from the given coordinates? – 2 points, linear; 3 points, quadratic; 4 points cubic;... • (x0, y0), . . . ,(xn, yn). 2
Lecture note 3 Numerical Analysis ● p()=ao ai a2x2+...+amz" .We want to find ao,a1,...,am. m+1 parameters,n+1 conditions (p(zi)=yi) It is reasonable to try first with n=m. So we want to find ao,a1,...,am such that ao a1zo a2o+...+anto y0 do a1z1+a2i+...+anzn=y ao alIn a2zn+...+antn yn Write it into a system of linear equations n To 哈 昭7 ao 「3o1 1 1 “ 理 1 T2 吃 02 .. . . 1 In 品 zn] an Ln」 Xa=可 X-Vandermonde matrix. ·“There exists a unique vector such that Xa=” is equivalent to“det(X)≠0.” Theorem 1 (Theorem 1.1)Given n+1 distinct points xo,11,...,In and the corresponding yo,1,...,yn:there is a polynomial p(x)of degree <n such that p(ro）=o,p(r）=h1,,p(xn)=yn·This polynomial is unique among the set of all polynomials of degree <n. Why degree n and not n? -Why this set? Proof.We will prove that det(X)0.Let To 哈 昭 1 T1 1 T2 Vn(z)= 1 n-1品1 In-1 3
Lecture note 3 Numerical Analysis • p(x) = a0 + a1x + a2x 2 + . . . + amx m • We want to find a0, a1, . . . , am. m + 1 parameters, n + 1 conditions (p(xi) = yi) It is reasonable to try first with n = m. • So we want to find a0, a1, . . . , am such that a0 + a1x0 + a2x 2 0 + . . . + anx n 0 = y0 a0 + a1x1 + a2x 2 1 + . . . + anx n 1 = y1 . . . a0 + a1xn + a2x 2 n + . . . + anx n n = yn • Write it into a system of linear equations 1 x0 x 2 0 . . . xn 0 1 x1 x 2 1 . . . xn 1 1 x2 x 2 2 . . . xn 2 . . . . . . . . . 1 xn x 2 n . . . xn n a0 a1 a2 . . . an = y0 y1 y2 . . . yn X~a = ~y • X — Vandermonde matrix. • “There exists a unique vector such that X~a = ~y” is equivalent to “det(X) 6= 0.” Theorem 1 (Theorem 1.1) Given n + 1 distinct points x0, x1, . . . , xn and the corresponding y0, y1, . . . , yn, there is a polynomial p(x) of degree ≤ n such that p(x0) = y0, p(x1) = y1, . . . , p(xn) = yn. This polynomial is unique among the set of all polynomials of degree ≤ n. – Why degree ≤ n and not n? – Why this set? Proof. We will prove that det(X) 6= 0. Let Vn(x) = 1 x0 x 2 0 . . . xn 0 1 x1 x 2 1 . . . xn 1 1 x2 x 2 2 . . . xn 2 . . . . . . . . . 1 xn−1 x 2 n−1 . . . xn n−1 1 x x2 . . . xn 3
Lecture note 3 Numerical Analysis so that X=Vn(In). We have the claims: 1.Vn(r)is a polynomial of degree n. 2.The roots are zo,1,...,In-1. 3.The coefficients of the term z"is Vn-1(n-1). Proof. 1.Expand the last row by minor. 2.If two row are the same then det(X)=0. 3.Expand the last row by minor. ◇ So Vn(z)=(2n-1)(x-z0)(-z1)...(x-In-1)Vn-1. By induction, ⅓a=dtl到=a-到 V2(x2)=(x2-t0)(x2-x1)(r1-x0) (x3)=(x3-to)(x3-x1)(a3-x2).. Vn(xn)=Πl0≤i<jsn(rj-xi. Since zo,...,n are distinct,det(X)=Vn(Xn)0. 0 1.2 Lagrange Formula Find a polynomial P(z)of order <n passes through (r0,0),(x1,班)，(x2,2),.(rn,h) Method of undetermined coefficients: Pn(z）=a0+a1x+a2x2+..+anx”. Need to solve Xa=灭 Computational cost is high. 4
Lecture note 3 Numerical Analysis so that X = Vn(xn). We have the claims: 1. Vn(x) is a polynomial of degree n. 2. The roots are x0, x1, . . . , xn−1. 3. The coefficients of the term x n is Vn−1(xn−1). Proof. 1. Expand the last row by minor. 2. If two row are the same then det(X) = 0. 3. Expand the last row by minor. So Vn(x) = (xn−1)(x − x0)(x − x1). . .(x − xn−1)Vn−1. By induction, V1(x1) = det 1 x0 1 x1 = (x1 − x0) V2(x2) = (x2 − x0)(x2 − x1)(x1 − x0) V3(x3) = (x3 − x0)(x3 − x1)(x3 − x2). . . Vn(xn) = Π0≤i<j≤n(xj − xi). Since x0, . . . , xn are distinct, det(X) = Vn(Xn) 6= 0. 1.2 Lagrange Formula • Find a polynomial Pn(x) of order ≤ n passes through (x0, y0), (x1, y1), (x2, y2), . . .(xn, yn). • Method of undetermined coefficients: Pn(x) = a0 + a1x + a2x 2 + . . . + anx n . Need to solve X~a = ~y. Computational cost is high. 4
Lecture note 3 Numerical Analysis Computational cost is high: Gaussian Elimination O(n3). Find fast solvers of the linear equation or explicit expression of a. 。Use“bases'”other than{L,x,z2,,z}. .Two points case:(To,y0),(x1,21). Construct two linear functions (polynomials of order 1)L1.o(z)and L11(x) such that: L1.0(z0)=1L1.0(x1)=0 and L1,1(xo)=0L1,1(x1)=1. Then,let 乃(x)=0L1,o(x)+hL1,1(x) We have P1(xo)=0L1,0(xo)+y1L1,1(x0)=0 (c1)=0L1,0(x1)+1L1,1(x1)=h. ·Construct L1,o(r): L1.0(a)=工- T0-E1 Use a graph to illustrate it!. Similarly, L1,1()=-0 x1一T0 Generalize this idea to more points. Lagrange formula. .Given (To,20),(1:11),...(In:Un). Construct polynomials Lo(x),L1(),...,Ln(x)of order n such that Ln.o(o)=1,Ln.o(1)=0,Ln.o(2)=0,...In.o(n)0. Ln,1(xo)=0,Ln,1(x1)=1,Lm,1(x2）=0,.Ln,1(xn)≠0. Ln.i(xi)=1,Ln.i(j)=0,Vj#i. Ln.n(0)=0,Ln,n(1)=0,...Ln.n(In-1)=0,Ln,n(n)#1. 5
Lecture note 3 Numerical Analysis • Computational cost is high: Gaussian Elimination O(n 3 ). • Find fast solvers of the linear equation or explicit expression of a. • Use “bases” other than {1, x, x2 , . . . , xn}. • Two points case: (x0, y0),(x1, y1). Construct two linear functions (polynomials of order 1) L1,0(x) and L1,1(x) such that: L1,0(x0) = 1 L1,0(x1) = 0 and L1,1(x0) = 0 L1,1(x1) = 1. Then, let P1(x) = y0L1,0(x) + y1L1,1(x) We have P1(x0) = y0L1,0(x0)+y1L1,1(x0) = y0 P1(x1) = y0L1,0(x1)+y1L1,1(x1) = y1. • Construct L1,0(x): L1,0(x) = x − x1 x0 − x1 . Use a graph to illustrate it!. Similarly, L1,1(x) = x − x0 x1 − x0 . • Generalize this idea to more points. Lagrange formula. • Given (x0, y0),(x1, y1), . . .(xn, yn). Construct polynomials L0(x), L1(x), . . . , Ln(x) of order n such that Ln,0(x0) = 1, Ln,0(x1) = 0, Ln,0(x2) = 0, . . . Ln,0(xn) 6= 0. Ln,1(x0) = 0, Ln,1(x1) = 1, Ln,1(x2) = 0, . . . Ln,1(xn) 6= 0. . . . Ln,i(xi) = 1, Ln,i(xj ) = 0, ∀j 6= i. . . . Ln,n(x0) = 0, Ln,n(x1) = 0, . . . Ln,n(xn−1) = 0, Ln,n(xn) 6= 1. 5