Numerical algorithms for problems in analysis and algebra, scientific computation

**4**

votes

**1**answer

407 views

### Hilbert Matrix and Approximation Theory

I was reading about the Hilbert matrix and Cauchy determinants:
\[ \det \left[ \frac{1}{i+j-1} \right]_{i,j} \]
By guessing where this determinant is $0$ or $\infty$ we can guess the right formula. ...

**5**

votes

**0**answers

241 views

### Approximation by polynomials

The following is a well-known theorem (see e.g. The Chebyshev Polynomial by Rivlin):
If $p(x) = x^n + a_{n_1} x^{n-1} + \ldots + a_0$, then $\max_{-1\leq x \leq 1} |p(x)| \geq 2^{1-n}$ for $n \geq 1$ ...

**2**

votes

**1**answer

132 views

### Optimization problem

I'm trying to solve a very practical optimization problem and I think I hit a dead-end.
There are $N$ products ($N \sim 50$). Each product can have a price $p_i$ in range between 1 and 40 dollars. ...

**0**

votes

**1**answer

84 views

### Avoiding epsilon in mixed integer linear and quadratically constrained programs

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$.
$(x = 0 \wedge y = 1) \vee (x \neq 0 ...

**1**

vote

**0**answers

68 views

### Orthogonal projection of discontinuous piecewise polynomial space in energy scalar product

Let $I = [0,1]$ be the unit interval Let $I$ be partioned into $n$ closed subintervals $(I_j)_J$, each of length $1/n$.
Let $X_{DC} = \{ v \in L^2[0,1] | 1 \leq j \leq n : v_{|I_j} \in \mathcal P_1( ...

**9**

votes

**2**answers

635 views

### Rigorous numerical integration

I need to evaluate some (one-variable) integrals that neither SAGE nor Mathematica can do symbolically. As far as I can tell, I have two options:
(a) Use GSL (via SAGE), Maxima or Mathematica to do ...

**0**

votes

**2**answers

196 views

### Proof that polynomial evaluated at roots of unity is DFT [closed]

Hello All,
I hope I am not abusing the forum here.
I am just trying to understand the efficient implementations of the fast fourier transform. My reading and searching has led me to understand that ...

**13**

votes

**1**answer

2k views

### The unreasonable effectiveness of Pade approximation

I am trying to get an intuitive feel for why the Pade approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence. But what I can't ...

**4**

votes

**1**answer

227 views

### best rank r approximation for non-Frobenius norm

The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to Eckart-Young theorem, is truncated SVD - just keep $r$ largest singular values. What if I need to construct best ...

**2**

votes

**2**answers

1k views

### Finding the formula for Bezier curve ratios (hull/point : point/baseline)

Given a cubic Bezier curve defined by points p₁, p₂, p₃, and p₄, a point B on that curve at some t value (where 0 ≤ t ≤ 1), a point A on the line (p₂ — p₃) at distance ratio t from p₂, and a point C ...

**1**

vote

**1**answer

120 views

### Recommendations for binomial system solver

I am interested in solving binomial systems of the form
$$
\begin{cases}
a_1 x_1^{d_{11}} x_2^{d_{12}} \cdots x_n^{d_{1n}} +
b_1 x_1^{d_{11}} x_2^{d_{12}} \cdots x_n^{d_{1n}} &= 0 \\\\
...

**3**

votes

**1**answer

124 views

### approximation methods in integral equations

Recently I was reading about integral equations and I am a beginner in it. There was a constant reference to the non-availability of methods to find the exact solutions and hence lot of approximation ...

**1**

vote

**1**answer

196 views

### How are real-analytic functions encoded in computer algebra?

I would like to know how are encoded the real-analytic functions on the interval by the computers. When I think in a real-analytic function I just think in a composition of the ''typical'' analytic ...

**4**

votes

**1**answer

522 views

### Matrix perturbation theory

I am having matrix $M_0$ with coresponding eigenvectors and 4 eigenvalues {0,0,a,-a}. Eigenvalue $\lambda=0$ is double degenerated. Now I am appliing small perturbation $\epsilon M_1$ and want to get ...

**2**

votes

**0**answers

196 views

### Convergence rate of iterated nonlinear equations?

For $i=1, \dots, n$ ($n$ could be large) we have variables $x_i$ and $y_i$ relating to probability bounds s.t. $x_i, y_i \geq 0, x_i+y_i \leq 1 \; \forall i$. Each $i$ has a constant $\theta_i$, and ...

**2**

votes

**0**answers

171 views

### Heat transfer coefficients - correlation equations for Nusselt number - vertical pipe

I need a heat transfer coefficient applicable to free convection of water INSIDE a vertical pipe. I have the correlation equation from Churchill and Chu, but it is only valid for D/L>=35/Gr^(1/4), ...

**3**

votes

**1**answer

91 views

### Kronecker-structured matrix kernel

Let $A,B\in\mathbb{C}^{n\times 3n}$ be two matrices, and denote the Kronecker matrix product by $\otimes$. The matrix
$$
M=
\begin{bmatrix} A \otimes I_n \\\\ I_n \otimes B\end{bmatrix}
$$
has size ...

**2**

votes

**1**answer

213 views

### Approximation theory under $L_1$-error

Is there a reference for results in approximation theory of bounded functions of one (and multiple) variables under $L_1$-error?
Formal definitions for functions of one variable are below.
Let $C$ ...

**2**

votes

**0**answers

132 views

### Radius of convergence to be proved more precisely (differential equation)

There is a differential equation in polar coordinates:
$r'^2+r^2=(kt)^2$, $r(t=0)=0$, k- Const.
It is possible to get a solution which is a power series (see below). However, I am looking for an ...

**3**

votes

**1**answer

280 views

### Lebesgue constant as condition number of polynomial interpolation

Let $T = \{ x_0,\ldots,x_n \}$ be a set of $n+1$ different points in the real interval $[a,b]$. Let $X_T$ be the associated interpolation operator on $C[a,b]$: it takes a function $f \in C[a,b]$ into ...

**4**

votes

**1**answer

820 views

### Smoothing L1 norm, Huber vs Conjugate

I'm trying to minimize a convex (not necessarily strictly convex) function involving an L1 norm (similar to lasso), which makes it non-differentiable at some points. So I'd like to smooth it and treat ...

**4**

votes

**0**answers

47 views

### Recovering Shared Eigenvector Set

Suppose we are given a set of $M$ pairs $\{(\vec{x}^{(i)},\vec{y}^{(i)})\}$, with
$\vec{x}^{(i)}\in\mathbb{R}^N$,
$\vec{y}^{(i)}\in\mathbb{R}^N$,
$M\gg N$ such that
$\vec{y}^{(i)} = Q^{(i)} ...

**6**

votes

**2**answers

706 views

### Approximating erf by tanh

It appears to be well-known that $\tanh(x)\le \mathrm{erf}(x)$ on $[0,\infty)$. It's off-handedly mentioned here, for example. Where can I find a formal proof? On the one hand, it's hard to imagine ...

**2**

votes

**0**answers

125 views

### integrate square of bessel 1st and 2nd kind

Has anyone ever solved the integral of square of Bessel and Neumann functions? This is for standing wave analysis on a cylindrical object.
I need to integrate $(AJ(kr) + BY(kr))^2$ from $r=a$ to ...

**1**

vote

**0**answers

75 views

### Integrating B-Spline composed with log

If $f$ is a real B-Spline and $a, b$ are real numbers, then is there a numerically stable way to evaluate the following expression?
$\int_a^b f (\log x) \mathrm{d}x$

**16**

votes

**3**answers

840 views

### Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute
$f(x)$. The input consists of the digits of $x$ and the output of
a rational number approximating $f(x)$. A function $f$ is called ...

**5**

votes

**0**answers

139 views

### Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi,
my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$.
The matrix $C$ is huge ($n$ up to a ...

**13**

votes

**2**answers

297 views

### Condition number of matrix after partial orthogonalization

I'm wondering about which bounds one can put on the condition number of
a $n\times n$ square matrix which is obtained from another $n\times n$
square matrix by orthogonalizing the first $m < n$ ...

**3**

votes

**0**answers

137 views

### Upper bound on integrals of Legendre polynomials

Hi,
If $P_n(x) $ is unnormalized shifted Legendre polynomial, and $g_{n,m}(x) = \int_0^x P_n(x_1)x_1^m dx_1, n>m $ then what is the upper bound $ |g_{n,m} (x)|_{max} , x\in (0,1) $ as a function ...

**5**

votes

**0**answers

420 views

### Parabolic cylinder functions - explicit estimates?

I need estimates for the parabolic cylinder functions $U(a,z)$ (first studied by Whittaker).
Most work in the literature focuses on $a$ real. As it happens, I am interested in $U(a,z)$ on a strip in ...

**7**

votes

**2**answers

312 views

### How to solve a system of linear equations without storing the matrix?

I have a procedurally defined Hermitian matrix $M$, i.e. I can get any matrix element by calling a black box function (e.g. a library function), and a vector $Y$. And I have to solve a system of ...

**4**

votes

**4**answers

786 views

### When we use Bernstein polynomials in application

When it is preferable to use Bernstein polynomials to approximate a continuous function instead of using the only following preliminary Numerical Analysis methods: "Lagrange Polynomials", "Simple ...

**1**

vote

**0**answers

99 views

### Matrix Minimax problem

I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The ...

**0**

votes

**0**answers

26 views

### Problem with the convergence of a Nystrom algorithm

I programmed a Nystrom Algorithm specifically for my problem:
This is the exact equation i want to solve:
$y''=(w^2-e*cos(t))*sin(t)-b*y'$
And this is my algorithm
...

**1**

vote

**1**answer

150 views

### An upper bound on a simple sum

Hi,
I am trying to put a bound on a sum. Given $\omega=\exp(2\pi i/3)$ and $n$ positive real numbers
$ 0=\tau_0 < \tau_1 < \tau_2 < ...\tau_{n-1}< \tau_n=1 $
such that
...

**4**

votes

**1**answer

311 views

### Norm of inverse confluent Vandermonde matrix

Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as
$$V=
\begin{bmatrix}
...

**2**

votes

**0**answers

135 views

### Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...

**0**

votes

**0**answers

138 views

### How to interpolate in 3-D non-euclidean space?

Assume, one has a 3-D non-euclidean space of points $p_i = \left(x_i, y_i, z_i\right) \in \mathcal{R}^2 \times \mathcal{R}_{> 0}$ with the following "distance" function $d\left(p_1, p_2\right) = ...

**1**

vote

**1**answer

262 views

### Books on Numerical Methods for Partial Differential Equations

Any good references for undergraduates?

**4**

votes

**1**answer

483 views

### Solution of Helmholtz-Equation where Phase is restricted by additional PDE

Hello!
Let's say I have
$(\partial_x^2 + \partial_y^2 + a)f(x,y)=0$
with $f(x,y) \in \mathbb{C}$, ($\lim_{x,y \to \infty} f(x,y)=0$).
Now separate the Amplitude and Phase of the solution:
...

**6**

votes

**1**answer

150 views

### Algorithm for numerically approximating the Prokhorov metric?

Question: What is known about algorithms for numerically computing/approximating the Prokhorov distance between two measures?
Recall that the Prokhorov distance metrizes the topology of weak(-*) ...

**8**

votes

**7**answers

2k views

### Any good books on numerical methods for ordinary differential equations?

I need to find some masters-level exercises about numerical methods for solving ODEs. Are there any good references?

**5**

votes

**1**answer

1k views

### Upper bound on largest eigenvalue of a real symmetric n*n matrix with all main diagonal >0, everywhere else <=0

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 ...

**1**

vote

**2**answers

315 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 ...

**1**

vote

**2**answers

262 views

### Delauney triangulation in high (>20) dimensions

Hi all,
I know that its very hard to find the Delauney triangulation of high dimensional spaces, especially if there are several thousand points that need to be triangulated.
So I was wondering . . ...

**1**

vote

**3**answers

320 views

### What software one needs to solve a big linear system on a small computer?

A time ago I was intrigued by the following remark:
"... one ends up with a (non-sparse) system of equations in
about 10000 real variables. One important practical point is
that solving such systems ...

**4**

votes

**1**answer

218 views

### Most orthogonal lattice basis

Let $n \in \mathbf{N}$ be a natural number and $v_1,\cdots,v_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}_n(\mathbb{Z})$ orthogonalizing these best ...

**0**

votes

**1**answer

254 views

### Solving system of nonlinear equations

Dear all,
Can anyone tell me all the algorithms that are available for finding all solutions of a system of nonlinear equations?
I am particularly interested in solving problems of the form:
...

**0**

votes

**1**answer

401 views

### Global Error Analysis of Euler's Method

I know that the local error at each step of Euler's method is O(t^2), where t is the time step. And since there are (b-a)/t steps, the order of the global error is O(t).
However, I saw a derivation ...

**2**

votes

**0**answers

161 views

### fast multipole method and geometric algebra

Hello,
I just learned about fast multipole method(FMM) from this article http://math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf and I really liked the use of complex numbers in 2d. But I didn't ...