# Solve f(x)=0 by Time Stepping x = x+f(x)*dt

An equation $f(x)=0$ with $f(x)$ a given function of a variable x taking rational values can be solved by time stepping:

• $x = x + f(x)*dt$

where the sign of $f(x)$ is chosen so that $\frac{df}{dx} <0$ and the time step dt is small enough. We start with $x=x_0$ as a start approximation and compute successively:

• $x_{n+1} = x_n + f(x_n)*dt$ for $n=0, 1, 2,...$

If the sequence x_n converges to a value X so that $x_{n+1}-x_n=f(x_n)*dt$ gets small as n increases, also $f(x_n)$ becomes small and so we will have $f(X)=0$ (assuming $f(x)$ is continuous) and so we have computed a root X to the equation $f(x)=0$.

As an example consider $f(x)=2-x^2$ with $x_0=1$ and $dt=0.1$.

See that $X =\sqrt{2}$.

To understand the condition $\frac{df}{dx} <0$ and dt small enough, subtract two successive steps to get

• $x_{n+1}-x_{n} = x_n -x_{n-1} +(f(x_n)-f(x_{n-1})*dt\approx (x_n-x_{n-1})(1+\frac{df}{dx}(x_n)*dt)$

where convergence with

• $\vert x_{n+1}-x_{n}\vert \approx q\vert x_{n}-x_{n-1}\vert$

is guaranteed if

• $q=\vert 1+\frac{df}{dx}(x_n)*dt\vert < 1$

with quicker convergence the smaller q is. Explain.

Play with the above code and compute roots.

Compare with Solving Equations by Newton’s Method

Compare with Fixed Point Iteration