From: Lynn Killingbeck Subject: Re: [Q] Derive Newton-Raphson for Square Root Date: Tue, 21 Mar 2000 18:00:32 -0600 Newsgroups: sci.math.num-analysis Summary: [missing] Todd A. Guillory wrote: > > > It looks a lot less cluttered in ASCII with a programmer's notation: > > x <== x - f(x)/f'(x). > > Apply this to f(x) = x^2 - a = 0. > > f'(x) = 2 * x. > > x <== x - (x^2 - a) / (2 * x). > > For best accuracy (most notably at the final step), that's probably the > > form to use. But, it is usually rearranged algebraically to > > x <== (x + a / x) / 2. > > OK, that helps but I'm still a bit confused. > BTW - my original equation came from Chapra & Canale "Numerical Methods for > Engineers" 3rd. > > OK, so if NR is: > > (1) x <== x - f(x)/f'(x). > > my f(x) = x^(1/2). > > The programming book makes the statement that the root can be found to an > input value a by iterating > > (2) x(i+1) = (x(i) + a / x(i)) / 2 > > until x(i+1) <== x(i) > > or > > for ( x1 = .5 * (x0 + a/x0); x0 != x1; x0 = x1, x1 = .5 * (x0 + a/x0) ) > ; > > where a > 0 > > I'm just not clear how they are going from (1) to (2) when > > f(x) = x^(1/2) > > and > > f'(x) = (1/2)x^(-1/2) > > Thanks Your f(x) is the problem. NR is explicitly for functions of the form f(x) = 0. Note that "=0" is missing from your f(x)=x^(1/2). You need to change it into something of the form f(x)=0. In this case, the one that works is f(x) = x^2 - a = 0. If you start with f(x) = x^(1/2) - a = 0, you will get another NR iteration. In this case, though, you won't be making any progress toward a practical solution! Let's try it: f(x) = x^(1/2) - a f'(x) = (1/2)*x^(-1/2) x <== x - (x^(1/2) - a) / [(1/2) * x^(-1/2)] = x - 2 * (x - a * x^(1/2)) = 2 * a * x^(1/2) - x. Wow! Doing this in ASCII is a nightmare! Check the algebra. Then, note that the iteration requires x^(1/2). But, if you had that, you would not be doing this, anyway! That particular form of f(x)=0 does not help. The f(x)=x^2-a=0, on the other hand, ends up with nothing worse than dividing a/x, adding to x, and taking 1/2 this sum. These divide, add, and 1/2 primitive operations are very likely available to you. Take it further. Presume that your machine does not even have a divide instruction! Now, the (x+a/x)/2 is also worthless, since the division is not available. This requires another form of NR. In this case, one that works is f(x) = 1/x^2 - a = 0. This x will not be what you want, since this x will be 1/x^(1/2). But, once you have it, you can multiply by 'a' to get the desired answer. It sounds like nonsense: to get sqrt(x), first compute 1/sqrt(x) and then multiply by x. But, getting 1/sqrt(x) can be done without any division, and this 'nonsense' gives a very useable method. (From experience, since I've worked with computers that do not have a divide instruction.) f(x) = 1/x^2 - a f'(x) = -2 / x^3 x <== x - (1/x^2 - a) / [-2 / x^3] = x + (x - a * x^2) / 2 = x + x * (1 - a * x^2)/2 = x * (3 - a * x^2) / 2 Again, check that awkward ASCII algebra. This time, there is also a constraint on the closeness of the original value of x. Lynn Killingbeck ============================================================================== From: "Dann Corbit" Subject: Re: [Q] Derive Newton-Raphson for Square Root Date: Tue, 21 Mar 2000 12:00:30 -0800 Newsgroups: sci.math.num-analysis "Todd A. Guillory" wrote in message news:8b85bd$d17$1@hiram.io.com... > My C book shows a method for finding the Square Root (SqRt) or a number with > a derived Newton-Rhapson: > > (1) xb = (1/2)*(xa + a/xa) > > where xb is x sub i, and xb is x sub i+1 > > I know Newton-Raphson is > > (2) f'(xa) = [f(xa) - g(xa)] / [xa - xb] > > In my numerical analysis book, g(xa) is substituted with 0 since they always > find where f(x) crosses the x axis. All the examples are also always with > polynomials. > > Now, let me first say, I suck at math, but I've tried several times and I > can't get the NR general equation to equation (1). Get a copy of cs-tr-2990.ps, which is "On Infinitely Many Algorithms For Solving Equations" by Ernst Schroder, Translated by G. W. Stewart. It explains not only Newton's method, but just about every related root finding algorithm. Newton's method is just a special case of one of Schroder's generated algorithms. -- C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html "The C-FAQ Book" ISBN 0-201-84519-9 C.A.P. Newsgroup http://www.dejanews.com/~c_a_p C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm