2

Use Brent's algorithm to find all real roots of the equation $$9-\sqrt{99+2x-x^2}=\cos(2x),\\ x\in[-8,10]$$

I am having difficulty understanding Brent's algorithm. I looked at an example in wikipedia and in my book but the examples given isn't the same as this question. Any help will be greatly appreciated.

Mhenni Benghorbal
  • 47,431
Tom
  • 1,079

2 Answers2

4

I would start by looking at the problem and trying to analyze it with other methods.

If we plot these two functions over the indicated range, we have:

enter image description here

As you can clearly see, there are eight roots.

These are located at:

  • x = -3.80962245582300...
  • x = -2.08783181165642...
  • x = -1.21128304795669...
  • x = 1.49277841962787...
  • x = 1.67831642586421...
  • x = 4.17818286865309...
  • x = 5.54381657586530...
  • x = 6.64685888158733...

The original Brent paper has the Algo based algorithm.

For Brent's method, of course, you are going to write:

$f(x) = -9 + \sqrt{99+2x-x^2} + \cos 2x , x\in [-8,10]$

Now, you would 'single step' through each line in the algorithm, test the conditional and continue until a root is found.

Amzoti
  • 56,093
  • Very very cool! Nice work, Amzoti! +1 – amWhy Apr 14 '13 at 02:01
  • As you said, I am trying to figure out how to use it to crank the roots. Thanks very much! – Tom Apr 14 '13 at 02:04
  • But first: @user71642, you do know how the secant and bisection methods work, yes? Brent's method is nothing more than a clever way to get the best of both worlds... – J. M. ain't a mathematician Apr 14 '13 at 02:21
  • How can I find the roots specifically using Brent's algorithm ? – Tom Apr 14 '13 at 02:27
  • Have you gone through the very detailed example on the Wiki? Did you go through that and compare step by step with the algorithm? That is about as detailed as one get on an example. – Amzoti Apr 14 '13 at 02:55
  • Amzoty, yes I have. Some of the information given on wiki I dont understand how to translate it to $$9-\sqrt{99+2x-x^2}=cos(2x),\ x\in[-8,10]$$ – Tom Apr 14 '13 at 03:25
  • @user71642: See update for $f(x)$, is that what is confusing you? You know $a$ and $b$ and can actually change those to much smaller ranges to make it easier. – Amzoti Apr 14 '13 at 03:29
  • So I must use directly each step from the wiki example to find the roots? – Tom Apr 14 '13 at 07:31
  • I meant to say exactly* instead of directly. – Tom Apr 14 '13 at 07:44
  • @user71642: Now that you $f9x)$, you would 'single step' through each line in the algorithm, test the conditional and continue until a root is found. – Amzoti Apr 14 '13 at 12:51
  • @user71642, you still haven't answered my question. Do you know how to do the bisection and secant methods? – J. M. ain't a mathematician Apr 14 '13 at 12:59
  • FWIW, if OP can obtain the classic Algorithms for minimization without derivatives, that might help; it too has a a good description of Brent-Dekker. – J. M. ain't a mathematician Apr 14 '13 at 13:00
  • @J.M. Thanks and yes I do know about bisection and secant methods, but I was asked to perform this using Brent's algorithm which wasn't thoroughly taught to us like bisection and secant methods. – Tom Apr 15 '13 at 01:05
  • 1
    @user71642 As I said, the method is precisely a way to use either of bisection or secant, whichever one of them is appropriate. The idea is to almost always use the secant method, unless the estimate of the secant method gives an estimate that is outside the brackets you are maintaining; if that happens, then you perform bisection. So, think of it as a safer version of the secant method. – J. M. ain't a mathematician Apr 15 '13 at 01:12
  • @J.M. Thanks for clearing that up! I will use your idea. – Tom Apr 15 '13 at 01:37
  • 1
    @J.M.isn'tamathematician Minor detail, what you are describing is Dekker's method. Brent's method tries to also use inverse quadratic interpolation instead of the secant method when possible. – Simply Beautiful Art Oct 22 '20 at 16:26
0

The wikipedia entry you cite explains Brent's algorithm as a modification on other ones. Write down all algorithms that are mentioned in there, see how they go into Brent's. Perhaps try one or two iterations of each to feel how they work.

Try to write Brent's algorithm down as a program in some language you are familiar with. Make sure your program follows the logic given.

Run your program on the function given (or some simpler one), and have it tell you what it is doing each step. Look over the explanation to see why that step makes sense, check what the alternative would have been.

As a result, you will have a firm grasp of the algorithm (and some others, with their shortcommings and strong points), and thus why it is done the way it is.

[Presumably that is what this assignment is all about...]

vonbrand
  • 27,812