• Support PF! Buy your school textbooks, materials and every day products Here!

Newton-Raphson method

  • Thread starter DryRun
  • Start date
  • #1
DryRun
Gold Member
838
4

Homework Statement


Solve for positive root of equation: 10 + 3x^2 = e^x


Homework Equations


The usual Newton-Raphson formula.


The Attempt at a Solution


f(x) = 10 + 3x^2 - e^x

f'(x) = 6x -e^x

But then my biggest problem, how to find the initial guess? I have looked around, and i can't find a definitive answer on how to find the initial value. From what i understand, i can plot a graph and then look for an estimate. Is that the best method there is?
Anyway, i plotted a graph and i have no idea how to interpret it, as the two curves don't touch on my graph paper, so i can't figure out an estimate. I get a curve with minimum 3x^2 + 10 and the graph of e^x. Is that correct?
 

Answers and Replies

  • #2
SteamKing
Staff Emeritus
Science Advisor
Homework Helper
12,798
1,666
Are you sure the two curves don't intersect? (Hint: your graph paper only shows a small snap-shot of the real plane.)

If you don't like to graph, you can always systematically investigate (guess) x values.
At some point, the LHS will switch from being greater than the RHS to being less.
 
  • #3
Simon Bridge
Science Advisor
Homework Helper
17,847
1,644
But then my biggest problem, how to find the initial guess? I have looked around, and i can't find a definitive answer on how to find the initial value. From what i understand, i can plot a graph and then look for an estimate. Is that the best method there is?
You should also use you knowledge and experience of the way different shaped graphs work to guide you. To plot a graph, you need to make sure that the domain includes the root you want.

How many roots would you expect?
Where would you expect to find a positive root?

Anyway, i plotted a graph and i have no idea how to interpret it, as the two curves don't touch on my graph paper, so i can't figure out an estimate. I get a curve with minimum 3x^2 + 10 and the graph of e^x. Is that correct?
Perhaps you didn't go high enough?
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,806
932
Do you understand that just choosing an arbitrary starting value, say, x= 1.0, would give you the corrrect answer in less time than it took you to post this?
 
  • #5
DryRun
Gold Member
838
4
Do you understand that just choosing an arbitrary starting value, say, x= 1.0, would give you the corrrect answer in less time than it took you to post this?
I am aware that most of the time (from what i read in my little online research) any arbitrary value can be chosen, but here i need to choose an initial value that's reasonable so that i can complete the problem in less time (exams, tests) and i also need to make sure that the oscillations don't go on endlessly or give me no roots, as sometimes is the case (again, from what i read and understood).

However, i asked one of my friends (who also has no definitive idea on how to do this) and he tells me that as a general rule, i should always evaluate f(0) and then use that value as the initial value. Is that correct and common practice? Or am i just being misled into more confusion, if that's even possible?
 
  • #6
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683

Homework Statement


Solve for positive root of equation: 10 + 3x^2 = e^x


Homework Equations


The usual Newton-Raphson formula.


The Attempt at a Solution


f(x) = 10 + 3x^2 - e^x

f'(x) = 6x -e^x
The first thing to do is to do a simple analysis of the function at hand, which is f(x)=10+3x2-ex. The function is continuous everywhere, so that's good. It goes to -∞ (exponentially) as x→+∞, and to +∞ (quadratically) as x→-∞. So there must be at least one zero. Since f(0)=9, at least one of the zeros lies between 0 and +∞.

Newton-Raphson has big problems when f'(x) is zero. In this case, f'(x)=6x-ex is negative at x=0, negative for very large x, but is positive for x=1. So we have a potential problem. f'(x) is positive for x=2 as well, negative for x=3. Choosing an initial guess between 0 and 2 might well be a very bad idea here.

The graphs of 10+3x2 and ex do cross somewhere between x=0 and x→+∞. I'll hold off on the rest of my comments on the specific problem at hand you yourself have a better guess as to how to proceed. I will comment on your last post.


I am aware that most of the time (from what i read in my little online research) any arbitrary value can be chosen
Most of the time you should expect that NR will behave badly. That's why more powerful techniques such as Levenberg–Marquardt only use NR (actually, Gauss-Newton) when the candidate solution is in an a region where Newton's method is well-behaved.

but here i need to choose an initial value that's reasonable so that i can complete the problem in less time (exams, tests) and i also need to make sure that the oscillations don't go on endlessly or give me no roots, as sometimes is the case (again, from what i read and understood).
There are tests to see if something bad has happened. But generic rules to guarantee a good choice? No. For example, ...

However, i asked one of my friends (who also has no definitive idea on how to do this) and he tells me that as a general rule, i should always evaluate f(0) and then use that value as the initial value. Is that correct and common practice? Or am i just being misled into more confusion, if that's even possible?
Here's a simple counterexample: f(x)=x^2+2x-1. f(0)=-1, and f'(-1)=0. Kaboom!
 
  • #7
Simon Bridge
Science Advisor
Homework Helper
17,847
1,644
D_H said:
The graphs of 10+3x2 and ex do cross somewhere between x=0 and x→+∞. I'll hold off on the rest of my comments on the specific problem at hand you yourself have a better guess as to how to proceed. I will comment on your last post.
That's my position too - I plotted the function and found it in less than 10 seconds. Mind you - helps if you have a math-scripting program. It should be clear just looking at the two functions that there is an intersection.

sharks said:
However, i asked one of my friends (who also has no definitive idea on how to do this) and he tells me that as a general rule, i should always evaluate f(0) and then use that value as the initial value. Is that correct and common practice?
It comes back to my earlier question: how many roots do you expect the function to have? How well behaved is the function?

This is not something you can do consistently well on automatic. I'm afraid you just have to work it out. Sketching the graphs was a good start - it's amazing how few people do this.
 
  • #8
DryRun
Gold Member
838
4
So, to summarize, the best way to go about using the N-R method, is to always start with a graph and then try to approximate the initial value from the graph itself. We don't normally have graph paper in exams, as no such thing is required for N-R (according to my class notes, there is zero mention of drawing up any graphs), but i guess i should try to sketch it as accurately as possible.
 
  • #9
Simon Bridge
Science Advisor
Homework Helper
17,847
1,644
You can always sketch the graph. You don't need to actually plot anything. It need not be all that accurate so long as you get the important bits. You only need a general idea of where the roots can be found ... maybe avoid cyclic bits, but that is not often a problem in things like exams.

The rest depends on your access to computers.

If you are not allowed computers (phones, graphical or programmable calculators etc) in your exams then the N/R problems will be quite simple. If you are allowed computers, then the plots become trivial. Learn to use GNU/Octave for eg. Though a spreadsheet can be used in a pinch.

In the attachment, the blue line is the function - the red is the exponential and the green is the quadratic.
With the difference between a quadratic and an exponential, in general, there may be as many as three roots, and as few as none. Do you see how?
 

Attachments

Last edited:
  • #10
DryRun
Gold Member
838
4
The Octave software looks very impressive. It greatly simplifies the whole problem, as it gives a clear overview of the problem and i can almost see the root (it's between 4.0 and 4.5). I am downloading the Windows version and will make it a habit of referring to it for all Newton-Raphson problems.

Thank you all for your much appreciated and precious advice.
 
  • #11
Simon Bridge
Science Advisor
Homework Helper
17,847
1,644
I've never got the Windows version working ... but I know lots of people have, it's probably some sort of personal failing. The GNU/Linux version gets set up automatically and linux works around the terminal anyway.

The trick is thinking in terms of everything being a matrix.
But here are tutorials online.

That plot was generated with:

Code:
x=-5:0.125:5;
y=10+3.*x.^2;
z=exp(x);
plot(x,y-z,x,y,x,z)
grid
This samples the functions at 81 evenly spaced discrete points in the domain [-5,5], and generates a plot linking the dots by lines.

You can zoom in on the root by choosing tighter bounds for x, eg.

x=3.5:0.125/8:4.5;
y=10+3.*x.^2-exp(x);
plot(x,y)

You can also get it to do the N-R calculations for you by putting each step in a loop.
eg. finding the square-root of 25, starting at x=4:
Code:
octave:1> 0.5*(4+25/4)
ans =  5.1250
octave:2> 0.5*(ans+25/ans)
ans =  5.0015
octave:3> 0.5*(ans+25/ans)
ans =  5.0000
I can repeat a command in the terminal by pressing the up-arrow key.
For your function, it takes 5 iterations starting from ans=5 to get the root to 4dp.

Note - there are two turning points? Pick a starting point too close to one of them and it takes quite a long time to converge.
 
Last edited:
  • #12
DryRun
Gold Member
838
4
Thanks for the info on how to use the program, Simon Bridge. It's not so simple though, especially for the beginner. Maybe there are other alternatives where you can just click, drag, drop. I don't mind even paid software if it'll let me be lazy. :) I will do a little research on this.

Cheers!
 
  • #13
Simon Bridge
Science Advisor
Homework Helper
17,847
1,644
The hardest part is thinking about everything as a vector.
The visual studio set has drag-and-drop but anything much simpler than these script languages is also highly limited.

For just plotting a function, it is almost intuitive - just how you'd automatically think of writing it down here - watch:

lets say you want to plot y=x^2 -1 on the interval [-2,2]...

Your only decision is to work out how many points you want to use for the plot. Pick a number out of a hat ... the more points you use the smoother the plot, and the slower the calculation. You'll get used to it.

Let's say 100 points - including the end-points that's 99 steps (that's the hardest part) then:

a=-2;
b=2;
N=100;
s=(b-a)/(N-1);

x=a:s:b;
y=x.^2 -1;
plot(x,y)


The difference between y=x^2-1, which you'd naturally write, and y=x.^2-1 is trivial (and due to the fact that x is treated as a vector).

Seriously - if you want to pursue math and science at all past High School level - you need to learn some math script language anyway. The sooner you get used to it the better you'll do. Otherwise you'll struggle.

[Mind you - I've not used the windows version ... I gather Matlab and Mathematica are easier to use on Windows. In GNU/Linux, octave is pretty much built in.]
 

Related Threads on Newton-Raphson method

  • Last Post
Replies
6
Views
7K
Replies
2
Views
3K
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
892
  • Last Post
Replies
4
Views
20K
Replies
2
Views
1K
Replies
0
Views
1K
Top