Задачи по многочленам (Винберг)

[caxap]

1.1. Так называемая задача интерполяции состоит в нахождении многочлена степени $<n$, принимающего в заданных точках $x_1,...,x_n\in K$ заданные значения $y_1,...,y_n\in K$. Доказать, что задача интерполяции имеет единственное решение при любых $x_i$, $y_i$.

Идея: найти СЛАУ для коэффициентов интерполяционного многочлена и показать, что она имеет 1 решение.

Пусть искомый многочлен $f(x)=\sum_{k=0}^{n-1} a_k x^k$. Получаем СЛАУ $\sum_{k=0}^{n-1} a_k x_i^k=y_i$ для $i=\overline{1,n}$. Число уравнений равно числу неизвестных $\Rightarrow$ может быть $0,1,\infty$ решений. Докажем, что не может быть $\infty$. Пусть многочлены $f,g$ являются решениями этой системы. Тогда многочлен $h(x)=f(x)-g(x)=c(x-x_1)\cdots(x-x_n)$ будет равен нулю в $n$ точках $x_1,...,x_n$. Но $\deg f=\deg g<n \Rightarrow \deg (f-g)< n$ и, если он не нулевой, то он не может равняться нулю в $n$ точках. Значит он нулевой $\Rightarrow f=g$.

А как доказать, что не может быть 0 решений?

[ewert]

caxap в сообщении #412595 писал(а):

А как доказать, что не может быть 0 решений?

Для квадратных СЛАУ существование решений при любой правой части равносильно единственности.

[caxap]

А вдруг некоторые строки в матрице коэффициентов окажутся зависимыми? Тогда, если ранг расширенной матрицы будет больше, то не будет решений.

-- 13 фев 2011, 19:33 --

Если $y_i=0$, то есть решение (нулевое). А т. к. $\infty$ решений быть не может, то матрица коэффициентов невырождена. Так?

[Ales]

Сможете найти определитель матрицы этой СЛАУ?
Если определитель не равен нулю, то есть обратная матрица.

Этот определитель - дискриминант искомого многочлена. (Или корень из дискриминанта.)
- На самом деле корень из дискриминанта, но совсем не искомого многочлена.

-- Вс фев 13, 2011 19:48:39 --

А вообще есть формула для нахождения этого многочлена.
Найдите сначала формулу для $n=2$, потом для $n=3$.
Потом в общем виде.

[Joker_vD]

caxap в сообщении #412599 писал(а):

А вдруг некоторые строки в матрице коэффициентов окажутся зависимыми?

Так это же матрица Вандермонда, нет?

[caxap]

Ales в сообщении #412604 писал(а):

Сможете найти определитель матрицы этой СЛАУ?

Это определитель Вандермонда. Он $=\prod_{i>j} (x_i-x_j)$, поэтому равен нулю, только если $x_i=x_j$ при $i\neq j$. У нас все $x_i$ различные, поэтому он не ноль.

А предыдущее моё "доказательство" (Если $y_i=0$...) правильно?

[Ales]

caxap в сообщении #412606 писал(а):

Ales в сообщении #412604 писал(а):

Сможете найти определитель матрицы этой СЛАУ?

Это определитель Вандермонда. Он $=\prod_{i>j} (x_i-x_j)$, поэтому равен нулю, только если $x_i=x_j$ при $i\neq j$. У нас все $x_i$ различные, поэтому он не ноль.

А предыдущее моё "доказательство" (Если $y_i=0$...) правильно?

Правильно. Но надо все же доказать и существование.

[caxap]

Ales в сообщении #412608 писал(а):

Правильно. Но надо все же доказать и существование.

"Правильно" -- это к чему относится (к вандермонду или "если $y_i=0$...")? Если ко второму, то там же доказано, что матрица коэффициентов невырождена. Значит, система по-любому совместна, причём имеет 1 решение.

2.1. Пусть $n$ -- простой число. Пользуясь малой теоремой Ферма и формулами Виета, доказать, что $(n-1)!\equiv -1\pmod n$.

Идея: наверное, надо рассмотреть многочлен $p(x)=(x-1)(x-2)\cdots (x-(n-1))$. Тогда произведение его корней даст $(n-1)!$. Но, чтобы связать с формулами Виета, наверное нужно знать какое-то другое представление $p(x)=\sum_{k=0}^{n-1} a_k x^k$ и приравнять $(n-1)!=(-1)^{n-1} a_0/a_n$, а потом применить МТФ. Я туда думаю? Если да, то какое можно взять это другое представление?

[Ales]

caxap в сообщении #412612 писал(а):

"Правильно" -- это к чему относится

"Правильно" - относится к Вашему доказательству.
Но плохо, что Вы не знаете формулы для такого многочлена, а она тривиальна.

[caxap]

Ales в сообщении #412615 писал(а):

Но плохо, что Вы не знаете формулы для такого многочлена, а она тривиальна.

Можно вывести, но зачем, если и без них всё получилось. (Вы говорите об интерполяционных многочленах Лагранжа, Ньютона..?)

[Ales]

caxap в сообщении #412616 писал(а):

Ales в сообщении #412615 писал(а):

Но плохо, что Вы не знаете формулы для такого многочлена, а она тривиальна.

Можно вывести, но зачем, если и без них всё получилось. (Вы говорите об интерполяционных многочленах Лагранжа, Ньютона..?)

Я имел в виду формулу Лагранжа.
Полезно понимать ее связь с линейной алгеброй: Вы раскладываете многочлен по базису, каждый из базисных многочленов принимает значение 1 в одной из точек и в остальных точках равен нулю.

[ewert]

Ales в сообщении #412608 писал(а):

Правильно. Но надо все же доказать и существование.

Не надо -- существование следует из единственности. И это принципиально.

Тем более не надо никаких вандермондов. Скорее наоборот: определитель Вандермонда, не важно чему конкретно равный -- не равен нулю именно потому, кто задача интерполяции всегда корректна (ибо второй вопрос гораздо проще и идейнее первого).

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

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

[Ales]

caxap в сообщении #412612 писал(а):

Пользуясь малой теоремой Ферма

Что можно сказать о многочлене $x^{n-1}-1=0$?

-- Вс фев 13, 2011 20:58:20 --

ewert в сообщении #412628 писал(а):

Не надо -- существование следует из единственности. И это принципиально.

Тем более не надо никаких вандермондов. Скорее наоборот: определитель Вандермонда, не важно чему конкретно равный -- не равен нулю именно потому, кто задача интерполяции всегда корректна (ибо второй вопрос гораздо проще и идейнее первого).

Но это надо специально оговорить и понимать почему.
Впрочем как-раз было оговорено и поэтому ОК.

А определитель Вандермонда - маслом каши не испортишь.
Надо знать разные стороны вопроса, тем более раз уж появилась матрица Вандермонда, то почему бы не спросить и про определитель.

[caxap]

ewert, спасибо за информацию.

Ales в сообщении #412634 писал(а):

Что можно сказать о многочлене $x^{n-1}-1=0$?

По МТФ $x^{n-1}-1=0\pmod n$ при $x=\overline{1,{n-1}}$, а т. к. $p(x)=0$ при тех же $x$, то и $p(x)-(x^{n-1}-1)=0$ при тех же $x$, а их $n-1$ штук. Но $\deg (p(x)-(x^{n-1}-1))\le n-2$ ($x^{n-1}$ сократится) и, если он не нулевой, не может иметь $n-1$ корней $\Rightarrow$ он нулевой $\Rightarrow$ все коэффициенты нулевые, в том числе свободный, а он равен $(n-1)!+1$, поэтому $(n-1)!\equiv -1\pmod n$. Так?

-- 13 фев 2011, 21:14 --

Только я не понял, причём тут формулы Виета. Наверное, Винберг какое-то более простое решение имел в виду.

[Ales]

caxap в сообщении #412640 писал(а):

По МТФ $x^{n-1}-1=0\pmod n$ при $x=\overline{1,{n-1}}$, а т. к. $p(x)=0$ при тех же $x$, то и $p(x)-(x^{n-1}-1)=0$ при тех же $x$, а их $n-1$ штук. Но $\deg (p(x)-(x^{n-1}-1))\le n-2$ ($x^{n-1}$ сократится) и, если он не нулевой, не может иметь $n-1$ корней $\Rightarrow$ он нулевой $\Rightarrow$ все коэффициенты нулевые, в том числе свободный, а он равен $(n-1)!+1$, поэтому $(n-1)!\equiv -1\pmod n$. Так?

-- 13 фев 2011, 21:14 --

Только я не понял, причём тут формулы Виета. Наверное, Винберг какое-то более простое решение имел в виду.

Да, так правильно.
Думаю, это именно то самое доказательство, которое имел в виду Винберг.
Формулу Виета Вы использовали для нахождения свободного члена.
Кстати, Вы получили заодно, что остальные симметрические многочлены - нули $\pmod n$.

-- Вс фев 13, 2011 21:48:23 --

А вообще бы, я доказывал так: в произведении $(n-1)!$ у каждого остатка кроме $1$ и $-1$ есть обратный остаток по $\pmod n$. Все эти пары сокращаем, остается $-1$.