Editing Brent's method (section)

==Example==

Suppose that we are seeking a zero of the function defined by '''''f''(''x'') = (''x'' + 3)(''x'' &minus; 1)<sup>2</sup>'''.

We take '''[''a''<sub>0</sub>, ''b''<sub>0</sub>] = [&minus;4, 4/3]''' as our initial interval.

We have ''f''(''a''<sub>0</sub>) = &minus;25 and ''f''(''b''<sub>0</sub>) = 0.48148 (all numbers in this section are rounded), so the conditions ''f''(''a''<sub>0</sub>) ''f''(''b''<sub>0</sub>) < 0 and |''f''(''b''<sub>0</sub>)| ≤ |''f''(''a''<sub>0</sub>)| are satisfied.

[[Image:Brent method example.svg|thumb|Graph of ''f''(''x'') = (''x'' + 3)(''x'' &minus; 1)<sup>2</sup>]]
# In the first iteration, we use linear interpolation between (''b''<sub>&minus;1</sub>, ''f''(''b''<sub>&minus;1</sub>)) = (''a''<sub>0</sub>, ''f''(''a''<sub>0</sub>)) = (&minus;4, &minus;25) and (''b''<sub>0</sub>, ''f''(''b''<sub>0</sub>)) = (1.33333, 0.48148), which yields ''s'' = 1.23256. This lies between (3''a''<sub>0</sub> + ''b''<sub>0</sub>) / 4 and ''b''<sub>0</sub>, so this value is accepted. Furthermore, ''f''(1.23256) = 0.22891, so we set ''a''<sub>1</sub> = ''a''<sub>0</sub> and ''b''<sub>1</sub> = ''s'' = 1.23256.
# In the second iteration, we use inverse quadratic interpolation between (''a''<sub>1</sub>, ''f''(''a''<sub>1</sub>)) = (&minus;4, &minus;25) and (''b''<sub>0</sub>, ''f''(''b''<sub>0</sub>)) = (1.33333, 0.48148) and (''b''<sub>1</sub>, ''f''(''b''<sub>1</sub>)) = (1.23256, 0.22891). This yields 1.14205, which lies between (3''a''<sub>1</sub> + ''b''<sub>1</sub>) / 4 and ''b''<sub>1</sub>. Furthermore, the inequality |1.14205 &minus; ''b''<sub>1</sub>| ≤ |''b''<sub>0</sub> &minus; ''b''<sub>&minus;1</sub>| / 2 is satisfied, so this value is accepted. Furthermore, ''f''(1.14205) = 0.083582, so we set ''a''<sub>2</sub> = ''a''<sub>1</sub> and ''b''<sub>2</sub> = 1.14205.
# In the third iteration, we use inverse quadratic interpolation between (''a''<sub>2</sub>, ''f''(''a''<sub>2</sub>)) = (&minus;4, &minus;25) and (''b''<sub>1</sub>, ''f''(''b''<sub>1</sub>)) = (1.23256, 0.22891) and (''b''<sub>2</sub>, ''f''(''b''<sub>2</sub>)) = (1.14205, 0.083582). This yields 1.09032, which lies between (3''a''<sub>2</sub> + ''b''<sub>2</sub>) / 4 and ''b''<sub>2</sub>. But here Brent's additional condition kicks in: the inequality |1.09032 &minus; ''b''<sub>2</sub>| ≤ |''b''<sub>1</sub> &minus; ''b''<sub>0</sub>| / 2 is not satisfied, so this value is rejected. Instead, the midpoint ''m'' = &minus;1.42897 of the interval [''a''<sub>2</sub>, ''b''<sub>2</sub>] is computed. We have ''f''(''m'') = 9.26891, so we set ''a''<sub>3</sub> = ''a''<sub>2</sub> and ''b''<sub>3</sub> = &minus;1.42897.
# In the fourth iteration, we use inverse quadratic interpolation between (''a''<sub>3</sub>, ''f''(''a''<sub>3</sub>)) = (&minus;4, &minus;25) and (''b''<sub>2</sub>, ''f''(''b''<sub>2</sub>)) = (1.14205, 0.083582) and (''b''<sub>3</sub>, ''f''(''b''<sub>3</sub>)) = (&minus;1.42897, 9.26891). This yields 1.15448, which is not in the interval between (3''a''<sub>3</sub> + ''b''<sub>3</sub>) / 4  and ''b''<sub>3</sub>). Hence, it is replaced by the midpoint ''m'' = &minus;2.71449. We have ''f''(''m'') = 3.93934, so we set ''a''<sub>4</sub> = ''a''<sub>3</sub> and ''b''<sub>4</sub> = &minus;2.71449.
# In the fifth iteration, inverse quadratic interpolation yields &minus;3.45500, which lies in the required interval. However, the previous iteration was a bisection step, so the inequality |&minus;3.45500 &minus; ''b''<sub>4</sub>| ≤ |''b''<sub>4</sub> &minus; ''b''<sub>3</sub>| / 2 need to be satisfied. This inequality is false, so we use the midpoint ''m'' = &minus;3.35724. We have ''f''(''m'') = &minus;6.78239, so ''m'' becomes the new contrapoint (''a''<sub>5</sub> = &minus;3.35724) and the iterate remains the same (''b''<sub>5</sub> = ''b''<sub>4</sub>). 
# In the sixth iteration, we cannot use inverse quadratic interpolation because ''b''<sub>5</sub> = ''b''<sub>4</sub>. Hence, we use linear interpolation between (''a''<sub>5</sub>, ''f''(''a''<sub>5</sub>)) = (&minus;3.35724, &minus;6.78239) and (''b''<sub>5</sub>, ''f''(''b''<sub>5</sub>)) = (&minus;2.71449, 3.93934). The result is ''s'' = &minus;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.
# In the seventh iteration, we can again use inverse quadratic interpolation. The result is ''s'' = &minus;3.00219, which satisfies all the conditions. Now, ''f''(''s'') = &minus;0.03515, so we set ''a''<sub>7</sub> = ''b''<sub>6</sub> and ''b''<sub>7</sub> = &minus;3.00219 (''a''<sub>7</sub> and ''b''<sub>7</sub> are exchanged so that the condition |''f''(''b''<sub>7</sub>)| ≤ |''f''(''a''<sub>7</sub>)| is satisfied). (''Correct'' : linear interpolation {{tmath|1=s = -2.99436, f(s) = 0.089961}})
# In the eighth iteration, we cannot use inverse quadratic interpolation because ''a''<sub>7</sub> = ''b''<sub>6</sub>. Linear interpolation yields ''s'' = &minus;2.99994, which is accepted. (''Correct'' : {{tmath|1=s = -2.9999, f(s) = 0.0016}})
# In the following iterations, the root ''x'' = &minus;3 is approached rapidly: ''b''<sub>9</sub> = &minus;3 + 6·10<sup>&minus;8</sup> and ''b''<sub>10</sub> = &minus;3 &minus; 3·10<sup>&minus;15</sup>. (''Correct'' : Iter 9 : ''f''(''s'') =&nbsp;−1.4&nbsp;×&nbsp;10<sup>−7</sup>, Iter 10 : ''f''(''s'') =&nbsp;6.96&nbsp;×&nbsp;10<sup>−12</sup>)