Brent’s Method of Finding Roots and Inverse Functions: Algorithms for Grad Students (1)
Вставка
- Опубліковано 26 січ 2025
- Also discusses the Saha Equation, which is fundamental to plasma physics.
References
[1] Image of a Casio fx-85GT X Classwiz calculator, (User: L ke)
commons.wikime...
[2] R. P. Brent, Personal Home Page,
maths-people.a... (Accessed 02/08/24)
[3] R. P. Brent, “An algorithm with guaranteed convergence for finding a zero of a function”, The Computer Journal 14, 422 (1971).
[4] R. P. Brent, “Algorithms for Minimisation without Derivatives”, p. 47 (Prentice Hall, 1972).
[5] Scipy Github (Zeros subdirectory), github.com/sci... (Accessed 31/07/24)
[6] Experimental double-resonance solid-state Tesla coil II by Dr. Antônio Carlos M. de Queiroz
commons.wikime...
[7] M. R. Zaghloul, et al., “A simple formulation and solution strategy of the Saha equation for ideal and nonideal plasmas”, J. Phys. D: Appl. Phys. 33, 977 (2000).
[8] Image of a helium filled discharge tube shaped like the element’s atomic symbol (User: Pslawinski)
commons.wikime...
[9] Green plasma in xenon-nitrogen mixture by Carl Willis,
• Green plasma in xenon-...
[10] B. A. Remington et al., “Rayleigh-Taylor instabilities in high-energy density settings on the National Ignition Facility” PNAS 116, 18233 (2019).
Not related to the “Finch Method” of throwing a shoe.
I was just using the scipy Brent's method to calculate some inverse functions for my masters thesis, but I didn't dig into the machinery behind the method. Very cool video!
This channel is a gem. I started with fusion. It is great.
Lithium ionization fraction results in a quartic left to be solved (12:19)
When the free electron density is high, you need to change the equation to stay accurate (12:33)
except for the cases of low density hydrogen and helium, we can't find the roots analytically (13:05)
Hydrogen and helium are quadratics and cubics without high electron density - it makes sense why they can be solved analytically
so why not lithium - a quartic? quartics can be solved in general, but not quintics or higher atleast in the general case
(en.wikipedia.org/wiki/Abel_Ruffini_theorem)
Is there some underlying physics cause?
Does it just never occur in low enough density realistically?
Hope this doesn't seem like a nit-pick, atleast it was not intended as such; I am more so curious about this and as you have already researched this it feels appropriate to ask you.
Thanks for the cool video!
Yes, I suppose you're right, you could solve Lithium as well with the Quartic formula after a lot of pain. 😆
@yak-i4c Yeah, and you don't actually need to take any roots for the inverse quadratic interpolation. Once you've evaluated the function, it's all just primitives to calculate the new x values. Have a pause at 05:23 for example.
3:20 the function being one-to-one in a given interval (i.e. being an injection in that interval) along with something like it being continuous and knowing that the image of the function contains a positive and a negative value does imply that it has a single root (that's basically just IVT + injective). However, just knowing that it has a single root does not mean the function is one-to-one in the whole interval, or indeed in any interval at all. With some stronger smoothness conditions (like it being analytic), it only implies that it is one-to-one in *some* sufficiently small interval around the root (and then obviously all smaller intervals). I'm guessing these details are what is meant by this equivalence written on screen, because this is all basic real analysis stuff that everyone knows, but anyway, maybe it's a tiny bit misleading.
An example of a continuous function that has exactly one root, but in every interval around the root it is not injective, would be something like f(x) = x(sin(1/x) + 2) for x not 0, and f(0) = 0. To prove it is continuous, x = 0 is the only point that needs to be checked, and by bounding sin it is easy to get continuity. Showing it has exactly one root is easy again by bounding sin. Showing it is not injective in any neighbourhood of 0 is not trivial to do rigorously, but it should be clear that the sin part oscillates enough near 0 for this to easily be the case.
Agreed, but the reason for the "stronger" assertion that I make (the presence of a single root implies it should be one-to-one) should make sense later in the video.
We want to use Brent's algorithm to invert a function in a given interval. Therefore, given an interval, we want to be able to find the roots of f(x)-y in that said interval for any y in that range. If the function is not one-to-one, that clearly won't work.
Not sure if I've explained myself well, but there we go.
Hey random question that has nothing to do with this video. Could tokamaks and other fusion devices be used to reduce the lifespan of radioactive waste? I think u briefly mentioned this in a previous video.
Yes. Run them at an energy loss to produce neutrons from D-D reactions and line the walls with problematic isotopes.
@@ImprobableMatter holy smokes u responded awesome... and thanks
Brent's method sounds like generating a Taylor series from measurements.
A little bit, but crucially it doesn't use derivatives (the Taylor series does), which is meant to improve performance.
Great video! How do you create your 2D animated explanatory videos, and what software do you use?
I use Inkscape to make the still graphics (often use Python if I need data as in this case). Then just any video making program can animate them (fade in and so on).
at 7:28 you said x belongs to [y/2,y] so for our example it will be [1.5,3] no ? also can you tell which method(bisection,quadratic,secant) to be used when because for me the best seeming is secant and most ugly the quadratic one....
Yes, that's correct, the interval shown at 07:28 is [1.5,3.0].
For which method to use, that's what Brent's method is there to determine - it tries to pick one of those three at every step. It will pick different ones at different steps, so for example it might do Secant, then Quadratic, then bisection.
Sorry but I think i didn't get that or missed that part in video can you pls tell what is the timestamp where Brent method tell which method to determine out of 3...
Brilliant. Very well explained! Liked and subscribed.
6:27 could you get a similar outcome if y>0? Such as .03? Not a student or anything. Just a regular joe schmo.
Sure. For y
That's insanely cool. Thanks for that. Any integer. Just depends on what part of quadrant you're on.
can you tell how you arrived at equation of Xq at 5:07....
It's a standard Inverse Quadratic interpolation formula. You could also derive it by setting x as a quadratic in y and then solving where y=0.
Sorry but I didn't learnt that yet so...
For the initial problem given at the beginning of the video, isn't brent's method strictly inferior to newton's method? The derivative is continuous & trivial and using it in an exam situation is more feasible.
If you're talking about solving it with only a calculator: yeah, you could absolutely go that way. The iterative formula from Newton's method is slightly bulkier, but should be doable.
you should explain fission to put your fusion videos in perspective
*Summary*
* *(**0:00:10**) Solving Difficult Equations:* The video explains how to solve equations that can't be rearranged easily, specifically those involving logarithms or exponential terms.
* *(**0:00:59**) Iterative Formula and its Limitations:* An initial method using an iterative formula (guessing and refining the answer) is presented, but it's noted to be slow and unreliable.
* *(**0:03:01**) Brent's Method Introduction:* A more robust method called Brent's method is introduced, which is faster and more reliable for finding the root of an equation.
* *(**0:03:48**) Components of Brent's Method:* Brent's method uses three techniques:
* *(**0:04:02**) Bisection:* Dividing an interval in half repeatedly to narrow down the root's location.
* *(**0:04:23**) Secant Method:* Using a straight line approximation to estimate the root.
* *(**0:04:52**) Inverse Quadratic Interpolation:* Using a parabolic approximation to estimate the root.
* *(**0:05:44**) Key Requirement of Brent's Method:* It requires specifying an interval containing only one root of the equation.
* *(**0:07:36**) Python Implementation:* The `BrentQ` function from the SciPy library in Python can be used to implement Brent's method.
* *(**0:08:58**) Plasma Physics Application:* The video then demonstrates how Brent's method can be used to calculate the ionization fraction of a plasma (a hot, ionized gas), a complex problem involving the Saha equation. This illustrates the method's practical use in scientific applications.
* *(**0:14:03**) In summary, the video provides a clear explanation of Brent's method, a powerful numerical technique for solving difficult equations and its application in a real-world scientific context.*
I used Google Gemini 1.5 Pro exp 0801 to summarize the transcript.
Cost (if I didn't use the free tier): $0.1170
Time: 34.22 seconds
Input tokens: 31170
Output tokens: 749
Why do you need highly efficient algorithm for plasma physic ? Real time diagnostics and control ?
What are you thoughts on quantum kinetics corporation
Couldn’t finding roots be used to crack digital encryption keys? (im bad at math :p)
In short: kind of, but not really.
Imagine coming up with multiple complicated sequential methods just to solve one type of equation.
This comment was sponsored by the Monte Carlo Method gang.
Bisection method is binary search in function !
I would solve it using the lambert w function then use it's integral represention.
Sorry only got to 5:12, before I realised this is way above me. I need at least 10 minutes of kitten video’s now to recover.
❤
Crystal math labs
i hate this so much.
First