[QGHG-it-dev-list] Zadatak 40 - odredjivanje signature zadate kvadratne matrice

[Marko Vojinovic]

Implementirati staticku funkciju

   vector<int> evaluate_signature_of_matrix( const vector<vector<double>> *matrix )

koja kao input dobija pointer na simetricnu realnu kvadratnu matricu, a kao output vraca vektor sa tri integer-a, (p,n,z), koji odgovara signaturi te matrice. Proveriti da je pointer na matricu dobro definisan, da je matrica kvadratna, i da je simetricna. Ako bilo sta od ovoga nije zadovoljeno, prijaviti gresku log_report funkcijom, i vratiti signaturu sa tri nule, (0,0,0). Ako je sve dobro definisano, odrediti i vratiti odgovarajucu signaturu zadate matrice. Funkcija ne sme da menja vrednosti elemenata matrice (matrica je const), nego po potrebi napraviti kopiju matrice pa manipulisati sa elementima kopije.

Signatura (p,n,z) je definisana kao broj pozitivnih (p), negativnih (n), odnosno nultih (z) svojstvenih vrednosti realne simetricne kvadratne matrice. Spektralna teorema garantuje da svaka realna simetricna kvadratna matrica dimenzije N ima tacno N realnih svojstvenih vrednosti, od kojih svaka moze biti pozitivna, negativna ili nula. Signatura onda meri koliko ima kojih znakova svojstvenih vrednosti. Ocigledno mora da vazi p + n + z = N. Za detaljnije informacije o pojmu signature videti [1,2,3].

Algoritam za odredjivanje signature istrazite i implementirajte sami. Neki predlozi se mogu videti u [4], recimo algoritam baziran na Dekartovom pravilu znakova [5]. Alternativno, pronadjite neki efikasan algoritam za odredjivanje svojstvenih vrednosti, pa prebrojte koliko ima pozitivnih, negativnih i nultih. ChatGPT preporucuje LDL^T dekompoziciju matrice [6] kao generalno najbrzi metod, mada ima nekih problema sa numerickom stabilnoscu ako ima nultih svojstvenih vrednosti...

Funkciju evaluate_signature_of_matrix() staviti u fajl math_functions.cpp i odgovarajuci .hpp.

Unutar triangulator/test/ putanje zatim dodati nov fajl signaturetest.cpp, u kome mozete da testirate racunanje signatura na nekoliko primera raznoraznih matrica.

Ukoliko imate bilo kakva pitanja ili sugestije vezane za ovaj zadatak, slobodno se javite.

:-)
Marko

[1] https://en.wikipedia.org/wiki/Metric_signature

[2] https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia

[3] https://en.wikipedia.org/wiki/Quadratic_form#Real_quadratic_forms

[4] https://en.wikipedia.org/wiki/Metric_signature#How_to_compute_the_signature

[5] https://en.wikipedia.org/wiki/Descartes%27_rule_of_signs

[6] https://en.wikipedia.org/wiki/Cholesky_decomposition#LDL_decomposition


Dr. Marko Vojinovic
Group for Gravitation, Particles and Fields
Institute of Physics
University of Belgrade
======================
home page: www.markovojinovic.com
e-mail:    vmarko at ipb.ac.rs