метод Ньютона

[lamerok]

Для поиска минимума некоторой функции $f(x)$ ($x$ — вектор) методом Ньютона второго порядка пользуются стандартной итерационной формулой:

$x^{k+1}=x^k-(f''(x^k))^{-1}f'(x^k).$

То есть в данном случае нужно будет дважды вычислять градиент функции в точке $x^k$. Здесь все понятно. Заглянул в википедию, увидел формулу:

$x^{k+1}=x^k-H^{-1}(x^k)\nabla f(x^k)$

Я знаю, что гессиан — это определитель матрицы вторых производных. Вопрос: эти формулы равносильны? Если да, то зачем записывать в форме с гессианом? Этим они хотят подчеркнуть, что $x$ — вектор? Или я что-то не понимаю?

[мат-ламер]

Гессиан - это матрица из вторых производных. Её можно записывать как и в первой формуле. Так что обе формулы равносильны. Градиент два раза вычислять не нужно.

[lamerok]

мат-ламер
Почему не нужно?

[мат-ламер]

Во-первых, в формуле один градиент (левее - это вторая производная). Но, если даже он там и был, то зачем его второй раз вычислять в одной и той же точке?

[lamerok]

Все, разобрался. Переклинило что-то :) Спасибо.

[lamerok]

мат-ламер

Есть еще вопрос. При вычислении оптимального шага согласно формуле (при одномерной минимизации)

$ h^k= \arg \min_h f\left(x^k-hH^{-1}(x^k) \nabla f(x^k)\right) $

нужно нормировать вектор градиента или же нормировать вектор, полученный в результате произведения матрицы Гессе и вектора градиента?

[мат-ламер]

Для той формулы, что Вы написали - без разницы. Главное, вектор задаёт направление поиска.

[lamerok]

Да, я тоже заметил, что в разных источниках пишут то норму вектора, то без нормы. Это касательно обычного градиентного метода с оптимальным шагом. Вот и в методе Ньютона у меня встал такой вопрос. Спасибо за ответ :)

[lamerok]

мат-ламер в сообщении #346071 писал(а):

Для той формулы, что Вы написали - без разницы. Главное, вектор задаёт направление поиска.

А можно ли вообще использовать в методе Ньютона и градиентном метода в качестве остановки равенство вычесленного шага нулю? Ведь, фактически, при шаге, равном нулю, мы не сдвигаемся в новую точку. Это помимо условий $|f_{n-1}-f_n| \leq eps$ и $||x_{n-1}-x_n|| \leq eps$, разумеется.

[мат-ламер]

Из-за погрешностей вычисления вероятность получения ровно нуля исчезающе малая.

[lamerok]

Ну, не нулю, конечно :) Например, 1e-10.

[мат-ламер]

Можно.

[lamerok]

Спасибо :)