как бы неравенство Йенсена для невыпуклой функции

[Markiyan Hirnyk]

maxal Доказательство в Математике:

ForAll[x, x >= 0, 
  1176 x^8 + 3248*x^7 - 2759*x^6 - 2736*x^5 + 5290*x^4 - 3377*x^3 + 
    1056*x^2 - 152*x + 8 >= 0];Resolve[%, Reals]
True

[maxal]

Markiyan Hirnyk, и как именно она это делает?

[wrest]

maxal в сообщении #1407673 писал(а):

Показать неотрицательность здесь проще по теореме Штурма
,

Почитал Вики по ссылке. Там требуется полином без кратных корней. Это тоже какое-то "легко видеть, что" свойство нашего полинома?

[g______d]

wrest в сообщении #1407703 писал(а):

Это тоже какое-то "легко видеть, что" свойство нашего полинома?

Оно легко проверяемое: достаточно посчитать его дискриминант (но я не считал)

https://ru.wikipedia.org/wiki/Дискриминант

[maxal]

wrest, g______d, достаточно посчитать всего лишь $\gcd(f(x),f'(x))$ и убедиться, что это константа.

[g______d]

(Оффтоп)

maxal, согласен, так проще.

[wrest]

maxal в сообщении #1407715 писал(а):

достаточно посчитать всего лишь $\gcd(f(x),f'(x))$ и убедиться, что это константа.

А... то есть если у многочлена есть кратные корни, то они общие с корнями первой производной. ХитрО! А есть какой-то ускоренный способ это определить, или надо (в олимпиадных условиях) столбиком делить пока не получится $gcd=const$?

[Rak so dna]

wrest в сообщении #1407695 писал(а):

Плюс остается вопрос доказательства справедливости

Rak so dna в сообщении #1407363 писал(а):

Неравенство $(\frac{\sin(\pi x)}{\pi})^2 \geqslant \frac{x^2(8-9x)}{7x^3+16x^2-8x+8}$

Для $0\leqslant x\leqslant\frac{1}{2}$
$\left( \frac{\sin(\pi x)}{\pi x}\right)^2\geqslant 1-\frac{\pi^2x^2}{3}+\frac{2\pi^4x^4}{45}-\frac{\pi^6x^6}{315}\geqslant \frac{8-9x}{7x^3+16x^2-8x+8}$
Для $\frac{1}{2}\leqslant x\leqslant1$ достаточно показать, что $\left( \frac{\sin(\pi (y+\frac{1}{2}))}{\pi}\right)^2\geqslant \frac{(y+\frac{1}{2})^2\left(8-9(y+\frac{1}{2})\right)}{7(y+\frac{1}{2})^3+16(y+\frac{1}{2})^2-8(y+\frac{1}{2})+8}$ для $0\leqslant y\leqslant\frac{1}{2}$.
Показываем:
$\left( \frac{\cos(\pi y)}{\pi}\right)^2\geqslant \frac{1}{\pi^2}-y^2+\frac{\pi^2y^4}{3}-\frac{2\pi^4y^6}{45}\geqslant -\frac{72y^3+44y^2-10y-7}{56y^3+212y^2+106y+71}$ для $0\leqslant y\leqslant\frac{1}{2}$

[wrest]

Rak so dna
Т.е. трех членов Тейлора достаточно оказалось, но как же показать что неравенство выполняется?
Оно же опять "на тоненького", а там число $\pi$ -- его тоже раскладывать?
Ну и следующий вопрос -- а правая часть неравенства из космоса свалилась? В смысле -- вы просто знали или как-то решали?

[Markiyan Hirnyk]

maxal

Цитата:

и как именно она это делает?

Этот же вопрос можно задать и о команде

polsturm

. Не знаю. Продемонстрировал, что предикаты и кванторы эффективно внедрены в Математике.

[wrest]

Markiyan Hirnyk в сообщении #1407811 писал(а):

Этот же вопрос можно задать и о команде

Покашта из предложенных способов проверки неравенства после его конвертации в алгебраическое, ряд полиномов Штурма -- самый доступный для проверки "руками".

[wrest]

В общем, я попробовал построить ряд Штурма на бумаге, это адъ!
Лист А4 надо класть поперек иначе не влезает убористым почерком, и это только первые пара членов, дальше там тьма.

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

Для справки, предпоследний член:

(Оффтоп)

4066635782071730062726234052745758704691969669464140874088294871889986104157
3571504985594483320901196100/67006081316873233816878142542290045220643577
9269914205819165489009032178840893121884499791141784106569x - 600033197365
5556050396403570127294760235332159474332104439208852445393760888362952038
442179385172659050/670060813168732338168781425422900452206435779269914205
819165489009032178840893121884499791141784106569

Ясно, что столько знаков не надо, но не ясно сколько надо.
Знаки у старших коэффициентов выходят ++++--++- (бесконечность - 3 перемены), знаки у младших +----+--- (ноль - 3 перемены), так что корней от нуля до бесконечности $3-3=0$ (т.е. нет корней). На всякий случай проверяем знаки старших коэффициентов на минус бесконечности: +-+--++-- получаем 5 перемен, так что всего у полинома два корня, оба отрицательные - Штурм работает.
На pari/gp, которая может делить многочлены с остатком, "вручную" это выглядит так:

(Оффтоп)

? f0=1176*x^8 + 3248*x^7 - 2759*x^6 - 2736*x^5 + 5290*x^4 - 3377*x^3 + 1056*x^2 - 152*x + 8;
? f1=deriv(f0);f2=-f0%f1;f3=-f1%f2;f4=-f2%f3;f5=-f3%f4;f6=-f4%f5;f7=-f5%f6;f8=-f6%f7;
Печатаем знаки старших коэффициентов (при старших степенях):
? print(sign(polcoef(f0,8)),sign(polcoef(f7,1)),sign(polcoef(f6,2)),sign(polcoef(f5,3)),sign(polcoef(f4,4)),
sign(polcoef(f3,5)),sign(polcoef(f4,4)),sign(polcoef(f5,3)),sign(polcoef(f6,2)),sign(polcoef(f7,1)),sign(polcoef(f8,0)))
1111-1-111-1
Печатаем знаки младших коэффициентов (свободных членов):
?print(sign(polcoef(f0,0)),sign(polcoef(f7,0)),sign(polcoef(f6,0)),sign(polcoef(f5,0)),sign(polcoef(f4,0)),
sign(polcoef(f3,0)),sign(polcoef(f4,0)),sign(polcoef(f5,0)),sign(polcoef(f6,0)),sign(polcoef(f7,0)),sign(polcoef(f8,0)))
1-1-1-1-11-1-1-1

Ну и поскольку рациональные числа pari/gp хранит точно, то можно сказать что это доказательство неотрицательности полинома на нужном нам интервале (с учетом конечно того, что НОД полинома и его первой производной - константа, т.е. кратных корней нет). НОД вычисляем так:

(Оффтоп)

?gcd(f0,f1)
%1 = 1

[maxal]

Markiyan Hirnyk, я вам дал ссылку в Википедию на то, что именно делает команда polsturm. Можно ее работу проверить вручную, как это сделал wrest.

[wrest]

maxal
У меня вопрос по Штурму. Там по процедуре мы должны каждый раз менять знак остатка. В этой связи, когда мы получаем константу на послднем ($n$-ом) шаге, означает ли это автоматически, что и НОД полинома и её производной - константа? И если НОД не константа, то в процессе вычисления по процедуре с переменой знаков -- обнаружим ли мы это (получив константу в остатке раньше времени)?

То есть надо ли нам сначала искать НОД, а затем по той же, фактически, процедуре, выписывать полиномы ряда Штурма?

[g______d]

maxal в сообщении #1407907 писал(а):

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

Думаю, стоит отметить, что алгоритм цилиндрического разложения, на который я ссылался ранее, тоже является точным, работает только с рациональной арифметикой, и описан в литературе (ссылки я могу привести, но их легко найти). И тоже может быть проверен вручную