{"history":[],"article":{"id":"32a6cc98-66d1-483f-8a20-46706d78832f","title":"Brent's method","slug":"brent-s-method","content":":::summary\n:::\n\n# \nIn [numerical analysis](https://bliptext.com/articles/numerical-analysis), **Brent's method** is a hybrid [root-finding algorithm](https://bliptext.com/articles/root-finding-algorithm) combining the [bisection method](https://bliptext.com/articles/bisection-method), the [secant method](https://bliptext.com/articles/secant-method) and [inverse quadratic interpolation](https://bliptext.com/articles/inverse-quadratic-interpolation).\nIt has the reliability of bisection but it can be as quick as some of the less-reliable methods.\nThe algorithm tries to use the potentially fast-converging secant method or inverse quadratic interpolation if possible, but it falls back to the more robust bisection method if necessary.\nBrent's method is due to [Richard Brent](https://bliptext.com/articles/richard-brent-scientist) and builds on an earlier algorithm by [Theodorus Dekker](https://bliptext.com/articles/theodorus-dekker).\nConsequently, the method is also known as the **Brent–Dekker method**.\nModern improvements on Brent's method include Chandrupatla's method, which is simpler and faster for functions that are flat around their roots; [Ridders' method](https://bliptext.com/articles/ridders-method), which performs exponential interpolations instead of quadratic providing a simpler closed formula for the iterations; and the [ITP method](https://bliptext.com/articles/itp-method) which is a hybrid between regula-falsi and bisection that achieves optimal worst-case and asymptotic guarantees.\n\n# Dekker's method\nThe idea to combine the bisection method with the secant method goes back to.\nSuppose that we want to solve the equation f(x) = 0.\nAs with the bisection method, we need to initialize Dekker's method with two points, say a0 and b0, such that f(a0) and f(b0) have opposite signs.\nIf f is continuous on [a0, b0], the [intermediate value theorem](https://bliptext.com/articles/intermediate-value-theorem) guarantees the existence of a solution between a0 and b0.\nThree points are involved in every iteration:\nTwo provisional values for the next iterate are computed.\nThe first one is given by linear interpolation, also known as the secant method:\nand the second one is given by the bisection method\nIf the result of the secant method, s, lies strictly between bk and m, then it becomes the next iterate (bk+1 = s), otherwise the midpoint is used (bk+1 = m).\nThen, the value of the new contrapoint is chosen such that f(ak+1) and f(bk+1) have opposite signs.\nIf f(ak) and f(bk+1) have opposite signs, then the contrapoint remains the same: ak+1 = ak. Otherwise, f(bk+1) and f(bk) have opposite signs, so the new contrapoint becomes ak+1 = bk.\nFinally, if |f(ak+1)| < |f(bk+1)|, then ak+1 is probably a better guess for the solution than bk+1, and hence the values of ak+1 and bk+1 are exchanged.\nThis ends the description of a single iteration of Dekker's method.\nDekker's method performs well if the function f is reasonably well-behaved.\nHowever, there are circumstances in which every iteration employs the secant method, but the iterates bk converge very slowly (in particular, |bk − bk−1| may be arbitrarily small).\nDekker's method requires far more iterations than the bisection method in this case.\n\n# Brent's method\nproposed a small modification to avoid the problem with Dekker's method.\nHe inserts an additional test which must be satisfied before the result of the secant method is accepted as the next iterate.\nTwo inequalities must be simultaneously satisfied:\nGiven a specific numerical tolerance \\delta, if the previous step used the bisection method, the inequality must hold to perform interpolation, otherwise the bisection method is performed and its result used for the next iteration.\nIf the previous step performed interpolation, then the inequality is used instead to perform the next action (to choose) interpolation (when inequality is true) or bisection method (when inequality is not true).\nAlso, if the previous step used the bisection method, the inequality\nmust hold, otherwise the bisection method is performed and its result used for the next iteration.\nIf the previous step performed interpolation, then the inequality\nis used instead.\nThis modification ensures that at the kth iteration, a bisection step will be performed in at most additional iterations, because the above conditions force consecutive interpolation step sizes to halve every two iterations, and after at most iterations, the step size will be smaller than \\delta, which invokes a bisection step.\nBrent proved that his method requires at most N2 iterations, where N denotes the number of iterations for the bisection method.\nIf the function f is well-behaved, then Brent's method will usually proceed by either inverse quadratic or linear interpolation, in which case it will converge [superlinearly](https://bliptext.com/articles/rate-of-convergence).\nFurthermore, Brent's method uses [inverse quadratic interpolation](https://bliptext.com/articles/inverse-quadratic-interpolation) instead of [linear interpolation](https://bliptext.com/articles/linear-interpolation) (as used by the secant method).\nIf f(bk), f(ak) and f(bk−1) are distinct, it slightly increases the efficiency.\nAs a consequence, the condition for accepting s (the value proposed by either linear interpolation or inverse quadratic interpolation) has to be changed: s has to lie between (3ak + bk) / 4 and bk.\n\n# Algorithm\n**input** a, b, and (a pointer to) a function for f\ncalculate f(a)\ncalculate f(b)\n**if** f(a)f(b) ≥ 0 **then**\nexit function because the root is not bracketed.\n**end if**\n**if** |f(a)| < |f(b)| **then**\nswap (a,b)\n**end if**\nc := a\n**set** mflag\n**repeat until** f(b **or** s) = 0 **or** |b − a| **is** small enough (convergence)\n**if** f(a) ≠ f(c) **and** f(b) ≠ f(c) **then**\n([inverse quadratic interpolation](https://bliptext.com/articles/inverse-quadratic-interpolation))\n**else**\n([secant method](https://bliptext.com/articles/secant-method))\n**end if**\n**if** (condition 1) s **is not** between (3a+b)/4 and b **or**\n(condition 2) (mflag **is** set **and** |s−b| ≥ |b−c|/2) **or**\n(condition 3) (mflag **is** cleared **and** |s−b| ≥ |c−d|/2) **or**\n(condition 4) (mflag **is** set **and** |b−c| < |δ|) **or**\n(condition 5) (mflag **is** cleared **and** |c−d| < |δ|) **then**\n([bisection method](https://bliptext.com/articles/bisection-method))\n**set** mflag\n**else**\n**clear** mflag\n**end if**\ncalculate f(s)\nd := c (d is assigned for the first time here; it won't be used above on the first iteration because mflag is set)\nc := b\n**if** f(a)f(s) < 0 **then**\nb := s\n**else**\na := s\n**end if**\n**if** |f(a)| < |f(b)| **then**\nswap (a,b)\n**end if**\n**end repeat**\n**output** b or s (return the root)\n\n# Example\nSuppose that we are seeking a zero of the function defined by f(x) = (x + 3)(x − 1)2.\nWe take [a0, b0] = [−4, 4/3] as our initial interval.\nWe have f(a0) = −25 and f(b0) = 0.48148 (all numbers in this section are rounded), so the conditions f(a0) f(b0) < 0 and |f(b0)| ≤ |f(a0)| are satisfied.\n# [Brent's method | upload.wikimedia.org/wikipedia/commons/2/2d/Brent///method///example.svg]\n\n# Implementations","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:17:04.252Z","updated_at":"2025-01-25T21:17:04.252Z","search_vector":"'brent':1 'method':3","search_content":" \n \n\n# \nIn [numerical analysis](https://bliptext.com/articles/numerical-analysis), **Brent's method** is a hybrid [root-finding algorithm](https://bliptext.com/articles/root-finding-algorithm) combining the [bisection method](https://bliptext.com/articles/bisection-method), the [secant method](https://bliptext.com/articles/secant-method) and [inverse quadratic interpolation](https://bliptext.com/articles/inverse-quadratic-interpolation).\nIt has the reliability of bisection but it can be as quick as some of the less-reliable methods.\nThe algorithm tries to use the potentially fast-converging secant method or inverse quadratic interpolation if possible, but it falls back to the more robust bisection method if necessary.\nBrent's method is due to [Richard Brent](https://bliptext.com/articles/richard-brent-scientist) and builds on an earlier algorithm by [Theodorus Dekker](https://bliptext.com/articles/theodorus-dekker).\nConsequently, the method is also known as the **Brent–Dekker method**.\nModern improvements on Brent's method include Chandrupatla's method, which is simpler and faster for functions that are flat around their roots; [Ridders' method](https://bliptext.com/articles/ridders-method), which performs exponential interpolations instead of quadratic providing a simpler closed formula for the iterations; and the [ITP method](https://bliptext.com/articles/itp-method) which is a hybrid between regula-falsi and bisection that achieves optimal worst-case and asymptotic guarantees.\n\n# Dekker's method\nThe idea to combine the bisection method with the secant method goes back to.\nSuppose that we want to solve the equation f(x) = 0.\nAs with the bisection method, we need to initialize Dekker's method with two points, say a0 and b0, such that f(a0) and f(b0) have opposite signs.\nIf f is continuous on [a0, b0], the [intermediate value theorem](https://bliptext.com/articles/intermediate-value-theorem) guarantees the existence of a solution between a0 and b0.\nThree points are involved in every iteration:\nTwo provisional values for the next iterate are computed.\nThe first one is given by linear interpolation, also known as the secant method:\nand the second one is given by the bisection method\nIf the result of the secant method, s, lies strictly between bk and m, then it becomes the next iterate (bk+1 = s), otherwise the midpoint is used (bk+1 = m).\nThen, the value of the new contrapoint is chosen such that f(ak+1) and f(bk+1) have opposite signs.\nIf f(ak) and f(bk+1) have opposite signs, then the contrapoint remains the same: ak+1 = ak. Otherwise, f(bk+1) and f(bk) have opposite signs, so the new contrapoint becomes ak+1 = bk.\nFinally, if |f(ak+1)| < |f(bk+1)|, then ak+1 is probably a better guess for the solution than bk+1, and hence the values of ak+1 and bk+1 are exchanged.\nThis ends the description of a single iteration of Dekker's method.\nDekker's method performs well if the function f is reasonably well-behaved.\nHowever, there are circumstances in which every iteration employs the secant method, but the iterates bk converge very slowly (in particular, |bk − bk−1| may be arbitrarily small).\nDekker's method requires far more iterations than the bisection method in this case.\n\n# Brent's method\nproposed a small modification to avoid the problem with Dekker's method.\nHe inserts an additional test which must be satisfied before the result of the secant method is accepted as the next iterate.\nTwo inequalities must be simultaneously satisfied:\nGiven a specific numerical tolerance \\delta, if the previous step used the bisection method, the inequality must hold to perform interpolation, otherwise the bisection method is performed and its result used for the next iteration.\nIf the previous step performed interpolation, then the inequality is used instead to perform the next action (to choose) interpolation (when inequality is true) or bisection method (when inequality is not true).\nAlso, if the previous step used the bisection method, the inequality\nmust hold, otherwise the bisection method is performed and its result used for the next iteration.\nIf the previous step performed interpolation, then the inequality\nis used instead.\nThis modification ensures that at the kth iteration, a bisection step will be performed in at most additional iterations, because the above conditions force consecutive interpolation step sizes to halve every two iterations, and after at most iterations, the step size will be smaller than \\delta, which invokes a bisection step.\nBrent proved that his method requires at most N2 iterations, where N denotes the number of iterations for the bisection method.\nIf the function f is well-behaved, then Brent's method will usually proceed by either inverse quadratic or linear interpolation, in which case it will converge [superlinearly](https://bliptext.com/articles/rate-of-convergence).\nFurthermore, Brent's method uses [inverse quadratic interpolation](https://bliptext.com/articles/inverse-quadratic-interpolation) instead of [linear interpolation](https://bliptext.com/articles/linear-interpolation) (as used by the secant method).\nIf f(bk), f(ak) and f(bk−1) are distinct, it slightly increases the efficiency.\nAs a consequence, the condition for accepting s (the value proposed by either linear interpolation or inverse quadratic interpolation) has to be changed: s has to lie between (3ak + bk) / 4 and bk.\n\n# Algorithm\n**input** a, b, and (a pointer to) a function for f\ncalculate f(a)\ncalculate f(b)\n**if** f(a)f(b) ≥ 0 **then**\nexit function because the root is not bracketed.\n**end if**\n**if** |f(a)| < |f(b)| **then**\nswap (a,b)\n**end if**\nc := a\n**set** mflag\n**repeat until** f(b **or** s) = 0 **or** |b − a| **is** small enough (convergence)\n**if** f(a) ≠ f(c) **and** f(b) ≠ f(c) **then**\n([inverse quadratic interpolation](https://bliptext.com/articles/inverse-quadratic-interpolation))\n**else**\n([secant method](https://bliptext.com/articles/secant-method))\n**end if**\n**if** (condition 1) s **is not** between (3a+b)/4 and b **or**\n(condition 2) (mflag **is** set **and** |s−b| ≥ |b−c|/2) **or**\n(condition 3) (mflag **is** cleared **and** |s−b| ≥ |c−d|/2) **or**\n(condition 4) (mflag **is** set **and** |b−c| < |δ|) **or**\n(condition 5) (mflag **is** cleared **and** |c−d| < |δ|) **then**\n([bisection method](https://bliptext.com/articles/bisection-method))\n**set** mflag\n**else**\n**clear** mflag\n**end if**\ncalculate f(s)\nd := c (d is assigned for the first time here; it won't be used above on the first iteration because mflag is set)\nc := b\n**if** f(a)f(s) < 0 **then**\nb := s\n**else**\na := s\n**end if**\n**if** |f(a)| < |f(b)| **then**\nswap (a,b)\n**end if**\n**end repeat**\n**output** b or s (return the root)\n\n# Example\nSuppose that we are seeking a zero of the function defined by f(x) = (x + 3)(x − 1)2.\nWe take [a0, b0] = [−4, 4/3] as our initial interval.\nWe have f(a0) = −25 and f(b0) = 0.48148 (all numbers in this section are rounded), so the conditions f(a0) f(b0) < 0 and |f(b0)| ≤ |f(a0)| are satisfied.\n# [Brent's method | upload.wikimedia.org/wikipedia/commons/2/2d/Brent///method///example.svg]\n\n# Implementations","revisionCount":0},"hasMore":false,"nextCursor":null}

History