Забавное уравнение

[Иоп]

Кто решит x^x = а наиболее простым способом?
Методы приближения приветствуются.

[venco]

Во первых, аналитически оно не решается.
Но достаточно легко решается методом Ньютона.

1. Метод первого порядка.
Простая формула, но сходится не очень быстро, особенно около точки минимума - за 23 итерации.
x = 1+ln(a)
x = (x+ln(a))/(1+ln(x))

2. Метод второго порядка.
Формула немного сложнее, зато сходится в худшем случае за 5 итераций.
x = sqrt(1+2ln(a))
x = x*(sqrt(ln(x)^2+2ln(a)/x+1)-ln(x))

[venco]

В обоих вариантах можно подправить константу в начальном приближении, чтобы ускорить сходимость.

1.
x = 2/e+eps+ln(a), где, например, eps = 1e-6.
Будет сходиться в худшем случае за ~12 итераций.

2.
x = sqrt(1/e^2 + 2/e + ln(a)^2).
Почти всегда будет сходиться за 3 итерации.

[random]

Это вы какую точность имеете в виду говоря о сходимости за n итераций?

[venco]

Это вы какую точность имеете в виду говоря о сходимости за n итераций?

Точность double type в C - ~1e-16 относительная ошибка.

[Иоп]

Я вывел следующее:
x = -c*ln c + SQRT ([c*ln c]^2 + c^2 + 2c*ln a),
где с это х из предыдущей итерации.

Юзал формулу Тейлора, отбросил члены выше второго порядка и решал квадратичное уравнение.

А можно это решить как-нибудь позаковыристей, с тригонометрией, через ряды Фурье, например?

PS А почему не существует аналитического решения? И как задать решение одним рядом без итераций? (как будет выглядеть такой ряд?)

[Иоп]

anyone?

[IvanGrozniy]

И как задать решение одним рядом без итераций? (как будет выглядеть такой ряд?)

Ряд Тейлора спасет отца демократии. Стоит однако учестб, что функция должна иметь производные n-го порядка в точке x0. Если x0 = 0, то получается ряд Маклорена

[venco]

Я вывел следующее:
x = -c*ln c + SQRT ([c*ln c]^2 + c^2 + 2c*ln a),
где с это х из предыдущей итерации.

Это такая же формула, что и у меня под номером 2.

Юзал формулу Тейлора, отбросил члены выше второго порядка и решал квадратичное уравнение.

Это и есть метод Ньютона: http://mathworld.wolfram.com/NewtonsMethod.html

А можно это решить как-нибудь позаковыристей, с тригонометрией, через ряды Фурье, например?

Можно, но обычно метод последовательных приближений самый быстрый.
Сравните 3 итерации по Ньютону и несколько десятков членов ряда.
Например, корень все компьютеры считают именно этим методом.
Да и простое деление очень больших чисел быстрее считать по Ньютону, используя умножение и сложение.

PS А почему не существует аналитического решения? И как задать решение одним рядом без итераций? (как будет выглядеть такой ряд?)

Мне кажется многообещающей формула

Code: Select all

    ln(a) - ln(ln(a))
-------------------------
ln(ln(a)) - ln(ln(ln(a)))

которая близка к ответу для очень больших чисел.
Если ето удастся модифицировать, чтобы и при малых аргументах она давала правильный результат...

[IvanGrozniy]

Самый простой способ метод половинного сечения (частный случай золотого сечения).

[venco]

Ещё лучше формула:

Code: Select all

b = ln(a)
c = ln(1+b)
d = c-ln(c-ln(c-ln(c....)))
x = b / d

Проблема в том, что при малых a формула для d расходится.

[Иоп]

Два дня ломал голову, но так и не понял, октуда получились эти формулы для больших чисел

[Tigrius]

Это уравнение решается в специальных функциях (хотя, конечно, это жульничество , не можем решить уравнение - вводим новую функцию):

x = exp(W(ln(a))

где W - это W функция Ламберта:

http://mathworld.wolfram.com/LambertW-Function.html

[vlad12345]

Немного облегченный частный случай: x ^ x = (1/2) ^ (1/2)
Аналитически решить, конечно, нельзя, но можно угадать (что впрочем не так уж тривиально).
Вроде как-то давно была такая задача на вступительных экзаменах (а может легенда). В МФТИ что-ли.

[vlad12345]

Никто, значит, не угадал для случая (1/2)^(1/2)
Что ж, сообщаем ответ: множество ВСЕХ решений {1/2, 1/4}.
Желающие могут доказать, что других решений нет.