Fixed Point Iteration

[@OscarVeliz]

If you want to learn more about Fixed Point Iteration, or feel like you still have questions, then watch my follow-up video Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@krishnendumondal317]

Can you please answer , xn=1÷(1+xn-1) is it convergent or not

[@OscarVeliz]

See the follow-up video linked above.

[@Swarmish]

Quick and too the point. This is exactly how I want to be taught when I'm first studying math material. Thank you so much!

[@eevibessite]

kzbin.info/www/bejne/h4nckKalfKuca7s

[@hans3331000]

Why isn't there more tutorials like this?? i love you man! these other people trying to show off and typing out useless crap, i love this and hope you keep making videos. thank you for taking my headache away!

[@ZeroKelvin440]

Final in 8 hrs. This saved at least half of one of those. Thanks!

[@ahmetkarakartal9563]

did you pass :D

[@eevibessite]

kzbin.info/www/bejne/h4nckKalfKuca7s

[@ninjahunterx7497]

@@ahmetkarakartal9563 Dude probably has a job now.

[@ahmetkarakartal9563]

@@ninjahunterx7497 ahaha exactly

[@ninjahunterx7497]

@@ahmetkarakartal9563 Lol

[@edon1257]

This world needs people like you man :)

[@haticeonal9383]

no doubt !

[@sandeeps7043]

*True.*

[@elisemarie5140]

To think a four minute video makes more sense than two hours of lecture from my prof. Thanks.

[@AJ-et3vf]

Nice video. I particularly like the mention about how Newton's method is a special case of fixed-point iteration. Brings things into perspective and gives me more appreciation for fixed-point iteration method.

[@BlakeDietz]

Nice explanation. This is very digestible. It's a nice overview that helps to solidify all of the concepts for fixed point iteration.

[@gabriellaadinugraha237]

You, sir, deserved a gold medal

[@MaryMartinezdev]

Wow that was SO much clearer than my class lecture and all of my notes AND everything else I have seen online. THANK YOU!!

[@dungtrantri6213]

Những ngày đầuo I

[@Mrhalloween55]

Passed my midterm because of these vids, thanks a ton!

[@OscarVeliz]

Tyler Perry good job! Glad these videos helped.

[@Philleatsfood]

I have a question. At 2:50 in the video you plug in a root to check if the iteration will converge. Is this root an arbitrary guess or is it the actual root of the function? If the latter, how are we supposed to know this root from the start? As I've understood it, the whole point of the iteration is to find this value.

[@OscarVeliz]

Please take a look at the frequently asked questions in the description box below the video. Let me know if that clears things up.

[@sabaducia]

Thank you! Understood all the "fancy maths" in my computational lecture, but then didn't pay attention to the last step... =3 This made it sooooo much easier to understand the actual iteration part

[@ClownDatWalk]

a 4 minute video explained this concept better than my prof who took over 2 hours. Thank you :)

[@tolgakarahan2848]

Very good and fast explanations. I get a grasp immediately. Thanks dude.

[@kashifaminji]

such a complicated algorithm explained completely and very well in just 4 minutes.

[@angelailieva9711]

when you did the convergence test on 2:40, how did you find the value you plugged in g'(x)? 🥺please

[@OscarVeliz]

I have a follow up video answering this and other commonly asked questions kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@rockstarvivek27]

made it crystal clear in just 4 min....,nice work man

[@ChrisLuigiTails]

At 3:13, if you choose the other root, the equation on the left diverges and the one on the right converges. How do you decide which root you should use?

[@OscarVeliz]

I have a second video (Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE ) that answers this and many other frequently asked questions.

[@95_Ends]

Love it. Just started with the Numerics, and was blessed to find your channel Thanks

[@isxp]

This 10-year-old video is amazing. Cheers from a senior ME student taking Numerical Methods.

[@OscarVeliz]

Check out the follow-up video kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@alexandrevachon541]

If we make fractals from fixed point iteration, you might see that the diverging functions can occasionally generate Julia sets.

[@ramili0711]

Thanks for great collection of videos. How do you check for convergence when you don't what the root is?

[@OscarVeliz]

+ramili0711 Please see the Frequently Asked Questions in the video description.

[@OscarVeliz]

Fixed Point Iteration can only find one root at a time and it depends on g(x) and the starting point. With g(x)=1+1/x and starting around 1 (for example) it converges to (1+root(5))/2 also known as the number phi. However, if you take the example that did not converge, g(x)=1/(x-1), but started at -1 (for example) the function converges to (1-root(5))/2 which is known as the number psi. As long as you start in the neighborhood of a root and g(x) behaves well, it converges to the closest root.

[@QuinnMorgendorffer]

Thank you. This is a fantastic video and the best on the web for this method.

[@AliHasanAli]

Thank you @Oscar for the great videos you make! I have a question, In 2:04, you mentioned that the g(x) on the right side does not converge if you start with the initial guess x1=1.6. I tried that with Matlab and my code ended up with converging to the other root (-0.6180) after 44 iterations (with accuracy = 10^-15). Did you try it? I don't know if I've done something wrong, but it's really confusing?

[@OscarVeliz]

You haven't done anything wrong. I touch on this behavior in my follow-up video Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@AliHasanAli]

@@OscarVeliz Thanks for replying 🌷 I already checked this follow-up video, and I saw how you say that it converges to the other root when we start with -1, but what made me confused is that you mentioned the divergence when we start with 1.6..

[@OscarVeliz]

Yes that is similar to the example showing how the first version converged to 1.618 even when you started very close to the other root (around -0.618)

[@OscarVeliz]

That it looks like it is diverging but if you keep iterating it eventually converges.

[@ggg17ggg17]

How did you go from x^2=x+1 to x=x+1/x ? At 0:50 seconds . Pleas help I watched q and a video and it wasnt explained

[@OscarVeliz]

This is dividing both sides by x. x² = x+1 x²/x = (x+1)/x x = x/x + 1/x x = 1 + 1/x

[@ggg17ggg17]

@@OscarVelizI’m so retarded thank you

[@Darklink224]

Thank you so much! I wish my professor would lay it out like this after doing all the proofs and derivations.

[@viscourtroy]

I remember the lecturer have shown us at the classroom how to use EXCEL to find the convergence by modified the first term in the formulae! I should try it!

[@mnm3781]

@Oscar, we donot know the root in the beginning so how can we check if g'(x) will converge or not?

[@OscarVeliz]

+Mohsin Noman Please take a look at the video description box. It has the answer to this and many other frequently asked questions.

[@supremecurt8047]

Thank you! I understood it so easily, the terms on the textbooks were so confusing lol

[@ericelegado1677]

I will nominate you for this year's CNN Hero of the Year.

[@gecaprathamesh6583]

Thank you! Was able to understand the method in one go! :)

[@OscarVeliz]

@Anandtrceg It is sort of a catch-22 isnt it. Saying less than 1 guarantees that the function converges. However if greater/equal 1 it does not say that the function will diverge; it might still converge but that it is not guaranteed to converge. This just happens to be one of the properties of fixed point iteration. The other way to figure out if it is converging or diverging is to run it and check if x is converging to a number or bouncing around everywhere in a loop or sipping to infinity.

[@alexbedoian]

Super helpful in understanding how this method works. Gonna look more into it now. Amazing video. Thanks!

[@OscarVeliz]

Definitely check out my followup video kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@animereyiz5082]

Thanks for video, i like so much the part which you talk about converge test, i was wondering why we examine derirative of G but i understood. Thanks again

[@ccluv6451]

Why can't my prof be just like you!! He freaking spent an hour to explain this to us but nobody understood.

[@jorgeboro6105]

Thanks for teaching the procedure so nicely. I will get A+ in tomorrow's exam

[@OscarVeliz]

I'd also recommend watching my follow-up video Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@piupolino2618]

I find it ironic that you need the root to find out whether it'll converge at the root. Great video, very helpful!

[@OscarVeliz]

I discuss this irony in my followup video kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@smile4dako]

Savior for my engineering analysis final

[@user-ve3wy1oz7n]

how do you know which root to us to satisfy that g'(root)

[@user-ve3wy1oz7n]

use*

[@OscarVeliz]

+Efrain Castanon Please refer to the Frequently Asked Questions in the video description. Hope that helps.

[@kikokimo2]

Thank you first of all for this great video! But sorry, I still don't really get it, also after reading the answer to this question in the FAQ, how you come to this root of (1+sqrt(5))/2: 1) If you iterate multiple times and come to a number to which it converges (in this case 1.618), you know already that it converges! So why doing the test? 2) how to know directly the fraction form of a decimal number like you did from 1.618 --> (1+sqrt(5))/2 ? Thanks in advance!

[@OscarVeliz]

Karim and I exchanged more comments on a different video so I only now just saw your comment Gajendra. The short answer is that "Will this function converge?" and "Will this function converge to this root?" are two different questions. Similar to "Are you married?" vs "Are you married to Ada?" and the convergence test only answers the latter. There is a way to force Fixed Point Iteration to converge which I will make a video on in the future but as an open method like Newton's and Secant it has no ultimate convergence guarantee.

[@OscarVeliz]

That works since this a quadratic but what if our polynomial was 5th degree or some crazy function? The question that many people have asked is how to use the convergence test without the root or also if you've already found the root why do you need to know if it converges because clearly it did. I am working on a video to show how to force fixed point iteration to converge.

[@user__unknown]

Thanks for such a wonderful video, it made the topic easily understandable.

[@hiawatadhya]

Thank you for all your numerical method video. You just make my night feels like one semester.

[@pratikmitra35]

Can anyone help me here....why does x1 = 2 picked....why not any other no. ? At 1:30

[@OscarVeliz]

I have a second video (Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE ) that answers this and many other frequently asked questions.

[@SuperExpert]

Really well explained. Thanks for the upload.

[@jayrajzala9870]

👑 👈🏻 You Dropped this.

[@intanlast2981]

Great explanation! cannot wait to watch another video, since there's many mathematical theory which really difficult to understand

[@frajolapuc5006]

Dear Oscar, thank you for your help.

[@OscarVeliz]

Frajola Puc you're welcome.

[@Sammy-jk3hw]

u really helped, my professor sucked at explaining it, i like it straightforward

[@mehdimovahedaagre8253]

highly appreciated your video and clear explanation.

[@toshnono7237]

Good Job Oscar. This video was amazing Sir

[@Shreyansh147]

At 2:50 seconds, plug in the root of what value ?

[@marflage]

It was actually very clear. Thank you so much. I knew it Newton's method was the base for every other method to find iterations; read it somewhere, perhaps the book. Lol

[@dremr2038]

2:14 when does convergence occur?

[@limmy_b]

you're the fucking boss. so simple. so concise. so good.

[@PSP5559]

THANK YOU MR. OSCAR VELIZ

[@aviraj017]

Thanks ! for simple and clear explanation.

[@mrrobot9112]

Sorry master I didnt understand a point because of my poor english. at 1:31 why you said x(sub1)=2 and at 1: 51 x(sub1)=1.6? These are random values?

[@OscarVeliz]

The starting point should be an educated guess, a point close to your root. You can turn on captions and have the video player auto-translate to a language you are more comfortable with.

[@daco54]

Thanks this is very helpful and very clear to understand.

[@yblizzo]

Please make more videos on numerical analysis :)

[@joaovitordutra9365]

Thank you for the small, yet excellent video!

[@АлександрЖарков-у9ш]

this was informative and short, thanks I finally got it

[@AlexButterfield]

So in order to find the rate of convergence for some given f(x) we must evaluate the derivative at the root. Sense we probably only care about the rate of convergence in order to choose if this is an appropriate method for our function, seems to defeat the purpose if we need to run the algorithm it out it to determine if it is worth running. Can we evaluate using our interval?

[@OscarVeliz]

Please take a look at the FAQ in the description box below the video particularly the answers to "How can you use the convergence test without the root?" and "What happens if a function fails the convergence test?" If you are given an interval of convergence then there is no need to test for convergence as anything within the interval will converge.

[@meghna1915]

How to we find the theoretical error bound for each iteration? What is the formula?

[@OscarVeliz]

+Meghna Tanwal Consider Bisection Method where you halve the search space between an interval each iteration. The constant halving gives a linear convergence. The order of convergence for Fixed Point Iteration depends on your starting function and at the end of the video I showed how you can gauge it using derivatives of g. To find the exact order of convergence you'll need three consecutive errors like I showed in my video on Secant Method kzbin.info/www/bejne/lX7Jm4uFgbqhr9km41s

[@meghna1915]

+Oscar Veliz yeah I got it. thank you

[@naru909]

Amazing explanation!!

[@sitapea32167]

where does the root value come from?

[@OscarVeliz]

The answer to this and many other frequently asked questions can be found in the description box below the video.

[@thataintme]

2:52 wats going on there? Where did the (1+sqrt(5))/2 come from?

[@OscarVeliz]

Please refer to my follow-up video Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@thataintme]

@@OscarVeliz okay thanks for the reply. I really thought I wouldnt get one T_T

[@OscarVeliz]

This version of the iteration causes divergence at either root. g(x) = x^2 - 1. g' = 2(x). r = (1[+/-]sqrt(5))/2. g'(r) =~ | 2*-0.618 | >= 1 or | 2*1.618 | >= 1. You can try it yourself and see. If you pick x_1 = 1 then x_2 = 0, x_3 = -1, x_4 = 0, x_5 = -1 ... You generally try to reduce the degree of the polynomial whose roots you're solving for.

[@obigwejesse2004]

How did you get the 1+root5/2 from

[@esaskhan95]

Great tutorial!

[@kasun611]

Arn't we trying to find the root at the first place? So how do we find g'(root) for the convergence test without knowing the root?

[@Sthriven]

also, how did you find the root to plug into your convergence test when you're test is to determine whether or not that function is capable of finding the root?

[@OscarVeliz]

Please see the other comments and my responses which will answer your questions. It will make it easier to read if you select the "Newest first" option and scroll down rather than "Top comments" which has them out of order.

[@oumaimaabouzaid4948]

Thanks for the video! but i have a question ... you used the root for testing the convergence ! ... but sometimes it's not that easy to find the root ...so what are we gonna do in this case?? ...another question ...if we already know the root ...so what is the point of this method?? thank you for answering :)

[@OscarVeliz]

Please take a look at the frequently asked questions in the description box below the video. Hope this helps.

[@Philleatsfood]

I have raised this question recently as well. Upon more study I've learnt that this is a limitation of fixed point iteration. It may be prudent to plot y=x and y=g(x) in the same figure so you can see more or less where the roots are. (Where the lines intersect) Looking at the slope of g(x) at the root may give you an indication weather FPI will converge to the root or not. If not, you might need to use a different numerical method like Newton-Raphson or Secant method as a compliment.

[@oumaimaabouzaid4948]

Philleatsfood thank you !

[@mobins127]

Thank you very much for the great explanation.

[@ChaliandChloeForever]

How do you get x equal to that at 0:58? Shouldn't you be taking the square route? I understand you're dividing it but that doesn't make sense to me...

[@OscarVeliz]

I discuss taking the square root at 1:11. I think the confusion may come from the skipped step in the isolation of x process x^2/x = (x+1)/x becomes x = x/x + 1/x which becomes x = 1 + 1/x then label accordingly. If you prefer you technically can use the square root with a few caveats and as long as you don't mind doing using imaginary numbers as I explain in the follow-up video kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@aneeshsrinivas9088]

Is the uniqueness theorem for fixed points also true if the condition that |g’(x)|

[@OscarVeliz]

I go over the convergence test in more detail in my video on Fixed Point Iteration for Nonlinear Systems kzbin.info/www/bejne/rpKVp4ipjq93Y8U and maybe that will help to clear things up. Sorry for taking so long to respond.

[@somebody539]

its Really Good, Thank you , its well explained than my Teacher!!

[@HellOnGames]

Thanks! You saved my day, again.

[@OscarVeliz]

Be sure to check out the follow-up video kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@pauselab5569]

one of the best iteration theorem is banach's fixed point theorem which is great for all the continued fraction and continued root because they all satisfy the conditions for the theorem

[@AquaBerk96]

really helpful i finally get it how it works, thank you sir..

[@Melsi1979]

I too want to thank you, your help is so valuable!

[@nkurunzizaladislas2599]

sir! ,where did u got from that " one plus square roots 5 over 2 in bracket power 2" that you replaced in g prime

[@OscarVeliz]

Please check out my follow-up video Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@nkurunzizaladislas2599]

@@OscarVeliz thx sir

[@jy02679284]

isnt suppose to have two answers for x? is there a way to find the 2nd answer by using the same method?

[@lucianoinso]

Thanks for the video, really clear! On a side note: I implemented it on python for a course and tried with the x = 1.6 starting point and it converged, I was like hmm that's odd, checked the points and seems like with exact arithmetic when the iteration reaches 1 it fails because of division by zero (1/(1-1) = 1/0 = Zero division Error), but because of error carried by floating point arithmetics it calculated (1/(1-1.0000000000000018)) = 562949953421312 and continued to calculate the next point till it converged to the left root lmao!

[@OscarVeliz]

Good job on finding that behavior! I covered something similar in a follow-up video to this one kzbin.info/www/bejne/fKqmp5ytZ790aNE that I think you will also find helpful.

[@lucianoinso]

@@OscarVeliz thank you! I'll check it!

[@leesweets4110]

Is it possible to use simple transforms (horizontal shifting, compression/expansions, etc), to force the condition |g'(x)|

[@OscarVeliz]

I'd recommend looking into Steffensen's Method with Aitken's Δ² kzbin.info/www/bejne/eIW8hZ1mp5qDkKc as well as Wegstein's Method kzbin.info/www/bejne/ipCZnoVsp6-Lh7M that latter of which induces convergence

[@leesweets4110]

@@OscarVeliz At the time of my writing that comment I had already watched those videos. Thanks though. No, Im talking about something fundamentally different. Or at least I think I am. I wouldnt argue that those methods constitute simple linear transformations. Wegstein comes close but it is a bit different.

[@OscarVeliz]

I think I see more about what you're asking. Applying a transformation might also do the opposite and cause it to diverge. Knowing which transformation to apply would take some functional analysis before hand which is just sort of built-in to something like Wegstein.

[@YouTubeChannel2000]

Hi, How it can converge quadrically when |g'(x)|=0??

[@OscarVeliz]

Wajdi Al-Rekaby not g'(x) = 0 but g'(root) = 0 which means it is *at least* 2nd order. You'll also have to check higher order derivatives of g'', g''', ... until you get a non-zero derivative at the root. The more levels you check the higher the order. To find the exact order you'll need three consecutive errors like I discussed in my Secant Method video kzbin.info/www/bejne/lX7Jm4uFgbqhr9k

[@OscarVeliz]

The |g'|>=1 test only applies at x=r so you can't test it a x=1.6. Even then, this test is not a guarantee (see my reply to Anandtrceg). For example with g(x) = x^2 - 1 if you picked x1 = (1+sqrt(5))/2 then mathematically x2 will be (1+sqrt(5))/2 however, in the computer or calculator there is not enough precision to represent the sqrt(5) and the resulting iteration may or may not work. Picking x1 = 1.6 as you suggested causes x2 = 1.56, x3 = 1.4336 x4 = 1.0552...

[@ordinaryperson3554]

what i dont understand is that wasnt our purpose to find the root, if so , how can i know if the g of x converges or not (without knowing the root)

[@OscarVeliz]

Please see the Frequently Asked Questions (FAQ) in the description box below the video.

[@DrSlough]

Great explanation, thank you

[@marksolvent3259]

Idk how tf you summarized these long pages from my book, which, due to my attention span, I already had trouble reading, and I was also mad about how the book doesn't define a lot of what it is making use of.

[@vd853]

3:08 how would we know the root if that is what we're looking for?

[@madawacko258]

Great Video, thanks mate.

[@theoriginalcows1357]

This is seriously high level for a 2011 video lmao

[@OscarVeliz]

Check out the follow-up video, it is much more recent kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@mechwise6811]

Superb 👍

[@zoedepecol]

What if we don't know our root answer? so how do we know what to plug into g"(x) if the problem we have is super complicated and we can't exactly solve for x

[@OscarVeliz]

I have a second video (Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE ) that answers this and many other frequently asked questions.

[@zoedepecol]

@@OscarVeliz thank you so much!

[@abdulmukit4420]

I wish you were the math teacher at my university. :(

[@nikoskoutsilieris6087]

what if i do not know the root? then do i have to prove that the derivative of g(x) is less than one for every x allowed by the first function f(x)?

[@OscarVeliz]

See the follow up video Fixed Point Iteration Q&A kzbin.info/www/bejne/fKqmp5ytZ790aNE

[@AjjawiPhoto]

Thank you, it is really a beneficial video.

[@trippymintz]

well done sir this is more than enough even our instructor couldn't do that :P thanks a lot :)

[@Alice-rm7lj]

Finally know what's going on, thank you!