Brent’s Method of Finding Roots and Inverse Functions: Algorithms for Grad Students (1)

[@ImprobableMatter]

Not related to the “Finch Method” of throwing a shoe.

[@ihmejakki2731]

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!

[@Danji_Coppersmoke]

This channel is a gem. I started with fusion. It is great.

[@biesing]

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!

[@ImprobableMatter]

Yes, I suppose you're right, you could solve Lithium as well with the Quartic formula after a lot of pain. 😆

[@ImprobableMatter]

@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.

[@stanleydodds9]

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.

[@ImprobableMatter]

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.

[@azzamdaaboul1619]

Great video! How do you create your 2D animated explanatory videos, and what software do you use?

[@ImprobableMatter]

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).

[@garyknight8616]

Brilliant. Very well explained! Liked and subscribed.

[@BubblesTheAlphaWhale]

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.

[@ImprobableMatter]

Yes. Run them at an energy loss to produce neutrons from D-D reactions and line the walls with problematic isotopes.

[@BubblesTheAlphaWhale]

@@ImprobableMatter holy smokes u responded awesome... and thanks

[@ciCCapROSTi]

Brent's method sounds like generating a Taylor series from measurements.

[@ImprobableMatter]

A little bit, but crucially it doesn't use derivatives (the Taylor series does), which is meant to improve performance.

[@RUDRARAKESHKUMARGOHIL]

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....

[@ImprobableMatter]

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.

[@RUDRARAKESHKUMARGOHIL]

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...

[@CognitiveGear]

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.

[@ImprobableMatter]

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.

[@FrancoisQian]

you should explain fission to put your fusion videos in perspective

[@Law0086]

6:27 could you get a similar outcome if y>0? Such as .03? Not a student or anything. Just a regular joe schmo.

[@ImprobableMatter]

Sure. For y

[@Law0086]

That's insanely cool. Thanks for that. Any integer. Just depends on what part of quadrant you're on.

[@ryanwaldt1710]

What are you thoughts on quantum kinetics corporation

[@RUDRARAKESHKUMARGOHIL]

can you tell how you arrived at equation of Xq at 5:07....

[@ImprobableMatter]

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.

[@RUDRARAKESHKUMARGOHIL]

Sorry but I didn't learnt that yet so...

[@wolpumba4099]

*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

[@fabienleguen]

Why do you need highly efficient algorithm for plasma physic ? Real time diagnostics and control ?

[@RUDRARAKESHKUMARGOHIL]

Bisection method is binary search in function !

[@battlelawlz3572]

Couldn’t finding roots be used to crack digital encryption keys? (im bad at math :p)

[@ImprobableMatter]

In short: kind of, but not really.

[@theletter4349]

I would solve it using the lambert w function then use it's integral represention.

[@MadeleineTakam_Info_on_Profile]

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.

[@alekseiorig]

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.

[@ILLUSTRON-l5v]

❤

[@leflavius_nl5370]

Crystal math labs

[@infty1369]

i hate this so much.

[@XpnLef]

First