The Inverse Quadratic Method 3 – Brent’s Method

The previous post in this series presented iterative methods to solve polynomial equations using direct or inverse quadratic interpolation.  These methods have two disadvantages:

• In some circumstances the function may converge very slowly, or not at all.
• The name of the function to be solved must be hard coded into the solution function

The user defined function QuadBrent overcomes both of these problems:

• Brent’s Method is used to use different interpolation techniques (quadratic, linear, or bisection) through the course of the solution.
• The name of the function to be solved is an argument of the UDF, (using the technique described in this recent post) so the QuadBrent function may be used to solve any equation that can be evaluated with a VBA function.

In addition the quadratic interpolation may be performed either by the Inverse Quadratic Method (the default), or by using Muller’s Method.

The function is entered as shown below:
 =QuadBrent(FunctionName, Ak, Bk, Coefficients,  Max error = 1E-14, Max iterations = 20, Subroutine = 1, Xtol 1e-14)

• FunctionName is the name of a VBA function evaluating the equation to be solved.
• Ak and Bk are the lower and upper bounds to the solution value.
• Coefficients is a range or array of values that will be passed to FunctionName
• Subroutine = 1 for Inverse Quadratic method or 2 for Muller’s method

The function returns a single column array with three rows:

• The solution to the equation
• The number of iterations
• The error in the function value for the given solution

In order to display all three rows the function must be entered as an array function:

• Enter the function as normal.
• Select the cell containing the function and the two below.
• Press F2
• Press Ctrl-Alt-Enter

The QuadBrent function has been added to the ItSolve Functions2.xls spreadsheet, including full open source code.  The functions previously presented, QuadMuller and QuadSolve2 have also been modified to accept the input the name of a function  to be evaluated.

Use of the Quadbrent function, along with the two earlier functions, is shown in the screen shots below:

QuadBrent solution to a quartic polynomial, click for full size view

QuadBrent solution to a cubic polynomial

Note that in the second example the function crosses the x axis at x = -3, then touches the axis, but does not cross, at x = 1.  The QuadBrent function has found the solution at x = -3, but the QuadMuller function has failed to converge:

Wikipedia Brent Method Example

The spreadsheet also includes an on-spreadsheet implementation of Brent’s Method used to solve the equation shown above.  The solution output is shown below, and may be compared with the detailed description of the evaluation given in the Wikipedia article:

Step by step output for Brent's Method, click for full size view