would love to see Interpolate Truncate and Project nad maybe ridders methods but i know its time consuming keep up the great work
11 місяців тому+2
Great video. If you ever feel like getting back to this topic, I'd love to see your take on TOMS 748, which is considered(?) superior to Brent's method (albeit, some doubt has been cast from a very thorough review by Gregory W. Chicares).
Hi Oliver, when you have 3(a+b)/4 at 11:05, is that your guessed value of c for the second iteration of IQI or is it some other variable? If not then what is 3(a+b)/4?
c is always the old value of b (initially a). In Dekker we test if s is between b and (a+b)/2 but Brent tests between b and 3(a+b)/4 since IQI needs the additional space.
Remember what you said about a criteria: if the sign of the function of new b is the same as the sign of the function of a, the new a is the old value of b, otherwise a is itself. But what happens if either of these functions were zero? Which condition prioritizes the other?
Two things. At the initial iteration a and b can't be a zero because you start assuming they are different signs (which is easy enough to add logic to check). Therefore, the only way a or b would would be a zero during normal iteration could only happen if their previous s or m were zero which Brent adds checks for and returns when true. Therefore the iteration would stop before assigning that zero to a or b. QED
@@OscarVeliz I was trying to find the root of f(x) = (x - 1.75)^3 = 0, with the interval [1, 2]. At the first iteration, assuming that I followed steps, the function f(b_new) is equal to zero, and m is equal to 1.75, which is our root. If f(b_new) is zero, which is in our case, I get confused, because I don't know if the signs of f(b_new) and f(a) are the same or not.
matlab code for those who want: function [xi, Fi, xs, Fs, i] = Brents(Func, xl, xu, er, N) xs=zeros(1,N+1); Fs=zeros(1,N+1); a = xl; b = xu; c = a; d = b - c; e = d; Fa=Func(a); Fb=Func(b); Fc=Fa; F=[Fa, Fb]; x=[a, b]; if prod(F>0) error('Root is not bracketed in [xl, xu]') end [~,indx] = min(abs(F)); Fs(1)=F(indx); xs(1)=x(indx); for i = 1:N if sign(Fa) == sign(Fb) % (If necessary, rearrange points) a = c; Fa = Fc; d = b-c; e = d; end if abs(Fa) < abs(Fb) c = b; Fc=Fb; b = a; Fb=Fa; a = c; Fa=Fc; end m=0.5*(a-b); % (Choose open methods or bisection) if abs(e)>= er && abs(Fc) > abs(Fb) s = Fb / Fc; if a==c % Secant method p = 2 * m * s; q = 1 - s; else % (Inverse quadratic interpolation) q = Fc / Fa; r = Fb / Fa; p = s * (2 * m * q * (q - r) - (b - c) * (r - 1)); q = (q - 1) * (r - 1) * (s - 1); end if p > 0 q = -q; else p = -p; end if 2 * p < 3 * m * q - abs(er * q) && p < abs(0.5 * e * q) e = d; d = p / q; else d = m; e = m; end else d = m; e = m; end c = b; Fc = Fb; if abs(d) > er b = b + d; else b = b - sign(b - a) * er; end Fb = Func(b); Fs(i+1)=Fb; xs(i+1)=b; if abs(m)
We are having at our couse of numerical mathematics a method (after we had fixiteration method, bisection method, newton method, and secant method) called "Global newton method" which mixes the bisection and the newton method. Do you have an idea, or a video about this method?
Oscar Veliz, have you tried making fractals based on the Brent-Dekker, bisection and regula falsi methods? I have a lot of hard time making attempts to make it work. Is it doable?
I have not tried making fractals based on those methods. Generalizing Bisection and other interval-based approaches to the complex plane is not straightforward. Check out the paper "A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane" by Wilf, which is essentially an improved version of Weyl's algorithm. Also take a look at "Approximating Complex Polynomial Zeros: Modified Weyl's Quadtree Construction and Improved Newton's Iteration" by Pan, that resembles a generalized Newt-Safe for the complex plane. I might make videos on these... no promises.
I think IQI can also fail if your three points happen to be colinear. Am I wrong? Side note, I would appreciate it if you broke these videos down into multiple videos. IQI, Brent, Dekker. There is a lot of content here and plenty to go over; they are worthy of their own videos, I would argue. Youre feeding us arguably too large of bites at a time.
IQI would fail in that case. I actually went back and forth on splitting these topics. I decided though that if someone started watching a video on just Brent's Method that said go watch Dekker's Method then UA-cam would penalize it. I did put chapter markers though so people can go directly to just the Brent part if they want.
@@OscarVeliz They penalize you for referencing other videos, as suitable followups or necessary prerequisites? Kind of hard to build content up in lesson-form without doing one 500 hour video. BS. I hope they hit MIT's channel as their content builds on each other and references prior lessons. YT is kind of trash these days; migrate over to one of the competitor platforms, my guy. Many people are, and I spend more time there than here anymore. Fast growing, and you want to get in on the ground floor. Let me tell you, there are not a lot of math videos on those platforms. You have little competition.
YT cares about watch time and retention. A good metric is to have 20% still watching after the first 30 seconds. Clicking off the vid can count as someone who didn't finish. In Mist's case, all of their videos are usually recommended in order anyway so pre-reqs are more for those who weren't aware of what they came across or somehow landed on something more advanced than they thought. Their channel has amazing watch time and completion metrics. Smaller channels like this one, with much shorter videos, doesn't get as much attention.
Great work. Thank you for this amazing content.
You did a great job! Thank you very much!
would love to see Interpolate Truncate and Project nad maybe ridders methods but i know its time consuming keep up the great work
Great video. If you ever feel like getting back to this topic, I'd love to see your take on TOMS 748, which is considered(?) superior to Brent's method (albeit, some doubt has been cast from a very thorough review by Gregory W. Chicares).
Thank you!!!! It is very clear
Perfect video!
Hi Oliver,
when you have 3(a+b)/4 at 11:05, is that your guessed value of c for the second iteration of IQI or is it some other variable? If not then what is 3(a+b)/4?
c is always the old value of b (initially a). In Dekker we test if s is between b and (a+b)/2 but Brent tests between b and 3(a+b)/4 since IQI needs the additional space.
Remember what you said about a criteria: if the sign of the function of new b is the same as the sign of the function of a, the new a is the old value of b, otherwise a is itself. But what happens if either of these functions were zero? Which condition prioritizes the other?
Two things. At the initial iteration a and b can't be a zero because you start assuming they are different signs (which is easy enough to add logic to check). Therefore, the only way a or b would would be a zero during normal iteration could only happen if their previous s or m were zero which Brent adds checks for and returns when true. Therefore the iteration would stop before assigning that zero to a or b. QED
@@OscarVeliz Yeah. But what if f(b_new) or f(a) themselves were zero? Would a_new = b_old or a_new = a_old?
Give it a second glance. b_new is either s or m. There is a check to see if s or m are zeros. They would never get assigned to b_new if they were.
@@OscarVeliz I was trying to find the root of f(x) = (x - 1.75)^3 = 0, with the interval [1, 2]. At the first iteration, assuming that I followed steps, the function f(b_new) is equal to zero, and m is equal to 1.75, which is our root. If f(b_new) is zero, which is in our case, I get confused, because I don't know if the signs of f(b_new) and f(a) are the same or not.
Sorry I meant b or s see 10:38
At about 11:52, why check |s-b|
this is a great video
matlab code for those who want:
function [xi, Fi, xs, Fs, i] = Brents(Func, xl, xu, er, N)
xs=zeros(1,N+1);
Fs=zeros(1,N+1);
a = xl;
b = xu;
c = a;
d = b - c;
e = d;
Fa=Func(a);
Fb=Func(b);
Fc=Fa;
F=[Fa, Fb];
x=[a, b];
if prod(F>0)
error('Root is not bracketed in [xl, xu]')
end
[~,indx] = min(abs(F));
Fs(1)=F(indx);
xs(1)=x(indx);
for i = 1:N
if sign(Fa) == sign(Fb) % (If necessary, rearrange points)
a = c;
Fa = Fc;
d = b-c;
e = d;
end
if abs(Fa) < abs(Fb)
c = b; Fc=Fb;
b = a; Fb=Fa;
a = c; Fa=Fc;
end
m=0.5*(a-b);
% (Choose open methods or bisection)
if abs(e)>= er && abs(Fc) > abs(Fb)
s = Fb / Fc;
if a==c % Secant method
p = 2 * m * s;
q = 1 - s;
else % (Inverse quadratic interpolation)
q = Fc / Fa;
r = Fb / Fa;
p = s * (2 * m * q * (q - r) - (b - c) * (r - 1));
q = (q - 1) * (r - 1) * (s - 1);
end
if p > 0
q = -q;
else
p = -p;
end
if 2 * p < 3 * m * q - abs(er * q) && p < abs(0.5 * e * q)
e = d;
d = p / q;
else
d = m;
e = m;
end
else
d = m;
e = m;
end
c = b;
Fc = Fb;
if abs(d) > er
b = b + d;
else
b = b - sign(b - a) * er;
end
Fb = Func(b);
Fs(i+1)=Fb;
xs(i+1)=b;
if abs(m)
We are having at our couse of numerical mathematics a method (after we had fixiteration method, bisection method, newton method, and secant method) called "Global newton method" which mixes the bisection and the newton method. Do you have an idea, or a video about this method?
It isn't a method I'm familiar with. I imagine it would work similar to Brent.
Okay, thx a lot for every answer!!
I realize is rather late coming, but I did find out about a Global Newton Method and made a video about it ua-cam.com/video/BGZfHxzZ-7c/v-deo.html
Oscar Veliz, have you tried making fractals based on the Brent-Dekker, bisection and regula falsi methods? I have a lot of hard time making attempts to make it work. Is it doable?
I have not tried making fractals based on those methods. Generalizing Bisection and other interval-based approaches to the complex plane is not straightforward. Check out the paper "A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane" by Wilf, which is essentially an improved version of Weyl's algorithm. Also take a look at "Approximating Complex Polynomial Zeros: Modified Weyl's Quadtree Construction and Improved Newton's Iteration" by Pan, that resembles a generalized Newt-Safe for the complex plane. I might make videos on these... no promises.
@@OscarVeliz I think I might have successfully rendered a Newton-Bisection fractal. See here: fractalforums.org/index.php?topic=3499.msg25627#msg25627
Why (3a + b)/4?
I think IQI can also fail if your three points happen to be colinear. Am I wrong?
Side note, I would appreciate it if you broke these videos down into multiple videos. IQI, Brent, Dekker. There is a lot of content here and plenty to go over; they are worthy of their own videos, I would argue. Youre feeding us arguably too large of bites at a time.
IQI would fail in that case.
I actually went back and forth on splitting these topics. I decided though that if someone started watching a video on just Brent's Method that said go watch Dekker's Method then UA-cam would penalize it. I did put chapter markers though so people can go directly to just the Brent part if they want.
@@OscarVeliz They penalize you for referencing other videos, as suitable followups or necessary prerequisites? Kind of hard to build content up in lesson-form without doing one 500 hour video. BS. I hope they hit MIT's channel as their content builds on each other and references prior lessons. YT is kind of trash these days; migrate over to one of the competitor platforms, my guy. Many people are, and I spend more time there than here anymore. Fast growing, and you want to get in on the ground floor. Let me tell you, there are not a lot of math videos on those platforms. You have little competition.
YT cares about watch time and retention. A good metric is to have 20% still watching after the first 30 seconds. Clicking off the vid can count as someone who didn't finish. In Mist's case, all of their videos are usually recommended in order anyway so pre-reqs are more for those who weren't aware of what they came across or somehow landed on something more advanced than they thought. Their channel has amazing watch time and completion metrics. Smaller channels like this one, with much shorter videos, doesn't get as much attention.