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
![p = X ^ n + p_ {n-1} X ^ {n-1} + \ dots + p_0](https://wikimedia.org/api/rest_v1/media/math/render/svg/6236136bdd55f13c488ac58ef591f668c64b00ea)
lie in a circle around the origin with the radius , with the estimates
![r](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538)
-
and
![r \ leq \ max \ {| p_ {0} |, 1 + | p_ {1} |, \ dots, 1 + | p _ {{n-1}} | \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/043c2fdc208480f961b9ae3cfe5f45f5c2cba99e)
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
![A \ in \ mathbb C ^ {n \ times n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83b3023de9ab6f59e511d7c8ae72d03b64bcecbc)
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![D {\ big (} a _ {{k, k}}, r_ {k} {\ big)} = {\ big \ {} \, z \ in {\ mathbb C}: \, | z-a _ {{ k, k}} | \ leq r_ {k} \, {\ big \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f35e507e8e2d2fe353a549998e6eede1baeae7c8)
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 .
![a_ {k, k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e68cbef4ae4f7f60a841df6d187c74df518a9069)
![r_ {k} = \ sum _ {{j \ neq k}} | a _ {{k, j}} |](https://wikimedia.org/api/rest_v1/media/math/render/svg/559e3b53aea381af6f67bd05652cdeab7d094140)
![r_ {k} = \ sum _ {{j \ neq k}} | a _ {{j, k}} |](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c89f37119de87ea8efffc8e67aba0aa7fe54c1)
![A.](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
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.
![q (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/352e294916cf0c2b425f097071daf0da1b47123b)
![{\ displaystyle \ deg (q) <n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d1e78bdea885ce994859450562ca3a593e6f63)
![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
![p (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7425278aab7b6ceb8ddb54fa5ce71d2cf52d28f)
![\ tilde q (X) = X \ cdot q (X) \ mod p (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/55a408528fcf64e4691d497c72a736025ff05f63)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![\ mathbb C [X] _ {n-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4b749334c0eaf4531a2befd1d5f7cd275bcd252)
![n-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521)
![\ mathbb C [X] / (p (X))](https://wikimedia.org/api/rest_v1/media/math/render/svg/eae45913a946b73ce29afca6067a5551ab6cc59c)
Every accompanying matrix of the polynomial has the polynomial zeros as eigenvalues. The eigenpolynomial for the eigenvalue is , because .
![p (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7425278aab7b6ceb8ddb54fa5ce71d2cf52d28f)
![\ xi _ {k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d15cfc3ac865cb9b3fefec7096afaedc65eb81bd)
![q_k (X) = \ prod_ {j \ ne k} (X- \ xi_k)](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eae70a0e935859ce5e8795afc51aa98be19dab5)
![X \ cdot q_k (X) = \ xi_kq_k (X) + p (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a419f4ced5dac7a394479be250be4f8372957d6)
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
![w_1 = 1, w_2 = X, w_3 = X ^ 2, \ dots, w_n = X ^ {n-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9f21ec6ba627df0384497332d101315f0e8db80)
![X \ cdot w_ {1} (X) = w_ {2} (X), \ dots, X \ cdot w _ {{n-1}} (X) = w_ {n} (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/df711c3175c485e047a2b48b5504aa54ecddb2e0)
![p (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7425278aab7b6ceb8ddb54fa5ce71d2cf52d28f)
-
.
So the accompanying matrix (in Frobenius form) is
-
.
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.
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![D (0.1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e278b4ff5c32f3cce4a2ea680f269a5398a7d49)
![D (-p_ {n-1}, | p_0 | + \ cdots + | p_ {n-2} |)](https://wikimedia.org/api/rest_v1/media/math/render/svg/377ab443b95203b38a4709c30a3eaade5e845485)
![D (0, | p_ {0} |)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f570904d2c7229bf51b6b194a724deba3e1e86b4)
![{\ displaystyle D (0,1+ | p_ {k} |), \; k = 1, ..., n-2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/356adfb637ea7690404fa425d8f48738e6a5a617)
![D (-p _ {{n-1}}, 1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7a778cc64388c12872e6578802addda47fdefbf)
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 w_ {k} (X) = \ prod _ {j \ neq k} (X-z_ {j}), \; k = 1, ..., n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48350da38265512c08e4443f6f71bd9b4f54b00b)
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:
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![X \ cdot w_ {k} (X) \ mod p (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c361c3c04b9fabdb23af57393f6dd6d1e5148326)
![X \ cdot w_ {k} (X) -p (X)](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb88614b84cdfcdb86387113ae9a0aac73c96c52)
-
.
The accompanying matrix thus results in
-
.
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.
![z_1, \ dots, z_n \ in \ mathbb C](https://wikimedia.org/api/rest_v1/media/math/render/svg/557cad76decc8ee556e18631cfdde0ee50394a2b)
The zeros of are then in the union of the circular disks
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![D \ left (z_k- \ frac {p (z_k)} {w_k (z_k)}, \ sum_ {j \ ne k} \ left | \ frac {p (z_j)} {w_j (z_j)} \ right | \ right)](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c0053d5280dc22acb23ffe3e85dcec852dd06b5)
or when using the transposed accompanying matrix in the union of the circular disks
![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)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9c3dfee6724567cca95fcf4bfb056e7255e18bc)
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.
![z_1, \ dots, z_n \ in \ mathbb C](https://wikimedia.org/api/rest_v1/media/math/render/svg/557cad76decc8ee556e18631cfdde0ee50394a2b)
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 .
![z_ {k} - {\ tfrac {p (z_ {k})} {w_ {k} (z_ {k})}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7f970e4b439735fef9c4332325b073e9005bb30)
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
improvement
A. Neumaier (2003) gives the following improvement of the circular disks in the last example: The zeros are in the circular disks
-
,
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 .
![1/2](https://wikimedia.org/api/rest_v1/media/math/render/svg/e308a3a46b7fdce07cc09dcab9e8d8f73e37d935)
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.