On finding the root of two equations

[huijunchen9260]

Dear Oscar:

After watching your videos about Broyden's method and the generalized bisection method, I am wondering about the comparison between the two methods. My questions are:

1. Is Broyden's method ensure finding a root, or it would be similar to Newton's method where is might not converge?
2. After seeing the code, the Broyden's method seems way simpler than the Harley-Stenger method, and it seems that Harley-Stenger method may not be fast? What is the benefit of Harley-Stenger over Broyden's method or other root-finding method?
3. If I am solving a model where every evaluation of the function takes a long time (solving a general equilibrium model in econ), which method would you recommend me to try to implement?

Thank you!

HJ

[osveliz]

Hi HJ,

1. Broyden does not guarantee convergence similar to Newton.
2. Part of the complexity for my Harvey-Stenger was plotting the behavior. Their full algorithm is guarnateed to find a solution which its major selling point. It also doesn't need a Jacobian (or even an approximation) at all. The shorter version I went over will converge assuming that your starting points contain a solution.
3. It depends. You also have to worry about how long it will take to evaluate a Jacobian (or approximating it with additional function evaluations). Using Broyden would be better than Newton since it will save on Jacobian calls. Harvey-Stenger will reuse function results each iteration as would Broyden, but since Broyden converges quadratically it would be faster and therefore save more function calls compared to Harvey-Stenger. If you can trust Broyden to reliably converge for your problem, then that would be the way to go. That being said, you could imagine a hybrid-ized version of Broyden, similar to Dekker's Method, that bounds the solution inside of an area and switches to Bisection whenever the iteration goes outside. Similarly, if you want something faster than Harvey-Stenger and converges reliably, while slower than Broyden but with no Jacobian, then also consider Generalized Secant Method (Wolfe-Bittner) https://youtu.be/p2OPlnHJPNI .

Hope that helps,

OV

[huijunchen9260]

Dear Oscar:

Thank you so much for your reply! After seeing your reply and I think I successfully implemented the two dimensional bisection method. I think this works great!

I think it is possible to immediately tell computer to stop if we initialize with just a triangle and using L test to see whether the (0, 0) is inside the triangle. I am guessing that it is the simplex method.