Equilibration

In numerical mathematics, equilibration ( Latin aequilibrium , equilibrium) means the multiplication of the rows or columns of a linear system of equations with certain factors , so that all rows or columns then have the same norm . The aim of this scaling is to reduce the condition number of the equation system, which reduces the influence of disturbances in the input data (e.g. due to rounding errors) on the solution.

Equilibration is thus a possibility of preconditioning linear systems of equations, but as a rule not particularly effective, since the approximation of the inverse given by the diagonal matrix is not good. For most of the discretization methods for partial differential equations , other preconditioners are preferable.

Mathematical description

The aim of equilibration is to replace the system of equations with an equivalent system of equations with a system matrix with the smallest possible condition number. The condition number depends on the matrix norm and this reduction does not necessarily work with every matrix norm. However, you can specify optimal scalings for the row sum norm and the column sum norm. ${\ displaystyle Ax = b}$ ${\ displaystyle A ^ {*}}$

Line equilibration

A Zeilenäquilibrierung corresponds to the multiplication of the matrix A from the left and a diagonal matrix D . By scaling the lines with the amount sum norm, the condition of the scaled equation system with respect to the line sum norm becomes ${\ displaystyle \ kappa _ {\ infty} (A ^ {*}) = \ Vert A ^ {*} \ Vert _ {\ infty} \ cdot \ Vert A ^ {* - 1} \ Vert _ {\ infty} }$

{\ displaystyle \ Vert A ^ {*} \ Vert _ {\ infty} = \ max _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {n} {| a_ {ij} ^ { *} |}}

optimized. So there is no regular diagonal matrix such that . Each row of the matrix is divided by its row sum (this sum is greater than 0, since the matrix was assumed to be regular). ${\ displaystyle {\ hat {D}}}$ ${\ displaystyle \ kappa _ {\ infty} (A ^ {*})> \ kappa _ {\ infty} ({\ hat {D}} A ^ {*})}$ ${\ displaystyle i}$ ${\ displaystyle A}$ ${\ displaystyle \ textstyle \ sum _ {j = 1} ^ {n} \ vert a_ {ij} \ vert}$

Column equilibration

An equilibration of the columns corresponds to the multiplication of the matrix A from the right by a diagonal matrix. Scaling the columns using the sum sum norm by dividing by the column sums provides an optimal scaling with regard to the column sum norm in the sense that no diagonal matrix exists such that . ${\ displaystyle \ textstyle \ sum _ {i = 1} ^ {n} \ vert a_ {ij} \ vert}$ ${\ displaystyle {\ hat {D}}}$ ${\ displaystyle \ kappa _ {1} (A ^ {*})> \ kappa _ {1} (A ^ {*} {\ hat {D}})}$

example

The line equilibration will be demonstrated with a short example. Given is the matrix A for the linear system of equations . ${\ displaystyle Ax = b}$

${\ displaystyle A = {\ begin {pmatrix} 1 & 2 \\ 3 & 4 \ end {pmatrix}}}$ with the inverse ${\ displaystyle A ^ {- 1} = {\ begin {pmatrix} -2 & 1 \\ {\ frac {3} {2}} & - {\ frac {1} {2}} \ end {pmatrix}}}$

This is the condition of the matrix with respect to the row sum norm

{\ displaystyle \ kappa _ {\ infty} (A) = \ Vert A \ Vert _ {\ infty} \ cdot \ Vert A ^ {- 1} \ Vert _ {\ infty} = 7 \ cdot 3 = 21.}

During line equilibration, the following diagonal matrix (set up as described above) is now multiplied in from the left. This results in ${\ displaystyle D = {\ begin {pmatrix} {\ frac {1} {3}} & 0 \\ 0 & {\ frac {1} {7}} \ end {pmatrix}}}$

${\ displaystyle A ^ {*} = DA = {\ begin {pmatrix} {\ frac {1} {3}} & {\ frac {2} {3}} \\ {\ frac {3} {7}} & {\ frac {4} {7}} \ end {pmatrix}}}$ with the inverse ${\ displaystyle A ^ {* - 1} = {\ begin {pmatrix} -6 & 7 \\ {\ frac {9} {2}} & - {\ frac {7} {2}} \\\ end {pmatrix} }}$

The condition of the matrix is calculated ${\ displaystyle A ^ {*}}$

{\ displaystyle \ kappa _ {\ infty} (A ^ {*}) = \ Vert A ^ {*} \ Vert _ {\ infty} \ cdot \ Vert A ^ {* - 1} \ Vert _ {\ infty} = 1 \ cdot 13 = 13,}

which is less than the condition of the matrix . The value is always 1 due to the definition . ${\ displaystyle A}$ ${\ displaystyle \ Vert A ^ {*} \ Vert _ {\ infty}}$ ${\ displaystyle A ^ {*}}$

literature

A. Meister: Numerics of linear systems of equations . 2nd Edition. Vieweg, 2005, ISBN 3528131357
A. Kielbasinski and H. Schwetlick: Numerical linear algebra . German Science Publishing House, 1988