Numerical Methods - Newton Raphson

[hotvette]

The following 2 page example illustrates the use of the Newton-Raphson technique for solving for roots of functions. Examples included:

1. Function in a single variable
2. System of non-linear equations

 

[Pseudo Statistic]

Nicely formatted... great examples too; interesting to finally find something on its use with non-linear systems. :)
Thanks!

 

[hotvette]

Thanks for the nice comments. My objective is to make things clear, concise, and practical. I need to see examples to understand things, so I figured others do also.

 

[Johan de Vries]

Division using Newton-Raphson.

We want to compute $1/y$ for some number $y$. This amounts to solving the equation:

$$\frac{1}{x} - y = 0$$

for $x$. If we do that using Newton-Raphson, we get:

$$x_{n+1} = 2x_{n} - x_{n}^{2}y$$

This is indeed a true division algorithm as it doesn't contain any divisions. Also, due to quadratic convergence, you double the number of significant digits at each step. Long division will only yield one significant digit per step.

The above algorithm can also be used to compute the Taylor series of a function $1/f(x)$ if the Taylor series of $f(x)$ is known. You just take $P_{0}(x)$ to be the first term of the expansion, e.g. if $f(0)$ is nonzero then $P_{0}=1/f(0)$ and you iterate using the algorithm:

$$P_{n+1}(x) = 2P_{n}(x) - P_{n}(x)^{2}f(x)$$

At each step the number of correct terms will double, so $P_{n}(x)$ will contain the first $2^{n}$ terms of the series expansion of $1/f(x)$. Note that this means that the term $P_{n}(x)^{2}f(x)$ has to be computed to order $\mathcal{O}\left(x^{2^{n+1}-1}\right)$.

So, computing the first billion terms of $1/f(x)$ only requires 30 iterations But we can do much more than computing reciprocals. Computing the series expansion of $\log(f(x))$ is almost as easy as computing the reciprocal of $f(x)$ as all you have to do is integrate $f'(x)/f(x)$ term by term. And using this algorithm for $\log(f(x))$ you can also compute $\exp\left(f(x)\right)$ using Newton-Raphson to solve for that function that yields $f(x)$ after taking the logarithm using Newton-Raphson and the algorithm for computing the logarithm of a series expansion.

Since a large class of functions can be expressed in terms of logarithms and exponentials, the series expansion of pretty much any awkward function can be computed this way.