Numerical Methods - Newton Raphson

  • Thread starter hotvette
  • Start date

hotvette

Homework Helper
981
3
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
 

Attachments

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

hotvette

Homework Helper
981
3
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:
 
Division using Newton-Raphson. :smile:

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

[tex]
\frac{1}{x} - y = 0
[/tex]

for [itex]x[/itex]. If we do that using Newton-Raphson, we get:

[tex]
x_{n+1} = 2x_{n} - x_{n}^{2}y
[/tex]

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 [itex]1/f(x)[/itex] if the Taylor series of [itex]f(x)[/itex] is known. You just take [itex]P_{0}(x)[/itex] to be the first term of the expansion, e.g. if [itex]f(0)[/itex] is nonzero then [itex]P_{0}=1/f(0)[/itex] and you iterate using the algorithm:

[tex]
P_{n+1}(x) = 2P_{n}(x) - P_{n}(x)^{2}f(x)
[/tex]

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

So, computing the first billion terms of [itex]1/f(x)[/itex] only requires 30 iterations :smile: But we can do much more than computing reciprocals. Computing the series expansion of [itex]\log(f(x))[/itex] is almost as easy as computing the reciprocal of [itex]f(x)[/itex] as all you have to do is integrate [itex]f'(x)/f(x)[/itex] term by term. And using this algorithm for [itex]\log(f(x))[/itex] you can also compute [itex]\exp\left(f(x)\right)[/itex] using Newton-Raphson to solve for that function that yields [itex]f(x)[/itex] 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.
 
Last edited by a moderator:

Related Threads for: Numerical Methods - Newton Raphson

  • Posted
Replies
8
Views
6K
Replies
1
Views
2K
Replies
2
Views
5K
  • Posted
Replies
1
Views
2K
  • Posted
Replies
1
Views
3K
Replies
1
Views
3K
Replies
1
Views
6K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top