Интерполяция
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Пусть 
— приведённый многочлен степени 
Ильнур посчитал его значения в 
различных целых точках. Докажите, что одно
из полученных Ильнуром чисел по модулю хотя бы 
Подсказка 1
Вспомните интерполяционную формулу Лагранжа: P(x)=∑ P(xᵢ)·ℓᵢ(x), где ℓᵢ(x)=∏ (x−xⱼ)/(xᵢ−xⱼ) по всем j≠i. Посмотрите именно на старшие коэффициенты этих ℓᵢ(x).
Подсказка 2
У приведённого P старший коэффициент равен 1. В сумме он получается как ∑ P(xᵢ)/(∏(xᵢ−xⱼ) по всем j≠i). Значит, эта сумма равна 1. Какие оценки можно применить, если мы хотим оценить max|P(xᵢ)|?
Подсказка 3
Пусть S:=∑ 1/(∏|xᵢ−xⱼ| по всем j≠i). Тогда maxᵢ|P(xᵢ)| ≥ 1/S.
Подсказка 4
Чтобы оценить S, вспомните, что все xᵢ целые. Что тогда можно сказать про их разности?
Подсказка 5
Упорядочив xᵢ по возрастанию, получим, что |xᵢ−xⱼ| ≥ |i−j|. Тогда каждое слагаемое в S можно оценить сверху.
Подсказка 6
Тогда ∏|xᵢ−xⱼ| по всем j≠i не меньше, чем i!·(n−i)!; теперь в оценке далее можно собрать биномиальный коэффициент.
Рассмотрим интерполяционную формулу Лагранжа для 
на узлах 
Сравним коэффициенты при 
в обеих частях. Поскольку 
приведённый, коэффициент при 
слева равен 
У базисного
многочлена 
старший коэффициент равен
Следовательно,
| (1) |
Переходя к модулям и применяя неравенство треугольника, получаем
Обозначим
Тогда
| (2) |
Оценим 
сверху, используя лишь то, что 
— попарно различные целые. Без ограничения общности упорядочим их по возрастанию:
Тогда для любого фиксированного 
и каждого 
выполнено неравенство
поскольку между 
и 
лежит не менее 
целых точек и шаг по целым не меньше 
Следовательно,
Тем самым
Подставляя это в неравенство для максимума, получаем желаемую оценку
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
