Newton's Method
Aaron Toponce
topic will cover the Newton-Raphson recursive algorithm, commonly known as
Newton's Method. Given the fact that we alredy know how to calculate
derivatives and find the equations of tangent lines to curves at a given
point, we will move on. To set the stage for a problem, suppose a used car
dealer offers to sell you a car for $18,000 or for payments of $375 per
month for five years. You would like to know what monthly interest rate the
dealer is, in effect, charging you. To find the answer, you have to solve
the equation (for our time here we will not discuss how we come up with the
equation. Accept it right now for no better reason than authority):
48x(1+x)^60 - (1+x)^60 + 1 = 0
How would you approach solving it? (Note for a quadratic ax^2 + bx +c = 0,
there is a well known formula to find the roots called the quadratic
equation, 3rd and 4th degree equations get much more complicated and there
are formulas to find the roots there, but if f(x) is a polynomial of degree
5 or higher, there is no such formula to find exact roots.) We could graph
the function in our HP-49 or TI-89, set the viewing rectangle to x->{0,.012}
y->{-.05,.15}, and then use the trace function to approximate the root
between .007 and .008. Zooming in repeatedly, we could find correct to nine
decimal places that the root is .007628603. But this is tiresome,
redundant, and takes a great deal of time. We could use the Solve( )
command in our calculators to find the approx solution as well. But how
does the calulator find the root? They use a variety of methods, but the
most commonly used method is Newton's Method. Now what is Newton's Method?
Lets discuss it detail:
Suppose you have a curve that has a root R and suppose R is not known. To
find R, we take a known value close to R and call it x1. Then we locate the
y-value on the curve so that we have a point (x1, f(x1)). Then calculate
the tangent line at that point and sketch it such that the tangent line
crosses the x axis. That root where the tangent line crossed we will call
x2. Then find the y-value of x2 and repeat the process. What you will find
is in effect x2, x3, etc will get closer and closer to your R root (there
are cases where this will fail, we will discuss these later). In fact, you
only need to find about x5 or x6 to be correct to 6-8 decimal places! To
find a formula for x2 in terms of x1, we use the fact that the slope of L is
f'9x10, so its equation is:
y - f(x1) = f'(x1)*(x-x1); where f'(x1) is the derivative of f(x1).
Since the x-intercept of L is x2, we set y=0 and obtain;
0 - f(x1) = f'(x1)*(x2-x1).
If f'(x1) != (does not equal) 0, we can solve this equation for x2:
x2 = x1 - f(x1) / f'(x1)
We use x2 as a second approximation to R:
x3 = x2 - f(x2) / f'(x2)
If we keep repeating this process, we obtain a sequence of approximations
x1,x2,x3,x4,....... In general, if the nth approximation is xn and f'(xn)
!= 0, then the next approximation is given by:
xn+1 = xn - f(xn) / f'(xn).
If the numbers xn become closer and closer to R as n becomes large, then we
say that the sequence converges to R and we write:
lim xn = R
n->oo
Although the sequence fo successive approximations converges to the desired
root for some functions, in other circumstances the sequence may not
converge. This is likely to be the case when f'(x1) is close to 0. It
might even happen that an approximation falls outside the domain of f. THEN
NEWTONS METHOD FAILS AND A BETTER INITIAL APPROXIMATION X1 SHOULD BE CHOSEN.
Now how would you use this with the HP-49 or the TI-89? Well, each
calculator goes about it differently but the idea is the same. Suppose we
want to find the root of x^3 + x + 1 = 0. Let's make our first guess (x1)
be -1. f'(x) = 3x^2 + 1, so our equation would be:
(-1) - ((-1)^3 + (-1) + 1) / (3(-1)^2 + 1).
Which yields -.75. Putting .75 in for x2 and re-evaluating gives
us-.686046511628. Put our answer now in for x3 and evaluate again, and we
get -.682339582597. One more time yields -.682327803947, and a last
evaluation gives us -.682327803828. (Note: Notice how on our 2nd and 3rd
evaluations .68 is repeated, and on our 3rd and 4th .6823 is repeated and on
our 4th and 5th .682327803 is repeated? Newton brought to light something
interesting when coming up with his recursive formula. For each evaluation
after x2, your accuracy will double. Notice we have two decimal places of
accuracy by our 3rd evaluation, 4 by our fourth, and 9 by our fifth.
Newton's Method is a GREAT way to get accurate in a hurry. Chances are by
our 6th evaluation, we would be accurate to 18 decimal places!)
Now those of you with the HP-49, you can program it so each time you hit
enter, your answer will be displayed. To program the algorithm, do the
follwing (assuming you are in RPN mode): Place your first equation ( f(x) )
on the stack. Press alpha Y, then STO. Now put the derivative of your
first equation ( f'(x) ) on the stack. Press alpha Z then STO. Press your
first initial guess on the stack (in our previous example, it would be -1),
press alpha X then STO. Now for the program. Key in the following, then
press enter to place it on the stack:
<< X Y Z / - ->NUM { X } PURGE X STO X >>
Now that it is on the stack, press alpha twice, type NEWT, the STO. If you
press the VAR button you will notice your variables X, Y, Z, and NEWT above
their respective soft keys. Now every time your press NEWT, you will get a
numerical value closer and closer to your root. On the TI-89, the idea is
the same. Press the gree diamond then f1. This brings you to the y=
screen. Type your first equation in y1, and your second equation in y2.
Then press the home button. For your program here, press your first inital
guess (ours was -1) the press STO-> , press X, then ENTER. Here you
assigned a value to x, Then in this sequence, press the following:
X - Y1(X) / Y2(X) STO-> X ENTER
Each time you press ENTER, you will get closer and closer to the root you
are seeking.
I know this was a lengthy post, so your comments are appreciated. Any
questions, feel free to email me, or respond to the post. Thanks!
-Aaron
Veli-Pekka Nousiainen
news:RL%v9.170362$md1.36573@sccrnsc03...
X
> I know this was a lengthy post, so your comments are appreciated. Any
> questions, feel free to email me, or respond to the post. Thanks!
> -Aaron
search for "PDF" in tucows
If you need full "Office", try:
EasyOffice (Office Suite) including PDF Filter 4.1
http://www.tucows.com/business/preview/198735.html
or
search for "PDF" in zdnet
If you need something simple, try:
Acropad PDF Creator 1.0
http://downloads-zdnet.com.com/3000-2383-8994127.html?tag=lst-0-11
VPN
Colin Croft
HP48/49, but I wrote an aplet for the HP39/40G which illustrates
graphically the process of iterating to find the root. You give it a
starting value and it draws the tangent down to the x axis then back up
to the fn, then... etc. It shows clearly how N-R method can be unstable
for some starting points where f'(x) is near zero. Look on the Maths
Aplets page -> Functions & Calculus section of http://www.hphomeview.com
Nick Karagiaouroglou
Mille gracie for this. :-)
Keep it up! The club is growing.
Greetings,
Nick.
---snipped rest---
Cyrille de Brébisson
Is someone actually archiving these Marathons and teachings aids? I can see
that as beeing of huge value to market HP calculators against TI.
regards, Cyrille
"Colin Croft" <ccr...@iinet.net.au> wrote in message
news:3DC116B7...@iinet.net.au...
Dahmonic
Aaron Wallace
> command in our calculators to find the approx solution as well. But how
> does the calulator find the root? They use a variety of methods, but the
> most commonly used method is Newton's Method.
PowerPlot uses this method to find roots. It can be done reasonably
fast with a relatively high degree of accuracy, so I thought it was an
optimal choice, especially since the cursor could be used for the
initial guess. If you download the docs for powerplot, you'll find a
graphical illustration of Newton's method.
Regards,
Aaron
Steen Schmidt
How do you bracket the root? This is a much more interesting question -
this'll usually use up 80% of the total root finding execution time. Then
18% is used on deciding if to stop or continue searching inside the
(probably might-be) bracket. I guess 2% is used for actually finding the
root - the easy part.
Regards
Steen
Aaron Wallace
From what I can remember, I pretty much just followed the Newton's
method algorithm. I didn't do any derivatives, just used the slope
between the previous (x,y) and the current one. It looks like I just
checked for an arbitrary tolerance and if it was less than that
tolerance or had looped 50 times (whichever came first), then I quit and
spit out whatever I had.
Here's the source code. I wrote it a LONG time ago when I was first
learning sysrpl, and I can already see that it could use some work.
Regards,
Aaron
DEFINE X 1GETLAM
DEFINE EQU 2GETLAM
DEFINE CX 3GETLAM
DEFINE PX 4GETLAM
DEFINE CY 5GETLAM
DEFINE PY 6GETLAM
DEFINE BG 7GETLAM
DEFINE I 8GETLAM
DEFINE IX 9GETLAM
::
CK1
ID CONV
X
TrueTrue
3PICK
DUP
% .01
%+SWAP
6ROLL
6ROLL
$ "ERROR: BAD GUESS"
7UNROLL
0
8UNROLL
1GETLAM
9
UNROLL
TRUE
9
NDUPN
DOBIND
PX
1PUTLAM
EQU
ERRSET
COMPEVAL
ERRTRAP
::
xCLEAR
BG
DISPROW1
RSKIP
;
::
6PUTLAM
CX
1PUTLAM
BEGIN
CX
1PUTLAM
EQU
ERRSET
COMPEVAL
ERRTRAP
::
xCLEAR
BG
DISPROW1
TRUE
RSKIP
;
::
DUP
5PUTLAM
PY
%-
DUP
%ABS
% .00000000001
%>
ITE
::
CX
PX
%-
%/
CY
SWAP
%/
CX
SWAP
%-
CX
4PUTLAM
CY
6PUTLAM
3PUTLAM
FALSE
;
DROPTRUE
;
I
#1+
8PUTLAM
I
50
#=
ITE
::
IX
3PUTLAM
TRUE
;
FALSE
OR
UNTIL
;
3GETLAM
ABND
;
John H Meyers
> Is someone actually archiving these Marathons and teaching aids?
> I can see these as beeing of huge value
> to market HP calculators against TI.
Is HP any longer producing calculators
which can use these Marathons and teaching aids?
Well, that's good news!
[r->] [OFF]
.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----