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

и задачки для интервью.
User avatar
Иоп
Уже с Приветом
Posts: 8832
Joined: 18 Feb 2005 08:00
Location: Yekaterinburg --> Toronto

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

Post by Иоп »

Кто решит x^x = а наиболее простым способом?
Методы приближения приветствуются.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by 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))
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by 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
Posts: 7
Joined: 03 Mar 2003 06:04

Post by random »

Это вы какую точность имеете в виду говоря о сходимости за n итераций?
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

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

Точность double type в C - ~1e-16 относительная ошибка.
User avatar
Иоп
Уже с Приветом
Posts: 8832
Joined: 18 Feb 2005 08:00
Location: Yekaterinburg --> Toronto

Post by Иоп »

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

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

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

PS А почему не существует аналитического решения? И как задать решение одним рядом без итераций? (как будет выглядеть такой ряд?)
User avatar
Иоп
Уже с Приветом
Posts: 8832
Joined: 18 Feb 2005 08:00
Location: Yekaterinburg --> Toronto

Post by Иоп »

anyone?
User avatar
IvanGrozniy
Уже с Приветом
Posts: 10503
Joined: 04 Feb 2004 14:14
Location: Edgewater, NJ

Post by IvanGrozniy »

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

Ряд Тейлора спасет отца демократии. Стоит однако учестб, что функция должна иметь производные n-го порядка в точке x0. Если x0 = 0, то получается ряд Маклорена
You do not have the required permissions to view the files attached to this post.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Иоп wrote:Я вывел следующее:
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)))

которая близка к ответу для очень больших чисел.
Если ето удастся модифицировать, чтобы и при малых аргументах она давала правильный результат...
User avatar
IvanGrozniy
Уже с Приветом
Posts: 10503
Joined: 04 Feb 2004 14:14
Location: Edgewater, NJ

Post by IvanGrozniy »

Самый простой способ метод половинного сечения (частный случай золотого сечения).
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

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

Code: Select all

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

Проблема в том, что при малых a формула для d расходится.
User avatar
Иоп
Уже с Приветом
Posts: 8832
Joined: 18 Feb 2005 08:00
Location: Yekaterinburg --> Toronto

Post by Иоп »

Два дня ломал голову, но так и не понял, октуда получились эти формулы для больших чисел :(
Tigrius
Уже с Приветом
Posts: 266
Joined: 23 Oct 2004 22:07

Post by Tigrius »

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

x = exp(W(ln(a))

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

http://mathworld.wolfram.com/LambertW-Function.html
User avatar
vlad12345
Уже с Приветом
Posts: 605
Joined: 14 Feb 2002 10:01
Location: Russia

Post by vlad12345 »

Немного облегченный частный случай: x ^ x = (1/2) ^ (1/2)
Аналитически решить, конечно, нельзя, но можно угадать (что впрочем не так уж тривиально).
Вроде как-то давно была такая задача на вступительных экзаменах (а может легенда). В МФТИ что-ли.
User avatar
vlad12345
Уже с Приветом
Posts: 605
Joined: 14 Feb 2002 10:01
Location: Russia

Post by vlad12345 »

Никто, значит, не угадал для случая (1/2)^(1/2)
Что ж, сообщаем ответ: множество ВСЕХ решений {1/2, 1/4}.
Желающие могут доказать, что других решений нет.
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

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

А я решил, что это слишком просто. :)
User avatar
vlad12345
Уже с Приветом
Posts: 605
Joined: 14 Feb 2002 10:01
Location: Russia

Post by vlad12345 »

Если немного переиначить, получится вполне неплохая задачка в рамках школьной птограммы:
При каких значениях параметра a уравнение
x ^ x = a ^ a
имеет 1 решение, 2 решения, ...?

Return to “Головоломки”