Read again what I wrote: there exist jobs that require knowledge of Newton's method, and in those cases this would be a valid interview question. This is not in disagreement with your "there exist jobs that do not require knowledge of Newton's method". You're likely to need to know about Newton's method for jobs in the area of machine learning, robot control, or some kind of physics simulation.
That said, Newton's method is not rocket science. The basic algorithm is iterating this line:
z = z - f(z)/f'(z)
Where f is some function and f' is its derivative. In many cases this will rapidly converge to a root of f (i.e. z will converge such that f(z) = 0). As far as algorithms go, this one is pretty damn simple. It is not in my working memory either, and I expect that many people rederive it when they need it.
The idea behind Newton's algorithm is that you approximate the function f(x) with the tangent line L at z:
L(x) = A + B*(x-z)
with A = f(z) and B = f'(z)
Now L(x) is an approximation of f(x). How well an approximation this is depends on how much f(x) looked like a line in the first place. Then instead of solving f(x) = 0 (which is our goal, but hard) you solve L(x) = 0 (which is not exactly our goal but almost our goal, and it is easy). So:
f(z) + f'(z)(x-z) = 0
Rewriting:
x = z - f(z)/f'(z)
Now the approximation of f(x) at that x is 0. Because it's only an approximation to f(x) it will probably not make the real f(x) = 0. Therefore we apply the method again and again with x as the new starting point:
z = some starting value
until f(z) is small enough:
z = z - f(z)/f'(z)
Because we're iterating, this method works even if f(x) doesn't look much like a line. For example x^2 - a doesn't look much like a line, but Newton's method is very effective at computing its root to compute sqrt. To see how outrageously effective it is, lets compute sqrt(2.0) with it. Lets start with a starting guess x = 1.0. We get the following numbers:
Note that at the 6th iteration already all 16 digits are correct.
Newton's method is perhaps the most beautiful algorithm due to its simplicity and effectiveness, and worth knowing even if only for its beauty. It is also quite probably the most important algorithm ever invented. It is used everywhere from division in hardware to optimizing all kinds of things and solving differential equations.
That said, Newton's method is not rocket science. The basic algorithm is iterating this line:
Where f is some function and f' is its derivative. In many cases this will rapidly converge to a root of f (i.e. z will converge such that f(z) = 0). As far as algorithms go, this one is pretty damn simple. It is not in my working memory either, and I expect that many people rederive it when they need it.The idea behind Newton's algorithm is that you approximate the function f(x) with the tangent line L at z:
Now L(x) is an approximation of f(x). How well an approximation this is depends on how much f(x) looked like a line in the first place. Then instead of solving f(x) = 0 (which is our goal, but hard) you solve L(x) = 0 (which is not exactly our goal but almost our goal, and it is easy). So: Rewriting: Now the approximation of f(x) at that x is 0. Because it's only an approximation to f(x) it will probably not make the real f(x) = 0. Therefore we apply the method again and again with x as the new starting point: Because we're iterating, this method works even if f(x) doesn't look much like a line. For example x^2 - a doesn't look much like a line, but Newton's method is very effective at computing its root to compute sqrt. To see how outrageously effective it is, lets compute sqrt(2.0) with it. Lets start with a starting guess x = 1.0. We get the following numbers: Note that at the 6th iteration already all 16 digits are correct.Newton's method is perhaps the most beautiful algorithm due to its simplicity and effectiveness, and worth knowing even if only for its beauty. It is also quite probably the most important algorithm ever invented. It is used everywhere from division in hardware to optimizing all kinds of things and solving differential equations.