Hello internet this is Oscar Veliz this time looking at generalized Newton's method for
solving systems of nonlinear equations go over the background and history as
well as some examples before finally showing how to make some cool fractals
i will assume that you already have some familiarity with newton's method
for finding the root of a single equation check out my videos if you haven't already
as optional viewing check out my videos on fixed point iteration for systems of equations
as well as generalized aiken-steffensen method
as a reminder when solving a system of equations it could be linear or non-linear this video will
focus on non-linear systems assuming you have as many equations as you do unknowns we'll use again
the example from my earlier videos using x squared minus y equal to one and x minus y squared equal
to negative one which has these four solutions our first step is to write it in terms of zero we'll
call this system F let's take the point one one and evaluate it at F giving results of negative
one one think of F as a transformation onto some input to give you some output the points we want
are these where when plugged into f give a transformation of zero
going back to this example from earlier if we make a small change to one one
going a little to the right in the x direction this gives us that transformation if we
instead change a little upwards in the y direction it gives us this transformation
what we would really like is a way to identify how a change in the input changes our output
for that we're going to need F' which requires taking partial derivatives of
every function in F against every variable in F don't worry if you're not too sure how
to do this i'll show you a trick later on in the video we usually call this
the Jacobian i've taken the liberty of doing the partial data is for you
we'll then want to evaluate it at one one giving the matrix two minus one one minus two
if we take our Jacobian i multiply it by our small delta of 0.1, 0 it gives us an output
of about 0.2, 0.1 what does that mean well if we plug that in to our change in the function
this addition is just about accurate the same is true about our change in y giving that answer
visualized looks something like this note this isn't exact that's because the larger your change
away from 1 1 the less accurate the Jacobian will be around those points
for more context let's look to "historical development of the newton-raphson method" by Ypma
and "Thomas Simpson and Newton's method of approximation and enduring myth"
by Kollerstrom both of whom cite "essays on several curious and useful subjects in
speculative and mixed mathematics by Thomas Simpson" Simpson describes "a new method for
the solution of equations in numbers when only one equation is given and the quantity x to be
determined take the fluxion of the equation be it what it will supposing x the unknown to be
the variable quantity having divided the whole by x dot let the quotient be represented by A
estimate the value of x pretty near the truth substituting the same in the equation
and also in the value of A and let the error or resulting number in the former be divided
by the numerical value A and the quotient be subtracted from the said former value of x
and from thence will arise a new value of that quantity much nearer to the truth than
the former wherewith proceeding as before another new value may be had
and so another etcetera till we arrive to any degree of accuracy desired"
what Simpson is describing here is Newton's method represented in model terms like this
Ypma writes "this is the first formulation of the iterative
method for general nonlinear equations based on the use of fluxional calculus
this significant contribution by Simpson received little recognition the formulation of
the method using the now familiar f' calculus notation was published by Lagrange in 1798"
but what does this have to do with solving systems for that we'll need to turn the page
Simpson describes "when there are two equations given and as many quantities x and y to be
determined" i'll spare you the details Ypma writes "Simpson here is describing the technique
now generally referred to as `Newton's method' for systems of nonlinear equations
restricted to the case of two such equations in modern terms x sub i plus 1 is equal to x
sub i minus d sub i where d is the solution of the system of linear equations this equation in
which f' is the Jacobian matrix of f evaluated at x sub i" let's use this knowledge on our example
let's use our equation for d setting up this linear system and plugging in one and one we
can then solve it using any linear system solver like Gauss-Jordan Simpson used Cramer's rule
this leaves us with the value of negative one negative one
note what d is telling us is what changed the input results in a change to the output
here if we added that negative one negative one to our input for f this doesn't help us a lot
but we can instead subtract it which should give us an output of around zero this is where we get
our equation of x sub n minus d sub n giving our new value for x n plus one as our example starting
with the point one one subtracting our value for d gives us an answer of two two plotted right there
this value x1 is indeed closer to our solution but when we plug it in to our function for f
the transformation isn't all that much closer
we can instead though repeat the process by plugging in 2 2 into our Jacobian
using again our equation for d plugging everything in gives us this linear system
which we solve using any linear system solver giving a value for d of one third one third
plug that into our equation for x and we get a new value of five thirds five thirds
plot it right there to give us our value for x2 plugging x2 into our equation for F gives
us a transformation of around zero we'll stop iterating once our norm for the change in step
size becomes less than some epsilon which is also coincidentally the value for d or
we get close enough in our function call at that point or we reach a maximum number of iterations
let's look at a numerical example using our same function and Jacobian but starting from point 1
2 and ending with an epsilon of 10 to the minus 6
we'll need x F at that point J at that point and d using this equation for x and this equation for d
it converges to a solution in about four iterations
let's take a closer look at these two equations if we're using MATLAB or GNU Octave for example
you can use the backslash operator to rewrite our value for d like this which simplifies our
equation to eliminate a d variable it still does solve a linear system each iteration
we could instead multiply both sides of our d equation with the inverse Jacobian resulting in
the identity simplified to this now we can use substitution to come up with this form
for newton's method this does require now to compute an inverse each iteration or does it
if you're using MATLAB or GNU Octave you can use symbolic programming to define variables for x
and y as well as a function F here i'm using the example from the rest of the video but you
can make any function f then have it compute the Jacobian for you by calling the jacobian
function on F you can also have it invert J for you giving an output that looks like this
so if you're not too familiar with finding partial derivatives or don't want to do that by hand this
is a great option for you you can even take it one step further by multiplying the inverse Jacobian
times F giving you this function that takes in x and y and has no matrix multiplication whatsoever
for the next part of the video i recommend checking out my other lesson on newton fractals
if we apply newton's method starting from any of these
points we know that it would converge to 1.618 for the x and 1.618 for the y
we can test some more points and all of these red dots would eventually converge
to that same solution these dots in blue would converge to the next solution negative one zero
these dots would converge to zero negative one and these dots in green scattered throughout the blues
and yellows would eventually converge on our last solution we can do this with all the points in
this area to come up with this fractal identifying the basin of convergence for each solution
the darker the color the faster the convergence although if you're not interested as to which
solution it converge to but rather if it converges or not you can create a different kind of fractal
which looks like this we can also add a scalar value in front of each newton's step
to then generalize this fractal even further
like one half plus i over two giving a sort of James Cameron vibe
here is another system of nonlinear equations of x squared plus y squared equal to one
and x plus two y squared equal to one giving this fractal
with very distinct basins of convergence when colored only on the number of iterations you
can tell it's having a very difficult time converging on the solution of one zero
scaled with an a value we get something like this
let me know which director you think would have made this fractal in the comments
going back to our fractal from earlier this was how it looks essentially in the x-y plane but
as you can kind of already tell this works with complex numbers here's the slice taken from the
x i plane and here's one taken from the i y plane we can actually combine all of them
these are just three slices shown in the three dimensions
but you could take any number of slices in any axis you wanted
for some more context let's turn back again to Ypma's paper on the history of newton's method
Ypma refers to another document by Simpson called "a new treatise of fluxions"
with these examples
to quote "in passing it seems appropriate to note also and contribution by Simpson
to the closely related problem of multivariable constraint optimization Simpson gives what may
be the first example of maximizing a function of several variables obtaining the maximum by
essentially setting the gradient of the function equal to zero the idea of setting the gradient
equal to zero combined with newton's method to solve the resulting system of nonlinear equations
is a key ingredient of many techniques for solving unconstrained optimization problems"
some important takeaways of this video are that newton's method can be generalized to
solve systems of nonlinear equations with a quadratic order of convergence there are also many
attributions by Thomas Simpson but the history of newton's method probably requires its own video
the method also needs the Jacobian which means partial derivatives but you can use
symbolic programming to help you out note the two versions of newton's method either solving
a system or taking the inverse of the Jacobian the choice is up to you there are other methods
that avoid using the Jacobian but those require their own videos you can also use Newton's method
to create fractals the code that i wrote as well as the images i created will be hosted on GitHub
as always thank you for watching for more about the Jacobian i recommend
checking out 3blue1brown's video series on Khan Academy
link will be in the description and as a title card in the end screen please let me know your
thoughts on this video in the comments below and again thank you for watching