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
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'...
- 6,882
59
votes
9
answers
5k
views
Examples of back of envelope calculations leading to good intuition?
Some time ago, I read about an "approximate approach" to the Stirling's formula in M.Sanjoy's Street Fighting Mathematics. In summary, the book used a integral estimation heuristic from ...
28
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
- 2,353
27
votes
2
answers
3k
views
Accumulation of algebraic subvarieties: Near one subvariety there are many others (?)
Let's work over the field $\mathbb{C}$ of complex numbers, and let $X\subset \mathbb{P}^n$ be a projective variety. Let $\tilde{X}\subset \mathbb{P}^n$ be any small open neighborhood of $X$, in the ...
- 19.9k
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 ...
- 251
24
votes
4
answers
2k
views
Why the sequence of Bernstein polynomials of $\sqrt x$ is increasing?
Bernstein polynomials preserves nicely several global properties of the function to be approximated: if e.g. $f:[0,1]\to\mathbb R$ is non-negative, or monotone, or convex; or if it has, say, non-...
- 56.6k
23
votes
1
answer
1k
views
Hilbert's Theorem on $L_2$ norm of polynomials in $\mathbb{Z}[X]$ - Explicit construction and a converse?
Consider the set of polynomials with real coefficients as a vector space with the following inner-product: $\langle f, g \rangle = \int_{a}^{b} f(x)g(x) dx$.
Hilbert showed, in a paper from 1894, ...
- 13.4k
22
votes
2
answers
647
views
Does every positive continuous function have a non-negative interpolating polynomial of every degree?
Let $f:[a,b] \to (0,\infty)$ be a continuous function. Then is it necessarily true that for every $n\ge 1$, we can find $n+1$ distinct points $\{x_0,x_1,...,x_n\}$ in $[a,b]$ such that the ...
- 1,199
19
votes
1
answer
2k
views
Accumulation of algebraic subvarieties: Near one subvariety there are many others (?), 3
Part 3 of this series of questions. In the meantime, I realized that there is some very simple question that was left open in Accumulation of algebraic subvarieties: Near one subvariety there are many ...
- 19.9k
17
votes
4
answers
3k
views
Using Quotient of Prime Numbers to Approximation Reals
We know a positive rational number can be uniquely written as $m/n$ where $m$ and $n$ are coprime positive integers. Particularly, we can pick out those numbers with $m$ and $n$ both prime.
Question ...
- 273
17
votes
4
answers
976
views
Finite interpolation by a nondecreasing polynomial
Let $x_1 < x_2 < \ldots < x_n$ and $y_1 < y_2 < \ldots < y_n$ be two sequences
of $n$ real numbers. It is well known that there are polynomials that "interpolate"
in that $f(x_i)...
- 3,565
17
votes
2
answers
726
views
Approximation of smooth diffeomorphisms by polynomial diffeomorphisms?
Is it possible to (locally) approximate an arbitrary smooth diffeomorphism by a polynomial diffeomorphism?
More precisely: Let $f:\mathbb{R}^d\rightarrow\mathbb{R}^d$ be a smooth diffeomorphism for $d&...
- 173
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
16
votes
2
answers
3k
views
Approximating a convex function by a piecewise linear function
Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow \...
- 161
16
votes
1
answer
608
views
Approximating zero sets of real polynomials with "less complicated" polynomials
Let $K \subset \mathbb{R}^n$ be a compact subset, and let $P(x_1,\dots,x_n)$ be a real multivariable polynomial of degree $d$, whose vanishing set we denote by $Z_P$. Is it plausible to approximate $...
- 1,303
15
votes
5
answers
13k
views
A differentiable approximation to the minimum function
Suppose we have a function $f : \mathbb{R}^N \rightarrow \mathbb{R}$ which, given a vector, returns the value of its smallest element. How can I approximate $f$ with a differentiable function(s)?
- 453
15
votes
0
answers
516
views
Functions approximated by rolling epicycle curves
Imagine a decreasing sequence of (positive) radii $r_1 > r_2 > r_3 > \cdots$
and a series of nested circles $C_1 \supset C_2 \supset C_3 \supset \cdots$
with these radii,
initially each ...
- 149k
13
votes
5
answers
3k
views
Application of polynomials with non-negative coefficients
Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I ...
13
votes
5
answers
1k
views
Does this sequence span $L^2$?
Consider the following sequence of functions in $L^2[0,\infty)$:
$$f_n(x)=e^{-x/n}x^n,\;\;n\geq 1$$
Does this sequence span $L^2[0,\infty)$ (that is, is the set of finite linear combinations
of these ...
- 520
12
votes
1
answer
516
views
Can $C^1$ mappings with derivative of low rank be approximated by smooth maps?
Asked once on SE-mathematics.
Let $U$ be an open subset in $\mathbb{R}^n$, $m\in\mathbb{N}$, $1\leq m<n$ and let
$$\mathcal{C}^k_{\leq m}(U,\mathbb{R}^n):=\lbrace g\in\mathcal{C}^k(U,\mathbb{R}^n)\...
- 123
12
votes
1
answer
1k
views
Accumulation of algebraic subvarieties: Near one subvariety there are many others (?), 2
This is a sequel to the question Accumulation of algebraic subvarieties: Near one subvariety there are many others (?) .
Let $Y$ be some projective variety, over $\mathbb{C}$. Let $X\subset Y$ be ...
- 19.9k
11
votes
2
answers
1k
views
Low-degree polynomial approximation of the piecewise-linear function $x \mapsto \max(x, 0)$ on an interval $x \in [-R,R]$
For $R > 0$, consider the piecewise-linear function $\sigma_R: [-R,R] \rightarrow \mathbb R^+$, defined by $\sigma_R(x) := \max(x,0)$.
Question
Given $\epsilon> 0$, find a "low-degree" ...
- 6,726
11
votes
1
answer
618
views
Real polynomial bounded at inverse-integer points
Let $p$ be a real polynomial and $N$ be a positive integer. Suppose I tell you that $|p(\frac{1}{k})| \le 1$ for all $k\in\{1,\ldots,N\}$, and also that $p(\frac{1}{N})\le -\frac{1}{2}$ while $p(\...
- 9,743
11
votes
2
answers
793
views
A generalization of Chebyshev polynomials
What is the monic polynomial $p(x)$ of degree $n$ which minimizes $\max_{x \in [-1,1]} |p(x)|$? The answer is the Chebyshev polynomial, and its largest value on $[-1,1]$ is $1/2^{n-1}$.
Now suppose ...
- 113
11
votes
4
answers
2k
views
A senseful meaning of 'approximation of manifolds'?
Any continuous function can be uniformly approximated by smooth functions.
I would like to have something similar - in what-ever sense - for continuous manifolds.
For example, by Whitney's theorem, ...
- 4,776
11
votes
1
answer
1k
views
Stone-Weierstrass analogue for $L^p$
Let $A$ be a complex algebra of bounded measurable functions on the measure space $(X,\mu)$ (case of $[0,1]$ with Lebesgue measure is enough for me) closed under conjugation. Assume that $A$ separates ...
- 103k
11
votes
1
answer
1k
views
What are some of the surprising results of finite sample statistical estimation?
I'm trying to familiarize myself with the latest results in finite sample statistics. It seems to me that these results can be classified into two categories:
Unsurprising results confirm that the ...
- 385
11
votes
1
answer
1k
views
New method to compute square roots [closed]
In 2011 when I was in school I created a formula to calculate square roots... For $x\in\mathbb{R}$ with $x>0$ the following holds:
$$\sqrt{x} = \sum_{n=0}^{\infty}\frac{\left(\prod_{k=1}^{n}\left(\...
- 53
11
votes
0
answers
202
views
Degree of 2-variable real polynomial that’s large on a square and small on a nearby “L”
I’d like to know what’s the minimum possible total degree of a real polynomial $p(x,y)$ such that:
(1) $p(x,y)\in [0,1]$ whenever $x,y\in [0,1]$ with either $x$ or $y$ at most $\epsilon$, and
(2) $p(...
- 9,743
10
votes
3
answers
20k
views
Approximation of a normal distribution function
I am reviewing and documenting a software application (part of a supply chain system) which implements an approximation of a normal distribution function; the original documentation mentions the same/...
- 211
10
votes
4
answers
10k
views
Approximation with continuous functions
Is it true that for every function $\mathbb{R} \to \mathbb{R}$ there exists a sequence of continuous functions $f_n(x): \mathbb{R} \to \mathbb{R}$ such that for any $x \in \mathbb{R}$ $f_n(x)$ ...
- 2,761
10
votes
2
answers
526
views
Reference request: Extensions of Wiener's Tauberian Theorem
Wiener's Tauberian Theorem says that linear combinations of translations of a function $f$ are dense in $L^1(\mathbb{R})$ if and only if the zero set of the Fourier transform of $f$ is empty. This is ...
- 680
10
votes
1
answer
543
views
Are the polynomials in $\{1/t\}$ dense in $L^2(0,1)$?
Added. My question in the title was solved (in the negative) by Nik Weaver (in the answer below) and Mateusz Kwaśnicki (in the comments). In both solutions, the reason is that the $L^2$ density fails ...
- 13.7k
10
votes
2
answers
5k
views
Approximate a probability distribution by moment matching
Suppose we want to approximate a real-valued random variable $X$ by a discrete random variable $Z$ with finitely many atoms. Suppose all moments of $X$ is finite. We want to match the moments of $X$ ...
- 1,829
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 ...
- 288
10
votes
1
answer
864
views
The closures in $C^0(\mathbb{R}, \mathbb{R})$ of the set of integer valued polynomials, resp, of polynomials with integer coefficients
This is a follow up of an interesting recent question on the topic. The answer given there by fedia shows that the matter is rich and complicated, and I can't resist to submit here a further question.
...
- 56.6k
10
votes
3
answers
1k
views
Non-linear "Fourier analysis"
Call a function of the following form a beep: $e^{-(\frac{x-\alpha}{\beta})^2}\sin(\rho x+\theta)$. Given a real-valued function $f\in L^2(R)$ and a number $n$, I'm interested in the approximating $f$...
- 17.5k
10
votes
1
answer
504
views
Density of smooth function in Hilbert spaces
I am looking for a simple reference to the following fact:
If $f:\Omega\to\mathbb{R}$ is continuous, where $\Omega\subset H$ is an open subset of a separable Hilbert space $H$, then for any $\...
- 27.3k
10
votes
1
answer
786
views
Approximation of a compactly supported function by Gaussians
Let $f:\mathbb{R}\to\mathbb{R}$ be a smooth function whose support is a closed interval, e.g. $\text{supp}(f)=[a,b]$. Then $f$ can be approximated (e.g. in $L^2$) by a linear combination of Gaussian ...
- 680
9
votes
3
answers
649
views
Degree necessary of a polynomial?
Given $-1<a<b<0$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[a,b]$ at every $x\in[b^2,a^2]$ and $f(0)=0$. What is minimum degree that is needed and maximum degree that ...
- 13.7k
9
votes
2
answers
1k
views
polynomials with minimal $L_\infty$ norm on multiple disjoint intervals
It is well-known that Chebyshev polynomials are the polynomials of minimal $L_\infty$ norm on [-1,1] with leading coefficient 1. But what if you want the minimal $L_\infty$ polynomial on two disjoint ...
- 223
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)}.
$...
- 458
9
votes
1
answer
517
views
Approximating power series coefficients --- Why does a clearly illegitimate method (sometimes) work so well?
For reasons that don't matter here,
I want to estimate the power series coefficients
$t_{ij}$ for the rational function
$$T(x,y)= {(1+x)(1+y)\over 1- x y(2+x+y+x y)}=\sum_{i,j} t_{ij}x^iy^j$$
Using a ...
- 22.5k
9
votes
1
answer
474
views
Subspaces of $L^2(0,1)$ dense on every truncation $L^2(c,1)$
It may be better to move this to a separate question.
Let me call a linear subspace $V \subset L^2(0,1)$ to be tame if, for every linear subspace $W \subset V$, either $W$ is dense in $L^2(0,1)$, or ...
- 13.7k
9
votes
2
answers
767
views
Approximation theory on the disc
Chebyshev theory provides a very effective method for approximating continuous real valued functions on the unit interval. Is there something similar for continuous real valued functions on the ...
- 55k
9
votes
1
answer
542
views
Polynomial approximations of curves
This is the 3D version of this question. The responses to that question contained a lot of complaints about fuzzy definition of the problem, so I made this new question very narrow and explicit.
For ...
- 649
9
votes
0
answers
548
views
Padé approximations of $e$
The following question came up in the analysis of some algorithm.
Let $R_{s,t}(z)$ be the Padé approximants of $e^z$, and define $r_{s,t} = R_{s,t}(1)$. Using the explicit expression for the error ...
- 1,886
8
votes
6
answers
7k
views
How to approximate a solution to a matrix equation? [closed]
Suppose a matrix equation $Ax = b$ has no solution ($b$ is not in the column space of $A$)
How can I find a vector $x^\prime$ so that $Ax^\prime$ is the closest possible vector to $b$?
- 451
8
votes
3
answers
2k
views
Kronecker Approximation theorem and Fibonacci numbers
There is a famous old theorem by Kronecker that for every positive real $\alpha$ and $\epsilon>0$ there exists a positive integer n such that $\alpha n$ is within $\epsilon$ of an integer.
...
- 616
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 ( ...
- 609