Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [numerical-methods]

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

15
votes
1answer
981 views

Could this approximation be made simpler ? Solve $n!=a^n 10^k$

I need to find the smallest value of $n$ such that $$\frac{a^n}{n!}\leq 10^{-k}$$ in which $a$ and $k$ are given (these can be large numbers). I set the problem as : solve for $n$ the equation $$n!...
31
votes
7answers
25k 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
5answers
979 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. ...
3
votes
3answers
4k 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 ...
57
votes
3answers
36k 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 ...
29
votes
2answers
2k 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 $\lim_{n\to\infty}\...
23
votes
6answers
16k 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 ...
25
votes
4answers
82k views

Help with using the Runge-Kutta 4th order method on a system of 2 first order ODE's.

The original ODE I had was $$ \frac{d^2y}{dx^2}+\frac{dy}{dx}-6y=0$$ with $y(0)=3$ and $y'(0)=1$. Now I can solve this by hand and obtain that $y(1) = 14.82789927$. However I wish to use the 4th order ...
17
votes
5answers
15k views

How to accurately calculate the error function $\operatorname{erf}(x)$ with a computer?

I am looking for an accurate algorithm to calculate the error function $$\operatorname{erf}(x)=\frac{2}{\sqrt{\pi}}\int_0^x e^{-t^2}\ dt$$ I have tried using the following formula, (Handbook of ...
9
votes
7answers
6k 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
3answers
2k views

Is there a mean value theorem for higher order differences?

The standard mean value theorem tells us $\frac{f(x+h)-f(x)}{h} = f'(c)$ for some $c$ between $x$ and $x+h$. Rewriting this, we may see it as $\frac 1h\Delta_h f(x) = f'(c)$. This makes me wonder if ...
2
votes
2answers
1k views

Convergence of cos, sin, tan functions

In Radian mode, continually pressing the $\cos$ function of a number causes the result to converge to $x=0.739085133$, a fixed point of $\cos(x)$. Repeating this behavior with the $\sin$ function ...
29
votes
4answers
20k 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 ...
54
votes
12answers
4k 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 ...
9
votes
3answers
5k 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 manipulations/...
17
votes
2answers
4k 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 ...
8
votes
10answers
3k views

How can I find the value of $\ln( |x|)$ without using the calculator?

I want to know if there is a way to find for example $\ln(2)$, without using the calculator ? Thanks
4
votes
3answers
18k views

The mode of the Poisson Distribution

Lately, I am doing an investigation on Stirling's formula and its applications. So I thought I could use it to prove that the mode of the Poisson model is approximately equal to the mean. Of course, ...
13
votes
1answer
8k 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 ...
16
votes
2answers
11k views

Relation of cubic B-splines with cubic splines

Does anyone know the relation between the cubic B-splines and cubic splines?
2
votes
3answers
833 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) + xlog(b)...
2
votes
3answers
4k 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
487 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 $ \zeta(s)...
13
votes
2answers
35k views

Convergence rate of Newton's method

Let $f(x)$ be a polynomial in one variable $x$ and let $\alpha$ be its $\delta$-multiple root ($\delta\ge2$). Show that in the Newton's $x_{k+1}=x_k-f(x_k)/f'(x_k)$, the rate of convergence to $\...
14
votes
2answers
4k 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$$
22
votes
6answers
4k 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 ...
19
votes
6answers
18k 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) = \log(a)...
9
votes
1answer
8k 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
2k views

Solving for streamlines from numerical velocity field

Say I have a given numerical velocity field in two dimensions, (u,v). I am trying to find the streamlines from this data set at a particular contour level and I ...
25
votes
6answers
2k views

Why do I get a converging result when pressing cosine multiple times on a calculator? [duplicate]

I'm trying to comprehend the following: If I choose any starting value (e.g. 1) and keep clicking on cosine on the calculator (in radian mode), it gives me a result of about 0.739085...(I believe it's ...
6
votes
2answers
478 views

What is the difference between Hensel lifting and the Newton-Raphson method?

So in the Newton-Raphson method to iteratively approximate a root of a real polynomial, we start with a crude approximation $x_0 \in \mathbb{R}$ for $f(x)=0$ where $f(x) \in \mathbb{R}[x]$. For the ...
1
vote
1answer
986 views

Lax-Wendroff method for linear advection - Stability analysis

Question 1: Consider the wave equation $$ u_t + c(x) u_x = 0 , $$ where $x\in \Omega \subset \Bbb R$ and $c(x)$ is a function of $x$. (a) Show that the Lax-Wendroff scheme for this PDE is ...
1
vote
2answers
1k views

Rate of convergence of Newton's method near a double root.

Suppose that $r$ is a double root of $f(x)=0$; that is, $f(r)=f′(r)=0$ but $f''(r)\ne 0$, and suppose that f and all derivatives up to and including the second are continuous in some neighborhood of $...
1
vote
1answer
210 views

Quick question that I can't find anywhere online about Runge-Kutta

I'm writing a presentation on modelling fluid flow. We used Runge-Kutta second order to describe the flow as a numerical method. I just want verify that Runge-Kutta fourth order would be of a higher ...
1
vote
1answer
225 views

Understanding Galerkin method of weighted residuals

I have a puzzlement regarding the Galerkin method of weighted residuals. The following is taken from the book A Finite Element Primer for Beginners, from chapter 1.1. If I have a one dimensional ...
23
votes
1answer
28k 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} = y_i+(a_1k_1+a_2k_2+...
62
votes
3answers
2k 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 ...
21
votes
7answers
52k views

What is the difference between Finite Difference Methods, Finite Element Methods and Finite Volume Methods for solving PDEs?

Can you help me explain the basic difference between FDM, FEM and FVM? What is the best method and why? Advantage and disadvantage of them?
30
votes
4answers
7k views

Why does Monte-Carlo integration work better than naive numerical integration in high dimensions?

Can anyone explain simply why Monte-Carlo works better than naive Riemann integration in high dimensions? I do not understand how chosing randomly the points on which you evaluate the function can ...
16
votes
1answer
248 views

Numbers $p-\sqrt{q}$ having regular egyptian fraction expansions?

I remind that the greedy algorithm for egyptian fraction expansion for a positive number $x_0 <1$ goes like this: $$x_0=\frac{1}{a_0}+\frac{1}{a_1}+\frac{1}{a_2}+\dots$$ $a_n$ are positive ...
8
votes
2answers
14k views

Explanation of Lagrange Interpolating Polynomial

Can anybody explain to me what Lagrange Interpolating Polynomial is with examples? I know the formula but it doesn't seem intuitive to me.
12
votes
4answers
55k views

A practical way to check if a matrix is positive-definite

Let $A$ be a symmetric $n\times n$ matrix. I found a method on the web to check if $A$ is positive definite: $A$ is positive-definite if all the diagonal entries are positive, and each diagonal ...
8
votes
1answer
8k views

Why is 'catastrophic cancellation' called so?

I was studying Numerical Analysis by K. Mukherjee; there he discussed Loss of Significant Figures by Subtraction, as followed: In the subtraction of two approximate numbers, a serious type of error ...
8
votes
1answer
6k views

Derivative of $f(x,y)$ with respect to another function of two variables $k(x,y)$

Suppose that we have a function $f(x,y)$ of two variables: $$f(x,y) = g(x) + h(y) + 5(x-y) = x^2 + y^2 + 5(x-y)$$ where $g(x) = x^2$ and $h(y) = y^2$ are also functions of $x$ and $y$, respectively. ...
18
votes
4answers
12k 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 ...
5
votes
1answer
3k 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 ...
5
votes
4answers
2k 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 ...
4
votes
3answers
737 views

Numerical Approximation of Differential Equations with Midpoint Method

I want to proof that the local truncation error of the Midpoint Method is $d_{k+1}=O\left(h^{3}\right)$ Approach The local truncation error is defined as: $d_{k+1}=u(t_{k+1})-\underset{u_{k+1}}{\...
3
votes
1answer
8k 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
2k 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 ...