Тема АЛГЕБРА

Многочлены → .09 Интерполяция

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела алгебра

Разделы подтемы Многочлены

Многочлены с целыми коэффициентами и теорема Безу

Теорема Виета для многочленов

Корни многочленов

Свойства коэффициентов многочленов, раскрытие скобок и бином Ньютона

Симметрические многочлены

Применение производной в многочленах

Многочлены над конечным полем

Неприводимость и разложение на неприводимые многочлены

Интерполяция

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#136137Максимум баллов за задание: 7

На плоскости отмечены $2020$ точек, их абсциссы различны, каждая из точек окрашена либо в красный, либо в синий цвет. Скажем, что многочлен $P(x)$ разделяет эти точек, если либо выше графика $P(x)$ нет красных точек, а ниже — нет синих, либо наоборот; на самом графике могут лежать точки обоих цветов. Докажите, что всегда можно построить разделяющий многочлен не выше $2018$ -й степени.

Подсказки к задаче

Подсказка 1

Точки, лежащие на графике многочлена, не мешают разделению, вне зависимости от того, какой цвет и где он находится.

Подсказка 2

Значениями в скольких точках задаётся многочлен степени 2018?

Подсказка 3

Возьмите любые 2019 точек и постройте P(x) степени ≤ 2018, проходящий через них. Остаётся одна точка — что с ней делать?

Показать доказательство

Выберем любые $2019$ точек и построим интерполяционный многочлен $P (x)$ степени не выше $2018,$ проходящий через них.

Так как $P(x)$ проходит через $2019$ точек, то для них условие разделения выполнено автоматически (они лежат на графике).

Рассмотрим последнюю, $2020$ -ю точку. Её цвет определит, как именно многочлен $P$ будет разделять точки:

если точка красная, то договоримся, что красные должны лежать не выше графика $P,$ а синие — не ниже;
если точка синяя, то наоборот: синие не выше, а красные не ниже.

Таким образом, построенный многочлен $P(x)$ степени $≤ 2018$ разделяет все $2020$ точек.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#136139Максимум баллов за задание: 7

Пусть $x i$ — попарно различные числа, $y i$ — какие-то числа. Докажите, что следующая система линейных уравнений имеет ровно одно решение (в переменных $ai);$

(| a xn +a xn−1+ ...+ ax + a = y |||{ n0n n−1 0n−1 1 0 0 0 | anx1 +an−1x1 + ...+ a1x1+ a0 = y1 . |||( ...n n−1 anxn +an−1xn + ...+ a1xn +a0 = yn

Подсказки к задаче

Подсказка 1.

Левые части в системе уж слишком похожи. Что же они напоминают?

Подсказка 2.

Эта система равносильна существованию такого многочлена степени не выше n, что его значение в каждом x равно соответствующему y. Знаем ли мы, как восстановить многочлен степени не выше n по n+1 точке?

Подсказка 3.

Вспомните интерполяционный многочлен Лагранжа. Как доказать, что он единственный?

Подсказка 4.

Рассмотрите разность двух потенциально подходящих многочленов.

Показать доказательство

Положим

∏n x − xj li(x)= xi−-xj j=j0⁄=,i

и рассмотрим многочлен

n P(x)=∑ yili(x). i=0

Для $0≤ i≤ n$ получаем, что при подстановке $xi$ в него все слагаемые, кроме одного, обнулятся, а оставшееся слагаемое будет равно $yi.$ Тогда в качестве $ai$ возьмём коэффициент при $i x .$

Переход между системой и многочленом равносилен, а значит, требуется доказать, что такой многочлен степени не выше $n$ единственен. Это так, ведь если существуют два таких многочлена степени не выше $n,$ то их разность имеет хотя бы $n+ 1$ корень и степень не выше $n,$ чего быть не может.

Ошибка.
Попробуйте повторить позже

Задача 3#136140Максимум баллов за задание: 7

Докажите, что для любых различных $a$ , $b$ , $c$ , $d$ верно

(d− a)(d− b) (d− b)(d− c) (d− c)(d− a) (a)(c−-a)(c−-b) +(a−-b)(a−-c) +-(b−-c)(b−-a) = 1;

(b) ------abc-------+ ------bcd------+ (d − a)(d− b)(d− c) (a− b)(a− c)(a− d)

+------cda------+ ------dab------= −1. (b− c)(b− d)(b− a) (c− d)(c− a)(c− b)

Подсказки к задаче

Пункт a, подсказка 1.

Пытаясь подступиться к задаче, понимаем, что тождество очевидно при d=a, d=b и d=c. На какую мысль это наталкивает?

Пункт a, подсказка 2.

Если рассмотреть левую часть как уравнение относительно d, то оно квадратное, но имеет три различных точки, в которых принимается одно значение.

Пункт b, подсказка 1.

Попытаемся сделать что-то похожее, найдя такое же уравнение, как в пункте a, но кубическое.

Пункт b, подсказка 2.

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

Показать доказательство

(a) Рассмотрим многочлен

(x− a)(x− b) (x−-b)(x−-c) (x−-c)(x−-a) P(x)= (c− a)(c− b) + (a− b)(a− c) + (b− c)(b− a).

Его степень не выше 2, а принимает значение 1 он в трёх различных точках $a,$ $b$ и $c.$ Тогда он тождественно равен 1. При $x =d$ получаем требуемое.

(b) Рассмотрим многочлен

P(x)= (x-− a)(x-− b)(x−-c)+ (x-− b)(x-− c)(x−-d)+ (d − a)(d − b)(d− c) (a− b)(a − c)(a− d)

+ (x-− a)(x-− c)(x-− d)+ (x−-a)(x−-b)(x− d). (b− c)(b− d)(b− a) (c− d)(c− a)(c− b)

Его степень не выше 3, а принимает значение $1$ он в четырёх различных точках $a,b,c$ и $d.$ Тогда он тождественно равен $1.$ При $x =0$ получаем требуемое.

Ошибка.
Попробуйте повторить позже

Задача 4#136141Максимум баллов за задание: 7

Докажите тождество

C0n -C1n- n-Cnn- --------n!--------- x − x+ 1 + ...+ (− 1) x +n = x(x +1)(x +2)...(x+ n).

Подсказки к задаче

Подсказка 1.

Домножим всё на знаменатель, чтобы слева получился многочлен степени n, а справа константа. Как можно доказать такое тождество?

Подсказка 2.

Можно попытаться найти n+1 точку, в которых выполняется равенство.

Подсказка 3.

Хочется их выбрать так, чтобы большинство слагаемых обнулялось.

Показать доказательство

Рассмотрим многочлен

n∑ P(x)= (−1)iCinx(x+1)...(x+ i)...(x+ n), i=0

где крышечка означает отсутствие скобки. При $0≤ i≤n$ в точке $− i$ этот многочлен принимает значение $n!,$ потому что все слагаемые, кроме одного, обнуляются, а в последнем сокращается знаменатель из числа сочетаний.

Многочлен степени не выше $n$ принимает одинаковое значение в $n +1$ различной точке, а значит, он тождественно равен $n!.$ Деля полученное равенство на $x(x+ 1)$ … $(x+ n),$ получаем требуемое тождество.

Ошибка.
Попробуйте повторить позже

Задача 5#136142Максимум баллов за задание: 7

Многочлен $P(x)$ степени $n$ таков, что $P(k)= -1- k+1$ для всех $k$ от $0$ до $n.$ Найдите $P(2n).$

Подсказки к задаче

Подсказка 1

Попробуйте «убрать» знаменатель k+1 умножением на (x+1) и вычесть 1, чтобы получить многочлен, обращающийся в 0 при x=0,1,…,n.

Подсказка 2

Пусть Q(x):=(x+1)P(x)−1. Нам известны его степень и его корни. Как он выглядит?

Подсказка 3

Q(x)=c·∏(x−j), j от 0 до n. Как найти константу c? Может, стоит подсчитать значение многочлена в какой-то точке, отличной от его корней?

Подсказка 4

Подставьте x=−1: Q(−1)=−1, а справа c·(−1)ⁿ⁺¹(n+1)!. Многочлен Q найден, а значит, и P тоже.

Показать ответ и решение

Рассмотрим многочлен

Q(x)=(x+ 1)P (x)− 1.

По условию для $k= 0,1,...,n$ имеем $(k +1)P(k)− 1= 0,$ поэтому

Q(k) =0 (k =0,1,...,n).

Следовательно, $Q$ делится на $x(x− 1)⋅⋅⋅(x− n)$ и, так как $degQ = n+ 1,$ существует число $c$ такое, что

∏n Q (x)= cj=0(x− j).

Найдём константу $c.$ Подставим $x =− 1:$

Q(−1)= (− 1+1)P(−1)− 1 =− 1,

а, с другой стороны,

n Q(−1)= c∏ (−1− j)= c(−1)n+1(n+ 1)!. j=0

Отсюда

n c= ((−n1+)1)!.

Следовательно,

-(−1)n- n∏ (x +1)P(x)=1 +(n+ 1)!j=0(x − j).

Подставим теперь $x= 2n.$ Получаем

(2n+ 1)P (2n)= 1+ (−1)n-∏n(2n− j). (n +1)!j=0

Заметим, что

∏n (2n)! (2n− j) =(2n)(2n− 1)⋅⋅⋅n= (n−-1)!. j=0

Следовательно

(2n +1)P(2n)= 1+ (−1)n----(2n)!--- . (n+ 1)!(n− 1)!

1 (2n)! 1 ( ) P(2n)= 2n-+1 +(−1)n(n-+1)!(n−-1)!(2n+-1) = 2n+-1 1+ (−1)nCn2+n1

Ответ:

$--1-(1+ (−1)nCn+1) 2n+1 2n$

Ошибка.
Попробуйте повторить позже

Задача 6#136143Максимум баллов за задание: 7

Докажите, что если многочлен степени $n$ принимает целые значения в точках $0,$ $1,$ $4,$ …, $n2,$ то он принимает целые значения во всех квадратах целых чисел.

Подсказки к задаче

Подсказка 1

Мы знаем, что если многочлен степени ≤ n принимает целые значения в точках 0,…,n, то его значения во всех целых точках тоже будут целыми. Как свести нашу задачу к этой ситуации? Может, стоит рассмотреть новый многочлен, подставив что-нибудь в P?

Подсказка 2

Рассмотрите G(k):=P((k−n)²). Какая у него степень и что можно сказать о его целочисленности в точках 0,…,2n?

Показать доказательство

Рассмотрим многочлен от одной переменной

2 G(k):= P((k− n) ).

Поскольку $degP ≤n,$ степень $G$ не превосходит $2n.$ При $k= 0,1,...,2n$ значения $(k− n)2$ пробегают квадраты целых чисел $0,1,4,...,n2,$ а потому по условию $G(0),G(1),...,G(2n)$ — целые числа.

Докажем стандартную лемму о целочисленности многочлена.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $H$ — многочлен степени $≤d.$ Если $H(0),H(1),...,H(d)$ — целые числа, то $H (t)∈ ℤ$ для всех целых $t.$

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

b a(a− 1)...(a− b+ 1) Ca = -------b!-------

при целых $b≥ 0$ и $a.$ Это число при неотрицательном $a$ — целое по комбинаторному определению числа сочетаний, а при отрицательном $a= −c$ оно тоже целое, ведь

a(a− 1)...(a− b+ 1) −c(−c − 1)...(−c− b+1) Cba =--------b!------- = ---------b!---------= Cbc+b−1⋅(− 1)b.

Тогда из теоремы Лагранжа об интерполяции

∑n (x− 0)...(x− i)...(x− n) n∑ i n−i n−i H (x) = H(i)⋅ ---i!(n−-i)!(−1)n−i----= H (i)⋅CxCx−i−1(−1) , i=0 i=0

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

_________________________________________________________________________________________________________________________________________________________________________________

Применяя лемму к $G$ (с $d= 2n$ ), получаем, что $G(t)∈ ℤ$ для всех целых $t.$ В частности, для произвольного целого $m$ имеем

P(m2)= G(m+ n)∈ ℤ.

Это и требовалось доказать.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#136147Максимум баллов за задание: 7

Интерполяция по Ньютону. Докажите индукцией по $n,$ что для попарно различных действительных чисел $x ,x , 0 1$ …, $x n$ и любых действительных чисел $y0,y1,$ …, $yn$ существуют многочлен $f$ такой, что для каждого $1≤i≤ n$ выполнено $f(xi)= yi.$

Показать доказательство

База для $n = 0$ очевидна, ведь можно взять $f(x)= y. 0$ Докажем переход от $k$ к $k +1.$

Требуется найти многочлен $f,$ что для каждого $0≤ i≤k +1$ выполнено $f(xi)= yi.$ По предположению индукции существует многочлен $fk,$ что для каждого $0 ≤i≤ k$ выполнено $fk(xi)=yi.$ Тогда возьмём

fk+1(x)= fk(x)+ (x − x0)...(x− xk)⋅C,

где

----yk+1− fk(xn+1)--- C = (xk+1− x0)...(xk+1 − xk).

Тогда для каждого $0≤i≤ k$ выполнено

fk+1(xi)=fk(xi)= yi,

ведь второе слагаемое в $fk+1$ обнуляется. Проверим выполнение условия для $xk+1 :$

fk+1(xk+1) =fk(xk+1)+ (xk+1− x0)...(xk+1− xk)⋅C = fk(xk+1)+yk+1− fk(xk+1) =yk+1.

А значит, многочлен $fk+1$ нам подходит, что и завершает переход индукции.

Ошибка.
Попробуйте повторить позже

Задача 8#136148Максимум баллов за задание: 7

Интерполяция по Лагранжу. Пусть $x , 0$ $x , 1$ $x , 2$ …, $x n$ — попарно различные действительные числа.

(a) Найдите многочлен $Pi(x)$ степени $n$ такой, что $Pi(xi)= 1,$ и $Pi(xj)= 0$ при $j ⁄= i;$

(b) Выведите из пункта (a) существование интерполяционного многочлена степени не выше $n.$

Показать ответ и решение

(a) Заметим, что

(x− x0)...(x− xi)...(x− xn) Pi(x)= (x-− x-)...(x-− x-)...(x-−-x-), i 0 i i i n

где крышечка означает отсутствие скобки, подходит, ведь в $xi$ значения числителя и знаменателя одинаковы и не равны 0, а в остальных точках числитель обнуляется, а знаменатель нет.

(b) Возьмём

∑n -(x−-x0)...(x-− xi)...(x-− xn) P(x)= y0⋅P0(x)+ ...+ yn⋅Pn(x)= i=0yi⋅(xi− x0)...(xi− xi)...(xi− xn).

Он подходит, ведь в точке $xi$ все слагаемые кроме $(i+ 1)$ -ого обнуляются, а $(i+ 1)$ -ое принимает значение $yi.$ Его степень не выше $n,$ так как степень каждого слагаемого равна $n.$

Ответ:

(a) $P (x)= -(x−x0)...(x−-xi)...(x−xn)-, i (xi−x0)...(xi−xi)...(xi−xn)$ где крышечка означает отсутствие скобки.

Ошибка.
Попробуйте повторить позже

Задача 9#136149Максимум баллов за задание: 7

Докажите, что если многочлен в рациональных точках принимает рациональные значения, то и все его коэффициенты рациональные.

Показать доказательство

Пусть $P (x)$ — многочлен из условия и его степень равна $n.$ Возьмём любую $n+ 1$ рациональную точку и построим по ним интерполяционный многочлен Лагранжа:

∑n (x− x )...(x − x )...(x − x ) P(x)= yi⋅ (x-−-x0)...(x-−-ix)...(x-−n x-), i=0 i 0 i i i n

где крышечка означает отсутствие скобки. Так как все $xi$ и $yi$ рациональны, то любой коэффицент $P (x),$ очевидно, рационален.

Ошибка.
Попробуйте повторить позже

Задача 10#136150Максимум баллов за задание: 7

(a) Пусть $P (x)$ — многочлен степени не выше $n,$ для которого $P(xi)= yi$ при $i= 0,1,2,...,n,$ $Q$ — другой многочлен, для которого $Q (xi)=yi$ при $i=0,1,2,...,n.$ Тогда многочлен $P (x)$ является остатком от деления многочлена $Q(x)$ на многочлен $(x− x0)(x− x1)...(x− xn).$

(b) Пусть $a,b,c$ — натуральные числа. Верно ли, что обязательно существует квадратный трёхчлен с целыми коэффициентами, который в некоторых целых точках принимает значения $3 3 3 a ,b,c?$

Показать ответ и решение

(a) При любом $0≤ i≤ n$ разность этих многочленов обнуляется в $x , i$ а значит, делится на $(x− x ). i$ Пусть частное равно $H (x),$ тогда

Q(x)=(x− x0)...(x − xn)H(x)+P (x),

а это мы и хотели доказать.

(b) Многочлен $Q (x)= x3$ почти подходит, но нам нужен квадратный трёхчлен. Пользуясь идеей из пункта (a), получаем, что многочлен

3 P (x)= x − (x − a)(x − b)(x − c)

подходит, ведь коэффицент при $x3$ сократится, а значения в этих точках не изменятся.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 11#136152Максимум баллов за задание: 7

Пусть $x , 1$ $x , 2$ …, $x n$ — попарно различные числа, а $f(x)$ — многочлен степени меньше $n.$ Докажите, что дробь

---------f(x)--------- (x− x1)(x− x2)...(x− xn)

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

-a1--+ -a2--+ ...+ -an--, x− x1 x− x2 x− xn

где $ai$ — некоторые числа.

Показать доказательство

Пусть $f(x)= y i i$ для каждого $1≤ i≤ n.$ Запишем интерполяционный многочлен Лагранжа для $f(x)$ степени меньше $n$ по точкам $x, 1$ …, $xn :$

∑n (x− x)...(x− x )...(x − x ) f(x)= yi⋅(x-− x-1)...(x-− xi)...(x−-nx-), i=1 i 1 i i i n

где крышечка означает отсутствие скобки. Тогда

---------f(x)--------- ∑n -----------yi------------ -1--- (x− x1)(x− x2)...(x− xn) = i=1(xi− x1)...(xi− xi)...(xi− xn) ⋅x− xi.

Взяв в каждом слагаемом первую дробь в качестве $ai,$ получим требуемое представление.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#136153Максимум баллов за задание: 7

(a) Для различных $a,$ $b,$ $c$ упростите выражение

2 (x − a)(x − b) 2 (x − b)(x − c) 2 (x − c)(x− a) c ⋅(c− a)(c−-b) + a ⋅(a-− b)(a-− c) + b ⋅(b-− c)(b−-a).

(b) Для различных $a,$ $b,$ $c$ упростите выражение

2 2 2 ----c-----+----a----- +----b-----. (c− a)(c− b) (a− b)(a− c) (b− c)(b− a)

----an---- ----bn----- ----cn----- (a − b)(a− c) + (b − a)(b− c) + (c− a)(c− b)

целое.

Показать доказательство

(a) Запишем интерполяционную формулу Лагранжа для многочлена $f(x)= x2$ в точках $a,b$ и $c$ и получим в точности выражение из условия, а значит, это выражение равно $2 x .$

(b) Запишем интерполяционную формулу Лагранжа для многочлена $2 f(x)=x$ в точках $a,$ $b$ и $c:$

2 (x− a)(x− b) 2 (x− b)(x− c) 2 (x− c)(x− a) f(x)=c ⋅-(c−-a)(c−-b) +a ⋅-(a−-b)(a−-c) +b ⋅(b−-c)(b− a).

Нетрудно увидеть из формулы, что выражение из условия является старшим коэффицентом этого многочлена. С другой стороны, он равен 1. Значит, выражение равно 1.

(c) Пусть $Q (x)= xn,$ а $P(x)$ — многочлен степени не выше 2, который в точках $a,$ $b,$ $c$ принимает значения $an,$ $bn,$ $cn$ соответственно. Запишем интерполяционную формулу Лагранжа для $P(x):$

P(x)=cn⋅ (x−-a)(x−-b)+an ⋅ (x-− b)(x−-c)+ bn ⋅ (x-− c)(x−-a). (c− a)(c− b) (a − b)(a− c) (b− c)(b− a)

Тогда нам требуется доказать, что старший коэффицент $P(x)$ является целым.

Так как разность $Q(x)− P(x)$ обнуляется в точках $a,$ $b$ и $c,$ то она делится на

R(x)= (x − a)(x − b)(x− c).

Степень $P(x)$ не больше 2, тогда $P(x)$ является остатком от деления $Q(x) =xn$ на $R(x).$

Но в процессе деления в столбик $Q(x)$ на $R(x)$ мы получаем в частном только целые коэффиценты при степенях, что следует из приведенности $R(x).$ Теперь $Q(x),$ $R (x)$ и частное — многочлены с целыми коэффицентами, а значит, и $P(x)$ имеет целые коэффиценты, что и доказывает требуемое.

Ошибка.
Попробуйте повторить позже

Задача 13#136154Максимум баллов за задание: 7

Многочлен $P(x)$ степени $n$ принимает целые значения в точках $0,$ $1,$ $2,$ …, $n.$

(a) Приведите пример такого $P(x),$ у которого не все коэффициенты целые;

(b) Докажите, что $n!⋅P(x)$ — многочлен с целыми коэффициентами;

Показать ответ и решение

(a) Рассмотрим многочлен

(x−-1)(x−-2)...(x-− n) P (x)= n! .

У него старший коэффицент не является целым при $n ≥2.$ В точке 0 он равен $n (− 1) ,$ а в точках 1, 2, …, $n$ он обнуляется. Значит, он нам подходит.

(b) Пусть $P(i)= yi$ для $0≤ i≤ n.$ Запишем интерполяционный многочлен Лагранжа для $P(x)$ степени $n$ в точках 0, 1, …, $n:$

n n P(x)= ∑ yi⋅ (x−-0)...(x−-i)...(x-− n)= ∑ yi⋅ (x−-0)...(x− i)...n(−xi−-n), i=0 (i− 0)...(i^− i)...(i− n) i=0 i!(n− i)!(−1)

где крышечка означает отсутствие скобки. Тогда

∑n (x− 0)...(x− i)...(x− n) ∑n n!⋅P (x)= yi⋅n!⋅----i!(n-− i)!(−1)n−i---= yi⋅Cin(x− 0)...(x − i)...(x− n) i=0 i=0

— многочлен с целыми коэффицентами.

b a(a−-1)...(a− b+-1) Ca = b!

b a(a−-1)...(a−-b+-1) −c(−c-− 1)...(−c−-b+1) b b Ca = b! = b! = Cc+b−1⋅(− 1) .

Из пункта (b):

∑n ∑n P (x)= yi⋅ (x−-0)...(x-− i)...n(−xi− n) = yi⋅CixCnx−−ii−1(−1)n−i. i=0 i!(n− i)!(−1) i=0

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

Ответ:

(a) Например, $P(x)= (x−1)(x−-2)...(x−-n) n!$

Ошибка.
Попробуйте повторить позже

Задача 14#136155Максимум баллов за задание: 7

(a) Докажите, что для любого многочлена $P(x)∈ℝ [x]$ существует многочлен $Q$ такой, что $P(x)= Q(x+1)− Q(x),$ и этот многочлен $Q$ определен с точностью до прибавления произвольной константы.

(b) Пусть $k$ — натуральное число. Докажите, что существует многочлен $P(x)$ степени $k+ 1,$ такой, что

1k+ 2k+...+nk =P (n)

для любого натурального $n.$

Показать доказательство

(a) Пусть

n P(x)= anx +...+a0

m m −1 Q(x)=bmx + bm −1x +...+b0.

Тогда

Q(x+ 1)− Q(x)= bm (x +1)m+ b (x +1)m−1+ ...+ b − bmxm − b xm− 1− ...− b . m−1 0 m− 1 0

Коэффицент при $xm$ равен 0, а при $xm−1$ равен $bmm ⁄= 0.$ Значит, $m =n +1$ и $bn+1 = nan+1.$

Докажем индукцией по $n,$ что такой многочлен $Q(x)$ существует и единственен с точностью до прибавления константы. База для $n =0$ очевидна, докажем переход от $n− 1$ к $n.$ Так как $bn+1$ мы уже нашли, то пусть

P ′(x)=P (x)− bn+1(x+ 1)n+1+ bn+1xn+1.

По предположению индукции (так как степень $P′(x)$ не больше $n− 1$ ) существует многочлен $Q′(x)$ что

P′(x)= Q′(x +1)− Q′(x).

Но тогда возьмём

Q(x)= Q′(x)+ bn+1xn+1

и получим, что

P(x)= P′(x)+ bn+1(x+ 1)n+1− bn+1xn+1 = Q′(x +1)− Q′(x)+ bn+1(x+ 1)n+1− bn+1xn+1 = Q(x+ 1)− Q (x)

Значит, такой многочлен $Q(x)$ существует. Теперь докажем его единcтвенность с точностью до прибавления константы. Пусть

P(x) =Q(x+ 1)− Q (x),

тогда

′ n+1 Q (x)= Q(x)− bn+1x ,

где $bn+1 =-an-. n+1$ Тогда

P(x)= Q′(x+ 1)− Q ′(x)+b (x +1)n+1− b xn+1. n+1 n+1

Пусть

P′(x)= P(x)− bn+1(x+1)n+1+ bn+1xn+1 = Q′(x +1)− Q′(x).

Многочлен $P′(x)$ однозначно восстанавливается по $P (x).$ Но тогда по предположению индукции $Q′(x)$ однозначно восстанавливается с точностью до прибавления константы, откуда и следует единcтвенность $Q (x)$ с точностью до прибавления константы.

(b) Условие равносильно тому, что $P (0)= 0$ и

(x+ 1)k =P (x +1)− P(x).

Как мы поняли из пункта (a), многочлен $P(x),$ удовлетворяющий второму условию, существует и единственен с точностью до прибавления константы, тогда сдвинем его на константу так, что $P(0) =0.$ Также мы ранее уже доказывали, что его степень равна $k+ 1.$

Ошибка.
Попробуйте повторить позже

Задача 15#124303Максимум баллов за задание: 7

Пусть $P(x)$ — приведённый многочлен степени $n.$ Ильнур посчитал его значения в $n +1$ различных целых точках. Докажите, что одно из полученных Ильнуром чисел по модулю хотя бы $n n!∕2 .$

Подсказки к задаче

Подсказка 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)!; теперь в оценке далее можно собрать биномиальный коэффициент.

Показать доказательство

Рассмотрим интерполяционную формулу Лагранжа для $P$ на узлах $x,...,x : 0 n$

∑n ∏ x− xj P (x)= P(xi)ℓi(x), ℓi(x)= xi− xj. i=0 0≤jj≤⁄=ni

Сравним коэффициенты при $xn$ в обеих частях. Поскольку $P$ приведённый, коэффициент при $xn$ слева равен $1.$ У базисного многочлена $ℓi(x)$ старший коэффициент равен

∏---1----. (xi− xj) j⁄=i

Следовательно,

∑n P(xi) 1= i=0 ∏-(xi−-xj). j⁄=i

(1)

Переходя к модулям и применяя неравенство треугольника, получаем

∑n |P(xi)| ∑n 1 1≤ ∏-|xi− xj| ≤ (0 m≤aix≤n|P (xi)|)⋅ ∏-|xi−-xj|. i=0j⁄=i i=0 j⁄=i

Обозначим

n S :=∑ ∏---1----. i=0 |xi− xj| j⁄=i

Тогда

1- 0m≤aix≤n|P(xi)| ≥ S.

(2)

Оценим $S$ сверху, используя лишь то, что $xi$ — попарно различные целые. Без ограничения общности упорядочим их по возрастанию: $x0 < x1 < ...< xn.$ Тогда для любого фиксированного $i$ и каждого $j ⁄= i$ выполнено неравенство

|xi− xj|≥|i− j|,

поскольку между $xi$ и $xj$ лежит не менее $|i− j|− 1$ целых точек и шаг по целым не меньше $1.$ Следовательно,

∏ ∏ ( i−∏ 1 )( n∏ ) |xi− xj| ≥ |i− j| = ( (i− j))( (j− i)) = i!(n− i)!. j⁄=i j⁄=i j=0 j=i+1

Тем самым

∑n 1 1∑n 2n S ≤ i!(n−-i)! = n! Cin =-n!. i=0 i=0

Подставляя это в неравенство для максимума, получаем желаемую оценку

max |P(x )| ≥ 1 ≥ n!. 0≤i≤n i S 2n

Ошибка.
Попробуйте повторить позже

Задача 16#124313Максимум баллов за задание: 7

Найдите в замкнутом виде значение выражения

1∑000 k 1 k 2 k 1000 (2k−-21)(2..−.(23k−)(22k−−1)3(2)k.−..(22k+−1).3..(2)k−-21000). k=1

Подсказки к задаче

Подсказка 1

Обратите внимание, в знаменателе стоят разности вида 2ᵏ − 2ʲ, это очень похоже на базисы интерполяционной формулы Лагранжа.

Подсказка 2

Подумайте чему равен коэффициент при старшей степени в интерполяционном многочлене, если мы знаем его значения в точках xᵢ = 2ⁱ?

Подсказка 3

Попробуйте построить многочлен P(x), который в точке x = 2ᵏ принимает значение (2ᵏ − 3¹)(2ᵏ − 3²)…(2ᵏ − 3¹⁰⁰⁰). Тогда сумма в условии как раз равна старшему коэффициенту интерполяционного многочлена по этим данным.

Подсказка 4

Попробуйте догадаться, какой именно многочлен, степени 999 подойдёт для всех точек сразу. Если бы степень равнялась 1000, подошел бы (x − 3¹)(x − 3²)…(x − 3¹⁰⁰⁰)?

Показать доказательство

Определим $1000$ точек на координатной плоскости следующим образом:

i k 1 k 2 k 1000 xi =2 , yi = (2 − 3 )(2 − 3)...(2 − 3 ).

Тогда по теореме об интерполяционном многочлене Лагранжа требуемое выражение — старший коэффициент многочлена степени не выше $999,$ график которого проходит через все точки $(x ,y). i i$ Как известно, существует лишь один такой многочлен. Значит, осталась его угадать и посчитать старший коэффициент. Заметим, что многочлен

1 1000 1 1000 P(x) =(x− 3)...(x− 3 )− (x− 2)...(x− 2 )

подходит. Его коэффициент при старшей степени равен

(21+...+21000)− (31+ ...+ 31000)= 21001− 2+ 31001− 3. 2

Предыдущая подтема