|
|
| Author |
Message |
john_shaeffer@earthlink.n
science forum beginner
Joined: 12 Apr 2006
Posts: 1
|
 Posted: Wed Apr 12, 2006 2:10 pm Post subject:
Matrix Norm algorithm: Source
|
|
|
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) |
|
| Back to top |
|
 |
Gordon Sande
science forum beginner
Joined: 11 May 2005
Posts: 48
|
| Posted: Wed Apr 12, 2006 3:02 pm Post subject:
Re: Matrix Norm algorithm: Source
|
|
|
On 2006-04-12 11:10:53 -0300, john_shaeffer@earthlink.net said:
| Quote: | 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. |
|
| Back to top |
|
|
Ron Shepard
science forum beginner
Joined: 11 Jun 2005
Posts: 31
|
| Posted: Wed Apr 12, 2006 3:58 pm Post subject:
Re: Matrix Norm algorithm: Source
|
|
|
In article <1144851053.754049.121670@e56g2000cwe.googlegroups.com>,
john_shaeffer@earthlink.net wrote:
| Quote: | 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.
|
This is based on the power method for finding the largest
eigenvector of the matrix A^2. The norm that is computed
(approximated) is the spectral norm, which is the largest magnitude
eigenvalue. Its weakness is that the power method is sometimes slow
to converge, or in the worst cases, if the initial vector is
orthogonal to the desired eigenvector, it will converge to a
different eigenvector and result in an incorrect value. Convergence
from below should be observed. If you add a couple of lines to
compute the residual norm, then you can compute bounds to the
eigenvalue error. An improved upper bound can be computed if you
know the gap, or a lower bound to the gap, to the second largest
eigenvalue. Also, if you know an upper bound to the matrix spread
(lambda_max-lambda_min), then you can compute an improved lower
bound too.
$.02 -Ron Shepard |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Mar 11, 2010 5:56 pm | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
num-analysis
