Računanje i analiza matrične funkcije predznaka

master's thesis

• Author: Petra Stopić
• Mentor: Nela Bosner (mentor)
• Committee member: Nela Bosner (predsjednik povjerenstva)
• Committee member: Saša Singer (član povjerenstva)
• Committee member: Josip Tambača (član povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2016-07-14, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Matrična predznak funkcija je objašnjena pomoću dvije definicije. Pristup dvjema definicijama se temelji na svojstvenim vrijednostima. Prva je definicija preko Jordanove forme, dok je druga pomoću interpolacijskog polinoma. Koordinatna ravnina koja se koristi je kompleksna pa je važno za \(sign(A)\) s koje se strane imaginarne osi nalaze svojstvene vrijednosti od \(A\). Funkcija \(S := sign(A)\) ima specifična svojstva kao što su involutornost, dijagonalizabilnost i komutativnost sa \(A\). Schurov algoritam za računanje matrične funkcije predznaka koristi Schurovu dekompoziciju matrice \(A\) te primjenu \(sign\) funkcije na gornjetrokutastu matricu iz dekompozicije. Složenost mu je \(O(n^3)\), a sveukupno za algoritam je potrebno oko \(\frac{86}{3}n^3\) operacija da bi se došlo do rješenja. Slijedeća metoda opisana u radu je bila Newtonova. Newtonova metoda koristi Newtonove iteracije te je dokazan teorem o konvergenciji Newtonovih iteracija prema \(sign(A)\). Također taj teorem pokazuje da je brzina konvergencije kvadratna te pomoću njega vidimo da će konvergencija biti sporija ako su svojstvene vrijednosti od \(A\) blizu imaginarne osi te ako je spektralni radijus \(\rho(A)\) puno veći od 1. Sam algoritam metode zahtjeva otprilike \(2in^3\) za \(i\) koraka Newtonovih iteracija. Složenost mu je također \(O(n^3)\). Učinkoviti način da se poveća brzine konvergencije može ponekad biti skaliranje iteracija. Zato postoje i Newtonove skalirane iteracije koje su slične običnima, osim što se kako im ime kaže množe sa nekim određenim skalarom. U tekstu su korištena tri skalara: pomoću determinante, spektralnog radijusa te norme. Dokazan je teorem o konvergenciji spektralno skaliranih iteracija prema \(sign(A)\) funkciji. Naime, konvergiraju nakon \(d+p-1\) koraka gdje je \(d\) broj različitih svojstvenih vrijednosti od \(A\), a \(p\) je određen dimenzijom najvećeg Jordanovog bloka od \(A\). Algoritam skalirane metode zahtjeva \(2in^3\) za \(i\) iteracija. Postoji još jedna vrsta iteracija koja je izvedena iz formule: \(sign(A) := A(A^2)^{-\frac{1}{2}}\) a to su Padéove iteracije. Temelje se na racionalnim polinomnim funkcijama. Matrična iteracija ovisi o kvadratnoj potenciji i inverzu matrice. Teorem o konvergenciji Padéoveih iteracija govori o dva slučaja: kada je konvergencija iteracija lokalna i globalna. Brzina u oba slučaja je \(l+m+1\) gdje su \(l\) i \(m\) stupnjevi polinoma koji se koriste u toj Padéoveoj aproksimaciji. Numerička stabilnost iteracija je objašnjena pomoću teorema koji daje rezultat da su iteracije koje superlinearno konvergiraju prema \(sign(A)\) numerički stabilne, Fréchetova derivacija od iteracijske funkcije u \(S\) je idempotentna i vrijedi da je Fréchetova derivacija od iteracijske funkcije jednaka Fréchetovoj derivacija od \(sign\) funkcije te jednaka \(\frac{1}{2} (H-SHS)\) gdje je \(H\) perturbacijska matrica. Zbog tih rezultata zaključujem da za ograničenu uvjetovanost matrice \(S := sign(A)\) iteracija iz gornjeg teorema je stabilna. Također, isto vrijedi ako \(H\) i \(S\) komutiraju. Što se tiče iteracija, analizirana je i njihova konačnost, odnosno koliko je iteracija potrebno da bi se došlo do rješenja. Dokazan je teorem o granicama za rezidualnu pogrešku \(||X_i-S||\) te relativnu pogrešku \(\frac{||X_i-S||}{||S||}\) za iteracije \(X_i\) što nam pomaže u odabiru kriterija zaustavljanja. Osjetljivost i uvjetovanost matrice su objašnjene pomoću relativnog broja uvjetovanosti funkcije \(sign\). Teorem daje rezultat o donjoj i gornjoj granici za broj uvjetovanosti \(sign\) funkcije u odnosu na matricu \(A\) te matricu \(S\).

Abstract (english)

Matrix sign function is defined in two ways. Both definitions require values of sign function on the spectrum of \(A\). First definition is about Jordan canonial form and the other with polynomial interpolation. Everything is based on the complex coordinate plane so for sign function it's important to know if eigenvalues are on the right or left side of the plane. Function \(sign(A)\) has some useful properties: involution, diagonalizable matrix and commutation with \(A\). Schur algorithm is based on Schur decomposition. The problem is therefore to computing \(sign(T)\) where matrix \(T\) is triangular matrix from decomposition. The complexity of the algorithm is \(O(n^3)\). In total, \(\frac{86}{3}n^3\) flops are needed to get the solution. The next method is Newton's. It uses Newton's iterations. In that chapter, theorem about quadratically convergence of Newton's sign iterations is proven. The other result from that theorem is that iterations will converge slower if the spectral radius is much greater than 1 and also if eigenvalues of \(A\) are very close to the imaginary axe. The method requires \(2in^3\) where \(i\) is the number of used iterations. The complexity of the algorithm is also \(O(n^3)\). An effective way to enhance the initial speed of convergence is to scale the iterations. That's why scaled Newton's iterations exist. They are very similar to the original Newton's iterations. The only difference is that scalar is multiplied by original iteration. There are three types of that positive and real scalar: determinantal, spectral and norm. There is the theorem which tells that scaled Newton's iterations converge to \(sign(A)\). The finite iteration will be after \(d+p-1\) steps where \(d\) is the number of distinct eigenvalues and \(p\) is determined with dimension of the largest Jordan block. Algorithm needs \(2in^3\) flops for \(i\) iterations. There is one more kind of the iterations which is derivatived from formula: \(sign(A) := A(A^2)^{-\frac{1}{2}}\) and their name is Padé iterations. They are determined on rational polynomial functions. The theorem about convergence of Padé iterations contains two cases: global and local convergence. Speed of the convergence in both cases is \(l+m+1\) where \(l\) and \(m\) are degrees of polynomials which are used in that Padé approximation. Numerical stability of iterations is explained by theorem which gives the result that iterations which superlineary converge to \(sign(A)\) are stable. Also, Fréchet derivation of the iteration function in \(S\) is idempotent and it's equal to Fréchet derivation of \(sign\) function. They are both equal to: \(\frac{1}{2} (H-SHS)\) where \(H\) is small perturbation. Because of these results, I conclude that for bounded condition of the matrix \(S := sign(A)\), iteration is stable. That is also valid when \(H\) i \(S\) commute. Also, in relation with iterations, stopping criteria is analyzed. The theorem about residual error and relative error boundaries is also proven. Sensitivity and condition of matrices are explained by relative condition number of the function \(sign\). The result from that part gives the boundaries for condition number of \(sign\) function.

• Keywords: matrična predznak funkcija; Jordanova forma; interpolacijski polinom; Schurov algoritam; Newtonova metoda; Newtonove skalirane iteracije; Padéove iteracije; Padéovaj aproksimacija; Fréchetova derivacija od iteracijske funkcije; konačnost iteracija
• Keywords (english): matrix sign function; Jordan canonial form; polynomial interpolation; Schur algorithm; Newton's model; Newton's sign iterations; Padé iterations; Padé approximation; Fréchet derivation of the iteration function; iterations stopping criteria
• Language: croatian
• URN:NBN: urn:nbn:hr:217:466011
• Study programme: Title: Finance and Business Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-02-07 14:54:23