Портал Естественных Наук, версия 1.1

zykov писал(а):Source of the post как бы поточнее найти [math]f(\frac12).

Вроде получается 0.691274562 (это [math]G_{400}(\frac12) если брать многочлен 4-ой степени).
Для многочлена 5ой степени вроде стабилизируется на 0.6912745628104900 (16 цифр для double float).
Повышение степени многочлена со 2-ой до 4-ой значительно улучшает точность.
Вот графики [math]G_n(\frac12) от [math]n для многочленов 2ой, 3ей и 4ой степеней:

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

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

Далее, для точки [math]x_1 \in [1-\delta,1) берем точку [math]x_2=\phi^{-1}(x_1)=\frac12+\sqrt{x_1-\frac34} вне нашего интервала.
И определяем [math]f(x_2)=\phi^{-1}(f(x_1)).
Проделав это для всех точек [math]x_1 расширим область, где знаем значение функции, до [math][\phi^{-1}(1-\delta),1].
Далее, повторяем это опять и за конечное количество шагов расширим область до [math][\frac12,1].

Единственная неоднозначность в [math]f(x_2)=\phi^{-1}(f(x_1)), где можно было бы взять корень с минусом. Но из непрерывности корень должен быть с плюсом. А так, разрывных функций конечно много можно сделать.

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

Далее, для точки [math]x_1 \in [1-\delta,1) берем точку [math]x_2=\phi^{-1}(x_1)=\frac12+\sqrt{x_1-\frac34} вне нашего интервала.
И определяем [math]f(x_2)=\phi^{-1}(f(x_1)).
Проделав это для всех точек [math]x_1 расширим область, где знаем значение функции, до [math][\phi^{-1}(1-\delta),1].
Далее, повторяем это опять и за конечное количество шагов расширим область до [math][\frac12,1].

Я утверждаю, что это конечное число шагов имеет порядок [math]\frac 1{\delta}. У нас же правило итераций от [math]x_0=\frac 12 вперед [math]x_{n+2}=\phi (x_n). Для итераций вида [math]x_{n+1}=\phi (x_n) есть теоремы о скорости сходимости [math]x_n к [math]x_*- корню уравнения [math]\phi(x)=x:
Если это простой корень, то скорость сходимости геометрическая[math]\frac{x_{n+1}-x_*}{x_n-x_*}\to \phi '(x_*)-очевидно по определению производной.Если там касание 2-го порядка, то [math]|x_n-x_*|\sim \frac Cn, где С пропорционально второй производной в точке. А например для 3-го порядка на старом форуме была олимпиадная задачка [math]x_0=a,x_{n+1}=\sin x_n, тогда [math]\sqrt n x_n\to\sqrt 3, где тройка взялась от коэффициента -1/6 в разложении синуса, а вовсе не зависит от [math]a.И также не зависит от того, синус там был или просто похожая на синус. То есть, зная только третий член асимптотики разложения [math]\phi, определить с чего начались итерации -невозможно (а в случае геометрической сходимости можно было).А тут, зная номер итерации и асимптотику функции, мы не восстановим начало, оно будет разным для разных функций с такой асимптотикой

Ian писал(а):Source of the post Я утверждаю, что это конечное число шагов имеет порядок [math]\frac{1}{\delta}.

Да, это так.
Последовательность [math]\phi_n(x_1) будет приближатся к 1 слева медленно, как [math]1-\frac1n.
Про остальное, не понял, как оно даёт неоднозначность.

Да, где я говорю, что вблизи 1 мы заменяем приближенно [math]f(x) многочленом, то тут конечно возникают вопросы, что оно всё таки неточно, и может там какие-то проблемы будут.
Но это можно и построже расписать.
Так для [math]f(x) в малой области [math][1-\delta,1) можно записать строгое неравенство:
[math]x+\frac12(1-x)^2 < f(x) < x+\frac12(1-x)^2+\frac{\gamma}{4}(1-x)^3
([math]\gamma чуть больше 1, чтобы компенсировать добавку [math](1-x)^4.)
Размер диапазона пропорционален [math]\delta^3.
Когда мы применяем [math]n раз [math]\phi^{-1}(x), то этот диапазон каждый раз раздувается на величину производной этой функции. Производная там примерно [math]1+2\delta_k, произведение таких множителей [math]1+\frac{2}{k} растёт как [math]n^2.
Т.е. изначалный диапазон [math]\delta^3 будет умножен в итоге примерно на фактор [math]\frac{1}{\delta^2}, что даст конечный диапазон [math]\delta.
Значит уменьшая [math]\delta мы будет зажимать значение например [math]f(\frac12) всё точнее вплоть до нуля. И места для неоднозначности там просто не остаётся.

zykov писал(а):Когда мы применяем [math]n раз [math]\phi^{-1}(x), то этот диапазон каждый раз раздувается на величину производной этой функции. Производная там примерно [math]1+2\delta_k, произведение таких множителей [math]1+\frac{2}{k} растёт как [math]n^2

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

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

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

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

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

Ian писал(а):Source of the post Вы можете, как начали с верных неравенств, так неравенствами и довести до оценки точности определения f(1/2)?

В принципе можно, но долго выйдет.
Идея там такая:
При маленьком дельта мы знаем [math]f(x) с точностью [math]C_1 \delta^3, т.е. её значение зажато неравенством в таком малом диапазоне.
Когда берём [math]\phi^{-1}(f(x)), то результат будет зажат в новом диапазоне, размер которого равен старому размеру умноженному на производную [math]\phi^{-1}(x) в точке [math]f(x). Это стандартный момент, при анализе вычислительной ошибки так и делают, ограничиваясь только этим.
Это не строгое соотношение, т.к. тут только линеаризация. При желании можно получить строгое неравенство с учётом нелинейности. Т.к. нелинейность мала, то это можно сделать в форме коэффициента чуть больше единицы. Тут ничего сложного - чисто технический момент.

Потом делаем ещё такой шаг и так далее. Получим произведение производных взятых в точках [math]f(x), \; \phi^{-1}(f(x)), \; \phi^{-2}(f(x)), \; ..., \; \phi^{-(n-1)}(f(x)).
Точки поначалу идут примерно как [math]1-\frac{1}{n} (опять для строгости нужно какие-то коэффициенты вводить).
Производная [math]\phi^{-1}(x) равна [math]\frac{1}{2\sqrt{x-\frac34}}=\frac{1}{2\sqrt{\frac14-\delta}}=1+2\delta+6\delta^2+...
Т.е. нужно найти произведение [math](1+\frac{2}{n})(1+\frac{2}{n-1})(1+\frac{2}{n-2})...(1+\frac{2}{3}), которое примерно даст насколько начальный интервал раздулся после всех этих трансформаций.
Это произведение примерно равно [math]n^2.
Т.е. изначальный интервал раздуется из [math]\delta^3 в [math]\delta^{-2} раз (там ещё будут фиксированные множители независящие от [math]n) и итоговый интервал останется малым.

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

zykov писал(а):...
Т.е. нужно найти произведение [math](1+\frac{2}{n})(1+\frac{2}{n-1})(1+\frac{2}{n-2})...(1+\frac{2}{3}), которое примерно даст насколько начальный интервал раздулся после всех этих трансформаций.
Это произведение примерно равно [math]n^2.

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

Для [math]\sin x есть только одна стационарная точка в нуле.
Она же будет стационарной для [math]f(x).
Там можно ряд получить: [math]x-\frac{{{x}^{3}}}{12}-\frac{{{x}^{5}}}{160}-\frac{53 {{x}^{7}}}{40320}+....
Последовательность [math]\phi^n(x) тоже к нулю сходится.
Около нуля можно многочленом приблизить, а потом вернуться через [math]\phi^{-n}(x).

На интервале [math][-\frac\pi2,\frac\pi2] вот так получается.Дальше наверно периодически можно продолжить (всё равно значения из вне сюда сразу попадут).
Использовать [math]f(x)=f(\pi-x) и [math]f(x)=f(x+2\pi).

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

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

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

Сказано, что [math]P(x) квадратный трёхчлен, но не сказано, что действительный.
Из [math]a^3=1 кроме [math]a=1 ещё два комплексных вылезет.

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

Ian писал(а):Source of the post то чисто алгебраически найдется решение [math]P(P(x))=\phi(x) в виде многочлена степени [math]k

Тут как-то непонятно.
Вот в их случае они нашли [math]a,\;b,\;c из первых трёх равенств.
Но есть ещё равенства 4 и 5. Если бы там были значения не [math]-3 и [math]4, а другие, то не сошлось бы...

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

Если [math]P(x)=x+(x-c_1)(x-c_2), то [math]P(P(x))-x=(x-c_1)(x-c_2)(x^2+(2-c_2-c_1)x+(c_1-1)c_2-c_1+2).
Корни квадратного множителя: [math]\frac{c_1+c_2-2\pm\sqrt{(c_1-c_2)^2-4}}{2}=\frac{c_1+c_2}{2}-1\pm\sqrt{(\frac{c_1-c_2}{2})^2-1}.
Если [math]c_1 и [math]c_2 комплексно-сопряженные, то это будет [math]Re-1\pm i\sqrt{Im^2+1}.
Если [math]c_1 и [math]c_2 действительные и [math]|c_1-c_2| > 2, то это будет пара действительных.
Если [math]c_1 и [math]c_2 действительные и [math]|c_1-c_2| < 2, то это будет пара комплексно-сопряженных.
Если [math]c_1 и [math]c_2 действительные и [math]|c_1-c_2| = 2, то это будет дважды вырожденный [math]\frac{c_1+c_2}{2}-1.