Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

7
votes
3answers
379 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 ...
2
votes
0answers
42 views

Compute the smoothing of functions

Given a function $g:R^d\rightarrow R$, which is not necessarily continuous, I want to compute the "smoothing" of $g$, i.e., $G(\vec{y})=\int_{R^n} g(\vec{x}) f_{\vec{y}, \sigma}(\vec{x}) d\vec{x} $ ...
0
votes
0answers
80 views

Generalized arithmetic progressions contained in Bohr sets

Recall that generalized arithmetic progression of dimension $d$ is by definition a set of the form $P = P_1+\dots+P_d$, where $P_j = \{lp_j\ \mid \ |l|\leq l_j\}\subset \mathbb Z$ is an ordinary ...
5
votes
1answer
153 views

Computing Gauss Legendre Quadrature for Large N

I've been scanning across the web, and haven't found a good method to compute the Gauss Legendre abscisas and weights $\{ x_j, w^j \} _j$ for large N. My question is how to do it, and why should it ...
1
vote
0answers
21 views

LU growth factor applied to LDL of a Positive Semidefinite matrix [closed]

For a Positive Semidefinite matrix $A$, which we can decompose through $LDL$ decomposition as follows: $A=LDL^\text{T}$; how can we prove that for a decomposition $A=LU=L(DL^\text{T})$, the growth ...
4
votes
0answers
57 views

Numerical integration error bounds on the unit sphere

A sequence of points $x_1,x_2,\dots$ on the unit sphere $S^{D-1}$ is said to be uniformly distributed if \begin{align} \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{j=1}^N f(x_j) = \int_{x \in ...
0
votes
0answers
33 views

Global optimisation of the real part of impedance

I have the following global optimisation problem: $$ \underset{\omega}{\min}-c^{T}\left(\omega^{2}\mathbf{1}+A^{2}\right)^{-1}b $$ where $A$ is a $n \times n$ real matrix, $c$ and $d$ are ...
2
votes
1answer
67 views

The bubble function

In the finite element method and more precisely the MINI element method in two dimensions, they use a function called the "bubble function" which is related to a triangle K of the space meshing and is ...
0
votes
1answer
66 views

Upper bound for a ratio of modified Bessel functions

I am looking for an upper bound for the ratio of Bessel I functions $\dfrac{|I_\nu'(z)|}{|I_\nu(z)|}$ where $\nu$ is complex, and $z$ is a positive real number. Do you know any results about it? Thank ...
9
votes
1answer
205 views

What happens to continuous spectrum upon discretization?

Excuse me for a bit of an vague question, but I haven't been able to find a definite answer for this for quite some time. My question is regarding (mostly non-normal )linear operators and their ...
2
votes
0answers
34 views

Global error estimates for numerical solutions of ODEs in Matlab or Mathematica [closed]

I need to find the first zero (smallest positive root) of the solution of the initial value problem $ry''+y'+f(r)y=0, \ \ y(0)=y'(0)=1$ for certain $f \in C^{\infty}(R)$. One can easily use ...
2
votes
1answer
72 views

Relation between Chebyshev Interpolation and Expansion

I am seeking connections between pointwise Lagrange interpolation (using Chebyshev-Gauss nodes) and generalized series approximation approach using Chebyshev polynomials. Pointwise Lagrange ...
2
votes
0answers
29 views

Estimating overshoot in spline interpolation

Say I have a spline space $\mathcal S$ of dimension $n$ with a set of unisolvent points $(\xi_i)_{i=1}^n$, i.e., points at which I can unambiguously interpolate within the spline space. So, given ...
0
votes
0answers
51 views

inflow/outflow Boundary Conditions for flow in pipe

I have a question about boundary condition of solving Navier-Stokes equation through pipe. When I simulate the flow in pipe using periodic boundary condition, it works good. But when I tried to change ...
3
votes
2answers
159 views

What are interesting heuristics of determining how far given matrix is from a singular one?

The condition number and volume of matrix (defined as absolute value of its determinant) are things which come to mind. Is there more? I think that over the years numerical folks (who are faced with ...
5
votes
0answers
96 views

Hyperbolic toral automorphisms, and maximizing over orbits the minimum along an orbit of a function

Setup: Let $\phi\colon T^2 \to T^2$ be a hyperbolic toral automorphism. Let $f\colon T^2 \to \mathbb{R}$ be a continuous function. For $x \in T^2$, let $\underline{f}(x) = \inf_{n \in \mathbb{Z}} ...
9
votes
4answers
521 views

Rounding errors in images of Julia sets

One typically computes Julia sets by iterating a complex function, such as a polynomial or rational function. How do rounding errors affect the results? I'm looking for references on this issue, ...
2
votes
1answer
98 views

cohomology algebra of submanifold in euclidean space

If we write a manifold or CW-complex $X$ as a subset of $\mathbb{R}^n$, in expression of coordinates, for example, \begin{multline} F(S^2,k+1)=\{(x_1,x_2,x_3,\cdots, ...
6
votes
4answers
366 views

Expected value of a function over random sets

I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows: Pick $k$ distinct numbers out of numbers ...
0
votes
0answers
47 views

volterra equation of the first kind with K(0,t)=0

A standard assumption both in theory and numerical methods for the Volterra equation of the first kind $$ g(t) = \int_0^t K(s,t) f(s) ds$$ is that $K(s,t) \neq 0$. One can show existence of the ...
4
votes
2answers
128 views

Accuracy of the formulas for angles between almost colinear vectors

Assume $x$ and $y$ are two vectors in $\mathbb{R}^3$ and we want to compute the acute angle $\alpha\in(0,\pi/2]$ between these two (noncolinear) vectors. There are (at least) two possibilities: In ...
4
votes
1answer
51 views

Numerical approximation to the Wasserstein metric?

Are there numerical methods for approximating/calculating the Wasserstein metric in particular cases? Suppose that $f$ and $g$ are two density functions with the same support. How can I calculate the ...
0
votes
0answers
43 views

Orthogonalization technique after cosparse dictionary update

I'm trying to adapt the cosparse dictionary learning (DL) approach described in Analysis K-SVD to a DL method that creates the dictionary as a union of orthonormal blocks (UONB). For this I apply the ...
0
votes
0answers
34 views

Smoothness of linear equation

Suppose $\beta$ is a solution to some linear equation $ M \beta = f$ where $M$ is lower triangular with all negative entries except for the diagonal and first sub-diagonal where all entries are ...
0
votes
0answers
46 views

Bits of precision matrix reconstruction

We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$. Suppose we have diagonalized using $LMR=D$. I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of ...
3
votes
1answer
143 views

Monte Carlo integration of Gaussian integrals

I was doing a physical problem, and then it comes to this Gaussian integral. The dimension of the integral is very large (dimension = 300~600), and it is difficult to find the maximum of the ...
1
vote
1answer
97 views

What is a one-parameter Newton's method?

The Newton's method that I know is defined as follows: $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$ However, I've recently encountered a paper that talks about a one-parameter family of Newton's method ...
0
votes
1answer
96 views

Generating random variables from the Cantor Distribution [closed]

I am looking for a method (exact, if possible, but at least asymptotically correct) for generating random variates from a Cantor Distribution? It seems like its abstract definition prevents this. In ...
0
votes
0answers
20 views

Column Subset Selection implementations

Are there readily available implementations of algorithms for the CSSP - Column Subset Selection Problem?
0
votes
0answers
37 views

Comparing Calculation Error in Divergent Numerical Methods

I'm not an expert in numerical methods, but I'm doing a simulation based on non-linear differential equations (General Relativity), there solutions has singularities, thus at some points numerical ...
0
votes
1answer
80 views

What is exponentially fitted osculating straight line?

While reading an article about iterative methods for solving nonlinear equations I can't understand what is exponentially fitted osculating straight line. Could someone please briefly explain this ...
3
votes
1answer
223 views

Analytic Solution to SDEs

Are there any example of SDEs with constant diffusion terms, other than the Ornstein Uhlenbeck process, which have exact solutions? I'm thinking of something of the form: \begin{equation} dX_t = ...
-2
votes
1answer
191 views

BDF2 and TR-BDF2: what is better? [closed]

What method of numerical solving ODEs is better? BDF2 or TR-BDF2? Namely, what advantages has TR-BDF2 over BDF2? Is TR-BDF2 more accurate? Does it damp "ringing" better? The BDF2 method requires the ...
0
votes
0answers
27 views

non-coherent estimation problem

I have the following signals $$\left[\begin{array}{c} y_{mn} \\ y_{nm}\end{array}\right] =\left[\begin{array}{c} x_{n} \\ x_{m}\end{array}\right]h_{nm} +\left[\begin{array}{c} e_{mn} \\ ...
7
votes
1answer
196 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 ...
0
votes
0answers
75 views

Eigenvalue problem (finite difference operator)

Consider an arbitrary elliptic (perhaps, degenerate) finite difference operator $$L_{i,j,k}=-\Delta_{i,j,k}+\alpha_{i,j,k}\frac{\partial}{\partial x}_{i,j,k}+\beta_{i,j,k}\frac{\partial}{\partial ...
0
votes
0answers
44 views

Shooting method for non-oscillatory solutions

I am having some trouble with using the shooting method : I am given a system of ode's representing initial value problem, and I know I want one of the unknowns (=u) to vanish at infinity (which I ...
1
vote
1answer
122 views

Divergence of the Lagrange interpolation on the Chebyshev nodes

Faber theorem states that for every $\lbrace x_k^{(n)} \rbrace$ there exists a continuous $f$ function such that $\| f - L_n \|_{\infty} \not\rightarrow 0$, where $L_n$ is interpolation polynomial on ...
0
votes
1answer
126 views

A kind of Discrete Fourier Transform

Given a $z\in \mathbb{C}^N$, the DFT of $z$ is given for every $k\in [0,N-1]_\mathbb{N}$ by $$DFT_z(k)=\frac{1}{N} \sum_{j=0}^{N-1} z_j\, \omega^{-k j}$$ where I have denoted by $\omega$ the $N$-th ...
0
votes
0answers
134 views

$Ax=b$ in a function space (again)

Let $X$ be compact Hausdorff topological space, $C(X)$ denote the algebra of complex-valued continuous functions on $X$, $b\in \mathbb{C}^m$, $\mathbf{A}\in C(X)^{m\times n}$, Let ${\mathbb{C}}^n$ ...
0
votes
0answers
31 views

Multiple integral of the resolvent kernel

I am trying to implent Volterra equations using resolvent kernel.To do this, the iterative kernel $$K_i(x,y) = \int\limits_x^y K_1(y,t)K_{i-1}(t, x)dt. $$ should be calculated. However, it is not ...
1
vote
1answer
40 views

Convergent algorithm for dividing a body into two regions of equal volume

Let $\Omega \subset R^3$ be a bounded open region. It is well known that there exists a smooth surface $\Gamma$ with minimum area and constant mean curvature which is orthogonal to $\partial \Omega$ ...
1
vote
1answer
218 views

Residues and values of Riemann Zeta function at some points

I need the following computational results for proving something. Let $1/2 + i\gamma_0$, be the first nontrivial zero of Riemann zeta function, $\zeta(s)$, i.e. $\gamma_0\sim 14.134...$. 1) what is ...
0
votes
0answers
56 views

Rational dynamical system with nonnegative paramaters

let $A$ be a rational system of the form :$\begin{cases} x_{n+1}=\frac{\alpha_{1}}{y_{n}} \\ y_{n+1}=\frac{\alpha_{2}}{z_{n}} \\ ...
2
votes
0answers
106 views

error estimate of linear interpolation in high dimension

Consider convex functions $f,g$ on $[0,1]^d$. Let $x_1,\cdots,x_n$ be $n\geq d+1$ fixed point in $[0,1]^d$ that is equally 'distributed' in the sense that $$c_1\leq ...
4
votes
1answer
173 views

Resolvent of a triangular matrix

Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$? Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the ...
0
votes
0answers
40 views

Bound on change of function given bound on Hessian

Suppose I have very some smooth function $F(x)$, and let $x_0 = \text{argmin}_x F(x)$. I would like to bound $F(x) - F(x_0)$ from above, in terms of the gradient $\nabla f(x)$ and the Hessian matrix ...
-2
votes
2answers
58 views

Systems of ODEs that fulfill a matrix relationship at steady state [closed]

It is well known that for a system of linear ODE $$x'(t) = A(t) \cdot x(t) + b(t)$$ with initial condition $x(t_0) = x_0$, that for a solution at any other time point $t_1$, $x(t_1) = (z_1, \ldots, ...
3
votes
0answers
55 views

Estimating polynomial approximation error in high dimension

Question Let $x \in [-1, 1]^d \subset \mathbb{R}^d$ be a $d$-dimensional variable and assume that -- given $n$ -- I have a way of computing a polynomial $p_n(x)$ of degree $n$ that approximates a ...
0
votes
0answers
34 views

Probability of close approach for multivariate normal variables

The following problem comes from a physical model of two groups of particles in three dimensions. I need to know the probability that the two groups of particles approach each other within some ...