Fibonacci Search @OscarVeliz

Uploaded June 2020 | Updated September 2026, 2 weeks ago

Fibonacci search scheme for finding the minimum of a function discovered by J. Kiefer and S. M. Johnson. This interval-based numerical method improves on Ternary Search and Dichotomous Search be reusing interval points based on ratios from the Fibonacci Sequence. Code can be found on GitHub github.com/osveliz/numerical-veliz

Chapters
0:00 Intro
0:12 Recap
0:23 Optimum Seeking Method
0:41 Sequential Minimax Search for a Maximum
1:06 Best Exploration for Maximum is Fibonaccian
1:23 Kiefer's Ratios
1:33 Kiefer's Ratios Example
1:50 Kiefer's Ratios Visualized
2:49 Fibonacci Search Visualized
3:58 Advantage of Fibonacci
4:16 Stopping Condition
4:47 Finding n
5:12 Johnson's Remarks on n
5:27 Ending Interval Length
5:48 Fibonacci Search Algorithm
6:56 Fibonacci Search Numerical Example
7:26 Finding n from the Example
7:49 Kiefer's Constant Ratio
8:03 Johnson's Golden-section
8:19 Oscar's Notes
8:42 Thank You

Suggested Viewing:
Ternary Search youtu.be/7h86n97naH4
Dichotomous Search youtu.be/n_zefNBfhSM
Golden-section Search youtu.be/wpGN2xus75w
Jarratt's Method - Successive Parabolic Interpolation youtu.be/3WHcQofG7B8
Minimization Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-x

References:
Optimum Seeking Methods by Douglass Wilde archive.org/details/optimumseekingme00wild
Sequential Minimax Search for a Maximum by J. Kiefer jstor.org/stable/2032161
Best Exploration for Maximum is Fibonaccian by S. M. Johnson https://apps.dtic.mil/dtic/tr/fulltext/u2/224385.pdf

#FibonacciSearch #NumericalAnalysis

$Newton Fractals Using Newtons Method to create Fractals by plotting convergence behavior on the complex plane. Functions used in this video include arctan(z), z^3-1, sin(z), z^8-15z^4+16. Example code and images available at https://github.com/osveliz/numerical-veliz Correction: The derivative of arctan(x) should be 1/(1+x^2). This error is only impacts the slides, not the numerical examples nor fractals which used the correct derivative. A video covering this mistake can be found here https://youtu.be/4jw0cjddmB8 Chapters 0:00 Intro 0:16 Convergence Interval Recap 0:42 Imaginary Numbers 1:05 Newtons Method in Complex Plane 1:29 Basin of Convergence 1:38 Arctangent Fractal 1:50 Newton Fractal 2:10 Why Fractals Emerge 2:54 Example z^3-1 4:07 Example sin(z) 4:33 Example z^8+15z^4-16 4:50 Generalized Newton Fractal 5:05 Generalized Newton Fractal Examples 6:16 Summary 6:42 Thank You Further Viewing: Newtons Method https://youtu.be/E24zUEKqgwQ Newtons Method Interval of Convergence https://youtu.be/zyXRo8Qjj0A Newton Bisection Hybrid (Newt-Safe) https://youtu.be/FD3BPTMGJds Laguerres Method and Fractal https://youtu.be/blOARV4lnIM Halleys Method and Fractal https://youtu.be/3WiVGSy_084 Generalized Newtons Method https://youtu.be/p0SBubUfwiI Further Reading: Numerical Recipes http://numerical.recipes/ Wikipedia https://en.wikipedia.org/wiki/Newton_fractal #Fractal #NewtonsMethod #NumericalAnalysis$

$Wilfs Method - Global Bisection #SoME5 Wilfs Method Global Bisection for finding roots of polynomials in the complex plane. Example code hosted on GitHub https://github.com/osveliz/numerical-veliz Clarification and Correction: The V(x) test example on x^2-x-1 is used on the Sturm Sequence of the given polynomial f_n = {x^2-x-1, 2x-1, 5/4}. Therefore, the four test points result in the series: f_n(-1) = {1, -3, 5/4}, f_n(0) = {-1, -1, 5/4}, f_n(1) = {-1, 1, 5/4}, & f_n(2) = {1, 3, 5/4} Applying the V(x) function looks at the sign changes in the sequence so - → + counts as does + → - but not - → - nor + → +. Going from non-zero to zero and vice versa also counts. Giving these results: V(-1) = {+,-,+} = 2, V(0) = {-, -, +} = 1, V(1) = {-, +, +} = 1, & V(2) = {+, +, +} = 0 Some of these values did not appear in the final rendering of the video. Chapters: 0:00-0:36 Intro 0:37-0:58 Lehmer-Schur video 0:59-2:37 Wilf Search 2:38-4:49 Sturm Sequence 4:50-5:50 Fouriers Approach 5:51-6:44 Historical Context 6:45-9:01 Adapting for Complex Plane 9:02-10:02 Oscars Thoughts 10:03-10:18 Outro Recommended Viewing: Lehmer-Schur https://youtu.be/hT0EY2rxLlQ Bernoullis Method https://youtu.be/zB_pQJWnhTc Jenkins-Traub https://youtu.be/3_yxAnhLiAk Bairstows Method https://youtu.be/iUGEk6kngFw Graeffes Method https://youtu.be/92oh5gYUP7Y Aberth-Ehrlich https://youtu.be/XIzCzfMDSzk Durand-Kerner https://youtu.be/5JcpOj2KtWc Horners Method https://youtu.be/zEvfkSuPqWk Generalized Bisection for Systems of Nonlinear Equations https://youtu.be/rMg61nfkZ3M Bisection Method https://youtu.be/MlP_W-obuNg References: Wilf, Herbert S. A global bisection algorithm for computing the zeros of polynomials in the complex plane. Journal of the ACM (JACM) 25.3 (1978): 415-420. Sturm Biography https://mathshistory.st-andrews.ac.uk/Biographies/Sturm/ Heindel, Lee E. Integer arithmetic algorithms for polynomial real zero determination. Proceedings of the second ACM symposium on Symbolic and algebraic manipulation. 1971. Pinkert, James R. An exact method for finding the roots of a complex polynomial. ACM Transactions on Mathematical Software (TOMS) 2.4 (1976): 351-363. Background music Drifting at 432 Hz by @UnicornHeads #numericalanalysis #rootfinding #bisectionmethod$