The Secant Method for Root Finding Explained

[00:00:06]I have a function I tried some experiment I substituted a point it's not zero it's not a root okay I want to improve it and using the tangent line I get the formula which leads to the Newton method and I'm really unhappy about the derivative here so my question is can I do something about the derivative while keeping the general idea and actually uh at the beginning of the course uh we had a chapter on approximating derivatives we needed to know the function at two points that was enough now as it happens before I go to XK there must have been another approximation XK minus one so it means I actually know the function at two places and therefore I can approximate the derivative at X XK can be approximated by and here is a triangle which way do I want to play it it doesn't really make any difference so let's start at XK minus fxk minus one that's the difference in value divided by difference in the horizontal uh Direction okay I put it here into my formula and something happens uh the difference in values will be in the denominator and the difference in X's will come to the top so let's see XK minus the function values will go down and on the top that will be fxk time XK minus XK minus one and of course if you want you can switch the order but since you doing it both places it gives you the same answer okay what next come on denominator that's a good idea come on denominator well let's see let's see let's see uh I have to take XK and multiply it by this expression and I'm going to break it into pieces so XK fxk that's one of them I'm multiplying out the bracket if you want then there will be minus XK fxk Min - one then there will be minus fxk XK minus minus yields plus uh F XK XK minus one okay there should be some cancelling I remember from home uh I've been looking at it and I saw there is something fishy what's X there is no X it's XK yeah now it looks better and I can see the cancelling here we go let's write it nicely which order do I prefer okay I'll start with that one fxk XK minus one minus F XK minus one XK so you can see the indices just switched so that's nice it's a nice picture to have and in the denominator I'm just subtracting FS without those AES so it's a very nice formula a Statics also plays a role in mathematics if the formula is nice we like it and perhaps we remember it better that's a nice formula uh do we need to remember it by the way the answer is no I want you to know the bisection method and the Newton method because they are like blueprints for everything that comes afterwards this one uh I don't like I mean I like the formula but it's too complicated for my taste so yeah I'm not going to ask for the formula on the test you won't have to do calculations by hand for this method on the test it's a method yeah it moves us from XK and XK minus one to XK + 1 so it's a new type of a method before we went like that but now now we also need to know something about the past now when you think about it logically if you need to know the past also for the next step how do you start it and the answer is well you have to make two guesses and then you can keep going so that's a new method it's called secant method why because I could derive exactly the same formula but from a different story let's go back to our picture I know my function at two distinct places if I connect them by a secant line I can ask for the intersection with the xaxis and that would be XK + 1 so the Newton method I I said that I would prefer the name tangent method for the Newton method and that's exactly one of the reasons why I like to see that way Newton method went by tangents the secant method goes by secant that's a nice coincidence nice name uh you can calculate the equation of this line and then find its intersection just like we did for the Newton we found the equation of the tangent line and find intersection you can do the same work for the secant line and you would arrive at exactly this formula so it's not really difficult and it has a nice geometric interpretation what do I do next well I have the last two points I connect and so one here we go that's the root okay so the secant method based on the picture looks quite fast because you know I'm approaching the root really nicely let's make it official uh here we go so the second method for finding root we have a function which is continuous I don't need derivative that's a big Advantage I start with two points X not and X1 and then I'm just following the formula and for some reason when I was typing it I prefer to start here with XK minus one it's the same yeah and then there is a stopping condition because again we have the same problem how do we control the error so the answer is we cannot control the error so there is no error control it's not a bracketing method so everything that we said about the error regard regarding the Newton method I mean the general points they are still valid we cannot really tell precisely what the error is so we have to apply stopping conditions when I look here I can see that I'm suggesting two stopping conditions the first stopping condition is the absolute difference I'm looking at the difference of the last two approximations and if it's small enough I say okay that's enough the second possibility is I'm going to buy the value and we know that none of them is reliable and we also know that we cannot do really B so the same story uh unreliable and again the same story imagine uh okay camel let's try this one caml is quite bad for it as well for the secon method but this one is nice to see if you are unlucky and you guess your two numbers here in this region then the second line will bring you here and you have two values you connect them and the secant line brings you here and you have secant line and so on and you can see where it leads you would go to Infinity with your approximations not very nice you will never get to this root so essentially the behavior the general behavior of the secant method is very similar to the Newton method because after all it's just an approximation of the Newton method uh we have unreliability we have no error control how about how about the speed well let's make some experiments let's go back to the very first problem this cubic polinomial let me remind you X Cub minus x - 10 and for the bisection method which is a bracketing method we started with the interval 05 now I will start with the same numbers for the uh secant method although it's not bracketing these are just two numbers let's look at it and we got to the root after 20 iterations why is it so slow well let's have a look uh here are our X's the first two guesses 0 and five then we go to zero and then to 61 so again it likes to travel just like the Newton method then we then back to zero and then to 11 and so on it kept traveling and finally it settle down so the secant method is also very sensitive to starting uh to starting situation uh that's life but as I said the actual number is not really that important what we really care for is the rate of improvement so I'm going to 10 to7 and for that we need 21 iterations and that's what we care about this comparison uh so we can see that the bisection improves slowly Newton improves really fast and secant is yeah it's not bad quite fast let's talk a little bit about the sensitivity uh let's go back to the original tolerance where we had how many 20 20 iterations that fits and I'm going to change the starting points into let's say one and 3.5 now notice that both that these two points are on either side of the root so that's an interesting situation well we have a root and we start the second method like that so I wouldn't expect too much trouble we will see ah nice eight iterations which is somewhere which fall somewhere in in between Newton and bisection but as we can see this doesn't really tell us much one would say Okay eight iterations it means that it's faster than bsection and Sol than Newton but it's not comparable because of the different starting position you can see just small change in the initial two conditions initial two numbers and you get widely different Behavior so that's a slight disadvantage now just out of curiosity let's improve the Precision here and we get nine iteration so that's exactly the important observation the rate of improvement okay let's have a look at some theorems we have a function which is twice continuously differentiable we don't actually need it for the second method but we need it if we want to analyze the error so that's just a mathematical restriction now we have a sequence generated by the method which is convergent we have to assume it because as we saw it may happen that we don't have any convergence but if we have a convergent if we have a convergent sequence produced by the second method then we get a comparison for the errors which we can see here on the last line and it shows us that it's a method of order Alpha if the root is simple here we go again for simple Roots it's a method of order Alpha what's alpha alpha is a very curious number uh just out of curiosity the rate is about 1.6 so it really Falls between Newton and the bisection bisection is linear and Newton had rate two or order two now uh if you remember there was a chart here which was comparing the behavior of Errors for different formulas for different orders and there was a line where EK was raised to power 1.5 now I didn't want to use 1.6 because I couldn't do the calculations in my head but 1.5 1.6 they're pretty close so that line in the chart if you look in the video now back that line is essentially telling us how the SEC method behaves it's quite fast not as fast as Newton but it's very fast so that could be the end of the story for the SEC method but I'm not going to stop here yet I'm going to to talk about something really really interesting uh first of all Sy method is less flexible than Newton why because it's somehow inherently based on one dimensional situation you don't have a tangent line from two points in more Dimensions so it's hard to adjust it to more dimensional situations in this respect the Newton method is much more flexible but on the other hand the secant method can be faster now you may say wait a minute how can it be faster if it is a lower order the problem is the order is artificial the one that we defined in a way and second it's not practical let me explain how did we calculate the order of the bisection method we split the interval in two what if I decide that one cycle of the bisection method one iteration means that I split in half and split in half and split in half I simply take three stages of the regular bisection method and call them one stage of my new improved method then this new method will be faster but it still will be the bisection method uh of course it would be cheating but how can you tell so the order of a method as defined mathematically is actually not as transparent or not as unique as one would like that's of course mathematicians don't cheat because they really interested in knowing how methods behave uh but the the right measure of the speed is how much work you have to do for a certain Improvement which is a different story now where is the work well there is some service that you have to do you have to run a cycle you have to check on the conditions you have to do some uh perhaps some decision making in the bisection method do I choose the left or right but it turns out that this is not the big problem the real problem is function evaluation this is what takes most work so a practical point of view is slightly different it asks what is the Improvement in Precision for one evaluation of a function or a derivative of a function it's about the same problem if I have it now let's have a look at the bisection how many times do you have to substitute into a function for one step and the answer is uh well actually just one you find the middle which is a very simple algebraic operation and then you substitute NE function so for the bisection method the mathematical order is one and the Practical order is also one uh this practical order doesn't have an official name that's my name for it but it's a Viewpoint which is really very useful how about the secant method mathematic order is about 1.6 and by the way 1.6 why is such a strange number I cannot give you a nice story about this number why it's exactly this number but I look at the formula and I say wait a minute I've seen this formula before you know what it is it's the golden ratio isn't that amazing you probably heard about Golden Ratio it appears in nature in many situations it appears in in arts it's one of the most important numbers in arts it's uh found in quite many places and depending on how you look at the world you may feel that this number is very special so for people who are of the esoteric band uh the secant method is the right one because the rate of converion is the golden ratio wonderful anyway let's go here secant method that's the mathematical rate uh of convergence how about the Practical rate how many times do you have to evaluate your function to get a new approximation well you need fxk that's one evaluation you still have it and this one you remember from the last time because you already evaluated it in the previous step so just one evaluation which means that the Practical rate is also 1.6 let's have a look at the Newton method theoretical evaluation two how about the Practical one how many times do you have to evaluate for Newton XK minus fxk over fime XK you have to evaluate twice so it actually means that one step in Newton order two is in fact from the Practical point of view represented by two steps each has one evaluation of f now how does it work with the orders how does it work with the orders uh let's call these steps not e but uh let's say F so the official Newton works like this I'm going to drop the constant now whereas The Unofficial step looks like this we have FK and then there is some imaginary order let's call it Q for a second and after I do FK to Q this makes the error of this intermediate stage and then I apply another stage of the same type and I get the final error that's how the Practical point of view sees it I guess I can afford to put e here so let's put e here now these two procedures are in fact the same this is the mathematical point of view this is the Practical point of view so if we compare them we can see that EK squ should be what how much is this this is EK to Q ^ s so Q is sare < TK of two so we can say that a practical point of view for Newton yields rate of convergence 1.4 so if you are using if you are evaluating function which really takes a lot of time to evaluate I talked about this experimental work then the secant will be actually running faster than Newton although the number of Cycles will be larger for the secant method the number of work will be smaller you can also look at it this way you have an error if you use Newton you get a new error EK squ which doubles the number of digits if you are close to the root uh number of correct digits if you're close to the root if you decide to do the second method you get e to approximately 1.6 but you do it with just one evaluation of f so by the time this calculation is complete you still have time to make another step of the secant method measured by time not by Cycles this is the same so the secant method can actually make two steps and the two steps STS mean that I'm taking e k to 1.6 and again to 1.6 so it's e k to 1.6 s and 1.6 squ is about uh three roughly so the Improvement in error is much better for secant when I measure it by let's say the time spent on the calculations so that's interesting there is a big difference between a mathematical notion of order and a practical point of view from practical point of view the secant method is better it's faster it also doesn't need derivative so it has big advantages from this point of view but as I said the Newton method has other advantages and that's about it these are the three basic methods for this course uh I'm going to make another totally