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
4
votes
0answers
88 views

Convergence speed of discrete approximation

Here I asked the question about approximating the function $g(x) := \mathbb{E}(f(x,Y))$, where $x \in R$ and $Y$ is a random variable. If you follow the link you will see that $g(x)$ can be ...
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}{\...
3
votes
2answers
177 views

Rigorous rationale for the Pade Approximant?

I recently asked a Question for which the only Answer I got was a recommendation to punt and use the Pade Approximant. This is the first time I recalling seeing this, and intuitively it seems like ...
0
votes
1answer
164 views

Closed set that is not $\rm proximinal$ set

Every $proximinal$ set must be $closed$, but the opposite is not true. I'm looking for such an example. A $closed$ set that is not $proximinal$ set ?
0
votes
1answer
58 views

Approximation of a continuous function with a particular sequence of smooth functions

Let the interval $[0,1]$ be divided into $n$ subintervals each of length $\frac{1}{n}$. Let $f\in C([0,1], \mathbb R)$ a continuous functions in $[0,1]$ and consider the set $\Omega_n=\big(f\in C^2([0,...
0
votes
1answer
44 views

Polynomial Extrapolation Error Resource

Given $n + 1$ samples of a $n+1$ times continuously differentiable function $f \in C^{k + 1}$: \begin{equation} (x_0, f(x_0)), (x_1, f(x_1)), \dots, (x_n, f(x_n)) \end{equation} Lagrange polynomial is ...
0
votes
0answers
20 views

Binomial Approximation with Small Exponent

Find an approximation for the expression $ (1 + x)^n $, where $ 0 < x < C $ and $ n $ is positive but small. $ C $ is arbitrarily large (<< 1000) and $ n $ is arbitrarily small ($ n <&...
1
vote
0answers
13 views

Jaggedness of the boundary of the $\epsilon$ neighborhood of a set

Let $X$ be a simply connected set in $\mathbb{C}$. Of course $X$ can be quite jagged and nasty. Let $\epsilon>0$ be given, and define $C(X;\epsilon)=\{z\in\mathbb{C}:\min(|z-w|:w\in X)=\epsilon\}$...
0
votes
0answers
30 views

What is the “right” way of approximating random variables with other random variables?

It is well-known that one can construct a Hilbert space of zero mean, finite variance random variables such that every random variable of this type $X$ can be represented as a linear combination of a ...
0
votes
2answers
55 views

Are of Polynomials of Continuous functions complete?

The Stone-Weierstrass Theorem guarantees that every continuous function defined on a closed interval [a,b] can be approximated as closely as desired by a polynomial. I'm curious in polynomials of ...
0
votes
1answer
38 views

Approximating the basis of a specific function

We are given a continuous function $g: A \to B $, where $A, B$ are compact subsets of $\mathbb{R}$. We define a function $f(x) := g(b_1x)+g(b_2x)+...+ g(b_mx)$, where $b_i < 1$ and $b_ix$ is a ...
1
vote
0answers
23 views

Number of simple functions needed to approximate another function

I have got a function $f$ which maps from one compact space to another. Function $f$ is smooth. I want to approximate it with some simple functions (e.g polynomials). Is there any theory that gives ...
1
vote
2answers
25 views

Optimal Fixed-Digit Rational Approximations of $\pi$

Is there a systematic way of finding optimal rational approximations to $\pi$ whose numerator and denominator have at most $n$ digits? More precisely: Let $D_n$ be the set of all positive integers ...
0
votes
1answer
37 views

Extension of function analytic on [-1,1]

Given that a function $f$ is analytic on $[-1,1]$, that is, for any $s ∈ [−1, 1]$, $f$ has a Taylor series about $s$ that converges to $f$ in a neighborhood of $s$. Can we conclude that $f$ is ...
0
votes
2answers
31 views

Can we find a holomorphic function $g$ on an open disk such that $\sum_{i \in \mathbb{N}} |(f-g)(a_i)|^2 < +\infty$?

Let $f : \mathbb{C} \to \mathbb{C}$ be a continuous function with $f(0)=0$. Let $\{a_i\}_{i\in \mathbb{N}}$ be a set of scalars in $\mathbb{C}$ such that $$\exists C > 0 : \forall i\in \mathbb{N} ...
1
vote
1answer
91 views

Truncation error with growing step size

When I read about finite difference methods (or really any approximation method), truncation error is often central to the discussion, and rightfully so. But it is also most often discussed in the ...
0
votes
0answers
19 views

What are some options for adaptive spline approximation of data in 1-D?

What are available options for adaptive spline approximation of data in 1-D? I've some data in a single dimension that I would like to approximate using some kind of spline, preferably a cubic. As ...
0
votes
0answers
10 views

Approximation of mean of a rational function of random variables

Let $\xi_i$ with $i\in\{1,\dots,n\}$ be iid random variables and let $Q(x,y)$ be a rational function. I need to compute one $x$ that satisfies $$\frac{1}{n}\sum_{i=1}^n Q(x,\xi_i)=0.$$ This is a ...
0
votes
1answer
45 views

$N$ birds are distributed on a telephone wire

$N$ birds are distributed on a telephone wire that can fit a maximum of $2N$ birds. The spacings between birds form a sequence $S$. The minimum space between birds is $1$ unit. The sequence is ordered ...
2
votes
1answer
821 views

Natural Cubic Spline Unequal Spacing

I'm currently trying to create a natural cubic spline by setting up linear equations to solve for the coefficients of the spline. Where the spline follows as : $S_i(x)=a_i+b_i(x-x_i)+c_i(x-x_i)^2+...
0
votes
0answers
34 views

The singular values of the best rank-$k$ approximation to a matrix

Let $A\in\mathbb{C}^{m\times n}$ be a complex matrix. Let $B_k$ be a best rank-$k$ approximation to $A$ such that \begin{equation*} B_k\in\arg\min\limits_{{\rm rank}(B)=k}||A-B||_F, \end{equation*} ...
2
votes
1answer
31 views

Distance of the element from the subspace of $l_{1}.$

Let $l_{1}$ be as follows $$l_{1}=\Big\{\{x_{n}\}_{n=0}^{\infty}\subset \mathbb C\: : \: \sum_{n=0}^{\infty}|x_{n}|<\infty\Big\}$$ and its subspace be $$V=\Big\{\{x_{n}\}_{n=0}^{\infty}\in l_{1}\: :...
0
votes
0answers
58 views

Expressions approximating Generalized Harmonic Number (truncated polynomials with shrinking error term preferred)

Specifically, $$H_m^{(2n)} \approx\ ?$$ and $$H_m^{(4n)} \approx\ ?$$ where $(m, n)$ $\in \mathbb N_{>1}$ I would not like to use special functions like the (Riemann zeta function) unless they ...
0
votes
0answers
50 views

Elementary approximations to $\zeta(s)?$

What are the best approximations in terms of elementary functions of one real variable for: $$\zeta(s)=\sum_{n=1}^{\infty} \frac{1}{n^s},$$ for $Re(s)>1?$ There is not an elementary function that ...
0
votes
0answers
43 views

Uniform approximation of $L^2$ basis by smooth functions with bounded derivatives of all orders

Let $\mathcal{F}=\{f_i\}_{i\in\mathbb{N}}$ be an orthonormal Hilbert basis of $L^2[0,1]$. I am wondering whether it is possible to approximate the $f_i$ uniformly across $i$ in the $L^2$-norm by ...
2
votes
0answers
26 views

Can $x^n$ be uniformly approximated by the combination of $x^{k^2}$?

For each $n\in\mathbb{N}$ , can $x^n$ be uniformly approximated by the linear combination of $\left(x^{k^2}\right)_{k\in\mathbb{N}}$ ? In order to facilitate a solution, we might as well try to ...
0
votes
1answer
41 views

Approximate solution for high order polynomial (order 12) [closed]

I'm trying to get an approximation value of y by x from the following equation $\ x = $$\sum_{i=1}^{12} y^i$ The current suggestion is to take y=1+z and z tending to zero or y tending to 1 any ...
2
votes
2answers
40 views

Tight upper bounds for a monotonically increasing non-linear recurrence

I have the following non-linear recurrence: $$y_{n+1} = \sqrt{\frac{2}{1+y_n}}y_n,\quad y_0 \in[0,1]$$ Some basic thought shows that $0$ and $1$ are fixed points of this, and that $0$ is repelling ...
0
votes
0answers
20 views

$(N+1)^{\text{th}}$-order terms in $N^{\text{th}}$-order approximation

I am working with a formula for which I'd like an $N^{\text{th}}$-order approximation. After some simplification, I am able to solve for a form of the expression with some but not all $(N+1)^{\text{th}...
0
votes
0answers
34 views

Unbounded approximation ratio

Suppose that there is a specific instance of a graph for which the approximation ratio of an algorithm polynomially increases with the number of nodes of the graph, say the approximation ratio is $n^2$...
1
vote
1answer
81 views

SDP relaxation for the sparset cut

On page 338 of Williamson & Shmoys's The Design of Approximation Algorithms, the presentation of the ARV algorithm for the sparsest cut over a graph $G(V,E)$ has the following formulation ...
1
vote
1answer
55 views

What is the complete Partial Derivatives approximation formula to calculate the value of a function?

We know the approximation formula using partial derivatives to calculate the value of a function with some variables $x$ and $y$, which can be extended to any number of variables to be \begin{...
0
votes
1answer
31 views

A question on the existence and uniqueness of a cubic Hermite interpolant

I have been trying to solve a particular problem that establishes both the existence and uniqueness of a cubic hermite interpolant on some generic interval $[a,b]$. Briefly, for a function $f$ we ...
1
vote
0answers
32 views

Smooth approximation (under supremum norm) of distance to algebraic set in $\mathbb{R}^n$.

Given a set $S$ which is the zeroes of a finite number of homogenous polynomials in $x\in\mathbb{R}^n$, I want a constant $\alpha$ and a $C^2$ approximation, denoted $d$, to the function $d(x,S)=\inf_{...
1
vote
1answer
149 views

Sign of approximation error and remainder (residual)

In the Wikipedia article Taylor series it is said that: The error incurred in approximating a function by its $n$th-degree Taylor polynomial is called the remainder or residual and is denoted by ...
0
votes
0answers
28 views

How could I obtain this approximation of the May-Wigner theorem?

I'm trying to understand the complete proof of the May-Wigner theorem. We have a real random $n\times n$ matrix $B$ with its non-zero elements $B_{ij}$ are chosen independiently from a fixed ...
0
votes
1answer
116 views

Can we approximate continuous functions arbitrarily well with polynomials? (beyond Weierstrass )

Let $f:(0,1) \to \mathbb{R}$ be continuous, and let $\delta:(0,1) \to \mathbb{R}$ be continuous and positive. Does there always exist a polynomial $p(x)$ satisfying $|f(x)-p(x)| < \delta(x)$ for ...
0
votes
0answers
44 views

Landau inequality for several variables

For $f \in C^n(\mathbb{R})$ and $0 < \alpha < n$, Landau-Kolmogorov inequlity is geven by $$ \|f^{(\alpha)}\| \leq K(n,\alpha)\| f\|^{1-\alpha/n}\|f^{(n)}\|^{\alpha/n}, 0 < \alpha < n,$$ ...
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 ...
1
vote
0answers
19 views

Approximating the lateral derivatives

Let $f : [0,2] \to \mathbb{R}$ be a continuous function with continuous derivatives of all orders in every point except at $t = 1,$ where the lateral derivatives exist. We know that one can ...
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 ...
0
votes
0answers
17 views

Optimize a fixed size susbset

So I'm trying to solve this problem: There are many people who apply for jobs at a company. Each applicant has some technical skills required for jobs. The skills possessed by different ...
1
vote
0answers
58 views

Advanced Methods for Approximating Surfaces based only on partial derivative estimates

I'm looking for information on interpolating a surface function p(x,y) based only on estimates of the partial derivatives at points on a grid. Obviously, any such approximation is subject to a ...
1
vote
1answer
21 views

Generalization of Power Series

Given a smooth function $f(x):$ Does there always exist an expansion of x around a point $x_{0}$ of the form $$\sum_{n=0}^\infty \frac{h(f^{(n)}(x_{0}))}{n!}g(x-x0,n)$$ for some functions $h(c),g(a,b)...
0
votes
0answers
28 views

Regression through linear Fourier coefficient fitting?

Basically suppose on was given an unknown function/data and expected to write a function so that $Y=f(X)$, this can be done by linear regression in simple cases very easily. However, suppose that the ...
0
votes
1answer
195 views

Smoothing of a step function using smoothstep. (Curve fitting)

I was trying to smoothen the step function (zero when $x$ is less than $2/3$ and equal to $1$ when $x$ is greater then $5/6$) as in the picture below. Trying to fit $f$ in between $2/3$ and $5/6$ ...
0
votes
0answers
15 views

Finding optimal knots for function approximations

I would like to approximate a continuous (complex) function $f(x)$ in the interval $[a,b]$ $ (x\in\mathbb{R})$ by local polynomial functions of order $3$ (cubic Hermite spline or cubic C2 spline). Is ...
1
vote
0answers
25 views

Reference request: Bounded function can be approximated by continuous functions in $L_1$ with bounded $L_\infty$-norm

I think that it is well-known that a real valued function $f\in L_\infty[a,b]$ can be approximated by continuous functions $f_n$ with respect to the $L_1$-norm, i.e. $||f_n-f||_{L^1}\to0$, where the $...
0
votes
0answers
49 views

References for a proof of a Jackson's inequality?

Let $g:[0,2\pi]\to \mathbb{C}$ which is $\mathcal{C}^k([0,2\pi],\mathbb{R})$ and periodic. If $\mid f^{(k)}(x) \mid\le 1$ then for each $n\in \mathbb{N}^*$, there exists a trigonometric polynomial $T_{...
0
votes
1answer
23 views

Approximating a bounded measurable function from below by a sequence of smooth functions

Suppose that $f: \mathbb{R} \to \mathbb{R}$ is a bounded measurable function. Is it possible to find a sequence of functions $\{f_n \}_n: \mathbb{R} \to \mathbb{R}$ in $C^{\infty}_c( \mathbb{R})$ ...