Questions tagged [na.numerical-analysis]
Numerical algorithms for problems in analysis and algebra, scientific computation
1,112
questions
4
votes
2
answers
236
views
Accelerating convergence for some double sums
I am interested in the following general double sums, for integers $a\geq 1$ and $b\geq 2$,
$$Z(a,b) = \sum_{k,\ell \geq 0} \frac{2k+3}{\binom{k+2}{2}^a} \frac{2\ell+3}{(\binom{k+2}{2}+\binom{\ell+2}{...
- 3,345
1
vote
0
answers
21
views
A general question about spectral methods vs finite element methods
According to this Wikipedia article:
Spectral methods can be computationally less expensive and easier to implement than finite element methods; they shine best when high accuracy is sought in simple ...
- 527
0
votes
0
answers
20
views
A simple procedure to simulate multifractional Brownian motion paths
In a paper by Peltier and Vehel the multifractional Brownian motion (mBm) was defined for the first time, and they also give a procedure to simulate mBm sample paths. Briefly, mBm generalizes the ...
- 197
0
votes
0
answers
38
views
Approximation of inverse trigonometric functions [closed]
I would like to implement algorithms from scratch for inverse trigonometric functions (inverse of sine, cosine, and tangent). I found on Wikipedia that those functions are approximated by the Taylor ...
0
votes
1
answer
72
views
FEM based solution to parabolic problem
Consider the problem
$$
\begin{cases}
u_t - \Delta u = 0 &\text{ on } \Omega\times (0,T)\\u=0 &\text{ on } \partial \Omega\times (0,T) \\ u(x,0)=g(x) &\text{ on } \Omega
\end{cases}
$$
...
1
vote
0
answers
31
views
Is there a more efficient computer algebra system to solve the system of nonlinear equations in N-R method or other numerical methods?
Consider the system of infinite series
\begin{align}
&F=x+\frac{y^{3^2}}{3}+\frac{x^{3^5}}{3^2}+\frac{y^{3^7}}{3^3}+\frac{x^{3^{10}}}{3^4}+\frac{y^{3^{12}}}{3^5}+\cdots=0
\\
&G=y+\frac{x^{3^3}}...
- 754
0
votes
0
answers
25
views
What are the convergence requirements for Inverse Power Method?
I'm struggling to find the convergence requirements for the Inverse Power Method. I implemented this method in MATLAB as shown below.
...
0
votes
0
answers
45
views
Fourier spectral methods for an elliptic equation
I would like to study a linear elliptic problem on the torus $\mathbb{T}^n$ (i.e. periodic boundary conditions) which is of the following form:
$$
-\Delta u + b^i \partial_i u + c u = f
$$
where $b^i$,...
- 803
3
votes
0
answers
58
views
Tight bounds on the iterates of the Clenshaw algorithm for Chebyshev polynomials
I'm trying to bound the iterates of the Clenshaw algorithm when applied to the Chebyshev series, related to a question I'm running into related to the stability of this algorithm. Recall that, for $p(...
- 101
1
vote
0
answers
26
views
Complexity of singular value decomposition using matrix multiplication oracles
Suppose I have an $n\times m$ real matrix $A$, $n\ll m$ with full row rank $(\mathrm{rank}(A) = n)$. I have an oracle that can compute $Ax$ or $A^T y$ for any $x\in \mathbb{R}^m, y\in \mathbb{R}^n$. ...
- 363
0
votes
1
answer
77
views
Correct way to conduct equilibrium scaling of linear/integer/MIP program
I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
- 21
6
votes
1
answer
151
views
Reporting inconclusive experimental searches
In many areas of mathematics it is informative to conduct numerical experiments.
But, it not uncommon that the searches do not lead to the examples or data one was hoping for. Since the numerical ...
- 2,771
0
votes
0
answers
49
views
3D interpolation function
I've got a 3D figure created using around 30k points and has different regions colored in an specific way according to some unrelated variables that come from a project I'm creating. Taking in ...
0
votes
0
answers
29
views
Finding the maximum of a certain trigonometric series
Let $a_0,_1,a_2,\dots,a_n$ be a finite sequnce of $n
$ real numbers and consider the function $$f(t)=\sum_{j,k=0}^{n}a_j a_k \cos\left((j-k)t\right)$$ for $t \in [0,2 \pi]$ .If we want to maximise ...
- 532
1
vote
0
answers
81
views
Generating Hermite polynomial with coefficient recurrance relation algorithm
I am writing a math paper for my numerical analysis class about orthogonal Hermite polynomials. I want to implement the algorithm for generating the "probabilist's Hermite polynomials":
$$
\...
- 11
1
vote
0
answers
88
views
p-adic taylor polynomial [closed]
This might be an easy question but i am sorry for asking this.
Let $f(x)\in\mathbb{Z}_p[x].$ Is it always true that
$$f(x+y)=f(x)+f'(x)y+f''(x)\frac{y^2}{2}+zy^3$$
for some $z\in\mathbb{Z}_p.$ if it ...
- 31
2
votes
0
answers
65
views
Iterative method of finding root
I don't know much about numerical analysis. I need the following for help with my research in number theory.
Is there a simple(not multistep) iterative method of finding the root of a real-valued ...
- 31
0
votes
0
answers
57
views
Sampling a distribution related to factoring
Consider these two problems.
Given two numbers $a$ and $N$, find the smallest $r$ such that $a^r= 1 \pmod N$.
Given three numbers $a$, $r$, and $N_{max}$, find $N\le N_{max}$ such that $a^r= 1 \pmod ...
- 333
6
votes
3
answers
350
views
How to numerically compute $x \ln x$ and related functions near $0$?
I was recently trying to find a numerical solution to a thermodynamics problem and the expression $x\ln x$ appeared in one of the computations. I did not have to find its value very near $0$, so the ...
- 3,462
1
vote
0
answers
77
views
Minimizer for a certain variational problem
In the process of estimating certain hitting probabilities for Brownian motion I've run into the following variational problem. Let $\mathbb{D}\subseteq{\mathbb{C}}$ be the unit disk in the plane, ...
- 195
0
votes
1
answer
58
views
Maximizing a skew-symmetric 4D cross product
How do I find two orthonormal 4D vectors, $(x_0,x_1,x_2,x_3)$ and $(y_0,y_1,y_2,y_3)$, which maximize this function:
$-19x_1y_0 - 33x_2y_0 + 11x_3y_0 + 19x_0y_1 - 21x_2y_1 - 33x_3y_1 + 33x_0y_2 + ...
- 1,425
4
votes
1
answer
215
views
Singular value decomposition of truncated discrete Fourier transform matrix
Let $\mathbf{F}$ be a discrete Fourier transform (DFT) matrix such that
\begin{align}
F_{m,n}=e^{-j2\pi(m-1)(n-1)/N},\quad m,n=1,\ldots,N.
\end{align}
What we can say about the singular value ...
- 129
0
votes
0
answers
21
views
References for discrete calculus of variations
What would be good references for discrete calculus of variations? For applications such as minimizing a functional not on a $[0,1]\times[0,1]\to \mathbb{R}$ but on a bitmap image that approximates ...
- 1,942
0
votes
0
answers
23
views
Convergence conjugate gradient method
For Conjugate Gradient (to solve a linear system $Ax=b$) there is a theorem: "if $m$ is the number of distinct eigenvalues of matrix $A$, then the Conjugate Gradient method converges at the ...
- 11
4
votes
0
answers
72
views
How can I numerically solve the Laplace equation with cohomological data?
Consider the problem of solving for $u$ where $-\Delta u = f$, $[u] = [g]$ where $[\cdot]$ denotes cohomology class and $u, f, g$ are $p$-forms on a Riemannian manifold $M$. If $g$ instead was ...
- 183
5
votes
3
answers
181
views
closest equidistant point to N points in M dimensions
Is there a formula/algorithm/etc. to find the closest equidistant point (assuming it exists) to a set of points, allowing that the number of dimensions of the space is independent of the number of ...
- 425
0
votes
0
answers
38
views
Padé–Hermite approximants of the exponential of type II
I found the explicit expression of the Padé–Hermite approximants of the exponential function, of type I by complex integrals (see for instance Khémira - Approximants de Hermite–Padé, déterminants
d’...
- 2,997
3
votes
1
answer
173
views
Polynomial and rational approximation of continuous functions in $\mathbb{C}$
I am wondering what the state of the art is for polynomial and rational approximations to continuous/holomorphic functions in $\mathbb{C}$. The particular domains of interest are the closed unit ball $...
- 325
1
vote
0
answers
59
views
Fitting a model
I have a function expressed as the ratio of two exponential series with certain parameters
$$\frac{\sum\limits_{j=1}^{i-1} \frac{e^{-ar_jt}}{\prod_{l=1\\l \ne j}^{i-1} (b^j-b^l)}}{\sum\limits_{j=1}^{i}...
- 35
2
votes
0
answers
44
views
Harmonic function over a square with linear Neumann boundary conditions
For a rectangle with height 1 and length 2, here is the unique numerical solution
(showing contours of the equipotential from 0, defined by the bottom, to 0.54, the numerically-calculated maximum)
to ...
- 1,425
0
votes
1
answer
108
views
Are root finding algorithms stable for bounded polynomials? [closed]
Suppose that we have a bounded polynomial defined on $[0,1]$. I think because it is just polynomial, root finding algorithms would easily and without any instability find all its roots. Am I right?
...
- 113
0
votes
0
answers
62
views
Translating between interpolation vs approximation
tl;dr: Is there a way to translate interpolation error estimates into approximation error estimates for non-interpolating polynomials?
Given a function $f\in L^2(\Omega)$ and a basis $\{\phi_n\}$ for $...
- 17
0
votes
0
answers
42
views
Error estimates for orthogonal polynomial approximation
tl;dr: Are there explicit bounds for the approximation error by orthogonal polynomials?
There are various ways to formulate this question more precisely, so want I emphasize up front that this is a ...
- 17
6
votes
0
answers
187
views
Where to cut off a double sum?
I have to compute a double infinite sum to within a given accuracy $\epsilon$. Let us say the sum is of the form
$$\sum_{m\geq 1} \sum_{n\geq 1} \frac{a_{m,n}}{m^2 n^2 \max(m,n)},$$
where $|a_{m,n}|\...
- 16.7k
2
votes
1
answer
106
views
Is it possible to obtain orthogonal (but not normalized) vectors after QR factorization?
After QR decomposition of a matrix, $M$, the columns of Q are orthonormal. Is it possible after obtaining Q, we recover unnormalized column vectors from $Q$? For example, the matrix M has the ...
- 677
1
vote
0
answers
62
views
Largest nuclear norm of $n \times n$ symmetric matrices whose entries are between -1 and 1
Let $\cal M$ be the set of real symmetric $n \times n$ matrices whose entries are all in the interval $[-1, 1]$. I'm interested in understanding the largest possible nuclear norm of these matrices as ...
- 11
3
votes
1
answer
97
views
Proof of Levinson-Durbin algorithm
Is there any article or reference book with a full proof of the Levinson-Durbin algorithm used for solving linear system with a Toeplitz matrix ?
- 31
1
vote
0
answers
24
views
P1-finite element as convolution of P0-finite element
For a vector $u\in\mathbf{R}^N$ let's denote $\pi_N(u)$ the unique piecwise linear and $1$-periodic function matching the components of $u$ on the discretization $x_k = \frac{k}{N}$ of the unit ...
- 2,058
1
vote
1
answer
143
views
Computing global maximum
For $\lambda\in\mathbb{R}$, I want to find the expression of $f(\lambda)$:
$$f(\lambda)=\max_{E\in\mathbb{C}}arccosh{\frac{|E^2+i\lambda E|+|E^2+i\lambda E-4|}{4}}-arccosh{\frac{|E^2-i\lambda E|+|E^2-...
- 91
1
vote
0
answers
92
views
Numerical calculation of a double integral from the slowly-decaying oscillating function
Let us consider the following integral
$$
I = \int\limits_{0}^{+\infty}dx\int\limits_{-\infty}^{+\infty}dy \left[f(x,y) + g(x,y) \right].
$$
We know several properties of these functions.
There are ...
- 305
2
votes
0
answers
56
views
What are desirable properties that data should satisfy to reasonably use the dynamic mode decomposition?
In the dynamic mode decomposition, we consider a sequence of data vectors $\{z_0, \dots, z_m\}$ where $z_k \in \mathbb{R}^n$ for all $n$. We assume that the data satisfies the linear relationship $z_{...
- 253
1
vote
3
answers
247
views
Determining polynomial approximations of piecewise constant functions
Let $t_1 < t_2 < \cdots <t_m$ be real, and $X = \cup_{i=1}^{m-1} (t_i, t_{i+1})$ be a union of real open intervals. Let $f:X \rightarrow \{-1, 1\}$ be any piecewise constant function of form
...
- 823
1
vote
0
answers
49
views
How does a computer program recognize shocks given data of a solution to a conservation law?
Conservation laws are PDEs of the form $u_t +j_x=0.$ A discontinuous solution (for $u$ and $j$) to an equation like this can be easily found. Let's suppose that we are working with a piecewise ...
- 1,457
2
votes
0
answers
44
views
Is there a generalisation of this perturbation result about rank-one modifications of diagonal matrices?
In Theorem 1 of [1] we have the following result: Let $D$ be a real $n \times n$ diagonal matrix and consider the rank-one modification $C = D + \rho z z^T$, where $\rho > 0$ is a real scalar and $...
- 21
0
votes
0
answers
71
views
Is there an efficient algorithm to project a vector onto the eigenbasis of a symmetric matrix?
Let $H$ be a symmetric matrix over $\mathbb R^n$. Given some vector $u$, I would like to express $u$ in the eigenbasis for $H$. Can this be done efficiently, perhaps using some kind of iterative ...
- 611
0
votes
0
answers
16
views
Coordinate gradient descent in small time-step limit
I'm looking for a reference, proof or intuitive explanation that the $n$-dimensional coordinate-wise gradient descent sequence with step size $h>0$ converges to the $n$-dimensional gradient flow.
...
- 143
0
votes
0
answers
31
views
Polynomial Lagrange splines
Question:
if $x_0 \lt x_1\lt\cdots\lt x_{N-1}\lt x_N$, how can the spline-analogues $\mathscr{L}_i(x)$ of Lagrange polynomials be calculated when they are defined via
$\mathscr{L}_i^n(x)\in C^{n-1}$
$...
- 11k
1
vote
1
answer
80
views
Typo in error a-priori estimate in a discontinuous Galerkin paper?
I'm looking at this famous paper which is available in the link below:
Franco Brezzi, LD Marini, Endre Süli, Discontinuous Galerkin methods for first-order hyperbolic problems, Mathematical Models ...
- 111
0
votes
0
answers
64
views
Why does explicit Runge-Kutta 4 allow positive eigenvalues?
When solving a system of ODEs:
$$\dot{x} = A x,$$
we call the system unstable when the eigenvalues of A have a positive real part.
However, the stability region of the explicit Runge-Kutta 4 method ...
- 17
5
votes
1
answer
142
views
Efficients method for finding a zero of a multilinear complex polynomial in an specified region
Let P be a given multilinear polynomial in $\mathbb{C}[z_1,\dots,z_n]$ and $D\subset \mathbb{C}$ be a given disc in the complex plane. Does there exist an efficient method for checking that $P$ has a ...
- 4,406