Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 1K views

    Python 3 PDF

    Uploaded by

    Abhijit Kar Gupta
    The document discusses finite differences and Newton's formula for polynomial interpolation. It explains that finite differences are calculated from a set of equally spaced data points to estimate the value of an unknown function between points. Newton's formula uses forward finite differences to determine the coefficients of a polynomial that passes through the given data points, allowing interpolation of the function value at intermediate points. The key steps are: 1) calculate forward differences of the y-coordinates up to the desired polynomial degree, 2) determine the coefficients by setting the polynomial equal to the y-values at each x-point, and 3) interpolate the function value for any x-value by substituting into the polynomial formula.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Python 3 PDF

    Uploaded by

    Abhijit Kar Gupta
    1K views4 pages
    The document discusses finite differences and Newton's formula for polynomial interpolation. It explains that finite differences are calculated from a set of equally spaced data points to estimate the value of an unknown function between points. Newton's formula uses forward finite differences to determine the coefficients of a polynomial that passes through the given data points, allowing interpolation of the function value at intermediate points. The key steps are: 1) calculate forward differences of the y-coordinates up to the desired polynomial degree, 2) determine the coefficients by setting the polynomial equal to the y-values at each x-point, and 3) interpolate the function value for any x-value by substituting into the polynomial formula.

    Original Title

    Python 3.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses finite differences and Newton's formula for polynomial interpolation. It explains that finite differences are calculated from a set of equally spaced data points to estimate the value of an unknown function between points. Newton's formula uses forward finite differences to determine the coefficients of a polynomial that passes through the given data points, allowing interpolation of the function value at intermediate points. The key steps are: 1) calculate forward differences of the y-coordinates up to the desired polynomial degree, 2) determine the coefficients by setting the polynomial equal to the y-values at each x-point, and 3) interpolate the function value for any x-value by substituting into the polynomial formula.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    1K views4 pages

    Python 3 PDF

    Uploaded by

    Abhijit Kar Gupta
    The document discusses finite differences and Newton's formula for polynomial interpolation. It explains that finite differences are calculated from a set of equally spaced data points to estimate the value of an unknown function between points. Newton's formula uses forward finite differences to determine the coefficients of a polynomial that passes through the given data points, allowing interpolation of the function value at intermediate points. The key steps are: 1) calculate forward differences of the y-coordinates up to the desired polynomial degree, 2) determine the coefficients by setting the polynomial equal to the y-values at each x-point, and 3) interpolate the function value for any x-value by substituting into the polynomial formula.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    1

    FINITE DIFFERENCES:

    Suppose, we are given a set of values: ( ), ( ), ( ), ( )( ) and the


    values of are equally spaced: , . The values, in some interval,
    represent some function ( ) of which either we do not know or the function is very
    complicated. Now we want to estimate the value of ( ), for some intermediate value of
    [ in the range: ].

    To proceed, we calculate the differences of the -coordinates in the following ways:

    Forward Differences

    If , , .. are the values of , then, ( ), ( ),. ( ) are the


    successive differences between neighbouring -values.

    We denote differences in the following way:

    , ,

    We can think the symbol as a forward difference operator and , .etc. are called the
    first forward differences.

    The differences between the first forward differences are called second forward differences
    and so on.

    The second, third and successive higher order differences can be calculated easily.

    ( ) ( ) ( ) ,

    Similarly,

    ( ) ( ) ( )

    ( ) ( )

    Similarly, other differences of any order can be calculated in a straight forward way.

    Note:
    We can think of a shift operator defined by the following way:
    for any .

    So,
    2

    ( ) , and so on.

    In general, .

    Let us now think of the difference,

    ( )

    Thus we can think,

    Now with this, we can easily calculate the higher order differences.

    For example,

    ( ) ( )

    The following table demonstrates how different forward differences are computed:

    Table for Forward Differences

    Interpolation:

    As the explicit nature of the function ( ) is not known, the relation is approximated by a
    simple function ( ) so that the original ( ) [not known] and the approximated function
    ( ) agree at the set of given points ( ). This is called interpolation. If the interpolating
    function is a polynomial of some degree then it is called polynomial interpolation. There are
    3

    other kinds of interpolations like trigonometric interpolation etc., depending on what kind of
    function is used for interpolation.

    We can calculate the errors in polynomial and other kinds of interpolations. We will discuss this
    later.

    Newtons Formula for Interpolation:


    [This is also called Gregory-Newton Interpolation.]

    Newtons interpolation is done through a simple polynomial of degree for a set of ( )


    equidistant data points: ( ), ( ), ( ),.( ).

    Consider, , .

    The polynomial function of n-th degree, which passes through the given data points, can be
    written as

    ( ) ( ) ( )( ) ( )( )( ) (1)

    Since the above function will pass through the data points, by putting them we can determine
    the coefficients.

    So we obtain

    ( )

    ( )( )

    Similarly,

    In general, .

    To obtain the expression of the polynomial function for any arbitrary value , we set
    so that .

    Also, we put the values of , , .in (1), we get


    4

    ( )
    ( ) ( )( ) ( )( ) ( )
    (2)

    #Interpolation by Newton's Forward Difference Formula


    #Program by: A. Kar Gupta, email: kg.abhi@gmail.com
    #----------------------------------------------------

    x=[0,1,2,3] #x-coordinates as List


    y=[1,0,1,10] #y-coordinates as List
    d=[] #Empty List for differences
    h=1.0
    t=(4-x[0])/h #Conversion of variable for x=4
    coeff=t
    sum=y[0]
    k=1
    for i in range(len(y),1,-1):
    for j in range(i-1):
    diff=y[j+1]-y[j]
    d.append(diff) # Appended to difference List
    sum=sum+coeff*d[0]
    coeff=coeff*(t-k)/(k+1) # Updating the Coeff
    k=k+1
    y=d
    d=[] # Emptying the list for next round
    print 'Interpolated Value = ', sum

    You might also like