Lecture note 3 Numerical Analysis Then construct Pn(x)by B.()=∑Ln =0 We have Pn(i)=Vi. Find it！ .1,22,...,In are the n roots of Ln.o(),so Ln,0(x)=C(x-x1)(x-x2).(x-xn) where C is a constant. To find C,we use Ln.o(ro)=1. 1=Ln,0(xo）=C(x-x1)(x-x2).(x-xn) So 1 C=0-10-2)(0-n】） Therefore Ln,0(x)= (c-1)x-2).(红-xn）Π=1(e-x) (0-E1)(z0-x2).(0-xn)Π巧=1(0-) ·Similarly, Ln.i()= Π明=0j≠z-） Π=0，j≠ci-) Use a graph to illustrate it. .Lagrange formula:Given (ro:y0),(z1,),...,(En,Un).Define Π巧=0（c-） =0 Π写=0j≠(-） ·Example: zo 1,1 =2,r2 =4 and the correspondences yo =8,y 1 and y2=5. Find the polynomial p(x)of order 2 such that yo =p(xo),y=p(1),y2= p(r2) B(回=8c-2儿a-0+1g-1g-0+5红-a-2=3x2-16r+21 (1-2)1-4)(2-1)(2-4)(4-1)(4-2) Drawbacks of Lagrange interpolation. 6
Lecture note 3 Numerical Analysis • Then construct Pn(x) by Pn(x) = Xn i=0 yiLn,i(x). We have Pn(xi) = yi . Find it! • x1, x2, . . . , xn are the n roots of Ln,0(x), so Ln,0(x) = C(x − x1)(x − x2). . .(x − xn), where C is a constant. To find C, we use Ln,0(x0) = 1. 1 = Ln,0(x0) = C(x − x1)(x − x2). . .(x − xn). So C = 1 (x0 − x1)(x0 − x2). . .(x0 − xn) Therefore, Ln,0(x) = (x − x1)(x − x2). . .(x − xn) (x0 − x1)(x0 − x2). . .(x0 − xn) = Qn j=1(x − xj ) Qn j=1(x0 − xj ) • Similarly, Ln,i(x) = Qn j=0,j6=i (x − xj ) Qn j=0,j6=i (xi − xj ) • Use a graph to illustrate it. • Lagrange formula: Given (x0, y0), (x1, y1), . . . , (xn, yn). Define Pn(x) = Xn i=0 yi · Qn j=0,j6=i (x − xj ) Qn j=0,j6=i (xi − xj ) . • Example: x0 = 1, x1 = 2, x2 = 4 and the correspondences y0 = 8, y1 = 1 and y2 = 5. Find the polynomial p(x) of order 2 such that y0 = p(x0), y1 = p(x1), y2 = p(x2). P2(x) = 8(x − 2)(x − 4) (1 − 2)(1 − 4) +1 (x − 1)(x − 4) (2 − 1)(2 − 4) +5 (x − 1)(x − 2) (4 − 1)(4 − 2) = 3x 2−16x+21 • Drawbacks of Lagrange interpolation. 6
Lecture note 3 Numerical Analysis 1.Given z,need O(n2)to get Pn(x). 2.No part of the previous calculation can be used. Interpolation for additional values of x requires the same amount of effort as the first value. 3.If we want to add a new point (n+1,Un+1)or delete a point,all the “basis”Ln,i(z)should be changed. 1.3 Neville's method Idea:use previous calculation and generate recursively Lagrange polynomial ap- proximations. Definition 1 Let f be a function defined at ro,1,..,x2,..,In,and suppose that m1,m2,·,mk are k distinct integers,,with0≤mi≤n for each i.The Lagrange polynomial that agrees with f(r)at the k points imi,Im2,.,Imx is denoted Pm1,…,mk(c). Theorem 2 Let f be defined at xo,1,...,rk,and let rj and i be two distinct numbers in this set.Then P(z)= （工-工)P0.1.…j-1+1.…k(）-(r-x)D0.1…i-1i+1…k() 工i-Tj describes the k-th Lagrange polynomial that interpolates f at the k+1 points T0,T1,··,工k Algorithms ·INPUT:numbers z,xo,…,xn;values f(zo),…,f(rn)as thcolumn Q0.0,Q1.0,..,Qn,o of Q. .OUTPUT:the table Q with P()=Qn.n. 。Fori=1,2,…,n forj=1,2,…,i set Qig =Q1-Q11 ·Output(Q).Stop. 7
Lecture note 3 Numerical Analysis 1. Given x, need O(n 2 ) to get Pn(x). 2. No part of the previous calculation can be used. Interpolation for additional values of x requires the same amount of effort as the first value. 3. If we want to add a new point (xn+1, yn+1) or delete a point, all the “basis” Ln,i(x) should be changed. 1.3 Neville’s method Idea: use previous calculation and generate recursively Lagrange polynomial approximations. Definition 1 Let f be a function defined at x0, x1, · · · , x2, · · · , xn, and suppose that m1, m2, · · · , mk are k distinct integers, with 0 ≤ mi ≤ n for each i. The Lagrange polynomial that agrees with f(x) at the k points xm1 , xm2 , · · · , xmk is denoted Pm1,··· ,mk (x). Theorem 2 Let f be defined at x0, x1, · · · , xk, and let xj and xi be two distinct numbers in this set. Then P(x) = (x − xj )P0,1,··· ,j−1,j+1,··· ,k(x) − (x − xi)P0,1,··· ,i−1,i+1,··· ,k(x) xi − xj describes the k-th Lagrange polynomial that interpolates f at the k + 1 points x0, x1, · · · , xk. Algorithms • INPUT: numbers x, x0, · · · , xn; values f(x0), · · · , f(xn) as thcolumn Q0,0, Q1,0, · · · , Qn,0 of Q. • OUTPUT: the table Q with P(x) = Qn,n. • For i = 1, 2, · · · , n for j = 1, 2, · · · , i set Qi,j = (x−xi−j )Qi,j−1−(x−xi)Qi−1,j−1 xi−xj . • Output (Q). Stop. 7