馃攳
Multidimensional Newton - Approximate nonlinear equations by sequence of linear equations - lecture6 - YouTube
Channel: Ahmad Bazzi
[0]
what is up you guys so in this one we're going to聽
talk about newton's method applied on non-linear聽聽
[5]
systems if you've watched my previous lectures聽
you'd probably know that i have done a lecture on聽聽
[12]
newton's method but on one-dimensional functions聽
this one we're going to generalize stuff a bit聽聽
[19]
and we're going to see nonlinear systems that is聽
a bunch of non-linear functions and our goal is聽聽
[25]
to solve them simultaneously so what i have is聽
not only one function and not only one variable聽聽
[33]
instead i will have n variables x1 down to xn聽
and i will have n functions as well and my goal聽聽
[43]
is to find the variables x1 through xn dot set all聽
these functions simultaneously to zero now in some聽聽
[51]
references you might find the equivalent notation聽
or the vector notation which is a more compact way聽聽
[58]
of writing things so f would be a vector as well聽
as x all set to the zero vector so the zero vector聽聽
[65]
over here would be this vector of all zeros right聽
this guy would be all this my x vector would be聽聽
[73]
all this and my f vector would be all this this is聽
another way of writing my nonlinear system so the聽聽
[80]
goal here is to solve this system using newton聽
and if you recall in the one-dimensional case聽聽
[87]
because we're going to try to link things聽
together because you know the 1d is easy to聽聽
[92]
keep in mind right it's it's it's as we saw if聽
we're solving f of x equal to 0 1d so f is 1 d聽聽
[99]
x is one d then newton runs as follows x n plus聽
one is x n minus f of x n over f prime of x n聽聽
[110]
right well the 1d case is really similar actually聽
it's almost the same in our system which we have聽聽
[117]
written in a compact way as f bar x equal to zero聽
where f is a vector x is a vector here is the nd聽聽
[124]
case right in this case newton runs as follows聽
so we're going to check some similarities between聽聽
[132]
this and the multi-dimensional case so here i've聽
got a vector instead of a scalar right so as聽聽
[138]
here so x n plus 1 and x n are the same as before聽
but this time they're vectors instead of scalars聽聽
[144]
minus well when we're talking about vectors we聽
don't have division as such instead we have an聽聽
[150]
inverse then a multiplication so i could have聽
written the 1d case as f prime x n all inverse聽聽
[157]
times f x n right same thing the inverse in聽
one d is the reciprocal right well it's this聽聽
[164]
formula that is applied in n dimensions so if i聽
go down here instead of an f prime i don't have a聽聽
[171]
derivative on a vectored quantity the derivative聽
over here is defined as a matrix right it's the聽聽
[178]
matrix of derivatives we're going to call it d聽
of x n and it's going to be inverse for the same聽聽
[184]
reason we have here multiplied with our vector聽
valued function this is newton in n dimensions聽聽
[192]
okay and how do we define our d matrix well it's聽
easy it's as i said the matrix of derivatives so聽聽
[201]
it's defined as you take all possible derivatives聽
of your function okay so actually to be more聽聽
[207]
accurate you take all possible partial derivatives聽
of your function so the first entry of the the聽聽
[213]
vector valued function is f1 so you derive聽
this with respect to all your variables so聽聽
[218]
you've got x1 evaluated at x then you've got del聽
f1 with respect to x2 evaluated at x all the way聽聽
[227]
down to del f1 by del x n evaluated at x same聽
thing you do this for the second function with聽聽
[234]
respect to x2 all the way down to xn you keep聽
doing this till you reach your last function that聽聽
[241]
is the f n by del x 1 del f and by del x 2 and f聽
n by del x n now indeed if you take a look at this聽聽
[251]
in the 1d case you'd only have one function and聽
one variable the f by del x which is f prime right聽聽
[258]
here right okay well really that's how newton's聽
method is applied on nd we're going to see an聽聽
[264]
example we're going to work it manually then we're聽
going to solve it on matlab now let's say i've聽聽
[270]
got the following example just so that we know聽
how to apply it on any type of nonlinear system聽聽
[277]
we've got the following three by three example聽
that is i've got f1 of x1 x2 x3 that is 16聽聽
[284]
x1 to the power 4 plus 16 x2 to the power 4 plus聽
x3 to the power 4 minus 16. i've got f2 of x1聽聽
[296]
x2 x3 that is x1 squared plus x2 squared plus x3聽
squared minus 3. and last but not least i've got聽聽
[305]
f3 if x1 x2 x3 that is x 1 cubed minus x聽
2. good so newton over here is as we said聽聽
[315]
x n plus 1 is x n minus d prime of x and聽
multiplied by f of x n okay f is this entire thing聽聽
[326]
so i don't need to write it down all i need to get聽
going is my d right so for the d i need the matrix聽聽
[334]
of derivatives right so i need del f1 by del x1聽
evaluated that to x x vector okay it's x vector is聽聽
[342]
x1 x2 x3 so it's the vector of all my unknown聽
so del f1 by dot x1 and e del f1 by del x2 and聽聽
[350]
i need del f1 by del x3 right likewise the聽
rf2 by del x1 at x to f2 by delta x2 at x聽聽
[359]
and i'll have 2 by del x3 at x the f3 by del聽
x1 and so on by dell x2 at x and uh 3 by del x3聽聽
[371]
at x right now let's start by computing all my聽
derivatives we've got those nine derivatives聽聽
[376]
that we need to compute so let's compute them聽
we start by del f1 by del x1 at x that is聽聽
[383]
del by del x1 of f1 which is 16 x14 plus 16聽
x2 4 plus x 3 to the power 4 minus 16. we're聽聽
[396]
deriving this with respect to x1 and this term聽
is the only term that indeed depends on x1 so聽聽
[401]
we derive it with respect to x1 and everything聽
else is 0. um we're left with 64 x1 to the power 3聽聽
[408]
right because 4 times 16 is 64. likewise del f1聽
by del x2 at x is the same quantity but this time聽聽
[417]
derived with respect to x2 which gives me the same聽
thing but this time x2 cubed the third derivative聽聽
[424]
del f1 with respect to delta x3 we're deriving the聽
same term right will give me i have only this term聽聽
[431]
that depends on x3 so i get 4x3 cubed right okay聽
we finished the first three derivatives let's go聽聽
[438]
to the second three derivatives which are del f聽
two by del x one at x where i have x one squared聽聽
[446]
plus x two squared plus x three square minus 3 we聽
derive with respect to x1 we get 2x1 now i'm not聽聽
[454]
going to write the same thing down because this聽
guy is symmetric x2 we get 2x2 and x3 square we聽聽
[461]
get 2x3 i'm just going to write the derivative聽
here we've got 2x2 and here i've got 2x3 okay聽聽
[468]
now let's do the partial derivatives for f3 um we聽
start by f3 replacing it we have x1 cubed minus x2聽聽
[478]
the derivative with respect to x1 is 3x1聽
squared okay we're almost done bear with me聽聽
[485]
so the derivative with respect to x2 of this guy聽
is minus 1 and with respect to x 3 is 0 because聽聽
[494]
we don't have terms that contain x3 now that we聽
have our 9 partial derivatives i know what dx is
[506]
so this means that newton is going to run as such聽
here i'm i'm zooming in on each and every quantity聽聽
[514]
so x1 x2 x3 at iteration k plus 1 right聽
is going to be x1 x2 x3 at iteration k um聽聽
[525]
minus this matrix right here which聽
is 64 x1 at the duration k cube 64聽聽
[532]
x2 at iteration k cube and 4x3 at the iteration聽
k cube right likewise i've got 2x1 at iteration k聽聽
[541]
2 x2 at iteration k and 2x3 at iteration k we've聽
got a 0 minus 1 and three x one at the iteration k聽聽
[549]
square multiplied by f one x at the iteration k f聽
two x at iteration k and f three of x at iteration聽聽
[559]
k it would seem absurd that i start with a certain聽
iteration and compute all the iterations by hand聽聽
[567]
this would be a punishment right so for that聽
i'm going to use matlab smash lab is way faster聽聽
[572]
than me it allows me to run to check how the聽
points behave as a function of iteration number聽聽
[578]
and so we get to see things faster okay so聽
now let's hop into matlab and let me create聽聽
[584]
a new script and call it root 3d and inside聽
this root 3d i'm going to define my function聽聽
[591]
f that takes in three numbers x y z and returns聽
the function that we have that is 16 times x 1 to聽聽
[599]
the power 4 plus 16 times x 2 to the power 4 plus聽
x 3 the power 4 minus 16. the second function is x聽聽
[609]
1 squared plus x 2 squared plus x 3 squared minus聽
3. and the last function is x 1 cubed minus x2聽聽
[618]
okay we have this function now let's create a聽
main function um let's call it main for newton聽聽
[625]
okay let's define the number of iterations聽
let's say 10 that we're going to run newton聽聽
[629]
over and let's define the values of x1 x2 x3 at聽
the first iteration so this guy is the initial聽聽
[640]
guess then we're going to define a vector call聽
it x the stack all these initial values so x is聽聽
[647]
going to be let's say a 3 by an iteration matrix聽
at the end because 3 is the number of variables聽聽
[657]
that we have and at each iteration we're going聽
to stack the current xn so now let's define our聽聽
[665]
function even though we defined it here actually聽
this function i defined it now because i'm going聽聽
[670]
to use it in the main iteration of in the main聽
loop of newton no i defined it so that i can have聽聽
[677]
a solution using matlab subroutine that is f聽
solve so with f solved i can define my function聽聽
[685]
at root 3d give it an initializer and call x聽
subroutine to solve this function with the current聽聽
[694]
initialization so if i copy paste all this guy聽
right here in the command window there you go we聽聽
[700]
have the values of f but i need x sub routine so聽
this is the solution according to f solve which is聽聽
[708]
the correct solution because if i input it to my聽
function as such i get something really close to聽聽
[713]
zero right so now i'm going to run newton's method聽
and actually you know what i don't need to define聽聽
[719]
my function again i'm good with this this is my聽
function and if i pass it the following vector聽聽
[724]
i have my vector but i need to transpose it okay聽
so i'm going to use this function okay this is my聽聽
[730]
f right this is my f i'll i'll do this and in my聽
newton's method i'll run from 2 till an iteration聽聽
[738]
right because i have my x1 so i need my 2 which聽
is my x 1 minus inverse d times my f of x and聽聽
[751]
don't forget the transpose okay actually this聽
is not transposed this is transposed conjugate聽聽
[756]
but since we're dealing with real numbers um聽
i won't have to worry about conjugate or not聽聽
[761]
inverse this is not an okay this is the inverse聽
of d which is my matrix of partial derivatives聽聽
[768]
which is 64 times x 1 cubed 64 times x 2 cubed and聽
4 times x 3 cubed in the second row i've got 2 x 1聽聽
[780]
2 x 2 and 2 x 3. and the last row i've got 3x one聽
square minus one and zero and my x1 is taken to b聽聽
[791]
since i'm stacking as we said up here i'm going聽
to stack at each iteration in x since i'm stacking聽聽
[796]
i'm going to read x1 as such it's going to聽
be from the previous iteration and it's the聽聽
[802]
first row likewise x2 and x3 are going聽
to be obtained from the second and third聽聽
[809]
rows right so if i run all this i get an error聽
saying um index and position two no no no no okay聽聽
[817]
so what i usually do i don't take a look at the聽
error per se i place a break point and i run and聽聽
[823]
i check this one is three by one three by one if i聽
invert this guy it's three by three no problem but聽聽
[830]
the problem could come from here aha so this聽
guy is the problem what is the problem we can go聽聽
[836]
ahead and do this again error um what is the error聽
saying what if i do this okay the ah the problem聽聽
[845]
is this this guy should be n minus one right if聽
i do this okay and then this okay which which聽聽
[852]
makes sense because d is evaluated at x n minus 1聽
and f is also evaluated at x n minus 1. so let me聽聽
[858]
go ahead and run this again all this good i have聽
all my estimates right here look at the last row聽聽
[864]
and look at the subroutine pretty close if not the聽
same so we actually did a good job in conversion聽聽
[870]
now to visualize stuff we're going to plot and for聽
plotting i'm going to open a figure plot x one in聽聽
[881]
red set a line width of one i'm going to hold聽
on and do the same thing for x2 and x3 as such聽聽
[890]
now likewise i am going to plot the聽
true value which is x sub routine聽聽
[895]
but i'm going to have it over an iteration聽
number of times because i want to plot a聽聽
[901]
vector um supported at x1 i'll plot it in dashed聽
red and i'll set the line width for this guy聽聽
[910]
at 2. um i'm going to do the same thing for聽
x2 and x3 but just change their colors okay聽聽
[918]
so that they're matchy matchy rr m and black聽
black okay um label the x-axis as iteration um聽聽
[929]
number and i'm going to set the interpreter just聽
for i'm rendering um just to have a nice render聽聽
[938]
and i'm going to place the y axis as x as such聽
x values and grid on grid minor let's run this聽聽
[948]
and there you have it you can see x1 x2聽
and x3 converging to the true value after聽聽
[955]
something like 4 iteration for this particular聽
function of course let's put dollar signs on the聽聽
[959]
x so that it's rendered properly and let's place聽
a legend saying x n x 1 x 2 x 3 and f solve x1聽聽
[969]
f solve x2 and f solve x3 and there you go okay聽
so you can go ahead and experiment with this聽聽
[977]
really as as much as you want um let's say i聽
change my initializer see how initial conditions聽聽
[983]
have a really important role in the convergence聽
of your algorithm it's really important let's聽聽
[989]
change this to zero right here we don't see聽
anything i don't know where the points went聽聽
[994]
let's test this here x not a number i'm sure聽
because the derivative blew up to infinity so聽聽
[1001]
the d matrix yeah at some point um here it's okay聽
let's go to the second iteration haha because if聽聽
[1008]
we go here we check d we check its eigenvalues we聽
have two zero eigenvalues which means that your d聽聽
[1015]
matrix is not invertible you can test on the rank聽
so rank d is two so frank d is three you're good聽聽
[1023]
else three because three variables this should聽
be extended to end if you're looking forward聽聽
[1027]
to generalize this function so rank d is聽
three you're good else you have to throw uh聽聽
[1033]
either well we'll do a warning d is uninvertible聽
and break that case if we run this we get a聽聽
[1042]
warning here and then we break we'll take a look聽
at x um actually we need to clear sorry about聽聽
[1048]
that i need to clear over here clear all and clc聽
so this is x it doesn't show you not a number it聽聽
[1054]
doesn't do the effort of continuing so as i said聽
your initial values are very very important for聽聽
[1061]
the operation of newton's method because at some聽
point if if your newton's method is evaluating聽聽
[1068]
d at a singular point then you cannot invert聽
this matrix okay this is one downside of newton聽聽
[1074]
it requires gradient inverse okay let's experiment聽
with other points again we got this problem so聽聽
[1082]
this guy is important i think this guy is the聽
one that's causing all this yep look over here聽聽
[1087]
it starts to wiggle around and it's not doing good聽
let's take a look at 100 iterations boom at some聽聽
[1094]
point we stopped iterating at the 26th iteration聽
this initializer is not good let's do something聽聽
[1100]
like this aha look at how beautiful this is this聽
is so beautiful let's do something like this this聽聽
[1107]
guy converges but not quite not quite again聽
there are some conditions on the initial value聽聽
[1115]
i'm not going to talk about in this lecture so yes聽
it depends on some theorems of conversions if you聽聽
[1121]
care about those type of theorems let me know down聽
in the comments section below and i'll dedicate a聽聽
[1125]
lesson on that so that's it for this one we talked聽
about newton's method for non-linear systems聽聽
[1131]
or for matrix systems we saw how to to have an聽
analog definition between one dimensional newton聽聽
[1139]
and n dimensional newton then we saw an example聽
on how to get it implemented on a three by three聽聽
[1144]
system which could easily be extended for end聽
by end system okay so thanks for watching i'll聽聽
[1150]
be leaving a written version of this lecture聽
on my website the link is attached down in聽聽
[1154]
the description section below and i'll be doing聽
this more frequently so thanks for watching if聽聽
[1159]
you found this lecture beneficial please leave聽
a like on the video subscribe to the channel聽聽
[1163]
if you have any questions whatsoever don't be shy聽
leave a comment down in the comment section below聽聽
[1168]
i'll make sure i'll get to it as soon聽
as possible and i'll be seeing you then
Most Recent Videos:
You can go back to the homepage right here: Homepage