Функциональное уравнение f(f(x))

[zykov]

Функция [math]f(x) такова, что [math]f(f(x))=x^2-x+1.
Найти [math]f(0)?

Ну и ещё от себя дополнительный вопрос - что это за функция [math]f(x)?
Если не найти её явно, то хотя бы описать как-то.

[Ian]

Навскидку можно сказать, что график f(x) зажат между графиками [math]x^2-x+1,\max(x,(1-x))Это следует из графического представления f(f(x)) как гуляния по вертикалям и горизонтали между графиками f и x, а также функция в правой части не меняется при замене х на 1-х

[zykov]

Можно сделать замену [math]g(y)=f(y+\frac12)-\frac12.
Получится [math]g(g(y))=y^2+\frac14.
Что несколько проще (напоминает Julia set), но принципиально не помогает.

[Ian]

Так что, получается, что решение f(x) не единственное? У меня любое предположение [math]f\left(\frac 12\right)=a\in\left(\frac 12;\frac 34\right) не приводит к противоречию. Тогда непонятно, как доказать что для любого решения f(x)=f(1-x)

[zykov]

Там надо найти [math]f(0), а не [math]f(\frac12).
Насчёт самой функции, то если брать разрывные, то там их много. Если непрерывные, то вроде одна (надо ещё доказать).

[Ian]

Пусть мы ищем решение на луче [math]x\geq \frac 12 в классе монотонных непрерывных функций. Тогда положим [math]h_0(x)=x,\;\phi(x)=x^2-x+1 и устроим итерации , как по методу Ньютона нахождения корня из числа [math]h_{n+1}=\frac 12\left(h_n+\frac a{h_n}\right) только мы извлекаем "корень" из отображения [math]\phi
[math]h_{n+1}(x)=\frac 12\left(h_n(x)+\phi (h_n^{-1}(x))\right)
По идее, это сходится очень быстро. Но цикл нахождения обратной функции по табулированной надо сделать очень тщательно.
А дальше можно продолжить предельную функцию левее луча по непрерывности [math]f(x)=f(1-x) и получится f(0)=1 но не обязательно это единственный ответ

[zykov]

С [math]f(0) там просто.
Сначала найдём стационарные точки [math]\phi(x)=x, это [math]x^2-x+1=x или [math](x-1)^2=0.
Т.е. стационарная точка только одна. Для квадратной функции могло бы быть две, тогда ситуация была бы другая.
Из [math]\phi(x)=1, [math]x^2-x+1=1 видим, что в эту точку 1 можно попасть из 1 и из 0.

Сначала разберемся с 1. Пусть [math]f(1)=a, тогда [math]f(a)=f(f(1))=1.
Значит [math]f(f(a))=f(1)=a, но [math]f(f(a))=a^2-a+1.
Отсюда полчаем [math]a=1. Была бы вторая стационарная точка, она могла бы быть тоже значением.

Для 0 аналогично. Пусть [math]f(0)=b, тогда [math]f(b)=f(f(0))=1.
Значит [math]f(f(b))=f(1)=a=1, но [math]f(f(b))=b^2-b+1.
Отсюда полчаем [math]b^2-b+1=1, т.е. [math]b=0 или [math]b=1.
[math]b=0 не подходит, т.к. тогда [math]f(0)=0, значит [math]f(f(0))=f(0)=0, что неверно.
Остаётся [math]b=1, который ничему не противоречит.
Значит [math]f(0)=1.

[zykov]

Насчёт построения [math]f(x) есть такое соображение.
При больших [math]x примерно будет [math]\phi(x) \approx x^2.
Тогда для [math]f(x) подойдёт [math]f(x) \approx x^{\sqrt 2}. Есть ли другие гладкие?

[zykov]

Точка 1 - стационарная точка [math]\phi(x).
Если из некоторой точки [math]a_0 строить последовательность [math]a_{n+1}=\phi(a_n), то для [math]\frac12 \leq a_0 <1 она будет стремиться к [math]1-0.
Для [math]a_0 > 1 она будет стремиться к [math]+\infty. Здесь последовательность можно и влево продолжить (если брать положительный корень [math]a_{n-1}=\frac12+\sqrt{a_n-\frac34}), тогда влево эта двухсторонняя последовательность будет стремится к [math]1+0. (Для случая менее 1 влево не продолжается, там в комплексные уйдёт.)

[Ian]

С [math]f(0) там просто.
Сначала найдём стационарные точки [math]\phi(x)=x, это [math]x^2-x+1=x или [math](x-1)^2=0.
Т.е. стационарная точка только одна. Для квадратной функции могло бы быть две, тогда ситуация была бы другая.
Из [math]\phi(x)=1, [math]x^2-x+1=1 видим, что в эту точку 1 можно попасть из 1 и из 0.

Сначала разберемся с 1. Пусть [math]f(1)=a, тогда [math]f(a)=f(f(1))=1.
Значит [math]f(f(a))=f(1)=a, но [math]f(f(a))=a^2-a+1.
Отсюда полчаем [math]a=1. Была бы вторая стационарная точка, она могла бы быть тоже значением.

Для 0 аналогично. Пусть [math]f(0)=b, тогда [math]f(b)=f(f(0))=1.
Значит [math]f(f(b))=f(1)=a=1, но [math]f(f(b))=b^2-b+1.
Отсюда полчаем [math]b^2-b+1=1, т.е. [math]b=0 или [math]b=1.
[math]b=0 не подходит, т.к. тогда [math]f(0)=0, значит [math]f(f(0))=f(0)=0, что неверно.
Остаётся [math]b=1, который ничему не противоречит.
Значит [math]f(0)=1.

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

[zykov]

Насчёт симметричности относительно [math]\frac12, то тоже можно аналогично нулю сделать.
Пусть у нас уже есть непрерывная [math]f(x) для [math]x \geq \frac12.
Возьмём [math]x_1 < \frac12 и обозначим [math]f(x_1)=c.
Тогда [math]f(c)=f(f(x_1))=x_1^2-x_1+1 \geq \frac34, что попадает в область, где мы уже знаем [math]f(x).
Значит [math]f(f(c))=f(x_1^2-x_1+1), что должно быть больше [math]\frac34, т.к. [math]f(x) должна возрастать при [math]x \geq \frac12 (надо бы доказать).
Значит [math]c=\frac12 \pm \sqrt{f(x_1^2-x_1+1)-\frac34}. Для разрывной и минус перед корнем подойдёт, но из непрерывности в [math]\frac12 и ниже останется только плюс. (Используется, то [math]f(\frac12) > 0.)
Значит [math]c=f(1-x_1).

[zykov]

Ещё можно получить разложение в ряд около стационарной точки [math]x=1.
Если обозначить [math]v(y)=f(1+y)-1, то [math]v(v(y))=y^2+y.
Начнём раскладывать [math]v(y) в нуле в ряд методом неопределенных коэффициентов.
Пусть [math]v(y)=a_1 y+a_2 y^2+a_3 y^3+o(y^3).
Тогда [math]v(v(y))=a_1 (a_1 y+a_2 y^2+a_3 y^3)+a_2 (a_1 y+a_2 y^2+a_3 y^3)^2+a_3 (a_1 y+a_2 y^2+a_3 y^3)^3+o(y^3)=
[math]=a_1^2 y + a_2 a_1 (1+a_1)y^2+((a_1^3+a_1)a_3+2 a_1 a_2^2) y^ + o(y^3)

Отсюда [math]a_1^2=1, т.е. [math]a_1=\pm 1.
Далее, [math]a_2 a_1 (1+a_1)=1. Значит [math]a_1=-1 не подходит, отстаётся [math]a_1=1 и получается [math]a_2=\frac12.
Далее [math](a_1^3+a_1)a_3+2 a_1 a_2^2 = 0, значит [math]2 a_3+\frac12=0, т.е. [math]a_3=-\frac14.

Получим [math]f(x)=x+\frac12 (x-1)^2-\frac14 (x-1)^3+o((x-1)^3).

Можно этот процесс и дальше продолжить.
Автоматизировал его на wxMaxima и вот что получается.
[math]v(y)=y+\frac{{{y}^{2}}}{2}-\frac{{{y}^{3}}}{4}+\frac{{{y}^{4}}}{4}-\frac{5 {{y}^{5}}}{16}+\frac{27 {{y}^{6}}}{64}-\frac{9 {{y}^{7}}}{16}+\frac{171 {{y}^{8}}}{256}-\frac{69 {{y}^{9}}}{128}-\frac{579 {{y}^{10}}}{2048}+
[math]+\frac{10689 {{y}^{11}}}{4096}-\frac{60261 {{y}^{12}}}{8192}+\frac{116535 {{y}^{13}}}{8192}-\frac{304555 {{y}^{14}}}{16384}+\frac{268707 {{y}^{15}}}{32768}+
[math]+\frac{7942071 {{y}^{16}}}{262144}-\frac{19570935 {{y}^{17}}}{262144}+\frac{9537731 {{y}^{18}}}{1048576}+\frac{1117836325 {{y}^{19}}}{4194304}-\frac{630737297 {{y}^{20}}}{8388608}-
[math]-\frac{52310180977 {{y}^{21}}}{16777216}+\frac{618435378229 {{y}^{22}}}{67108864}+\frac{523526983623 {{y}^{23}}}{67108864}-\frac{3672122551119 {{y}^{24}}}{33554432}+\frac{8661572895987 {{y}^{25}}}{67108864}+
[math]+\frac{1205887924659627 {{y}^{26}}}{1073741824}-\frac{8604836834766111 {{y}^{27}}}{2147483648}-\frac{77855893119175779 {{y}^{28}}}{8589934592}+
[math]+\frac{361603115910936909 {{y}^{29}}}{4294967296}-\frac{152305703959002777 {{y}^{30}}}{17179869184}-\frac{13663291494961963791 {{y}^{31}}}{8589934592}+
[math]+\frac{930319681643781465159 {{y}^{32}}}{274877906944}+\frac{7744345260199075453761 {{y}^{33}}}{274877906944}-\frac{74957616592443792206343 {{y}^{34}}}{549755813888}-
[math]-\frac{237621055201522057591119 {{y}^{35}}}{549755813888}+\frac{19848927534546151309514391 {{y}^{36}}}{4398046511104}+\frac{55865315152940191973506305 {{y}^{37}}}{17592186044416}-
[math]-\frac{10012538507216110592697218313 {{y}^{38}}}{70368744177664}+\frac{13051600707461268121142637357 {{y}^{39}}}{70368744177664}+
[math]+\frac{311204897997769328562593792487 {{y}^{40}}}{70368744177664}+...
Правда складывается впечатление, что этот ряд расходится в любой сколь угодно малой окрестности (точно трудно сказать, т.к. общая формула для коэффициентов не получается). Когда брал ряд до порядка 30 и строил график, то он шел вразнос около 0.8. Когда увеличил порядок до 60, то график шел вразнос уже около 0.4. Хотя когда для синуса берешь больше порядков, то расширяется область, где график похож на синус.

PS: Это нормально, что ряд Тэйлора не сходится ни в какой малой окрестности?

[Ian]

Ненормально. В классическом примере неаналитической, но всюду бесконечно дифференцируемой функции [math]\exp\left( -\frac 1{x^2}\right) ряд Тейлора в 0 сходится к 0 а не к ней.

[Ian]

Пусть мы ищем решение на луче [math]x\geq \frac 12 в классе монотонных непрерывных функций. Тогда положим [math]h_0(x)=x,\;\phi(x)=x^2-x+1 и устроим итерации , как по методу Ньютона нахождения корня из числа [math]h_{n+1}=\frac 12\left(h_n+\frac a{h_n}\right) только мы извлекаем "корень" из отображения [math]\phi
[math]h_{n+1}(x)=\frac 12\left(h_n(x)+\phi (h_n^{-1}(x))\right)
По идее, это сходится очень быстро. Но цикл нахождения обратной функции по табулированной надо сделать очень тщательно.

Я так был доволен этим методом. Действительно , для монотонных [math]\phi (x)=kx и более нетривиальной [math]\phi (x)=x^3+1 сходится быстро. А для немонотонной мы ограничиваем область определения, а область значений [math]h_n оказывается уже, приходится экстраполировать и никакой сходимости наблюдать не удалось

[zykov]

Source of the post приходится экстраполировать и никакой сходимости наблюдать не удалось

Можно для начала ограничиться областью [math]x > 1. Она самозамкнута.

[zykov]

Выше я писал про двухстороние последовательности.
Для каждой точки [math]a_0 \in [2, 3) будет такая последовательность. Слева стремится к 1+0, справа к плюс бесконечности.
Причем каждая точка [math]x > 1 будет принадлежать ровно одной такой последовательности.

На этой области можно построить [math]f(x), не обязательно непрерывную (даже скорее разрывную).
Разбиваем все эти последовательности на пары ([math]a_n и [math]b_n) каким-то образом, для каждой пары выбираем целое число [math]k, тоже любое.
И определяем [math]f(a_n)=b_{n+k}, [math]f(b_{n+k})=a_{n+1}.

[zykov]

Для области [math][\frac12, 1) можно сделать похожим образом.
Для каждой [math]a_0 \in [\frac12, \frac34) будет односторонняя последовательность стремящаяся к 1-0.
Тоже можно разбить на пары и построить функцию.
Все точки [math]x \geq \frac34 будут иметь прообраз.
Точки в [math][\frac12, \frac34) не будут иметь прообраза.

[Ian]

Source of the post приходится экстраполировать и никакой сходимости наблюдать не удалось

Можно для начала ограничиться областью [math]x > 1. Она самозамкнута.

Там сразу получилось, скучный график похожий на [math]x^{\sqrt 2}

[zykov]

Я по-другому строил [math]f(x).
Сначала определим [math]\phi_k(x), как [math]\phi_1(x)=\phi(x) и [math]\phi_{k+1}=\phi(\phi_k(x)), т.е. [math]\phi(x) вложена в себя [math]k раз.
Аналогично, [math]\phi_k^{-1}(x) - это вложенная в себя обратная (там где корень с плюсом).
Тогда определим [math]F_k(x)=\phi_k^{-1}\left((\phi_k(x))^{\sqrt 2}\right).
Тогда при [math]x>1 будет [math]f(x)=\lim_{k \to \infty} F_k(x).

Например для [math]\hat f(x)=\begin{cases} многочлен \; до \; 10 \; степени \; при \; 1<x<1.1 \\ F_{16}(x) \; при \; x \geq 1.1 \end{cases}
Выражение [math]\hat f(\hat f(x)) будет примерно равно [math]x^2-x+1 с точностью [math]10^{-10} около 1.1.
И точность быстро улучшается ближе к 1 и дальше в сторону роста x.

Аналогично, при [math]\frac12 \leq x <1 можно взять [math]G_k(x)=\phi_k^{-1}\left(\,g(\phi_k(x))\,\right), где [math]g(x) - приближение многочленом [math]f(x) около 1.
Тут первого члена [math]x недостаточно. Нужно взять хотя бы квадратный [math]x+\frac12(x-1)^2=\frac{x^2+1}{2}. Его вобщем и достаточно для предела. Если практически считать, то можно порядок многочлена повыше взять.
Тут правда медленнее сходится, нужно брать большие [math]k для хорошей точности. Особенно плохо сходится около [math]x=\frac12.
Вот график для [math]G_8(G_8(x)):

ff.png (18.97 KiB) 8809 просмотра

Вроде наихудшая точность 0.5% получается при [math]x=\frac12.
[math]G_8(\frac12) \approx 0.6877, интересно, как бы поточнее найти [math]f(\frac12).

[zykov]

Вот сама [math]G_8(x):

ff_g8.png (30.97 KiB) 8809 просмотра