Algorithms for computing the optimal Geršgorin-type localizations

Abstract

There are numerous ways to localize eigenvalues. One of the best known results is that the spectrum of a given matrix ACn,n is a subset of a union of discs centered at diagonal elements whose radii equal to the sum of the absolute values of the off-diagonal elements of a corresponding row in the matrix. This result (Geršgorin's theorem, 1931) is one of the most important and elegant ways of eigenvalues localization ([63]). Among all Geršgorintype sets, the minimal Geršgorin set gives the sharpest and the most precise localization of the spectrum ([39]). In this thesis, new algorithms for computing an efficient and accurate approximation of the minimal Geršgorin set are presented.

Постоје бројни начини за локализацију карактеристичних корена. Један од најчувенијих резултата је да се спектар дате матрице АCn,n налази у скупу који представља унију кругова са центрима у дијагоналним елементима матрице и полупречницима који су једнаки суми модула вандијагоналних елемената одговарајуће врсте у матрици. Овај резултат (Гершгоринова теорема, 1931.), сматра се једним од најзначајнијих и најелегантнијих начина за локализацију карактеристичних корена ([61]). Међу свим локализацијама Гершгориновог типа, минимални Гершгоринов скуп даје најпрецизнију локализацију спектра ([39]). У овој дисертацији, приказани су нови алгоритми за одређивање тачне и поуздане апроксимације минималног Гершгориновог скупа.

Postoje brojni načini za lokalizaciju karakterističnih korena. Jedan od najčuvenijih rezultata je da se spektar date matrice ACn,n nalazi u skupu koji predstavlja uniju krugova sa centrima u dijagonalnim elementima matrice i poluprečnicima koji su jednaki sumi modula vandijagonalnih elemenata odgovarajuće vrste u matrici. Ovaj rezultat (Geršgorinova teorema, 1931.), smatra se jednim od najznačajnijih i najelegantnijih načina za lokalizaciju karakterističnih korena ([61]). Među svim lokalizacijama Geršgorinovog tipa, minimalni Geršgorinov skup daje najprecizniju lokalizaciju spektra ([39]). U ovoj disertaciji, prikazani su novi algoritmi za određivanje tačne i pouzdane aproksimacije minimalnog Geršgorinovog skupa.