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

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 18 авг 2022, 15:01

zykov писал(а):Source of the post как бы поточнее найти [math].
Вроде получается 0.691274562 (это [math] если брать многочлен 4-ой степени).
Для многочлена 5ой степени вроде стабилизируется на 0.6912745628104900 (16 цифр для double float).
Повышение степени многочлена со 2-ой до 4-ой значительно улучшает точность.
Вот графики [math] от [math] для многочленов 2ой, 3ей и 4ой степеней:
ff_234.png
ff_234.png (35.56 KiB) 9600 просмотра

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 18 авг 2022, 17:13

Описанное Вами как раз свидетельствует в пользу того, что непрерывное решение в области [math] не единственно и может иметь разные [math] и разный порядок гладкости. Собственно, и на луче, если итерации имеют поточечный предел в классе непрерывных монотонных функций, то он удовлетворяет уравнению и будет непрерывным и монотонным. Но кто сказал что это единственное решение в этом классе . Верно в данном случае только то, что совпадение двух соседних итераций (по моей формуле Ньютона) равносильно тому, что они совпали и с решением уравнения. Но в принципе - с другой начальной функции можно было прийти к другому решению.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 18 авг 2022, 17:29

Не вижу, откуда может взяться неединственность.
Вот определили мы непрерывно [math] в малой, но конечной, области [math].
Тут должно быть [math].
А определили по многочлену, который тем точнее, чем меньше область.

Далее, для точки [math] берем точку [math] вне нашего интервала.
И определяем [math].
Проделав это для всех точек [math] расширим область, где знаем значение функции, до [math].
Далее, повторяем это опять и за конечное количество шагов расширим область до [math].

Единственная неоднозначность в [math], где можно было бы взять корень с минусом. Но из непрерывности корень должен быть с плюсом. А так, разрывных функций конечно много можно сделать.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 19 авг 2022, 03:54

zykov писал(а):Не вижу, откуда может взяться неединственность.
Вот определили мы непрерывно [math] в малой, но конечной, области [math].
Тут должно быть [math].
А определили по многочлену, который тем точнее, чем меньше область.

Далее, для точки [math] берем точку [math] вне нашего интервала.
И определяем [math].
Проделав это для всех точек [math] расширим область, где знаем значение функции, до [math].
Далее, повторяем это опять и за конечное количество шагов расширим область до [math].

Я утверждаю, что это конечное число шагов имеет порядок [math]. У нас же правило итераций от [math] вперед [math]. Для итераций вида [math] есть теоремы о скорости сходимости [math] к [math]- корню уравнения [math]:
Если это простой корень, то скорость сходимости геометрическая[math]-очевидно по определению производной.Если там касание 2-го порядка, то [math], где С пропорционально второй производной в точке. А например для 3-го порядка на старом форуме была олимпиадная задачка [math], тогда [math], где тройка взялась от коэффициента -1/6 в разложении синуса, а вовсе не зависит от [math].И также не зависит от того, синус там был или просто похожая на синус. То есть, зная только третий член асимптотики разложения [math], определить с чего начались итерации -невозможно (а в случае геометрической сходимости можно было).А тут, зная номер итерации и асимптотику функции, мы не восстановим начало, оно будет разным для разных функций с такой асимптотикой

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 19 авг 2022, 20:19

Ian писал(а):Source of the post Я утверждаю, что это конечное число шагов имеет порядок [math].
Да, это так.
Последовательность [math] будет приближатся к 1 слева медленно, как [math].
Про остальное, не понял, как оно даёт неоднозначность.

Да, где я говорю, что вблизи 1 мы заменяем приближенно [math] многочленом, то тут конечно возникают вопросы, что оно всё таки неточно, и может там какие-то проблемы будут.
Но это можно и построже расписать.
Так для [math] в малой области [math] можно записать строгое неравенство:
[math]
([math] чуть больше 1, чтобы компенсировать добавку [math].)
Размер диапазона пропорционален [math].
Когда мы применяем [math] раз [math], то этот диапазон каждый раз раздувается на величину производной этой функции. Производная там примерно [math], произведение таких множителей [math] растёт как [math].
Т.е. изначалный диапазон [math] будет умножен в итоге примерно на фактор [math], что даст конечный диапазон [math].
Значит уменьшая [math] мы будет зажимать значение например [math] всё точнее вплоть до нуля. И места для неоднозначности там просто не остаётся.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 20 авг 2022, 07:09

zykov писал(а):Когда мы применяем [math] раз [math], то этот диапазон каждый раз раздувается на величину производной этой функции. Производная там примерно [math], произведение таких множителей [math] растёт как [math]

Я не говорю, что доказал неоднозначность, я просто сомневаюсь. Это похоже на доказательство того, что раз [math], то и [math]
Вы можете, как начали с верных неравенств, так неравенствами и довести до оценки точности определения f(1/2)?
И кстати, этим мы докажем, что дважды дифференцируемая в 1це функция f(x) единственна? Или сколько раз дифференцируемая?

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 21 авг 2022, 11:25

для промежутка от 0,5 до 1 я внес очевидное изменение в итерации Ньютона [math], те же [math]
Шаг сетки 0,0002 и значит такова же точность нахождения обратной функции на каждом шаге. Поэтому могу дать [math] только с прогнозируемым отклонением 0,0001. Для большей точности надо уменьшить шаг сетки.
h10.png
h10.png (37.75 KiB) 9579 просмотра

А вот 10 шагов на все заведомо хватит. Единственность в классе непрерывных и неубывающих доказать не могу, просто это одно из решений, интересно сравнить с Вашим поточечно (много значений поудалял, чтобы влезло в формат форума)

Код: Выбрать все

0,5   0,691174219
0,5002   0,691174414

0,5102   0,691262016
0,5104   0,691262215

0,53   0,693094238
0,5302   0,693094445
0,55   0,695752051
0,6   0,708386328
0,6002   0,708574063
0,6998   0,754898945
0,7   0,754900781
0,7002   0,755188945
0,7488   0,785798732
0,749   0,785997462
0,7492   0,785998926
0,7494   0,786198438
0,7496   0,786199902
0,7498   0,786400586
0,75   0,786561035
0,7502   0,786603906
0,7504   0,786949902
0,8   0,822498828
0,8002   0,822599922
0,9   0,9052
0,9002   0,905399961
0,99   0,990000098
0,9902   0,990200094
0,9904   0,99040009
0,9906   0,990600086
0,9908   0,990800083
0,991   0,991000079
0,9912   0,991200076
0,9914   0,991400072
0,9916   0,991600069
0,9918   0,991800066
0,992   0,992000062
0,9922   0,992200059
0,9924   0,992400056
0,9926   0,992600053
0,9928   0,992800051
0,993   0,993000048
0,9932   0,993200045
0,9934   0,993400043
0,9936   0,99360004
0,9938   0,993800038
0,994   0,994000035
0,9942   0,994200033
0,9944   0,994400031
0,9946   0,994600028
0,9948   0,994800026
0,995   0,995000024
0,9952   0,995200022
0,9954   0,995400021
0,9956   0,995600019
0,9958   0,995800017
0,996   0,996000016
0,9962   0,996200014
0,9964   0,996400013
0,9966   0,996600011
0,9968   0,99680001
0,997   0,997000009
0,9972   0,997200008
0,9974   0,997400007
0,9976   0,997600006
0,9978   0,997800005
0,998   0,998000004
0,9982   0,998200003
0,9984   0,998400002
0,9986   0,998600002
0,9988   0,998800001
0,999   0,999000001
0,9992   0,999200001
0,9994   0,9994
0,9996   0,9996
0,9998   0,9998
1   1

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 21 авг 2022, 18:37

У меня вот так получается (многочлен 5-ой степени)

Код: Выбрать все

         0.5   0.6912745628
      0.5002   0.6912746337
      0.5102   0.6914587923
      0.5104   0.6914660852
        0.53   0.6928640351
      0.5302   0.6928852346
        0.55   0.6956667495
         0.6   0.7084429469
      0.6002   0.7085096694
      0.6998   0.7548896054
         0.7    0.755006134
      0.7002   0.7551227452
      0.7488   0.7857740493
       0.749    0.785909193
      0.7492   0.7860444065
      0.7494   0.7861796898
      0.7496    0.786315043
      0.7498   0.7864504658
        0.75   0.7865859584
      0.7502   0.7867215206
      0.7504   0.7868571524
         0.8   0.8225360588
      0.8002   0.8226877617
         0.9   0.9052786103
      0.9002   0.9054568968
        0.99   0.9900502525
      0.9902   0.9902482576
      0.9904   0.9904463033
      0.9906   0.9906443896
      0.9908   0.9908425165
       0.991   0.9910406839
      0.9912   0.9912388919
      0.9914   0.9914371404
      0.9916   0.9916354294
      0.9918    0.991833759
       0.992    0.992032129
      0.9922   0.9922305396
      0.9924   0.9924289906
      0.9926   0.9926274821
      0.9928    0.992826014
       0.993   0.9930245864
      0.9932   0.9932231991
      0.9934   0.9934218524
      0.9936    0.993620546
      0.9938     0.99381928
       0.994   0.9940180543
      0.9942   0.9942168691
      0.9944   0.9944157242
      0.9946   0.9946146196
      0.9948   0.9948135553
       0.995   0.9950125314
      0.9952   0.9952115478
      0.9954   0.9954106044
      0.9956   0.9956097014
      0.9958   0.9958088386
       0.996   0.9960080161
      0.9962   0.9962072338
      0.9964   0.9964064917
      0.9966   0.9966057899
      0.9968   0.9968051282
       0.997   0.9970045068
      0.9972   0.9972039255
      0.9974   0.9974033844
      0.9976   0.9976028835
      0.9978   0.9978024227
       0.998    0.998002002
      0.9982   0.9982016215
      0.9984    0.998401281
      0.9986   0.9986009807
      0.9988   0.9988007204
       0.999   0.9990005003
      0.9992   0.9992003201
      0.9994   0.9994001801
      0.9996     0.99960008
      0.9998     0.99980002

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 21 авг 2022, 20:54

Да, мои значения все с недостатком 0,0001..0,0002 из-за особенностей взятия значения обратной функции (наибольшее значение сетки, при котором h(x)<y). Чем подтверждается, что эти методы сходятся к одной функции.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 22 авг 2022, 16:38

Ian писал(а):Source of the post Вы можете, как начали с верных неравенств, так неравенствами и довести до оценки точности определения f(1/2)?
В принципе можно, но долго выйдет.
Идея там такая:
При маленьком дельта мы знаем [math] с точностью [math], т.е. её значение зажато неравенством в таком малом диапазоне.
Когда берём [math], то результат будет зажат в новом диапазоне, размер которого равен старому размеру умноженному на производную [math] в точке [math]. Это стандартный момент, при анализе вычислительной ошибки так и делают, ограничиваясь только этим.
Это не строгое соотношение, т.к. тут только линеаризация. При желании можно получить строгое неравенство с учётом нелинейности. Т.к. нелинейность мала, то это можно сделать в форме коэффициента чуть больше единицы. Тут ничего сложного - чисто технический момент.

Потом делаем ещё такой шаг и так далее. Получим произведение производных взятых в точках [math].
Точки поначалу идут примерно как [math] (опять для строгости нужно какие-то коэффициенты вводить).
Производная [math] равна [math]
Т.е. нужно найти произведение [math], которое примерно даст насколько начальный интервал раздулся после всех этих трансформаций.
Это произведение примерно равно [math].
Т.е. изначальный интервал раздуется из [math] в [math] раз (там ещё будут фиксированные множители независящие от [math]) и итоговый интервал останется малым.

В строгих неравенствах, чтобы учесть все нелинейности - это на несколько страниц.
Но результат будет тот же. Вместо единицы в [math] будет степень чуть меньше 1. И какой-то кожффициент фиксированный появится.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 22 авг 2022, 17:43

zykov писал(а):...
Т.е. нужно найти произведение [math], которое примерно даст насколько начальный интервал раздулся после всех этих трансформаций.
Это произведение примерно равно [math].
Да, вот это место решающее. А если другая [math], не квадратный трехчлен а например синус? Что мы используем от [math] и в каком классе ищем решение, чтобы так доказать что оно единственное в своем классе? Потому что мы согласились, что вообще оно не единственное.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 22 авг 2022, 19:03

Для [math] есть только одна стационарная точка в нуле.
Она же будет стационарной для [math].
Там можно ряд получить: [math].
Последовательность [math] тоже к нулю сходится.
Около нуля можно многочленом приблизить, а потом вернуться через [math].

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 22 авг 2022, 19:29

На интервале [math] вот так получается.
ff_sin.png
ff_sin.png (18.25 KiB) 9558 просмотра
Дальше наверно периодически можно продолжить (всё равно значения из вне сюда сразу попадут).
Использовать [math] и [math].
Последний раз редактировалось zykov 22 авг 2022, 22:43, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 22 авг 2022, 21:40

Есть ещё второй вариант - та же функция помноженная на "-1".

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 31 авг 2022, 09:44

Кстати, извлечение функционального корня из многочлена степени, являющейся полным квадратом(без гарантии единственности найденной функции) проще, чем мы тут проделывали. Примером может служить задача с последней Моск. олимпиады для 11кл (заскриненное с сайта https://olimpiada.ru/activity/72/tasks
MMO11_6.png
MMO11_6.png (34.13 KiB) 9385 просмотра

И я бы очень расстроился, если бы узнал, что все кто решили -решили именно так. Потому что 11-классникам доступны комплексные числа. А легко раскладывается [math] , причем каждый из двух комплексных корней многочлена [math] с вещественными коэффициентами - является и корнем разложенного. Из 2 вариантов [math] -один сразу отпадает, в нем у P(P(x)) все коэффициенты выйдут положительные, вот и получили ответ. Метод обобщается на степени, являющиеся полным квадратом

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 31 авг 2022, 10:46

Сказано, что [math] квадратный трёхчлен, но не сказано, что действительный.
Из [math] кроме [math] ещё два комплексных вылезет.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 31 авг 2022, 11:43

В этой теме мы находимся в условиях, что решение (здесь P) отображает R в R. То что на проведенной олимпиаде это подразумевали, но забыли упомянуть - нам только помогает сравнить методы. В общем получается -если [math] многочлен степени [math] без кратных действительных корней, то чисто алгебраически найдется решение [math] в виде многочлена степени k

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 31 авг 2022, 22:21

Ian писал(а):Source of the post то чисто алгебраически найдется решение [math] в виде многочлена степени [math]
Тут как-то непонятно.
Вот в их случае они нашли [math] из первых трёх равенств.
Но есть ещё равенства 4 и 5. Если бы там были значения не [math] и [math], а другие, то не сошлось бы...

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

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

Сообщение Ian » 01 сен 2022, 03:01

Да, поправляюсь. Если решение в виде многочлена степени k существует, то оно найдется этим простым алгоритмом сочетания неподвижных точек- корней [math], даже когда действительных неподвижных точек нет. И как раз ищу: если [math], то частное Q(x) тоже как-то выразить через Р формулой без деления, может через корни [math], будет интересно

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

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

Сообщение zykov » 01 сен 2022, 21:47

Если [math], то [math].
Корни квадратного множителя: [math].
Если [math] и [math] комплексно-сопряженные, то это будет [math].
Если [math] и [math] действительные и [math], то это будет пара действительных.
Если [math] и [math] действительные и [math], то это будет пара комплексно-сопряженных.
Если [math] и [math] действительные и [math], то это будет дважды вырожденный [math].


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 9 гостей