3
$\begingroup$

Looking for Newton's method in Wikipedia, I read the following:

In numerical analysis, Newton's method (also known as the Newton-Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function.

After describing briefly the method, the Wikipedia page adds:

This algorithm is first in the class of Householder's methods, succeeded by Halley's method. The method can also be extended to complex functions and to systems of equations.

The emphasis on "algorithm" is mine.

I know Wikipedia is not always to be trusted, and I have been wondering whether Newton's method as described in Wikipedia does qualify as an algorithm, and what could be the reasons why it would qualify or not qualify.

The same question applies to other similar methods, such as the whole family of Householder's methods, also described in Wikipedia, but an answer in the Newton-Raphson case is enough.

Note, as a last remark, that the same question could be applied to Euclid's method to compute GCD as described in Wikipedia, though I expect the answer would be: "yes, because ...".

Related questions:

$\endgroup$
  • $\begingroup$ What is the "definition" of algorithm you want answers to be based on? Why does the question make sense, i.e. why don't you ask the same question for any algorithm? Is there a special feature of Newton's method that makes you wonder? $\endgroup$ – Raphael Nov 1 '14 at 19:34
  • $\begingroup$ If I had a definition, I might be able to answer myself. There was a direct question on what is an algorithm, that that did not give much useful results from my point-of-view. So I am trying to identify criteria, and to see what is included or excluded and why. My motivation is obvious from tags: Newton's method is described in terms of real-numbers. But I do not state it as I do not want to influence answers. There may be other issues I did not see. Still, I think it is a more focussed question than "what is an algorithm?". $\endgroup$ – babou Nov 1 '14 at 20:55
3
$\begingroup$

It's pretty clearly an algorithm according to my definition in the linked question. I think your real question is "what is the problem, if any, for which this algorithm is correct?" The answer would be something like "given some stuff and a number of iterations, output a value satisfying some condition with an accuracy related to the iteration count."

$\endgroup$
1
$\begingroup$

My definition of an algorithm is a finite sequence of operations provided by an abstract machine, where the operations are executed one after another in the order specified by the sequence. Different machines may provide different sets of operations, so the definition of an algorithm depends on the abstract machine. (Correct me if I am wrong).

When given a specific function to work on, the Newton's method is an algorithm. But Newton's method also needs the 1st and 2nd derivatives of the function, besides the function itself as inputs.

If the problem is to find the root of any function from a set of functions, then Newton's method must be augmented with some algorithms which can derive the 1st and 2nd derivatives of any function from the functional set. After that, we have an algorithm for solving the problem.

The cause of the differences between the above two cases is how specific a problem should be.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.