Bairstows Method Oscar Veliz 2022-08-06 | Bairstow's Method for finding the roots of polynomials including complex roots. Discussion of method derivation, relation to synthetic division of two variables, stopping condition, selection of initial values, fractals, and historical context. Submission for Summer of Math Exposition 2 contest by @3blue1brown. Example code hosted on GitHub github.com/osveliz/numerical-velizChapters:00:00 Intro00:36 Factoring with monomial01:13 Factoring with quadratic01:40 Synthetic Division 1 variable02:16 Synthetic Division 2 variables03:22 Solving for roots03:50 Different u and v04:24 Describing Notation05:22 Solving Nonlinear System07:01 Another Synthetic Division07:45 Updating u & v08:27 Bairstow Iteration Example08:56 Bairstow Iteration Example 209:22 Note on Quadratic Equation09:42 Bairstow Full Algorithm10:51 Complex Roots Example11:33 Bairstow Fractals12:23 Picking u & v12:46 Henrici Starting Values13:08 Bairstow's Original Problem14:40 Oscar's Notes15:24 OutroRecommended Viewing:Horner's Method youtu.be/zEvfkSuPqWkGraeffe's Method youtu.be/92oh5gYUP7YGeneralized Newton's Method youtu.be/p0SBubUfwiIReference links:"Applied Aerodynamics" by Bairstow books.google.com/books?id=GIUQAQAAMAAJ"Elements of Numerical Analysis" by Henrici archive.org/details/elements-of-numerical-analysis-by-peter-henrici"A Modified Bairstow Method for Multiple Zeros of a Polynomial" by F. M. Carrano doi.org/10.1090/S0025-5718-1973-0334492-5Background music "Drifting at 432 Hz" by @UnicornHeads#SoME2 #NumericalAnalysis #BairstowsMethod
Graeffes Method Oscar Veliz 2022-06-06 | Graeffe's Root-Squaring Method (also called Graeffe-Dandelin-Lobachevskiĭ or Dandelin–Lobachesky–Graeffe method) for finding roots of polynomials. The method solves for all of the roots of a polynomial by only using the coefficients and does not require derivatives nor an interation function. This lesson provides a history of the method, motivates "why" the method works, and walks through an example of root-squaring as well as solving for the roots using logarithms. Example code hosted on GitHub github.com/osveliz/numerical-velizChapters:00:00 Intro00:45 History01:10 Expanding & Reversing02:21 Bracket Notation03:53 Bracket Example04:16 Solving for a05:46 Solving for b06:11 Solving for c06:30 How does this help???06:55 Root Squaring Example07:56 Repeated Root Squaring08:36 Stopping Criteria08:58 On Programming Graeffe's Method09:30 Further Reading09:52 Oscar's Notes10:33 OutroRecommended Viewing:Horner's Method youtu.be/zEvfkSuPqWkBairstow's Method youtu.be/iUGEk6kngFwDurand-Kerner youtu.be/5JcpOj2KtWcAberth-Ehrlich youtu.be/XIzCzfMDSzkReference links:Graeffe's Version https://publikationsserver.tu-braunschweig.de/receive/dbbs_mods_00051359Dandelin's Version eudml.org/doc/180464Lobachevskiĭ's Version catalog.lindahall.org/permalink/01LINDAHALL_INST/19lda7s/alma999251234705961Householder's Article doi.org/10.2307/2310626Brodetsky and Smeal 1924 doi.org/10.1017/S0305004100002802Whittaker and Robinson books.google.com/books?id=0mUGAQAAIAAJ&ots=lFy0VTVeAd&dq=Whittaker%2C%20Edmund%20Taylor%2C%20and%20George%20Robinson.%C2%A0The%20calculus%20of%20observations%3A%20a%20treatise%20on%20numerical%20mathematics.%20Blackie%2C%201924.&lr&pg=PR3#v=onepage&q&f=falseBest's Paper doi.org/10.2307/2306166Background music "Drifting at 432 Hz" by @UnicornHeads #NumericalAnalysis #rootfinding #polynomials
Generalized Bisection Method for Systems of Nonlinear Equations Oscar Veliz 2022-04-18 | Generalization of the Bisection Method for solving systems of equations. This lesson explains the algorithm for a 2 dimension example based on Harvey-Stenger's approach using bisecting triangles. It includes a visualization of the method in action on an example nonlinear system. Other methods for solving in 3 dimensions and for larger systems are also discussed as well as hybrid approaches. Example code hosted on GitHub github.com/osveliz/numerical-veliz written in Python and using numpy and matplotlib.Chapters:0:00 Intro0:10 Literature0:47 Bisection Shapes1:12 Harvey-Stenger1:29 2D Bisection Setup2:44 Triangle Point L-Test3:00 Triangle Point Area-Test4:24 Picking a Triangle4:52 Stopping Criteria5:07 2D Bisection Visualized5:56 Generalized Bisection Algorithm7:02 Picking Starting Points7:38 Harvey-Stenger Algorithm8:20 Hybrid?8:50 Oscar's Notes9:30 OutroRecommended Viewing:Bisection Method youtu.be/MlP_W-obuNgGeneralized Secant Method youtu.be/p2OPlnHJPNIGeneralized False Position Method and Alternative Secant Methods youtu.be/c2kSfJ8of7EGeneralized Newton's Method youtu.be/p0SBubUfwiIBrent's Method youtu.be/-bLSRiokgFkNewton-Bisection Hybrid youtu.be/FD3BPTMGJdsReference links:"A two-dimensional analogue to the method of bisections for solving nonlinear equations" by Charles Harvey and Frank Stenger doi.org/10.1090/S0025-5718-1979-0521286-6"A three-dimensional analogue to the method of bisections for solving nonlinear equations" by Krzysztof Sikorski doi.org/10.1090/S0025-5718-1979-0521286-6"A bisection method for systems of nonlinear equations" by Eiger et. al. doi.org/10.1145/2701.2705"An efficient degree-computation method for a generalized method of bisection" by Baker Kearfott doi.org/10.1007/BF01404868"Abstract generalized bisection and a cost bound" by Baker Kearfott doi.org/10.1090/S0025-5718-1987-0890261-9"Solving systems of nonlinear equations using the nonzero value of the topological degree" by Michael N. Vrahatis doi.org/10.1145/50063.214384Background music "Drifting at 432 Hz" by @UnicornHeads #NumericalAnalysis #BisectionMethod #NonlinearSystem
Generalized False Position & Alternative Secant Methods Oscar Veliz 2022-01-31 | False Position Method for Nonlinear Systems (aka Generalized Regula Falsi) along with two Alternative Secant Methods. Includes discussion of history and primary sources along with numeric examples and visualizations. Example code hosted on GitHub github.com/osveliz/numerical-velizChapters:0:00 Scaffolding0:25 Korganoff1:02 Robinson1:32 Some History1:50 Robinson Continued2:51 Robinson versus Secant3:27 Nonlinear System Example4:16 On Notation4:37 Efficient Orthogonal Matrix4:53 Generalized False Position Method5:18 Oscar's Notes8:38 OutroRecommended Viewing:Secant Method youtu.be/_MfjXOLUnywGeneralized Secant Method youtu.be/p2OPlnHJPNIBroyden's Method youtu.be/UlLGzW-KjHsGeneralized Steffensen's Method youtu.be/ndf2vjXjXzQGeneralized Finite Difference Method youtu.be/G25sGOWkOuQFalse Position Method youtu.be/pg1I8AG59IkReference links:"Some Efficient Algorithms for Solving Systems of Nonlinear Equations" by Richard P. Brent doi.org/10.1137/0710031"Iterative Solution of Nonlinear Equations in Several Variables" by Ortega and Rheinboldt books.google.com/books/about/Iterative_Solution_of_Nonlinear_Equation.html?id=UEFRfUZBpUEC"Méthodes de calcul numérique: Algèbre non linéaire, Vol 1" by André Korganoff, worldcat.org/title/methodes-de-calcul-numerique/oclc/848108709"Interpolative Solution of Systems of Nonlinear Equations" by Stephen M. Robinson epubs.siam.org/doi/abs/10.1137/0703057Background music "Drifting at 432 Hz" by @UnicornHeads #NumericalAnalysis #FalsePosition #SecantMethod
Global Newtons Method - It Always Converges Oscar Veliz 2021-11-26 | Globally convergent modification of Newton's Method that uses backtracking whenever a test point would not cause the function iterations to shrink in absolute value based on the Armijo's Search. Lesson also covers fractals using Global Newton Method as well as solving systems of nonlinear equations. Example code hosted on GitHub github.com/osveliz/numerical-velizChapters:0:00 Intro0:30 Literature1:03 Damped Newton Method2:28 Armijo's Approach2:57 Global Newton Method Algorithm3:50 Numeric Example4:17 Global Newton Fractals - Single Variable5:30 On Extra Function Calls6:11 Nonlinear System Example6:55 Global Newton Fractals - Nonlinear System8:11 Oscar's Notes8:38 OutroRecommended Viewing:Newton's Method youtu.be/E24zUEKqgwQNewton's Method of Convergence youtu.be/zyXRo8Qjj0ANewton Bisection Hybrid youtu.be/FD3BPTMGJdsNewton Fractals youtu.be/MWD2A0Vg2V0Newton's Method for Systems of Nonlinear Equations youtu.be/p0SBubUfwiIReference links:"Fractal Basins of Attraction Associated with a Damped Newton's Method" by Bogdan et al jstor.org/stable/2653002"Numerical methods for unconstrained optimization and nonlinear equations" by Dennis Jr and Schnabel books.google.com/books?hl=en&lr=&id=ksvJTtJCx9cC&oi=fnd&pg=PR1&ots=BKlQGS9IGt&sig=BPKkOIGmU2it_rNqEDYY2Vtvh6k#v=onepage&q&f=false"Applied numerical linear algebra" by Hager openlibrary.org/books/OL2378827M/Applied_numerical_linear_algebra"Minimization of functions having Lipschitz continuous first partial derivatives" by Armijo msp.org/pjm/1966/16-1/p01.xhtml"Iterative methods for the solution of equations" by J. F. Traub openlibrary.org/works/OL1923690W/Iterative_methods_for_the_solution_of_equations?edition=ia%3Aiterativemethods0000trauBackground music "Drifting at 432 Hz" by @UnicornHeads #NumericalAnalysis #NewtonMethod #NewtonFractal
Halleys Method for Systems of Nonlinear Equations Oscar Veliz 2021-08-22 | Halley's Method for Solving Systems of Nonlinear Equations. Submission for The Summer of Math Exposition. Lesson includes motivation & explanation of notation, description of the method, numerical example, discussion of order, and comparison with the Method of Tangent Hyperbolas. Example code hosted on GitHub github.com/osveliz/numerical-velizChapters:0:00 Wikipedia0:44 Intro0:54 Recommended Viewing1:04 Recap1:42 Generalized Halley's Method2:55 Nonlinear System Example3:21 Order3:45 Method of Tangent Hyperbolas4:10 Side-by-side4:36 Higher Order4:54 Oscar's Notes5:15 OutroRecommended Viewing:Newton's Method youtu.be/E24zUEKqgwQHalley's Method youtu.be/3WiVGSy_084Generalized Newton's Method youtu.be/p0SBubUfwiIBroyden's Method youtu.be/UlLGzW-KjHsReference links:Newton's Method Wikipedia - en.wikipedia.org/wiki/Newton%27s_methodHalley's Method Wikipedia - en.wikipedia.org/wiki/Halley%27s_method"Abstract Padé-approximants for the solution of a sytem of nonlinear equations" by Cuyt and van der Cruyssen doi.org/10.1016/0898-1221(83)90119-0"Konstruktion und Durchführung von Iterationsverfabren höherer Ordnung" by Ehrmann doi.org/10.1007/BF00281379"The Solution of Equations by Continued Fractions" by Frame doi.org/10.1080/00029890.1953.11988293"Iterative Solution of Nonlinear Equations in Several Variables" by Ortega and Rheinboldt books.google.com/books/about/Iterative_Solution_of_Nonlinear_Equation.html?id=UEFRfUZBpUECBackground music "The Golden Present" by @JesseGallagher #NumericalAnalysis #some1 #HalleysMethod
Broydens Method Oscar Veliz 2021-06-28 | Broyden's Method for solving systems of nonlinear equations. Lesson covers motivation, history, examples, discussion, and order of this Quasi-Newton Method. It also explains the "Good" and "Bad", as well as the third version of the method. Example code hosted on GitHub github.com/osveliz/numerical-velizChapters:0:00 Intro0:22 Newton's Method According to Broyden1:08 Nonlinear System Example1:18 Newton's Method Example1:28 Analyzing Newton's Behavior2:07 Solving for J2:51 Broyden's Approach3:25 Almost Broyden's Method4:13 Solving for the Inverse4:46 Broyden's "Good" Method5:11 More Options5:35 Broyden's "Bad" Method6:07 Generalizing Root-Finding6:32 The Case for Secant Method6:52 The Case for Newton's Method7:17 Broyden's Take8:11 The question of Order8:31 Oscar's Notes9:03 OutroRecommended Viewing:Newton's Method for Systems of Nonlinear Equations youtu.be/p0SBubUfwiISecant Method for Systems of Nonlinear Equations youtu.be/p2OPlnHJPNIFixed Point Iteration for Systems of Nonlinear Equations youtu.be/G25sGOWkOuQGlobal Newton Method youtu.be/BGZfHxzZ-7cReference links:"A class of methods for solving nonlinear simultaneous equations" by Charles G. Broyden doi.org/10.2307/2003941"A faster Broyden method" by Kvaalen doi.org/10.1007/BF01931297"On Some Methods Based on Broyden's Secant Approximation to the Hessian" by Dennis hdl.handle.net/1813/5946"On the discovery of the 'good Broyden' method" by C. G. Broyden doi.org/10.1007/s101070050111"The convergence of an algorithm for solving sparse nonlinear systems" by C. G. Broyden ams.org/mcom/1971-25-114/S0025-5718-1971-0297122-5/S0025-5718-1971-0297122-5.pdf"On the Local and Superlinear Convergence of Quasi-Newton Methods" by Broyden, Dennis, and Moré doi.org/10.1093/imamat/12.3.223"Some Convergence Properties of Broyden's Method" by Gay doi.org/10.1137/0716047"Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix" by Sherman and Morrison jstor.org/stable/2236561Background music "The Golden Present" by @JesseGallagher #BroydensMethod #NumericalAnalysis #NonlinearSystem
Approximating the Jacobian: Finite Difference Method for Systems of Nonlinear Equations Oscar Veliz 2021-05-24 | Generalized Finite Difference Method for Simultaneous Nonlinear Systems by approximating the Jacobian using the limit of partial derivatives with the forward finite difference. Example code on GitHub github.com/osveliz/numerical-velizChapters0:00 Intro0:13 Prerequisites0:32 Refresher0:43 What is the Jacobian?2:06 Approximating the Jacobian3:00 Finite Differences3:21 Note on Notation4:23 Visualization6:17 Improving Accuracy6:42 Note on Notation 27:45 Oscar's Notes8:24 Mathemaniac8:34 Thank YouRecommended ViewingFinite Difference Method youtu.be/zvrTirWMzB8Newton's Method for Systems of Nonlinear Equations youtu.be/m_nfoUz-PNYGeneralized Steffensen's Method youtu.be/ndf2vjXjXzQGeneralized Secant Method youtu.be/p2OPlnHJPNI"What is Jacobian?" by @mathemaniac youtu.be/wCZ1VEmVjVoBroyden's Method youtu.be/UlLGzW-KjHsBackground music "The Golden Present" by @JesseGallagher #FiniteDifferenceMethod #NumericalAnalysis #NonlinearSystem
Steffensens Method for Systems of Nonlinear Equations Oscar Veliz 2021-04-05 | Generalized Steffensen's Method for Simultaneous Nonlinear Systems originally credited to J. F. Traub. Video shows how to solve nonlinear systems by approximating the Jacobian. Example code on GitHub github.com/osveliz/numerical-velizChapters0:00 Prerequisites0:20 Intro 0:40 Traub1:24 Soleymani et al1:58 Explaining Notation2:32 1D Example3:06 Two Methods - Same Method3:20 System of Equations3:27 Nonlinear System Example4:42 Closer = Better ~J5:03 Oscar's Notes5:46 Thank YouRecommended ViewingSteffensen's Method with Aitken's Δ² youtu.be/BTYTj0r5PZEGeneralized Aitken-Steffensen youtu.be/-x9_fSNrX3wNewton's Method for Systems of Nonlinear Equations youtu.be/m_nfoUz-PNYGeneralized Finite Difference Method youtu.be/G25sGOWkOuQBroyden's Method youtu.be/UlLGzW-KjHsReferences"Iterative Methods for the Solution of Equations" by J. F. Traub archive.org/details/iterativemethods0000trau"A Class of Steffensen-Type Iterative Methods for Nonlinear Systems" by Soleymani et. al. doi.org/10.1155/2014/705375Background music "The Golden Present" by @JesseGallagher #Steffensen'sMethod #NumericalAnalysis #NonlinearSystem
Secant Method for Systems of Nonlinear Equations Oscar Veliz 2021-03-01 | Generalized Secant Method for Simultaneous Nonlinear Systems originally credited to Wolfe and Bittner. Lesson shows how to solve nonlinear systems without the Jacobian, nor the need to approximate it, in a straightforward and visual manner. Example code on GitHub github.com/osveliz/numerical-velizChapters0:00 Intro0:15 Prerequisites0:25 Secant Method Recap0:45 Literature1:00 Secant Method Alternative2:12 Two Methods - Same Method2:27 Nonlinear System + Example2:49 Generalized Secant Method Visualized4:12 Numeric Example4:28 Order!4:50 "A Class of Secant Methods"5:31 Oscar's Notes6:05 Thank YouRecommended ViewingSecant Method youtu.be/_MfjXOLUnywNewton's Method for Systems of Nonlinear Equations youtu.be/m_nfoUz-PNYBroyden's Method youtu.be/UlLGzW-KjHsGeneralized False Position & Alternative Secant Methods youtu.be/c2kSfJ8of7EReferences"The Secant method for simultaneous nonlinear equations" by Phillip Wolfe doi.org/10.1145/368518.368542"Eine Verallgemeinerung des Sekantenverfahrens (regula falsi) zur naherungsweisen Berechnung der Nullstellen eines nichtlinearen Gleichungssystems" by Von Leonhard Bittner borrowed from Technische Universität Dresden"Convergence of Multipoint Iterative Methods" by Leonard Tornheim doi.org/10.1145/321217.321224"An Algorithm for Solving Non-Linear Equations Based on the Secant Method" by J. G. P. Barnes doi.org/10.1093/comjnl/8.1.66"Some Efficient Algorithms for Solving Systems of Nonlinear Equations" by Richard P. Brent doi.org/10.1137/0710031"The Computational Complexity of Iterative Methods for Systems of Nonlinear Equations" by Richard Brent doi.org/10.1007/978-1-4684-2001-2_7Background music "The Golden Present" by @JesseGallagher #SecantMethod #NumericalAnalysis #NonlinearSystem
Newtons Method for Systems of Nonlinear Equations Oscar Veliz 2021-01-04 | Generalized Newton's method for systems of nonlinear equations. Lesson goes over numerically solving multivariable nonlinear equations step-by-step with visual examples and explanation of the Jacobian, the backslash operator, and the inverse Jacobian. Example code in MATLAB / GNU Octave on GitHub: http://github.com/osveliz/numerical-velizChapters0:00 Intro0:12 Prerequisites0:32 Background0:58 Setup1:54 Jacobian2:55 Historical Context5:11 Newton's Method Example Step-by-Step6:57 End Condition7:12 Numerical Example in Table7:33 Newton's Method with Backslash7:53 Newton's Method with Inverse Jacobian8:16 MATLAB / GNU Octave9:01 Newton Fractals10:51 3D Fractal11:37 Historical Optimization Newton's Method12:18 Oscar's Notes12:59 Thank YouRecommended Viewing:Newton's Method youtu.be/E24zUEKqgwQNewton Fractals youtu.be/MWD2A0Vg2V0Newton-Bisection Hybrid youtu.be/FD3BPTMGJdsVideo Mistakes youtu.be/4jw0cjddmB8Fixed Point Iteration Systems of Equations youtu.be/xa2vUsYJD-cGeneralized Aitken-Steffensen Method youtu.be/-x9_fSNrX3wSecant Method for Systems of Nonlinear Equations youtu.be/p2OPlnHJPNIGeneralized Finite Difference youtu.be/G25sGOWkOuQBroyden's Method youtu.be/UlLGzW-KjHsGlobal Newton Method youtu.be/BGZfHxzZ-7c@3blue1brown 's series on @khanacademy:Jacobian Prerequisite youtube.com/watch?v=VmfTXVG9S0UThe Jacobian Matrix youtube.com/watch?v=bohL918kXQkComputing a Jacobian Matrix youtube.com/watch?v=CGbBbH1e7YwLocal Linearity for a Multivariable Function youtube.com/watch?v=Vnga_psnCAoReferences:"Historical Development of the Newton–Raphson Method" by Ypma doi.org/10.1137/1037125"Thomas Simpson and ‘Newton's method of approximation’: an enduring myth" by Kollerstrom doi.org/10.1017/S0007087400029150"Essays on Several Curious and Useful Subjects, in Speculative and Mix'd Mathematicks" by Simpson books.google.com/books?id=3HpYAAAAcAAJ&dq"A New Treatise of Fluxions" by Simpson books.google.com/books?id=GGZbUevBqskCBackground music "The Golden Present" by @JesseGallagher #NewtonsMethod #NumericalAnalysis #NonlinearSystem
Video Mistakes II: The Sequel Oscar Veliz 2020-11-30 | This video corrects mistakes in my videos on Taylor Series Origin, Ternary Search, Dichotomous Search, Fixed Point Iteration for Fixed Point Iteration System of Equations with Banach, and Wegstein's Method. Thanks to commenters who pointed these errors out. If you find other mistakes feel free to comment or post in the GitHub Issues Forum for the code repository github.com/osveliz/numerical-velizChapters0:00 Intro0:11 Taylor Series Origin youtu.be/KJYauVgXA4E0:44 Ternary Search youtu.be/7h86n97naH40:54 Dichotomous Search youtu.be/n_zefNBfhSM1:04 Fixed Point Iteration System of Equations with Banach youtu.be/xa2vUsYJD-c1:19 Wegstein's Method youtu.be/T_6mR6rJXQQ1:58 OutroCheck out the first episode of Video Mistakes: youtu.be/4jw0cjddmB8#NumericalAnalysis
Brents Minimization Method Oscar Veliz 2020-11-05 | Hybrid minimization algorithm combining Golden-section Search and Successive Parabolic Interpolation (Jarratt's Method) that is guaranteed to locate minima with superlinear convergence order. Example code github.com/osveliz/numerical-velizChapters:0:00 Intro0:16 Scaffolding0:31 Motivation1:17 Parabolic Interpolation Review1:48 Renaming Variables2:40 Brent's Method Algorithm3:19 SPI Behaving?4:08 Note on Updating4:38 Brent's Method Visualization6:02 Numerical Example6:29 Note on Steps6:43 MATLAB fminbnd7:12 Minimum Strategy - Derivative7:49 Note on Convergence Order8:04 Oscar's Notes8:39 OutroSuggested Viewing:Golden-section Search youtu.be/wpGN2xus75wSuccessive Parabolic Interpolation - Jarratt's Method youtu.be/3WHcQofG7B8Minimization Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-xBrent-Dekker Method youtu.be/-bLSRiokgFkReferences:Brent's Book https://maths-people.anu.edu.au/~brent/pub/pub011.htmlMATLAB fminbnd documentation mathworks.com/help/matlab/ref/fminbnd.htmlSciPy documentation docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize_scalar.htmlGNU Octave fminbnd documentation octave.org/doc/v4.0.1/Minimizers.htmlBackground music "The Golden Present" by @JesseGallagher#GoldenSectionSearch #SuccessiveParabolicInterpolation #NumericalAnalysis
Successive Parabolic Interpolation - Jarratts Method Oscar Veliz 2020-09-29 | Optimization method for finding extrema of functions using three points to create a parabola that is then used to find the next approximation to the solution. This lesson visualizes the behavior of the method with numeric examples as well as its convergence through fractals. Based off the paper "An iterative method for locating turning points" by P. Jarratt. Example code github.com/osveliz/numerical-velizChapters:0:00 Intro0:21 Scaffolding0:42 Richard P. Brent1:01 An Iterative Method for Locating Turning Points1:33 Graphing1:46 Create a Quadratic1:58 Finding the Next Point2:35 The Next Iteration2:22 Derivative is Zero2:56 Avoid Calculating L_23:32 Jarratt's Method3:47 Example4:10 Fractal Scaffolding4:20 Complex Plane Discussion5:47 Jarratt Fractal z^4/4 - z6:33 Jarratt Fractal -cos(z)6:55 Jarratt Fractal z^9/9 + 3z^5 - 16z7:52 Jarratt's Notes8:32 Oscar's Notes9:00 Thank YouSuggested Viewing:Ternary Search youtu.be/7h86n97naH4Lagrange Polynomials youtu.be/GtJKUIG9KXIMuller's Method youtu.be/XIIEjwtkONcInverse Quadratic Interpolation youtu.be/-bLSRiokgFkBrent's Minimization Method youtu.be/BQm7uTYC0sgReferences:Jarratt's paper doi.org/10.1093/comjnl/10.1.82Brent's Book https://maths-people.anu.edu.au/~brent/pub/pub011.htmlBackground music "The Golden Present" by @JesseGallagher#SuccessiveParabolicInterpolation #NumericalAnalysis
Sublinear Convergence #MegaFavNumbers Oscar Veliz 2020-08-31 | Lesson discusses the convergence rate of the Gregory-Leibniz series for computing pi and the mega number of terms needed for 100 decimal digits of accuracy. Example code on github.com/osveliz/numerical-velizChapters:0:00 Intro0:18 Scaffolding1:03 Gregory-Leibniz Series1:36 Numerical Iterations2:24 Finding n Setup3:09 Finding n Bad Example3:34 Finding n Good Example4:43 Oscar's Notes5:17 Thank YouRecommend Viewing:Machin-like Formula youtu.be/M_fTdDx8IlYWhat is Order of Convergence youtu.be/JTinepDn1dIThank you to @singingbanana for putting together the playlist for #MegaFavNumbers and to my GitHub Sponsor community for requesting this video.Background music "The Golden Present" by @Jesse Gallagher#ConvergenceOrder #NumericalAnalysis
Golden-section Search Oscar Veliz 2020-07-22 | Golden-section Search is a minimization algorithm that expands on the Fibonacci Search scheme described 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 the golden ratio (phi). Code can be found on GitHub github.com/osveliz/numerical-velizChapters0:00 Intro0:23 Algorithms for Minimization without Derivatives0:43 Optimum Seeking Methods1:34 Ternary Recap2:04 Reusing Points2:22 Finding c2:45 Fixed Constant Ratio3:28 Computing c3:58 Golden-section Search Algorithm4:47 GSS Visualized5:31 Numerical Example5:55 Comparing Methods6:18 Search Space Shrinkage7:01 Golden Ratio Extra History7:28 Properties of φ8:13 Oscar's Notes8:38 Mathemaniac8:49 Thank YouSuggested Viewing:Ternary Search youtu.be/7h86n97naH4Dichotomous Search youtu.be/n_zefNBfhSMFibonacci Search youtu.be/GAafWFRGP7kJarratt's Method - Successive Parabolic Interpolation youtu.be/3WHcQofG7B8Brent's Minimization Method youtu.be/BQm7uTYC0sgMinimization Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-xTwo opposite games involving golden ratio (ft. Tom Rocks Maths) by @mathemaniac youtu.be/UOAylfclg14References:Algorithms for Minimization without Derivatives by Richard P. Brent https://maths-people.anu.edu.au/~brent/pub/pub011.htmlOptimum Seeking Methods by Douglass Wilde archive.org/details/optimumseekingme00wildSequential Minimax Search for a Maximum by J. Kiefer jstor.org/stable/2032161Best Exploration for Maximum is Fibonaccian by S. M. Johnson https://apps.dtic.mil/dtic/tr/fulltext/u2/224385.pdfBackground music "The Golden Present" by @JesseGallagher#GoldenSectionSearch #NumericalAnalysis
Fibonacci Search Oscar Veliz 2020-06-24 | 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-velizChapters0:00 Intro0:12 Recap0:23 Optimum Seeking Method0:41 Sequential Minimax Search for a Maximum1:06 Best Exploration for Maximum is Fibonaccian1:23 Kiefer's Ratios1:33 Kiefer's Ratios Example1:50 Kiefer's Ratios Visualized2:49 Fibonacci Search Visualized3:58 Advantage of Fibonacci4:16 Stopping Condition4:47 Finding n5:12 Johnson's Remarks on n5:27 Ending Interval Length5:48 Fibonacci Search Algorithm6:56 Fibonacci Search Numerical Example7:26 Finding n from the Example7:49 Kiefer's Constant Ratio8:03 Johnson's Golden-section8:19 Oscar's Notes8:42 Thank YouSuggested Viewing:Ternary Search youtu.be/7h86n97naH4Dichotomous Search youtu.be/n_zefNBfhSMGolden-section Search youtu.be/wpGN2xus75wJarratt's Method - Successive Parabolic Interpolation youtu.be/3WHcQofG7B8Minimization Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-xReferences:Optimum Seeking Methods by Douglass Wilde archive.org/details/optimumseekingme00wildSequential Minimax Search for a Maximum by J. Kiefer www.jstor.org/stable/2032161Best Exploration for Maximum is Fibonaccian by S. M. Johnson https://apps.dtic.mil/dtic/tr/fulltext/u2/224385.pdf#FibonacciSearch #NumericalAnalysis
Dichotomous Search Oscar Veliz 2020-05-31 | Dichotomous Search is an improved version of Ternary Search. This video describes the motivation and algorithm followed by a visualized example. Code can be found on GitHub github.com/osveliz/numerical-veliz*Correction* The numerical example used epsilon = 10^(-6) not 10^(-7) see Video Mistakes II: The Sequel youtu.be/YEUbzqkJBf0Chapters0:00 Intro0:19 Ternary Recap0:32 Moving Test Points0:59 Computing c and d1:19 A Tale of Halving1:40 Optimum Seeking Methods2:17 End Condition3:04 Dichotomous Search Algorithm3:50 Numerical Example4:03 Oscar's Notes4:36 Thank YouSuggested Viewing:Ternary Search youtu.be/7h86n97naH4Fibonacci Search youtu.be/GAafWFRGP7kGolden-section Search youtu.be/wpGN2xus75wJarratt's Method - Successive Parabolic Interpolation youtu.be/3WHcQofG7B8Minimization Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-xReference:Optimum Seeking Methods by Douglass Wilde archive.org/details/optimumseekingme00wild#DichotomousSearch #NumericalAnalysis
Ternary Search Oscar Veliz 2020-05-31 | Ternary Search is an interval-based divide-and-conquer algorithm for finding the minimum of a unimodal function. This video describes how to find a minimum when the derivative is know, defines unimodal, presents interval-based approaches for minimum finding, and visualizes the algorithm. Example code available on GitHub github.com/osveliz/numerical-veliz*Correction* The numerical example used epsilon = 10^(-6) not 10^(-7) see Video Mistakes II: The Sequel youtu.be/YEUbzqkJBf0Chapters0:00 Intro0:23 Minimum Finding0:42 Derivative Plot1:01 Minimum Strategy: Derivative1:32 Unimodal2:24 Unimodal Examples2:35 Not Unimodal Examples2:48 Maximum Finding?3:11 Splitting into Intervals4:26 Minimum Strategy: Intervals5:09 Ternary Search Algorithm5:58 Ternary Search Visualized6:32 Numerical Example7:03 Optimization 1 - Test Ends7:39 Optimization 2 - Check Equal7:56 Discussion8:28 Oscar's Notes9:04 Thank YouSuggested Viewing:Bisection Method youtu.be/MlP_W-obuNgDichotomous Search youtu.be/n_zefNBfhSMFibonacci Search youtu.be/GAafWFRGP7kGolden-section Search youtu.be/wpGN2xus75wJarratt's Method - Successive Parabolic Interpolation youtu.be/3WHcQofG7B8Minimum Finding Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-xReference:Algorithms for Minimization without Derivatives by Richard P. Brent https://maths-people.anu.edu.au/~brent/pub/pub011.html#TernarySearch #NumericalAnalysis
Computing π: Machin-like formula Oscar Veliz 2020-03-14 | Machin-like formulae are used to find many decimal places of pi, although why they work can seem confusing. This lesson shows how the Taylor Series of arctangent is used to compute π, and the power of combining it with Machin's approach, as well as covering the history of Gregory, Leibniz, Euler, and Machin. Example code: github.com/osveliz/numerical-veliz/tree/master/src/seriesChapters00:00 - Intro00:11 - Taylor Series00:20 - Unit Circle & Solve for π00:57 - Gregory01:07 - Gregory-Leibniz Series01:33 - Leibniz02:27 - arctan(1)02:48 - Moving a03:40 - Increasing n04:11 - Getting Close04:44 - Nearer to zero05:07 - Adding arctangents example05:28 - Arctangent Trick05:51 - Euler06:06 - Euler's Equation for π06:26 - Deriving Euler's Equation07:00 - Machin intro07:15 - Machin-like formula08:00 - John Machin08:22 - Demo Code & Story Time09:40 - 10,000 digits of π10:08 - Beckmann's thoughts on higher digits10:27 - Oscar's Notes11:00 - Thank YouSuggested Viewing:Origin of Taylor Series - youtu.be/KJYauVgXA4ENewton Fractals - youtu.be/MWD2A0Vg2V0Reference Links:"James Gregory Tercentenary memorial volume" - catalog.hathitrust.org/Record/000438471"A History of Pi" by Petr Beckmann books.google.com/books?id=XqqUUSyz138C&dq=a+history+of+piLeibniz's π paper - books.google.com/books?id=E7MasYIsMKQC&pg=PA41"On the Leibnizian quadrature of the circle" - http://ac.inf.elte.hu/Vol_004_1983/075.pdf"The Discovery of the Series Formula for π by Leibniz, Gregory and Nilakantha" - tandfonline.com/doi/pdf/10.1080/0025570X.1990.11977541"How Euler Did Even More" by C. Edward Sandifer books.google.com/books?id=3c6iBQAAQBAJ&dq=how+euler+did+even+moreEuler's π paper E705 - http://eulerarchive.maa.org/pages/E705.html"John Machin and Robert Simson on Inverse-tangent Series for π" jstor.org/stable/41133896"Synopsis palmariorum matheseos" by William Jones - books.google.com/books/about/Synopsis_palmariorum_matheseos.html?id=eZPRxQEACAAJCLISP source code for π - github.com/clisp-lang/clisp/blob/520f02b36acbb49a9d0c93870f3dc4cb3d00e6d9/src/realtran.d#pi #PiDay #π
Origin of Taylor Series Oscar Veliz 2020-02-24 | The history of Taylor Series and Maclaurin Series including the works of de Lagny, Halley, Gregory, and Madhava using primary sources whenever possible. Lesson also presents the Taylor Theorem along with visualizations of James Gregory's equations. Finally the video discusses the time period and context during the battle over calculus.Chapters00:00 Intro00:20 Solving Cube Roots00:53 de Lagny's Conditions01:26 Halley's Equations03:46 Taylor's Letter04:04 Taylor's Treatise04:25 Two Mathematical Camps04:51 Quotes About Taylor05:29 Methodus06:34 Going Back in Time06:47 James Gregory07:13 Gregory's Letter07:47 Gregory's Other Series08:32 Certain Mathematical Achievements08:59 Taylor Series09:31 Taylor Series Example10:27 Colin Maclaurin11:10 Nilakantha and Madhava11:28 Oscar's Notes11:58 Thank You**Corrections** The second value of b at 2:22 is actually negative. James Gregory was 36 years old, not 37, when he died. The numerator at 9:18 should be f^(k)(a)(x-a)^k not f^(k)(x-a)^k. See Video Mistakes II: The Sequel youtu.be/YEUbzqkJBf0Suggested Videos:Halley's Method youtu.be/3WiVGSy_084Video Mistakes and How to Fix Them youtu.be/4jw0cjddmB8Computing π: Machin-like formula youtu.be/M_fTdDx8IlYReferences:Methodus archive.org/details/UFIE003454_TO0324_PNI-2529_000000/page/6/mode/2upMethodus (english) http://www.17centurymaths.com/contents/taylorscontents.htmlAn account of methodus royalsocietypublishing.org/doi/10.1098/rstl.1714.0039A Treatise of Fluxions books.google.com/books?id=NUw7AQAAIAAJ&vqHalley's Method biodiversitylibrary.org/page/23266907#page/660/mode/1upThomas Fantet de Lagny (French) https://nubis.univ-paris1.fr/ark%3A/15733/3415#?c=&m=&s=&cv=&xywh=-56%2C-26%2C1895%2C2570Brook Taylor and the method of increments link.springer.com/article/10.1007/BF00329903Certain Mathematical Achievements of James Gregory tandfonline.com/doi/abs/10.1080/00029890.1943.11991343Colin Maclaurin tandfonline.com/doi/abs/10.1080/00029890.1947.11991846The Discovery of the Series Formula for π byLeibniz, Gregory and Nilakantha tandfonline.com/doi/pdf/10.1080/0025570X.1990.11977541James Gregory Tercentenary Memorial Volume catalog.hathitrust.org/Record/000438471#TaylorSeries #NumericalAnalysis
What is Order of Convergence? Oscar Veliz 2020-01-05 | Converge order and error reduction can be confusing but this video breaks it down and provides examples showing how order relates to speed and runtime. It also explains how order of convergence relates to Big O. Watching the other videos on this channel can be helpful but is not necessary. Example root finding method code for all of the above methods can be found on github github.com/osveliz/numerical-velizBecome a GitHub Sponsor github.com/sponsors/osvelizChapters00:00 - Intro00:19 - Order Montage00:54 - Error Definition01:11 - Introduction of α01:35 - α equation01:41 - α example 1 Bisection02:09 - Solving for M02:36 - α example 2 False Position03:13 - α example 3 Newton03:41 - On Function Calls04:19 - α with iterations and runtime05:02 - Note on previous example05:23 - Generalized operation count06:28 - How fast is linear?07:29 - How fast is quadratic?09:33 - Digits of accuracy10:15 - Distance impacts α10:52 - Big O brief intro11:37 - Big O of Bisection12:09 - Big O of Newton and Halley13:02 - Oscar's Notes13:47 - Thank YouThe other methods referenced in this video include: Fixed Point Iteration Method, Bisection Method, False Position Method - Regula Falsi, Newton's Method, Steffensen's Method, Wegstein's Method, Muller's Method, Durand-Kerner Method, Secant Method, Householder's Method, and Halley's Method. All of these method can be found in this root finding playlist youtube.com/playlist?list=PLb0Tx2oJWuYIpNE23qYHGQD42TIR3ThNz#ConvergenceOrder #NumericalAnalysis
Video Mistakes and How to Fix Them Oscar Veliz 2019-12-16 | This video corrects mistakes in my videos on Newton's Method, Newton Fractals, Newton-Bisection Hybrid, Halley's Method, and Cubic Splines. Thanks to commenters who pointed these errors out. If you find other mistakes feel free to comment or post in the GitHub Issues Forum for the code repository github.com/osveliz/numerical-velizChapters0:00 Intro0:11 Newton's Method youtu.be/E24zUEKqgwQ0:48 Newton Fractals youtu.be/MWD2A0Vg2V01:07 Newton-Bisection Hybrid youtu.be/FD3BPTMGJds1:58 Halley's Method youtu.be/3WiVGSy_0843:00 Cubic Splines youtu.be/f4iNbNRKZKUCheck out the 2,500 Subscriber Milestone video youtu.be/YpSKjCo9M-8 and Video Mistakes II: The Sequel youtu.be/4jw0cjddmB8#NumericalAnalysis
Subscriber Milestone - 5 Ways to Help the Channel Oscar Veliz 2019-12-01 | 2,500 Subscribers!!! This video covers five ways to help the channel including an updated process for submitting topic requests and a community funding opportunity through @GitHub. Thank you for your feedback and support on these videos. Here's to the next 2,500!Subscribe: youtube.com/OscarVeliz?sub_confirmation=1GitHub Repository: http://github.com/osveliz/numerical-velizTopic Request: github.com/osveliz/numerical-veliz/issuesGitHub Sponsor: github.com/sponsors/osvelizCommunity Captions: http://www.youtube.com/timedtext_cs_panel?c=UCiUgUMz7OCDbX78z15SJtPg&tab=2
Householders Method Oscar Veliz 2019-10-01 | Householder's Method for finding roots of equations including history, derivation, examples, and fractals. Example code is available on GitHub github.com/osveliz/numerical-velizChapters0:00 Intro0:25 Derivation1:58 History2:34 Householder's Method4:07 Householder's Method Example4:41 Higher Order Householder's Method Examples5:30 Principles of Numerical Analysis6:03 Householder Fractals8:10 Summary8:41 Thank YouSuggested Videos:Newton's Method youtu.be/E24zUEKqgwQNewton's Method Convergence Interval youtu.be/zyXRo8Qjj0ANewton Fractals youtu.be/MWD2A0Vg2V0Halley's Method youtu.be/3WiVGSy_084Newton-Bisection Hybrid youtu.be/FD3BPTMGJdsReference:Householder's book archive.org/details/principlesofnume030218mbp/page/n143Petković's paper sciencedirect.com/science/article/pii/S0377042709006347#HouseholdersMethod #NumericalAnalysis
Halleys Method Oscar Veliz 2019-08-25 | Halley's Method (the method of tangent hyperbolas) for finding roots including history, derivation, examples, and fractals. Also discusses Taylor's Theorem relating to Halley's Method as well as Halley's Comet. Sample code and images available on GitHub github.com/osveliz/numerical-velizChapters00:00 Intro00:36 History03:48 Derivation Setup05:20 Derivation Tangent Hyperbolas06:00 Derivation Taylor Series07:21 Example07:53 Example 2 (see correction)08:24 Newton versus Halley08:45 Example 309:29 Halley Fractals11:27 Summary11:52 Thank YouCorrections: The example at 8:08 had an error with the programming of f'(x). The bug caused the numbers in the table and the plots for that example to be incorrect. There is a separate issue in that example where 2 was written as the input instead of -2. Also there is typo in the name Christopher Wren at 0:46. A video covering these corrections can be found here youtu.be/4jw0cjddmB8 Suggested viewing:Newton's Method youtu.be/E24zUEKqgwQNewton Convergence Interval youtu.be/zyXRo8Qjj0ANewton Fractal youtu.be/MWD2A0Vg2V0Laguerre's Method youtu.be/blOARV4lnIMHouseholder's Method youtu.be/F9DFewL0mhoReference Links:* On the Geometry of Halley's Method - jstor.org/stable/2975033* Halley's Method (Latin) - royalsocietypublishing.org/doi/abs/10.1098/rstl.1694.0029* Halley's Method (English) - biodiversitylibrary.org/page/23266907* Thomas Fantet de Lagny (French) - https://nubis.univ-paris1.fr/ark%3A/15733/3415#?c=0&m=0&s=0&cv=0&xywh=-312%2C-140%2C2406%2C2799* Raphson's Book (Latin) - archive.org/details/bub_gb_4nlbAAAAQAAJ/page/n5* A Synopsis of the Astronomy of Comets (English) - https://library.si.edu/digital-library/book/synopsisofastron00hall* A Synopsis of the Astronomy of Comets (Latin) - jstor.org/stable/102980* Principia (English) - openlibrary.org/books/OL7089085M/Newton%27s_Principia* Principia (Latin) - loc.gov/item/28020872* Brook Taylor and the Method of Increments - link.springer.com/article/10.1007/BF00329903* Royal Society Charter - http://ttp.royalsociety.org/ttp/ttp.html?id=c627ecf4-22aa-4e4f-8919-c6a514f441aa&type=bookSong: "A Quiet Thought" by Wayne Jones#HalleysMethod #NumericalAnalysis
Laguerres Method Oscar Veliz 2019-07-14 | Laguerre's method for finding real and complex roots of polynomials. Includes history, derivation, examples, and discussion of the order of convergence as well as visualizations of convergence behavior. Example code available on github github.com/osveliz/numerical-velizChapters00:00 Intro00:20 Sources00:44 Derivation03:08 Laguerre's Method03:52 K. A. Redish04:13 Visuzliation05:24 Forman S. Acton06:05 Example07:04 Example 207:43 Example 308:01 Convergence8:35 Laguerre Fractal10:05 Summary10:34 Thank YouFurther Viewing:Newton's Method youtu.be/E24zUEKqgwQHorner's Method youtu.be/zEvfkSuPqWkNewton Fractals youtu.be/MWD2A0Vg2V0Aberth-Ehrlich Method youtu.be/XIzCzfMDSzkHalley's Method and Fractal youtu.be/3WiVGSy_084Householder's Method and Fractal youtu.be/F9DFewL0mhoBairstow's Method youtu.be/iUGEk6kngFwReference Links:"Racines d'une Équation Algébrique" by Laguerre babel.hathitrust.org/cgi/pt?id=miun.aan9493.0001.001&view=1up&seq=103"On Laguerre's Method" by K. A. Redish tandfonline.com/doi/abs/10.1080/0020739740050112"Numerical Methods That Work" by Forman S. Acton books.google.com/books?id=cGnSMGSE5Y4C&lpg=PP1&pg=PA187#v=onepage&q&f=false
Aberth-Ehrlich Method Oscar Veliz 2019-05-29 | The Aberth-Ehrlich Method for solving all roots of a polynomial simultaneously including history, methodology, examples, and order as well as comparison to Durand-Kerner. Example code github: http://github.com/osveliz/numerical-velizChapters0:00 Intro0:19 History0:41 Methodology0:59 Starting Points1:11 Starting Points Visualized1:33 Newton Fractal2:22 A Modified Newton Method2:35 Ehrlich's Derivation4:43 Example5:09 Durand-Kerner versus Aberth-Ehrlich6:22 Behavior of Aberth-Ehrlich6:33 Notes on Aberth-Ehrlich7:01 Thank YouFurther viewing:Durand-Kerner youtu.be/5JcpOj2KtWcLaguerre's Method youtu.be/blOARV4lnIMNewton Fractals youtu.be/MWD2A0Vg2V0Bairstow's Method youtu.be/iUGEk6kngFwReferences:Aberth's paper ams.org/journals/mcom/1973-27-122/S0025-5718-1973-0329236-7Ehrlich's paper dl.acm.org/citation.cfm?id=363115Kerner link.springer.com/article/10.1007%2FBF02162564Algorithm 283 dl.acm.org/citation.cfm?id=365527Wilkinson dl.acm.org/citation.cfm?id=1096474Maehly link.springer.com/article/10.1007/BF01600333Börsch link.springer.com/article/10.1007%2FBF01385904#DurandKerner #AberthEhrlich #NumericalAnalysis
Durand-Kerner Method Oscar Veliz 2019-05-29 | The Durand-Kerner Method for solving all roots of a polynomial simultaneously including complex solutions. Example code github: http://github.com/osveliz/numerical-velizChapters0:00 Intro0:24 History1:04 Methodology & Derivation2:28 Example 1 real numbers2:55 Example 2 need for complex numbers3:19 Complex Roots3:39 Complex Numbers Visualized4:16 Example 2 with complex numbers5:00 Formal Definition5:28 Starting Points6:14 Example 3 Visualized6:57 Behavior of Durand-Kerner7:33 Computational Order7:54 Notes on Durand-Kerner8:23 Thank YouFurther Viewing:Fixed Point Iteration Systems of Equations with Banach youtu.be/xa2vUsYJD-cHorner's Method youtu.be/zEvfkSuPqWkAberth-Ehrlich youtu.be/XIzCzfMDSzkBairstow's Method youtu.be/iUGEk6kngFwPrimary SourcesKerner's paper link.springer.com/article/10.1007%2FBF02162564Durand, Émile. "Solutions numériques des équations algébriques. Tome I: Équations du type F(x)=0, racines d'un polynôme." (1960).Dochev's paper sciencedirect.com/science/article/abs/pii/004155536490148XWeierstrass's paper http://bibliothek.bbaw.de/bibliothek-digital/digitalequellen/schriften/anzeige?band=10-sitz/1891-2&seite:int=00000565Ehrlich's paper dl.acm.org/citation.cfm?id=363115Aberth's paper ams.org/journals/mcom/1973-27-122/S0025-5718-1973-0329236-7#DurandKerner #AberthEhrlich #NumericalAnalysis
Generalized Aitken-Steffensen Method Oscar Veliz 2019-03-14 | Generalized Aitken's delta-squared method and Generalized Steffensen's Method applying Fixed Point Iteration to Systems of Nonlinear Equations. Video goes step-by-step to derive Generalized Aitken-Steffensen and discusses induced and accelerated convergence behavior as well as quadratic order. Example code github: http://github.com/osveliz/numerical-velizChapters0:00 Intro0:40 Motivation2:32 Solve for X*3:10 Generalized Aitken3:44 Generalized Aitken Example4:10 Generalized Aitken-Steffensen Method4:40 Generalized Aitken-Steffensen Method Example 15:02 Generalized Aitken-Steffensen Method Example 25:26 Henrici5:59 On Order & Proving Convergence6:31 Proof Intuition6:55 Notes7:40 Thank YouRecommended Viewing:Fixed Point Iteration youtu.be/OLqdJMjzib8Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2oSteffensen's Method with Aitken's Δ² youtu.be/BTYTj0r5PZEFixed Point Iteration Systems of Equations youtu.be/xa2vUsYJD-cGeneralized Newton's Method youtu.be/p0SBubUfwiIGeneralized Steffensen's Method youtu.be/ndf2vjXjXzQReferences:Elements of Numerical Analysis by Peter Henrici archive.org/details/ElementsOfNumericalAnalysis/page/n65Tatsuo Noda "The Steffensen Iteration Method for Systems of Nonlinear Equations" projecteuclid.org/euclid.pja/1195515278 projecteuclid.org/euclid.pja/1195513725 and projecteuclid.org/euclid.pja/1195514312Yves Nievergelt "Aitken's and Steffensen's Accelerations in Several Variables" link.springer.com/article/10.1007/BF01385782#AitkensDeltaSquaredMethod #SteffensensMethod #NumericalAnalysis
Fixed Point Iteration System of Equations with Banach Oscar Veliz 2019-03-14 | Fixed Point Iteration Method to solve Systems of Nonlinear Equations with discussion of Banach Fixed Point Theorem, finding the Jacobian, convergence, and order. Example code on GitHub: http://github.com/osveliz/numerical-velizChapters:00:00 Intro00:25 Systems of Equations00:33 Solving Nonlinear Systems01:03 Fixed Point Iteration01:26 Rewriting Equations02:03 Example 102:23 Visualized Example03:12 Measuring Distance and Norm03:45 End Conditions04:09 Different Combinations of Rewrites04:45 When Does it Converge?05:10 Banach Fixed Point Theorem05:56 The Jacobian06:48 Contraction Mapping Test07:24 Contraction Mapping Test Examples08:20 Notes on the Contraction Mapping Test09:06 Order of Convergence09:41 Exact Order10:31 Summary10:49 Thank YouSee Video Mistakes II: The Sequel youtu.be/YEUbzqkJBf0 for a small correction.Recommended Viewing:Fixed Point Iteration youtu.be/OLqdJMjzib8Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2oGeneralized Aitken-Steffensen youtu.be/-x9_fSNrX3wGeneralized Newton's Method youtu.be/p0SBubUfwiIReference Link:"Elements of Numerical Analysis" by Peter Henrici archive.org/details/ElementsOfNumericalAnalysis/page/n57#FixedPointIteration #NumericalAnalysis
Newton Fractals Oscar Veliz 2019-01-01 | Using Newton's 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 github.com/osveliz/numerical-velizCorrection: 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 youtu.be/4jw0cjddmB8Chapters0:00 Intro0:16 Convergence Interval Recap0:42 Imaginary Numbers1:05 Newton's Method in Complex Plane1:29 Basin of Convergence1:38 Arctangent Fractal1:50 Newton Fractal2:10 Why Fractals Emerge2:54 Example z^3-14:07 Example sin(z)4:33 Example z^8+15z^4-164:50 Generalized Newton Fractal5:05 Generalized Newton Fractal Examples6:16 Summary6:42 Thank YouFurther Viewing:Newton's Method youtu.be/E24zUEKqgwQNewton's Method Interval of Convergence youtu.be/zyXRo8Qjj0ANewton Bisection Hybrid (Newt-Safe) youtu.be/FD3BPTMGJdsLaguerre's Method and Fractal youtu.be/blOARV4lnIMHalley's Method and Fractal youtu.be/3WiVGSy_084Generalized Newton's Method youtu.be/p0SBubUfwiIFurther Reading:Numerical Recipes http://numerical.recipes/Wikipedia en.wikipedia.org/wiki/Newton_fractal#Fractal #NewtonsMethod #NumericalAnalysis
Newton Bisection Hybrid (Newt-Safe) Oscar Veliz 2018-12-09 | Newton Bisection Hybrid Method for root finding. Example code available at github.com/osveliz/numerical-velizChapters0:00 Intro0:26 Viewer Request0:49 Numerical Recipes1:12 Numerical Methods That Work1:54 Motivation Examples3:04 Problems with Newton Recap3:17 Newt-Safe Basic Algorithm4:00 Newt-Safe Basic Examples4:53 Additional Conditions5:39 ΔX Condition Explanation6:33 ΔX Example7:18 Newt-Safe without Interval7:55 Other Hybrid Methods8:33 Notes and Summary8:57 Thank YouCorrection: The bracket size test at 5:26 used DeltaX which should be DeltaX_old. A video covering this mistake can be found here youtu.be/4jw0cjddmB8Further Viewing:Bisection Method youtu.be/MlP_W-obuNgNewton's Method youtu.be/E24zUEKqgwQNewton's Method Interval of Convergence youtu.be/zyXRo8Qjj0ANewton Fractal youtu.be/MWD2A0Vg2V0Halley's Method youtu.be/3WiVGSy_084Householder's Method youtu.be/F9DFewL0mhoReference Links:Based of off NewtSafe from Marc Spiegelman https://www.ldeo.columbia.edu/~mspieg/e4300/BlankPDFs/Lecture06_blank.pdfrtsafe from Numerical Recipes http://numerical.recipes/Numerical Methods That Work by Forman S. Acton books.google.com/books?id=cGnSMGSE5Y4C&lpg=PA41&pg=PA51#v=onepage&q&f=false#BisectionMethod #NewtonsMethod #NumericalAnalysis
Fixed Point Iteration Q&A Oscar Veliz 2018-11-09 | Fixed Point Iteration Method followup video answering your frequently asked questions like "How do you pick a starting point?" and "How do you use the convergence test without the root?" Example code can be found at github.com/osveliz/numerical-veliz specifically in the programs for Steffensen's and Wegstein's Methods.Chapters0:00 Intro0:14 Why not x = x^2 -1?1:08 Where did 1.618 come from?1:29 How do you pick a starting point?2:04 How do you find the other root?3:24 Use the Convergence Test without the root? Which root do you use in the test?4:22 On the Matter of Convergence5:04 Thank YouSuggested VideosFixed Point Iteration: youtu.be/OLqdJMjzib8Steffensen's Method with Aitken's Δ²: youtu.be/BTYTj0r5PZEWegstein's Method: youtu.be/T_6mR6rJXQQ#FixedPointIteration #NumericalAnalysis
Wegsteins Method Oscar Veliz 2018-10-09 | Wegstein Method for finding roots, accelerating fixed point iteration, and inducing convergence in fixed point iteration. Explained examples and discussion of order as well as how to compute q. Example code: github.com/osveliz/numerical-velizChapters0:00 Intro0:22 Wegstein's Method Sources0:52 Wegstein's Methodology1:56 Wegstein's Method Examples3:24 Computing q4:55 Computing q example5:24 Updating q5:43 Updating q example6:03 Computational Order6:36 Oscar's Notes7:13 Thank YouSee Video Mistakes II: The Sequel youtu.be/YEUbzqkJBf0 for a small error and correction.Suggestions for further watching:Fixed Point Iteration: youtu.be/OLqdJMjzib8Steffensen's Method with Aitken's Δ²: youtu.be/BTYTj0r5PZEFixed Point Iteration Q&A youtu.be/FyCviw2ZA2oReferences:Wegstein's original paper: dl.acm.org/citation.cfm?id=368871Gutzler's thesis: https://ir.library.oregonstate.edu/downloads/2r36v1962#WegsteinsMethod #NumericalAnalysis
Power Method with Inverse & Rayleigh Oscar Veliz 2018-09-02 | Discussion of Eigenvalues & Eigenvectors, Power Method, Inverse Power Method, and the Rayleigh Quotient with brief overview of Rayleigh Quotient Iteration. Example code hosted on GitHub github.com/osveliz/numerical-velizChapters0:00 Title Card0:12 Terminology0:37 Eigenvalue Example1:04 Power Method1:29 Power Method Example2:33 Notes on Power Method2:50 Inverse Power Method3:21 Inverse Power Method Example4:12 Rayleigh Quotient4:54 Solve using Determinant5:15 Inverse Power Method with Shift5:34 Inverse Power Method with Shift Example6:12 Rayleigh Quotient Iteration6:37 Summary7:01 Thank You#PowerMethod #RayleighQuotient #NumericalAnalysis
Horners Method Oscar Veliz 2018-08-01 | Horner's Method (Ruffini-Horner Scheme) for evaluating polynomials including a brief history, examples, Ruffini's Rule with derivatives, and root finding using Newton-Horner. Example code on GitHub github.com/osveliz/numerical-velizChapters0:00 Intro0:11 - History1:33 - TLDR1:47 - Function vs Polynomial2:23 - Horner's Method2:50 - Horner's Method Examples3:36 - Synthetic Division4:32 - Ruffini's Rule Main Idea4:58 - Ruffini's Rule5:34 - Derivative with Ruffini's Rule6:00 - Derivative Example6:27 - Polynomial Root Finding6:36 - Algebraic Root Finding6:59 - Rational Root Theorem7:35 - Newton-Horner Method8:23 - Newton-Horner Example9:11 - Summary9:36 - Thank YouFurther Viewing:Newton's Method youtu.be/E24zUEKqgwQLaguerre's Method youtu.be/blOARV4lnIMNewton Fractals youtu.be/MWD2A0Vg2V0Durand-Kerner Method youtu.be/5JcpOj2KtWcAberth-Ehrlich Method youtu.be/XIzCzfMDSzkBairstow's Method youtu.be/iUGEk6kngFwReferences:Horner's paper jstor.org/stable/107508 Ruffini doi.org/10.1090/S0002-9904-1911-02072-9Chemla's paper doi.org/10.1017/S0957423900001235Qin Jiushao http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.454.4986&rep=rep1&type=pdf#page=169Sharaf al-Dīn al-Tūsī doi.org/10.1016/0315-0860(89)90099-2Jia Xian https://www.math.vt.edu/people/brown/doc/fibo_number.pdfYong's paper https://sms.math.nus.edu.sg/smsmedley/Vol-14-1/The%20development%20of%20polynomial%20equations%20in%20traditional%20China(Lam%20Lay%20Yong).pdf#HornersMethod #NumericalAnalysis
Steffensens Method with Aitkens Δ² Oscar Veliz 2018-07-01 | Discussion of Steffensen's Method and Aitken's Delta-Squared Method with their relation to Fixed Point Iteration including examples, convergence acceleration, order, and code.GitHub: github.com/osveliz/numerical-velizChapters0:00 Intro0:08 Aitken's Δ² Method History0:23 Derivation with Example1:01 Aitken's Δ² Method1:21 Solve for r2:16 Δ² Notation2:39 Aitken's Δ² Example3:12 Steffensen's Method History3:40 Steffensen's Methodology4:05 Steffensen's Method Example4:43 Steffensen's Method 2.04:55 One Method, Two Versions6:30 Steffensen's Method 2.0 Continued6:55 Order7:26 Summary8:02 Thank YouFurther Watching:Fixed Point Iteration youtu.be/OLqdJMjzib8Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2oWegstein's Method youtu.be/T_6mR6rJXQQFixed Point Iteration Nonlinear Systems youtu.be/xa2vUsYJD-cGeneralized Aitken-Steffensen youtu.be/-x9_fSNrX3wReference Links:Aitken's paper: cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/xxvon-bernoullis-numerical-solution-of-algebraic-equations/64D4A7C56F1EFEC696AF68D7870DB451Steffensen's paper: tandfonline.com/doi/abs/10.1080/03461238.1933.10419209Kumar et. al: sciencedirect.com/science/article/pii/S1110256X1300028X#AitkensDeltaSquaredMethod #SteffensensMethod #NumericalAnalysis
Brents Method Oscar Veliz 2018-06-01 | Dekker's Method, Inverse Quadratic Interpolation, and Brent's Method including example, code, and discussion of order. GitHub github.com/osveliz/numerical-velizChapters00:00 Intro00:12 Secant Method Recap00:37 Bisection Method Recap00:54 Dekker's Method History01:35 Dekker's Method Big Idea01:50 Dekker's Method02:28 Dekker's Method Visual Example02:50 Dekker's Method Update Step03:48 Dekker's Method Visual Example Continued04:19 Dekker's Method Example05:04 Tolerance05:20 "Remarks on the Paper by Dekker"05:58 George E. Forsythe06:30 Brent's Method06:59 Brent's Method Big Idea07:19 Inverse Quadratic Interpolation07:30 Create a Quadratic07:50 Lagrange Polynomial08:01 Inverse Quadratic08:32 Inverse Quadratic Interpolation Methodology08:54 Inverse Quadratic Simplified09:23 Trouble with IQI09:55 Brent's Method - Round 211:06 Ill Behaved Functions11:58 Comparison12:32 Computational Order13:06 Summary and Notes13:40 Thank YouFurther Viewing:Bisection Method youtu.be/MlP_W-obuNgSecant Method youtu.be/_MfjXOLUnywNewton-Bisection Hybrid youtu.be/FD3BPTMGJdsReference Links:Cleve’s Corner MATLAB fzero blogs.mathworks.com/cleve/2015/10/12/zeroin-part-1-dekkers-algorithmDekker’s paper dl.acm.org/citation.cfm?id=355659Brent’s paper academic.oup.com/comjnl/article/14/4/422/325237Knuth’s paper dl.acm.org/citation.cfm?doid=361532.361538Cleve’s Corner George Forsythe blogs.mathworks.com/cleve/2013/01/07/george-forsytheBrent's Original Code for zeroin.f can be found here http://www.netlib.org/goThank you Adrian and Les for helping and Micheal for the suggestion.#BrentsMethod #NumericalAnalysis
Newtons Method Interval of Convergence Oscar Veliz 2018-05-08 | How to find the Interval of Convergence for Newton-type methods such as Newton's Method, Secant Method, and Finite Difference Method including discussion on Damped Newton's Method and widening the convergence interval. Example code in R hosted on Github: github.com/osveliz/numerical-velizChapters0:00 Intro0:08 Methods with Guaranteed Convergence0:26 Newton-type Methods0:42 Convergence vs Divergence Example1:02 Example Visualized1:31 Convergence Interval Visual2:02 Finding Convergence Interval2:20 Converge Interval Numerical Example3:25 Widening the Interval3:55 Widened Interval Visualized4:31 Summary and Notes5:14 Thank YouFurther Viewing:Newton's Method youtu.be/E24zUEKqgwQNewton Bisection Hybrid youtu.be/FD3BPTMGJdsNewton Fractal youtu.be/MWD2A0Vg2V0Halley's Method youtu.be/3WiVGSy_084Householder's Method youtu.be/F9DFewL0mhoGeneralized Newton's Method youtu.be/p0SBubUfwiI#NewtonsMethod #NumericalAnalysis
Mullers Method Oscar Veliz 2018-04-16 | Muller's Method for finding roots including simple examples, discussion of order, and biography of David Eugene Muller. Example code in Python hosted on GitHub: github.com/osveliz/numerical-velizChapters0:00 Intro0:12 David Muller Bio0:43 Muller's Method History1:07 Secant Method with a Parabola1:38 Visualized Parabola1:47 Creating a Quadratic2:09 Finding X42:49 Putting It All Together3:08 Muller's Method3:30 Muller's Method Examples4:15 Order4:47 Notes and Summary5:04 Special Thanks5:15 Thank YouReferences:Original Paper: http://www.jstor.org/stable/2001916ILLIAC I: https://music.illinois.edu/ems-history-illiac-iWolfram: http://mathworld.wolfram.com/MullersMethod.html#MullersMethod #NumericalAnalysis
False Position Method - Regula Falsi Oscar Veliz 2018-03-29 | False Position Method (Regula Falsi) for finding roots of functions. Includes comparison against Bisection and discussion of order. Sample code in C available on GitHub github.com/osveliz/numerical-velizChapters0:00 Intro0:21 Regula Falsi Family Tree0:33 False Position Method1:01 Bisection Visualized1:10 False Position Visualized1:27 Computing c1:45 You have c now what?2:10 Bisection vs False Position Examples2:52 A closer look3:18 Notes and Summary3:46 Thank YouFurther Viewing:Bisection Method youtu.be/MlP_W-obuNgNewton-Bisection Hybrid youtu.be/FD3BPTMGJds#FalsePositionMethod #RegulaFalsi #NumericalAnalysis
Finite Difference Method Oscar Veliz 2012-12-12 | Finite Difference Method for finding roots of functions including an example and visual representation. Also includes discussions of Forward, Backward, and Central Finite Difference as well as overview of higher order versions of Finite Difference.Chapters0:00 Intro0:04 Secant Method Recap0:38 Finite Difference Method Motivation1:03 Finite Difference Method Visualized1:37 Example2:00 Versions of Finite Difference2:54 Higher Orders3:31 Thanks For WatchingFurther Viewing:Newton's Method youtu.be/E24zUEKqgwQNewton's Method Interval of Convergence youtu.be/zyXRo8Qjj0ASecant Method youtu.be/_MfjXOLUnywFinite Difference Method for Nonlinear Systems youtu.be/G25sGOWkOuQ#FiniteDifferenceMethod #NumericalAnalysis
Cubic Splines Oscar Veliz 2011-04-24 | Function approximation using Cubic Splines and Natural Cubic Splines including discussion about figuring out if two sets of equations are splines. Important note: around 1:10 the functions also need to go through the points at the endsax1^3 + bx1^2 + cx1 + d = y1ex3^3 + fx3^2 + gx3 + h = y3A video covering this correction can be found here youtu.be/4jw0cjddmB8Chapters0:00 Intro0:05 Ways to Approximate a Function0:23 Splines1:06 Calculating Cubic Splines1:40 Example 12:26 Example 23:24 Thanks For WatchingFurther Viewing:Lagrange Polynomials youtu.be/GtJKUIG9KXI#CubicSpline #NumericalAnalysis
Lagrange Polynomials Oscar Veliz 2011-04-10 | Lagrange Polynomials for function approximation including simple examples.Chapters0:00 Intro0:08 Lagrange Polynomials0:51 Visualizing L21:00 Numeric Example1:11 Example Visualized1:27 Why Lagrange Works1:47 Lagrange Accuracy2:12 Error2:59 Error Visualized3:20 Error Bounds4:08 Notes4:25 Thanks For WatchingFurther Viewing:Inverse Quadratic Interpolation (part of Brent's Method) youtu.be/-bLSRiokgFkMuller's Method youtu.be/XIIEjwtkONcCubic Spline youtu.be/f4iNbNRKZKU#LagrangePolynomials #NumericalAnalysis
Fixed Point Iteration Oscar Veliz 2011-03-27 | 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 Δ² youtu.be/BTYTj0r5PZE and my video on Wegstein's Method youtu.be/T_6mR6rJXQQHow can I force Fixed Point Iteration to converge?There is a very simple change you can make to induce convergence called Wegstein's Method youtu.be/T_6mR6rJXQQCan you make a video that answers these questions?Absolutely check out Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2oChapters0:00 Intro0:06 Fixed Point Iteration0:39 Fixed Point Iteration Example2:12 Convergence Test2:41 Convergence Test Example3:18 Order4:03 Thanks For WatchingFurther Viewing:Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2oSteffensen's Method with Aitken's Δ² youtu.be/BTYTj0r5PZEWegstein's Method youtu.be/T_6mR6rJXQQFixed Point Iteration Systems of Equations youtu.be/xa2vUsYJD-cGeneralized Aitken-Steffensen Method youtu.be/-x9_fSNrX3w#FixedPointIteration #NumericalAnalysis
Secant Method Oscar Veliz 2011-03-21 | Secant Method for finding roots of functions including examples and discussion about the order.Chapters0:00 Intro0:11 Drawback of Newton's Method1:05 Secant Method Visualized1:53 Secant Method Example2:42 Order3:05 Order Discussion3:48 Thanks For WatchingFurther Viewing:False Position Method youtu.be/pg1I8AG59IkBrent-Dekker Method youtu.be/-bLSRiokgFkSecant Method for Systems of Nonlinear Equations youtu.be/p2OPlnHJPNI#SecantMethod #NumericalAnalysis
Newtons Method Oscar Veliz 2011-03-20 | Newton's Method for finding roots of functions including finding a square root example and discussion of the order (newton's method is also known as Newton-Raphson method). Small correction around 2:26 the sign is incorrect it should be x_(n+1) = (1/2)(x_n + a/x_n). A video covering this mistake can be found here youtu.be/4jw0cjddmB8Chapters0:00 Intro0:12 Newton's Method0:53 Newton's Method Visualized1:47 Finding Square Root (see correction)2:30 Example3:43 Order4:26 Thanks For WatchingFurther Viewing:Newton's Method Interval of Convergence youtu.be/zyXRo8Qjj0ANewton-Bisection Hybrid youtu.be/FD3BPTMGJdsNewton Fractal youtu.be/OLqdJMjzib8Steffensen's Method youtu.be/BTYTj0r5PZESecant Method youtu.be/_MfjXOLUnywHalley's Method youtu.be/3WiVGSy_084Generalized Newton's Method youtu.be/p0SBubUfwiI#NewtonsMethod
Bisection Method Oscar Veliz 2011-03-18 | Bisection Method for finding roots of functions including simple examples and an explanation of the order.Chapters0:00 Intro0:14 Bisection Method1:06 Visual Example1:49 Difficult Functions2:14 Order3:16 Finding Order Example3:38 Maximum Number of Iterations4:28 Thanks For WatchingFurther Viewing:False Position Method: youtu.be/pg1I8AG59IkBrent-Dekker Method: youtu.be/-bLSRiokgFkNewton-Bisection Hybrid: youtu.be/FD3BPTMGJds#BisectionMethod #NumericalAnalysis
