# Questions tagged [approximation]

A method of finding nearly-optimal solutions to a problem. Generally, this terminology is applied to algorithms and heuristics for solving NP-Hard problems in computer science.

93 questions
Filter by
Sorted by
Tagged with
75 views

156 views

• 161
1 vote
68 views

### Questions on Daubechies wavelets

Is the refinement equation for the orthonormal Daubechies scaling function $$\phi(x) = \sqrt{2} \sum_n h_n \phi(2x-n) \;?$$ The filter coefficients for Daubechies wavelets have been given e.g. in this ...
• 331
126 views

### Remez algorithm convergence

I have implemented the Remez algorithm in Python where all calculations were done with the Python mpmath library. I have noticed that sometimes the $|E_{max}|$ and $|E_{min}|$ do not monotonically ...
• 161
332 views

### What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate

What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more ...
• 131
1 vote
922 views

### what is non-asymptotic convergence?

I guess convergence in general means it is in asymptotic sense but what does non-asymptotic convergence mean?. Can someone please explain with an example?
30 views

### Fast approximate evaluation of Fourier-Legendre series

Suppose I know that a function from $[0,\pi] \to \mathbb{R}$ may be written as $$\sum_{k=0}^\infty A_l \frac{2l+1}{4\pi} P_l(r)$$ where $A_l$ all are known. Is there a way in which I may very ...
• 21
281 views

### How can I calculate the exponential integral?

(I originally asked this in a different exchange.) I'm writing a program that uses the prime-counting function. Right now, I'm using x/log(x), but I want to ...
• 109
79 views

• 73
282 views

### Size of jump for piecewise discontinuous approximations

If one has a sufficiently smooth function $u$ that is approximated by a piecewise constant function $u_h=\Pi^0_h u$ on a mesh of cell size $h$ (where $\Pi^0_h$ is the $L_2$ projection onto the ...
• 50.2k
43 views

• 161
214 views

### Numerical evaluation of the Exponential Integral Ei by rational Chebyshev approximations fails

I am trying to evaluate the Exponential Integral $Ei(x)=-\int^{\infty}_{-x}\frac{e^{-t}}{t}dt$ for $x>0$ (interpreted as the Cauchy principal value) by using rational Chebyshev approximations, ...
• 155
1 vote
37 views

### Find alternative path closest to original

I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that ...
1 vote
58 views

### Finding optimal point distance to get desired number of random points in an area

I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$: I need to control the number of points in the ...
• 383
435 views

### Polynomial order of an approximation of a section of sine and numerical accuracy

I was playing with the idea that a sine function is periodic. But even within one period there are symmetries, namely the second fourth of a period is the mirror image of the first fourth and the ...
• 430
3k views

### imaginary time propagation to find ground state wavefunction

I understand the basic idea of imaginary time propagation method: The wavefunction $\psi(x,t)$ as a superposition of energy eigenstates $\phi_m(x)$: $$\psi(x,t)=\sum_m \phi_m(x)e^{-iE_mt/\hbar}$$ ...
• 153
1 vote
49 views

### Alternative to two "for" loops in finding best neighborhoods for TSP?

I am trying to solve Travelling Salesman Problems using tabu search. I have been able to successfully find "near enough" optimal solutions (as well as one optimal, yay!). For the moment I am using ...
468 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 ...
• 639
2k views

### Methods for fast approximation of convolution

What are the state of the art methods for fast 2D convolution approximation? I'm familiar with SVD based multiplication and cross approximation approaches, but would be thankful to get additional ...
• 83
135 views

### Are there any benefits of computable analysis to numerical algorithms

Computers can work only with computable numbers, while most of the algorithms are based on analysis of real numbers (real analysis). When I heard of the existence of computable analysis I ...
• 607
287 views

### Does this Algorithm (probably Fourier like) Exist for 2D Shapes? [closed]

Update: Someone changed the title to this post to a possible answer ("Fourier decomposition of parametric shapes") but I changed it to a different title as that makes it clear what I was asking. As I ...
1 vote
75 views

### Expected number of steps before a global optimum is found with Simulated Annealing

I'm reading a technical report on Simulated Annealing: On the Convergence Time of Simulated Annealing, by Sanguthevar Rajasekaran. You may find it following this link. Given $G=(V, E)$ is the graph ...
• 113
4k views

### Solving a system of linear equations with only an approximate solution

I have a system of linear equations that is derived partially from experimental data. Theoretically, the system should have a single, exact solution; however, experimental error causes it to not have ...
• 61