Konjugaattigradienttimenetelmiä

Konjugaattigradienttimenetelmiä, usein lyhennettynä konjugaattigradientiksi (CG), on joukko numeerisia algoritmeja, joita käytetään lineaaristen yhtälöryhmien ratkaisemiseen. Nämä menetelmät ovat erityisen tehokkaita, kun käsiteltävä matriisi on suuri, harva ja symmetrinen sekä positiivisesti definiitti. Konjugaattigradienttimenetelmät kuuluvat iteratiivisiin ratkaisumenetelmiin, mikä tarkoittaa, että ne tuottavat sarjan approksimaatioita lopulliselle ratkaisulle, jotka paranevat jokaisella iteraatiolla.

Menetelmän perusidea on etsiä ratkaisua lineaariselle yhtälöryhmälle Ax = b käyttäen konjugaattisia suuntia. Nämä suunnat valitaan siten, että ne ovat ortogonaalisia toisiinsa A:n määrittelemän sisäisen tulon suhteen. Jokaisella iteraatiolla tehdään askel valitun konjugaattisen suunnan mukaisesti, joka minimoi virheen kvadraattisessa funktiossa. Algoritmi konvergoi teoriassa yhteen iteraatioon täydellisessä aritmetiikassa, mutta käytännössä koneen tarkkuus ja numeeriset epävakaudet vaativat usein useita iteraatioita.

Konjugaattigradienttimenetelmiä käytetään laajalti tieteellisessä laskennassa, fysiikassa, insinööritieteissä ja koneoppimisessa. Ne ovat tehokkaampia kuin suorat menetelmät, kuten Gaussin eliminointi, kun matriisin koko kasvaa merkittävästi, koska ne eivät vaadi koko matriisin tallentamista muistiin. Algoritmin tehokkuus riippuu matriisin ominaisarvojen jakaumasta; mitä tasaisempi jakauma, sitä nopeampi konvergenssi. Useita variaatioita konjugaattigradienttimenetelmistä, kuten esikonitiontio, on kehitetty nopeuttamaan konvergenssia entisestään.