GramSchmidtprosessi

Gram-Schmidt-prosessiksi kutsutaan lineaarialgebran algoritmia, jolla joukko lineaarisesti riippumattomia vektoreita muunnetaan ortogonaaliseksi tai ortonormaaliksi kattamaan samasta aliavaruudesta. Jos A on m×n matriisi, jonka sarakkeet ovat a_1,...,a_n, prosessi etsii Q:n ja R:n siten, että A = Q R, missä Q:n sarakkeet q_i ovat yksikkövektoreita ja ovat keskenään ortonormaaleja (q_i^T q_j = δ_{ij}) ja R on n×n yläpääteinen.

Käytännön laskenta etenee seuraavasti: v_1 = a_1 ja q_1 = v_1 / ||v_1||. Tämän jälkeen k = 2,...,n: v_k = a_k - sum_{i=1}^{k-1} proj_{q_i}(a_k), jossa proj_{q}(a) = (q^T a) /(q^T q) q. Lopuksi q_k = v_k / ||v_k||. Matriisina R:n alkiot ovat r_{ij} = q_i^T a_j (i ≤ j) ja diagonaalialkiot r_jj = ||v_j||.

Classical Gram-Schmidt voi olla numeerisesti epävakaa, erityisesti jos sarakkeet ovat lähellä riippuvia. Tämän vuoksi käytetään Modified Gram-Schmidt -versiota, jossa orthogonalisaatio toteutetaan yksi kerrallaan aiempien q_i:n suhteen. Myös uudelleenkäynnistys (re-orthogonalization) ja vaihtoehtoiset menetelmät, kuten Householder-reflektoinnit, parantavat vakauden.

Sovellukset ja yleispiirteet: Gram-Schmidt on keskeinen osatekijä QR-dekompositiossa ja least squares -ratkaisussa, sekä osa monien eigenarvoalgoritmien valmistelua. Se toimii sekä reaalisessa että kompleksisessa tilassa; kompleksissa käytetään konjugoitua transponointia.

Historiallisesti nimen takana ovat Jørgen Pedersen Gram ja Erhard Schmidt. Nykyaikaisessa numeerisessa linear algebra -laskennassa sitä käytetään usein vakaammien menetelmien, kuten Householderin, rinnalla.