Questions tagged [na.numerical-analysis]
Numerical algorithms for problems in analysis and algebra, scientific computation
1,227
questions
0
votes
0
answers
20
views
Is there any way to approximate a function based on a series of logarithm
Is there a way to expand a function in terms of logarithmic series? Like when we expand a function in terms of Taylor or Fourier series?
I tried to answer this question this way: Let's assume it can ...
14
votes
1
answer
1k
views
A mass spring model for hair simulation
A strand of hair is represented by a set of particles connected by springs.
The velocity for a particular particle is calculated implicitly using the following formula:
$\boldsymbol{v}^{n+1/2}=\...
0
votes
0
answers
37
views
Galerkin scheme in $H^s_0(G)\subset L^2(G)\subset H^{-s}(G)$ ($s>0$)
What basis functions are usually choosen if one attempts to conduct a Galerkin finite element method given an evolution triplet $H^s_0(G)\subset L^2(G)\subset H^{-s}(G)$. Where $G$ is a sufficiently ...
0
votes
1
answer
107
views
Explicit expression of Padé–Hermite approximant of type I
It is well known that the Padé approximants $(P,Q)$ of an analytic function in the neighborhood of $0$ can be expressed as a quotient of Hankel determinants built on the coefficients of the function $...
4
votes
3
answers
584
views
Approximation for complex variables
Approximation theory, which aims to provide the optimal polynomial function approximating the target function in a given domain such as $x\in[-1,1]$, has been well-developed for real variables. In ...
1
vote
0
answers
61
views
Discretization of oscillating integral
Suppose I am interested in computing
$$
I \equiv \int_0^B dx \, g(x) f(x)
$$
where $B$ is a known upper bound for the integral,
$g(x)$ is a known oscillating function and
$f(x)$ is a smooth function ...
0
votes
0
answers
126
views
Antiderivatives via Taylor series and the FT of Calculus
If $f$ is a real function on an interval $[a,b]$ such that
$f$ is computationally tractable on $[a,b]$: you can calculate $f(x)$ to $n$ bits of precision using an algorithm which is polynomial in $n$ ...
1
vote
0
answers
84
views
Vandermonde-type factorization of moment matrix?
Consider $n,d \in \mathbb{N}_{>0}$, there are many functions $y:\mathbb{N}^{n} \to \mathbb{R}$. Now for simplicity, we denote $y(\alpha)$ to be $y_{\alpha}$. Let $|\alpha| = \sum_{i=1}^{n}\alpha_{i}...
6
votes
4
answers
2k
views
Quantitative de Moivre–Laplace theorem (reference request)
The classical de Moivre-Laplace theorem states that we can approximate the normal distribution by discrete binomial distribution:
$${n \choose k} p^k q^{n-k} \simeq \frac{1}{\sqrt{2 \pi npq}}e^{-(k-np)...
1
vote
1
answer
549
views
Strong convergence of differential quotient in $L^2(0,T;V^*)$
I have got a problem regarding the weak differentiability of Bochner-integrable functions. Let $(V,H,V^*)$ be a Gelfand-triple and
\begin{align*}
w \in W(0,T) := \{w\in L^2(0,T;V) ~\vert~ \exists w' \...
1
vote
0
answers
17
views
Formulation of multipoint constraints using Lagrange multipliers for a time dependent problem (with the Finite Element Method)
Intro
Suppose we have the following static linear equations (e.g. of an elastostatic problem):
$$\mathbf{K}\boldsymbol{u}=\boldsymbol{f}$$
We want a multipoint constraint of the type
$$\boldsymbol{\...
1
vote
1
answer
210
views
Solving (or approximating) a certain delay differential equation
I'm interested in finding the (unique?) solution to the set of delay differential equations
$$f_w(w,x) = xf(w,w^2x)+w^3x^2f(w,w^4x), $$
$$f_x(w,x) = wf(w,w^2x)$$
With the initial condition $f(1,x) = e^...
11
votes
1
answer
700
views
Weakest condition for an integrable, almost-symplectic manifold?
I was recently speaking with someone who works in Computational Chemistry and they mentioned that in a lot of the computational simulations they do, they have systems that are not symplectic but still ...
2
votes
1
answer
233
views
How to solve this set of equations as efficiently as possible (with "efficiently" measured in FLOPS)?
The system of equations is the following:
$$
\Gamma_i^{\ -1} = \sum_{i=1}^nA_{ij}\Gamma_j,
$$
where $\Gamma = (\Gamma_i)$ is a vector of size $n$ and $A$ is a matrix of size $n\times n$, with $n \gt ...
3
votes
1
answer
112
views
Converting an algebraic equation into a ODE
I'm working on a method to solve algebraic equations by converting them into ordinary differential equations (ODEs) and then integrating these ODEs over time.
Given an algebraic equation $f(x(t), t) = ...
2
votes
1
answer
136
views
Are the coefficients in the stationary phase approximation computed explicitly somewhere
In Stein's "Harmonic analysis" book, page 334, one can find
the asymptotic expansion
An instructive proof is given for the case $k=2$. It is clear enough to generalize to the cases $k\geq ...
0
votes
0
answers
73
views
Interpolation polynomials with constraints
Lets consider a collection of $n$ points $\{Z_i\}_{i=1}^n\subseteq \mathbb{D}^k(1)=\{(z_1,\ldots,z_k)\in\mathbb{C}^k:\forall j\leq k, |z_j|\leq 1\}$. Let $h: \{Z_i\}_{i=1}^n \to \mathbb{D}^1(1)$ be a ...
1
vote
1
answer
277
views
Numerical estimation of partial derivatives of convolved functions when closed forms do not exist
Summary: Some peak functions are convolutions which may not have a closed form solution. A classical example can that of a Voigt which is a convolution of a Lorentzian and a Gaussian, followed by ...
1
vote
0
answers
48
views
Galerkin’s Method for hyperbolic PDEs: proving convergence without using compactness
Lawrence Evan's PDE book prove the existence of solution to the following problem where $L$ is an elliptic operator:
$$
\begin{cases}
u_{tt} = -Lu+f,\\
u|_{t=0} = u_0,\\
u|_{\partial U} = 0
\end{cases}...
10
votes
5
answers
14k
views
Numerical differentiation. What is the best method?
What is the best method for 1D numeric differentiation? Something as glorious as Gaussian quadrature for numeric integration.
Maybe differential quadrature is such a method? What is its accuracy?
I'...
4
votes
1
answer
385
views
Linear convergence rate of proximal point algorithm
For $T : R^n \to P({R^n})$ maximally monotone, the proximal point algorithm (step size $c>0$)
$$
x^{k+1} = (I + c T)^{-1} x^k,
$$
converges linearly with rate $\kappa = \frac{1}{1 + c \sigma}$ if $...
2
votes
2
answers
428
views
Approximating a subclass of $L^2(\mathbb{R})$ by Schwartz functions within similar subclass
It is well-known that real valued Schwartz functions on $\mathbb{R}_+$ $\mathcal{S}(\mathbb{R}_+)$ are dense in the set of square integrable functions on $\mathbb{R}_+$ $L^2(\mathbb{R}_+)$. We can ...
2
votes
2
answers
287
views
Reference request on computational schemes for $\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$
Let $\Omega\subset \mathbb R^d$ be compact, $\rho$ be a density function on $\Omega$ and $p_1,\ldots, p_n\in (0,1)$ be weights satisfying $\int_{\Omega}\rho(z)dz=1=\sum_{k=1}^n p_k$. We consider the ...
0
votes
0
answers
49
views
Concentration of bilinear forms
This is a bit vague so I'll begin by indicating the motivation. I am looking for ways to [do something interesting or useful] with the self-attention in transformer models. Ultimately the self-...
8
votes
2
answers
3k
views
Condition number related to root finding problems
Suppose we want to find the root of the equation $f(x)=\phi(x) - d = 0$, where d is a real constant and $f$ is continuously differentiable function.
The problem is well posed if the inverse $\phi^{-...
0
votes
1
answer
54
views
Integration algorithm and analytic property
This question is the continuation of the previous one.
In the article about the integration of analytical polynomial - time computable function $f(x)$ with the Taylor series $$f(x) = \sum_{n=0}^{\...
1
vote
0
answers
113
views
Integration in polynomial time
The work of Friedman and Ko and
Müller guarantee the polynomial time computability of the integrals of analytic functions inside the circle of convergence. But do algorithms have practical value? Is ...
1
vote
0
answers
32
views
Error bounds for a Romberg-style improvement of a non-linear approximation
I have a (possibly non-linear) functional $F$, which I want to numerically approximate by a (typically non-linear) $\widehat{F}_h$. For a suitable class of functions, I have asymptotic error behaviour
...
1
vote
0
answers
45
views
Computing smallest singular value of a matrix with explicit error control?
Many good algorithms are out there computing truncated SVD: What is the time complexity of truncated SVD?.
I am trying to implement some codes to find the smallest singular value of a big matrix $A$. ...
14
votes
3
answers
2k
views
Guaranteed correct digits of elementary expressions
Let $E$ be the set of elementary expressions, defined as the smallest set of mathematical expressions such that $1 \in E$, and if $a,b \in E$ then $a + b$, $a - b$, $ab$, $a/b$, $\exp(a)$, $\log(a)$ ...
0
votes
0
answers
30
views
Ensuring symmetry in mixed derivatives using RBF-FD method
I'm working on a numerical problem where I have the first-order partial derivatives $\frac{\partial f}{\partial x}$ and $\frac{\partial f}{\partial y}$ of a bivariate function $f(x, y)$ at a set of ...
-1
votes
1
answer
164
views
Best approximation of the modulus function
While there is extensive study regarding the best approximation of function with polynomial functions in the real domain, the study of approximation of complex variables becomes much sparse. See this ...
5
votes
2
answers
332
views
Locating the maximum point $x_n$ of $f_n(x):=e^{-1/x}\Bigl(1+\frac{1}{n^2 x^n} \Bigr)$ in $(0,1)$
I am trying to observe the behavior of $x_n \in (0,1)$ defined such that the function
\begin{equation}
f_n(x):=e^{-1/x}\Bigl(1+\frac{1}{n^2 x^n} \Bigr)
\end{equation}
attains its maximum inside the ...
2
votes
2
answers
178
views
Roots of modified polynomials
Consider the following two polynomials:
$$
g=x^3 - x^2 - (c + 2)x + c
$$
and
$$
h=x^3 - x^2 - cx + c
$$
The roots of $h$ are $1$ and $\pm \sqrt{c}$. I am interested in obtaining the roots of $g$, ...
2
votes
1
answer
233
views
Computing 3-term connection coefficients for wavelets
I am trying to calculate the three-term connection coefficients
$$
Λ_{l,m}^{d_1,d_2,d_3} = \int_{-\infty}^\infty \varphi^{(d_1)}(x) \varphi^{(d_2)}_l(x) \varphi^{(d_3)}_m(x) dx
$$
for Daubechies ...
1
vote
2
answers
187
views
Numerical integration method that doesn't involve derivative in the error bound
Consider the integral $\int_a^b f(t)dt$.
There are many numerical integration methods, like trapezoidal rule, Simpson's rule, Gaussian quadrature, but all they involve derivative in the error bound.
...
0
votes
0
answers
31
views
Convergence of numerical scheme for HJB equation
Convergence of numerical scheme for HJB equation has been widely studied, the key paper is the Barles's one. Essentially, the convergence is guarenteed if the scheme is:
Consistent
Stable
Monotony
...
0
votes
0
answers
45
views
Godunov splitting convergence research
The approximation of Godunov splitting on certain differential equations is known to be first order accurate. In 2011, a paper has also shown that it is first order accurate for nonlinear ordinary ...
1
vote
1
answer
272
views
Best approximation with tensors of rank $\ge2$
Let $k\in\mathbb N$, $H_i$ be a (finite-dimensional, if necessary) $\mathbb R$-Hilbert space for $i\in I:=\{1,\ldots,k\}$, $H:=\bigotimes_{i\in I}H_i$ denote the tensor product$^1$ of $(H_i)_{i\in I}$ ...
0
votes
1
answer
475
views
How do I get an analytical solution to this nonlinear equation?
I posted this question over on Math Stack Exchange (link), but have not received a response. I'm wondering if it's too complicated for that audience, so I'm posting it here in the hopes that someone ...
1
vote
5
answers
583
views
Avoiding overfitting by averaging polynomials fit to part of the data?
I was thinking about the problem of overfitting data. Suppose you have a hundred data points sampled from an unknown function (call this the training set). You could try fitting a hundred-...
0
votes
0
answers
52
views
How to solve with FEM a semilinear elliptic equation?
I searched in many books regarding FEM how to solve semilinear elliptic equation, but I did not find too many things. They mostly treat linear and simple problems. For example in P.Ciarlet-The finite ...
1
vote
0
answers
175
views
Connection of eigenspace of finite Hilbert matrix and its continuous operator counterpart
I am trying to understand the connection between the eigenspace of the continuous operator
$$
H(x,y) = \frac{1}{x+y}
$$
which is nothing but the square of the Laplace operator, and its discrete ...
1
vote
0
answers
48
views
Computing geodesic length of Euclidean lines in the manifold of positive definite matrices
I am working with the manifold of positive definite matrices $PD(n)$ equipped with the affine-invariant Riemannian metric (AIRM) $g_P(V,W):=tr(P^{-1}VP^{-1}W)$, where $P \in PD(n)$ and $V,W \in T_P PD(...
8
votes
1
answer
7k
views
Upper bound on largest eigenvalue of a real symmetric $n \times n$ matrix with all main diagonal entries positive, everywhere else nonpositive
Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them ...
4
votes
0
answers
193
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
3
votes
1
answer
271
views
Root finding algorithm for an analytic function
Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
3
votes
1
answer
157
views
Numerical scheme for convex optimization
Given $(e_n)_{-N\le n\le N}\in\mathbb R^{2N+1}$ and $-1<x<1$, solve
\begin{eqnarray}
&&\max_{(q_n)_{-N\le n\le N}\in\mathbb R^{2N+1}_+}~ \sum_{n=-N}^N (e_n-\log(q_n))q_n \\
\mbox{s.t.} &...
0
votes
1
answer
149
views
Where can I find the paper by Tappert and Hardin on split-step Fourier transform method?
The split-step method is a numerical method that can be used to solve a nonlinear PDE (https://en.wikipedia.org/wiki/Split-step_method). Even Wikipedia does not refer to the original authors (F.D. ...
4
votes
2
answers
630
views
Difference between Chebyshev first and second degree iterative methods
Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...