Comparing Root-find Algorithms (Functions) in Python

Question

I would like to compare different methods for finding the roots of functions in python (e.g. Newton methods or other simple Calc based methods). I don’t think that I will have too many problems writing algorithms. What would be a good way to make an actual comparison? I read a little about Big-O. Will it be the way?

(any design ideas or twists will also be appreciated)

Thanks.

Answer 1

The answer from @sarnold is right - there is no point in doing a Big-Oh analysis.

The main differences between the root search algorithms:

• convergence rate (number of iterations)
• iteration effort
• what is required for input (i.e. you need to know the first derivative, you need to set lo / hi restrictions for halving, etc.).
• what functions does it work well (i.e. works fine on polynomials, but doesn't work on functions with poles)
• what assumptions does he make about a function (i.e., a continuous first derivative or analytic, etc.)
• how a simple method implements

I think you will find that each of the methods has good qualities, some bad qualities and many situations where this is the most suitable choice.

Answer 2

The Big O sign is ideal for expressing the asymptotic behavior of algorithms as a contribution to the “increase” of algorithms. This is probably not a big measure for root search algorithms.

Instead, I would think that the number of iterations needed to bring the actual error below some epsilon ε would be a better measure. Another measure would be the number of iterations needed to achieve the difference between successive iterations below some epsilon ε. (The difference between consecutive iterations is probably the best choice if you do not have exact root values ​​for your input. You would use criteria such as consecutive differences to know when to terminate the root finders in practice, so that you can or should also use them here.)

As long as you can characterize the number of iterations required for different algorithms by the relationships between them (one algorithm can achieve the same accuracy over another ten times as many as the other), often there is no "growth" in iterations as the inputs change.

Of course, if your algorithms take more iterations with "large" inputs, then the Big O notation makes sense.

Answer 3

The designation Big-O is intended to describe how the algorithm behaves in the limit, as n goes to infinity. It is much easier to work in a theoretical study than in a practical experiment. I would choose things to study that you can easily measure that these people care, for example, about accuracy and computer resources (time / memory).

When you write and run a computer program to compare two algorithms, you perform a scientific experiment, like the one who measures the speed of light, or someone who compares the death rates from smokers and non-smokers, and many of them apply the same factors.

Try to select an example of a problem or problems to solve that are representative or at least interesting to you, because your results may not generalize to syntaxes that you have not actually tested. You can increase the range of situations that your results will answer if you arbitrarily make a choice from a large number of possible problems and find that all your random samples behave the same or at least adhere to the same trend. You can get unexpected results, even if theoretical studies show that there should be a good trend n log n, because theoretical studies rarely take into account a sudden cache out or out of memory, or usually even for things like integer overflow.

Be careful about the sources of errors and try to minimize them or apply to the same extent to all the things that you are comparing. Of course, you want to use exactly the same input for all the algorithms you are testing. Take a few runs of each algorithm and check how things are variable - maybe a few starts are slower because the computer was doing something else at a time. Keep in mind that caching can speed up subsequent algorithms, especially if you run them immediately after each other. What time you want depends on what you decide, you measure. If you have a lot of I / O, to remember that modern operating systems and computer cache have huge amounts of disk I / O in memory. Once I finished working with the computer again and again after each start, as the only way to make sure that the device I / O cache was reset.

Answer 4

You can get completely different answers for the same problem by simply changing the starting points. Choose the initial assumption that is close to the root method and Newton will give you a result that converges quadratically. Choose another in another part of the problem space, and the root crawler will be diversified.

What does this say about the algorithm? Good or bad?

Answer 5

I would advise you to take a look at the following Python search demo. This is a simple code with various methods and comparisons between them (in terms of convergence speed).

http://www.math-cs.gordon.edu/courses/mat342/python/findroot.py

Answer 6

Why bother? There can only be one:

public class BrentsMethodResult { public bool TerminatedSuccessfully; public double Result; public double UpperResult; public double LowerResult; } public static BrentsMethodResult BrentsMethodSolve(Func<double, double> function, double lowerLimit, double upperLimit, double errorTol) { BrentsMethodResult result = new BrentsMethodResult(); double a = lowerLimit; double b = upperLimit; double c = 0; double d = double.MaxValue; double fa = function(a); double fb = function(b); result.LowerResult = fa; result.UpperResult = fb; if (Double.IsNaN(fa) || Double.IsNaN(fb)) { result.TerminatedSuccessfully = false; result.Result = Double.NaN; return result; } double fc = 0; double s = 0; double fs = 0; // if f(a) f(b) >= 0 then error-exit if (fa * fb >= 0) { result.TerminatedSuccessfully = false; if (Math.Abs(fa) < Math.Abs(fb)) { result.Result = a; return result; } else { result.Result = b; return result; } } // if |f(a)| < |f(b)| then swap (a,b) end if if (Math.Abs(fa) < Math.Abs(fb)) { double tmp = a; a = b; b = tmp; tmp = fa; fa = fb; fb = tmp; } c = a; fc = fa; bool mflag = true; int i = 0; while (Math.Abs(fb) > errorTol && Math.Abs(a - b) > errorTol) { //tol1 = 2.0 * double_Accuracy * Math.Abs(b) + 0.5 * errorTol; if ((fa != fc) && (fb != fc)) // Inverse quadratic interpolation s = a * fb * fc / (fa - fb) / (fa - fc) + b * fa * fc / (fb - fa) / (fb - fc) + c * fa * fb / (fc - fa) / (fc - fb); else // Secant Rule s = b - fb * (b - a) / (fb - fa); double tmp2 = (3 * a + b) / 4; if ((!(((s > tmp2) && (s < b)) || ((s < tmp2) && (s > b)))) || (mflag && (Math.Abs(s - b) >= (Math.Abs(b - c) / 2))) || (!mflag && (Math.Abs(s - b) >= (Math.Abs(c - d) / 2)))) { s = (a + b) / 2; mflag = true; } else { if ((mflag && (Math.Abs(b - c) < errorTol)) || (!mflag && (Math.Abs(c - d) < errorTol))) { s = (a + b) / 2; mflag = true; } else mflag = false; } fs = function(s); if (Double.IsNaN(fs)) { result.TerminatedSuccessfully = false; result.Result = Double.NaN; return result; } d = c; c = b; fc = fb; if (fa * fs < 0) { b = s; fb = fs; } else { a = s; fa = fs; } // if |f(a)| < |f(b)| then swap (a,b) end if if (Math.Abs(fa) < Math.Abs(fb)) { double tmp = a; a = b; b = tmp; tmp = fa; fa = fb; fb = tmp; } i++; if (i > 100) { throw new Exception(String.Format("100 iterations exceeded and error is {0}", fb)); } } result.TerminatedSuccessfully = true; result.Result = b; return result; } 

Answer 7

I will just finish the project, which compares the split methods in half, Newton and secant root. Since this is a practical case, I don't think you need to use Big-O notation. The Big-O designation is more suitable for an asymptotic view. What you can do is compare them in terms of:

Speed ​​- for example, here a new person is the fastest if a good condition is collected

The number of iterations - for example, here the bisector takes the iteration itself

Accuracy. How often does it converge to the correct root if there is more than one root, or maybe it does not converge at all.

Login - what information is needed to get started. for example, in order to converge, Newton needs X0 near the root, he also needs the first derivative, which is not always easy to find.

Other rounding errors

For visualization, you can save the value of each iteration in arrays and build them. Use a function that you already know roots.

Answer 8

Although this is a very old post, my 2 cents :)

Once you have decided which algorithmic method to use (your so-called “evaluation protocol”), you may be interested in how to run your applicants on real data sets.

This guide explains how to do this using an example (comparison of polynomial matching algorithms for several data sets).

(I'm the author, feel free to leave feedback on the GitHub page!)