balance (MATLAB Functions)

Diagonal scaling to improve eigenvalue accuracy

Syntax

[T,B] = balance(A)
[S,P,B] = balance(A)
B = balance(A)
B = balance(A,'noperm')

Description

[T,B] = balance(A) returns a similarity transformation T such that B = T\A*T, and B has, as nearly as possible, approximately equal row and column norms. T is a permutation of a diagonal matrix whose elements are integer powers of two to prevent the introduction of round-off error. If A is symmetric, then B == A and T is the identity matrix.

[S,P,B] = balance(A) returns the scaling vector S and the permutation vector P separately. The transformation T and balanced matrix B are obtained from A, S, and P by T(:,P) = diag(S) and B(P,P) = diag(1./S)*A*diag(S).

B = balance(A) returns just the balanced matrix B.

B = balance(A,'noperm') scales A without permuting its rows and columns.

Remarks

Nonsymmetric matrices can have poorly conditioned eigenvalues. Small perturbations in the matrix, such as roundoff errors, can lead to large perturbations in the eigenvalues. The condition number of the eigenvector matrix,

```
cond(V) = norm(V)*norm(inv(V))
```

where

```
[V,T] = eig(A)
```

relates the size of the matrix perturbation to the size of the eigenvalue perturbation. Note that the condition number of A itself is irrelevant to the eigenvalue problem.

Balancing is an attempt to concentrate any ill conditioning of the eigenvector matrix into a diagonal scaling. Balancing usually cannot turn a nonsymmetric matrix into a symmetric matrix; it only attempts to make the norm of each row equal to the norm of the corresponding column.

Note The MATLAB eigenvalue function, eig(A), automatically balances A before computing its eigenvalues. Turn off the balancing with eig(A,'nobalance').

Examples

This example shows the basic idea. The matrix A has large elements in the upper right and small elements in the lower left. It is far from being symmetric.

A = [1  100  10000; .01  1  100; .0001  .01  1]
A =
   1.0e+04 *
    0.0001    0.0100    1.0000
    0.0000    0.0001    0.0100
    0.0000    0.0000    0.0001

Balancing produces a diagonal matrix T with elements that are powers of two and a balanced matrix B that is closer to symmetric than A.

[T,B] = balance(A)
T =
   1.0e+03 *
    2.0480         0         0
         0    0.0320         0
         0         0    0.0003
B =
    1.0000    1.5625    1.2207
    0.6400    1.0000    0.7813
    0.8192    1.2800    1.0000

To see the effect on eigenvectors, first compute the eigenvectors of A, shown here as the columns of V.

[V,E] = eig(A); V
V =
   -1.0000    0.9999    0.9937
    0.0050    0.0100   -0.1120
    0.0000    0.0001    0.0010

Note that all three vectors have the first component the largest. This indicates V is badly conditioned; in fact cond(V) is 8.7766e+003. Next, look at the eigenvectors of B.

[V,E] = eig(B); V
V =
   -0.8873    0.6933    0.0898
    0.2839    0.4437   -0.6482
    0.3634    0.5679   -0.7561

Now the eigenvectors are well behaved and cond(V) is 1.4421. The ill conditioning is concentrated in the scaling matrix; cond(T) is 8192.

This example is small and not really badly scaled, so the computed eigenvalues of A and B agree within roundoff error; balancing has little effect on the computed results.

Algorithm

Inputs of Type Double

For inputs of type double, balance uses the linear algebra package (LAPACK) routines DGEBAL (real) and ZGEBAL (complex). If you request the output T, balance also uses the LAPACK routines DGEBAK (real) and ZGEBAK (complex).

Inputs of Type Single

For inputs of type single, balance uses the LAPACK routines SGEBAL (real) and CGEBAL (complex). If you request the output T, balance also uses the LAPACK routines SGEBAK (real) and CGEBAK (complex).

Limitations

Balancing can destroy the properties of certain matrices; use it with some care. If a matrix contains small elements that are due to roundoff error, balancing may scale them up to make them as significant as the other elements of the original matrix.

See Also

eig

References

[1] Anderson, E., Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK User's Guide (http://www.netlib.org/lapack/lug/lapack_lug.html), Third Edition, SIAM, Philadelphia, 1999.

axis bar, barh