A nice idea for a new video that would connect well to this one: Explain the ITP method, which has recently been adapted in many root solving libraries. Instead of making Newton's method secure, it is making bisection fast (without losing the worst-case behaviour). Also interesting is Chandrupatla's method, which has an inbuilt way to decide when to bisect and when to use quadratic inverse interpolation.
@OscarVeliz
2 ай бұрын
Adding to the queue. Thanks for the suggestions!
@AJ-et3vf
3 жыл бұрын
These videos are so nice. I get an idea or I imagine what a Newton bisection method would look like and I remember that you exactly have this in one of your videos! Thanks very much. This channel's very helpful for root-finding algorithms ❤️
@karstenonarheim6343
3 жыл бұрын
This was very informative; it helped me with a part of my final project for a CS class in java
@OscarVeliz
3 жыл бұрын
I'm glad this was helpful
@alexandrevachon541
3 жыл бұрын
I also found something about Bisection, while using the function (x - 1.75)^3 : if I start with the interval [1, 2], I find the root of 1.75 after a single iteration. This means that if the root is exactly the midpoint value of the initial interval, Bisection will find the root in one iteration.
@OscarVeliz
3 жыл бұрын
If you started with [1.5, 2] then it would find it in zero iterations. All of these methods can get lucky and find the root immediately. We usually aren't concerned with the best case but rather the expected case and the worst case.
@alexandrevachon541
3 жыл бұрын
@@OscarVeliz I had something in my mind today, and it's about adding inverse quadratic interpolation, in a similar fashion to Brent's method, forming an IQI-Newton-Bisection hybrid. Would it work well? But a reminder: IQI requires three points, so it doesn't work on the first iteration.
@OscarVeliz
3 жыл бұрын
It could work but Newton's is faster so you wouldn't really need to... With Brent, IQI is faster than Secant so it makes sense to switch up.
5 жыл бұрын
that's the problem... in numerical recipes the condition "not converges fast enough" is different, it checks if(abs(2.0*f) > abs(dxold*df)), but if you look at code close enough you see that 'dxold' is not previous step lengh, but second to previous! dxold - second to previous step size dx - previous step size f,df - current function evaluation (hence f/df - current step size). perhaps it's a bug in numerical recipes?
@OscarVeliz
5 жыл бұрын
I think you're on to something. I hadn't paid too close attention when I programmed my own version of the hybrid; trying to create it just from the descriptions from Acton and Numerical Recipes. Notice too that when they do force a bisection they save dx into dxold which will be compared against in the next loop iteration. I would have expected it to be reinitialized to be the same as dx like they do before the loop. The tricky thing is that they never justified the condition they give (like I did with what I think is meant to be the correct condition). Perhaps they do so in later editions of the book or maybe they fixed it.
5 жыл бұрын
@@OscarVeliz i found some clues: " The reason for comparing to the step before last seems essentially heuristic: Experience shows that it is better not to “punish” the algorithm for a single bad step if it can make it up on the next one." which seems completely wrong to me, because a function could be constructed that alternates between step multipliers 0.5. That could take as much as 60 function evaluations for 1e-8 tolerance, while bisection would take only 30. oh well, looks like there are no free lunches after all :/
@presidentevil9951
4 жыл бұрын
"simply switch to bisection" LOL I understood this video This method is good creative and funny at the same time
@harukeyn5580
4 жыл бұрын
At 3:54 you say shrink [a,b] based on sign fx, how to interpret this? Based on the example you show afterwards I would say if one of the two has the same sign, then either a=x or b=x. But what if my interval is only positive or negative values, what would happen then?
@OscarVeliz
4 жыл бұрын
See the discussion regarding variations on Newt-Safe starting at 7:18
@djamelaitamrane9226
3 жыл бұрын
Any body knows any link about the rtsafe() in C. I have found only the single rtsafe, will be very glad to get a complet C code with f(x) and f'(x).
@hewu56
3 жыл бұрын
how can I use this method to solve nonlinear equations?
@OscarVeliz
3 жыл бұрын
I will post a video on Generalized Newton's Method in the next few weeks. You can check out similar videos on Fixed Point Iteration for Systems of Equations kzitem.info/news/bejne/2Zdo3Impknx1YJg and Generalized Aitken-Steffensen kzitem.info/news/bejne/jq5vxZqJh6SJZqw if you need a solution method right now.
@hewu56
3 жыл бұрын
@@OscarVeliz Thank you so much for your reply and looking forward to your next video.
@OscarVeliz
3 жыл бұрын
It is up kzitem.info/news/bejne/0WaJqKmYjpionH4
@hewu56
3 жыл бұрын
@@OscarVeliz Thanks a lot. Dear sir, Can we use the Newton-Bisection Hybrid method to solve nonlinear equations? Based on the Newt-Safe method , we need to adjust the boundary (a, b) dynamically. How can I do this for nonlinear equations?
@OscarVeliz
3 жыл бұрын
I misunderstood your question early as I thought you were referring to systems of nonlinear, not just a single nonlinear. The example functions I showed in this video on Newton-Bisection were nonlinear, like the arctangent. As far as adjusting the boundary, the rules are already built-in to the algorithm and are independent of the function being used. Check out my example program (on GitHub) to see those rules for adjusting the interval in action.
@alexandrevachon541
4 жыл бұрын
I made a partially successful attempt at making a Newton-Bisection fractal, by testing the arctangent function. See here: github.com/avachon100501/ultrafractalcollection/blob/main/photos/newt-safe/Newt-Safe1.png Compared with Halley: github.com/avachon100501/ultrafractalcollection/blob/main/photos/halley/HalleyAtan.png It shows that unlike Newton, which it diverges, it successfully converges in the same point as Halley. My code here: github.com/avachon100501/ultrafractalcollection/blob/main/Root-Finding/Newton-Bisection%20Hybrid.ufm
@OscarVeliz
4 жыл бұрын
Your default a and b should have different signs when evaluating the function and it looks like you've chosen the values 1 and 2 which for arctan are both positive. The real question though is "what does it even mean to do bisection on the complex plane?" and for that I've mentioned a few other algorithms in previous comments.
@alexandrevachon541
4 жыл бұрын
@@OscarVeliz I also noted something: if (f(x)*f(a)) is smaller than zero, shouldn't it be: a = x, f(a) = f(x), otherwise if (f(x)*f(a)) is greater than zero, then b = x, f(b) = f(x)? Your code says: if fx * fa < 0.0 then b:= x; fb:= fx; else a:= x; fa:= fx; end if; Is it a mistake? I experimented on something: what if I replaced the Bisection step in the Newt-Safe algorithm by the regula falsi step, in a sort of Newton-Regula Falsi hybrid algorithm? Would it give better results?
@OscarVeliz
4 жыл бұрын
At the end of that loop we've taken a Newton step giving a new value for x. Then we want to play catch-up and move either a or b to overlap that x, while still keeping the interval valid. I believe the original code is correct.
@alexandrevachon541
4 жыл бұрын
Upon analysis, using f(x) = arctan(x), with a = -1, b = 3 and an epsilon of 10^(-6): Newton-Bisection: 0. x = 1, [-1, 3], f(x) = 0.785398, f(a) = -0.785398, f(b) = 1.249046 1. x = -0.570796, [-0.570796, 3], f(x) = -0.518669, f(a) = -0.518669, f(b) = 1.249046 2. x = 0.116860, [-0.570796, 0.116860], f(x) = 0.116332, f(a) = -0.518669, f(b) = 0.116332 3. x = -0.001061, [-0.001061, 0.116860], f(x) = 0.001061, f(a) = -0.001061, f(b) = 0.116332 4. x = 0, [0, 0.116860] It took four iterations to find the root (x4 = 0). Newton-Regula Falsi: 0. x = 0.544202, [-1, 3], f(x) = 0.498381, f(a) = -0.785398, f(b) = 1.249046 1. x = -0.101778, [-1, -0.101778], f(x) = -0.101429, f(a) = --0.785398, f(b) = -0.101429 2. x = 0.000702, [-0.101778, 0.000702], f(x) = 0.000702, f(a) = 0.000702, f(b) = -0.101429 3. x = 0, [0, 0.000702] This new algorithm that I created (unless it was already created before) needs only three iterations to find the root (x3 = 0), in other words, it saved one iteration.
@OscarVeliz
4 жыл бұрын
I would suspect others have looked at Newton-Bisection hybrid and swapped in Regula Falsi but I do not know for certain. This would require some literature searching.
@goop69_
7 ай бұрын
useless video, no coding
@OscarVeliz
7 ай бұрын
Code is provided in the GitHub repo for the channel. Link in description.
Пікірлер: 39