An equation with a given function of a variable x taking rational values can be solved by time stepping:
where the sign of is chosen so that and the time step dt is small enough. We start with as a start approximation and compute successively:
If the sequence x_n converges to a value X so that gets small as n increases, also becomes small and so we will have (assuming is continuous) and so we have computed a root X to the equation .
See that .
To understand the condition and dt small enough, subtract two successive steps to get
where convergence with
is guaranteed if
with quicker convergence the smaller q is. Explain.
Play with the above code and compute roots.
Generalisation to Newton’s Method
Consider time stepping with the following variant of (1):
- , (2)
where alpha is a number to be chosen according to the following consideration:
Rewrite (2) as fixed point iteration
with convergence if for all x, where and quicker convergence the smaller is. We compute
to find that Dg(x) is small (0) if
We are thus led to time step as follows choosing dt = 1,
which is Newton’s Method with very quick convergence (assuming Df(x) not zero).