Brent's Method - Example

Example

Suppose that we are seeking a zero of the function defined by f(x) = (x + 3)(x − 1)2. We take = as our initial interval. We have f(a₀) = −25 and f(b₀) = 0.48148 (all numbers in this section are rounded), so the conditions f(a₀) f(b₀) < 0 and |f(b₀)| ≤ |f(a₀)| are satisfied.

1. In the first iteration, we use linear interpolation between (b₋₁, f(b₋₁)) = (a₀, f(a₀)) = (−4, −25) and (b₀, f(b₀)) = (1.33333, 0.48148), which yields s = 1.23256. This lies between (3a₀ + b₀) / 4 and b₀, so this value is accepted. Furthermore, f(1.23256) = 0.22891, so we set a₁ = a₀ and b₁ = s = 1.23256.
2. In the second iteration, we use inverse quadratic interpolation between (a₁, f(a₁)) = (−4, −25) and (b₀, f(b₀)) = (1.33333, 0.48148) and (b₁, f(b₁)) = (1.23256, 0.22891). This yields 1.14205, which lies between (3a₁ + b₁) / 4 and b₁. Furthermore, the inequality |1.14205 − b₁| ≤ |b₀ − b₋₁| / 2 is satisfied, so this value is accepted. Furthermore, f(1.14205) = 0.083582, so we set a₂ = a₁ and b₂ = 1.14205.
3. In the third iteration, we use inverse quadratic interpolation between (a₂, f(a₂)) = (−4, −25) and (b₁, f(b₁)) = (1.23256, 0.22891) and (b₂, f(b₂)) = (1.14205, 0.083582). This yields 1.09032, which lies between (3a₂ + b₂) / 4 and b₂. But here Brent's additional condition kicks in: the inequality |1.09032 − b₂| ≤ |b₁ − b₀| / 2 is not satisfied, so this value is rejected. Instead, the midpoint m = −1.42897 of the interval is computed. We have f(m) = 9.26891, so we set a₃ = a₂ and b₃ = −1.42897.
4. In the fourth iteration, we use inverse quadratic interpolation between (a₃, f(a₃)) = (−4, −25) and (b₂, f(b₂)) = (1.14205, 0.083582) and (b₃, f(b₃)) = (−1.42897, 9.26891). This yields 1.15448, which is not in the interval between (3a₃ + b₃) / 4 and b₃). Hence, it is replaced by the midpoint m = −2.71449. We have f(m) = 3.93934, so we set a₄ = a₃ and b₄ = −2.71449.
5. In the fifth iteration, inverse quadratic interpolation yields −3.45500, which lies in the required interval. However, the previous iteration was a bisection step, so the inequality |−3.45500 − b₄| ≤ |b₄ − b₃| / 2 need to be satisfied. This inequality is false, so we use the midpoint m = −3.35724. We have f(m) = −6.78239, so m becomes the new contrapoint (a₅ = −3.35724) and the iterate remains the same (b₅ = b₄).
6. In the sixth iteration, we cannot use inverse quadratic interpolation because b₅ = b₄. Hence, we use linear interpolation between (a₅, f(a₅)) = (−3.35724, −6.78239) and (b₅, f(b₅)) = (−2.71449, 3.93934). The result is s = −2.95064, which satisfies all the conditions. But since the iterate did not change in the previous step, we reject this result and fall back to bisection. We update s = -3.03587, and f(s) = -0.58418.
7. In the seventh iteration, we can again use inverse quadratic interpolation. The result is s = −3.00219, which satisfies all the conditions. Now, f(s) = −0.03515, so we set a₇ = b₆ and b₇ = −3.00219 (a₇ and b₇ are exchanged so that the condition |f(b₇)| ≤ |f(a₇)| is satisfied). (Correct : linear interpolation s = -2.99436, f(s) = 0.089961)
8. In the eighth iteration, we cannot use inverse quadratic interpolation because a₇ = b₆. Linear interpolation yields s = −2.99994, which is accepted. (Correct : s = -2.9999, f(s) = 0.0016)
9. In the following iterations, the root x = −3 is approached rapidly: b₉ = −3 + 6·10−8 and b₁₀ = −3 − 3·10−15. (Correct : Iter 9 : f(s) = -1.4E-07, Iter 10 : f(s) = 6.96E-12)