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.
717
questions
34
votes
5answers
2k views
How close can $\sum_{k=1}^n \sqrt{k}$ be to an integer?
How close can
$S(n) = \sum_{k=1}^n \sqrt{k}$
be to an integer?
Is there some $f(n)$ such that,
if $I(x)$ is the closest integer to $x$,
then $|S(n)-I(S(n))|\ge f(n)$
(such as $1/n^2$, $e^{-n}$, ...).
...
33
votes
1answer
838 views
Examples of transcendental functions giving almost integers
Informally speaking, an "almost integer" is a real number very close to an integer.
There are some known ways to construct such examples in a systematic way. One is through the use of certain ...
28
votes
2answers
606 views
Prove $|P(0)|\leq 2n+1$
Let $P(x)$ be a polynomial with degree $\leq n$ and $|P(x)|\leq\frac{1}{\sqrt{x}}$ for $x\in(0,1]$. Prove that $|P(0)|\leq 2n+1$. The idea should be that if $|P(0)|$ is too large, then the polynomial ...
23
votes
2answers
9k views
Series expansion of the determinant for a matrix near the identity
The problem is to find the second order term in the series expansion of the expression $\mathrm{det}( I + \epsilon A)$ as a power series in $\epsilon$ for a diagonalizable matrix $A$. Formally, we ...
22
votes
2answers
564 views
Distance from $x^n$ to lesser polynomials
I am interested in the $L_1$ distance of $x^n$ to the $\mathbb R$-span of $\{1,x,\ldots,x^{n-1}\}$ over some interval. We can WLOG consider the interval $[0,1]$ (say) because scaling and shifting only ...
18
votes
2answers
1k views
Why is $(\sqrt{2}+\sqrt{3})^{2008}$ so close to an integer?
Using 5000-digit precision in PARI/GP, I discovered that the fractional part of $(\sqrt{2}+\sqrt{3})^{2008}$ is extremely small, less than $10^{-999}$.
Is there a simple explanation for this fact ?
...
17
votes
4answers
2k views
Approximating continuous functions with polynomials
Given $\epsilon \gt 0$ and $f \in C^{0}[0,1]$, Weierstrass says that I can find at least one (how many? probably a lot?) polynomial $P$ which approximates f uniformly: $$\sup_{x \in [0,1]} |f(x) - P(x)...
17
votes
2answers
8k views
How do I find a Bezier curve that goes through a series of points?
When someone has the 4 control points P0, P1, P2, P3 of a 2D cubic Bézier curve,
that person can calculate a series of hundreds of points along the curve
that start from P0 at t=0 and end at P3 at t=1
...
16
votes
5answers
5k views
Polynomial approximation of circle or ellipse
Trying again, with a somewhat simpler sounding question, since my previous one (Generalizations of equi-oscillation criterion) got zero response:
Let $F:[0,1] \to R^2$ be a parametric polynomial ...
15
votes
1answer
1k views
Approximation of Semicontinuous Functions
Assume that $k \in \mathbb{N}$ and $f : \mathbb{R}^d \rightarrow [0,\infty)$ is lower semicontinuous, i.e. $f(x) \leq \liminf_{y \rightarrow x} f(y)$ for all $x \in \mathbb{R}^d$.
Does there exist ...
14
votes
3answers
331 views
A curious algebraic fraction that converges to $\frac{\sqrt{2}}{2}$
I have noticed that the algebraic fraction
$\frac{3a+2b}{4a+3b} $
Gives better and better approximations to $\sin 45^\circ = \frac{\sqrt{2}}{2} $
For $ a = b = 1$ we get $5/7 \approx 0.714 $
...
14
votes
2answers
280 views
Why do deep neural networks work well?
The universal approximation theorem, as I understand it, states that for any continuous bounded function $f: X \rightarrow \mathbb{R}$ with compact domain $X$ and any threshold $\varepsilon$ there is ...
14
votes
2answers
945 views
Monotonic version of Weierstrass approximation theorem
Let $f\in\mathcal{C}^1([0,1])$ be an increasing function over $[0,1]$.
Prove or disprove the existence of a sequence of real polynomials $\{p_n(x)\}_{n\in\mathbb{N}}$ with the properties:
$p_n(x)$ ...
13
votes
2answers
364 views
$f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$.
Let $f\in\mathcal{C}^2(\Bbb{R},\Bbb{R})$ be a positive function such that $f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ does it implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$?
...
12
votes
5answers
925 views
Approximation theorems
The Weierstrass' approximation theorem for continuous functions on a compact space by using polynomials is well-known. As far as I know, there are some variants of this theorem, e.g. Stone-Weierstrass ...
11
votes
1answer
2k views
Proving that: $9.9998\lt \frac{\pi^9}{e^8}\lt 10$?
I would like to use mathematical tools to prove that
$$9.9998\lt \frac{\pi^9}{e^8}\lt 10$$
With an on-line calculator I got
$$ \frac{\pi^9}{e^8}\approx 9.9998387978$$
But I do not know any ...
11
votes
1answer
457 views
Function for which trapezoidal rule outperforms midpoint rule for every $n$
Is there a continuous elementary function $f:[0,1]\to [0,\infty)$ such that for every $n$ the trapezoidal approximation to $\int_{0}^{1}f(x)\,dx$ with $n$ trapezoids is strictly better than the ...
11
votes
0answers
385 views
A generalization of an integral related with $\zeta(2)$
It is well-known that:
$$ \int_{0}^{+\infty}\frac{x}{e^{x}-1}\,dx = \zeta(2) = \sum_{n\geq 1}\frac{1}{n^2} \tag{1}$$
but what is known about
$$ I_2 = \int_{0}^{+\infty}\frac{x^2}{e^x-1-x}\,dx \...
10
votes
4answers
2k views
Is Ramanujan's approximation for the factorial optimal, or can it be tweaked? (answer below)
Ramanujan's famous factorial approximation, $$n!\approx\sqrt{\pi}\left(\frac{n}{e}\right)^n\root\LARGE{6}\of{8n^3+4n^2+n+\frac{1}{30}}$$ is far more accurate that the Stirling approximation when ...
10
votes
6answers
190 views
Approximating $\log x$ with roots
The following is a surprisingly good (and simple!) approximation for $\log x+1$ in the region $(-1,1)$:
$$\log (x+1) \approx \frac{x}{\sqrt{x+1}}$$
Three questions:
Is there a good reason why this ...
10
votes
2answers
1k views
Why is the polynomial best approximation to an even function itself even?
I have seen this stated and it seems intuitively obvious but I cannot prove it. I have a feeling it may be because a non-even best approximant would not satisfy the equioscillation property of the ...
10
votes
2answers
241 views
Approximating smooth function on $[0,1]$ by Bernstein polynomial (interested in approximation rate in $L^2$ norm)
Consider a smooth function $f$ on $[0,1]$ and its Bernstein polynomial of power $n$:
$$B_n(f)=\sum_{k=0}^n f\left(\frac{k}{n}\right) b_{n,k}(x)$$
with
$$b_{n,k}(x) = \binom{n}{k}x^k (1-x)^{n-k}.$$
...
10
votes
1answer
461 views
$\epsilon>0$ there is a polynomial $p$ such that $|f(x)-e^{-x}p|<\epsilon\forall x\in[0,\infty)$
Could any one tell me how to solve this one?
Given $f\in C[0,\infty)$ such that $f(x)\to 0$ as $x\to\infty$ we need to show that for any $\epsilon>0$ there is a polynomial $p$ such that $|f(x)-e^{-...
10
votes
0answers
123 views
Is there a theory of “almost symmetry” generalizing group theory?
Apologies for the inescapably soft question.
Does there exist a theory that aims to develop tools analogous to those of group theory, except for the study of objects that are merely almost ...
10
votes
0answers
384 views
About the Gibbs phenomenon for the Legendre polynomials as an orthogonal base of $L^2(-1,1)$
In a recent question, I proved that the Fourier-Legendre expansion of the function $f(x)=\text{sign}(x)$ over $(-1,1)$ is given by:
$$2\sum_{m\geq 0}\frac{4m+3}{4m+4}\cdot\frac{(-1)^m}{4^m}\binom{2m}{...
9
votes
3answers
340 views
Approximation of elements in arithmetic progressions by logarithms of integers
For fixed $a,b,c \in \mathbb{R}$ with $ac \neq 0$, it seems to me that one can find an increasing sequence of integers $\{\alpha_n\}$ such that the quantity $c \log \alpha_n$ becomes arbitrarily close ...
8
votes
7answers
558 views
Why does $ \frac{2x}{2+x}$ provide a particularly tight lower bound for $\ln(1+x)$ for small positive values of $x$?
EDIT:
My question was poorly worded.
I wasn't asking about showing $\ln(1+x) > \frac{2x}{2+x}$ for $x>0$.
What I wanted to know is why the lower bound provided by $ \frac{2x}{2+x}$ was so ...
8
votes
2answers
3k views
How to best approximate higher-degree polynomial in space of lower-degree polynomials?
My question is: Find the best 1-degree approximating polynomial of $f(x)=2x^3+x^2+2x-1$ on $[-1,1]$ in the uniform norm(NOT in the least square sense please)?
Orginially, as the title of the post ...
8
votes
1answer
228 views
How prove $ \; |f(1)|\le 2004\;$ if $\sqrt {x(1 - x)}\; \Big|f(x)\Big|\le 334$ for $f(x) = Ax^2+ Bx + C $
Let $ \; A,B, C\in {\mathbb R} ,\;$ and $ \; f(x) = Ax^2+ Bx + C$ and
$ \sqrt {x(1 - x)} \left|f(x)\right|\le 334,\;\forall x\in [0,1]\;$.
How prove $ \; \left|f(1)\right|\le 2004\;$ ?
7
votes
5answers
453 views
What is a nice way to compute $f(x) = x / (\exp(x) - 1)$?
I want it to be stable near $f(0) = 1$. Is there a nice function that does this already, like maybe a hyperbolic trig function or something like expm1, or should I just check if $x$ is near zero and ...
7
votes
3answers
302 views
How to derive this curious approximation to the cube root of $a + bi$?
In this Wikipedia article in Portuguese is given the following approximation for the cube root of a complex number $ c = a + bi$:
$$ \sqrt[3]{c} \approx k\left ( \frac{29z^3 + 261z^2 + 255z + 22}{7z^...
7
votes
1answer
507 views
What is “Approximation Theory”?
What exactly is "Approximation Theory"? If I read the wikipedia-article I doesn't get much clearer. Why are "pure" mathematicians interested in it? I see a lot of people that do harmonic analysis also ...
7
votes
1answer
2k views
Why do people fit polynomials?
Could someone explain the justification and limits of fitting polynomials to arbitrary data points? I mean what about square roots or fractional or inverse powers?
Most of the time some wants to ...
7
votes
1answer
163 views
recurrence relation in approximating theory
I am stuck in a little part of a problem:
I wish to give an approximation of $\sin(\pi x)$ on $-1 \leq x \leq 1$, when using the polynomial $$F_N(x)=\sum_{k=0}^{N}a_kx^{2k+1}$$
with the coefficients $...
7
votes
1answer
291 views
Integral with Bessel function
Let $n$ be half an odd integer, say $n=k+1/2, k \in \mathbb{N}$.
Let $q\geq 1$. I would like to calculate (or approximate) the following integral:
$$
\int_0^{\infty}\left(\sqrt{\frac{\pi}{2}}\cdot 1\...
7
votes
0answers
91 views
“Taylor series” is to “Volterra series” as “Padé approximant” is to _________?
Padé approximants are often better than Taylor series at representing a function. Given a Taylor series, one can use Wynn's epsilon algorithm to easily produce the Padé approximants to it.
Volterra ...
7
votes
0answers
118 views
$\operatorname{frac}(na)$ is dense in $[0,1]$ for irrational $a$. How to find the smallest $n$ efficiently?
It is well known that the sequence $\operatorname{frac}(na)$ , where $\operatorname{frac}$ denotes the fractional part and $n$ runs over the positive integers, is dense in $[0,1]$.
Suppose, I have ...
6
votes
2answers
9k views
Atan2 Faster Approximation
I am using atan2(y, x) for finding the polar angle from the x-axis and a vector which contains the point (x,y) for converting Cartesian coordinates to polar coordinates. But, in my program which will ...
6
votes
2answers
87 views
If $f\in C[0,1]$ and $A\subset[0,1]$ is finite, can $f$ be approximated uniformly by polynomials that coincide with $f$ on $A$?
Let $f\colon[0,1]\to\mathbb{R}$ be continuous and $A$ a finite subset of $[0,1]$. Given $\epsilon>0$ is there a polynomial $p$ such that
$$
|f(x)-p(x)|\le\epsilon\quad\forall x\in[0,1]\quad\text{...
6
votes
1answer
593 views
Does an extension operator in Sobolev spaces commute with derivative operators?
Assume that $\Omega\subseteq \mathbb R^d$ is open and has a Lipschitz boundary. Let $\tau\geq0$. Then we know that there exists a linear operator $E:H^\tau(\Omega)\to H^\tau(\mathbb R^d)$ such that ...
6
votes
2answers
2k views
Natural cubic spline interpolation error estimate
I am looking for an error estimation for natural (one with $s''(a) = s''(b) = 0$ boundary conditions) cubic spline interpolation on an evenly spaced grid. The best result I've found was $O(h^2)$ ...
6
votes
1answer
431 views
Approximation of bounded and continuous mappings
Does anyone know if we can approximate a bounded (i.e. bounded sets in V are mapped to bounded sets in V': for every bounded $U\subseteq V$ and $x\in U$, there exists $K_U>0$ such that $\|f(x)\|_{V'...
6
votes
1answer
187 views
Any insight on the half reciprocal Fibonacci sequence?
Define $R_n=R_{n-1}+\frac{1}{R_{n-2}} $ with $R_0=R_1=1$
Define $K_n=\frac{1}{K_{n-1}}+K_{n-2} $ with $K_0=K_1=1$
These are all limits I've found using Python but no basis of proof for these limits ...
6
votes
1answer
232 views
Simple approximation to a sum involving Stirling numbers?
I have also posted this question at https://mathoverflow.net/questions/141552/simple-approximation-to-a-sum-involving-stirling-numbers#141552. I have an exact answer to a problem, which is the ...
6
votes
2answers
2k views
Weierstrass factorization of sine, and related questions
So the idea is that you can represent a function as a product of its zeroes, and there are some fundamental factors that often crop up.
I am interested in, give this is the WF of sine :
Is it ...
6
votes
1answer
187 views
Limits of the wave equation with piecewise constant propagation speed
Consider a wave equation
$$\frac{\partial^2 u}{\partial t^2} = c(x)^2 \frac{\partial^2 u}{\partial x^2} \tag{1}$$
In frequency domain this becomes an ODE:
$$-\omega^2 u = c(x)^2 \frac{\partial^2 u}{\...
6
votes
0answers
69 views
What is the rational function that deviates least from $0$?
It is a well known result that among the set of polynomials of degree $n$ with leading coefficient $1$, the $n^{th}$ order Chebyshev polynomial $T_n (x)$ minimizes the (point-wise maximum) deviation ...
5
votes
3answers
213 views
How to approximate the integral $\int_{-b}^{\infty}\log(t+b)e^{-t}e^{-e^{-t}}dt$
Suppose we have the following integral
\begin{equation}
\int_{-b}^{\infty}\log(t+b)e^{-t}e^{-e^{-t}}dt,
\end{equation}
where $b$ is a positive constant. It seems very difficult to derive the exact ...
5
votes
1answer
557 views
Taylor polynomial approximation
How do you determine if adding more terms to the Taylor polynomial will improve its approximation of $f(p)$ or in other words, how do you determine if a Taylor series converges for a particular value ...
5
votes
2answers
100 views
Can we approximate any eigenvalue of an infinite matrix via eigenvalues of some sequence of submatrices which approximates the matrix?
Let $T:\ell^2\to\ell^2$ be a compact linear operator. Let $[T]=(a_{i,j})_{i,j=1}^{\infty}$ be the representing infinite matrix of $T$ with respect to the canonical base. Let $T_n$ be the finite rank ...
