Когда речь заходит о решении систем линейных уравнений прямыми методами, первым на ум приходит классическое LU-разложение. Однако в вычислительной математике, статистике и машинном обучении мы крайне часто сталкиваемся с матрицами особого класса — симметричными и положительно определенными. Для таких «идеальных» матриц применение общего LU-разложения является избыточным и неэффективным. Французский военный геодезист и математик Андре-Луи Холецкий еще в начале XX века разработал алгоритм факторизации, который учитывает симметрию задачи, сокращая вычислительные затраты и требования к памяти ровно в два раза. Разложение Холецкого стало незаменимым инструментом в финансовом моделировании, фильтрации сигналов и оптимизации.

Когда классические итерационные методы (такие как метод Якоби или Зейделя) сталкиваются с плохо обусловленными системами уравнений астрономических размеров, их сходимость становится неприемлемо медленной. Настоящую революцию в вычислительной линейной алгебре произвело появление методов в подпространствах Крылова, венцом которых является метод сопряженных градиентов (Conjugate Gradient method, CG). Разработанный в 1952 году Хестенсом и Штифелем, этот алгоритм был изначально задуман как прямой метод, но его истинная мощь раскрылась именно в итерационном применении. Сегодня это абсолютный стандарт де-факто для решения гигантских разреженных симметричных положительно определенных систем, возникающих при дискретизации дифференциальных уравнений в частных производных.

Когда размерность матрицы коэффициентов в системе линейных алгебраических уравнений достигает миллионов (что типично для задач теплопроводности, гидродинамики или квантовой химии), прямые методы решения, такие как метод Гаусса или LU-разложение, становятся бессильны. Они требуют кубического времени O(n^3) и гигантских объемов оперативной памяти. Более того, физические матрицы часто являются разреженными (состоят в основном из нулей), а прямые методы превращают эти нули в ненулевые элементы (fill-in), уничтожая структуру памяти. Решением этой проблемы являются итерационные методы. Они работают по принципу постепенного улучшения ответа: задается начальное, случайное приближение, которое шаг за шагом уточняется, пока не будет достигнута требуемая точность.