метод наибольших квадратов :)

Есть N точек.
Нужно провести полином степени К<N, который бы точно проходил через максимальное число точек. На отклонения выпадающих точек начхать =)))

 

persicum
Этот полином в большинстве случаев будет проходить через K точек, и если повезёт на него могут попасть еще какие-то точки, решение в лоб - перебирать все подмножества из К точек.

 

Если начальные данные случайны, вероятность того, что полином пройдёт через более, чем K точек, равна 0, так что можно просто взять K произвольных точек и построить полином по ним.

 

не-не, задачка не имеет ничего общего с ошибками астрономических измерений или NP-полным перебором! Она относится к кодированию, хочу построить свой шифр и декодировать его таким образом. Вроде достаточно методом евклида найти НОД пары полиномов (длинного и покороче), но как их постороить ума не приложу =(((

 

Я конечно могу ошибиться,
но если точек n , а полином
степени k<n, то он пройдет через все точки.

Ну по аналогии
прямая y=x^1 - 2 точки
парабола y=x^2 - 3 точки
...
... y=x^k - n точек, где n>k

Или я не в теме?

 

Все праильна, интерполяционный полином степени N-1 проходит через N точек и единственен. Но я имел в виду K<<N =))) Иначе задача решается неоднозначно (декодирование невозможно)

 

Как выглядит хи-квадрат как функция от K переменных (коэффициентов полинома) при изменении любого (нескольких) из них? Есть ли локальные минимумы и "основной" минимум?

Точки заданы целыми числами?

 

PSR1257
Квадратичная форма имеет только один глобальный минимум?
Ошибок округления нет, ну и плюс надо не минимизировать расстояния (как в МНК), а максимизировать число точек, через которые полином проходит точно.

 

Не знаю, но если Хи даже с несколькими (число их кратно K?) экстремумами - их можно искать быстрее чем полным перебором.

Это понятно. Не уверен, но возможно можно аналитически показать что для некоторого K0 и N0 или какой-то f(K0,N0) невозможно для N случайно заданных точек провести полином через них точно (те оклонение точно 0.000..).

Может быть вы имеете в виду что при "шифровании" задаются N точек заданных ЦЕЛЫМИ числами которые заведомо принадлежат некоему ЗАДАННОМУ полиному K-степени, т.е. задача заведомо имеет точное решение просто нужно найти его?

 

Разумеется, так оно и есть!
Вместо полинома степени K-1 удобнее говорить о наборе из К коэффициентов.
Имея К коэффициентов, можно настругать сколько угодно, т.е. N точек. Это будет кодовым представлением этих К коэффициентов-символов с внесенной избыточностью.

Если известно, что некоторые любые K из N точек заведомо верны, то сообщение можно декодировать решив систему уравнений с матрицей вандермонда K x K (интерполяция).

А если не известно, какие именно символы из N полученных точек верны, то задача декодирования усложняется.

Разумеется, на смежные темы имеется множество литературы вроде спектрального регрессионного анализа Берлекампа-Месси и тому подобное, но для меня все это бесполезно.

Как известно, мамаша Коала вскармливает своих медвежат собственным калом, поскольку листья эвкалипта очень тверды и малосъедобны. Тожасть самое относительно специальной литературы - она мне не по зубам. Мне нужно все разжевать и показать на простом примере, как провести полином К через N точек чтобы максимизировать число точек, через которые полином проходит точно. Тогда я смогу это запрогать.

 

persicum,

Тогда критерий этой самой «максимальности» нужно чётко определить. Для десяти точек полином степени 5, проходящий через 8 точек, лучше полинома степени 6, проходящего через 9 точек?

 

K задано в условии, как я понимаю.

 

persicum

Опишите схему шифрования и обмена шифроданными - ?

Пока как я понял у Фокса и Дейны есть общий никому неизвестный полином степени K. Фокс выбирает случайным образом N точек - все принадлежат полиному - и засылает их Дейне. Плохо понятно где здесь обмен данными?

Также непонятно что вы спрашиваете решается ли такая задача "быстро" (==является ли задача получения всех коэффициентов по N точек трудной?), но именно это удивляет меня - если она решается быстро (как я уже трындел про максимумы) то задача по определению НЕ трудная и не может быть использована? Плюс про однозначность? Что если существует "большое" множество верных решений?

 

Откель растет такая уважуха? =)))

Оставим злоумышленников в стороне пока вместе с Бобом и Алисой.
Рассмотрим просто помехоустойчивый код без ключей.

Классический Рид-Соломон работает так:
Информационный полином К умножаем на генераторный полином G и получаем кодовое слово избыточной длины по сравнению с К. Передаем абракадабру по каналу с ошибками. Декодируем.

Неклассические коды Рида-Соломона работают так:
Информационный полином К эвалюционируем для некоторых известных принимающей стороне X1..XN и получаем то что я называю N точек - Y1..YN. Передаем вектор Y по каналу с помехами. Вопрос: как декодировать?

 

persicum,

По выборке фактов можно построить любую гипотезу. "Эвалюционируем" -- вычисляем, что ли?

 

Нужна максимально правдоподобная гипотеза. Перебор очевидно не годится.

 

Предположим, K = N/2.
Тогда можно построить 2 полинома степени (K-1) - один для истинных точек, второй - для мусорных. Как определить какой из них нужный? Очевидно, никак. Далее предположим, что K = N/2 + 1. Где гарантия, что оставшиеся (N/2 - 1) мусорных точек не образуют более "длинный" полином степени (K - 1) с некоторыми точками из истинных? И так далее.
Да что тут разглагольствовать, вот пример:
Берём 2 полинома: x+(x^4-4*x^2+1) и x-(x^4-4*x^2+1).
Пусть N = 5, K = N - 1 = 4, и все истинные точки соответствуют пересечениям полиномов (на рисунке отмечены фиолетовым). Разбавим истинные значения всего лишь одним мусорным (на рисунке обозначено синей точкой).
Как видим, по заданным точкам можно провести 2 полинома, оба степени K - 1. Один из которых, истинный, будет проходить через 4 точки, а второй, мусорный, через 5 точек.
Это конечно редкий случай, и, возможно, его можно обойти, но вряд ли есть другой способ кроме как перебор всех возможных полиномов степени K - 1 с проверкой - не будет ли существовать полином "длиннее", если добавить очередную мусорную точку.


Uploaded with ImageShack.us

 

KeSqueer
Спасибо за красочный рассказ в картинках!
Вот только опасения напрасны - вы демонстрируете невозможность исправления ошибок при отсутствии избыточности. Кто бы сомневался! Все правильно, если число коэффициентов K (так удобнее, чтобы не вычитать единицу) равно N, то исправить ничего нельзя, поскольку даже одна ошибка переведет интерполяционный полином в другой K'.
В общем, N=K+2T должен исправлять T ошибок однозначно.

Для вашего случая надо рассмотреть не 5, а семь N. При выпадании одной точки все неправильные полиномы K'=5 будут покрывать только 5 точек, а правильный полином K=5 будет покрывать уже шесть точек, и может быть ущучен!

 

Алгоритм с числом операций K! или exp(K) очевидно не имеет практической ценности для не очень малых K. Интересует что-то типа ln(K) как в алгоритме Евклида получения Наибольшего Общего Делителя. Смущает только, что матерые лбы Рид и Соломон в своих там 60-х пошли другим путем, оставив этот более простой и быстрый в вычислительном плане вариант для кодирования. Видать, в самом общем виде, когда места ошибок неизвестны, неклассический алгоритм может требовать слишком много вычислений на декодирование. =(((

 

persicum
Осознал. Не учёл того факта, что не все "наструганные" точки обязаны быть избыточными.

Хорошо. Давайте упростим задачу до "не могу".
Раскидаем по плоскости пару сотен точек, с условием, что их координаты должны быть целыми числами (чтобы ещё проще). Как провести прямую через максимальное количество точек? Очевидно, перебором. Других мыслей пока нет.