hello Internet this is Oscar Veliz again this time showing you to solve systems
of equations using fixed point iteration we'll go over some examples talk about
the Banach Fixed Point Theorem and discuss order this video does require
some background knowledge of fixed point iteration for finding roots of one
equation I recommend watching my earlier videos on these topics if you haven't
already
for solving systems of equations you should have at least as many equations
as you do unknowns and fixed point iteration will actually work for both
linear and nonlinear systems of equations when it comes to solving
system there could be no solution and infinite number of solutions or a finite
number and for nonlinear systems you can't use things like Gaussian
elimination to solve them you could try to solve them algebraically or iterative
numerical way like this video will show you how to do it with fixed point
iteration as the basis for this video we'll use the nonlinear system of x
squared minus y equal to 1 and x minus y squared equal to negative 1 which has
these 4 solutions so how does fixed point iteration work first rewrite your
equation set you can isolate your variables for example X is equal to
something and Y is equal to something you can also represent it using a vector
for example capital X is X Y then we label the left-hand side with n plus 1
and the right hand side with n then pick a starting value for X and iterate until
you find a solution so let's rewrite these expressions first the green one we
can simply take Y to the other side and then divide everything by X giving us X
sub n plus 1 is equal to Y of X sub n plus 1 over X sub n for our other
equation we can move X over then divide everything in by minus 1 and take the
square root of course this gives us two answers for our new Y therefore we can
break this up into two separate solutions as you might imagine there are
many different ways that we can rearrange these functions regardless
you'll still need to have one that you created from the first function and one
that you created from the second in this case one green and one blue let's keep
things simple and just use the square root of y plus 1 and the square root of
x plus 1 as our system of equations if we start at (1,2) and plug them in to our
newest systems of equations and this gives us square root of 3, square root
2 we'll plug that in to get a new value for X and then plug that in to get our
next X if we graph this on the XY plane with our original system of equations
starting from (1,2) performing one iteration a fixed point iteration
getting the next value and the next value
eventually we're actually reaching a solution let's ignore the numbers and
just look at our steps this is our first step followed by our second step our
third and our fourth and you can kind of tell that our steps are getting smaller
each iteration let's put the numbers back in and figure out what is the
length of this step if we use that step as the hypotenuse of a right triangle
labeled as A B and C then C is equal to the square root of A squared plus B
squared and to figure out A and B we just need to do subtraction this gives
us our length of C. given our sequence of iterations if we compute the
distance between each iteration you'll notice that the distance approaches zero
the trouble is that these are actually not Cartesian points they're Banach
spaces named after Stefan Banach we can think of them more like vectors and to
compute the norm of a vector in this case the l-2 norm will simply take the
square root of the sum of squares for example the norm of X1 is equal to the
square root of 5 and the norm of X2 minus X1 is our distance function we
know that we can stop iterating with fixed point iteration when the norm of
our steps becomes less than some epsilon or if we take our original function and
rewrite it in terms of zero we can stop it when the norm of the function at our
X is less than some epsilon or whenever to reach some maximum number of
iterations so far we've been able to find this solution using fixed point
iteration but what if we wanted to find this one with our set of equations
starting at (1,2) we found our first solution at 1.618 for X and 1.618
for Y if we instead start at negative point six and negative point seven this
should give us a better chance at finding our second solution and indeed
this one ends up at our first one again let's instead
use a different set of equations and if we start from negative 0.6 and negative
0.7 and this ends up diverging if you use even another set of equations
starting from that point after 55 iterations we're able to find our second
solution so when does it converge recall how we rewrote our equations to be X is
equal to something and Y is equal to something we call that something G of X
such that X sub n plus 1 is equal to G of X sub n when our norms are getting
smaller this means the distance between our
steps is shrinking and when we have a sequence of shrinking steps we call this
Cauchy you can also rewrite it to look like this things are gonna get a little
technical now but bear with me first we say that there exists a solution X star
such that f of X star is 0 and a Cauchy sequence to X star is generated by G of X
given this sequence and that its Cauchy we can say that a contraction mapping
creates a Cauchy sequence a contraction mapping basically says that for any two
points the norms between them are greater than the norm of the functions
subtracted from those points more formally we will write like this with an
L variable in front then G of X is guaranteed to converge if it is a
contraction mapping let's go back a bit and look at our X's but more
specifically our change in X's if we take a matrix which we'll just call J and
multiply it by our change in X's there's something peculiar that happens each new
change in X is approximately this special sequence J times our old change
in X maybe this will help
using that expression we can say that J our Jacobian is G Prime at X star to
find G Prime using our example G we take the partial derivative of every equation
in G against every variable in G using X star which is the solution to our first
system of equations plug that into G Prime
to get our Jacobian so how does this help us using our contraction mapping
condition which looks like this and our Jacobi a multiplication expression that
looks like this if you replace two of those X's with G of X then take the norm
of everything we can say that the norm of J is an upper bound on L in this case
the norm is still the square root of the sum of squares of all terms in J when
our norm is less than 1 then G is going to be guaranteed to be a contraction
mapping using our first set of equations we can compute G prime using partial
derivatives then if you plug in X star in this case values of phi we can
compute J then by taking the norm of J we get about 0.44 which is less than 1
and therefore it passes the convergence test using our second set of equations
we can also find G prime then plugging in X star we can compute J taking the
norm of J we get about 1.66 which fails the test what if we instead
use our second solution and plug this into J taking the norm of J in this case
also fails the test what about our last set of equations we know that this one
found our second solution if we compute G prime and plug in our second solution
we can compute J then all we do is take the norm of J and wait a second this
also failed the test? earlier I refer to it as the convergence test but really it
is the contraption mapping test passing it guarantees it to be a contraction map
failing it only means that there is no guarantee also if you needed
to X star to find J then what was the point of trying to guarantee its
convergence because you already know the solution think of it as is G a mapping
to X star also having J is a good indicator of the change in step size you
can avoid a lot of this by using the generalized Aiken-Steffensen's method
which is the subject of another video now what about the all-important order
let me refer to Peter Henrici's book Elements at American Analysis
here is my library's copy Henrici writes if J is not equal to zero that is if the
elements of the matrix J are not all zero it shows that the error vector is
approximately multiplied by the Jacobian in this sense we again may speak of linear
convergence if J is equal to zero that is if all four elements of J are zero
then we see that this expression this is similar to what earlier has been
quadratic convergence to find the exact order will depend on
your sequence you can use three consecutive errors like we have with our
order formula from earlier if you've seen my other videos here the error is
either the norm of F of X sub N or the norm of X sub n minus X star using our example
from earlier plugging in three errors we get about a linear order going back to
the slide from earlier we've been able to find two solutions but what about
these other two I'll leave those for you to find some parting notes fixed point
iteration can converge even if it's not guaranteed to be contraction map and it
also works with complex numbers usually the l-2 norm is good enough but you might
need to use a different norm if things are working out well and I
oversimplified the Banach Fixed Point Theorem this is probably the discussion
of another video all on its own you can also use the generalized form of
Aitken's method to accelerate convergence induced convergence and
avoid the convergence mapping test altogether the code that I used will be
hosted on github thank you very much for watching this video took a lot of
iterations to get right and I hope things made sense please comment with
your thoughts questions and suggestions for future videos I will highly
recommend that following this video you watched my other video on generalized
Aitken-Steffensen's method which follows up on key topics from this video