Questions tagged [interpolation]

Interpolation is the process of estimating the values of a function, when the function's values are known only at a particular set of points. Questions on interpolation in one or more dimensions, as well as algorithms for doing so, should have this tag.

Filter by
Sorted by
Tagged with
27
votes
1answer
25k views

What is the preferred and efficient approach for interpolating multidimensional data?

What is the preferred and efficient approach for interpolating multidimensional data? Things I'm worried about: performance and memory for construction, single/batch evaluation handling dimensions ...
25
votes
5answers
2k views

Why do equi-spaced points behave badly?

Experiment description: In Lagrange interpolation, the exact equation is sampled at $N$ points (polynomial order $N - 1$) and it is interpolated at 101 points. Here $N$ is varied from 2 to 64. Each ...
20
votes
4answers
5k views

What is the best way to find discontinuities of a black-box function?

It was suggested that this might be a better place for this question than Mathematics Stack Exchange where I asked it before. Suppose one has a black-box function which can be evaluated anywhere (...
16
votes
6answers
2k views

Example of a continuous function that is difficult to approximate with polynomials

For teaching purposes I'd need a continuous function of a single variable that is "difficult" to approximate with polynomials, i.e. one would need very high powers in a power series to "fit" this ...
13
votes
4answers
6k views

Efficient interpolation method for unstructured grids?

I would like to know a good method for interpolating data between two unstructured grids, where one grid is a coarser version of the other. Efficiency is very important to me since I'm solving a ...
11
votes
2answers
2k views

How to interpolate multipoint data to the cell centres of an unstructured mesh?

I have sets of multipoint field data, each point data set relates to a single cell of an unstructured mesh. The goal is to interpolate the data to the cell centre, directly or indirectly, in the most ...
11
votes
1answer
198 views

Implications of thermodynamic inconsistency in CFD calculations

During my PhD work, I had to use tabulated values of thermodynamic properties of gases in some Computational Fluid Dynamics (CFD in short) simulations. My tables are discretized in temperature and ...
10
votes
2answers
3k views

Do RBF kernel matrices tend to be ill-conditioned?

I use RBF kernel function to implement one kernel based machine learning algorithm(KLPP), the resulting kernel matrix $K$ $$K(i,j)= \exp\left({\frac{-(x_{i}-x_{j})^2}{ \sigma_{m}^2}}\right)$$ is ...
9
votes
4answers
2k views

When we use Bernstein polynomials in application

When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", "Simple ...
9
votes
1answer
2k views

Fast (approximate) evaluation of Chebyshev polynomial

Is there a preferred way how to implement a fast (approximate) evaluation of the Chebyshev interpolation polynomial on uniform grid (given the function values at the Chebyshev nodes)? My problem is ...
9
votes
2answers
2k views

Help deciding between cubic and quadratic interpolation in line search

I'm performing a line search as part of a quasi-Newton BFGS algorithm. In one step of the line search I use a cubic interpolation to move closer to the local minimizer. Let $f : R \rightarrow R, f \...
9
votes
1answer
1k views

What is the most accurate interpolation method for a 3D-flowfield on a structured grid?

I solve multi-species, compressible Navier-Stokes equations on a 3D structured grid. I have obtained a solution on a given grid (let's say a relatively coarse one). I want now to refine my grid and ...
8
votes
4answers
4k views

High Order derivatives of splines using SciPy

I have created a spline to fit my data in python using: spline=scipy.interpolate.UnivariateSpline(energy, fpp, k=4) The equation I want to use involves a ...
8
votes
5answers
266 views

Polynomial interpolation on a regular hexagon

Background We know a function $f$ on the vertices of a regular hexagon, as follows $$\left( 1, \ 0, \ f_{0}\right), \ \left( \frac{1}{2}, \ \frac{\sqrt{3}}{2}, \ f_{1}\right), \ \left( - \frac{1}...
8
votes
1answer
190 views

What are these oscillations?

I have a function $g(x)$ defined numerically that is sort of in between a Gaussian and a Lorentzian. It decays much slower than a Gaussian, but still faster than a simple inverse power. I need to ...
7
votes
5answers
9k views

Interpolate 2D data

I generated a cartesian grid in Python using NumPy's linspace and meshgrid, and I obtained some data over this 2D grid from an ...
7
votes
2answers
3k views

Intermediate values (interpolation) after Runge-Kutta calculation

I have a numerical ODE simulation that I computed at fixed time step $h$ using a 4-th order Runge-Kutta method (RK4), producing a series of results $(x_1,y_1), (x_2,...
7
votes
3answers
170 views

Evaluating an integral numerically at many points

Given a real function $f$, how can one efficiently evaluate $\int_0^{a_i}f(x)dx$ for millions of different $a_i$? Applying a standard quadrature method (such as Simpson's rule or Gaussian quadrature) ...
6
votes
2answers
11k views

Linear interpolation in Fortran

Is there a Fortran subroutine which performs linear interpolation in one-dimenional data? I need something similar to MATLAB function interp1.
6
votes
2answers
4k views

Is there a Gauss-Laguerre integration routine in Python?

I am reading the book "Numerical Recipes in Fortran 77: The Art of Scientific Computing" (Second Edition) and I came across some methods for numerical integration of 1D functions. More specifically ...
6
votes
2answers
5k views

Piecewise polynomial interpolation: Hermite vs Lagrange

I am a bit confused of the qualitative behavior of the two methods. Consider quadratic case, start by having points $x_i$, where I know the value and points $y_j$, where the values to be found. If I ...
6
votes
1answer
230 views

interpolation combined with methods of characteristics can cause oscillations for the transport equation?

I would like to know about the effect of using a higher order interpolator for the methods of characteristics. I am solving $$u_t+a(x,t)u_x=0$$ with some nonsmooth initial data $u_0(x)$ by the method ...
6
votes
2answers
235 views

Continuation procedure to solve for a 2D curve that satisfies f(x,y) = 0

I have some function of $R^2$, that must be numerically computed. For instance, I might be interested in a real-valued contour integral that begins from (x,y) = 0. $$ f(x,y) = \Re\left[\int_0^{x + iy}...
6
votes
1answer
203 views

What spline functions are used in Section 13.9 of "Numerical Recipes in C"?

I asked a similar question on MathSE but with more added fluff, but didn't really get any straight answers, so I figured I'd ask here. Computing Fourier coefficients of a function using the FFT is ...
6
votes
1answer
1k views

Grid mapping from an unstructured triangular mesh to a regular rectangular mesh

I am modeling fracture propagation using a 2-D dynamic unstructured grid. As the fracture propagates over time, the elements move accordingly. For a given time step, I would like to interpolate the ...
6
votes
2answers
5k views

Fortran, making a more efficient bilinear interpolation

I'm trying to write an efficient bilinear (2D)-interpolation, after reading some recipes, as a fortran-mex for Matlab that is used extensively throughout a long algorithm of solar image processing, ...
6
votes
1answer
210 views

What is the most efficient approach to interpolate values between two FEM meshes in 2D?

I am looking for efficient algorithm to interpolate values from one unstructured 2D mesh grid to another. Both grids are constructed using the same type of elements (triangles or quadrilaterals). Both ...
6
votes
1answer
390 views

Full Multigrid Prolongation Operator

I am looking into full multigrid, FMG, and several sources, including these slides, that a lot of people are referring to, state that the prolongation operator used in FMG the first time you visit a ...
6
votes
0answers
272 views

Integrating highly oscillatory functions

I have a logarithmic grid, upon which i have two functions that are similar to this one (this is only the last 100 points): These are essentially very similar to a Sin function at this point. I need ...
5
votes
2answers
1k views

Interpolation by Solving a Minimization Problem (Optimization)

I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - $M \times N$ Matrix). Someone marks some pixels as anchors. Now, you need to ...
5
votes
1answer
983 views

restriction and interpolation in multigrid method

I need detailed explanation of the formula below A2=I1*A1*I2 I suppose this formula computes matrix A2 on a coarse grid and here A1 is original matrix on fine ...
5
votes
1answer
3k views

Approximating a step function with polynomials

The Weierstrass approximation theorem says any continuous function $f(x): [0,1] \to \mathbb{R}$ can be approximated uniformly by polynomials. Given any $\epsilon$, we can find $p(x) = x^n + \dots $ ...
5
votes
2answers
648 views

Interpolation schemes to move data between cells and nodes

I work on non-graded quadtree grids where the entire grid is a hierarchy of cells specified using a quadtree data structure, where, in general, there is no constraint regarding the relative size of ...
5
votes
2answers
8k views

SciPy interpolation with Univariate Splines

I have coded a routine for interpolation with B-splines, only to discover later that this functionality is already included in Python's SciPy. However, I do not understand one parameter in the SciPy ...
5
votes
3answers
163 views

Automatic finite differences

Given numbers $x, y \in \mathbb{R}$ where $$\frac{|y-x|}{|x|}$$ is small, and code that implements the function $f$ with a sequence of arithmetic operations, I would like to compute to high accuracy ...
5
votes
2answers
2k views

Minimal surface solution in Python

Note: this question was also posted in StackOverflow and math.stackexchange. I have a set of 3D points defining a 3D contour, as shown below. The points in this contour lie in their best-fit plane ...
5
votes
2answers
178 views

Polynomial approximation spaces

I often see people using products of 1-D polynomials to do interpolation or projection of smooth multivariate functions over grids or cells because it is intuitive and simple to implement. What are ...
5
votes
2answers
198 views

Computing inverse functions of functions of two variables

There are several functions of two or three variables that I am working with. For this question I have made a small set showing the resistivity, $\rho$, in n$\Omega$m, of copper as a function of its ...
5
votes
1answer
193 views

Adaptive Table Lookup for Expensive Function Evaluation

I have a function that is expensive to evaluate whose inputs are n-dimensional (n is the order of a dozen or two). I need the output of this function at each node and each time step for a PDE ...
5
votes
0answers
686 views

Cressman interpolation and objective analysis

I have read this question and answer – Interpolation of scattered data to a regular grid in python and I am doing something similar as I have temperature values of the atmosphere at different heights ...
5
votes
0answers
74 views

Automatic differentiation of barycentric rational functions

By a barycentric rational interpolant we understand a function of the form \begin{align*} r(t) := \frac{\sum_{i=0}^{n-1} \frac{w_i y_i}{t-t_i} }{ \sum_{i=0}^{n-1} \frac{w_i}{t-t_i}} \end{align*} In ...
5
votes
0answers
67 views

Padua-type pointset for functions singular on line $x=y$

The Padua points $\mathrm{Pad}_{n} \subset [-1,1]^{2}$ are a unisolvent pointset with optimal growth of Lebesgue constant, described in detail here. With some work they can be used to generate a ...
5
votes
0answers
173 views

How to optimally choose points for multivariable Hermite interpolation?

I have a multi-variate, continuous function $f$ from $R^n$ to $R$, which I can query for its output for any input. I would like to create interpolation polynomial for it. In one-dimensional case ...
5
votes
0answers
87 views

How do I perform chebyshev interpolation from a to b with custom angle range?

Typically Chebyshev interpolation from $-1$ to $1$ with angle from $0$ to $\pi$: $\xi_j=\cos \left ({\pi j \over N}\right )$ $x_j=(1+\xi_j) * {L \over 2}$ $w$: $w_0=\pi/(2N)$ $w_{1,...,N-1}=\pi/(N)$...
4
votes
2answers
162 views

What is the difference between $u_h$ and $I_h(u)$ in finite element literature?

In finite element books, we have estimates for $$||u-u_h||$$ and also estimates for $$||u - I_h(u)||$$ where $I_h(u): V \mapsto V_h$ projects a function from the infinite dimensional space to the ...
4
votes
2answers
155 views

Interpolate the orbital coordinates of an object using coordinates and velocities vector

I have a table of the orbital coordinates and velocities of an object with time steps of 1 minute. Now I would like to interpolate this to a finer time increments with time steps of the order of 1 ...
4
votes
1answer
467 views

Interpolating a mathematical function using a Hermite Cubic Finite Element Space

I have a Hermite Cubic Finite Element Space on a computer in the form of Matlab m-files. More specifically, I can evaluate four "shape functions" $N_1, N_2, N_3,$ and $N_4$, for which the following ...
4
votes
2answers
422 views

Interpolation with the roots of orthogonal polynomials & Spectral expansion

I'm a bit confused about the relationships between these two approximation methods mentioned in the title. Does this kind of interpolation also belongs to the field of spectral methods? Are the ...
4
votes
1answer
1k views

Generating harmonic polynomials in cartesian coordinates

TLDR: Are these polynomials really harmonic polynomials, and how can I generate them? Long version: I want to describe an electrostatic potential $\Phi(x,y,z)$ over a source-free volume, by using a ...
4
votes
2answers
1k views

Interpolating irregular data on a sphere

I am trying to interpolate irregular data $f(\theta, \phi)$ on a sphere and I have so far tried a scipy approach using Kd-Trees and inverse distance weighting, which works ok - however I was wondering ...