Generalized Bisection Method for Systems of Nonlinear Equations @OscarVeliz

Oscar Veliz 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 Intro
0:10 Literature
0:47 Bisection Shapes
1:12 Harvey-Stenger
1:29 2D Bisection Setup
2:44 Triangle Point L-Test
3:00 Triangle Point Area-Test
4:24 Picking a Triangle
4:52 Stopping Criteria
5:07 2D Bisection Visualized
5:56 Generalized Bisection Algorithm
7:02 Picking Starting Points
7:38 Harvey-Stenger Algorithm
8:20 Hybrid?
8:50 Oscar's Notes
9:30 Outro

Recommended Viewing:
Bisection Method youtu.be/MlP_W-obuNg
Generalized Secant Method youtu.be/p2OPlnHJPNI
Generalized False Position Method and Alternative Secant Methods youtu.be/c2kSfJ8of7E
Generalized Newton's Method youtu.be/p0SBubUfwiI
Brent's Method youtu.be/-bLSRiokgFk
Newton-Bisection Hybrid youtu.be/FD3BPTMGJds

Reference 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.214384

Background music "Drifting at 432 Hz" by @UnicornHeads

#NumericalAnalysis #BisectionMethod #NonlinearSystem

updated 4 years ago

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 Intro
0:10 Literature
0:47 Bisection Shapes
1:12 Harvey-Stenger
1:29 2D Bisection Setup
2:44 Triangle Point L-Test
3:00 Triangle Point Area-Test
4:24 Picking a Triangle
4:52 Stopping Criteria
5:07 2D Bisection Visualized
5:56 Generalized Bisection Algorithm
7:02 Picking Starting Points
7:38 Harvey-Stenger Algorithm
8:20 Hybrid?
8:50 Oscar's Notes
9:30 Outro

Recommended Viewing:
Bisection Method youtu.be/MlP_W-obuNg
Generalized Secant Method youtu.be/p2OPlnHJPNI
Generalized False Position Method and Alternative Secant Methods youtu.be/c2kSfJ8of7E
Generalized Newton's Method youtu.be/p0SBubUfwiI
Brent's Method youtu.be/-bLSRiokgFk
Newton-Bisection Hybrid youtu.be/FD3BPTMGJds

Reference 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.214384

Background music "Drifting at 432 Hz" by @UnicornHeads

#NumericalAnalysis #BisectionMethod #NonlinearSystem

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-veliz

Chapters:
00:00 Intro
00:36 Factoring with monomial
01:13 Factoring with quadratic
01:40 Synthetic Division 1 variable
02:16 Synthetic Division 2 variables
03:22 Solving for roots
03:50 Different u and v
04:24 Describing Notation
05:22 Solving Nonlinear System
07:01 Another Synthetic Division
07:45 Updating u & v
08:27 Bairstow Iteration Example
08:56 Bairstow Iteration Example 2
09:22 Note on Quadratic Equation
09:42 Bairstow Full Algorithm
10:51 Complex Roots Example
11:33 Bairstow Fractals
12:23 Picking u & v
12:46 Henrici Starting Values
13:08 Bairstow's Original Problem
14:40 Oscar's Notes
15:24 Outro

Recommended Viewing:
Horner's Method youtu.be/zEvfkSuPqWk
Graeffe's Method youtu.be/92oh5gYUP7Y
Generalized Newton's Method youtu.be/p0SBubUfwiI

Reference 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-5

Background 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-Lobachevskiĭ 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-veliz

Chapters:
00:00 Intro
00:45 History
01:10 Expanding & Reversing
02:21 Bracket Notation
03:53 Bracket Example
04:16 Solving for a
05:46 Solving for b
06:11 Solving for c
06:30 How does this help???
06:55 Root Squaring Example
07:56 Repeated Root Squaring
08:36 Stopping Criteria
08:58 On Programming Graeffe's Method
09:30 Further Reading
09:52 Oscar's Notes
10:33 Outro

Recommended Viewing:
Horner's Method youtu.be/zEvfkSuPqWk
Bairstow's Method youtu.be/iUGEk6kngFw
Durand-Kerner youtu.be/5JcpOj2KtWc
Aberth-Ehrlich youtu.be/XIzCzfMDSzk

Reference links:
Graeffe's Version https://publikationsserver.tu-braunschweig.de/receive/dbbs_mods_00051359
Dandelin's Version eudml.org/doc/180464
Lobachevskiĭ's Version catalog.lindahall.org/permalink/01LINDAHALL_INST/19lda7s/alma999251234705961
Householder's Article doi.org/10.2307/2310626
Brodetsky and Smeal 1924 doi.org/10.1017/S0305004100002802
Whittaker 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=false
Best's Paper doi.org/10.2307/2306166

Background music "Drifting at 432 Hz" by @UnicornHeads

#NumericalAnalysis #rootfinding #polynomials

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-veliz

Chapters:
0:00 Scaffolding
0:25 Korganoff
1:02 Robinson
1:32 Some History
1:50 Robinson Continued
2:51 Robinson versus Secant
3:27 Nonlinear System Example
4:16 On Notation
4:37 Efficient Orthogonal Matrix
4:53 Generalized False Position Method
5:18 Oscar's Notes
8:38 Outro

Recommended Viewing:
Secant Method youtu.be/_MfjXOLUnyw
Generalized Secant Method youtu.be/p2OPlnHJPNI
Broyden's Method youtu.be/UlLGzW-KjHs
Generalized Steffensen's Method youtu.be/ndf2vjXjXzQ
Generalized Finite Difference Method youtu.be/G25sGOWkOuQ
False Position Method youtu.be/pg1I8AG59Ik

Reference 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/0703057

Background 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-veliz

Chapters:
0:00 Intro
0:30 Literature
1:03 Damped Newton Method
2:28 Armijo's Approach
2:57 Global Newton Method Algorithm
3:50 Numeric Example
4:17 Global Newton Fractals - Single Variable
5:30 On Extra Function Calls
6:11 Nonlinear System Example
6:55 Global Newton Fractals - Nonlinear System
8:11 Oscar's Notes
8:38 Outro

Recommended Viewing:
Newton's Method youtu.be/E24zUEKqgwQ
Newton's Method of Convergence youtu.be/zyXRo8Qjj0A
Newton Bisection Hybrid youtu.be/FD3BPTMGJds
Newton Fractals youtu.be/MWD2A0Vg2V0
Newton's Method for Systems of Nonlinear Equations youtu.be/p0SBubUfwiI

Reference 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%3Aiterativemethods0000trau

Background 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-veliz

Chapters:
0:00 Wikipedia
0:44 Intro
0:54 Recommended Viewing
1:04 Recap
1:42 Generalized Halley's Method
2:55 Nonlinear System Example
3:21 Order
3:45 Method of Tangent Hyperbolas
4:10 Side-by-side
4:36 Higher Order
4:54 Oscar's Notes
5:15 Outro

Recommended Viewing:
Newton's Method youtu.be/E24zUEKqgwQ
Halley's Method youtu.be/3WiVGSy_084
Generalized Newton's Method youtu.be/p0SBubUfwiI
Broyden's Method youtu.be/UlLGzW-KjHs

Reference links:
Newton's Method Wikipedia - en.wikipedia.org/wiki/Newton%27s_method
Halley'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=UEFRfUZBpUEC

Background 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-veliz

Chapters:
0:00 Intro
0:22 Newton's Method According to Broyden
1:08 Nonlinear System Example
1:18 Newton's Method Example
1:28 Analyzing Newton's Behavior
2:07 Solving for J
2:51 Broyden's Approach
3:25 Almost Broyden's Method
4:13 Solving for the Inverse
4:46 Broyden's "Good" Method
5:11 More Options
5:35 Broyden's "Bad" Method
6:07 Generalizing Root-Finding
6:32 The Case for Secant Method
6:52 The Case for Newton's Method
7:17 Broyden's Take
8:11 The question of Order
8:31 Oscar's Notes
9:03 Outro

Recommended Viewing:
Newton's Method for Systems of Nonlinear Equations youtu.be/p0SBubUfwiI
Secant Method for Systems of Nonlinear Equations youtu.be/p2OPlnHJPNI
Fixed Point Iteration for Systems of Nonlinear Equations youtu.be/G25sGOWkOuQ
Global Newton Method youtu.be/BGZfHxzZ-7c

Reference 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/2236561

Background 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-veliz

Chapters
0:00 Intro
0:13 Prerequisites
0:32 Refresher
0:43 What is the Jacobian?
2:06 Approximating the Jacobian
3:00 Finite Differences
3:21 Note on Notation
4:23 Visualization
6:17 Improving Accuracy
6:42 Note on Notation 2
7:45 Oscar's Notes
8:24 Mathemaniac
8:34 Thank You

Recommended Viewing
Finite Difference Method youtu.be/zvrTirWMzB8
Newton's Method for Systems of Nonlinear Equations youtu.be/m_nfoUz-PNY
Generalized Steffensen's Method youtu.be/ndf2vjXjXzQ
Generalized Secant Method youtu.be/p2OPlnHJPNI
"What is Jacobian?" by @mathemaniac youtu.be/wCZ1VEmVjVo
Broyden's Method youtu.be/UlLGzW-KjHs

Background 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-veliz

Chapters
0:00 Prerequisites
0:20 Intro
0:40 Traub
1:24 Soleymani et al
1:58 Explaining Notation
2:32 1D Example
3:06 Two Methods - Same Method
3:20 System of Equations
3:27 Nonlinear System Example
4:42 Closer = Better ~J
5:03 Oscar's Notes
5:46 Thank You

Recommended Viewing
Steffensen's Method with Aitken's Δ² youtu.be/BTYTj0r5PZE
Generalized Aitken-Steffensen youtu.be/-x9_fSNrX3w
Newton's Method for Systems of Nonlinear Equations youtu.be/m_nfoUz-PNY
Generalized Finite Difference Method youtu.be/G25sGOWkOuQ
Broyden's Method youtu.be/UlLGzW-KjHs

References
"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/705375

Background 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-veliz

Chapters
0:00 Intro
0:15 Prerequisites
0:25 Secant Method Recap
0:45 Literature
1:00 Secant Method Alternative
2:12 Two Methods - Same Method
2:27 Nonlinear System + Example
2:49 Generalized Secant Method Visualized
4:12 Numeric Example
4:28 Order!
4:50 "A Class of Secant Methods"
5:31 Oscar's Notes
6:05 Thank You

Recommended Viewing
Secant Method youtu.be/_MfjXOLUnyw
Newton's Method for Systems of Nonlinear Equations youtu.be/m_nfoUz-PNY
Broyden's Method youtu.be/UlLGzW-KjHs
Generalized False Position & Alternative Secant Methods youtu.be/c2kSfJ8of7E

References
"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_7

Background 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-veliz

Chapters
0:00 Intro
0:12 Prerequisites
0:32 Background
0:58 Setup
1:54 Jacobian
2:55 Historical Context
5:11 Newton's Method Example Step-by-Step
6:57 End Condition
7:12 Numerical Example in Table
7:33 Newton's Method with Backslash
7:53 Newton's Method with Inverse Jacobian
8:16 MATLAB / GNU Octave
9:01 Newton Fractals
10:51 3D Fractal
11:37 Historical Optimization Newton's Method
12:18 Oscar's Notes
12:59 Thank You

Recommended Viewing:
Newton's Method youtu.be/E24zUEKqgwQ
Newton Fractals youtu.be/MWD2A0Vg2V0
Newton-Bisection Hybrid youtu.be/FD3BPTMGJds
Video Mistakes youtu.be/4jw0cjddmB8
Fixed Point Iteration Systems of Equations youtu.be/xa2vUsYJD-c
Generalized Aitken-Steffensen Method youtu.be/-x9_fSNrX3w
Secant Method for Systems of Nonlinear Equations youtu.be/p2OPlnHJPNI
Generalized Finite Difference youtu.be/G25sGOWkOuQ
Broyden's Method youtu.be/UlLGzW-KjHs
Global Newton Method youtu.be/BGZfHxzZ-7c

@3blue1brown 's series on @khanacademy:
Jacobian Prerequisite youtube.com/watch?v=VmfTXVG9S0U
The Jacobian Matrix youtube.com/watch?v=bohL918kXQk
Computing a Jacobian Matrix youtube.com/watch?v=CGbBbH1e7Yw
Local Linearity for a Multivariable Function youtube.com/watch?v=Vnga_psnCAo

References:
"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=GGZbUevBqskC

Background 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-veliz

Chapters
0:00 Intro
0:11 Taylor Series Origin youtu.be/KJYauVgXA4E
0:44 Ternary Search youtu.be/7h86n97naH4
0:54 Dichotomous Search youtu.be/n_zefNBfhSM
1:04 Fixed Point Iteration System of Equations with Banach youtu.be/xa2vUsYJD-c
1:19 Wegstein's Method youtu.be/T_6mR6rJXQQ
1:58 Outro

Check 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-veliz

Chapters:
0:00 Intro
0:16 Scaffolding
0:31 Motivation
1:17 Parabolic Interpolation Review
1:48 Renaming Variables
2:40 Brent's Method Algorithm
3:19 SPI Behaving?
4:08 Note on Updating
4:38 Brent's Method Visualization
6:02 Numerical Example
6:29 Note on Steps
6:43 MATLAB fminbnd
7:12 Minimum Strategy - Derivative
7:49 Note on Convergence Order
8:04 Oscar's Notes
8:39 Outro

Suggested Viewing:
Golden-section Search youtu.be/wpGN2xus75w
Successive Parabolic Interpolation - Jarratt's Method youtu.be/3WHcQofG7B8
Minimization Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-x
Brent-Dekker Method youtu.be/-bLSRiokgFk

References:
Brent's Book https://maths-people.anu.edu.au/~brent/pub/pub011.html
MATLAB fminbnd documentation mathworks.com/help/matlab/ref/fminbnd.html
SciPy documentation docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize_scalar.html
GNU Octave fminbnd documentation octave.org/doc/v4.0.1/Minimizers.html

Background 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-veliz

Chapters:
0:00 Intro
0:21 Scaffolding
0:42 Richard P. Brent
1:01 An Iterative Method for Locating Turning Points
1:33 Graphing
1:46 Create a Quadratic
1:58 Finding the Next Point
2:35 The Next Iteration
2:22 Derivative is Zero
2:56 Avoid Calculating L_2
3:32 Jarratt's Method
3:47 Example
4:10 Fractal Scaffolding
4:20 Complex Plane Discussion
5:47 Jarratt Fractal z^4/4 - z
6:33 Jarratt Fractal -cos(z)
6:55 Jarratt Fractal z^9/9 + 3z^5 - 16z
7:52 Jarratt's Notes
8:32 Oscar's Notes
9:00 Thank You

Suggested Viewing:
Ternary Search youtu.be/7h86n97naH4
Lagrange Polynomials youtu.be/GtJKUIG9KXI
Muller's Method youtu.be/XIIEjwtkONc
Inverse Quadratic Interpolation youtu.be/-bLSRiokgFk
Brent's Minimization Method youtu.be/BQm7uTYC0sg

References:
Jarratt's paper doi.org/10.1093/comjnl/10.1.82
Brent's Book https://maths-people.anu.edu.au/~brent/pub/pub011.html

Background 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-veliz

Chapters:
0:00 Intro
0:18 Scaffolding
1:03 Gregory-Leibniz Series
1:36 Numerical Iterations
2:24 Finding n Setup
3:09 Finding n Bad Example
3:34 Finding n Good Example
4:43 Oscar's Notes
5:17 Thank You

Recommend Viewing:
Machin-like Formula youtu.be/M_fTdDx8IlY
What is Order of Convergence youtu.be/JTinepDn1dI

Thank 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-veliz

Chapters
0:00 Intro
0:23 Algorithms for Minimization without Derivatives
0:43 Optimum Seeking Methods
1:34 Ternary Recap
2:04 Reusing Points
2:22 Finding c
2:45 Fixed Constant Ratio
3:28 Computing c
3:58 Golden-section Search Algorithm
4:47 GSS Visualized
5:31 Numerical Example
5:55 Comparing Methods
6:18 Search Space Shrinkage
7:01 Golden Ratio Extra History
7:28 Properties of φ
8:13 Oscar's Notes
8:38 Mathemaniac
8:49 Thank You

Suggested Viewing:
Ternary Search youtu.be/7h86n97naH4
Dichotomous Search youtu.be/n_zefNBfhSM
Fibonacci Search youtu.be/GAafWFRGP7k
Jarratt's Method - Successive Parabolic Interpolation youtu.be/3WHcQofG7B8
Brent's Minimization Method youtu.be/BQm7uTYC0sg
Minimization Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-x
Two opposite games involving golden ratio (ft. Tom Rocks Maths) by @mathemaniac youtu.be/UOAylfclg14

References:
Algorithms for Minimization without Derivatives by Richard P. Brent https://maths-people.anu.edu.au/~brent/pub/pub011.html
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

Background 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-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 www.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

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/YEUbzqkJBf0

Chapters
0:00 Intro
0:19 Ternary Recap
0:32 Moving Test Points
0:59 Computing c and d
1:19 A Tale of Halving
1:40 Optimum Seeking Methods
2:17 End Condition
3:04 Dichotomous Search Algorithm
3:50 Numerical Example
4:03 Oscar's Notes
4:36 Thank You

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

Reference:
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/YEUbzqkJBf0

Chapters
0:00 Intro
0:23 Minimum Finding
0:42 Derivative Plot
1:01 Minimum Strategy: Derivative
1:32 Unimodal
2:24 Unimodal Examples
2:35 Not Unimodal Examples
2:48 Maximum Finding?
3:11 Splitting into Intervals
4:26 Minimum Strategy: Intervals
5:09 Ternary Search Algorithm
5:58 Ternary Search Visualized
6:32 Numerical Example
7:03 Optimization 1 - Test Ends
7:39 Optimization 2 - Check Equal
7:56 Discussion
8:28 Oscar's Notes
9:04 Thank You

Suggested Viewing:
Bisection Method youtu.be/MlP_W-obuNg
Dichotomous Search youtu.be/n_zefNBfhSM
Fibonacci Search youtu.be/GAafWFRGP7k
Golden-section Search youtu.be/wpGN2xus75w
Jarratt's Method - Successive Parabolic Interpolation youtu.be/3WHcQofG7B8
Minimum Finding Playlist youtube.com/playlist?list=PLb0Tx2oJWuYIXLHAjQgko2fZtJ_NxnV-x

Reference:
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/series

Chapters
00:00 - Intro
00:11 - Taylor Series
00:20 - Unit Circle & Solve for π
00:57 - Gregory
01:07 - Gregory-Leibniz Series
01:33 - Leibniz
02:27 - arctan(1)
02:48 - Moving a
03:40 - Increasing n
04:11 - Getting Close
04:44 - Nearer to zero
05:07 - Adding arctangents example
05:28 - Arctangent Trick
05:51 - Euler
06:06 - Euler's Equation for π
06:26 - Deriving Euler's Equation
07:00 - Machin intro
07:15 - Machin-like formula
08:00 - John Machin
08:22 - Demo Code & Story Time
09:40 - 10,000 digits of π
10:08 - Beckmann's thoughts on higher digits
10:27 - Oscar's Notes
11:00 - Thank You

Suggested Viewing:
Origin of Taylor Series - youtu.be/KJYauVgXA4E
Newton Fractals - youtu.be/MWD2A0Vg2V0

Reference 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+pi
Leibniz'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+more
Euler'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=eZPRxQEACAAJ
CLISP 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.

Chapters
00:00 Intro
00:20 Solving Cube Roots
00:53 de Lagny's Conditions
01:26 Halley's Equations
03:46 Taylor's Letter
04:04 Taylor's Treatise
04:25 Two Mathematical Camps
04:51 Quotes About Taylor
05:29 Methodus
06:34 Going Back in Time
06:47 James Gregory
07:13 Gregory's Letter
07:47 Gregory's Other Series
08:32 Certain Mathematical Achievements
08:59 Taylor Series
09:31 Taylor Series Example
10:27 Colin Maclaurin
11:10 Nilakantha and Madhava
11:28 Oscar's Notes
11: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/YEUbzqkJBf0

Suggested Videos:
Halley's Method youtu.be/3WiVGSy_084
Video Mistakes and How to Fix Them youtu.be/4jw0cjddmB8
Computing π: Machin-like formula youtu.be/M_fTdDx8IlY

References:
Methodus archive.org/details/UFIE003454_TO0324_PNI-2529_000000/page/6/mode/2up
Methodus (english) http://www.17centurymaths.com/contents/taylorscontents.html
An account of methodus royalsocietypublishing.org/doi/10.1098/rstl.1714.0039
A Treatise of Fluxions books.google.com/books?id=NUw7AQAAIAAJ&vq
Halley's Method biodiversitylibrary.org/page/23266907#page/660/mode/1up
Thomas Fantet de Lagny (French) https://nubis.univ-paris1.fr/ark%3A/15733/3415#?c=&m=&s=&cv=&xywh=-56%2C-26%2C1895%2C2570
Brook Taylor and the method of increments link.springer.com/article/10.1007/BF00329903
Certain Mathematical Achievements of James Gregory tandfonline.com/doi/abs/10.1080/00029890.1943.11991343
Colin Maclaurin tandfonline.com/doi/abs/10.1080/00029890.1947.11991846
The Discovery of the Series Formula for π byLeibniz, Gregory and Nilakantha tandfonline.com/doi/pdf/10.1080/0025570X.1990.11977541
James 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-veliz

Become a GitHub Sponsor github.com/sponsors/osveliz

Chapters
00:00 - Intro
00:19 - Order Montage
00:54 - Error Definition
01:11 - Introduction of α
01:35 - α equation
01:41 - α example 1 Bisection
02:09 - Solving for M
02:36 - α example 2 False Position
03:13 - α example 3 Newton
03:41 - On Function Calls
04:19 - α with iterations and runtime
05:02 - Note on previous example
05:23 - Generalized operation count
06:28 - How fast is linear?
07:29 - How fast is quadratic?
09:33 - Digits of accuracy
10:15 - Distance impacts α
10:52 - Big O brief intro
11:37 - Big O of Bisection
12:09 - Big O of Newton and Halley
13:02 - Oscar's Notes
13:47 - Thank You

The 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-veliz

Chapters
0:00 Intro
0:11 Newton's Method youtu.be/E24zUEKqgwQ
0:48 Newton Fractals youtu.be/MWD2A0Vg2V0
1:07 Newton-Bisection Hybrid youtu.be/FD3BPTMGJds
1:58 Halley's Method youtu.be/3WiVGSy_084
3:00 Cubic Splines youtu.be/f4iNbNRKZKU

Check 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=1
GitHub Repository: http://github.com/osveliz/numerical-veliz
Topic Request: github.com/osveliz/numerical-veliz/issues
GitHub Sponsor: github.com/sponsors/osveliz
Community 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-veliz

Chapters
0:00 Intro
0:25 Derivation
1:58 History
2:34 Householder's Method
4:07 Householder's Method Example
4:41 Higher Order Householder's Method Examples
5:30 Principles of Numerical Analysis
6:03 Householder Fractals
8:10 Summary
8:41 Thank You

Suggested Videos:
Newton's Method youtu.be/E24zUEKqgwQ
Newton's Method Convergence Interval youtu.be/zyXRo8Qjj0A
Newton Fractals youtu.be/MWD2A0Vg2V0
Halley's Method youtu.be/3WiVGSy_084
Newton-Bisection Hybrid youtu.be/FD3BPTMGJds

Reference:
Householder's book archive.org/details/principlesofnume030218mbp/page/n143
Petković'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-veliz

Chapters
00:00 Intro
00:36 History
03:48 Derivation Setup
05:20 Derivation Tangent Hyperbolas
06:00 Derivation Taylor Series
07:21 Example
07:53 Example 2 (see correction)
08:24 Newton versus Halley
08:45 Example 3
09:29 Halley Fractals
11:27 Summary
11:52 Thank You

Corrections: 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/E24zUEKqgwQ
Newton Convergence Interval youtu.be/zyXRo8Qjj0A
Newton Fractal youtu.be/MWD2A0Vg2V0
Laguerre's Method youtu.be/blOARV4lnIM
Householder's Method youtu.be/F9DFewL0mho

Reference 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=book

Song: "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-veliz

Chapters
00:00 Intro
00:20 Sources
00:44 Derivation
03:08 Laguerre's Method
03:52 K. A. Redish
04:13 Visuzliation
05:24 Forman S. Acton
06:05 Example
07:04 Example 2
07:43 Example 3
08:01 Convergence
8:35 Laguerre Fractal
10:05 Summary
10:34 Thank You

Further Viewing:
Newton's Method youtu.be/E24zUEKqgwQ
Horner's Method youtu.be/zEvfkSuPqWk
Newton Fractals youtu.be/MWD2A0Vg2V0
Aberth-Ehrlich Method youtu.be/XIzCzfMDSzk
Halley's Method and Fractal youtu.be/3WiVGSy_084
Householder's Method and Fractal youtu.be/F9DFewL0mho
Bairstow's Method youtu.be/iUGEk6kngFw

Reference 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-veliz

Chapters
0:00 Intro
0:19 History
0:41 Methodology
0:59 Starting Points
1:11 Starting Points Visualized
1:33 Newton Fractal
2:22 A Modified Newton Method
2:35 Ehrlich's Derivation
4:43 Example
5:09 Durand-Kerner versus Aberth-Ehrlich
6:22 Behavior of Aberth-Ehrlich
6:33 Notes on Aberth-Ehrlich
7:01 Thank You

Further viewing:
Durand-Kerner youtu.be/5JcpOj2KtWc
Laguerre's Method youtu.be/blOARV4lnIM
Newton Fractals youtu.be/MWD2A0Vg2V0
Bairstow's Method youtu.be/iUGEk6kngFw

References:
Aberth's paper ams.org/journals/mcom/1973-27-122/S0025-5718-1973-0329236-7
Ehrlich's paper dl.acm.org/citation.cfm?id=363115
Kerner link.springer.com/article/10.1007%2FBF02162564
Algorithm 283 dl.acm.org/citation.cfm?id=365527
Wilkinson dl.acm.org/citation.cfm?id=1096474
Maehly link.springer.com/article/10.1007/BF01600333
Bö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-veliz

Chapters
0:00 Intro
0:24 History
1:04 Methodology & Derivation
2:28 Example 1 real numbers
2:55 Example 2 need for complex numbers
3:19 Complex Roots
3:39 Complex Numbers Visualized
4:16 Example 2 with complex numbers
5:00 Formal Definition
5:28 Starting Points
6:14 Example 3 Visualized
6:57 Behavior of Durand-Kerner
7:33 Computational Order
7:54 Notes on Durand-Kerner
8:23 Thank You

Further Viewing:
Fixed Point Iteration Systems of Equations with Banach youtu.be/xa2vUsYJD-c
Horner's Method youtu.be/zEvfkSuPqWk
Aberth-Ehrlich youtu.be/XIzCzfMDSzk
Bairstow's Method youtu.be/iUGEk6kngFw

Primary Sources
Kerner's paper link.springer.com/article/10.1007%2FBF02162564
Durand, É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/004155536490148X
Weierstrass's paper http://bibliothek.bbaw.de/bibliothek-digital/digitalequellen/schriften/anzeige?band=10-sitz/1891-2&seite:int=00000565
Ehrlich's paper dl.acm.org/citation.cfm?id=363115
Aberth'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-veliz

Chapters
0:00 Intro
0:40 Motivation
2:32 Solve for X*
3:10 Generalized Aitken
3:44 Generalized Aitken Example
4:10 Generalized Aitken-Steffensen Method
4:40 Generalized Aitken-Steffensen Method Example 1
5:02 Generalized Aitken-Steffensen Method Example 2
5:26 Henrici
5:59 On Order & Proving Convergence
6:31 Proof Intuition
6:55 Notes
7:40 Thank You

Recommended Viewing:
Fixed Point Iteration youtu.be/OLqdJMjzib8
Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2o
Steffensen's Method with Aitken's Δ² youtu.be/BTYTj0r5PZE
Fixed Point Iteration Systems of Equations youtu.be/xa2vUsYJD-c
Generalized Newton's Method youtu.be/p0SBubUfwiI
Generalized Steffensen's Method youtu.be/ndf2vjXjXzQ

References:
Elements of Numerical Analysis by Peter Henrici archive.org/details/ElementsOfNumericalAnalysis/page/n65
Tatsuo 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/1195514312
Yves 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-veliz

Chapters:
00:00 Intro
00:25 Systems of Equations
00:33 Solving Nonlinear Systems
01:03 Fixed Point Iteration
01:26 Rewriting Equations
02:03 Example 1
02:23 Visualized Example
03:12 Measuring Distance and Norm
03:45 End Conditions
04:09 Different Combinations of Rewrites
04:45 When Does it Converge?
05:10 Banach Fixed Point Theorem
05:56 The Jacobian
06:48 Contraction Mapping Test
07:24 Contraction Mapping Test Examples
08:20 Notes on the Contraction Mapping Test
09:06 Order of Convergence
09:41 Exact Order
10:31 Summary
10:49 Thank You

See Video Mistakes II: The Sequel youtu.be/YEUbzqkJBf0 for a small correction.

Recommended Viewing:
Fixed Point Iteration youtu.be/OLqdJMjzib8
Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2o
Generalized Aitken-Steffensen youtu.be/-x9_fSNrX3w
Generalized Newton's Method youtu.be/p0SBubUfwiI

Reference 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-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 youtu.be/4jw0cjddmB8

Chapters
0:00 Intro
0:16 Convergence Interval Recap
0:42 Imaginary Numbers
1:05 Newton's 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:
Newton's Method youtu.be/E24zUEKqgwQ
Newton's Method Interval of Convergence youtu.be/zyXRo8Qjj0A
Newton Bisection Hybrid (Newt-Safe) youtu.be/FD3BPTMGJds
Laguerre's Method and Fractal youtu.be/blOARV4lnIM
Halley's Method and Fractal youtu.be/3WiVGSy_084
Generalized Newton's Method youtu.be/p0SBubUfwiI

Further 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-veliz

Chapters
0:00 Intro
0:26 Viewer Request
0:49 Numerical Recipes
1:12 Numerical Methods That Work
1:54 Motivation Examples
3:04 Problems with Newton Recap
3:17 Newt-Safe Basic Algorithm
4:00 Newt-Safe Basic Examples
4:53 Additional Conditions
5:39 ΔX Condition Explanation
6:33 ΔX Example
7:18 Newt-Safe without Interval
7:55 Other Hybrid Methods
8:33 Notes and Summary
8:57 Thank You

Correction: 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/4jw0cjddmB8

Further Viewing:
Bisection Method youtu.be/MlP_W-obuNg
Newton's Method youtu.be/E24zUEKqgwQ
Newton's Method Interval of Convergence youtu.be/zyXRo8Qjj0A
Newton Fractal youtu.be/MWD2A0Vg2V0
Halley's Method youtu.be/3WiVGSy_084
Householder's Method youtu.be/F9DFewL0mho

Reference Links:
Based of off NewtSafe from Marc Spiegelman https://www.ldeo.columbia.edu/~mspieg/e4300/BlankPDFs/Lecture06_blank.pdf
rtsafe 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.

Chapters
0:00 Intro
0: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 Convergence
5:04 Thank You

Suggested Videos
Fixed Point Iteration: youtu.be/OLqdJMjzib8
Steffensen's Method with Aitken's Δ²: youtu.be/BTYTj0r5PZE
Wegstein'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-veliz

Chapters
0:00 Intro
0:22 Wegstein's Method Sources
0:52 Wegstein's Methodology
1:56 Wegstein's Method Examples
3:24 Computing q
4:55 Computing q example
5:24 Updating q
5:43 Updating q example
6:03 Computational Order
6:36 Oscar's Notes
7:13 Thank You

See Video Mistakes II: The Sequel youtu.be/YEUbzqkJBf0 for a small error and correction.

Suggestions for further watching:
Fixed Point Iteration: youtu.be/OLqdJMjzib8
Steffensen's Method with Aitken's Δ²: youtu.be/BTYTj0r5PZE
Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2o

References:
Wegstein's original paper: dl.acm.org/citation.cfm?id=368871
Gutzler'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-veliz

Chapters
0:00 Title Card
0:12 Terminology
0:37 Eigenvalue Example
1:04 Power Method
1:29 Power Method Example
2:33 Notes on Power Method
2:50 Inverse Power Method
3:21 Inverse Power Method Example
4:12 Rayleigh Quotient
4:54 Solve using Determinant
5:15 Inverse Power Method with Shift
5:34 Inverse Power Method with Shift Example
6:12 Rayleigh Quotient Iteration
6:37 Summary
7: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-veliz

Chapters
0:00 Intro
0:11 - History
1:33 - TLDR
1:47 - Function vs Polynomial
2:23 - Horner's Method
2:50 - Horner's Method Examples
3:36 - Synthetic Division
4:32 - Ruffini's Rule Main Idea
4:58 - Ruffini's Rule
5:34 - Derivative with Ruffini's Rule
6:00 - Derivative Example
6:27 - Polynomial Root Finding
6:36 - Algebraic Root Finding
6:59 - Rational Root Theorem
7:35 - Newton-Horner Method
8:23 - Newton-Horner Example
9:11 - Summary
9:36 - Thank You

Further Viewing:
Newton's Method youtu.be/E24zUEKqgwQ
Laguerre's Method youtu.be/blOARV4lnIM
Newton Fractals youtu.be/MWD2A0Vg2V0
Durand-Kerner Method youtu.be/5JcpOj2KtWc
Aberth-Ehrlich Method youtu.be/XIzCzfMDSzk
Bairstow's Method youtu.be/iUGEk6kngFw

References:
Horner's paper jstor.org/stable/107508
Ruffini doi.org/10.1090/S0002-9904-1911-02072-9
Chemla's paper doi.org/10.1017/S0957423900001235
Qin Jiushao http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.454.4986&rep=rep1&type=pdf#page=169
Sharaf al-Dīn al-Tūsī doi.org/10.1016/0315-0860(89)90099-2
Jia Xian https://www.math.vt.edu/people/brown/doc/fibo_number.pdf
Yong'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-veliz

Chapters
0:00 Intro
0:08 Aitken's Δ² Method History
0:23 Derivation with Example
1:01 Aitken's Δ² Method
1:21 Solve for r
2:16 Δ² Notation
2:39 Aitken's Δ² Example
3:12 Steffensen's Method History
3:40 Steffensen's Methodology
4:05 Steffensen's Method Example
4:43 Steffensen's Method 2.0
4:55 One Method, Two Versions
6:30 Steffensen's Method 2.0 Continued
6:55 Order
7:26 Summary
8:02 Thank You

Further Watching:
Fixed Point Iteration youtu.be/OLqdJMjzib8
Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2o
Wegstein's Method youtu.be/T_6mR6rJXQQ
Fixed Point Iteration Nonlinear Systems youtu.be/xa2vUsYJD-c
Generalized Aitken-Steffensen youtu.be/-x9_fSNrX3w

Reference Links:
Aitken's paper: cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/xxvon-bernoullis-numerical-solution-of-algebraic-equations/64D4A7C56F1EFEC696AF68D7870DB451
Steffensen's paper: tandfonline.com/doi/abs/10.1080/03461238.1933.10419209
Kumar 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-veliz

Chapters
00:00 Intro
00:12 Secant Method Recap
00:37 Bisection Method Recap
00:54 Dekker's Method History
01:35 Dekker's Method Big Idea
01:50 Dekker's Method
02:28 Dekker's Method Visual Example
02:50 Dekker's Method Update Step
03:48 Dekker's Method Visual Example Continued
04:19 Dekker's Method Example
05:04 Tolerance
05:20 "Remarks on the Paper by Dekker"
05:58 George E. Forsythe
06:30 Brent's Method
06:59 Brent's Method Big Idea
07:19 Inverse Quadratic Interpolation
07:30 Create a Quadratic
07:50 Lagrange Polynomial
08:01 Inverse Quadratic
08:32 Inverse Quadratic Interpolation Methodology
08:54 Inverse Quadratic Simplified
09:23 Trouble with IQI
09:55 Brent's Method - Round 2
11:06 Ill Behaved Functions
11:58 Comparison
12:32 Computational Order
13:06 Summary and Notes
13:40 Thank You

Further Viewing:
Bisection Method youtu.be/MlP_W-obuNg
Secant Method youtu.be/_MfjXOLUnyw
Newton-Bisection Hybrid youtu.be/FD3BPTMGJds

Reference Links:
Cleve’s Corner MATLAB fzero blogs.mathworks.com/cleve/2015/10/12/zeroin-part-1-dekkers-algorithm
Dekker’s paper dl.acm.org/citation.cfm?id=355659
Brent’s paper academic.oup.com/comjnl/article/14/4/422/325237
Knuth’s paper dl.acm.org/citation.cfm?doid=361532.361538
Cleve’s Corner George Forsythe blogs.mathworks.com/cleve/2013/01/07/george-forsythe

Brent's Original Code for zeroin.f can be found here http://www.netlib.org/go

Thank 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-veliz

Chapters
0:00 Intro
0:08 Methods with Guaranteed Convergence
0:26 Newton-type Methods
0:42 Convergence vs Divergence Example
1:02 Example Visualized
1:31 Convergence Interval Visual
2:02 Finding Convergence Interval
2:20 Converge Interval Numerical Example
3:25 Widening the Interval
3:55 Widened Interval Visualized
4:31 Summary and Notes
5:14 Thank You

Further Viewing:
Newton's Method youtu.be/E24zUEKqgwQ
Newton Bisection Hybrid youtu.be/FD3BPTMGJds
Newton Fractal youtu.be/MWD2A0Vg2V0
Halley's Method youtu.be/3WiVGSy_084
Householder's Method youtu.be/F9DFewL0mho
Generalized 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-veliz

Chapters
0:00 Intro
0:12 David Muller Bio
0:43 Muller's Method History
1:07 Secant Method with a Parabola
1:38 Visualized Parabola
1:47 Creating a Quadratic
2:09 Finding X4
2:49 Putting It All Together
3:08 Muller's Method
3:30 Muller's Method Examples
4:15 Order
4:47 Notes and Summary
5:04 Special Thanks
5:15 Thank You

References:
Original Paper: http://www.jstor.org/stable/2001916
ILLIAC I: https://music.illinois.edu/ems-history-illiac-i
Wolfram: 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-veliz

Chapters
0:00 Intro
0:21 Regula Falsi Family Tree
0:33 False Position Method
1:01 Bisection Visualized
1:10 False Position Visualized
1:27 Computing c
1:45 You have c now what?
2:10 Bisection vs False Position Examples
2:52 A closer look
3:18 Notes and Summary
3:46 Thank You

Further Viewing:
Bisection Method youtu.be/MlP_W-obuNg
Newton-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.

Chapters
0:00 Intro
0:04 Secant Method Recap
0:38 Finite Difference Method Motivation
1:03 Finite Difference Method Visualized
1:37 Example
2:00 Versions of Finite Difference
2:54 Higher Orders
3:31 Thanks For Watching

Further Viewing:
Newton's Method youtu.be/E24zUEKqgwQ
Newton's Method Interval of Convergence youtu.be/zyXRo8Qjj0A
Secant Method youtu.be/_MfjXOLUnyw
Finite 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 ends
ax1^3 + bx1^2 + cx1 + d = y1
ex3^3 + fx3^2 + gx3 + h = y3
A video covering this correction can be found here youtu.be/4jw0cjddmB8

Chapters
0:00 Intro
0:05 Ways to Approximate a Function
0:23 Splines
1:06 Calculating Cubic Splines
1:40 Example 1
2:26 Example 2
3:24 Thanks For Watching

Further Viewing:
Lagrange Polynomials youtu.be/GtJKUIG9KXI

#CubicSpline #NumericalAnalysis

Lagrange Polynomials

Oscar Veliz 2011-04-10 | Lagrange Polynomials for function approximation including simple examples.

Chapters
0:00 Intro
0:08 Lagrange Polynomials
0:51 Visualizing L2
1:00 Numeric Example
1:11 Example Visualized
1:27 Why Lagrange Works
1:47 Lagrange Accuracy
2:12 Error
2:59 Error Visualized
3:20 Error Bounds
4:08 Notes
4:25 Thanks For Watching

Further Viewing:
Inverse Quadratic Interpolation (part of Brent's Method) youtu.be/-bLSRiokgFk
Muller's Method youtu.be/XIIEjwtkONc
Cubic 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_6mR6rJXQQ

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 youtu.be/T_6mR6rJXQQ

Can you make a video that answers these questions?
Absolutely check out Fixed Point Iteration Q&A youtu.be/FyCviw2ZA2o

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 youtu.be/FyCviw2ZA2o
Steffensen's Method with Aitken's Δ² youtu.be/BTYTj0r5PZE
Wegstein's Method youtu.be/T_6mR6rJXQQ
Fixed Point Iteration Systems of Equations youtu.be/xa2vUsYJD-c
Generalized 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.

Chapters
0:00 Intro
0:11 Drawback of Newton's Method
1:05 Secant Method Visualized
1:53 Secant Method Example
2:42 Order
3:05 Order Discussion
3:48 Thanks For Watching

Further Viewing:
False Position Method youtu.be/pg1I8AG59Ik
Brent-Dekker Method youtu.be/-bLSRiokgFk
Secant 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/4jw0cjddmB8

Chapters
0:00 Intro
0:12 Newton's Method
0:53 Newton's Method Visualized
1:47 Finding Square Root (see correction)
2:30 Example
3:43 Order
4:26 Thanks For Watching

Further Viewing:
Newton's Method Interval of Convergence youtu.be/zyXRo8Qjj0A
Newton-Bisection Hybrid youtu.be/FD3BPTMGJds
Newton Fractal youtu.be/OLqdJMjzib8
Steffensen's Method youtu.be/BTYTj0r5PZE
Secant Method youtu.be/_MfjXOLUnyw
Halley's Method youtu.be/3WiVGSy_084
Generalized 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.

Chapters
0:00 Intro
0:14 Bisection Method
1:06 Visual Example
1:49 Difficult Functions
2:14 Order
3:16 Finding Order Example
3:38 Maximum Number of Iterations
4:28 Thanks For Watching

Further Viewing:
False Position Method: youtu.be/pg1I8AG59Ik
Brent-Dekker Method: youtu.be/-bLSRiokgFk
Newton-Bisection Hybrid: youtu.be/FD3BPTMGJds

#BisectionMethod #NumericalAnalysis