19

For the first part of my question, I found this very useful comparison for performance of different linear interpolation methods using python libraries: http://nbviewer.ipython.org/github/pierre-haessig/stodynprog/blob/master/stodynprog/linear_interp_benchmark.ipynb Below is list of methods collected so far. Standart interpolation, structured grid: http:/...


14

Why not simply show the absolute value function? Approximation with e.g. Legendre-polynomial expansion works, but pretty badly: Taylor expansion is of course completely useless here, always giving only a linear function, either always decreasing or always increasing (depending on whether the point you expand around is negative or positive).


10

This is the classic colorization using optimization problem. Optimization and Linear Algebra To see how this can be expressed as a linear system, it's helpful to use a slightly different notation (and a slightly different objective function). Think of your image as graph $G$ with a node for each pixel in the image. There is an edge $(i,j)$ between two ...


10

It's a pathological case, but you can always resort to the Weierstrass monster function. It illustrates a broader point, namely that functions that are not smooth -- e.g., that have a kink -- are difficult to approximate because the interpolation error estimates require the function being interpolated to be differentiable a number of times. In other words, ...


9

Short answer You are missing the Jacobian of the transformation for the derivatives. Long answer The conditions that you propose for your interpolator translate into the following system of equations $$ \begin{bmatrix} 1 &x_1 &x_1^2 &x_1^3\\ 1 &x_2 &x_2^2 &x_2^3\\ 0 &1 &2x_1 &3x_1^2\\ 0 &1 &2x_2 &3x_2^2 \...


8

There are standard methods for these types of quadrature in Python, in NumPy and SciPy: Gauss-Laguerre quadrature Gauss-Legendre quadrature Gauss-Hermite quadrature (as noted in your post) Gauss-Chebyshev quadrature QUADPACK adaptive quadrature adaptive Gaussian quadrature and other routines. Given a degree of quadrature (essentially, the degree of the ...


8

There is no built-in Fortran functionality to do linear interpolation. You could either use a library or write your own routine. I haven't tried compiling or testing and my fortran may be a bit rusty, but something like the following should work. subroutine interp1( xData, yData, xVal, yVal ) ! Inputs: xData = a vector of the x-values of the data to be ...


8

This problem is generally called the Minimax Problem. Unfortunately the step function is not continuous and therefore the Weierstrass approximation theorem does not apply. Any continuous approximation will have $\epsilon \ge 0.5$ since there is a jump of size 1 so the best you can do at that point is split the difference. In fact, $y = 1/2$ is as good as you ...


8

That depends on how well you know the coordinates and velocities. If you have exact values, you can get a reasonable answer using Hermite interpolation. This will give you a degree-3 polynomial in each window that matches the coordinates and velocities at all the endpoints. Alternatively, if you do not know the coordinates and velocities exactly, but you do ...


7

For a polynomial interpolant we have the formula for the pointwise error $$ E_n(x) = f(x) - p_n(x) = \frac{f^{(n+1)}}{(n+1)!}\prod_{i=0}^n(x-x_i),$$ where the $x_i$ are the interpolation knots. In general, we want to work with the right hand side of the error formula (a derivation appears in the book by Quarteroni et. al.) as the function we interpolate is ...


7

The frequency content of the interpolated signal is significantly influenced by the interpolation basis. If you have a band-limited function that you have adequately sampled (i.e. satisfying Nyquist criterion), interpolating with any function that is not band-limited to the same frequency will indeed introduce high-frequency noise. Unfortunately, exact band-...


7

Your choice of parameterization is creating problems. Instead of spanning one in $t$ between points, span an amount proportional to the line segment between the two points in $(x,y)$ space. I've created a Python example that demonstrates the issue. It compares a uniform parameterization $(x_t(t),y_t(t))$ (like yours, but mine is scaled so that $t \in [0,1]$...


7

First of all, interpolation and approximation are slightly different from each other. Given a sufficiently smooth function $f$ (sufficiently smooth just means that I am covering my bases, there are many theorems in approximation theory considering different function classes, from discontinuous -measure zero- functions to infinitely smooth or analytic or ...


7

The other answer has everything you already need, but it's also worth pointing out that $u_h$ is computable whereas $I_hu$ is not: The latter requires you to know the exact solution, which in general we of course don't know (and if we did, we didn't need to compute a Galerkin approximation $u_h$).


6

I hope I understood the question correctly. They try to compute exactly the same thing, so they really are equivalent. I'll use Chebyshev polynomials because they are easy to analyze. Given a function $f(x)$ on $[-1,1]$, the spectral interpolant is the truncation of $$ \begin{aligned} f(x) &= \sum_{n\geq0} \bar a_n T_n(x), \\ \bar a_n &= \frac{1+[n&...


6

The point of @WolfgangBangerth is exactly what I mentionend in my comment, so I'd always try this first. In the best case, with millions of partitions $[a_{i},a_{i+1}]_{i\in \{0,\ldots,N-1\}}$ (where $a_{i} < a_{i+1}$), the length of these is quite small such that some low-order method could be appropriate. This will require roughly $N \times (s-1)$ ...


6

Approximation is not only made hard by the function to be approximated but by the interval in which the approximation should be a "good fit". And you should define the measure for a "good fit", i.e. what is the maximum (absolute or relative) error you wish to tolerate? For example, you will need a huge number of terms in the Taylor series of $\exp(x)$ to ...


6

Polynomials are surprisingly effective at function approximation [1]. If you have at least Lipschitz continuity, then Chebyshev approximations will converge. Of course, convergence may be slow, and that is the price we pay for dealing with a non-smooth function. Today, computers are much faster than the days in which many numerical analysis books were ...


6

The interpolated polynomial does not have roots. Considering that the behavior outside the interpolation region holds is termed extrapolation. You can explicitly use the polynomial, given by (as I explained in this post) $$f(x) \approx N_1(x) u_1 + N_2(x) u_2 + |J|(N_3(x) u'_1 + N_4(x) u'_2)\quad \forall x\in [a, b]$$ with $|J| = (b - a)/2$ the Jacobian ...


6

Let's assume $u$ is the solution to the variational problem and $u_h$ is the Galerkin approximation of the solution on the subspace $V_h \subset V$. By Cea's lemma you have: \begin{equation} ||u-u_h||_V \leq C\inf\limits_{v_h \in V_h}||u-v_h||_V \end{equation} for some positive constant $C$. Now you define the projection $I_h:V \rightarrow V_h$. As you ...


5

Running the command edit interp2 allows you to see the source code of this particular function and then you can read the piece of code that deals with bicubic interpolation. In MATLAB R2011, there is even a paper being cited: "Cubic Convolution Interpolation for Digital Image Processing", Robert G. Keys, IEEE Trans. on Acoustics, Speech, and Signal ...


5

Any polynomial interpolation method will include a 0th-order term and thus interpolate a constant exactly. Further, some methods have the nice property that they can interpolate polynomials up to some degree $N$ exactly, where $N$ is also the max. interpolation degree. Lagrange polynomials are an example of this.


5

The interpolation indeed affects the Fourier transform. @Steve already gives the correct answer in general, but I want to give you an example that helps the intuition more. Think for example that you have samples a sine function on a set of equally spaced points. If you did a (discrete) FFT on these points alone, you would of course recover a Fourier ...


5

A hexahedron with straight edges is the image of the unit cube under a trilinear mapping. So, if you have values on the eight vertices of a hexahedron, and you are asking to interpolate between them to a point $x$ somewhere inside the hexahedron, then the correct approach is as follows: Invert the trilinear mapping to find the corresponding point $\hat x = \...


5

I want to mention another idea in case it helps. The truncation error of replacing $\int_{-\infty}^{\infty}$ with $\int_{-L}^L$ is on the order of $$\begin{aligned} \int_L^\infty \cos(tx)g(x)\,\mathrm{d}x &= \frac{1}{t}\sin(tx)g(x)\big|_{L}^{\infty} - \int_L^\infty\frac{\sin tx}{t}g'(x)\,\mathrm{d}x \\&= -\frac1L g(L)\sin(tL) + \text{asymptotically ...


5

You assume that a property that holds for the original function $f$ is also true for the $L_2$ projection $u_h=P_h f$. In your case, the property is that if $f$ is non-negative, then $u_h$ should also be non-negative. But this assumption is not in general correct. You already know this from taking a few terms of a Fourier or Taylor series: Just because a ...


5

This will implicitly depend on your function, $F$, as well as the method you used to derive your $f$ and $g$. If your $F$ were, say, the constant function $F(y,z)=1$, then you'd be guaranteed to have no error whatever you do. On the other hand, if you have a discontinuous $F$, say $$F(x,y)=\begin{cases} 1&y\leq0,\\ 0& y>0, \end{cases} $$ then ...


5

Since you are trying to find the gradient of the function in the vertices of a triangular mesh. So, we are considering an interpolation over the dual mesh defining the value on each centroid, you can try those area based interpolation function e.g, Wachspress Interpolation function. The benefit of this interpolation function is that it is general enough for ...


4

There is a paper by Moré, implemented by Nocedal, about that: Jorge J. Moré and David J. Thuente. 1994. Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 3 (September 1994), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 (preprint).


4

Hmm... cubic interpolation is not unheard of for line search, but typically overkill. If I'm reading your problem correctly, $x$ is just a scalar? In this case BFGS is probably not the most efficient way of solving your problem. Scalar optimization algorithms like Brenth's method are likely to solve your problem faster. There are a number of line search ...


Only top voted, non community-wiki answers of a minimum length are eligible