Questions tagged [approximation-theory]
Approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby.
583
questions
2
votes
0
answers
136
views
"Almost rational" irrational
This is a follow-up to an older question.
Let $r\in \mathbb{R}\setminus\mathbb{Q}$, let $\mathbb{N}$ denote the set of non-negative integers and let $\mathbb{N}_+=\mathbb{N}\setminus\{0\}$. For $n\in\...
- 45.5k
3
votes
0
answers
356
views
A conjecture on consistent monotone sequences of polynomials in Bernstein form
A Conjecture
In the following, a polynomial $P(x)$ is written in Bernstein form of degree $n$ if it is written as— $$P(x)=\sum_{k=0}^n a_k {n \choose k} x^k (1-x)^{n-k},$$ where $a_0, ..., a_n$ are ...
- 637
17
votes
2
answers
1k
views
Explicit and fast error bounds for polynomial approximation
Main Question
This question is about finding explicit, calculable, and fast error bounds when approximating continuous functions with polynomials to a user-specified error tolerance.
EDIT (Apr. 23): ...
- 637
8
votes
3
answers
540
views
Approximation of pseudogeometric progression
Let $f_n(x)=1+x+x^{\sqrt{2}}+x^{\sqrt{3}}+x^{\sqrt{4}}+\cdots+x^{\sqrt{n}}$ be a sequence of functions on the interval $[0, 1]$. Is there a good closed form approximation for such a function ( ...
- 1,422
8
votes
1
answer
223
views
Smooth approximation of Hölder functions "from below"
We assume that we have a $\alpha$-Hölder continuous function $f$ on an interval $[0,1].$
I am wondering if there exists an explicit construction of a sequence $f_{n} \in C_c^{\infty}(\mathbb R)$ such ...
- 118k
5
votes
2
answers
655
views
Approximation of Hölder continuous functions "from below"
We assume that we have a $\alpha$-Hölder continuous function $f$ on an interval $[0,1]$ with $f(0)=0$.
I am wondering if there exists an explicit construction of a sequence $f_{n} \in C_c^{\infty}(\...
0
votes
1
answer
168
views
How to prove approximation for fresnel integral converges
I was looking at the fresnel integral $S(x)=\int^x_0\sin(s^2)ds$. From reading I learned that this integral approaches $\frac{1}{2} \sqrt{\frac{\pi}{2}}$ as $x \rightarrow \infty$. Through messing ...
- 11.4k
1
vote
1
answer
148
views
Approximating a strictly increasing non-negative function on a non-negative domain by polynomials with non-negative coefficients
Let $f:[0,2]\rightarrow [0,\infty)$ be a strictly increasing smooth function. The Weierstrass approximation theorem says that we can uniformly approximate $f$ by polynomials. But my concern is
...
CommunityBot
- 1
1
vote
0
answers
68
views
Carleman approximation for functions from $\mathbb R$ to (closed convex subset of) a Lie algebra
I am looking for an approximation result dealing with continuous functions of a real parameter with values in (some subset of) the unitary algebra. However, I wouldn't be surprised if the following ...
5
votes
4
answers
3k
views
Construct the best piece-wise linear continuous function fitting given curve
How to construct the optimal piece-wise linear continuous function fitting given curve and given number of knots (optimal knots positions also must be determined by this method)?
2
votes
0
answers
140
views
Wrinkling smooth functions
I am interested in applying a result from the work by Eliashberg and Mishachev on wrinkling. Namely, in their first paper on wrinkling, they prove Theorem 1.6 B (Theorem 1.6 A is a non-parameterized ...
- 1,446
2
votes
1
answer
211
views
Measuring how "close" $\alpha\in[0,1]\setminus\mathbb{Q}$ is to being rational
Let $\mathbb{N}_+$ denote the set of positive integers and let $\mathbb{N}_0 = \mathbb{N}_+\cup\{0\}$. Fix $\alpha\in[0,1]\setminus \mathbb{Q}$. For $n\in\mathbb{N}_+$ we let the approximation radius ...
- 577
25
votes
2
answers
4k
views
A "better" rational approximation of pi?
$355/113$ is a good fractional approximation of $\pi$, because we use six digits to produce seven correct digits of $\pi$.
$$\frac{355}{113} = 3.1415929\ldots$$
Let $R$ be the ratio of the number of ...
CommunityBot
- 1
2
votes
1
answer
75
views
Zeros in $[0,1]$ of functions $f \in \mathrm{span} \{ p(x - \lambda_k)e^{\lambda_k x} : k=1,\dots, n \}$
Let $n \in \mathbb N$, let $p:\mathbb R \to \mathbb R$ be a real polynomial, and let $\lambda_1< \lambda_2 <\dots < \lambda_n$. Now let
$$
f \in \mathrm{span} \left \{ p(x - \lambda_k)e^{\...
- 88.9k
1
vote
2
answers
101
views
Measurability of Brjuno numbers
A positive irrational number $\alpha\in{\mathbb R}\setminus {\mathbb Q}$ is said to be a Brjuno number if $$\sum_{i=1}^\infty\frac{\log q_{i+1}}{q_i} < \infty$$ where $q_i>0$ is the denominator ...
- 3,617
6
votes
2
answers
462
views
Optimal polynomial approximation of rational function $\frac{1}{1-x}$
I've been working on the following polynomial approximation problem. I want to find the optimal Chebyshev approximation of the rational function $\frac{1}{1-x}$ on the real interval $x\in[-\rho, \rho]$...
- 88.9k
3
votes
1
answer
154
views
Approximation in Bochner spaces
Is there any result like the Bramble-Hilbert lemma for Bochner spaces?
More specifically: let $H$ be a (e.g.) Hilbert space, $I\subset \mathbb R$ a bounded interval, and $L \in \mathcal L(H^k(I;H), Y)...
- 5,255
7
votes
3
answers
908
views
How to numerically compute $x \ln x$ and related functions near $0$?
I was recently trying to find a numerical solution to a thermodynamics problem and the expression $x\ln x$ appeared in one of the computations. I did not have to find its value very near $0$, so the ...
- 4,843
8
votes
1
answer
690
views
A robust version of "a holomorphic function is determined by its modulus"
It is well known that if $f(z)$ and $g(z)$ are both holomorphic on a (path-)connected open set $C$ and $\lvert f(z)\rvert=\lvert g(z)\rvert$ on $C$ then $f(z)=cg(z)$ on $C$ for some constant $c$. Do ...
- 8,672
1
vote
0
answers
209
views
Is there an approximate formula for this summation function?
Consider the function $$\sum_{n=1}^\infty \frac{\cos(nx)}{n^r},$$ where $r\in\mathbb{N}$. Is there any approximate formula (closed form possibly avoiding this type of summation) for this function? I ...
- 59
2
votes
2
answers
431
views
Approximation of a given function by rational functions
Given a function $1/\sqrt{x^2 -k^2}$ where k is a constant with a small imaginary part, how do you go about constructing a rational approximation? I am interested in the L_p (p=2 or $\infty$) norm of ...
- 1,422
1
vote
1
answer
216
views
Finding the set of best approximation
Given $X$=$l^1$ and its dual space $X^*=l^\infty$. Now take $f=(1, 1/2, 2/3, 3/4,...) \in X^*$. Then clearly $\|f\|_\infty = 1$. I have found that $H=\ker f$ is a proximinal hyperplane in $X$.
Note: A ...
- 551
5
votes
3
answers
637
views
The relative error of approximating a binomial
Are there any good approximations for a binomial CDF that work well in terms of the relative error, as opposed to absolute? For the usual normal approximation, the absolute error is very well-studied ...
- 37.2k
4
votes
0
answers
98
views
Interpolation on Sobolev space on $[0, 1]^d$ over finite meshes
Let $\Omega = [0, 1]^d$ and suppose that $f \colon \Omega \to \mathbb{R}$ lies in order $m > d/2$ Sobolev space; i.e.,
$$
\|f\|_{H^m(\Omega)}^2 = \sum_{|\alpha| \leq m} \|D^\alpha f\|_{L^2(\Omega)}^...
- 342
1
vote
0
answers
45
views
Error bounds for Sobolev space norm approximation on a finite grid
Suppose that $f : [0, 1] \to \mathbb{R}$ is an element of the order-$k$ Sobolev space,
\begin{multline}
f^{(k - 1)}~\text{is absolutely continuous},\quad \|f\|_{W^k}^2 := \int_0^1 f^{(k)}(x)^2 \, dx &...
CommunityBot
- 1
4
votes
1
answer
1k
views
Variational proof for minimum curvature of cubic splines
Background: Given an increasing set of points $(x_i)_{i=0}^n \subset \mathbb [a,b]$, a cubic spline $S(x)\in C^2([a,b])$ is a piecewise cubic polynomial on each subinterval $(x_i, x_{i+1})$.
Given a ...
- 3,554
2
votes
1
answer
246
views
Construction of the Lipschitz function with a given Lipschitz constant, given two values and with small Lipschitz norm
Let the function $f\colon [a,b] \to\mathbb{C}$ be Lipschitz and let $|f(a)| \geq c,$ $|f(b)| = c$ and $\varepsilon > 0.$
It is easy to see that if $\|f\|_{\infty}< \frac{\varepsilon}{2} =: \...
- 42.2k
1
vote
1
answer
124
views
Construction of the Lipschitz function with a given Lipschitz constant and given two values
Let the function $f\colon [a,b] \to\mathbb{C}$ be Lipschitz and let $|f(a)| \geq c$ and $|f(b)| = c$. Is there a Lipschitz function $g$ such that $|g| \geq c,$ $g(a)=f(a),$ $ g(b)=f(b)$ and Lipschitz ...
- 97
8
votes
1
answer
694
views
Bounding the discrete $l^p$ norm by the continuous $L^p$ norm for trigonometric polynomials
Let $ X_N = \text{span} \{\cos(2\pi lx): l=0, \cdots, N-1 \} $ with $ x \in [0, 1] $ and $ Y_N = \{v =(v_0, \cdots, v_{N-1}): v_j \in \mathbb{C}\} = \mathbb{C}^N $. Then $ X_N $ is the space of ...
- 109k
7
votes
3
answers
2k
views
Approximation theory reference for a bounded polynomial having bounded coefficients
Let $P(x)$ be a real polynomial of degree at most $d$. Assume $|P(x)| \leq 1$ for $|x| \leq 1$. I would like a bound saying that each coefficient of $P(x)$ is at most $C^d$ in magnitude, for some ...
- 3
0
votes
1
answer
102
views
Show that $\frac{1}{n} \sum_{i=1}^n a_i \operatorname{erf} \left( \frac{b_i-x}{\sqrt{2}} \right) \to x$ for some sequence $\{a_n\}$ and $\{b_n\}$
Consider the following function
\begin{align}
f_n(x)=\frac{1}{n} \sum_{i=1}^n a_i \operatorname{erf} \left( \frac{b_i-x}{\sqrt{2}} \right)
\end{align}
where $\operatorname{erf} $ is the error ...
- 11.9k
2
votes
0
answers
95
views
Generalization of the min-entropy that looks at the top $n$ probabilities
The min-entropy of a random variable $X$ can often be much easier to compute than the Shannon entropy. This is because the min-entropy is simply a function of the most probable value, and sometimes, ...
- 4,525
1
vote
1
answer
54
views
Can the second-order difference control the first-order difference for nowhere differentiable functions?
Suppose that $f$ is a continuous, nonconstant function on $[0,1]$. Fix some $0<a<1$. Is it possible to establish the following inequality
$$ |f(x+h)-f(x)| \leq C \left[ |h|^a + |2f(x)-f(x+h)-f(x-...
- 118k
9
votes
2
answers
287
views
Average as a constant approximation in $L^p$
Let $I=[0,1]$. For $p\in[1,\infty]$ define $C_p$ as the best constant such that for all $f\in L^p(I)$
$$
\left\|f-\int_If\,\right\|_{L^p(I)}\leq C_p\inf_{c\in\mathbb{R}}\left\|f-c\,\right\|_{L^p(I)}.
$...
- 37.6k
3
votes
0
answers
163
views
Rate of uniform approximation by piecewise constant functions
Definitions and Notation:
Fix a positive constant $M>0$ with positive integers $m,n$ and the standard orthonormal basis $e_1,\dots,e_n$ of $\mathbb{R}^n$.
For every positive integer $N$, define the ...
- 4,969
1
vote
0
answers
118
views
Uniform norm bounds for linear approximation of 1-Lipschitz functions
This problem seems like it should be quite easy/standard, but I've not found a solution written down anywhere.
Consider the set of 1-Lipschitz functions on the $[0,d]$ interval. Define the linear ...
- 5,945
10
votes
1
answer
269
views
A function is of bounded variation if and only if the errors of its best approximation by trigonometric polynomials satisfy $\sum\frac{e_n}n<\infty$?
Let $\mathcal P_n$ be the set of trigonometric polynomials of degree less than or equal to $n$ and let $\lVert\cdot\rVert_\infty$ be the supremum norm. The error of the best approximation of $f$ of ...
- 5,255
2
votes
0
answers
68
views
Under what conditions is the least-squares approximation bounded with the same Lipschitz gradient constants?
Let $f(x):\mathbb{R}^K\Longrightarrow \mathbb{R}^L$ denote a multivariate continuously differentiable function. All the partial derivatives of $f$ (all its Jacobian elements) are bounded from above ...
- 11.4k
4
votes
1
answer
403
views
Smooth approximation of the $\max\{0,x\}$ function with controlled derivatives
Motivation/Hand-Wavy Question:
In this post, it was asked what the best local approximation of $f(x):=\max\{0,x\}$ is by a polynomial of a given degree; with the answer provided by Chebyshev's ...
- 2,464
3
votes
0
answers
146
views
Chebyshev-like polynomials [closed]
In some approximation problems I'm working on, the errors turned out to be polynomials of various degrees whose graphs on the interval $[-1,1]$ look like this:
As you can see, these things look a bit ...
- 9,421
1
vote
0
answers
75
views
Does a matrix product have an upper bound on the largest coefficient?
Let $A$ and $B$ be two $n\times n$ random matrices. Matrix $A$ has coefficients taken from a normal distribution $ \mathcal{N}(\mu_A,\sigma_A)$, and matrix $B$ has coefficients taken from $ \mathcal{N}...
- 101
0
votes
0
answers
47
views
Numerically expanding a function in a rational-power "basis"
I have some scientific code which interfaces with a library which accepts real functions specified as any number of additive terms with exponential powers. For instance, it is capable of accepting ...
- 173
64
votes
5
answers
17k
views
The unreasonable effectiveness of Padé approximation
I am trying to get an intuitive feel for why Padé approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence.
But what I can'...
- 101
0
votes
0
answers
99
views
Wavelet decomposition of $C^{k}$-functions on smooth manifolds
Background (compactly supported wavelet decomposition of $\mathbb{R}^n$):
Fix compactly supported “mother and father wavelets” $\phi,\psi^{\epsilon}:\mathbb{R}^n\rightarrow \mathbb{R}$ where $\epsilon$...
- 4,969
1
vote
0
answers
56
views
Functional approximation with derivatives
I am trying to solve a functional approximation problem.
Consider a set of measurements of a d-dimensional state $\mathrm x \in \mathbb{R}^d$, together with velocities $\dot{\mathrm x}$ and ...
- 60.4k
3
votes
1
answer
3k
views
Simple algorithm to generate a Mondrian "Random Grid"
I was wondering if there is a simple way or algorithm that can generate 2-d grids resembling Mondrian paintings like the boogie woogie grid ( https://nuit-blanche.blogspot.com/2010/12/cs-boogie-woogie-...
- 4,618
5
votes
0
answers
105
views
Asymptotics in the Chebyshev-type optimization problem
Let $g(x)\colon [-2,2]\to \mathbb{R}$ be a continuous function. Let $f_n(x)$ be a polynomial of degree $n$ such that $\log |f_n(x)|\leqslant ng(x)$ for all $x\in [-2,2]$. Then the maximal possible ...
- 103k
0
votes
0
answers
45
views
Can we talk about approximation when the decision problem for solution existence is NP-Hard
I am wishing to design an approximation algorithm for an optimization problem where the existence of solution for corresponding decision problem is not guaranteed. Is it wise to find an approximation ...
- 5,632
1
vote
1
answer
171
views
Approximating a smooth function under some restrictions
Let $C^{m,\alpha}_M([0,1])$ be a Holder ball consisting of real-valued functions $g$ on $[0,1]$ such that
$$ \|g\|_{C^{m,\alpha}} := \max_{0\leq j \leq m } \sup_{x\in [0,1]} |g^{(j)}(x)| + \sup_{x,y\...
- 37.6k
1
vote
0
answers
48
views
Optimal regularity of polynomial interpolators
Definitions
We define the "complexity" of any polynomial function $p:\mathbb{R}^n\rightarrow \mathbb{R}^m$ as $m\binom{n+\deg(p)}{n}$ (i.e the dimension of $\oplus_{i=1}^m\,\mathbb{R}[X_1,\...
- 60.4k