Lecture note 3 Numerical Analysis 1.4 Newton's divided difference .method of undetermined coefficient:bases {1,x2,...,r"}. -Expand Pn(x)=ao +ax+a2x2+...+anz". -Need to solve a system linear equation to get ai. -Each basis doesn't depend on given points. Lagrange:bases {In.i()},Li()are polynomials of degree n and Ln,i(i)=1,Ln,i(j)=0,jti. -n回= -The corresponding coefficient is yi. -Each basis depends on o,1,...,i-1,i+1,...,In. -Less flexibility when a new point(+,)is added. Newton's divided difference -Each basis depends on part of the given points. -More flexibility when a new point (i+1,+1)is added. .Newton's divided difference:bases {x-zo,(x-zo)(x-z1),...,(x-zo)(x- 1)...(x-In-1)}.We assume Pn(x)=c0+c(x-xo)+c2(x-x0)(x-x1)+..+cn(x-x0)(x-x1)..(x-xn-1). We need to find ci. 。For co, 0=Pn(xo)=c0→c0=0 Then, Pn(x)=y0+c1(x-zo)+... ·ForC, 1=Pn(x1)=0+c1(x1-xo） So =欢-0 x1-T0 ·ForC2, 2=Pn(x2)=0+c(x2-x0）+c2(x2-xo)(c2-x1) So c2=2-0-a(2-x0) (x2-x0)(r2-工1) 8Lecture note 3 Numerical Analysis 1.4 Newton’s divided difference • method of undetermined coefficient: bases {1, x, x2 , . . . , xn}. – Expand Pn(x) = a0 + a1x + a2x 2 + . . . + anx n. – Need to solve a system linear equation to get ai . – Each basis doesn’t depend on given points. • Lagrange: bases {Ln,i(x)}, Li(x) are polynomials of degree n and Ln,i(xi) = 1, Ln,i(xj ) = 0, j 6= i. – Ln,i(x) = Qn j=0,j6=i (x−xj ) Qn j=0,j6=i (xi−xj ) . – The corresponding coefficient is yi . – Each basis depends on x0, x1, . . . , xi−1, xi+1, . . . , xn. – Less flexibility when a new point (xi+1, yi+1) is added. • Newton’s divided difference – Each basis depends on part of the given points. – More flexibility when a new point (xi+1, yi+1) is added. • Newton’s divided difference: bases {x − x0,(x − x0)(x − x1), . . . ,(x − x0)(x − x1). . .(x − xn−1)}. We assume Pn(x) = c0+c1(x−x0)+c2(x−x0)(x−x1)+. . .+cn(x−x0)(x−x1). . .(x−xn−1). We need to find ci . • For c0, y0 = Pn(x0) = c0 =⇒ c0 = y0. Then, Pn(x) = y0 + c1(x − x0) + . . . • For c1, y1 = Pn(x1) = y0 + c1(x1 − x0) So c1 = y1 − y0 x1 − x0 • For c2, y2 = Pn(x2) = y0 + c1(x2 − x0) + c2(x2 − x0)(x2 − x1) So c2 = y2 − y0 − c1(x2 − x0) (x2 − x0)(x2 − x1) 8