[Enter Post Title Here]

 

 

Wilson Sumanang - Lecture Notes Week #4

Week #4

Interpolation and Polinomial Approximation

It is the approximation of functions using polynomials

Graph1.jpg

It is also used for example to compute sin(x), cos(x), ex in the computer

 

Taylor Approximation

A polynomial pn(x) can be used to approx f(x)

                f(x) = pn(x) + en(x)

                f(x) pn(x) =

Example :

                sin(x) =  +

                           =           0             +               x                +                 0              +                  + ...

                          = 

 = 1 + x +  +  + ...

Methods for evaluating a polynomial ; assume :

               

                Evaluating each term independently will require 10 multiplicationand 4 additions

Horners Method (also called nested multiplication)

                ( ( 2x + 4 ) x + 3 ) x + 2 ) x + 1

                4 multiplication and 4 additions

 

Disadvantage of Taylor Expansion

The problem is that higher order derivatives must be known and maybe hard to compute

 

Polynomial Approximation

Suppose that a function f(x) is known to have N+1 points (X0, Y0), (X1, Y1), ..., (XN, YN)

such that

                                    and  YK = f(XK)

Situations arise when we want to approximate f(x) with a polynomial

                If , the approximation p(x) is called an interpolated value

                If  or , the approximation p(x) is called an extrapolated value

 

Lagrange Approximation

                Assume two points (X0, Y0), (X1, Y1) The polynomial that passes through two points is

                                                m =                                              m =

           m =  =

                 =  (

                           Y =  (

Lagrange method uses a different way to find this polynomial. The lagrange polynomial is written as follows :

                P1(x) = y =    +  

               

                P1(X0) =   1  +   0

                P1(X0) =

                P1(X1) =   0  +    1

                P1(X1)  = 

The terms

                L1,0 =                          and L1,1 =

are called Langrange polynomials

For p2(x) we have

                X =                    1                              0                              0

                X =                     0                              1                              0

                X =                    0                              0                              1

P2(x) =   +   

P2(x2) =  

For P3(x) =    +   +                                      

In general,

                PN(x) =

where  =

Example.

We want to approx sin(x) in the interval [0, ∏/2] with a polynomial of degree 3 and 4 points

                                X                             sin(x)

                                = 0                      = 0

                                = ∏/6                = 0.5

                                = ∏/3                = 0.866

                                = ∏/2                = 1

P3(x) =

Now use polynomial to estimate  sin(∏/4) = .7071

P3(∏/4) =

= .28078 + .4871 - .06246

= .7054

 

Newthon polynomials

- In langrange polymials  PN-1(x)  and PN(x) are not related

- Newthon polynomials can be built incrementally, so the work done to build PN-1(x)   can be used to build PN(x)

-Assume

P1(x) = a0 + a1(x - x0)

P2(x) = a0 + a1(x - x0) + a2(x - x0)(x - x1)

          = P1(x) + a2(x - x0)(x - x1)

P3(x) = a0 + a1(x - x0)+ a2(x - x0)(x - x1) + a3(x - x0)(x - x1)(x - x2)

PN(x) = a0 + a1(x - x0) + an(x - x0)...(x - xN-1)

How to compute a0, a1, ..., aN

Assume we want to build P1(x) with the points (x0, ƒ(x0)) and (x1, ƒ(x1)) where y0 = ƒ(x0) and y1 = ƒ(x1)

P1(x) = a0 + a1(x- x0) (1)

Substiture X = in (1)

P1(x0) = a0 + a1(x0- x0)

a0 = ƒ(x0) (2)

Substiture X = in (1)

ƒ(x1) = P1(x1) = a0 + a1(x1- x0) (3)

Substitute (2) in (3)

ƒ(x1) = ƒ(x0) + a1(x1- x0)

a1 = (ƒ(x1) - ƒ(x0)) / (x1- x0) (4)

Now if we want to build P2(x) with an additional point (X2, f(X2))

P2(x) = f(x) = a0 + a1 (x-x0) + a2(x-x0)(x-x1)... (5)

Substitute X = in (5)

ƒ(x2) = a0 + a1(x2- x0) + a2(x2-x0)(x-x1)... (6)

Substitute (2) and (4) in (6)

ƒ(x2) = ƒ(x0) + (x2- x0) *(ƒ(x1) - ƒ(x0)) / (x1- x0) + a2(x2-x0)(x-x1)

a2 = {  ƒ(x2) - ƒ(x0) - [(x2- x0) *(ƒ(x1) - ƒ(x0)) / (x1- x0)] } / (x2-x0)(x-x1)

Add to the numerator ƒ(x1) x1 -  ƒ(x1) x1

a2 = (1 /  x2-x0 ) [ (ƒ(x2) - ƒ(x1)) / (x2- x1)) - (ƒ(x1) - ƒ(x0)) / (x1- x0) ]

Example:

Build polynomial P1(x), P2(x), P3(x) that approximate ƒ(x) = sin(x) in the interval 0,∏/2

      xk                        ƒ(xk)                        ƒ[xk-1,xk]                                                    ƒ[xk-2, xk-1, xk]                               ƒ[xk-3, xk-2, xk-1, xk]

x0   0                       sin(0) = 0         (.5-0)/(0.5236) = .9544 (a1)

x1  ∏/6 = 0.5236  sin(∏/6) = .5    

x2  ∏/3 = 1.047    .8659               (0.8659-0.5)/(1.047-0.5236)=.699 (.60351)/(1.047) = -.2404              (-.179)/(1.5708) = -.1137

x3   ∏/2 = 1.5708  1                      (1-0.869)/(1.5708-1.047) = 0.256 (.256-0.699)/(1.5708-0.5236) = -0.4230

f'(a)=\lim_{h\to 0}{f(a+h)-f(a)\over h}              

P1(x) = 0 + 0.9549(x - 0) = 0.9549x

P2(x) = 0.9549x + (-.2444)(x - x0)(x - x0)

P3(x) = 0. .9549x + (-.2444)(x - x0)(x - x0) - 0.1137(x - x0)(x - x1)(x - x2)

 

sin(∏/4) = 0.7071

Pade Approximation

They are approximation for functions that we a qutient of two polynomials

                RN,M(x) =  for ... (1)

where

                ... (2)

                ... (3)

The polynomials are constructed of f(x) and RN,M(x) agree at x = 0 and their derivatives up to N+M agree also at x=0

Assume that f(x) has the following Maclaurin expansion (Maclaurin expansion is the same as Taylor expansion when x = 0)

                ƒ(x) = a0 + a1x + a2x2 + ... + aKxK... (4)

­­Then we make,

                ƒ(x)  = RN,M(x) =  ... (5)

                ƒ(x)   =  ... (6)

Substitute (4), (2), and (3)  into (6) :

                (a0 + a1x + a2x2 + ... + aKxK) () =  ... (7)

we want the terms multiplied by x to be equal, the term multiplied by x2 to be equal and so on so we get from (7) we get :

                a0 =  

                a1x + a0x =

and so on..

Example:

Find the Padé approximation R2, 2(x) for ƒ(x) = ln(1+x)/x start with the Maclurin expansion

ƒ(x) = 1  - x/2 + x2/3 - x3/4 + x4/5 - …

Solution:

RN, M(x) = PN(x)/QM(x)

R2, 2(x) = P2(x)/Q2(x) = (P0 + P1x + P2x2)/(1 + Q1x + Q2x2)

 

We want ƒ(x) QN(x) - PN(x) = 0

(1  x/2 + x2/3 -…)(1 + Q1x + Q2x2) - (P0+P1x + x2) = 0

 

1-x/2  + x^2 /3 - x^3 /4 +…

Qx  -Q/2 x^2  + Q/3x^3 - …

 

-P0 - P1x P2 x^2 = 0

1 - P0 = 0

-1/2 + Q1 - P1 = 0

1/3 - Q1/2 + Q2 - P2= 0

-1/4 + Q1/3 - Q2/2 = 0

1/5 - Q1/4 + Q2/3 = 0

P2 = 1/30

P1 = 7/10

P0 = 1

Q1 = 6/5

Q2 = 3/10

 

R2,2(x) = (1 + 7/10x + 1/30 x2)/(1 + 6/5x + 3/10 x2)

For x = 1     (ln(1+x))/x = .6931

R2, 2 = .6933

Given the approximation for ln(1+x)/x obtain an approximation for ln(1+x)

(ln(1+x))/x  = R2,2(x)

ln(1+x) = x  R2,2(x) = x.((1+7/10x+1/30 x2)/(1+6/5x+3/10x2))

                              = (30x+21x2+x3)/(36+36x+9x2)