Questions on numerical analysis/numerical methods; methods for approximately solving various problems that often do not admit exact solutions.

learn more… | top users | synonyms (2)

22
votes
7answers
11k views

Simple numerical methods for calculating the digits of $\pi$

Are there any simple methods for calculating the digits of $\pi$? Computers are able to calculate billions of digits, so there must be an algorithm for computing them. Is there a simple algorithm that ...
23
votes
2answers
728 views

Calculating $\lim_{n\to\infty}\sqrt{n}\sin(\sin…(\sin(x)..)$

I was asked today by a friend to calculate a limit and I am having trouble with the question. Denote $\sin_{1}:=\sin$ and for $n>1$ define $\sin_{n}=\sin(\sin_{n-1})$. Calculate ...
12
votes
4answers
5k views

Gradient Descent with constraints

In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method: $$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$ where $\alpha_k$ is the step size ...
2
votes
2answers
477 views

Relation of cubic B-splines with cubic splines

Does anyone know the relation between the cubic B-splines and cubic splines?
28
votes
3answers
10k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
8
votes
4answers
3k views

How to accurately calculate the error function erf(x) with a computer?

I am looking for an accurate algorithm to calculate the error function I have tried using [this formula] (http://stackoverflow.com/a/457805) (Handbook of Mathematical Functions, formula ...
7
votes
6answers
5k views

Algorithm to compute Gamma function

The question is simple. I would like to implement the Gamma function in my calculator written in C; however, I have not been able to find an easy way to programmatically compute an approximation to ...
4
votes
3answers
1k views

What is step by step logic of pinv (pseudoinverse)?

So we have a matrix $A$ size of $M \times N$ with elements $a_{i,j}$. What is a step by step algorithm that returns the Moore-Penrose inverse $A^+$ for a given $A$ (on level of ...
6
votes
1answer
1k views

Levin's u-transformation

Suppose I'm given a very slowly converging sequence $\sum_k a_k$. In the literature, the Levin u-transformation is mentioned as a good universal technique for convergence acceleration. I have ...
308
votes
7answers
12k views

“The Egg:” Bizarre behavior of the roots of a family of polynomials.

In this MO post, I ran into the following family of polynomials: $$f_n(x)=\sum_{m=0}^{n}\prod_{k=0}^{m-1}\frac{x^n-x^k}{x^m-x^k}.$$ In the context of the post, $x$ was a prime number, and $f_n(x)$ ...
41
votes
10answers
2k views

What is the fastest/most efficient algorithm for estimating Euler's Constant $\gamma$?

What is the fastest algorithm for estimating Euler's Constant $\gamma \approx0.57721$? Using the definition: $$\lim_{n\to\infty} \sum_{x=1}^{n}\frac{1}{x}-\log n=\gamma$$ I finally get $2$ decimal ...
45
votes
3answers
1k views

How much does symbolic integration mean to mathematics?

(Before reading, I apologize for my poor English ability.) I have enjoyed calculating some symbolic integrals as a hobby, and this has been one of the main source of my interest towards the vast ...
8
votes
2answers
2k views

How to evaluate Riemann Zeta function

How do I evaluate this function for given $s$? $$\zeta(s) = \sum_{n=1}^\infty \frac1{n^s} = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \cdots$$
19
votes
8answers
3k views

Rapid approximation of $\tanh(x)$

This is kind of a signal processing/programming/mathematics crossover question. At the moment it seems more math-related to me, but if the moderators feel it belongs elsewhere please feel free to ...
5
votes
1answer
2k views

Variational formulation of Robin boundary value problem for Poisson equation in finite element methods

So I am confused about some details of obtaining a variational formulation specifically for Poisson's equation. I am in a Scientific Computing class and we just started discussing FEM for Poisson's ...
13
votes
4answers
1k views

Detecting perfect squares faster than by extracting square root

Given the radix-$r$ representation of a integer $n$, and a small integer constant $k$, there is an $O(\log n)$ algorithm for detecting whether $n$ is a multiple of $k$, namely, division, which ...
9
votes
2answers
869 views

Minimum of the Gamma Function $\Gamma (x)$ for $x>0$. How to find $x_{\min}$?

The $\Gamma (x)$ function has just one minimum for $x>0$ . This result uses some properties of the gamma function: $\Gamma ^{\prime \prime }(x)>0$ and $\Gamma (x)>0$ for all $x>0$ $\Gamma (1)=\Gamma ...
6
votes
6answers
2k views

An alternative way to calculate $\log(x)$

How can I replace the $\log(x)$ function by simple math operators like $+,-,\div$, and $\times$? I am writing a computer code and I must use $\log(x)$ in it. However, the technology I am using does ...
3
votes
2answers
3k views

Implementation of Monotone Cubic Interpolation

I'm in need to implement Monotone Cubic Interpolation for interpolate a sequence of points. The information I have about the points are x,y and timestamp. I'm much more an IT guy rather than a ...
6
votes
2answers
458 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
3
votes
2answers
997 views

Trapezoid rule error analysis

How can I prove that the max error of the trapezoid rule for the integral $\int_{a}^{b}{f(x)\, \mathrm{d}x} $ is: $$\Delta=-\frac{1}{12n^2}f''(c)(b-a)^3 \text{for } c \in (a,b) \ ?$$ I know that to ...
2
votes
3answers
192 views

How to calculate the square root of a number? [duplicate]

By searching I found few methods but all of them involve guessing which is not what I want. I need to know how to calculate the square root using a formula or something. In other words how does the ...
1
vote
2answers
91 views

How to prove the eigenvalues of tridiagonal matrix?

Assume the tridiagonal matrix $T$ is in this form: $$ T = \begin{bmatrix} a & c & & & &\\ b & a & c & ...
4
votes
2answers
300 views

Plotting graphs using numerical/mathematica method

From the author's equation 13, 14 We can write by inserting V''(A)=0, Solving for R we get, $$R= \frac{6^{D/4} \sqrt{D}}{\sqrt{-2^{1+\frac{D}{2}} 3^{D/2}+3 2^{1+D} A-3^{1+\frac{D}{2}} A^2}}$$ Now ...
2
votes
1answer
441 views

Roots of a finite Fourier series?

In general, are there any clever tricks to help find the roots of a finite Fourier series? Presumably there aren't analytic methods, but can we use the fact that our function is a finite Fourier ...
1
vote
1answer
459 views

LU decomposition that is not unique

How can I show that every matrix of the form $\begin{bmatrix}0& x\\0 & y\end{bmatrix}$ has an $LU$ factorization and that even if $L$ is unit lower triangular there is not a unique ...
1
vote
1answer
173 views

Floating point arithmetic

How can I prove that : a real number has a finite representation in the binary system if and only if it is of the form $$\pm \frac{m}{2^n}$$ where n and m are positive integers.
0
votes
1answer
88 views

The order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$

Let $g(x)=0.5(x+a/x)$. Determine the order of convergence and the asymptotic error constant of the sequence $p_n=g(p_{n-1})$ toward $x=a^{.5}$. This is a problem in our homework in the class ...
0
votes
1answer
2k views

estimating the error of $\sin(x) = x$ with Taylor's Theorem

I want to calculate the numerical error in approximating $\sin(x)=x$ with Taylor's Theorem. Furthermore, what values of $x$ will this approximation be correct to within $7$ decimal places? Here is ...
97
votes
1answer
11k views

Proof that ${\left(\pi^\pi\right)}^{\pi^\pi}$ (and now $\pi^{\left(\pi^{\pi^\pi}\right)}$) is a noninteger

Conor McBride asks for a fast proof that $$x = {\left(\pi^\pi\right)}^{\pi^\pi}$$ is not an integer. It would be sufficient to calculate a very rough approximation, to a precision of less than 1, and ...
66
votes
23answers
13k views

Why do we still do symbolic math?

I just read that most practical problems (algebraic equations, differential equations) do not have a symbolic solution, but only a numerical. Numerical computations, to my understanding, never deal ...
23
votes
5answers
4k views

How do you calculate the decimal expansion of an irrational number?

Just curious, how do you calculate an irrational number? Take $\pi$ for example. Computers have calculated $\pi$ to the millionth digit and beyond. What formula/method do they use to figure this out? ...
32
votes
1answer
612 views

What's the most efficient way to mow a lawn?

For $S\subseteq\Bbb R^2$ and $x\in\Bbb R$, define $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ represents the expansion of $S$ by $x$.) Given a path $\gamma:[0,1]\to\Bbb R^2$, denote its length as ...
10
votes
2answers
2k views

Why does Newton's method work?

I find many sites explaining how to use Newton's method, but none explaining why it works. Could someone give me the intuition behind it? Thanks.
14
votes
5answers
6k views

Calculate logarithms by hand

I'm thinking of making a table of logarithms ranging from 100-999 with 5 significant digits. By pen and paper that is. I'm doing this old school. What first came to mind was to use $\log(ab) = ...
11
votes
1answer
1k views

Iterative refinement algorithm for computing exp(x) with arbitrary precision

I'm working on a multiple-precision library. I'd like to make it possible for users to ask for higher precision answers for results already computed at a fixed precision. My $\mathrm{sqrt}(x)$ can ...
5
votes
2answers
1k views

Numerical Approximation of the Continuous Fourier Transform

Given a function $F(k)$ in frequency space (sufficiently nice enough, eg. a Gaussian), I would like to compute its Fourier inverse \begin{equation}f(x) = ...
4
votes
1answer
1k views

Method for estimating the $n^{th}$ derivative?

When using numerical analysis, I often find that I am required to estimate a derivative (e.g. when using Newton Iteration for finding roots). To estimate the first derivative of a function $f(x)$ at ...
1
vote
6answers
2k views

How to calculate square root or cube root? [duplicate]

I was reading Richard Feynman biography when I read that one time he was able to calculate the cube root of large number in his brain by just using simple facts of everyday life. So my question is ...
16
votes
4answers
7k views

Determining whether a symmetric matrix is positive-definite (algorithm)

I'm trying to create a program, that will decompose a matrix using the Cholesky decomposition. The decomposition itself isn't a difficult algorithm, but a matrix, to be eligible for Cholesky ...
4
votes
4answers
1k views

Finding all complex zeros of a high-degree polynomial

Given a large univariate polynomial, say of degree 200 or more, is there a procedural way of finding all the complex roots? By "roots", I mean complex decimal approximations to the roots, though the ...
2
votes
1answer
4k views

Orthogonal polynomials and Gram Schmidt

How can we use the Gram Schmidt procedure to calculate $L_0,L_1, L_2, L_3$, where ${L_0(x), L_1(x), L_2(x), L_3(x)}$ is an orthogonal set of polynomials on $(0, \infty)$ w.r.t. the weight function ...
4
votes
1answer
315 views

Series expansion for iterated function

I would like to find the MacLaurin expansion of an iterated function. Finding the first few terms is not hard, but it doesn't take long before Mathematica runs out of memory using the straightforward ...
6
votes
2answers
7k views

Is a non-repeating and non-terminating decimal always an irrational?

We can build $\frac{1}{33}$ like this, $.030303$ $\cdots$ ($03$ repeats). $.0303$ $\cdots$ tends to $\frac{1}{33}$. So,I was wondering this: In the decimal representation, if we start writing the ...
5
votes
2answers
3k views

How can I calculate non-integer exponents?

I can calculate the result of $x^y$ provided that $y \in\mathbb{N}, x \neq 0$ using a simple recursive function: $$ f(x,y) = \begin {cases} 1 & y = 0 \\ (x)f(x, y-1) & y > 0 \end ...
4
votes
1answer
418 views

Approximating Lambert W for input below 0

As a small part of a much bigger project, I need to be able to approximate the numerical output of the Lambert W function. I have found decent approximations (good up to at least 4 decimal places), ...
2
votes
1answer
46 views

Singular value decomposition of column & row vectors

(a) Given the column vector $a$ as an $n\times 1$ matrix. Write out its singular value decomposition, showing the matrices $U, \sum$, and $V$ explicitly. (b) Given the row vector $a^T$ as an $1\times ...
2
votes
1answer
107 views

I would like a hint in order to prove that this matrix is positive definite

Let $a_{ij}$ be a real number for all $i,j\in\{1,...,n\}$. Consider the matrix below. $$B=\begin{bmatrix} \sum_{k=1}^n(a_{1k})^2 & \sum_{k=1}^na_{1k}a_{2k} & \cdots & ...
2
votes
1answer
1k views

Polynomial root finding

I have an univariate polynomial of some degree - how do I numerically find all of its real roots? I never thought I would ask this question - everyone knows how to find polynomial roots, right..? ...
2
votes
2answers
304 views

Solving short trigo equation with sine - need some help!

From the relation $M=E-\epsilon\cdot\sin(E)$, I need to find the value of E, knowing the two other parameters. How should I go about this? This is part of a computation which will be done quite a ...