Fixed Point Iteration

Fixed Point Iteration method for finding roots of functions.
Frequently Asked Questions:
Where did 1.618 come from?
If you keep iterating the example will eventually converge on 1.61803398875... which is (1+sqrt(5))/2.
Why not use x = x^2 -1?
Generally you try to reduce the degree of the polynomial you're trying to find the root for.
How did you pick x1?
Your starting point should be an educated guess, a point in the neighborhood of your root.
How can you use the convergence test without the root?
Think of the convergence test as more of "will this function converge to this root?" When you don't know the root, try iterating a few times to see if the function is converging, bouncing around in a loop, or going to infinity. It will become apparent very quickly.
What happens if a function fails the convergence test?
Failing the test means that the function is not guaranteed to converge. It might still converge but it makes no promises. Take the function which I showed fail in the example. If you iterate starting from the root that we found, the function might converge to the same value depending on your calculator's accuracy.
Doesn't this function have two roots? Is there a way to find the second one?
Indeed this function has two roots (1+sqrt(5))/2 and (1-sqrt(5))/2 which are the numbers φ (phi) and ψ (psi). I showed how the first example converged to phi and that the other did not for simplicity. You can use the second equation to converge on psi if you start close enough, like -1 for example.
Is there any way to use x = +/- sqrt(x + 1)?
In this case you can use x = sqrt(x+1) which will converge to 1.618 as long as the value inside the square root is positive. If you try to take the square root of a negative number you will have to use imaginary and complex numbers.
Is there a way to speed up Fixed Point Iteration?
Yes, check out my video on Steffensen's Method with Aitken's Δ² • Steffensen's Method wi... and my video on Wegstein's Method • Wegstein's Method
How can I force Fixed Point Iteration to converge?
There is a very simple change you can make to induce convergence called Wegstein's Method • Wegstein's Method
Can you make a video that answers these questions?
Absolutely check out Fixed Point Iteration Q&A • Fixed Point Iteration Q&A
Chapters
0:00 Intro
0:06 Fixed Point Iteration
0:39 Fixed Point Iteration Example
2:12 Convergence Test
2:41 Convergence Test Example
3:18 Order
4:03 Thanks For Watching
Further Viewing:
Fixed Point Iteration Q&A • Fixed Point Iteration Q&A
Steffensen's Method with Aitken's Δ² • Steffensen's Method wi...
Wegstein's Method • Wegstein's Method
Fixed Point Iteration Systems of Equations • Fixed Point Iteration ...
Generalized Aitken-Steffensen Method • Generalized Aitken-Ste...
#FixedPointIteration #NumericalAnalysis

[@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!

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

[@gabriellaadinugraha237]

You, sir, deserved a gold medal

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

[@kashifaminji]

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

[@Mrhalloween55]

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

[@OscarVeliz]

Tyler Perry good job! Glad these videos helped.

[@95_Ends]

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

[@tolgakarahan2848]

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

[@ccluv6451]

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

[@BlakeDietz]

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

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

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

[@rockstarvivek27]

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

[@alexandrevachon541]

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

[@ClownDatWalk]

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

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

[@jayrajzala9870]

👑 👈🏻 You Dropped this.

[@joaovitordutra9365]

Thank you for the small, yet excellent video!

[@Darklink224]

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

[@intanlast2981]

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

[@gecaprathamesh6583]

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

[@smile4dako]

Savior for my engineering analysis final

[@supremecurt8047]

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

[@SuperExpert]

Really well explained. Thanks for the upload.

[@QuinnMorgendorffer]

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

[@mehdimovahedaagre8253]

highly appreciated your video and clear explanation.

[@aviraj017]

Thanks ! for simple and clear explanation.

[@hiawatadhya]

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

[@Melsi1979]

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

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

[@mobins127]

Thank you very much for the great explanation.

[@TheSiriusSigma]

Awesome video, you're the bomb my dude! Thanks. c:

[@ericelegado1677]

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

[@madawacko258]

Great Video, thanks mate.

[@user-oh5vo5rj6y]

this was informative and short, thanks I finally got it

[@toshnono7237]

Good Job Oscar. This video was amazing Sir

[@frajolapuc5006]

Dear Oscar, thank you for your help.

[@OscarVeliz]

Frajola Puc you're welcome.

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

[@pablo_parra_]

Awesome, so easy to understand!

[@DrSlough]

Great explanation, thank you

[@esaskhan95]

Great tutorial!

[@daco54]

Thanks this is very helpful and very clear to understand.

[@user__unknown]

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

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

[@AquaBerk96]

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

[@RawbLV]

Thank you so much!

[@jutamari]

Awesome video. Helped me a lot

[@naru909]

Amazing explanation!!

[@PSP5559]

THANK YOU MR. OSCAR VELIZ

[@limmy_b]

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

[@somebody539]

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

[@trippymintz]

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

[@user-tq7pf8cv3g]

Helpful ! thank you :)

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

[@ruotingliang973]

thanks. It is very helpful!

[@editmar89]

easy to follow, thanks!

[@yblizzo]

Please make more videos on numerical analysis :)

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

[@AjjawiPhoto]

Thank you, it is really a beneficial video.

[@chamithdilshan3547]

Thank you so much 🥰

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

[@sxndrxcore]

Thanks man!!!

[@ratjockey]

Thanks, it helped a lot

[@Sammy-jk3hw]

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

[@HellOnGames]

Thanks! You saved my day, again.

[@OscarVeliz]

Be sure to check out the follow-up video 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

[@Alice-rm7lj]

Finally know what's going on, thank you!

[@conorclery5670]

Youre a good man lad

[@trockpitt]

Thank you!

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

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

[@asddsaafdg2287]

thank you!

[@heroturk51]

great i love it bro!

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

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

[@abdulmukit4420]

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

[@Bedocalaway]

Thank you :)

[@fernandoblanco1471]

Thank you Good video

[@taquiansari4833]

extremely helpful .. tysm

[@KyneticAcademy]

THANK YOU SO MUCHHHHHHHHHHHH!!!!!!!!!!!!!!!!!!

[@islamelbaz7232]

Thank You ...

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

[@haymanotgidena6083]

NO word THANKS so much

[@onlyonetwin]

THANK YOU

[@utkuozturk1363]

appreciated it !

[@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!

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

[@xjsmstr]

Thanks!

[@yukslunger]

Thanks mate

[@ballapranavachaitanya3975]

thanks bro very helpful

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

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

[@Ben.Standup]

thanks you

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

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

[@sadeghkhosravi]

Thank you💕❣