so we have been discussing iterative methods
for solving linear algebraic equations and
then after discussing algorithms we started
looking at convergence of these methods we
also derived necessary and sufficient condition
for convergence necessary and sufficient condition
for convergence was spectral radiance of matrix
as inverse t should be inside unit circle
and we said that it definitely gives us lot
of insight into what happens but we need something
even simpler to calculate and we have started
looking at matrix norms to come up with something
that is easier to compute in terms of assessing
whether a matrix which are used to formulate
the iterations we can apply some quick tests
to come up with convergence analysis
so induced matrix norm was defined as normal
of a let us talk about norm in which the norm
induced by identical normal on both range
and domain space so this is max x not equal
to 0 norm ax/norm x and the way i try to explain
this was this is the something like amplification
power of a matrix other way of writing the
same thing so it is 2 normal here and 2 norm
if i want 1 normal it will be a1 normal 1
norm and 1 norm and so on this is called induced
normal because this is induced by the norm
defined on the range and the domain space
okay that is why it is called induced norm
other way of writing this is this is generic
thing so i need not write 2 but we were discussing
2 norm at the end of the last class so this
inequality can also be written like this norm
ax/norm x is less than or equal to… so norm
a is in some sense bound upper bound on this
ratio of course this is always greater than
0 or x is not equal to 0 this is always greater
than 0 okay or it could be always greater
than or equal to 0
suppose a is a matrix which is rank deficient
and ax is in a null space then ax will be
0 but denominator is not 0 so this can be
greater than or equal to 0 and this is an
upper bound norm is an upper bound maximum
of this ratio or maximum of the gain maximum
of the amplifying power of the matrix whatever
way you want to give it okay
now in particular we started discussing 2
norm so in 2 norm i just started by putting
ax2 square/x2 square which i wrote as x transpose
a transpose ax/x transpose x i can do all
this divisions because this is a scalar x
transpose a transpose a*x is a scalar x transpose
x is a scalar so this is ratio of 2 scalars
okay
now this particular one this particular norm
where even though as i said that it is not
very convenient for computation but gives
you very nice interpretation so this one we
showed that we made additional assumption
that matrix a transpose a this is a symmetric
matrix positive definite matrix we made one
more assumption that a transpose a has linearly
independent eigenvalues
so we wrote this matrix a transpose a as psi
lambda psi inverse actually what i argued
was that since this is a symmetric positive
a matrix the eigenvectors are orthogonal which
is same as 
appearing on main diagonal 
and this matrix psi is nothing but matrix
formed by keeping eigenvectors of a transpose
a next to each other okay so i am just keeping
eigenvectors of a next to each other this
is a n*n matrix not only invertible it is
an orthonormal matrix which means psi transpose
psi=psi psi transpose=i special property of
this matrix okay and i transform this i transform
this ratio using this i transformed this ratio
to something very very interesting
so i wrote this x transpose a transpose ax
as x transpose psi lambda psi transpose x…
psi psi transpose x and defining y to be psi
transpose x we wrote this ratio defining this
new vector we defined y or we defined z we
wrote this ratio to be lambda 1 z1 square+lambda2z2
square+lambda nzn square… so you can see
that this is ratio of 2 positive quantities
is ratio of 2 positive quantities because
eigenvalues of a transpose a are always positive
okay eigenvalues of a transpose a are always
positive
because a transpose a is a positive defined
matrix its eigenvalues are positive z1 square
z2 square whatever is z z1 z2 square is always
positive so this is ratio of 2 positive quantities
okay now if we order the eigenvalues as all
the eigenvalues are real positive for positive
definite matrix
and then if i say that lambda 1 is greater
or equal to lambda 2>0 okay if this holds
well there is an implicit assumption when
we started all this analysis that a is full
rank because we are assuming that when you
are solving this we are talking about a full
rank matrix so that is why you get minimum
eigenvalue>0; otherwise you may have possibilities
some eigenvalues will be=0 now if i number
my eigenvalue such that lambda 1 corresponds
to of the largest
numbering it depends upon me what i call 1
and what i call 2 matrix as eigenvalues they
do not come numbered we number them so i am
numbering lambda 1 to be the largest okay
so it is very easy to see that this ratio
will always be less or equal to lambda 1z1
square+lambda 1z2 square+lambda 1zn square/z1
square up to zn square is everyone with me
on this i am just replacing lambda 2 by lambda
1 lambda 3 by lambda 1 lambda 4 by lambda
1 okay lambda 1 is the largest magnitude eigenvalue
of a transpose a okay
so i am allowed to do this denominator is
same numerator i am replacing by the larger
value for every term by term okay very easy
to see that you can take lambda common okay
so this ratio is independent of this is lambda
1 okay so this ratio can never exceed lambda
1 this ratio can never exceed lambda 1 very
very nice property okay what did we start
with? we started with this we wanted to find
out maximum of this ratio
what is the maximum of this ratio? lambda
1 okay this ratio can never exceed eigenvalue
of maximum magnitude eigenvalue of a transpose
a okay so what is 2 norm of matrix a? lambda
1 this is the upper bound and you can show
that this upper bound is attained when eigenvector
is aligned in a particular direction okay
what happens when x=v1? when will this be
an equality? for which direction?
v1 transpose a transpose av1/v1 transpose
v1 okay but v1 can be chosen to be orthonormal
so v1 transpose v1 will be unity okay so this
will be v1 transpose lambda 1v1/v1 transpose
… even if it is not chosen orthogonal even
then this ratio will be equal to lambda 1
okay so when x is aligned along the direction
which corresponds to the eigenvector associated
with lambda 1 eigenvector of a transpose a
not eigenvector of a
eigenvector is defined for a square matrix
okay eigenvector is defined for a square matrix
a transpose a is a square matrix a in general
need not be a square matrix but a transpose
a is always a square matrix so of course right
now we are dealing with square matrices we
are dealing with square matrices so there
is no question of non-square matrices we are
dealing with solving ax=b where a is square
in fact we also have a problem where is a
is invertible otherwise
so this ratio becomes equality where x is
aligned along eigenvector of a transpose a
first eigenvector first in the sense that
corresponds to the maximum magnitude eigenvalue
so this is equality okay but this ratio for
any other x is not equality okay for any other
x this ratio will not be equality this ratio
will be smaller okay that is why the maximum
amplification power of a matrix using 2 norm
is given by this okay so i think i have this
picture somewhere drawn for a 2-dimensional
case
actually when you have defined this z=psi
transpose x you have actually defined a transformation
which is rotation okay so suppose this is
your x y then this is your z so this is x1
x2 let us say this is x1 x2 and this will
be your z1 z2 coordinate space so this is
an invertible transformation you can go from
one to other okay so actually you are just
rotating your coordinate axis when you are
multiplying okay and what happens in the rotated
coordinate axis?
in the rotated coordinate axis okay this x
transpose if you draw this x transpose a transpose
a into x that is which is same as… okay
if you draw this inside a region where norm
x is less than 1 you also had other interpretation
of norm right you remember we did one more
interpretation of norm max of ax cap where
x cap is a selective unit circle okay if you
draw that in a locus of points then you will
see here that this actually corresponds to
a ellipse actually corresponds to an ellipse
okay and these coordinates will be nothing
but this will be v1 i have drawn i think wrong
the ellipse will be like this the ellipse
will be like this this z1 will be actually
aligned along your direction v1 z2 will be
aligned along direction v2 okay it will be
an ellipse this ellipse will be major axis
will be along the eigenvector corresponds
to maximum eigenvalue minor axis value along
the direction which is smallest eigenvalue
all other axis are in between so it will be
an ellipse drawn in 3-dimension it will be
a ellipse drawn in n-dimension depending upon
what kind of matrix we are looking at i have
drawn a picture somewhere in the… you can
have a look at it
but again the problem with this 2 norm is
you have to find out eigenvalue of a transpose
a if a is large it does not help us okay so
we could actually come up with a criteria
which says that convergence will occur if
2 norm 2 norm is nothing but eigenvalue of
a transpose a which is strictly<1 but as i
said it does not really help so actually this
what we have found here is ratio of the squares
it is square of this by square of this so
what is the 2 norm
so 2 norm it turns out is that is square root
of lambda 1 that is square root of lambda
max of a transpose 
a that ratio is far as square of see this
ratio was found for a2 square okay a2 square=lambda
1 so what is a2 square root of lambda 1 and
this will always be positive because a transpose
a will always have positives eigenvalues okay
so this number will be positive okay in fact
eigenvalues of a transpose a are called as
singular values of a and square root of the
maximum magnitude singular value that is what
is…
what do you expect when a is symmetric? there
is a problem in the problem sheet if a is
symmetric then it will be a transpose=a so
a transpose a will be equal to a square what
is the relationship of eigenvalue of a and
a square? square it is very easy to show that
if lambda is eigenvalue of a lambda square
is eigenvalue of a square okay so if a is
symmetric a transpose a will be… and if
a is symmetric positive definite then it is
much easier a is symmetric positive definite
then it is lambda max of a square okay lambda
max of a square is lambda square of a and
you can reduce for a symmetric positive definite
matrix just look at its eigenvalue and then
you can
maximum eigenvalue will directly give you
the norm but then this norm is again inconvenient
because you have to compute eigenvalue okay
now i am going to state 2 other norms without
deriving the derivations to some extent required
for these norms are there in the as a part
of your exercises so if you look at you should
try to work out and then you can see whether
you are able to derive that or you end up
into some difficulties
i am just going to write this final statements
for other norms 
okay so now even 2 norms though it has some
nice geometric interpretations it is not quite
convenient for me for computing so i am going
to talk about one norm so one norm is nothing
but max over this 
one norm is nothing but max over this okay
well one small correction i realise that i
made a small mistake here when i wrote the
earlier expression i will just correct it
so it is not norm 2 square=this equal to max
x not equal to 0 so earlier when i started
i had forgotten this max max operator is there
without max operator you cannot proceed and
then i have simplified this quantity okay
so moving on to one norm so this one norm
is induced by one norm on the range space
and one norm on the domain space okay one
norm on the domain space maximum of this ratio
now you can show that one norm so what is
one norm? how do you interpret this? what
is this row what is this summation? is it
a column sum or it is a row sum? it is a column
sum so you take all the elements in one column
a11 a21 okay so one is summation over 1 so
i am taking summation of mod of each column
okay and max over that so i find out… first
of all i take a matrix which is consisting
of only absolute values fully positive numbers
okay
then i find the column sums okay i find the
column sums max over the column sum is nothing
but this ratio max over this ratio that you
can show it is not very difficult to show
this so max over column sums absolute of column
sums that is one norm and what you can show
is infinite norm so infinite norm is nothing
but max over absolute of row sums okay so
these norms you can see here computationally
is much more easy to… see what you have
to do when you want to compute one norm or
infinite norms? you create a matrix a which
is a11 a12…
you create this matrix which is absolute value
of each number all of them are positive numbers
now okay if you take all column sums find
max over it you will get one norm take all
row sums okay find max of the row sums that
will give you infinite norm this is much much
easier to compute… one norm or infinite
norm are much much easier to compute let us
close the… see this one norm and infinite
norm are much much easier to compute than
computing a transpose a and its eigenvalues
though much more complex business than doing
this
this is very very easy okay so i want to take
some easy way of computing norms now where
am i going to use this okay? why am i computing
norms? because our condition necessary and
sufficient condition was spectral radius spectral
radius is nothing but eigenvalue okay so what
is the relationship between norm and the eigenvalue
so that is the next part of the puzzle is
this clear now that we have 3 different ways
of computing norms 2 norm 1 norm and infinite
norm among these 1 norm and infinite norm
are computationally preferable okay and now
comes the point is why am i talking about
norms yes
lambda 1 was nothing but eigenvalue of lambda
i we have this a transpose avi=lambda ivi
so lambdas are eigenvalues of a transpose
a okay now i said that i have numbered the
eigenvalues okay such that lambda is greater
than or equal to lambda 2 is greater than
or equal to lambda 3… i have numbered them
okay so lambda 1 is nothing but another way
of saying lambda is lambda max okay instead
of giving a number and remembering it is easier
to remember this as a formula lambda max of
a transpose a that is why i called it okay
so this theorem which i am going to state
is now the crux of the matter
for any matrix b any square matrix b okay
sorry any matrix a for any matrix a okay its
spectral radius is always less than or equal
to any induced norm okay the spectral radius
is always less than or equal to induced norm
so can you prove this? how will you prove
this? what is spectral radius? spectral radius
of a is max over i or let us use the new notation
that we have lambda max… spectral radius
is nothing but max over this right now what
is induced norm of a matrix?
for any induced norm this is true this is
the definition right this is the induced norm
definition okay so this thing also holds when
x corresponds to eigenvector of a let us say
vi is eigenvector of… okay vi=lambda ivi
right so i am going to write this is equal
to norm…
so avi and if i substitute vi here this is
nothing but lambda ivi… right right but
what is this quantity? when lambda comes out
of the numerator what happens? mod lambda
i norm vi/norm vi right mod lambda i norm
vi/norm vi so this cancels okay what remains
is? mod lambda i this holds for every eigenvector
so this also holds for maximum magnitude eigenvector
right see this holds for every eigenvector
okay which means it also holds for that eigenvector
which has a maximum magnitude okay but what
is the maximum magnitude eigenvalue? maximum
magnitude eigenvalue is nothing but the spectral
radius okay
so this inequality that is mod lambda i is
less than or equal to norm a this holds for
all i 1 to n and this implies that spectral
radius of a is less or equal to norm of a
every one with me on this okay so far so good
so now we have developed concept of matrix
norms we have expressions for computing matrix
norms of course in matlab if you give a matrix
and say give a matrix and say 2 norm it will
give you 2 norm which is nothing but this
if you say i and f infinite normal it will
give you infinite norm which is nothing but
this and so on
so computing using a software these days for
any huge matrix is just very very simple of
course computationally for a large-scale matrix
this is much much easier it just has to take
absolute sums of rows and find the max very
very easy as compared to doing this and we
have a very nice relationship here okay now
i am not to exploit this i am going to use
this relationship to come up with sufficient
conditions for convergence okay is this alright
we have matrix norms we know how to compute
them and now we know what is relationship
between the spectral radius and the matrix
a its eigenvalue
we were at one point analysing behaviour of
systems of the time zk+1 just about 2 lectures
back linear difference equations we were analysing
behaviour of this and we said that if spectral
radius of a is strictly less than 1 then what
happens? then norm zk goes to 0 as k tends
to infinity okay as k tends to infinity but
spectral radius for a large matrix is difficult
to compute you have to compute eigenvalues
okay
but from this inequality what i know is that
spectral radius is always less than induced
norm okay now suppose i take a matrix okay
compute its induced norm i compute its infinite
norm okay or not a matrix here we are talking
about sorry this should be b matrix here i
am really sorry just i stand corrected this
should be b matrix here b should be strictly
less than 1 i take my b matrix okay so i take
my b matrix compute its norm say 1 norm or
infinite norm and that norm turns out to be
less than 1
what can i say about the spectral radius right
so if its norm of b say infinite norm is less
than 1 or i am not going to compute 2 norm
i am going to compute only 1 norm or infinite
norm so this infinite norm or norm of b1 norm
if this is strictly less than 1 either of
them are strictly less than 1 okay from this
theorem what i know is that spectral radius
of b should be strictly less than 1 okay so
which means a sufficient condition for convergence
of this zk sequence to 0 norm of zk sequence
to 0 is that take b matrix find its 1 norm
or find its infinite norm if that norm turns
out to be less than 1 strictly less than 1
i am done okay
i know that zk is going to go to 0 irrespective
of what happens to what is your initial condition
it does not depend upon what is your z0 z0
can be large z0 can be small okay z0 can be
arbitrary i know that if this condition holds
then the spectral radius is always less than
1 because induced norm gives the upper bound
on the spectral radius induced norm gives
the upper bound on the spectral radius and
if upper bound is smaller than 1 obvious spectral
radius is less than 1 and then okay so i think
we had lot of side stories now let me go back
to solving ax=b so far so good is the line
of arguments clear okay so let us go back
and look at what we were doing
finally we are back to what we wanted i wanted
to solve ax=b using a iteration method xk+1=s
inverse txk+s inverse b okay we have this
iteration method and we said that the error
behaves according to ek+1=s inverse tek okay
s inverse tek and then we had this condition
that spectral radius of s inverse t now s
and t are different depending upon whether
it is a jacobi method or gauss-seidel method
or relaxation method and so on
now typically s is a simple matrix s is a
diagonal matrix or s is s lower triangular
matrix and inverting that matrix is not that
difficult well we will come up with conditions
which even do not require inversion further
but right now even if you may want to do it
by group force by actually inverting the s
matrix even though it is not difficult but
now we have this condition spectral radius
less than 1 for error convergence this is
necessary and sufficient condition
this is necessary and sufficient condition
i am now giving you a sufficient condition
that if induced norm of s inverse t is strictly
less than 1 okay then spectral radius is less
than 1 and… why this is just sufficient?
why this is not necessary? it can happen that
this is greater than 1 and this is less than
1 see this inequality says it is like saying
01<5 or 01<09 okay so if you get norm of a
to be 5 quite likely that spectral radius
of a could be 01 you do not know
but if norm of a is 09 i surely know that
spectral radius of a<1 okay if norm of a comes
out to be 11 i cannot say anything about being
less than 1 or this being… 1 sorry if induced
norm okay if we compute 1 norm or infinite
norm if this is less than 1 definitely this
is less than 1 okay but if this is greater
than 1 we cannot say anything about what is
this okay inequality just says that this quantity
is less than this quantity
we are particularly interested in this number
1 whether this is less than 1 so this is less
than 1 we are sure that this is less than
1 okay so i can actually use the norm computation
1 norm or repeat norm computation to come
up with a sufficient condition for convergence
okay so now let us actually apply this and
come up with more practical condition because
i will be talking about 1000*1000 matrix or
10000*10000 matrix
how do i know how do i compute s inverse if
it is non-regular matrix computing less than
1 is again not a great idea okay i still want
simpler conditions okay so what is this going
to be now i am going to design a special class
of matrices called as diagonally dominant
matrices okay i am going to define a special
class of matrices called as diagonally dominant
matrices or strictly diagonally dominant matrices
i am finding the summation i am getting a
matrix okay i am taking summation from j=1
to n so i am making rows of i am excluding
1 element from the rows of which is that element?
diagonal the diagonal element okay
now this mod of the diagonal element okay
if mod of the diagonal element is strictly
greater than sum of the remaining elements
absolute sum of the remaining elements okay
then and this should hold for every i okay
this is for mod i=1 2 …n so if these inequalities
hold for each i then such a matrix is called
as diagonally dominant matrix such a matrix
is called as diagonally dominant matrix now
where i will move on here i hope you have
all these in your notebook
let us go back and see in the jacobi method
what was we wrote a=s-t okay for jacobi method
we had s= and we also wrote this that a=l+d+u
then for jacobi method s=d and t=-(l+u) okay
now just think of think s inverse t which
is -d inverse l+u what is d inverse? d is
a diagonal matrix all the elements inversely
just 1/diagonal elements okay now if matrix
a is diagonally dominant if matrix a is diagonally
dominant okay then what happens? aii are all
greater than the summation of all the row
elements absolute of those elements what is
this matrix? can you just write down what
is this matrix?
for jacobi method s inverse t will be what
will be this matrix? 0 -a12/a11 -a13/a11 … -a1n/a11
-a21/a22 0 -a23/a22 … -a2n/a22 right this
s inverse t will be a matrix which has 0 on
the diagonal all diagonal elements will be
like this what will be its infinite norm?
row sum row sum row sum will be nothing but
what will be each row sum? summation aij j
going from 1-n divided by aii aii is divided
each row just look at here okay but this is
a matrix which means this sum is strictly
less than… right
this sum is strictly less than this if this
sum is strictly less than this what does it
mean? that all these ratios are strictly less
than 1 what does it mean infinite norm is
strictly less than 1 if infinity norm is strictly
less than 1 what can you say about the spectral
radius of this matrix? okay so now i have
reduced checking whether jacobi method will
converge or not just to see whether a matrix
whether this diagonally dominant or not
if matrix a diagonally dominant okay my iterations
will converge irrespective of where i start
from okay if starts from my iterations will
converge if my matrix a is diagonally dominant
so after bringing all these juggling lot of
arguments matrix norms and then spectral radius
all that you have come up with a very simple
criteria for finding out whether this jacobi
iterations will converge or not i will reduce
some more theorems
i will not get you the crux of each one of
them but i will give you some more theorems
which are very elegant and from which you
can ascertain whether the iterations will
converge or not or you can modify your problem
such that your iterations are diagonally converge
okay so that is what we will see in next class
we will see that then we will move on some
other norms but this is where you can see
and know i can value spectral radius and norms
everything is actually well we will get into
analyse the behaviour qualitatively without
actually having to solve it just looking at
diagonal dominance i can come to the conclusion
for any initial case our iterations will converge
okay
