《数值分析》课程PPT教学课件（Numerical Analysis）Chapter 3 Interpolation method

Chapter 3 Interpolation methodSection 1IntroductionSection 2 Lagrange interpolationSection 3 Deviation and Newton interpolationSection 4 Difference and Equidistant interpolationSection 5Hermite interpolationSection 6Piecewise low-order interpolationSection 7Cubic spline interpolation上页下页返圆

上页 下页 返回 Chapter 3 Interpolation method Section 1 Introduction Section 2 Lagrange interpolation Section 3 Deviation and Newton interpolation Section 4 Difference and Equidistant interpolation Section 5 Hermite interpolation Section 6 Piecewise low-order interpolation Section 7 Cubic spline interpolation

$1 IntroductionThe interpolation method is an important numerical method iswidely used in theoretical research and engineering practice.The definitionofinterpolation method:If function y = f (x) in the interval [a, b] are defined, andknown the value of yo, yi, ... , yn is a ≤ Xo<xi<... <xn ≤b, ifhaving a simplefunction P(x), letP(x;) =yi(i = 0,1,...,n)is right, P(x) is called the interpolation function of f(x), spot XoXi, ... , Xn is called interpolation node , the interval [a, b] is calledInterpolation interval, The method of solving interpolation上页functionP(x)calledinterpolationmethod.下页返圆

上页 下页 返回 The interpolation method is an important numerical method is widely used in theoretical research and engineering practice. The definition of interpolation method ： If function y = f (x) in the interval [a, b] are defined, and known the value of y0 , y1 , . , yn is a ≤ x0 < x1< . < xn ≤ b, if having a simple function P(x), let P(xi ) = yi (i = 0,1,.,n) is right，P(x) is called the interpolation function of f (x), spot x0 , x1 , . , xn is called interpolation node , the interval [a, b] is called Interpolation interval, The method of solving interpolation function P(x) called interpolation method. §1 Introduction

The geometric significance ofy=f(x)interpolationmethod:y=P(x)Getting the solution of curvey=P (x) , let it through given n+1points (xi,yi), i= O,l,...,n, andusing it approximate the known curve yXnXI=f (x) .上页下页返圆

上页 下页 返回 The geometric significance of interpolation method： Getting the solution of curve y = P (x) ，let it through given n+1 points (xi , yi )， i = 0,1,.,n，and using it approximate the known curve y = f (x)

$ 2 Lagrange interpolationDLinearinterpolation and Parabolic interpolation()Linearinterpolationyy=L(x)y=f(x)-Used straight line y = L, (x) approximat e curveiVk+1y = f(x), L,(x) is called Linear interpolat ionpolynomial , it can beindicated byTwo points linear equations4XkXk+1xXk+1 -XX-XkL;(x) = Yk+lXk+1 -XkXk+1 -Xk上页下页返圆

上页 下页 返回 1) Linear interpolation and Parabolic interpolation (1) Linear interpolation 1 1 1 1 1 1 1 ( ) Two points linear equations polynomial ( ) ( ) Linear interpolat ion straight line ( ) approximat e curve + + + + − − + − − = = = k k k k k k k k y x x x x y x x x x L x it can beindicated by y f x L x is called Used y L x ， ， §2 Lagrange interpolation

L, (x) is composed of two linear functionsX-XkX-X+L, 1k+I(x)lk(x) =Xk-Xk+1Xk+1-XkI (x) and Ik+i (x) are also Linear interpolat ion polynomial sInthe node need: l(x)= 1, l(xk+)= O;Ik+1(x) = O, lk+1(xk+1) = 1. calling l,(x) and lk+1(x) areLinear interpolat ion basic functions .上页下页返圆

上页 下页 返回 Linear interpolat ion basic functions . ( ) 0 ( ) 1. ( ) ( ) In the node need ( ) 1 ( ) 0 ( ) ( ) Linear interpolat ion polynomial s ( ) ( ) ( ) 1 1 1 1 1 1 1 1 1 1 1 l x l x calling l x and l x are l x l x l x and l x are also x x x x l x x x x x l x L x is composed of two linear functions k k k k k k k k k k k k k k k k k k k k + + + + + + + + + + = = = = − − = − − = ， ： ， ； ， ，

(2) Parabolic interpolationUsed para - curve y = L,(x) approximat e curve y = f(x),L, (x) is called the two difference polynomial ,used basic function method we can get:L,(x)= yk-lk-I(x)+ yklk(x)+ yk+1k+1(x).If basic function lk-i(x)、 Ik(x) and Ik+(x) are quadratic function,and in the node need :1(i=j)(i,j=k-l,k,k+l)1 (x) =?0(i±j)上页下页返圆

上页 下页 返回 (2) Parabolic interpolation ( ) ( ) ( ) ( ) . : ( ) d the two difference polynomial , para - curve ( ) approximat e curve ( ) 2 1 1 1 1 2 2 L x y l x y l x y l x used basic function method we can get L x is calle Used y L x y f x = k− k− + k k + k+ k+ = = ， ( 1 1) 0 ( ) 1 ( ) ( ) and in the node need ( ) ( ) ( ) quadratic function, 1 1 = − +  =    = − + i j k k k i j i j l x If basic function l x l x and l x are i j k k k ， ， ， ：

the basic functions of meeting the conditions is easy to get,for example lk-, (x), because it has two zero pointsX and xk+1' so can be exp ressed :Ik-1(x) = A(x - x,)(x - xk+1), A is a indetermin ed coefficien t,can be got by the condition Ik-I(xk-) = 1,1A=SO(Xk-1 - X)(xk-1 - Xk+1)(x - x)(x - Xk+1)(k-1(x) (Xk-1 - X,)(xk-1 - Xk+1)(x - xk-1)(x - X+1)(x - xk-1)(x -x)the same to, l,(x) =lk+1(x)(xk - Xk-1)(xk - Xk+1)(Xk+1 -Xk-1)(Xk+1 -Xk)上页下页返圆

上页 下页 返回 . ( )( ) ( )( ) ( ) ( )( ) ( )( ) ( ) ( )( ) ( )( ) ( ) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 k k k k k k k k k k k k k k k k k k k k k x x x x x x x x l x x x x x x x x x the same t o l x x x x x x x x x l x − − − − = − − − − = − − − − = + − + − + − + − + − − + + − ， ， ， so x x x x A can be got by the condition l x l x A x x x x A is a x x so can be ressed for example l x because it has two k k k k k k k k k k k k ， ， ， ， ， ( )( ) 1 ( ) 1 ( ) ( )( ), indetermin ed coefficien t, and exp : ( ) zero points the basic functions of meeting the conditions is easy to get 1 1 1 1 1 1 1 1 1 − − + − − − + + − − − = = = − −

二, Lagrange interpolating polynomialUse nth interpolation polynomial y= L,(x) to approch y= f(x) ,or use basisfunction theory to get: L,(x) =Zyl(x) ,called Lagrange interpolationpolymial.In order to structure L,(x) ,firstly define the nth interpolatingbasis function.Definition 1 If nth polynomial 1,(x) (j = 0, 1, ..., n) on the n+1 nodes<x<..<x,[1, k=j;(j, k=0, ,.,n),call the n+1 nthmeets the condition 1(x)=)[0,k±j.polynomial l,(x) (j = 0, ,..,n) nth interpolating basis function.n-l,n-2 are the linear and 2th interpolating basis function.Use thesimilar method to get the nth interpolating basis function.(x-x).(x-x-(x-x+).(x-xm)1 (x) :(k =0, 1, ", n)上页X-x)..(x-Xk-(x-Xk+1).(x-xm)下页返圆

上页 下页 返回 y L (x) = n y = f (x) = = n k Ln x yk l k x 0 ( ) ( ) 二、Lagrange interpolating polynomial Use nth interpolation polynomial to approch ,or use basis function theory to get: ,called Lagrange interpolation polymial.In order to structure ,firstly define the nth interpolating basis function. L (x) n Definition 1 If nth polynomial on the n+1 nodes meets the condition ,call the n+1 nth polynomial nth interpolating basis function. l (x) ( j 0 1 , n) j = ， n x  x  x 0 1 ( 0 1 , ) 0 , . 1, ( ) j k n k j k j l x j k ， ， ； =     = = l (x) ( j 0 1 , n) j = ， n=1,n=2 are the linear and 2th interpolating basis function.Use the similar method to get the nth interpolating basis function. ( 0 1 , ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) 0 1 1 0 1 1 k n x x x x x x x x x x x x x x x x l x k k k k k k n k k n k      = ， − − − − − − − − = − + − +

So,the Lagrange interploting polymial isnnnx-xL,(x)=Zyel(x)=)DykXk-Xjk=0k=0j=0j+kIntroduce the sign On+i(x)=(x-xo)(x-xi)..(x-xn), and afterdifferentiating for x,make x = x ,get0n+1(x) =(x-x)...(x -Xk-1)(x -xk+1)...(x -xn),Thus,the Lagrange interploting polymial can be exchanged ton(x)0.ZykL,(x) =上页(x-xk)0n+1(xk)k=0下页返圆

上页 下页 返回 n+1 (x) = (x − x0 )(x − x1 )(x − xn )， k x = x k n k n k n j k j k j j n k k y x x x x L (x) y l (x) ( ) 0 0 0    = =  = − − = = = + + −  = n k k n k n n k x x x x L x y 0 1 1 ( ) ( ) ( ) ( )   So,the Lagrange interploting polymial is Introduce the sign and after differentiating for x,make ,get ( ) ( ) ( )( ) ( ), n 1 xk = xk − x0 xk − xk 1 xk − xk 1 xk − xn   +  − +  Thus,the Lagrange interploting polymial can be exchanged to

There is the following theorem on the existence and uniqueness ofthe interpolating polynomial:Theorem 1 In the polynomial set Hn ,which's order don't exceed n.the interpolating polynomial L,(x,)=y, (j=0, ,., n) is unique when itmeets the condition L,(x)e HnNote : If the polynomial's order is not limited into n,theinterpolating polynomial is not uniqueFor example P(x)= L,(x)+ p(x)II(x-x) i is also an interpolatingpolynomial,among which p(x) can be any polynomial.上页下页返圆

上页 下页 返回 Hn L (x ) y ( j 0 1 n) n j = j = ，， Note：If the polynomial's order is not limited into n,the interpolating polynomial is not unique. There is the following theorem on the existence and uniqueness of the interpolating polynomial: Theorem 1 In the polynomial set ,which's order don't exceed n, the interpolating polynomial is unique when it meets the condition n Hn L (x) For example is also an interpolating polynomial,among which can be any polynomial. = = + − n i n i P x L x p x x x 0 ( ) ( ) ( ) ( ) p(x)