Черный ящик с полиномом внутри

[bayah]

Здравствуйте, товарищи.

Услышал такую задачку.
Есть "черный ящик". На вход подаем значения, на выходе получаем результат.
Внутри ящика функция вида $f(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n$.
Нужно ответить сколько нужно подать на вход значений $x$, чтобы найти все $a_i$, и величину чему равно $n$ - она тоже не известна.

Понятно, что для полинома степени $n$ нужно $n$ уравнений, а следовательно отвечая на вопрос - передать $n$ значений $x$ на вход. А как определить значение $n$?

[alisa-lebovski]

Добавлять значения на вход, пока система уравнений не станет совместной.

[TOTAL]

bayah в сообщении #1496311 писал(а):

Понятно, что для полинома степени $n$ нужно $n$ уравнений

Для полинома степени $n$ не хватит $n$ уравнений.

Никакого количества обращение не хватит. Предположим, при каждом обращении получаем ноль. Какой вывод?

[Null]

$a_i$ - натуральные может?

[artempalkin]

TOTAL в сообщении #1496319 писал(а):

Никакого количества обращение не хватит. Предположим, при каждом обращении получаем ноль. Какой вывод?

Может быть, вопрос в том, какой мощности числа введенных значений хватит, чтобы найти все коэффициенты? :)
Понятно, что континуума достаточно, но хватит и счетного числа рациональных чисел.

[Sicker]

Если $n$ фиксирована, то нужно подать $n+1$ значений на вход, а если не фиксирована, то конечным числом значений не обойдешься

-- 14.12.2020, 08:00 --

Null в сообщении #1496354 писал(а):

$a_i$ - натуральные может?

А это вообще не важно

[Евгений Машеров]

Задача может рассматриваться как теоретическая и как практическая. Как теоретическая она решения не имеет. Для любой наперёд заданной последовательности входных значений мощности N можно построить полином степени $M\ge N$ такой, что его значения на этих входных значениях совпадут со значениями некоторого полинома степени $n<N$ (или ещё проще - все будут нули).
Но если это практическая задача по оценке "полинома в чёрном ящике", то, подавая различные значения (для успокоения - рандомизированные) мы сможем оценить степень полинома с некоторой вероятностью. Для этого, построив по $(n+1)$ значениям оценку полинома в предположении, что его степень n, сгенерируем ещё одно входное значение, получим оценку выходного в предположении, что верна наша оценка полинома и сравниваем с выходом "ящика". Если не совпало - увеличиваем n и повторяем расчёт. Если совпало - есть основания считать, что степень оценена правильно, так что и коэффициенты верны. Но возможно случайное совпадение. Для гарантии подаём ещё несколько значений, сколько именно - зависит лишь от степени нашей паранойяльности. Если выход - случайная величина, матожидание которой задаётся этим полиномом, то оценивать надо не только его коэффициенты, но и дисперсию помехи. Если для новой величины фактическое отклонение существенно выше оценки ошибки прогноза, то степень надо увеличивать, если сравнима по величине - то повторяем пробы для той же степени с новыми входными значениями, пока не придём к выводу, что отклонения согласуются с ошибкой оценки прогноза (скажем, делим фактическое отклонение на оценку ошибки прогноза и для набора таких величин проверяем гипотезу, что она распределена $N(0;1)$

[Legioner93]

Предлагаю такой алгоритм. Подали два аргумента $x_0, x_1$, решили систему на коэффициенты в предположении $f(x) \equiv f_1(x) \equiv a_0 + a_1 x$

Подали третий аргумент $x_2$. Если на нём $f(x_2) = f_1(x_2)$, то с большой вероятностью (попинайте) $f(x) \equiv f_1(x)$. Можно ещё несколько иксов проверить, чтоб уж точно

В противном случае решаем систему на коэффициенты в предположении $f(x) \equiv f_2(x) \equiv a_0 + a_1 x + a_2 x^2$ и т.д.

[TOTAL]

Legioner93 в сообщении #1496411 писал(а):

Предлагаю такой алгоритм. Подали два аргумента $x_0, x_1$

Подали один аргумент. Затем ещё один. Затем ещё один.
Если записывать интерполяционный полином в форме Ньютона

$$p(x)=f(x_0)+f(x_0,x_1)(x-x_0)+f(x_0,x_1,x_2)(x-x_0)(x-x_1)+ \dots,$$

то находить надо только очередную разделённую разность $f(x_0,\dots,x_n)$ и в случае равенства её нулю начать подозревать, что нашли весь полином.

[mihaild]

Sicker в сообщении #1496402 писал(а):

А это вообще не важно

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

[Null]

(Оффтоп)

mihaild в сообщении #1496481 писал(а):

коэффициенты выяснить можно

Интересно как по десятичной записи числа строить многочлен от $\pi$ с алгебраическими коэффициентами?

[mihaild]

(Оффтоп)

Null в сообщении #1496578 писал(а):

Интересно как по десятичной записи числа строить многочлен от $\pi$ с алгебраическими коэффициентами?

Перебором. Многочленов с алгебраическими коэффициентами счетно, рано или поздно найдем нужный.

[upgrade]

Может быть можно найти значения, которые точно не примут коэффициенты?

[arseniiv]

Предлагаемую Евгений Машеров и Legioner93 процедуру для «практической степени» многочлена было бы конечно неплохо как-то сделать точной в том смысле, что именно она находит при каком способе определения совпадения (потому что на практике мы часто имеем дело с приближёнными числами, которые лучше не сравнивать на точное равенство, даже если это числа с фиксированной точкой или даже точные рациональные). Среди величин, которые она даёт, могут найтись вполне естественные.

Навскидку таких естественных не вижу. Для каждого множества точек, которые мы получили измерениями, можно например получить по многочлену каждой степени, минимизируя довольно натуральную сумму квадратов разностей между значениями многочлена и нашими, но такие разности будут разумеется при увеличении степени финально нулевыми, так что придётся ещё чего-то накрутить, чтобы получить что-то интересное вместо остановки на первом нуле, и это лишь добавит произвола в определение такой «практической степени».

[mihaild]

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