Questions tagged [interpolation]

Questions on interpolation, the estimation of the value of a function from given input, based on the values of the function at known points. It is necessary because in science and engineering we often need to deal with discrete experimental data.

Filter by
Sorted by
Tagged with
35
votes
1answer
736 views

Are my results new? [closed]

I'm eighteen and sometimes I like doing math on my own when I'm inspired. I would like to know if some of my "discoveries" are new (I don't think so :) ). These are some of the results I found in the ...
24
votes
1answer
25k views

What is the difference between natural cubic spline, Hermite spline, Bézier spline and B-spline?

I am reading a book about computer graphics. It is confusing about the various splines and their algorithms. What is the difference between natural cubic spline, Hermite spline, Bézier spline and B-...
15
votes
4answers
7k views

Polynomial fitting where polynomial must be monotonically increasing

Given a set of monotonically increasing data points (in 2D), I want to fit a polynomial to the data which is monotonically increasing over the domain of the data. If the highest x value is 100, I don'...
13
votes
2answers
608 views

General method to “naturally interpolate” to a complex map?

Given a region of the complex plane and a map $z \to f(z)$, is there a general way to "naturally interpolate" the point $z$ to $f(z)$ in such a way that the movement follows a "natural" smooth path ...
12
votes
2answers
225 views

Generalization of $\frac{x^n - y^n}{x - y} = x^{n - 1} + yx^{n - 2} + \ldots + y^{n - 1}$

I thought about a generalization for the formula $$\frac{x^n - y^n}{x - y} = x^{n - 1} + yx^{n - 2} + \ldots + y^{n - 1}$$ It can be written as $$\frac{x^n - y^n}{x - y} = x^{n - 1} + yx^{n - 2} + \...
12
votes
1answer
589 views

Interpolating the primorial $p_{n}\#$

The primorial $p_{n}\#$ is given by the product $p_n\# = \prod_{k=1}^n p_k$ (where $p_{k}$ is the $k$th prime) -- is there a natural (a la the gamma function $\Gamma(z)$) way of interpolating it for ...
12
votes
3answers
67k views

Newton's Interpolation Formula: Difference between the forward and the backward formula

I was taught that the forward formula should be used when calculating the value of a point near $x_0$ and the backward one when calculating near $x_n$. However, the interpolation polynomial is unique, ...
11
votes
2answers
27k views

How to calculate interpolating splines in 3D space?

I'm trying to model a smooth path between several control points in three dimensions, the problem is that there doesn't appear to be an explanation on how to use splines to achieve this. Are splines a ...
11
votes
2answers
4k views

Hardy–Littlewood-Sobolev inequality without Marcinkiewicz interpolation?

Here is the statement of the Hardy–Littlewood–Sobolev theorem. Let $0< \alpha< n$, $1 < p < q < \infty$ and $\frac{1}{q}=\frac{1}{p}-\frac{\alpha}{n}$. Then: $$ \left \| \int_{\mathbb{...
11
votes
1answer
430 views

Weighting a cubic hermite spline

I am trying to figure out a function behind the software's curve drawing algorithm. Originally, each node comes with 3 parameters : time, value, and tangent. I have found that it fits cubic Hermite ...
11
votes
3answers
1k views

Accurate floating-point linear interpolation

I want to perform a simple linear interpolation between $A$ and $B$ (which are binary floating-point values) using floating-point math with IEEE-754 round-to-nearest-or-even rounding rules, as ...
10
votes
1answer
10k views

Spatial Interpolation for Irregular Grid

How would I interpolate to a point P if I have four points around it such that: Q1 = (x1,y1), Q2 = (x2,y2), Q3 = (x3,y3), Q4 = (x4,y4) If the coordinates formed a regular 2D grid I would use a ...
10
votes
3answers
594 views

A Curious Binomial Sum Identity without Calculus of Finite Differences

Let $f$ be a polynomial of degree $m$ in $t$. The following curious identity holds for $n \geq m$, \begin{align} \binom{t}{n+1} \sum_{j = 0}^{n} (-1)^{j} \binom{n}{j} \frac{f(j)}{t - j} = (-1)^{n} \...
10
votes
1answer
1k views

Cauchy Integral Formula for Matrices

How do I evaluate the Cauchy Integral Formula $f(A)=\frac{1}{2\pi i}\int\limits_Cf(z)(zI-A)^{-1}dz$ for a matrix $A=\left(\begin{array}{ccc}2&2&-5\\3&7&-15\\1&2&-4\end{array}\...
10
votes
1answer
133 views

For a fixed degree, is there always a Lagrange polynomial below the original function?

Let $x_1<x_2< \ldots <x_n$ be $n$ real numbers, and let $y_1,y_2,\ldots,y_n$ be real values to be interpolated. Let $r\leq n$. For any $I\subseteq \lbrace 1,2,\ldots,n\rbrace$ of cardinality ...
9
votes
7answers
2k views

What is the pattern to this sequence?

$$0, 1, 3, 13, 51, 205$$ More specifically, $$(0,0)\quad(1,1)\quad (2,3)\quad (3,13) \quad(4,51)\quad (5,205)$$ I have tried using the interpolation feature in Grapher.app and Wolfram Alpha, but ...
9
votes
1answer
9k views

Implementation of Monotone Cubic Interpolation

I'm in need to implement Monotone Cubic Interpolation for interpolate a sequence of points. The information I have about the points are x,y and timestamp. I'm much more an IT guy rather than a ...
9
votes
4answers
21k views

Newton form vs. Lagrange form for interpolating polynomials

I'm just wondering, what are the advantages of using either the Newton form of polynomial interpolation or the Lagrange form over the other? It seems to me, that the computational cost of the two are ...
9
votes
1answer
5k views

Natural cubic splines vs. Piecewise Hermite Splines

Recently, I was reading about a "Natural Piecewise Hermite Spline" in Game Programming Gems 5 (under the Spline-Based Time Control for Animation). This particular spline is used for generating a C2 ...
9
votes
0answers
578 views

Discrete Fourier Transform: Shift by Fraction of a Sample

I use spectral Fourier methods to numerically solve PDEs and these methods make heavy use of the discrete Fourier transform (DFT). With respect to the DFT I have some issues understanding the discrete ...
9
votes
1answer
254 views

Could $4+2+4+2+4+2+\cdots = -1 $?

In physics classes, on this StackExchange and even in blogs the sum $1 + 2 + 3 + 4 + \cdots = - \frac{1}{12} $ has been under the microscope. Why does $1+2+3+\cdots = -\frac{1}{12}$? The Euler-...
9
votes
0answers
1k views

What is the maximum overshoot of interpolating splines in $d$ dimensions?

Consider cubic splines $s( x, y )$ which interpolate values $y = \{ y_0, y_1, \dots,y_n \}$, on the uniform grid $\{ 0, 1,\dots, n \}$. Fix $s''(0) = s''(n) = 0$ (natural splines). How big can $$\...
8
votes
3answers
2k views

Is it possible to have a rule which generates: 2, 4, 6, 8, 10, 12, 14, 16, -23?

This is on Lagrange Interpolations . . . Is it possible to have a rule which generates the sequence: 2, 4, 6, 8, 10, 12, 14, 16, -23? The hint that he gave us is to use Summation Products, the only ...
8
votes
2answers
5k views

Why is Lagrange interpolation numerically unstable?

Here is my understanding of the polynomial interpolation problem: Interpolating by inverting the Vandermonde matrix is unstable because the Vandermonde matrix is ill-conditioned, so "difficult" to ...
8
votes
4answers
583 views

Are there smooth analogs to polynomial splines

Is possible to construct infinitely differentiable functions that interpolate through arbitrary points, the way polynomial splines do? If so, do they have a name and is there an algorithm for ...
8
votes
2answers
2k views

$f(x)=1/(1+x^2)$. Lagrange polynomials do not always converge. why?

Let $f(x) = \frac{1}{1+x^2}$. Error of Interpolation with Lagrange polynomials for $n+1$ points is given by $$ e(x)=f(x)-P_n(x)=\frac{f^{(n+1)}(\eta_x)}{(n+1)!}\prod_{i=0}^n (x-x_i) $$ Carl Runge ...
8
votes
2answers
13k views

Evaluate derivative of Lagrange polynomials at construction points

Assume, that we have points $x_i$ with $i=1,...,N+1$. We construct the Lagrange basis polynomials as \begin{align} L_j(x) = \prod_{k\not = j} \frac{x-x_k}{x_j-x_k} \end{align} Now according to my ...
8
votes
1answer
133 views

Factorial-like function that behaves like $ 1\times \sqrt{2} \times \sqrt[3]{3} \times \dots \times \sqrt[n-1]{n-1} \times \sqrt[n]{n} $?

The Barnes G-function is a generalization of the factorial funcion which grows a lot faster. The factorial: $$ n! = 1 \times 2 \times 3 \times \dots \times (n-1) \times n $$ Then it is possible ...
8
votes
1answer
3k views

What is the math used in Excel's GROWTH function?

I am trying to implement Microsoft Excel's GROWTH function in JavaScript. This function calculates predicted exponential growth by using existing data. What makes it tricky is that it must work with ...
8
votes
3answers
3k views

Is there a generalization of the Lagrange polynomial to 3D?

What is a way to construct a smooth polynomial surface ($\mathbb{R}^2 \rightarrow \mathbb{R}$) with Lagrange-polynomial properties in every partial derivative? I want to try this for image ...
7
votes
3answers
624 views

Constructing a cubic given four points

Question: Is there an easier way to solve this problem? Suppose the polynomial $f(x)$ is of degree $3$ and satisfies $f(3)=2$, $f(4)=4$, $f(5)=-3$, and $f(6)=8$. Determine the value of $f(...
7
votes
2answers
188 views

Negative value of $\sqrt[3]{20}$

Given $f(x)=\sqrt[3] x$, find an approximation of $\sqrt[3]{20}$ using Lagrange interpolation method. $x_0=0$, $x_1=1$, $x_2=8$, $x_3=27$ and $x_4=64$ $f(x_0)=0$, $f(x_1)=1$, $f(x_2)=2$, $f(x_3)=3$...
7
votes
1answer
2k views

Lyapunov's Inequality for Weak-Lp Spaces

Let $(X,\mu)$ be a measure space. Suppose that $0 < p_{0} < p < p_{1} < \infty$ and $\frac{1}{p} = \frac{1-\theta}{p_{0}} + \frac{\theta}{p_{1}}$ for some $\theta \in (0,1)$. If $f \in L^{...
7
votes
1answer
572 views

Cubic Spline Interpolation math

I am writing a code snippet in Python to do an interpolation using cubic splines. I have first done the math, and then attempted to implement the pseudo code in Python. However, I think i might have ...
7
votes
3answers
869 views

Transform polygons into one another?

I am aware that there must be no standard way to achieve this, but I don't know what has been done so far. I feel like I'm missing keywords to investigate further. I have any two 2D polygons $a$ and $...
7
votes
2answers
230 views

Modified Hermite interpolation

I asked similar questions here and here, but I tried to formulate this one in a sharper way. Is anyone aware of some literature on polynomial interpolation where we sample the function and its ...
7
votes
0answers
792 views

Runge's phenomen: interpolation error using Chebyshev nodes oscillates

We're trying to approximate the Runge function $f(x) = \dfrac{1}{1+25x^2}$ using Chebyshev nodes. When calculating the interpolation error, using different degrees ranging from 0 to 50, we get the ...
7
votes
1answer
3k views

Interpolating point on a quad [closed]

I have a quad defined by four arbitrary points, A, B, C and D all on the same plane. I then have a known point on that quad, P. I want to find the value of 's' as shown in the diagram above, where t ...
6
votes
5answers
7k views

Why do we choose cubic polynomials when we make a spline?

Good morning, I want to learn more about cubic splines but unfortunately my class goes pretty quickly and we really only get the high level overview of why they're important and why they work. To me ...
6
votes
4answers
446 views

Profinite and p-adic interpolation of Fibonacci numbers

On the topic of profinite integers $\hat{\bf Z}$ and Fibonacci numbers $F_n$, Lenstra says (here & here) For each profinite integer $s$, one can in a natural way define the $s$th Fibonacci number ...
6
votes
4answers
2k views

Proof of Schur's test via Young's inequality

I am able to prove the following generalization of Schur's test using the Riesz-Thorin interpolation theorem, however I have been stuck for days now trying to prove it using Young's inequality: Let ...
6
votes
2answers
5k views

Why is $L^{1} \cap L^{\infty}$ dense is in $L^{p}$?

It is mentionned that using the interpolation inequality $$\Vert f \Vert_{p} \leq \Vert f \Vert^{1/p}_{1} \Vert f \Vert_{\infty}^{1-1/p}$$ one can deduce that the space $L^{1} \cap L^{\infty}$ is ...
6
votes
2answers
7k views

Spline interpolation versus polynomial interpolation

What is the difference, if any, between spline interpolation and piecewise polynomial interpolation?
6
votes
3answers
1k views

Where did the idea of hermite interpolation came from?

I am given the Hermite interpolation formula directly in my text book without ANY explanations about how it was first made (obviously it was somehow constructed for the first time with some sort of ...
6
votes
1answer
3k views

Remainder term of Lagrange Interpolation Polynomial

Suppose $x_0,x_1,\ldots,x_n$ are $n+1$ distinct numbers in the interval $[a,b]$ and $f\in C^{n+1}[a,b]$. Then for each $x$ in $[a,b]$, there is a number $\xi$ in $(a,b)$ such that $$f(x) = P(x) + \...
6
votes
3answers
23k views

How can I find which function corresponds to a set of data points?

Suppose I have a set of data points like this: 1;1 2;4 3;9 4;16 5;25 6;36 ... The first column is the input of the function and the second one is the result. I ...
6
votes
4answers
146 views

Prove $f[x_0,…,x_{n-1}] = \sum_{i=0}^{n-1}x_i$ if $f(x) = x^n$ for $n\in\mathbb{N}$

Definition The divided difference of function $f$ at points $x_0, x_1, ..., x_k$ is defined recursively as $$ f[x]=f(x), \qquad f[x_0,...,x_k] =\frac{f[x_1,...,x_k]-f[x_0,...,x_{k-1}]}{x_k-x_0}, \...
6
votes
2answers
8k views

Understanding proof of uniqueness in theorem on polynomial interpolation

There is a slight part of the following proof in my textbook which I don't quite get. THEOREM If $x_0, x_1,...,x_n$ are distinct real numbers, then for arbitrary values $y_0, y_1,...,y_n$, there is ...
6
votes
1answer
8k views

2D array downsampling and upsampling using bilinear interpolation

I am trying to understand how exactly the upsampling and downsampling of a 2D image I have, would happen using Bilinear interpolation. Now I am aware of how bilinear interpolation works using a 2x2 ...
6
votes
1answer
178 views

Is there a name for this piecewise cubic interpolation kernel

I went looking for a way to do piecewise cubic interpolation, like natural cubic splines, but: expressible as a convolution of data points with a piecewise cubic kernel; and still C2-continuous still ...