f08nh:: Least Squares and Eigenvalue Problems (LAPACK) (NAG Toolbox)

nag_lapack_dgebal (f08nh) balances a real general matrix

A

. The term ‘balancing’ covers two steps, each of which involves a similarity transformation of

A

. The function can perform either or both of these steps.

The function first attempts to permute

A

to block upper triangular form by a similarity transformation:

P A P^{T} = A^{'} = (\begin{matrix} A_{11}^{'} & A_{12}^{'} & A_{13}^{'} \\ 0 & A_{22}^{'} & A_{23}^{'} \\ 0 & 0 & A_{33}^{'} \end{matrix})

where

P

is a permutation matrix, and

A_{11}^{'}

and

A_{33}^{'}

are upper triangular. Then the diagonal elements of

A_{11}^{'}

and

A_{33}^{'}

are eigenvalues of

A

. The rest of the eigenvalues of

A

are the eigenvalues of the central diagonal block

A_{22}^{'}

, in rows and columns

i_{lo}

i_{hi}

. Subsequent operations to compute the eigenvalues of

A

(or its Schur factorization) need only be applied to these rows and columns; this can save a significant amount of work if

i_{lo} > 1

and

i_{hi} < n

. If no suitable permutation exists (as is often the case), the function sets

i_{lo} = 1

and

i_{hi} = n

, and

A_{22}^{'}

is the whole of

A

The function applies a diagonal similarity transformation to

A^{'}

, to make the rows and columns of

A_{22}^{'}

as close in norm as possible:

A^{''} = D A^{'} D^{- 1} = (\begin{matrix} I & 0 & 0 \\ 0 & D_{22} & 0 \\ 0 & 0 & I \end{matrix}) (\begin{matrix} A_{11}^{'} & A_{12}^{'} & A_{13}^{'} \\ 0 & A_{22}^{'} & A_{23}^{'} \\ 0 & 0 & A_{33}^{'} \end{matrix}) (\begin{matrix} I & 0 & 0 \\ 0 & D_{22}^{- 1} & 0 \\ 0 & 0 & I \end{matrix}) .

This scaling can reduce the norm of the matrix (i.e.,

‖A_{22}^{''}‖ < ‖A_{22}^{'}‖

) and hence reduce the effect of rounding errors on the accuracy of computed eigenvalues and eigenvectors.

References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

Parameters

Compulsory Input Parameters

Optional Input Parameters

Output Parameters

Error Indicators and Warnings

Accuracy

The errors are negligible.

Further Comments

If the matrix

A

is balanced by nag_lapack_dgebal (f08nh), then any eigenvectors computed subsequently are eigenvectors of the matrix

A^{''}

(see Description) and hence nag_lapack_dgebak (f08nj) must then be called to transform them back to eigenvectors of

A

If the Schur vectors of

A

are required, then this function must not be called with

job ='S'

'B'

, because then the balancing transformation is not orthogonal. If this function is called with

job ='P'

, then any Schur vectors computed subsequently are Schur vectors of the matrix

A^{''}

, and nag_lapack_dgebak (f08nj) must be called (with

side ='R'

) to transform them back to Schur vectors of

A

The total number of floating-point operations is approximately proportional to

n^{2}

The complex analogue of this function is nag_lapack_zgebal (f08nv).

Example

This example computes all the eigenvalues and right eigenvectors of the matrix

A

, where

A = (\begin{array}{r} 5.14 & 0.91 & 0.00 & - 32.80 \\ 0.91 & 0.20 & 0.00 & 34.50 \\ 1.90 & 0.80 & - 0.40 & - 3.00 \\ - 0.33 & 0.35 & 0.00 & 0.66 \end{array}) .

The program first calls nag_lapack_dgebal (f08nh) to balance the matrix; it then computes the Schur factorization of the balanced matrix, by reduction to Hessenberg form and the

Q R

algorithm. Then it calls nag_lapack_dtrevc (f08qk) to compute the right eigenvectors of the balanced matrix, and finally calls nag_lapack_dgebak (f08nj) to transform the eigenvectors back to eigenvectors of the original matrix

A

function f08nh_example


fprintf('f08nh example results\n\n');

n = int64(4);
a = [ 5.14, 0.91,  0.00, -32.80;
      0.91, 0.20,  0.00,  34.50;
      1.90, 0.80, -0.40,  -3.00;
     -0.33, 0.35,  0.00,   0.66];

% Balance a
[a, ilo, ihi, scale, info] = f08nh( ...
                                    'Both', a);

% Reduce a to upper Hessenberg form
[H, tau, info] = f08ne( ...
                        ilo, ihi, a);

% Form Q
[Q, info] = f08nf( ...
                   ilo, ihi, H, tau);

% Calculate the eigenvalues and Schur factorisation of A
[H, wr, wi, Z, info] = f08pe( ...
                              'Schur Form', 'Vectors', ilo, ihi, H, Q);

w = wr + i*wi;
disp('Eigenvalues:');
disp(w);

% Calculate the eigenvectors of A
[select, ~, VR, m, info] = ...
f08qk( ...
       'Right', 'Backtransform', false, H, zeros(1), Z, n);

% Back scale to get eigenvectors of A
[VR, info] = f08nj( ...
                    'Both', 'Right', ilo, ihi, scale, VR);

% Normalize eigenvectors: largest element positive
for j = 1:n
  [~,k] = max(abs(VR(:,j)));
  VR(:,j) =VR(:,j)/norm(VR(:,j));
  if VR(k,j) < 0;
    VR(:,j) = -VR(:,j);
  end
end                            

disp('Eigenvectors:');
disp(VR);

NAG Toolbox: nag_lapack_dgebal (f08nh)

▸▿ Contents

Purpose

Syntax

Description