быстрый и простой поиск единственного экстремума

[Igor_Dmitriev]

У нас есть функция $f(x_1, x_2 ... x_n)$.
Про неё известно, что у неё единственный экстремум, она гладкая и непрерывная, с непрерывными производными всех порядков. Как его найти? Я знаю про методы градиентного спуска, но при единственном экстремуме есть, возможно, более простой и быстрый метод.

И ещё вопрос по немного другой теме:
есть уравнение $x\ln(x) = 1$, его надо численно решить (из соседней темы). предложили использовать последовательность $x_{n+1} = x_n \left( 1- \frac{x_n \ln x_n -1}{x_n +1} \right) $.
Как поняли, что надо использовать именно такую последовательность и как их подбирают? Где про это можно прочесть?

[Legioner93]

По поводу второго вопроса.
$x=e^{W(1)}=\frac{1}{W(1)}$
Для $W(x)$ в википедии есть рекуррентная формула. Правда ничего не знаю о её эффективности. Ряд Тейлора для $W(x)$ тоже есть, но он не сходится в $x=1$. Может можно как-нибудь модифицировать.

Как получена ваша формула не знаю, но она очень похожа на формулы, которые получаются из метода Ньютона.

Для $f(x)=x \ln{x} -1 $ получаем $x_{n+1}=x_n - \frac{x_n \ln{x_n}-1}{\ln{x_n}+1}$. Формула даёт 19 верных знаков после запятой (сверил по $\frac{1}{W(1)}$ в Wolfram Alpha) уже через 5 итераций.

(Код)

#include <stdio.h>
#include <math.h>

main()
{
    long double x=1.0;
    while(1)
    {
        x=x-(x*logl(x)-1)/(logl(x)+1);
        printf("%.19Lf\n",x);
        getchar();
    }
}

[Евгений Машеров]

Единственный экстремум это прекрасно, но он даёт не ускорение поиска, а гарантию того, что поиск не застрянет на локальном оптимуме. Наличие производных высоких порядков, видимо, даёт возможность использовать метод Ньютона или другие методы второго порядка. Методы более высокого порядка редко полезны, и даже второй порядок, с учётом затрат на вычисление матрицы вторых производных и её обращение, может быть не оправдан. Метод сопряжённых направлений даёт почти такую же сходимость, но вторые производные считать не надо.

[Igor_Dmitriev]

Спасибо всем ответившим, частично разобрался с вопросами.

А что делать, если нашёл реккурентную формулу, которая даёт минимум при положительных параметрах многомерной функции, но при отрицательных реккурентный ряд расходится? Оно понятно, почему: решение лежит между положительными и отрицательными параметрами, из особенностей функции вытекает неправильный уход в минус бесконечность, но есть ли способ обойти это?

В вики пишут, что решение можно найти за несколько десятков операций, есть ли что-то менее затратное? Мне не обязательно знать черезчур точное значение.

[ewert]

Евгений Машеров в сообщении #728889 писал(а):

и даже второй порядок, с учётом затрат на вычисление матрицы вторых производных и её обращение, может быть не оправдан.

Затраты на обращение матрицы при не слишком большом количестве параметров сравнительно ничтожны. Действительно проблема -- это дифференцирование (производные могут даже и не браться в явном виде, смотря какая задача); но и это в каждом конкретном случае снимается заменой точного дифференцирования на конечноразностное. Всё это более чем искупается сверхлинейностью сходимости. А вот что воистину проблема в методе Ньютона, так это поиск достаточно хорошего начального приближения, и тут гарантированная единственность минимума как-то не очень спасает.