Gershgorin's theorem

The set of Gerschgorin (after the mathematician Semen Aronowitsch Gerschgorin ) is a theorem from the algebra . It says that the complex zeros of a normalized complex polynomial ${\displaystyle \xi _{1},\dots ,\xi _{n}}$

${\displaystyle p=X^{n}+p_{n-1}X^{n-1}+\dots +p_{0}}$

lie in a circle around the origin with the radius , with the estimates ${\displaystyle K}$ ${\displaystyle r}$

• ${\displaystyle r\leq \max\{1,\sum _{j=0}^{n-1}|p_{j}|\}}$ and
• ${\displaystyle r\leq \max\{|p_{0}|,1+|p_{1}|,\dots ,1+|p_{n-1}|\}}$

be valid.

Gershgorin circles

This theorem is a consequence of the theorem about the Gerschgorin circles in the complex plane, which contain the eigenvalues ​​of a square matrix. For every matrix it holds that the eigenvalues ​​of in the union of the circular disks ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle A}$

${\displaystyle D{\big (}a_{k,k},r_{k}{\big )}={\big \{}\,z\in \mathbb {C} :\,|z-a_{k,k}|\leq r_{k}\,{\big \}}}$

around the diagonal elements with radii or when considering the transposed matrix with radii . Each connected component of the union contains as many eigenvalues ​​as there are diagonal elements of the matrix . ${\displaystyle a_{k,k}}$ ${\displaystyle r_{k}=\sum _{j\neq k}|a_{k,j}|}$ ${\displaystyle r_{k}=\sum _{j\neq k}|a_{j,k}|}$ ${\displaystyle A}$

Accompanying matrices

If you multiply a polynomial with degree by the variable and reduce the product modulo , a new polynomial with degree is created . This assignment is a linear mapping of the space of the polynomials of degree (or less) into itself. For each base of this -dimensional vector space (more precisely the quotient ring ) a coefficient matrix of this multiplication operator can be given. This is called the companion matrix of the polynomial. ${\displaystyle q(X)}$ ${\displaystyle \deg(q)<n}$ ${\displaystyle X}$ ${\displaystyle p(X)}$ ${\displaystyle {\tilde {q}}(X)=X\cdot q(X)\mod p(X)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {C} [X]_{n-1}}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle \mathbb {C} [X]/(p(X))}$

Every accompanying matrix of the polynomial has the polynomial zeros as eigenvalues. The eigenpolynomial for the eigenvalue is , because . ${\displaystyle p(X)}$ ${\displaystyle \xi _{k}}$ ${\displaystyle q_{k}(X)=\prod _{j\neq k}(X-\xi _{k})}$ ${\displaystyle X\cdot q_{k}(X)=\xi _{k}q_{k}(X)+p(X)}$

Matrix accompanying the standard basis

The standard basis consists of the monomials . The products are already the minimal degree representatives modulo , for the last basic element applies ${\displaystyle w_{1}=1,w_{2}=X,w_{3}=X^{2},\dots ,w_{n}=X^{n-1}}$ ${\displaystyle X\cdot w_{1}(X)=w_{2}(X),\dots ,X\cdot w_{n-1}(X)=w_{n}(X)}$ ${\displaystyle p(X)}$

${\displaystyle X\cdot w_{n}(X)=X^{n}=p(X)-p_{0}w_{1}-p_{1}w_{2}-\dots -p_{n-1}w_{n}}$.

So the accompanying matrix (in Frobenius form) is

${\displaystyle A={\begin{pmatrix}0&1&0&\dots \\0&0&1&0&\dots \\\vdots &&\ddots &\ddots \\0&&&0&1\\-p_{0}&-p_{1}&-p_{2}&\dots &-p_{n-1}\end{pmatrix}}}$.

The zeros of the polynomial are therefore contained in the union of the circular disks and . Using the transposed accompanying matrix results in the union of the circular disks , and . The estimates given in the introduction result from these two cases. ${\displaystyle p}$ ${\displaystyle D(0,1)}$ ${\displaystyle D(-p_{n-1},|p_{0}|+\cdots +|p_{n-2}|)}$ ${\displaystyle D(0,|p_{0}|)}$ ${\displaystyle D(0,1+|p_{k}|),\;k=1,...,n-2}$ ${\displaystyle D(-p_{n-1},1)}$

Supplementary matrix for the basis of the Lagrange interpolation

(cf. Börsch-Supan 1963): Let be pairwise different complex numbers. Then form the polynomials ${\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }$

${\displaystyle w_{k}(X)=\prod _{j\neq k}(X-z_{j}),\;k=1,...,n}$

a base of the space of polynomials of degree smaller . The leading coefficient is 1 in each case . Therefore the minimal representative of just is the polynomial . According to the formula of Lagrange interpolation , this polynomial can be expressed in the selected base: ${\displaystyle n}$ ${\displaystyle X\cdot w_{k}(X)\mod p(X)}$ ${\displaystyle X\cdot w_{k}(X)-p(X)}$

${\displaystyle X\cdot w_{k}(X)-p(X)=\sum _{j=1}^{n}{\big (}z_{j}w_{k}(z_{j})-p(z_{j}){\big )}\,{\frac {w_{j}(X)}{w_{j}(z_{j})}}=z_{k}w_{k}(X)-\sum _{j=1}^{n}{\frac {p(z_{j})}{w_{j}(z_{j})}}\,w_{j}(X)}$.

The accompanying matrix thus results in

${\displaystyle A=\operatorname {diag} (z_{1},\dots ,z_{n})-{\begin{pmatrix}1\\\vdots \\1\end{pmatrix}}\left({\frac {p(z_{1})}{w_{1}(z_{1})}},\dots ,{\frac {p(z_{n})}{w_{n}(z_{n})}}\right)}$.

The closer the support points are to the true zeros, the smaller the second summand becomes, that is, the smaller the radii of the Gerschgorin circles. ${\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }$

The zeros of are then in the union of the circular disks ${\displaystyle p}$

${\displaystyle D\left(z_{k}-{\frac {p(z_{k})}{w_{k}(z_{k})}},\sum _{j\neq k}\left|{\frac {p(z_{j})}{w_{j}(z_{j})}}\right|\right)}$

or when using the transposed accompanying matrix in the union of the circular disks

${\displaystyle D\left(z_{k}-{\frac {p(z_{k})}{w_{k}(z_{k})}},(n-1)\left|{\frac {p(z_{k})}{w_{k}(z_{k})}}\right|\right)}$

contain. If the selected support points are good approximations of the zeros of p (X) , the union of the circular disks breaks down into connected components, each of which contains a cluster of zeros or a multiple zero. If the zeros are well separated and the approximation is good enough, the disks are disjoint in pairs and each contains exactly one zero. ${\displaystyle z_{1},\dots ,z_{n}\in \mathbb {C} }$

Another observation is that the centers of the circular disks represent better estimates of the zeros of . If this improvement is repeated in a recursion, the result is the Weierstrass (Durand-Kerner) method . ${\displaystyle z_{k}-{\tfrac {p(z_{k})}{w_{k}(z_{k})}}}$ ${\displaystyle p}$

improvement

A. Neumaier (2003) gives the following improvement of the circular disks in the last example: The zeros are in the circular disks

${\displaystyle D\left(z_{k}-{\frac {np(z_{k})}{2w_{k}(z_{k})}},\left|{\frac {np(z_{k})}{2w_{k}(z_{k})}}\right|\right),\;k=1,...,n}$,

contain. These circular disks are subsets of the circular disks for the transposed matrix in the last example. The radius is reduced by a factor of approximately compared to the formula derived there . ${\displaystyle 1/2}$

literature

• W. Börsch-Supan: A posteriori error bounds for the zeros of polynomials. In: Numerical Mathematics. Vol. 5, No. 1, 1963, ISSN  0029-599X , pp. 380-398, doi: 10.1007 / BF01385904 .
• Howard E. Bell: Gershgorin's Theorem and the Zeros of Polynomials. In: American Mathematical Monthly. Vol. 72, No. 3, March 1965, ISSN  0002-9890 , pp. 292-295.
• Arnold Neumaier: A Gerschgorin type theorem for zeros of polynomials. ( online ), probably published as Arnold Neumaier: Enclosing clusters of zeros of polynomials . In: Journal of Computational and Applied Mathematics . 156, 2003.