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)

7
votes
2answers
2k views

Numerical method for finding the square-root.

I found a picture of Evan O'Dorney's winning project that gained him first place in the Intel Science talent search. He proposed a numerical method to find the square root, that gained him $100,000 ...
8
votes
2answers
1k views

Big-O Interpretation

I have trouble understanding what the "Big O" notation, or asymptotic notation means. For instance, if you have $\sin(x)=x+O(x^3)$, what does this mean? Can anyone describe it in a simple way? I tried ...
3
votes
3answers
549 views

Numerical Analysis References

Could anyone suggest any good (perhaps online ref papers) reference material on numerical analysis focusing on determining accuracy/estimated errors, rates/orders of convergence especially when ...
18
votes
4answers
341 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. ...
6
votes
1answer
1k views

Numerical methods book

I'm looking for an introductory book on numerical methods. I'm beginning to learn to program (in Haskell, a functional language, if that would affect the recommendations). The reason I want such a ...
5
votes
1answer
770 views

Kullback-Leibler divergence based kernel

I'm looking to paper "A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications". Author suggest to use kernel function for two distributions $p$ and $q$: $k(p,q)= ...
4
votes
3answers
3k views

rewriting to avoid catastrophic cancellation

why is rewriting $x^2 -y^2$ as $(x+y)(x-y)$ a way to avoid catastrophic cancellation? We are still doing $(x-y)$. Is it because the last operation in the second form is a multiplication?
2
votes
2answers
86 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
148 views

Understand a weird method of calculus

I see this method of calculus on youtube and my question: is this method valid? How we can understand it? Thanks.
10
votes
1answer
680 views

Bounding the basins of attraction of Newton's method

In general, Newton's method for root finding has a "bubbly" boundary between basins of convergence for different roots. This is where fractals are usually created from. But outside these "bubbly" ...
7
votes
3answers
183 views

Parallel lines divide a circle's area into thirds

When I was young I came up with a geometry problem and drew it in a notebook: Suppose we have a circle with radius $r$ and area $A$. Let two parallel lines be equidistant from the center of the ...
7
votes
1answer
2k views

Restricted Three-Body Problem

The movement of a spacecraft between Earth and the Moon is an example of the infamous Three Body Problem. It is said that a general analytical solution for TBP is not known because of the complexity ...
6
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 ...
6
votes
1answer
710 views

Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
5
votes
1answer
516 views

How should a numerical solver treat conserved quantities?

Since the good old Noether Theorem ultimately states that any physical system will exhibit conserved quantities, how should they be treated best in numerical solvers? On the one hand, one can observe ...
5
votes
1answer
455 views

How to use FEM to solve a PDE

I come from a Computer Science background and I've been around searching for a concise tutorial that tells me how Finite Element Method is used to solve a certain partial differential equation. ...
5
votes
1answer
3k views

how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors

How does one diagonalize a large sparse symmetric matrix to get the eigenvalues and the eigenvectors? The problem is the matrix could be very large (though it is sparse), at most 2500*2500. Is there ...
4
votes
4answers
182 views

How to compute a lot of digits of $\sqrt{2}$ manually and quickly?

After having read the answers to calculating $\pi$ manually, I realised that the two fast methods (Ramanujan and Gauss–Legendre) used $\sqrt{2}$. So, I wondered how to calculate $\sqrt{2}$ manually in ...
4
votes
2answers
123 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 ...
4
votes
1answer
230 views

Conjugate Gradient Method and Sparse Systems

What is it about conjugate gradient that makes it useful for attacking sparse linear systems. Why would steepest descent be significantly worse? Please keep in mind that I am still trying to fully ...
4
votes
1answer
2k views

How to compute elliptic integrals in MATLAB

I need to calculate the complete elliptic integrals of the first and second kind , the incomplete elliptic integral of the first kind, and the incomplete elliptic integral of the second kind in ...
4
votes
1answer
133 views

What's the fastest way to get an exact value for a product of (powers of polynomials)?

Suppose we have two integers $a$ and $b$. Also, suppose we have polynomials in $x$, $p_k(x)$. Finally, suppose we have a sequence of integers, where an integer in the sequence is denoted by $c_k$. ...
4
votes
1answer
617 views

Efficiently calculating the logarithmic integral with complex argument

My number theory library of choice doesn't implement the logarithmic integral for complex values. I thought that I might take a crack at coding it, but I thought I'd ask here first for algorithmic ...
3
votes
1answer
4k 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 ...
3
votes
1answer
60 views

Need help to simplify an equation

I am computing an error estimate where at the end I got the following term $\|X_{k} - G\|\leq (q^{2^{k+2}} + q^{2^{k+3}}+ q^{2^{k+4}}....)q^{-3}\|Y_{0}\| + q^{2^{k+1}}.q^{-2}\|X_0\|$ , where $X_k$ ...
3
votes
1answer
499 views

Understanding rate of convergence and order of convergence

I am trying to understand what is the difference between 'rate of convergence' and 'order of convergence'. Does anyone know an intuitive explanation of the difference between them? For example, say I ...
3
votes
1answer
550 views

Explain the error term in Euler method

Task: I had to find out some estimates for M and L to make sure the proportional accucrazy is not above $10^{-4}$ in the Euler method with the problem below. I am trying to understand the page 672 on ...
2
votes
0answers
115 views

how to choose point spacing to approximate a parametric curve using line segments?

Suppose I have a parametric equation for a curve $\vec{r} = f(t)$, which I wish to draw using line segments between some set of points at times $t_0, t_1, t_2,$ etc. If I want to achieve a given ...
2
votes
1answer
281 views

How to get the linear equation system for finite element method from the variational formulation

Let the problem be $$-u'' + a(x) u = f , \;x \in \Omega = ]0,1[ , \;u(0) = \alpha ; \;u(1) = \beta,$$ where $f \in L^2(\Omega) , a(x) \geq a_0 > 0 , a(x) \in L^{\infty}(\Omega).$ This problem ...
2
votes
2answers
362 views

resources to study PDE from

I am an undergrad engineering student. I recently completed my second year, with that said, I have taken several calculus courses. Most recently I completed differential equations and multivariable ...
2
votes
1answer
462 views

Derivation of weak form for variational problem

My question is about understanding the derivation of the weak form of a variational problem (to be used for the solution via the finite element method). The problem is as follows (it is an image ...
2
votes
2answers
2k 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
vote
2answers
425 views

Is there a general formula for estimating the step size h in numerical differentiation formulas?

Using three-point central-difference formula $$ f^{\prime}(x_0)\approx \frac{f(x_0+h)-f(x_0-h)}{2h} $$ and for $f(x)=\exp(x)$ at $x_0=0$ we have $$ \begin{array}{c, l, r} h & f^{\prime}(0) ...
1
vote
1answer
17k views

Solving a system with Newton's method in matlab?

I have the following non-linear system to solve with Newton's method in matlab: x²+y²=2.12 y²-x²y=0.04 What is the linear equation system to be solved? Should I ...
14
votes
1answer
267 views

Fastest curve from $p_0$ to $p_1$

I'm trying to solve a problem in path planning: Given points $p_0$ and $p_1$ and vectors $v_0$ and $v_1$, find a function $p(t)$ st. $p(0) = p_0$, $p(T) = p_1$, $p'(0) = v_0$ and $p'(T) = ...
7
votes
3answers
178 views

Exact result of a series using Euler-Maclaurin expansion.

This is a variant of Exercise 64 in Chapter 9 of concrete mathematics. Prove the following identity \begin{equation} \sum_{n = -\infty}^{\infty}' \frac{1 - \cos( 2\pi n k )}{n^2 } = 2 \pi^2 ( k - ...
6
votes
1answer
49 views

Floating point arithmetic operations when row reducing matrices

A numerical note in my linear algebra text states the following: "In general, the forward phase of row reduction takes much longer than the backward phase. An algorithm for solving a system is usually ...
5
votes
4answers
2k 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, ...
5
votes
3answers
3k views

Gaussian quadrature three-point

Derive the one and two-point Gaussian quadrature formulas for $$I=\int^1_0xf(x)dx\approx \sum_{j=1}^nw_jf(x_j)$$ with weight function $w(x)=x$. Which I know how to do and which I attached below (I ...
5
votes
1answer
2k views

Natural cubic splines vs. Piecewise Hermite Splines

Recently, I was reading about a "Natural Piecewise Hermite Spline" in Game Programming Gems 5 (under the Spline-Based Time Control for Animation). This particular spline is used for generating a C2 ...
5
votes
2answers
1k views

Symmetrize eigenvectors of degenerate (repeated) eigenvalue

I have the following situation: I have a hermitian Matrix $A$ that satisfies some symmetries which I can express via $AS = SA$ for a unitary matrix $S$. Now I am interested in the eigenvectors of ...
4
votes
3answers
165 views

system of First-Order ODES

I am looking at the following exercise: Consider the initial value problem $\left\{\begin{matrix} x''(t)=x(t)\\ x(0)=a\\ x'(0)=b \end{matrix}\right.$ Write it as a system of First-Order ODES with ...
4
votes
1answer
149 views

How to use Newton's method to find the roots of an oscillating polynomial?

Use Newton’s method to find the roots of $32x^6 − 48x^4 + 18x^2 − 1 = 0$ accurate to within $10^{-5}$. Newton's method requires the derivative of this function, which is easy to find. Problem is, ...
4
votes
4answers
1k views

Calculation of Bessel Functions

I want to calculate the Bessel function, given by $$J_\alpha (\beta) = \sum_{m=0}^{\infty}\frac{(-1)^m}{m!\Gamma(m+\alpha +1)} \left(\frac{\beta}{2}\right)^{2m}$$ I know there are some tables that ...
4
votes
2answers
708 views

Numerical analysis textbooks and floating point numbers

What are some recommended numerical analysis books on floating point numbers? I'd like the book to have the following In depth coverage on the representation of floating point numbers on modern ...
4
votes
0answers
912 views

Convergence of Gauss-Newton method for piecewise linear functions

Notation for Gauss-Newton method Non-linear least squares problems are often solved by the Levenberg-Marquardt algorithm, which can be viewed as a Gauss–Newton method using a trust region approach. ...
4
votes
4answers
551 views

Numerical computation of the Rayleigh-Lamb curves

The Rayleigh-Lamb equations: $$\frac{\tan (pd)}{\tan (qd)}=-\left[\frac{4k^2pq}{\left(k^2-q^2\right)^2}\right]^{\pm 1}$$ (two equations, one with the +1 exponent and the other with the -1 exponent) ...
3
votes
2answers
133 views

Bernstein polynomial looks like this: $B_i^n={{n}\choose{i}}x^i(1-x)^{n-i}$.Find it's $r$'th derivative.

Bernstein polynomials are defined like this $B_i^n={{n}\choose{i}}x^i(1-x)^{n-i}$.I need to prove that $r$'th derivative of it is equal to: ...
3
votes
2answers
142 views

Root of the function $f(x)=xe^x-R$

How can we find the root of the function $f(x)=xe^x - R$ for a general R where $R>=-1/e.$ I don't have any idea as to how to even approach this. Came across this problem during my self-study in ...
3
votes
3answers
128 views

Accuracy from approximating $\zeta(2)$ with a partial sum

This is for an introductory numerical analysis class. The answer shouldn't be too complicated, but if you have one, feel free to post it. Figure out what $n$ should be such that $$\sum_{k=n+1}^\infty ...