Zhihua Zhang - Environmental Data Analysis: Methods and Applications

Let 1=x0 and let them be equally spaced, and data (xk,yk) ( k=0,1,,M ) be given. Then the polynomial fitting data is f(x)==0NP(x) , where 2M1k=1MykP(xk) and P(x) is the -th normal Legendre polynomial.

Now we consider the orthogonal polynomial with weight function to fit the given data.

Given data (xk,yk) ( k=1,,M ) satisfying a=x1 , the normal orthogonal polynomials P()(x) ( =0,1, ) on [a,b] with weight function (x) satisfy

where , is the Kronecker delta. Then the polynomial fitting data is

where

In fitting data using the orthogonality method, the BC-decomposition of matrices is crucial.

Let A be an MN matrix with rank r, where MN . Then the matrix A can be decomposed into A=BC , where B is an Mr matrix, C is an rN matrix, and ranks of B and C are both r.

In fact, let A=(ij)MN and aj=(1j,,Mj)T ( j=1,,N ) be its j-th column vector. Since rank(A)=r , there are r linearly independent column vectors. Say, a1,a2,,ar are the r linearly independent column vectors. We construct an orthonormal basis e1,e2,,eM on RM such that for any s=2,,M ,

Let P=(e1|e2||eM) . Then P is an orthogonal matrix of order M. Define U=PTA . Since PT=P1 ,

Let U=(ukl)MN , where ukl=(ek,al) . Since a1,a2,,ar are linearly independent, al=j=1rcjlaj ( l>r ). From this and esaj , it follows that ukl=(ek,al)=j=1rcjl(ek,aj)=0 ( k>r ). Denote B=(ukl)k,l=1,,r and C=(ukl)k=1,,r;l=r+1,,N . So

and the product PU only depends on the first r columns of P and the first r rows of U, and A=PU=BC , where B=(e1|e2||er) and C=(B|C) .

Consider a general system of linear independent functions 1(x),2(x),,N(x) . We use their linear combination F(x) to fit observation data (xi,yi) ( i=1,,M ), where MN , such that

attains the minimal value. Some often used function systems are the power function system {xi} , the trigonometric function system sin(ix) , and the exponential function system {eix} .

Let Fj=0 . Then

This is a system of linear equations. The matrix form is AT(Ay)=0 , where

and ij=j(xi) ( i=1,,M ; j=1,,N ). Denote by =(1,,N) the solution of (). Then the combination fitting data is j=1Njj(x) . We solve out = below.

Replacing A by its BC-decomposition in the matrix form of (),

Multiplying both sides by C,

Both CCT and BTB are rr nonsingular matrices and rank(B)=rank(C)=r , so

This implies that CT(CCT)1C=CT(CCT)1W . Note that CT(CCT)1C=I . The desired solution is

Write =(1,,N) . So the combination F(x) fitting data is j=1Njj(x) .

Given a real sequence yk ( k=1,,n ) and nodes xk ( k=1,,n ), where x1, we construct a Lagrange interpolation polynomial Ln(x) of degree n1 such that Ln(xk)=yk ( k=1,,n ). Moreover, we introduce the uniform convergence and mean convergence of the Lagrange interpolation polynomial sequences.

Let n(x) be the product of n factors (xxk) ( k=1,,n ), i.e.,

Then n(x) is a polynomial of degree n and n(xk)=0 ( k=1,,n ), and

Define fundamental polynomials as

Then lk(x) is a polynomial of degree n1 and lk(xj)=jk for j,k=1,,n , where jk is the Kronecker delta.

Let P(x) be any polynomial of degree n1 . Then P(x)=k=1nP(xk)lk(x) . In fact, let

Then Q(x) is a polynomial of degree n1 and Q(xk)=P(xk) ( k=1,,n ). These n pairs of values determine that P(x)=Q(x) , i.e., P(x)=k=1nP(xk)lk(x) .

Lagrange interpolation polynomial of degree n1 is defined as

Clearly, Ln(xj)=yj ( j=1,,n ). Formula () is called the Lagrange interpolation formula. For convenience of computation, it is rewritten in the form

This form is called the Newton interpolation formula. The coefficients {ck} are computed as follows.

The combination of Lagrange and Newton interpolation formulas gives

When we add a node, if we use the Lagrange interpolation formula, this again necessitates computing each fundamental polynomial li(x) ; if we use the Newton interpolation formula, the coefficients already computed do not have to be changed. Therefore, in numerical computations, it is best to use the Newton interpolation formula.