Questions tagged [numerical-methods]

Questions on numerical methods; methods for approximately solving various problems that often do not admit exact solutions. Such problems can be in various fields. Numerical methods provide a way to solve problems quickly and easily compared to analytic solutions.

Filter by
Sorted by
Tagged with
15
votes
1answer
1k 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!...
33
votes
7answers
26k 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 ...
64
votes
3answers
42k 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 ...
24
votes
5answers
1k 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. ...
25
votes
6answers
18k 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 ...
3
votes
3answers
5k 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 ...
30
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}\...
1
vote
1answer
577 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 ...
21
votes
7answers
57k 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?
27
votes
4answers
97k 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 ...
55
votes
12answers
5k 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
7answers
7k 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 ...
17
votes
5answers
18k 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 ...
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 ...
35
votes
4answers
24k 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 ...
9
votes
3answers
7k 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/...
4
votes
4answers
1k views

Series of natural numbers which has all same digits

For which $x$ exists sum $1 + 2 + 3 + \ldots + n$, where $n > 3$, which has notation $xxx\ldots x$? In other words, I am looking for a sum of natural numbers which gives a result which has all ...
26
votes
6answers
3k 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 ...
7
votes
2answers
641 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 ...
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
6
votes
3answers
21k 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, ...
1
vote
2answers
1k views

Euler's Method Global Error: How to calculate $C_1$ if $error = C_1 h$

My textbook claims that, for small step size $h$, Euler's method has a global error which is at most proportional to $h$ such that error $= C_1h$. It is then claimed that $C_1$ depends on the initial ...
1
vote
1answer
546 views

Are there any two-dimensional quadrature that only uses the values at the vertices of triangles?

After reading on my notes about two dimensional quadrature rules, I noticed that there weren't any Gaussian quadrature rules (or any in general) that only used values at the vertices of the triangles. ...
1
vote
1answer
2k 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 ...
15
votes
1answer
10k 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 ...
22
votes
2answers
15k views

What is the relationship between cubic B-splines and cubic splines?

What is the relationship between cubic B-splines and cubic splines?
22
votes
6answers
5k 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 ...
21
votes
6answers
20k 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
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
3answers
1k 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
5k 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
446 views

Does fourth-order Runge-Kutta have an higher accuracy than the second-order one?

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
524 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)...
24
votes
1answer
31k 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+...
65
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 ...
10
votes
2answers
17k 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.
14
votes
2answers
40k 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$$
12
votes
1answer
9k 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 ...
18
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 ...
6
votes
2answers
4k 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 ...
3
votes
1answer
10k 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 ...
1
vote
2answers
253 views

Deriving the central Euler method and intuition

My professor (Dutch) asked us to determine, among other things, the truncation error of the central Euler method. First of all, this is probably not the correct term, since there are very few results ...
33
votes
4answers
35k views

Recommendations for Numerical Analysis texts?

I'm in a numerical analysis course right now and it's pretty rigorous but I'm enjoying it a lot. I took a lower level course before that was more oriented towards implementation of numerical methods, ...
33
votes
4answers
8k 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 ...
17
votes
5answers
61k 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 ...
12
votes
1answer
12k 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 ...
16
votes
1answer
273 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 ...
5
votes
2answers
12k views

When does Newton-Raphson Converge/Diverge?

Is there an analytical way to know an interval where all points when used in Newton-Raphson will converge/diverge? I am aware that Newton-Raphson is a special case of fixed point iteration, where: $...
9
votes
2answers
7k 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. ...

1
2 3 4 5
18