How to set up a spreadsheet to use the Newton-Raphson method to find roots

There are many different root finding algorithms (https://en.wikipedia.org/wiki/Root-finding_algorithm ). The Newton-Raphson method is one of the most common because it generally converges rapidly and reliably. In Excel, one will usually use the built in Goal seek or Solver utilities to implement a NR type algorithm when finding roots of equations. On occasion, one may prefer a more automated approach. There are many ways to do this, including using VBA. What I want to show in this tutorial is how to set up a spreadsheet, without using VBA, to obtain roots. One thing that I will use is a "circular reference" to acheive this. Those who refuse to turn iteration on (Excel Options -> Formula options) will probably not be interested in this tutorial. For those who would be interested in becoming more comfortable with iterative calculations in a spreadsheet, this may be a good introduction.

For the tutorial, I will find the roots of a 2nd order polynomial. This can be useful, because I know of other ways to find the roots (quadratic formula) to test the result. I think will be better able to understand the tutorial if they already understand the NR method. If you are unfamiliar, I would suggest the wikipedia page above, or this tutorial using a Java applet: http://www.cs.utah.edu/~zachary/isp/...ot/Newton.html

Thanks a lot this really helped me sort out the McDougall-Wotherspoon modification.

Also good to note, I think it itterates left to right. As the attached file appears to be itterating correctly over the two cycles.

Glad that it proved interesting and useful to you.

Mathophobe warning: This version of the file will deal with imaginary and complex numbers. You have been warned.

As easy as that was to do in real space, somewhere along the line, I thought I would see if this works just as well in complex space. Excel can work with complex numbers using its collection of IM...() functions. (https://support.office.com/en-us/art...__toc309306710 )

As expected the NR algorithm works just fine in complex space. Formatting in Excel is a little difficult, since complex numbers are stored as text strings.

This can be an interesting spreadsheet for exploring Excel's ability to find the odd roots of negative numbers [cubed root of -8 or fifth root of -32, for example]. Excel's POWER() function cannot handle fractional powers of negative numbers. Excel's IMPOWER() function can do them, but it does not preferentially return the real root. IMPOWER(-8,1/3) prefers to return 1+1.732i instead of -2.

Just something to play around with.

Okay, here's another variation of the spreadsheet.

The NR algorithm we have described works very well when you can easily take the derivative. In the tab "secant" we have prepared a more complex "composite" function -- the product of two quadratics.

The original algorithm can still be used for this, if we want to do so. We could do the tedious work of multiplying both quadratics together to get the final quartic, then take the first derivative of that, then find the roots using the original algorithm.

If our calculus is strong, we can use combinations of chain rules and product rules (and division rules etc.) to get the derivative as is.

If we are really clever, we might notice (in this specific case) that the four roots of this function will be the roots of each of the factors, so we can put each quadratic into the previous spreadsheet.

Each of these possibilities, while possible, can be more work that we really want to put into it. The derivative really is not that important to us -- except as a step towards getting the final roots. If we can find a simpler way to approach this, without the tedium (and potential for stupid mistakes) of the algebra or calculus, we might be interested.

Enter the "secant method". It is essentially the same as the NR methods we have been talking about, except that we don't worry about doing the calculus/algebra to get the exact expression for the slope of the function. We approximate the slope with a numeric derivative, and use that. If you've had calculus, you will recall that the definition of the derivative looks something like "f'(x)=limit as h->0 of [f(x+h)-f(x)]/h". If we choose a small, arbitrary value for h, we can easily use this to compute the slope, and, from that, find the roots of the function.

I just keep extending this. I hope no one is bothered.

Another application of these numerical methods is in optimization. Sometimes we aren't looking for "roots", but we are looking for the maximum or the minimum of the function. If you recall from your calculus courses, the usual strategy for finding the max/min/"critical points" of a function was to find where the 1st derivative was 0. In other words, one strategy for finding the maxima/minima of a function is to find the roots of the 1st derivative. So, the algorithms and set up illustrated in previous spreadsheets can also work for finding maxima/minima. We only need to adapt our set up so that we are finding the roots of the 1st derivative instead of finding the roots of the original function.

The attached spreadsheet illustrates this for a quartic polynomial.

Things to do with this spreadsheet:
1) Explore different quartics by copying the random parameters in K2:O2 and pasting as values into B2:F2
2) I made a short list of quartics that have 3 max/min's. See how different "initial guesses" leads to finding different max/min points.
3) One common issue with optimization algorithms is the "Solver says it found the optimum, but I know there is a more optimum result elsewhere in the function". Consider those cases with three optima, and explore how one might know that there is a higher high or lower low elsewhere.
4) How can you tell if a reported point is a max or min?

Resurrecting this to make a new observation about computation speeds. As I have used circular references like this to solve some of the problems that I face, I have found that computation time can be a concern. I created this file to help feel out these concerns.

To start, I put together a couple of simple VBA UDF's to replicate the spreadsheet calculation. One UDF is specific to cubic polynomials and receives arguments as doubles, so it shoudl be the faster UDF. The other receives the coefficient array as a range and is expected to be slower. These UDFs are entered into columns R and S in the spreadsheet. Columns K:P contain a basic circular reference to perform the root finding algorithm. Columns F:I contain the coefficients for the cubic polynomials. Columns A:D contain random number calculations to generate random coefficients for F:I. By copying the desired application of the NR algorithm down, you can get a feel for how quickly that implementation works.

When the root finding algorithm is the only thing running, I get mixed results. On this computer, F:I is the slowest algorithm and column R is the fastest. On my work computer, F:I is the fastest algorithm, and column S is the slowest.

I included a very slow and inefficient lookup in columns V:AA to simulate downstream calculations. Sometimes, the root finding algorithm is the only thing you need to do. Other times, the root finding algorithm is only one step in a larger calculation. This lookup column is a placeholder for those downstream calculations to show how they can effect calculation speed. My tests showed that including these calculations dramatically slowed down the circular reference non-VBA implementation. This make sense when you recognize that, with the circular reference, Excel is performing the lookup for each iteration. When you take the NR loop into VBA, Excel waits until VBA completes the NR loop and returns the final value before performing the lookup.

Make of that what you will. This example illustrates how to code the NR algorithm in VBA. It also allows you to test calculation speed over different implementations of the NR algorithm. For small problems where the bulk of the algorithm is the root finding algorithm, the circular reference approach works approximately as well as the VBA implementation. However, for larger problems where the root finding algorithm is a smaller part of the overall problem, there are significant improvements to be found by performing the root finding step in a VBA UDF.

I obviously haven't added to this thread for a few years, but a recent discussion led to this about finding roots of polynomials as eigenvalues of a square matrix that represents the polynomial and my first foray into QR decomposition: https://www.excelforum.com/excel-for...ml#post5346740