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)

23
votes
7answers
12k 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 ...
24
votes
2answers
761 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
6k 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 ...
8
votes
4answers
4k 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 ...
4
votes
2answers
644 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
12k 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 ...
15
votes
5answers
2k 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 ...
7
votes
6answers
6k 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 ...
47
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 ...
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 ...
7
votes
7answers
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 ...
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 ...
2
votes
3answers
277 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
1answer
204 views

How does one calculate the amount of time required for computation?

For example, to compute the zeroes of the Riemann zeta function using the Euler-Maclaurin summation method one has to do O(T) work. The Euler-Maclaurin summation method for zeta is given by $ ...
322
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)$ ...
42
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 ...
20
votes
8answers
4k 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 ...
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$$
6
votes
1answer
3k 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 ...
10
votes
2answers
923 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 ...
4
votes
2answers
4k 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
478 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
1k 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
2answers
97 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 & ...
6
votes
4answers
296 views

A calculation that goes awfully wrong if we let $\pi=22/7$

Me and one of my friends had an argument and he said that using $22/7$ as value of $\pi$ is sufficient for any calculation. Can we always take it $22/7$, or is there some example of some calculation ...
4
votes
2answers
306 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
3answers
89 views

Exponential curve fit

I want to fit a curve of the form $y = ab^x +c$ where a, b and c are constant whereby i have a data of points $(x_i, y_i)$ I can reduced my primary equation into a form $log(y - c) = log(a) + ...
2
votes
1answer
514 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
505 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
182 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
100 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 ...
102
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 ...
73
votes
24answers
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 one. Numerical computations, to my understanding, never ...
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? ...
31
votes
1answer
695 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 ...
8
votes
2answers
9k views

Explanation and Proof of the fourth order Runge-Kutta method

Runge-Kutte 4th order method is a numerical technique used to solve ordinary differential equation of the form $dy/dx=f(x,y), y(0)=y_0$ It gives $y_{i+1}$ in the form $y_{i+1} = ...
10
votes
2answers
3k 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.
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) = ...
18
votes
4answers
355 views

How could I improve this approximation?

In a computer application, I need to solve trillions of times an equation which can be reduced to $$f(x)=\sin(x)-a x=0$$ Newton methods (quadratic and higher orders) are used for the solution. ...
14
votes
5answers
7k 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) = ...
12
votes
2answers
623 views

In what sense is the derivative the “best” linear approximation?

I am familiar with the definition of the Frechet derivative and it's uniqueness if it exists. I would however like to know, how the derivative is the "best" linear approximation. What does this mean ...
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 ...
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
3k 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
2answers
93 views

For what values of $x$ is the assignment $y=1-\cos x$ problematic, and why? [closed]

So I'm kind of stuck on this question and I don't exactly know how to describe this on the title header and I apologize... For some values of $x$, the assignment statement $y := 1-\cos(x)$ ...
2
votes
1answer
5k 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 ...
7
votes
2answers
2k views

Fast Matlab Code for hypergeometric function $_2F_1$

I am looking for a good numerical algorithm to evaluate the hypergeometric function $_2F_1$ in Matlab (hypergeom in Matlab is very slow). I looked across the ...