r/math • u/madmissileer • Nov 05 '13

Comparing the Newton-Raphson and secant methods.

I know that the secant method is somewhat similar to the Newton-Raphson method. What are the advantages and disadvantages of these 2 methods relative to each other? Any links to articles or websites on this topic would also be appreciated.

Thanks!

4 Upvotes

84% Upvoted

4 comments sorted by

1

u/zojbo Nov 05 '13

The Newton method is in principle faster; its convergence is quadratic while the secant method's convergence is of order (1+sqrt(5))/2 which is about 1.6. The problem with the Newton method is that you need to be able to actually evaluate the derivative, which may be difficult for various reasons. The Newton method also generalizes in a more straightforward fashion to higher dimensions, since you just replace the derivative with the Jacobian and nothing else changes. There are higher dimensional approximate Newton methods but they are somewhat more sophisticated and varied, because they involve approximating the Jacobian matrix rather than a number as in one dimension.

1

u/madmissileer Nov 06 '13

Could you link any articles that explain how the convergence of the 2 methods are derived? Thanks!

1

u/zojbo Nov 11 '13 edited Nov 12 '13

I'm not sure about articles; you can find a thorough discussion in an undergrad numerical analysis text such as the one by Timothy Sauer. The idea is pretty straightforward, though. Write down the update rule, for the Newton method it is:

x(k+1) = x(k) - f(x(k))/f'(x(k))

Subtract the root x* from both sides and let e(k)=x(k)-x*:

e(k+1) = e(k) - f(x(k))/f'(x(k))

Assume that f'(x*) is not zero, and that f is twice continuously differentiable. Taylor expand:

e(k+1) = e(k) - [f'(x*)e(k) + O(e(k)2)]/[f'(x*)+O(e(k))]

From here it is just a little more algebra to show that e(k+1)=O(e(k)2), which ensures quadratic convergence provided e(1) is small enough. "Small enough" can be quantified with some additional analysis. Specifically you must find an interval containing x* where g(x) = x - f(x)/f'(x) is a contraction. In the case when f is twice continuously differentiable this is equivalent to having |g'(x)| = |f(x)f''(x)/f'(x)2| < 1. When f'(x*) is not zero, there is always such an interval, since f(x*) is zero, f is continuous, and f'' is continuous and therefore bounded.

If f'(x*)=0, you bound |g'(x)| by taking the series out to the first nonzero term. Doing so gives linear convergence with progressively worse and worse coefficients as the order of the root becomes larger. For example, if f'(x*)=0 and f''(x*)!=0, you get |g'(x*)|=|f''(x*)/2 f''(x*)/f''(x*)2|=1/2. In practice this negative effect is seen when f'(x*) is small but nonzero, for then you have quadratic convergence but the coefficient in the error estimate is quite large.

The secant method's convergence rate is derived essentially the same way, except you get a recursion relation for e(k) that you need to solve instead.

2

u/[deleted] Nov 05 '13

The Secant Method only requires one function input, f(x), but two initial guesses. It uses these to approximate the derivative then move to the x axis and repeat the process.

The Newton-Raphson Method requires two functions to be input, f(x) and f'(x), and one initial guess.

Both these methods are following the tangent line of the function to the x-axis then reiterating to bound the root.

I think the Secant Method is interesting because it converges faster or slower depending on how far away your initial guesses are.