Best algorithm for root search

[Kelvin Stott]

I am looking for the best (fastest as well as most reliable) algorithm to solve equations (find their roots, f(x) = 0, where 0 < x < 1), but have only been able to find the following 2 algorithms:
<x<1), but="" have="" only="" been="" able="" to="" find="" the="" following="" 2="" algorithms:
<x<1), and="" have="" found="" 2="" different="" approaches,="" each="" with="" their="" own="" pros="" cons:

1. Binary search, which finds f(x') closest to zero for each cycle (i = 1 to 50), where x' = x +/- 0.5^i
2. Classic Newton Raphson

The problem is that a binary search is very inefficient and can take too long (too many cycles), while Newton Raphson is unreliable as it depends on an arbitrary initial estimate. So I'm wondering: Is there a better (faster and more reliable) algorithm (VBA code) available that combines these two approaches?

Thanks for any help.</x<1),></x<1),>

 

[Worf]

If you are going to do this within Excel, one option is Ribbon > Data > Solver.
Can you give an example of one actual equation you are working with? Do they have multiple roots?
Do you need the source code? It will not be available with Solver…

 

[Kelvin Stott]

If you are going to do this within Excel, one option is Ribbon > Data > Solver.
Can you give an example of one actual equation you are working with? Do they have multiple roots?
Do you need the source code? It will not be available with Solver…

I'm looking to write a solve function in VBA, so need an algorithm, or at least a reference to the preferred method.

 

[Kenneth Hobson]

If solver will work for you, here is an example.

'http://support.microsoft.com/en-us/kb/843304
' http://www.solver.com/content/basic-solver-solversolve-function


Sub Create_Square_Root_Table()

    ' Add a new worksheet to the workbook.
    Set w = Worksheets.Add

    ' Put the value 2 in cell C1 and the formula =C1^2 in cell C2.
    w.Range("C1").Value = 2
    w.Range("C2").Formula = "=C1^2"

    ' A loop that will make 10 iterations, starting with the number 1,
    ' and finishing at the number 10.
    For i = 1 To 10

        ' Set the Solver parameters that indicate that Solver should
        ' solve the cell C2 for the value of i (where i is the number
        ' of the iteration) by changing cell C1.
        SolverOK SetCell:=Range("C2"), ByChange:=Range("C1"), _
            MaxMinVal:=3, ValueOf:=i

        ' Do not display the Solver Results dialog box.
        SolverSolve UserFinish:=True

        ' Save the value of i in column A and the results of the
        ' changing cell in column B.
        w.Cells(i, 1) = i
        w.Cells(i, 2) = Range("C1")

        ' Finish and discard the final results.
        SolverFinish KeepFinal:=2

    Next

End Sub

 

[shg]

You could do a binary search in log space. That would converge in at most 64 iterations.

 

[Kelvin Stott]

You could do a binary search in log space. That would converge in at most 64 iterations.

Thanks, I'm actually looking for something that combines the binary search method (robust but too slow, even with 50 cycles) with Newton Raphson (converges in <10 cycles, but not robust and reliable).

 

[shg]

Well OK, carry on!

There are certainly seven oceans of published literature on root-finding. I think it would be a long slog to get to the front.

 

[Kelvin Stott]

So here's my combined algorithm finally. Just as reliable as binary search, but as fast as Newton Raphson:

Function SOLVE(Fx As String, Optional Target As Double = 0, Optional xMin As Double = 0, Optional xMax As Double = 1, _
    Optional yTol As Double = 10 ^ -15, Optional iMax As Integer = 50)

    Dim yMin As Double, yMax As Double
    Dim xMid As Double, yMid As Double
    Dim Sht As Worksheet, Fn As WorksheetFunction
    
    Set Sht = Application.ThisCell.Parent
    Set Fn = WorksheetFunction
    
    For i = 1 To iMax
        xMid = (xMin + xMax) / 2
        yMid = Sht.Evaluate(Replace(Fx, "x", xMid))
        yMin = Sht.Evaluate(Replace(Fx, "x", xMin))
        yMax = Sht.Evaluate(Replace(Fx, "x", xMax))
        If Abs(yMid - Target) <= yTol Then
            Exit For
        ElseIf Abs(yMin - Target) <= yTol Then
            xMid = xMin
            Exit For
        ElseIf Abs(yMax - Target) <= yTol Then
            xMid = xMax
            Exit For
        ElseIf (yMin - Target) * (yMax - Target) < 0 Then
            xMin = xMid + (xMin - xMid) * (Target - yMid) / (yMin - yMid)
            xMax = xMid + (xMax - xMid) * (Target - yMid) / (yMax - yMid)
        ElseIf Abs(yMin - Target) > Abs(yMax - Target) Then
            xMin = xMid
        Else '
            xMax = xMid
        End If
    Next i
    
    SOLVE = xMid

End Function

Anyone care to test this against their own solver and report back on performance?

 

[Kelvin Stott]

Improved version:

Function SOLVE(Fx As String, Optional Target As Double = 0, Optional xMin As Double = 0, Optional xMax As Double = 1, _
    Optional xTol As Double = 10 ^ -15, Optional yTol As Double = 10 ^ -15, Optional iMax As Integer = 50)

    Dim yMin As Double, yMax As Double
    Dim xMid As Double, yMid As Double
    Dim Sht As Worksheet, Fn As WorksheetFunction
    
    Set Sht = Application.ThisCell.Parent
    Set Fn = WorksheetFunction
    
    For i = 1 To iMax
        xMid = (xMin + xMax) / 2
        yMid = Sht.Evaluate(Replace(Fx, "x", xMid))
        yMin = Sht.Evaluate(Replace(Fx, "x", xMin))
        yMax = Sht.Evaluate(Replace(Fx, "x", xMax))
        If Abs(xMax - xMin) <= xTol Then
            Exit For
        ElseIf Abs(yMid - Target) <= yTol Then
            Exit For
        ElseIf Abs(yMin - Target) <= yTol Then
            xMid = xMin
            Exit For
        ElseIf Abs(yMax - Target) <= yTol Then
            xMid = xMax
            Exit For
        ElseIf Fn.Median(yMid, yMin, yMax) = yMin Then
            xMin = xMid
        ElseIf Fn.Median(yMid, yMin, yMax) = yMax Then
            xMax = xMid
        ElseIf Fn.Median(Target, yMin, yMax) = yMin Then
            xMid = xMin
            Exit For
        ElseIf Fn.Median(Target, yMin, yMax) = yMax Then
            xMid = xMax
            Exit For
        Else
            xMin = xMid + (xMin - xMid) * (Target - yMid) / (yMin - yMid)
            xMax = xMid + (xMax - xMid) * (Target - yMid) / (yMax - yMid)
        End If
    Next i
    
    SOLVE = xMid

End Function

 

[Worf]

Anyone care to test this against their own solver and report back on performance?

Can you give an example of one actual equation you are working with?