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.:cool:

[manojsoni]

what is newton raphson method for multiple roots ?

[Moridin]

Use a different initial value.

[AlephZero]

Use a different initial value.

Newton-Raphson is a poor method for multiple roots, even if it works at all.

Example: Solve f(x) = 0 where f(x) = x^2. Obviously there is a double root at x = 0.

From a starting point of x_0 = a, the next iteration is

x_1 = a - a^2/(2a) = a/2.

Successive iterations give a/2, a/4, a/8 ... which is not quadratic convergence.

They good way to solve double roots is use a function minimization method. Minimization methods "know" that at the minimum the function gradient is zero.

(But I haven't time to write a tutorial about that).

[Hootenanny]

Just a note to remind posters that this is not the place to post questions. They should be lodged in the appropriate forum.

[Astronuc]

what is newton raphson method for multiple roots ? When I was an undergrad taking numerical analysis, one of the assignments was to write a program to find roots using the NR method. It started with a guess as to where the roots might be located and the algorithm would march along the independent variable until the sign changed. Then one solved in that interval with the algorithm shown in attachment in the OP.

[Johan de Vries]

Division using Newton-Raphson. :smile:

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


\begin{equation*}
\frac{1}{x} - y = 0
\end{equation}


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


\begin{equation*}
x_{n+1} = 2x_{n} - x_{n}^{2}y
\end{equation}


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:


\begin{equation*}
P_{n+1}(x) = 2P_{n}(x) - P_{n}(x)^{2}f(x)
\end{equation}


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 :smile: 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.