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)

16
votes
6answers
9k 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 ...
12
votes
4answers
4k 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
327 views

Relation of cubic B-splines with cubic splines

Does anyone know the relation between the cubic B-splines and cubic splines?
26
votes
3answers
8k 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 ...
6
votes
5answers
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 ...
23
votes
2answers
667 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 ...
4
votes
3answers
857 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 ...
277
votes
7answers
7k 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 ...
42
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 ...
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
6answers
1k 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 ...
6
votes
2answers
434 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 ...
2
votes
3answers
159 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 ...
2
votes
2answers
755 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 ...
4
votes
2answers
290 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 ...
1
vote
1answer
358 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
143 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
68 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
236 views

Consider Van der Pol’s equation:

Consider Van der Pol’s equation: $$y′′−0.2(1−y^2)y′+y=0,\qquad y(0)=0.1,\ y′(0)=0.1$$ (i) Find the approximate solution for this problem using the Taylor series method. Your expansion should include ...
0
votes
1answer
1k 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 ...
92
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 ...
23
votes
5answers
3k 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? ...
14
votes
5answers
5k 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 ...
9
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.
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 ...
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
825 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 ...
16
votes
4answers
6k 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
1answer
298 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 ...
5
votes
2answers
2k 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
386 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
106 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
296 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 ...
1
vote
2answers
83 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 & ...
1
vote
2answers
1k views

How did people calculate numerical values of transcendental and trigonometric functions?

I know that back in the Stone Age, people used tables on this thing called paper to look up values for functions like $\sin$ and $\ln$. But how did the guys who wrote the tables calculate those ...
0
votes
1answer
60 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
0
votes
1answer
2k views

Rate of convergence of modified Newton's method for multiple roots

I've got a problem with a modified Newton's method. We've got a function $f \in C^{(k+1)}$ and $r$ which is it's multiple root of multiciplity $k$. Also $f^{(k)}(r) \neq 0$ and $f'(x) \neq 0 $ in the ...
8
votes
1answer
320 views

PDE - Feynman-Kac vs. finite difference methods

I've heard that in greater than three dimensions, it's more efficient to solve a second-order parabolic PDE using a Monte-Carlo method based on the Feynman-Kac formula that it is to use finite ...
6
votes
2answers
934 views

How do you determine the closest whole number ratio for a given real number?

I've been messing around with formulas for musical notes (trying not to read anything that would help me unless I get stuck) and currently I'm at a point where I'm trying to get a function that ...
6
votes
1answer
95 views

Formula for straight part of a slightly bumpy line

Given a straight line that deviates from the horizontal by at most 15 degrees. On this straight line there are bumps on top at random places on the line. The combined width of the bumps is at most ...
6
votes
3answers
697 views

Numerically estimate the limit of a function

Is there an algorithm that will allow me to numerically compute the limit of a function f(x) in a principled way? The most naive algorithm would be to continue to compute the function for larger ...
4
votes
0answers
238 views

A late-diverging “approximating solution” for a system of functional equations

Peace be upon you, At the end of this question, I have shown that how computing MLE on an i.i.d Beta distributed data, results in the following system \begin{align*} &\begin{cases} ...