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.

Filter by
Sorted by
Tagged with
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 ...