WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 46 | 47 || 49 | 50 |   ...   | 65 |

32.6. Пусть w(x) число перемен знака в последовательности f(x), f1(x),..., fn(x). Докажите, что количество корней многочлена f (без учёта их кратности), заключённых между a и b, где f(a) = 0, f(b) = и a < b, в точности равно w(a) - w(b) (Штурм).

32.7. Докажите, что корни производной многочлена P принадлежат выпуклой оболочке корней самого многочлена P (Гаусс–Люк).

а Глава 32. Многочлены II 32.8. Пусть P (z) = (z -x1)·...·(z -xn), где x1 <... < xn. Докажите, что если некоторый корень xi заменяется на x (xi, xi+1), то все корни i производной многочлена P увеличиваются.

32.2. Неприводимые многочлены Иногда возникает потребность рассматривать многочлены не только с действительными или целыми коэффициентами, но и с коэффициентами в произвольном поле или коммутативном кольце. Кольца и поля это множества, в которых есть операции сложения и умножения. В кольцах, в отличие от полей, нет операции деления. Например, действительные или рациональные числа образуют поле, а целые числа только кольцо, потому что отношение двух целых чисел не всегда является целым числом.

Точные определения таковы. Кольцо K это множество, в котором для любых двух элементов x и y определены их сумма x + y и произведение xy (они тоже являются элементами K). Эти операции обладают следующими свойствами:

• x + y = y + x (коммутативность сложения);

• (x + y) + z = x + (y + z) (ассоциативность);

• в K существует нулевой элемент 0, для которого x + 0 = x для любого x из K;

• для любого элемента x из K существует противоположный элемент -x, для которого x + (-x) = 0;

• x(y + z) = xy + xz и (x + y)z = xz + yz (дистрибутивность умножения относительно сложения).

Кольцо K называют коммутативным, если умножение в нём коммутативно, т.е. xy = yx для любых элементов x и y из K.

Кольцо K называют ассоциативным, если умножение в нём ассоциативно, т.е. (xy)z = x(yz) для любых x, y и z из K.

Элемент 1 кольца K называют единицей, если 1x = x1 = x для любого элемента x кольца K.

Говоря о кольцах, мы всегда будем подразумевать коммутативные ассоциативные кольца с единицей.

Полем называют коммутативное ассоциативное кольцо с единицей, в котором для каждого элемента x = 0 существует обратный элемент x-1, для которого xx-1 = 1.

396 Глава 32. Многочлены II Поле k называют подполем поля K (обозначение: k K; K при этом называют расширением поля k), если каждый элемент поля k одновременно является элементом поля K, причём операции сложения и умножения для элементов k будут теми же самыми, если мы рассмотрим их как элементы K; нулевой элемент и единица в k те же самые, что и в K. Например, поле рациональных чисел является подполем поля действительных чисел.

Пусть f и g многочлены с коэффициентами из поля k. Говорят, что многочлен f делится на многочлен g, если f = gh, где h некоторый многочлен (с коэффициентами из поля k).

Многочлен d называют общим делителем многочленов f и g, если f и g делятся на d. Общий делитель d многочленов f и g называют наибольшим общим делителем многочленов f и g, если он делится на любой общий делитель многочленов f и g. Ясно, что наибольший общий делитель определён однозначно с точностью до умножения на ненулевой элемент поля k.

Наибольший общий делитель d = НОД(f, g) многочленов f и g можно найти с помощью следующего алгоритма Евклида. Для определённости будем считать, что deg f deg g, где deg обозначает степень многочлена. Пусть r1 остаток от деления f на g, r2 остаток от деления g на r1,..., rk+1 остаток от деления rk-1 на rk. Степени многочленов ri строго убывают, поэтому для некоторого n получим rn+1 = 0, т.е.

rn-1 делится на rn. При этом f и g делятся на rn, так как на rn делятся многочлены rn-1, rn-2,... Кроме того, если f и g делятся на некоторый многочлен h, то rn делится на h, так как на h делятся многочлены r1, r2,... Таким образом, rn = (f, g).

Непосредственно из алгоритма Евклида вытекают важные следствия, которые мы сформулируем отдельно.

а) Если d наибольший общий делитель многочленов f и g, то найдутся такие многочлены a и b, что d = af + bg.

б) Пусть f и g многочлены над полем k K. Тогда если у многочленов f и g есть нетривиальный общий делитель над полем K, то у них есть нетривиальный общий делитель и над полем k.

Многочлен f с коэффициентами из кольца k называют приводимым над k, если f = gh, где g и h многочлены положительной степени с коэффициентами из кольца k. В противном случае многочлен f называют неприводимым над k.

Пусть f = f1 ·... · fs некоторое разложение многочлена f над полем k на множители f1,..., fs, являющиеся многочленами над полем k.

От разложения на множители с произвольными коэффициентами можГлава 32. Многочлены II но перейти к разложению со старшим коэффициентом 1. В самом деле, если fi(x) = aixi +... многочлен над полем k, то gi = a-1fi тоi же многочлен над полем k, причём его старший коэффициент равен 1.

Поэтому разложение f = f1 ·... · fs можно заменить на разложение f = = ag1 ·...· gs, где a = a1 ·...·as. Мы не будем различать два разложения такого вида, отличающиеся лишь порядком множителей.

32.9. Докажите, что если многочлен qr делится на неприводимый многочлен p, то один из многочленов q и r делится на p.

32.10. Пусть k поле. Докажите, что у многочлена f(x) с коэффициентами из k есть разложение на неприводимые множители, причём это разложение единственно.

Для кольца целых чисел неприводимость многочленов определяется точно так же, как и в случае поля, т.е. многочлен f(x) с целыми коэффициентами неприводим над кольцом целых чисел, если его нельзя представить в виде произведения многочленов положительной степени с целыми коэффициентами. Но в случае кольца целых чисел не всегда можно поделить коэффициенты многочлена на старший коэффициент;

можно лишь поделить коэффициенты на наибольший общий делитель всех коэффициентов. Это приводит к следующему определению. Пусть f(x) = aixi, где ai целые числа. Наибольший общий делитель коэффициентов a0,..., an называют содержанием многочлена f. Содержание многочлена f обозначают cont(f). Ясно, что f(x) = cont(f)g(x), где g многочлен с целыми коэффициентами и с содержанием 1.

32.11. Докажите, что cont(fg) = cont(f) cont(g) (лемма Гаусса).

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

32.13. Пусть f(x) = a0 + a1x +... + anxn многочлен с целыми коэффициентами, причём для некоторого простого числа p коэффициент an не делится на p, коэффициенты a0,..., an-1 делятся на p, но коэффициент a0 не делится на p2. Докажите, что тогда f неприводимый многочлен (признак Эйзенштейна).

32.14. Докажите, что если p простое число, то многочлен f(x) = = xp-1 + xp-2 +... + x + 1 неприводим.

398 Глава 32. Многочлены II 32.3. Симметрические многочлены Многочлен f(x1,..., xn) называют симметрическим, если для любой перестановки выполняется равенство f x,..., x = f(x1,..., xn).

(1) (n) Основным примером симметрических многочленов служат элементарные симметрические многочлены (элементарные симметрические функции) k(x1,..., xn) = xi ·... · xi, 1 k i1<... n.

Элементарные симметрические многочлены можно задавать с помощью производящей функции n (t) = ktk = (1 + txi).

k=0 i=Если x1,..., xn корни многочлена xn + a1xn-1 +... + an, то k(x1,..., xn) = (-1)kak.

Другим примером симметрических многочленов служат полные однородные симметрические многочлены 1 n pk(x1,..., xn) = xi ·... · xi.

1 n i1+...+in=k Им соответствует производящая функция n p(t) = pktk = (1 - txi)-1.

k=0 i=Важным примером симметрических многочленов служат также степенные суммы sk(x1,..., xn) = xk +... + xk.

1 n Им соответствует производящая функция n s(t) = sktk-1 = xi(1 - txi)-1.

k=1 i=Иногда используются мономиальные симметрические многочлены 1 n mi...in(x1,..., xn) = xi ·... · xi.

(1) (n) Sn Глава 32. Многочлены II 1 1 1 32.15. Докажите, что если a + b + c + d = 2 и + + + = 2, то a b c d 1 1 1 + + + = 2.

1 - a 1 - b 1 - c 1 - d * * * 32.16. Докажите, что n (-1)rrpn-r = 0.

r=32.17. Докажите, что n npn = srpn-r.

r=32.18. Пусть sk = xk +... + xk. Докажите, что 1 n nn = s1n-1 - s2n-2 +... + (-1)n-1sn(формулы Ньютона).

32.19. Сумма трёх целых чисел x, y, z равна нулю. Докажите, что 2(x4 + y4 + z4) квадрат целого числа.

32.20. Целые числа x1,... x5 таковы, что x1 +... + x5 и x2 +... + x1 делятся на нечётное число n. Докажите, что x5 +... + x5 - 5x1... x1 тоже делится на n.

* * * 32.21. Пусть x1, x2, x3 корни многочлена x3 + px + q. Вычислите sn = xn + xn + xn для n = 1, 2,..., 10.

1 2 32.22. Пусть x1 = b+c+d, x2 = -(a+b+c), x3 = a-d, y1 = a+c+d, y2 = -(a + b + d) и y3 = b - c. Пусть, далее, t3 + p1t + q1 и t3 + p2t + qмногочлены с корнями x1, x2, x3 и y1, y2, y3 соответственно. Докажите, что p1 = p2 тогда и только тогда, когда ad = bc.

32.23. Пусть f2n = (b + c + d)2n + (a + b + c)2n + (a - d)2n - (a + + c + d)2n - (a + b + d)2n - (b - c)2n, причём ad = bc. Докажите, что f2 = f4 = 0 и 64f6f10 = 45f8 (тождества Рамануджана).

* * * 400 Глава 32. Многочлены II 32.24. а) Пусть f(x1,..., xn) симметрический многочлен.

Докажите, что существует многочлен g(y1,..., yn), для которого f(x1,..., xn) = g(1,..., n). При этом многочлен g единствен (основная теорема о симметрических многочленах ).

б) Докажите, что если f(x1,..., xn) симметрический многочлен с целыми коэффициентами, то f(x1,..., xn) = g(1,..., n), где g тоже многочлен с целыми коэффициентами.

Из основной теоремы о симметрических многочленах следует, что если x1,..., xn корни многочлена xn + a1xn-1 +... + an, то величина D = (xi - xj)2, i

Назовём многочлен f(x1,..., xn) кососимметрическим, если f(..., xi,..., xj,...) = -f(..., xj,..., xi,...), т.е. при перестановке любых двух переменных xi и xj многочлен меняет знак. Примером кососимметрического многочлена служит = = (xi - xj).

i

Пусть = (1,..., n) разбиение, т.е. упорядоченный набор целых неотрицательных чисел 1 2... n 0. Положим || = 1 + +... + n. Будем считать, что µ, если 1 +... + k µ1 +... + µk при k = 1, 2,..., n.

Каждому набору можно сопоставить однородный симметрический многочлен 1 (1) (n) M(x1,..., xn) = x1 ·... · xn. (1) n! Sn Степень этого многочлена равна ||.

Например, если = (1,..., 1), то M(x1,..., xn) = x1 ·... · xn. В самом деле, сумма (1) в этом случае состоит из n! слагаемых x1 ·... · xn.

А если = (n, 0,..., 0), то M(x1,..., xn) = (xn +... + xn)/n. В самом 1 n деле, сумма (1) в этом случае состоит из (n - 1)! слагаемых xn, (n - 1)! слагаемых xn и т.д.

Глава 32. Многочлены II 32.26. Докажите, что неравенство M(x) Mµ(x) выполняется при всех x = (x1,..., xn) с положительными x1,..., xn в том и только том случае, когда || = |µ| и µ. При этом равенство достигается лишь в том случае, когда = µ и x1 =... = xn (Мюрхед).

32.4. Многочлены Чебышёва 32.27. Докажите, что cos n полиномиально выражается через cos, т. е. существует такой многочлен Tn(x), что Tn(x) = cos n при x = cos.

Многочлены Tn(x) из задачи 32.27 называют многочленами Чебышёва.

32.28. Вычислите многочлены Чебышёва Tn(x) при n 5.

32.29. Докажите, что |Tn(x)| 1 при x 1.

32.30. Докажите, что Tn(x) = 2n-1xn+a1xn-1+...+an, где a1,..., an целые числа.

32.31. Пусть Pn(x) = xn +... многочлен степени n со старшим коэффициентом 1, причём |Pn(x)| при |x| 1. Тогда Pn(x) = 2n-1 = Tn(x). (Иными словами, многочлен Tn(x) наименее укло2n-1 2n-няющийся от нуля на интервале [-1, 1] многочлен степени n со старшим коэффициентом 1.) 32.32. Докажите, что многочлены Чебышёва Tn(x) и Tm(x) обладают следующим свойством: Tn(Tm(x)) = Tm(Tn(x)).

2l 32.33. а) Пусть n = 2k + 1. Докажите, что число cos для n любого целого l является корнем многочлена T (x) - Tk(x).

k+2l б) Пусть n = 2k. Докажите, что число cos для любого целого n l является корнем многочлена Tk+1(x) - Tk-1(x).

32.34. а) Вычислите многочлены Tk+1(x) - Tk(x) при k 4.

2 б) Докажите, что числа cos и cos являются корнями много5 члена 4x2 + 2x - 1.

2 4 в) Докажите, что числа cos, cos и cos являются корнями 7 7 многочлена 8x3 + 4x2 - 4x - 1.

2 4 г) Докажите, что числа cos, cos и cos являются корнями 9 9 многочлена 8x3 - 6x + 1.

402 Глава 32. Многочлены II В некоторых случаях вместо многочлена Tn(x) удобно рассматривать многочлен Pn(x) = 2Tn(x/2) со старшим коэффициентом 1. Многочлены Pn(x) удовлетворяют рекуррентному соотношению Pn+1(x) = = xPn(x) - Pn-1(x), причём P0(x) = 1 и P1(x) = x, поэтому Pn(x) многочлен с целыми коэффициентами.

Если z = cos +i sin = ei, то z+z-1 = 2 cos и zn+z-n = 2 cos n.

Поэтому P (z + z-1) = 2Tn(cos ) = 2 cos n = zn + z-n, т. е. многочлен Pn(x) соответствует полиномиальному выражению величины zn + z-n через z + z-1.

32.35. С помощью многочленов Pn докажите следующее утверждение: если оба числа и cos() рациональны, то число 2 cos() целое, т. е. cos() = 0, ±1/2 или ±1.

См. также задачу 29.55.

32.5. Алгебраические и трансцендентные числа Комплексное число называют алгебраическим, если оно является корнем неприводимого многочлена с рациональными коэффициентами.

Если старший коэффициент этого многочлена равен 1, а все остальные коэффициенты целые числа, то число называют целым алгебраическим.

Комплексное число, которое не является алгебраическим, называют трансцендентным.

Если число является корнем многочленов f(x) и g(x) с рациональными коэффициентами, то эти многочлены имеют общий делитель x- над полем комплексных чисел. Но тогда они должны иметь нетривиальный общий делитель и над полем рациональных чисел. Таким образом, каждому алгебраическому числу соответствует единственный неприводимый многочлен f со старшим коэффициентом 1. Корни этого многочлена называют числами, сопряжёнными с.

Pages:     | 1 |   ...   | 46 | 47 || 49 | 50 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.