лекция. Лекция План лекции
![]()
|
Лекция 6. План лекции. Метод наискорейшего градиентного спуска. Основные понятия. Построение коэффициента спуска. Теорема о сходимости. Проблема собственных значений. Особенности задачи о собственных значениях. Метод наискорейшего градиентного спуска. Рассмотрим СЛАУ с положительно определенной симметричной матрицей: АХ=b Пусть ![]() ![]() ![]() Поскольку A – положительно определена имеет место (Ax, x)≥0 для каждого x, => ![]() ![]() Будем рассматривать задачу минимизации функции F, приближения к решению будем получать итерационным образом ![]() Так как ![]() ![]() Требуется выбрать параметр ![]() ![]() ![]() В этом случае мы получим метод, называемый методом наискорейшего градиентного спуска. Найдем параметр ![]() ![]() ![]() ![]() Обозначим ϕ ![]() ![]() Вычислим ϕ ![]() ![]() ![]() ![]() Минимум будет достигаться при ![]() ![]() ![]() Теорема (о скорости сходимости) Пусть собственные числа матрицы А удовлетворяют соотношению 0≤m<λ Тогда при любом выборе начального приближения метод наискорейшего спуска сходится и верна следующая оценка погрешности ![]() Таким образом, метод сходится со скоростью геометрической прогрессии со знаменателем ![]() Метод требует на каждом шаге 2 умножений матрицы на вектор 2 ![]() Можно преобразовать вычисление формулы ![]() ![]() ![]() Тогда ![]() В процессе итераций запоминаются векторы ![]() ![]() Геометрическая интерпретация метода: F(x) – положительно опр. квадратичная форма, линии уровня F(x) – эллипсоиды, (при m=2 - эллипсы). Движемся в направлении, противоположном градиенту до точки с наименьшим значением на этой прямой ![]() Глава 2. Задача о собственных значениях.. Проблема собственных значений. Рассмотрим матрицу А(m x m) как линейный оператор, задающий минимальное преобразование векторного пр-ва y = Ax. Если ![]() Данное равенство можно переписать в виде ![]() ![]() Если раскрыть определитель, то получаем множители степени m относительно λ, т.е. ![]() ![]() Если ![]() Обычно удобно преобразовывать матрицу прежде чем вычислять собственные числа и векторы. Матрица А в некоторой системе координат (х, у) осуществляет преобразование Ах = у. В другой системе координат (ζ, η) это же преобразование осуществляется матрицей S: ![]() ![]() ![]() Матрицы A и B называются подобными. Теорема: Подобные матрицы имеют одинаковые характеристические полиномы (соответственно одинаковые характеристические числа). Действительно: ![]() Следствие: подобные матрицы имеют одинаковое собственное число, включая их кратность. Мы рассмотрим методы отыскания собственных чисел и векторов. В некоторых задачах требуется получиться все собственные числа, а иногда и все собственные векторы – это полная проблема собственных значений. В других случаях нужно найти какое-то собственное число (максимальное, наиболее к какому-то значению и пр.) – это частичная проблема собственных значений. Вторая задача не является частным случаем первой, т.к. нет смысла каждый раз находить все. Чем сложна задача нахождения собственных векторов и собственных чисел? Если вычислить характеристический полином ![]() ![]() ![]() Примерно до середины XX-го века строились методы, рассчитанные на быстрое вычисление корней характеристического многочлена, а далее искались его решения. Такие методы назывались прямыми. Такие методы для больших матриц очень неэффективны, по указанным выше причинам. В настоящее время разработано много итерационных методов, в которых после преобразований матрицы мы получаем в явном виде собственные числа. Контрольные вопросы. В чём суть метода наискорейшего градиентного спуска для решения СЛАУ? Для систем с какими матрицами применяется метод наискорейшего градиентного спуска? Какой функционал минимизируется в методе наискорейшего спуска для СЛАУ вида AX=b? Из каких условий выбирается шаг спуска? Каковы условия сходимости метода наискорейшего градиентного спуска для решения СЛАУ? Каковы недостатки метода наискорейшего градиентного спуска для решения СЛАУ? Что такое полная проблема собственных значений? Что такое частичная проблема собственных значений? В чём сложность задачи о собственных значениях? Какие преобразования можно совершать с матрицей, чтобы её собственные числа не изменились? |