Aim: This class implements Lagrange basis functions and Lagrange interpolation. More...

#include <DGtal/math/LagrangeInterpolation.h>

Public Types
typedef LagrangeInterpolation< TEuclideanRing >	Self

typedef TEuclideanRing	Ring

typedef DGtal::MPolynomial< 1, Ring >	Polynomial
	The monovariate polynomial type. More...

typedef std::size_t	Size

Public Member Functions
	BOOST_CONCEPT_ASSERT ((concepts::CEuclideanRing< Ring >))

	~LagrangeInterpolation ()=default

	LagrangeInterpolation ()

	LagrangeInterpolation (const std::vector< Ring > &xvalues)

	LagrangeInterpolation (const LagrangeInterpolation &other)=default

	LagrangeInterpolation (LagrangeInterpolation &&other)=default

LagrangeInterpolation &	operator= (const LagrangeInterpolation &other)=default

LagrangeInterpolation &	operator= (LagrangeInterpolation &&other)=default

Size	size () const

Size	degree () const

Ring	denominator () const

void	init (const std::vector< Ring > &xvalues)

Polynomial	polynomial (const std::vector< Ring > &yvalues)

Polynomial	basis (Size i) const

void	selfDisplay (std::ostream &that_stream) const

bool	OK () const

Protected Attributes
std::vector< Ring >	myX
	The vector of X-values (abscissa) More...

Ring	myDeterminant
	The determinant of the Vandermonde matrix corresponding to X-values. More...

std::vector< Polynomial >	myLagrangeBasis
	The Lagrange polynomial basis corresponding to X-values. More...

Detailed Description

template<typename TEuclideanRing>
class DGtal::LagrangeInterpolation< TEuclideanRing >

Aim: This class implements Lagrange basis functions and Lagrange interpolation.

Description of class 'LagrangeInterpolation'

See also: testLagrangeInterpolation.cpp

Template Parameters

TEuclideanRing any model of CEuclideanRing like int, double, etc.

Definition at line 62 of file LagrangeInterpolation.h.

Member Typedef Documentation

◆ Polynomial

template<typename TEuclideanRing >

typedef DGtal::MPolynomial< 1, Ring > DGtal::LagrangeInterpolation< TEuclideanRing >::Polynomial

The monovariate polynomial type.

Definition at line 72 of file LagrangeInterpolation.h.

◆ Ring

template<typename TEuclideanRing >

typedef TEuclideanRing DGtal::LagrangeInterpolation< TEuclideanRing >::Ring

Definition at line 68 of file LagrangeInterpolation.h.

◆ Self

template<typename TEuclideanRing >

typedef LagrangeInterpolation< TEuclideanRing > DGtal::LagrangeInterpolation< TEuclideanRing >::Self

Definition at line 67 of file LagrangeInterpolation.h.

◆ Size

template<typename TEuclideanRing >

typedef std::size_t DGtal::LagrangeInterpolation< TEuclideanRing >::Size

Definition at line 73 of file LagrangeInterpolation.h.

Constructor & Destructor Documentation

◆ ~LagrangeInterpolation()

template<typename TEuclideanRing >

DGtal::LagrangeInterpolation< TEuclideanRing >::~LagrangeInterpolation ( )

default

Destructor.

◆ LagrangeInterpolation() [1/4]

template<typename TEuclideanRing >

DGtal::LagrangeInterpolation< TEuclideanRing >::LagrangeInterpolation ( )

inline

Constructor. The object is invalid.

Definition at line 86 of file LagrangeInterpolation.h.

87 : myDeterminant( NumberTraits< Ring >::ZERO )

88 {}

DGtal::LagrangeInterpolation::myDeterminant

Ring myDeterminant

The determinant of the Vandermonde matrix corresponding to X-values.

Definition: LagrangeInterpolation.h:235

DGtal::NumberTraitsImpl< std::decay< T >::type >::ZERO

static const std::decay< T >::type ZERO

Constant Zero.

Definition: NumberTraits.h:100

◆ LagrangeInterpolation() [2/4]

template<typename TEuclideanRing >

DGtal::LagrangeInterpolation< TEuclideanRing >::LagrangeInterpolation ( const std::vector< Ring > & xvalues )

inline

Constructs the Lagrange interpolation object with its x-values

Parameters

xvalues the vector of X-values, corresponding to the abscissa where the interpolation will take place.

Definition at line 94 of file LagrangeInterpolation.h.

    {
      init( xvalues );
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::init().

◆ LagrangeInterpolation() [3/4]

template<typename TEuclideanRing >

DGtal::LagrangeInterpolation< TEuclideanRing >::LagrangeInterpolation ( const LagrangeInterpolation< TEuclideanRing > & other )

default

Copy constructor.

Parameters

other the object to clone.

◆ LagrangeInterpolation() [4/4]

template<typename TEuclideanRing >

DGtal::LagrangeInterpolation< TEuclideanRing >::LagrangeInterpolation ( LagrangeInterpolation< TEuclideanRing > && other )

default

Move constructor.

Parameters

other the object to clone.

Member Function Documentation

◆ basis()

template<typename TEuclideanRing >

Polynomial DGtal::LagrangeInterpolation< TEuclideanRing >::basis ( Size i ) const

inline

Parameters

i	any value between 0 included and `size()` excluded.

Returns: the numerator of i-th Lagrange basis polynomial (divide by denominator to get the exact Lagrange basis polynomial).

Definition at line 199 of file LagrangeInterpolation.h.

    {
      ASSERT( 0 <= i && i < size() );
      return myLagrangeBasis[ i ];
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::myLagrangeBasis, and DGtal::LagrangeInterpolation< TEuclideanRing >::size().

Referenced by DGtal::LagrangeInterpolation< TEuclideanRing >::selfDisplay().

◆ BOOST_CONCEPT_ASSERT()

template<typename TEuclideanRing >

DGtal::LagrangeInterpolation< TEuclideanRing >::BOOST_CONCEPT_ASSERT ( (concepts::CEuclideanRing< Ring >) )

◆ degree()

template<typename TEuclideanRing >

Size DGtal::LagrangeInterpolation< TEuclideanRing >::degree ( ) const

inline

Returns: the degree of Lagrange polynomials (i.e. size()-1)

Definition at line 132 of file LagrangeInterpolation.h.

    {
      return size() - 1;
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::size().

◆ denominator()

template<typename TEuclideanRing >

Ring DGtal::LagrangeInterpolation< TEuclideanRing >::denominator ( ) const

inline

Returns: the common denominator to Lagrange bases and Lagrange polynomial.

Definition at line 138 of file LagrangeInterpolation.h.

    {
      return myDeterminant;
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::myDeterminant.

Referenced by DGtal::EhrhartPolynomial< TSpace, TInteger >::init().

◆ init()

template<typename TEuclideanRing >

void DGtal::LagrangeInterpolation< TEuclideanRing >::init ( const std::vector< Ring > & xvalues )

inline

Initializes the Lagrange interpolation object with its x-values, and computes the corresponding Lagrange Basis.

Parameters

xvalues the vector of X-values, corresponding to the abscissa where the interpolation will take place.

Definition at line 148 of file LagrangeInterpolation.h.

    {
      myX           = xvalues;
      // Compute Vandermonde determinant
      myDeterminant = NumberTraits< Ring >::ONE;
      for ( Dimension i = 0; (i+1) < size(); ++i )
        for ( Dimension j = i + 1; j < size(); ++j )
          myDeterminant *= myX[ j ] - myX[ i ];
      // compute Lagrange polynomial basis.
      myLagrangeBasis.clear();
      myLagrangeBasis.reserve( size() );
      for ( Dimension j = 0; j < size(); ++j )
        {
          Ring c = myDeterminant;
          for ( Dimension m = 0; m < size(); ++m )
            if ( m != j ) 
              c /= myX[ j ] - myX[ m ];
          Polynomial P = c; // constant
          for ( Dimension m = 0; m < size(); ++m )
            if ( m != j ) 
              P *= mmonomial<Ring>( 1 ) - myX[ m ] * mmonomial<Ring>( 0 );
          myLagrangeBasis.push_back( P );
        }
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::myDeterminant, DGtal::LagrangeInterpolation< TEuclideanRing >::myLagrangeBasis, DGtal::LagrangeInterpolation< TEuclideanRing >::myX, and DGtal::LagrangeInterpolation< TEuclideanRing >::size().

Referenced by DGtal::LagrangeInterpolation< TEuclideanRing >::LagrangeInterpolation().

◆ OK()

template<typename TEuclideanRing >

bool DGtal::LagrangeInterpolation< TEuclideanRing >::OK ( ) const

inline

Checks the validity/consistency of the object.

Returns: 'true' if the object is valid, 'false' otherwise.

Definition at line 224 of file LagrangeInterpolation.h.

    {
      return myDeterminant != NumberTraits< Ring >::ZERO;
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::myDeterminant.

◆ operator=() [1/2]

template<typename TEuclideanRing >

LagrangeInterpolation & DGtal::LagrangeInterpolation< TEuclideanRing >::operator= ( const LagrangeInterpolation< TEuclideanRing > & other )

default

Assignment.

Parameters

other the object to copy.

Returns: a reference on 'this'.

◆ operator=() [2/2]

template<typename TEuclideanRing >

LagrangeInterpolation & DGtal::LagrangeInterpolation< TEuclideanRing >::operator= ( LagrangeInterpolation< TEuclideanRing > && other )

default

Move assignment.

Parameters

other the object to move.

Returns: a reference on 'this'.

◆ polynomial()

template<typename TEuclideanRing >

Polynomial DGtal::LagrangeInterpolation< TEuclideanRing >::polynomial ( const std::vector< Ring > & yvalues )

inline

Parameters

[in] yvalues the y-values corresponding to the current x-values, in the same order.

Returns: the numerator of the Lagrange polynomial that interpolates all given values (divide by denominator to get the exact Lagrange polynomial).

Note: if yvalues has not the correct size, then the zero polynomial is returned.

Definition at line 182 of file LagrangeInterpolation.h.

    {
      Polynomial P;
      if ( yvalues.size() != size() ) return P;
      for ( Dimension j = 0; j < size(); ++j )
        P += yvalues[ j ] * myLagrangeBasis[ j ];
      return P;
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::myLagrangeBasis, and DGtal::LagrangeInterpolation< TEuclideanRing >::size().

Referenced by DGtal::EhrhartPolynomial< TSpace, TInteger >::init().

◆ selfDisplay()

template<typename TEuclideanRing >

void DGtal::LagrangeInterpolation< TEuclideanRing >::selfDisplay ( std::ostream & that_stream ) const

inline

Writes/Displays the object on an output stream.

Parameters

that_stream the output stream where the object is written.

Definition at line 212 of file LagrangeInterpolation.h.

    {
      that_stream << "[LagrangeInterpolation det=" << myDeterminant << std::endl;
      for ( Size i = 0; i < size(); i++ )
        that_stream << "l_" << i << "=" << basis( i ) << std::endl;
      that_stream << "]";
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::basis(), DGtal::LagrangeInterpolation< TEuclideanRing >::myDeterminant, and DGtal::LagrangeInterpolation< TEuclideanRing >::size().

Referenced by DGtal::operator<<().

◆ size()

template<typename TEuclideanRing >

Size DGtal::LagrangeInterpolation< TEuclideanRing >::size ( ) const

inline

Returns: the number of interpolation points (or number of x-values)

Definition at line 126 of file LagrangeInterpolation.h.

    {
      return myX.size();
    }

References DGtal::LagrangeInterpolation< TEuclideanRing >::myX.

Referenced by DGtal::LagrangeInterpolation< TEuclideanRing >::basis(), DGtal::LagrangeInterpolation< TEuclideanRing >::degree(), DGtal::LagrangeInterpolation< TEuclideanRing >::init(), DGtal::LagrangeInterpolation< TEuclideanRing >::polynomial(), and DGtal::LagrangeInterpolation< TEuclideanRing >::selfDisplay().

Field Documentation

◆ myDeterminant

template<typename TEuclideanRing >

Ring DGtal::LagrangeInterpolation< TEuclideanRing >::myDeterminant

protected

The determinant of the Vandermonde matrix corresponding to X-values.

Definition at line 235 of file LagrangeInterpolation.h.

Referenced by DGtal::LagrangeInterpolation< TEuclideanRing >::denominator(), DGtal::LagrangeInterpolation< TEuclideanRing >::init(), DGtal::LagrangeInterpolation< TEuclideanRing >::OK(), and DGtal::LagrangeInterpolation< TEuclideanRing >::selfDisplay().

◆ myLagrangeBasis

template<typename TEuclideanRing >

std::vector<Polynomial> DGtal::LagrangeInterpolation< TEuclideanRing >::myLagrangeBasis

protected

The Lagrange polynomial basis corresponding to X-values.

Definition at line 237 of file LagrangeInterpolation.h.

Referenced by DGtal::LagrangeInterpolation< TEuclideanRing >::basis(), DGtal::LagrangeInterpolation< TEuclideanRing >::init(), and DGtal::LagrangeInterpolation< TEuclideanRing >::polynomial().

◆ myX

template<typename TEuclideanRing >

std::vector< Ring > DGtal::LagrangeInterpolation< TEuclideanRing >::myX

protected

The vector of X-values (abscissa)

Definition at line 233 of file LagrangeInterpolation.h.

Referenced by DGtal::LagrangeInterpolation< TEuclideanRing >::init(), and DGtal::LagrangeInterpolation< TEuclideanRing >::size().

The documentation for this class was generated from the following file:

LagrangeInterpolation.h

Public Types

Public Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Polynomial

◆ Ring

◆ Self

◆ Size

Constructor & Destructor Documentation

◆ ~LagrangeInterpolation()

◆ LagrangeInterpolation() [1/4]

◆ LagrangeInterpolation() [2/4]

◆ LagrangeInterpolation() [3/4]

◆ LagrangeInterpolation() [4/4]

Member Function Documentation

◆ basis()

◆ BOOST_CONCEPT_ASSERT()

◆ degree()

◆ denominator()

◆ init()

◆ OK()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ polynomial()

◆ selfDisplay()

◆ size()

Field Documentation

◆ myDeterminant

◆ myLagrangeBasis

◆ myX