Gershgorin Circle Theorem - Application

Application

The Gershgorin circle theorem is useful in solving matrix equations of the form Ax = b for x where b is a vector and A is a matrix with a large condition number.

In this kind of problem, the error in the final result is usually of the same order of magnitude as the error in the initial data multiplied by the condition number of A. For instance, if b is known to six decimal places and the condition number of A is 1000 then we can only be confident that x is accurate to three decimal places. For very high condition numbers, even very small errors due to rounding can be magnified to such an extent that the result is meaningless.

It would be good to reduce the condition number of A. This can be done by preconditioning: A matrix P such that PA−1 is constructed, and then the equation PAx = Pb is solved for x. Using the exact inverse of A would be nice but finding the inverse of a matrix is generally very difficult.

Now, since PAI where I is the identity matrix, the eigenvalues of PA should all be close to 1. By the Gershgorin circle theorem, every eigenvalue of PA lies within a known area and so we can form a rough estimate of how good our choice of P was.

Read more about this topic:  Gershgorin Circle Theorem

Famous quotes containing the word application:

    Most people, no doubt, when they espouse human rights, make their own mental reservations about the proper application of the word “human.”
    Suzanne Lafollette (1893–1983)

    The human mind is capable of excitement without the application of gross and violent stimulants; and he must have a very faint perception of its beauty and dignity who does not know this.
    William Wordsworth (1770–1850)

    I think that a young state, like a young virgin, should modestly stay at home, and wait the application of suitors for an alliance with her; and not run about offering her amity to all the world; and hazarding their refusal.... Our virgin is a jolly one; and tho at present not very rich, will in time be a great fortune, and where she has a favorable predisposition, it seems to me well worth cultivating.
    Benjamin Franklin (1706–1790)