Following on from the previous post, this post presents a number of methods of solving polynomial equations using approximate iterative methods in Excel.  Similar methods can be used to find solutions to any other equation that can be evaluated numerically.

The problem is to find the value of x for which:

a + b*x + c*x^2 + d*x^3 … = 0

The examples and functions presented in this post are all included in the spreadsheet: Newtons Method.xls

The example used is the evaluation of a quartic polynomial, for which exact analytical solutions are available, but the functions in the spreadsheet may be used directly for polynomials of any degree, and may be easily adapted for other forms of equation.  The spreadsheet also includes User Defined Functions (UDFs) to solve Quartic, Cubic and Quadratic  equations.

The basis of the Newton-Raphson (and related) methods is shown in the chart below.

Basis of the Newton-Raphson method

 Click on any image to view full-size.

The value of the function, f(x), and its slope, f'(x), are evaluated at some estimated approximate solution value, x1.  A better approximation, x2, is then given by x2 = x1 – f(x)/f'(x).

The spreadsheet contains several alternative solutions to the equation:

-100 + 60x + 16x^2 + -2x^3 + 2x^4 = 0

Exact solutions and spreadsheet solution using SumProduct

The solution to the equation is given by the UDF quartic().  The solution to a polynomial equation (of any degree) may also be found by adapting the Excel IRR() function:

 =1/(1+IRR(B7:F7,-0.2))

Where the function coefficients are listed in ascending powers of x in the range B7:F7, and -0.2 is an initial guess of the IRR.  Note that in this case an IRR value of -0.2 is equivalent to a solution value of 1/(1 – 0.2) = 1.25.

As discussed in the comments to the previous post, the function Sumproduct can be used to evaluate a polynomial function, and its derivatives.  For a list of coefficients in B7:F7, powers of x in B8:F8, and x value in B16:

• f(x) =SUMPRODUCT($B$7:$F$7,B16^($B$8:$F$8))
• f'(x) =SUMPRODUCT($B$7:$F$7,$B$8:$F$8,B16^(($B$8:$F$8)-1)*($B$8:$F$8>=1))

The next approximation to the solution of the equation is then:  =+B16-C16/D16

These formulas may be simply copied down to give the required level of precision.

The same approach may be followed using the UDF EvalPoly1, which returns the values of f(x) and f'(x) in a two cell array:

Solution using EvalPoly1 on the spreadsheet, and the UDF SolvePoly1

This approach is incorporated in the UDF SolvePoly1(), which returns the solution to the equation, and the required number of iterations.

When the equation to be solved cannot be differentiated analytically a numerical differentiation may be used, as illustrated below.  Note that in SolvePoly2 there is no check on the intermediate solutions, but in SolvePoly3 the intermediate solutions are constrained to fall between the specified lower and upper bounds, or lower and upper bounds found in previous stages of the analysis:

Solutions using numerical differentiation

The functions described above will only solve polynomial equations.  The SolveNR() UDF illustrated below will solve any equation including functions that can be solved with the VBA Evaluate function:

Solve equations with the SolveNR() UDF

Finally the screenshot below shows a spreadsheet solution and UDFs using the secant method.  In the secant method the slope of the function is evaluated using the two previous solutions:

Solutions using the secant method

The relative speed of the UDF solutions presented in this post are shown below:

Relative speed of functions

It can be seen that:

1. The analytical solution is substantially quicker than any of the approximate methods, and is recommended where applicable.
2. The secant methods are approximately the same speed as the Newton-Raphson method using analytical evaluation of the slope, and are of wider applicability.
3. The solutions that check for intermediate solutions being within the specified bounds are slightly slower in this case, but for less well behaved functions will find solutions when the other methods may not converge.
4. Evaluation of functions specified in text on the spreadsheet, using the Evaluate function, is very slow.  Similar functionality with much better performance can be obtained by replacing the text function with a purpose written VBA function.