COUNTING AND COMPUTING THE EIGENVALUES OF A COMPLEX TRIDIAGONAL MATRIX, LYING IN A GIVEN REGION OF THE COMPLEX PLANE

We present a numerical technique for counting and computing the eigenvalues of a complex tridiagonal matrix, lying in a given region of the complex plane. First, we evaluate the integral of the logarithmic derivative p′(λ)/p(λ), where p(λ) is the characteristic polynomial of the tridiagonal matrix, on a simple closed contour, being the closure of that region. The problem of evaluating this integral is transformed into the equivalent problem of numerically solving a complex initial value problem defined on an ordinary first-order differential equation, integrated along this contour, and solved by the Fortran package dcrkf54.f95 (developed recently by the authors). In accordance with the "argument principle," the value of the contour integral, divided by 2πi, counts the eigenvalues lying in the region. Second, a Newton–Raphson (NR) method, fed by random guesses lying in the region, computes the roots one by one. If, however, NR signals that |p′(λ)| converges to zero, i.e. a multiple root probably exists at the current value λ, then counting the roots within an elementary square centered at λ reveals the multiplicity of this root.