2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 МСГ для квадратичной функции
Сообщение28.03.2013, 15:21 
Метод сопряженных градиентов для минимизации квадратичной функции работает за не более чем n шагов, где n - размерность пространства, на котором задана функция. Известно, что количество шагов определяется тем, какие собственные числа матрицы, которая задает квадратичную функцию - количество шагов в процессе минимизации - это количество разных собственных чисел.

Может кто-то скинуть ссылку\сказать где объяснение этого факта? Нигде не нашел, но
если все собственные числа совпадают - то сходимость за одну итерацию объясняется так как в методе Ньютона. Либо подайте идею, если конечно это не в лоб по формуле, которая определяет метод, проверяется.

Спасибо.

 
 
 
 Re: МСГ для квадратичной функции
Сообщение28.03.2013, 19:59 
Аватара пользователя
Возьмите какую-нибудь квадратичную форму с диагональной матрицей и с кратными собственными значениями. Затем рассмотрите произвольную прямую, не проходящую через нуль. Это будет типа направление поиска. Затем найдите минимум кадратичной функции на этой прямой. В точке минимума части суммы кв. формы, соответствующие равным собственным значениям, тоже равны. Что как-бы намекает, что поведение метода сопряжённых градиентов на подспространствах, отвечающих одинаковым собств. значениям, одинаково.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group