Введение
Алгоритм математической оптимизации
В математике метод сопряжённых градиентов — это алгоритм для численного решения определённых систем линейных уравнений, а именно тех, матрица которых является положительно полуопределённой. Метод сопряжённых градиентов часто реализуется как итеративный алгоритм, применимый к разреженным системам, которые слишком велики для обработки прямым методом или другими прямыми методами, такими как разложение Холецкого. Большие разреженные системы часто возникают при численном решении уравнений в частных производных или задач оптимизации. Метод сопряжённых градиентов также может использоваться для решения задач оптимизации без ограничений, таких как минимизация энергии. Обычно его приписывают Магнусу Хестену и Эдуарду Стифелю, которые запрограммировали его на Z4 и провели его всестороннее исследование. Метод бисопряжённых градиентов предоставляет обобщение для несимметричных матриц. Различные методы нелинейного сопряжённого градиента используются для поиска минимумов нелинейных задач оптимизации.
Перезапуск
Мы отмечаем, что вычисляется методом градиентного спуска, применяемого к задаче . Аналогично, установка приведет к тому, что будет вычисляться методом градиентного спуска из , то есть, это можно использовать как простую реализацию перезапуска итераций сопряженного градиента. Норма невязки обычно используется в качестве критерия остановки. Норма явной невязки обеспечивает гарантированный уровень точности как в точной арифметике, так и при наличии ошибок округления, когда сходимость естественным образом замедляется. В отличие от этого, амплитуда неявной невязки продолжает уменьшаться, опускается значительно ниже уровня ошибок округления и, следовательно, не может быть использована для определения застоя сходимости.
Свойства конвергенции
Метод сопряжённых градиентов теоретически можно рассматривать как прямой метод, поскольку при отсутствии ошибки округления он выдаёт точное решение после конечного числа итераций, не превышающего размер матрицы. На практике точное решение никогда не достигается, так как метод сопряжённых градиентов неустойчив даже к незначительным возмущениям, например, большинство направлений на практике не являются сопряжёнными из-за вырожденного характера построения подпространств Крылова. Как итеративный метод, метод сопряжённых градиентов монотонно (в энергетической норме) улучшает приближения к точному решению и может достичь требуемой точности после относительно небольшого (по сравнению с размером задачи) числа итераций. Улучшение обычно линейно, и его скорость определяется числом обусловленности матрицы системы: чем больше число обусловленности, тем медленнее улучшение. Если число обусловленности велико, то обычно применяется предварительное обусловливание для замены исходной системы на такую, чтобы число обусловленности новой системы было меньше, см. ниже.
По сравнению с оптимальным методом спуска с наибольшей крутизной
В обоих методах – исходном и методе сопряжённых градиентов с предварительной обработкой – достаточно лишь задать , чтобы добиться их локальной оптимальности, используя поиск вдоль прямой и методы наискорейшего спуска. При такой подстановке векторы 'p' всегда совпадают с векторами 'z', поэтому нет необходимости хранить векторы 'p'. Таким образом, каждая итерация этих методов наискорейшего спуска немного менее затратна по сравнению с итерациями методов сопряжённых градиентов. Однако последние сходятся быстрее, если не используется (сильно) переменный и/или не положительно определённый предварительный обуславливатель, как указано выше.
Метод соединенного градиента как оптимальный контроллер обратной связи для двойного интегратора
Метод сопряжённых градиентов также может быть выведен с использованием теории оптимального управления. В этом подходе метод сопряжённых градиентов возникает как оптимальный регулятор обратной связи для системы двойного интегратора, при этом величины и являются переменными коэффициентами обратной связи.