The condition number of square matrix A is defined as follows:

The condition number has the following meaning: if the machine precision equals ε, when solving a system of linear equations AX = b the order of relative error will be ε·k(A).

Although the matrix condition number depends on the selected norm, if the matrix is well-conditioned, the condition number will be small in all norms, and if the matrix is ill-conditioned, the condition number will be large in all norms. Thus, the most convenient norm is usually selected. 1-norm, 2-norm and ∞-norm are used most frequently. They are as follows:

The iterative algorithm of the condition number estimate

The algorithm estimates the condition number in 1-norm or ∞-norm. The main difficulty is to estimate the norm of matrix A ^-1 (since the norm of A is easily calculated). This program uses the iterative algorithm which estimates the norm of the matrix given implicitly - through multiplying by a vector.

Multiplying vector x by matrix A ^-1 is equivalent to solving the system of linear equations Ay = x. If the LU decomposition of matrix A is known, solving the systems requires O(N ²) operations. The common algorithms for obtaining a solution to the systems of linear equations can cause an overflow (if the matrix is close to singular), therefore a special algorithm is used which can't cause an overflow, but is a bit slower.

A disadvantage of the iterative algorithm lies in the fact that it only obtains an estimate of the condition number, and a rather rough estimate at that. An estimate is usually undersized by 5-10%, but sometimes the error is much bigger (during the numerical experiments, the estimate was lower than the condition number by 8% on average, and the maximum error was 87%). When the estimate is 10 times lower than a value itself, it is usually considered as an inaccurate estimate. Nevertheless, even such a precision may be sufficient.

Let's consider an example. Let the condition number of matrix A be equal to 10 ⁴. This means that if the machine precision is 10 ^-15, the system of linear equations will be solved with precision 10 ^-11. Suppose that our estimate can vary by 90% and equals 10 ³. This means that we can expect a higher precision: 10 ^-12. The difference is not very big because it is not the value of error that's important but its order. On average, 10% of the difference could be ignored since it is less than one decimal digit.

Note #1
You can use SVD decomposition which allows to get the exact value of 2-norm of the condition number as a ratio between the maximum singular value and the minimum one. The advantage of this method is that it allows to get an exact value. The disadvantage is that it is very slow (solving the system of linear equations is much faster than performing the singular value decomposition of a coefficient matrix).

Subroutine description

To avoid an overflow in case of a singular matrix, the subroutines below do not calculate a condition number, but an reciprocal number - . In case of a singular matrix . If the matrix is ill-conditioned, the value of is close to the value of machine precision.

The subroutines RMatrixRCond1 and RMatrixRCondInf calculate 1-norm and ∞-norm of the condition number, respectively. They require O(N ³) operations to perform the LU decomposition, and O(N ²) to estimate the condition number.

The subroutines RMatrixLURCond1 and RMatrixLURCondInf calculate 1-norm and ∞-norm of the condition number for a matrix given by its LU decomposition respectively. They use the result of the LUDecomposition subroutine as an input - matrices L and U in compact form (the permutation table isn't required because the permutations cannot change a condition number), and estimate the condition number in O(N ²) operations.

This algorithm is transferred from the LAPACK library.

Report a bug

C#

C# 1.0 source.
rcond.csharp.zip - Estimate of the condition number

C++

C++ source.
rcond.cpp.zip - Estimate of the condition number
ablas.zip - optimized basic linear algebra subroutines with SSE2 support (for C++ sources only)

C++, multiple precision arithmetic

C++ source. MPFR/GMP is used.
GMP source is available from gmplib.org. MPFR source is available from www.mpfr.org.
rcond.mpfr.zip - Estimate of the condition number
mpfr.zip - precompiled Win32 MPFR/GMP binaries

Delphi

Delphi source.
Can be compiled under FPC (in Delphi compatibility mode).
rcond.delphi.zip - Estimate of the condition number

Visual Basic 6

Visual Basic 6 source.
rcond.vb6.zip - Estimate of the condition number

Zonnon ^beta

Zonnon source.
Zonnon is an experimental language developed at ETH Zurich.
See www.zonnon.ethz.ch for more information.
rcond.zonnon.zip - Estimate of the condition number