Re: Matrix Norm algorithm: Source

On 2006-04-12 11:10:53 -0300, john_shaeffer@xxxxxxxxxxxxx said:

An approximate matrix condition number is needed for a block wise LU
factorization for problems of many thousands of unknowns. The
following algorithm seems to work to compute matrix norms, but I do not
have a reference for it or know the background of this approach. Can
anyone help with a reference and what the qualifications are for this
approach. Matrix A can represent both A or its effective inverse via
LU factorization so that rCond ~ |A| |Ainv|. Test on small matrices,
n = 1000 shows that this converges in about 3 iterations.

The norm finding algorithm for A seems to be:

X0 = 1 ! start with sphere in n space

Start loop k = 0, ...

Xk= Xk / |Xk| ! normalized X

Xk+1 = A (A Xk)*

AnormSq = |Xk+1| ! = | AA*X| = |AA*|

if Converge, exit loop

Anorm = sqrt(AnormSq)

You seem to assume that you need THE matrix (L_2) norm rather than
just A matrix norm. All norms are topologically equivalent meaning that
they are off by at most small coefficients. Some are easy to compute. Like
L_1, Frobenious, L_inf. The problem is that they need the inverse to
calculate the norm of the inverse. So much for the math major type carping.

You have what looks like the usual Raliegh-Ritz type iteration for
the dominant eigenvalue. It will then yield an estimate of L_2 norm.
If you have factors then you can do inverse as well and this is well
known as inverse iteration. This assumes that your initial guess will
include components of the dominant eigenvector. Some suggest a couple
random starts to be sure.

Approximate condition numbers were a topic of interest a long time ago.
Google would be your friend but a lot of this stuff may be so old it
is not on the web.

So in summary. A wee bit of serious mathematics would save a lot of
computation for the forward direction. Serious means advanced
undergraduate in this case. Frobenius is a good bet. For the reverse
direction look at inverse iteration which should be standared fare
in any reasonable numerical analysis text. Again advanced undergraduate.




.

Relevant Pages

  • inner products, vector norms and matrix norms
    ... A vector norm is defined as in http://mathworld.wolfram.com/VectorNorm.html ... Given an inner product, a vector norm can be readily derived as ... What kind of matrix norms generally do ...
    (sci.math)
  • Re: inner products, vector norms and matrix norms
    ... most vector norms cannot be related to an inner product in this ... How would you be able to prove that some given vector norm? ... What kind of matrix norms generally do ... An inner product space can be thought of as a vector space with a metric ...
    (sci.math)
  • Re: [ot?] matrix inversion
    ... "Tom St Denis" writes: ... Take the one of the matrix norms of A * A^-1. ... E.g. higher norm => higher error. ...
    (comp.lang.c)
  • Re: Davenport Lyons - Watchdog Report
    ... LOL are you STILL banging this drum, Norm? ... clients and under their instructions. ... a reference to the contrary, or are you just pouting and posturing ... Only about a dozen are accused of infringing Atari ...
    (uk.legal)
  • Re: Davenport Lyons - Watchdog Report
    ... LOL are you STILL banging this drum, Norm? ... What they don't seem to realise, however, is that DL as solicitors only act on behalf of their clients and under their instructions. ... To quote from the reference you provided: ... DL have withdrawn their actions against illegal downloaders of Atari products because Atari have for some reason seen fit to change their solicitors, ...
    (uk.legal)