Алгоритмы умножения и деления чисел в десятичной системе счисления

Визначення середньої і граничної похибок та необхідної чисельності вибірки

Відповідь Мотовила на книгу Петра Скарги «Про єдність церкви Божої» 1577(?) р. –перший полемічний твір Острозького осередку.

Вопрос № 1. Испарение влаги и разложение карбонатов в доменной печи. Термодинамика разложения карбонатов.

ВСЕ недостающие степени (и (или) свободные члены) без пропусков записываем в ОБОИХ многочленах с нулевыми коэффициентами.

Многочлен над кольцом целых чисел называется примитивным , если наибольший общий делитель его коэффициентов равен 1. Многочлен с рациональными коэффициентами единственным образом представляется в виде произведения положительного рационального числа, называемого содержанием многочлена, и примитивного многочлена. Произведение примитивных многочленов есть примитивный многочлен. Из данного факта вытекает, что если многочлен с целочисленными коэффициентами приводим над полем рациональных чисел, то он приводим над кольцом целых чисел. Таким образом, задача разложения многочлена на неприводимые множители над полем рациональных чисел сводится к аналогичной задаче над кольцом целых чисел.

Пусть - многочлен с целыми коэффициентами и содержанием 1, а - его рациональный корень. Представим корень многочлена в виде несократимой дроби . Многочлен f (x ) представляется в виде произведения примитивных многочленов . Следовательно,

A. числитель является делителем ,

B. знаменатель – делителем

C. для любого целого k значение f (k ) – целое число, которое делится без остатка на (bk -a ).

Перечисленные свойства позволяют свести задачу отыскания рациональных корней многочлена к конечному перебору. Похожий подход используется в разложении многочлена f на неприводимые множители над полем рациональных чисел методом Кронекера. Если многочлен f (x ) степени n приводим, то один из множителей имеет степень не выше n /2. Обозначим этот множитель через g (x ). Поскольку все коэффициенты многочленов суть целые числа, то для любого целого a значение f (a ) делится без остатка на g (a ). Выберем m= 1+n /2 различных целых чисел a i , i =1,…,m . Для чисел g (a i) существует конечное число возможностей (число делителей любого ненулевого числа конечно), следовательно, существует конечное число многочленов, которые могут быть делителями f (x ). Осуществив полный перебор, либо покажем неприводимость многочлена, либо разложим его в произведение двух многочленов. К каждому множителю применим указанную схему до тех пор, пока все множители не станут неприводимыми многочленами.

Неприводимость некоторых многочленов над полем рациональных чисел можно установить с помощью простого критерия Эйзенштейна.

Пусть f (x ) многочлен над кольцом целых чисел. Если существует простое число p , что

I. Все коэффициенты многочлена f (x ), кроме коэффициента при старшей степени, делятся на p

II. Коэффициент при старшей степени не делится на p

III. Свободный член не делится на

Тогда многочлен f (x ) неприводим над полем рациональных чисел.

Следует отметить, что критерий Эйзенштейна даёт достаточные условия неприводимости многочленов, но не необходимые. Так многочлен является неприводимым над полем рациональных чисел, но не удовлетворяет критерию Эйзенштейна.

Многочлен , по критерию Эйзенштейна, является неприводимым. Следовательно, над полем рациональных чисел найдётся неприводимый многочлен степени n , где n любое натуральное число больше 1.

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

Теорема 5.1 (основная теорема алгебры многочленов). Поле комплексных чисел алгебраически замкнуто.

Следствие 5 .1.1. НадС существуют неприводимые многочлены только первой степени.

Следствие 5.1.2. Многочленn -ой степени надС имеетn комплексных корней.

Теорема 5.2. Если– комплексный корень многочленаf с действительными коэффициентами, то комплексное сопряженное число- также кореньf .

Следствие 5 .2.1. НадR существуют неприводимые многочлены только первой или второй степени.

Следствие 5.2.2. Мнимые корни многочлена надR распадаются на пары комплексных сопряженных.

Пример5.1. Разложить на неприводимые множители надС и надR многочленx 4 + 4.

Решение. Имеем

x 4 + 4 =x 4 + 4х 2 + 4 – 4х 2 = (x 2 + 2) 2 – 4х 2 = (x 2 – 2х + 2)(x 2 + 2х + 2) –

разложение над R . Найдя обычным способом комплексные корни многочленов второй степени, стоящих в скобках, получаем разложение над С :

x 4 + 4 = (x – 1 – i ) (x – 1 + i ) (x + 1 – i ) (x + 1 + i ).

Пример5.2. Построить многочлен наименьшей степени с действительными коэффициентами, имеющий корни 2 и 1 +i .

Решение. Согласно следствию 5.2.2, многочлен должен иметь корни 2, 1 –i и 1 +i . Коэффициенты его можно найти по формулам Виета:

 1 = 2 + (1 –i ) + (1 +i ) = 4;

 2 = 2(1 – i ) + 2(1 + i ) + (1 – i )(1 + i ) = 6;

 3 = 2(1 – i )(1 + i ) = 4.

Отсюда f =x 3 – 4x 2 + 6x – 4.

Упражнения.

5.1. Разложите на неприводимые множители над С и надR многочлены:

а) х 3 – 6х 2 + 11х – 6;

б) х 4 – 10х 2 + 1.

5.2. Постройте многочлен наименьшей степени с действительными коэффициентами, имеющий двойной корень 1 и простой корень 1 – 2i .

6. Многочлены над полем рациональных чисел

Теорема 6.1 (критерий Эйзенштейна). Пусть f = a 0 + a 1 x + … + a n x n – многочлен с целыми коэффициентами. Если существует такое простое числоp , чтоa 0 , a 1 , … , a n -1 делятся наp , a n не делится наp ,a 0 не делится наp 2 , тоf не приводим над полем рациональных чисел.

Упражнение 6.1. Докажите неприводимость надQ многочленов:

а) f = 2х 5 + 3х 4 – 9х 3 – 6х + 3;б)f = 5х 4 + 6х 3 – 18х 2 – 12х + 54.

Теорема 6.2. Пусть– несокр­атимая ­­дробь, являющаяся корнем многочленаf = a 0 + a 1 x + … + a n x n с целыми коэффициентами. Тогда

a 0  p , a n  q ;

f (1)  p – q, f (–1)  p + q .

Эта теорема позволяет решить задачу отыскания рациональных корней многочлена с целыми коэффициентами. Для этого определяем все делители свободного члена и старшего коэффициента и строим из них всевозможные несократимые дроби. Все рациональные корни содержатся среди этих дробей. Для их определения можно использовать схему Горнера. Чтобы избежать в ней лишних вычислений, используем утверждение 2) теоремы 6.2.

Пример6.1. Найти рациональные корни многочлена

f = 2х 4 + 7х 3 + 3х 2 – 15х – 18.

Решение. Выписываем все дроби, числители которых p – делители 18, а знаменателиq – делители 2:

1, –1, 2, –2, 3, –3, 6, –6, 9, –9, 18, –18,
,
,
.

Производим их проверку по схеме Горнера:

						Комментарий
						f (1) = –21  p – q
						f (–1) = –3  p + q
						х 1 = –2
						х 2 = 3/2

Найдя корень х 1 = –2 и разделив многочлен нах + 2, получили многочлен с новым свободным членом –9 (его коэффициенты подчеркнуты). Числители остальных корней должны быть делителями этого числа, и из списка можно исключить дроби, не удовлетворяющие этому условию. Остальные целые значения исключены, так как не удовлетворяют условию f (1)p – q или f (–1)p + q . Например, для 3 имеемp = 3, q = 1, и не выполняется условиеf (1) = –21p – q (как и второе условие).

Аналогично найдя корень х 2 = 3/2, получили многочлен с новым свободным членом 3 и старшим коэффициентом 1 (когда корень дробный, следует произвести сокращение коэффициентов получившегося многочлена). Ни одно оставшееся число из списка больше не может быть его корнем, и список рациональных корней исчерпан.

Найденные корни следует проверять на кратность.

Если в процессе решения пришли к многочлену второй степени, а список дробей еще не исчерпан, то оставшиеся корни можно найти по обычным формулам как корни квадратного трехчлена.

Упражнение 6.2. Найдите рациональные корни многочлена

а) х 3 – 6х 2 + 15х – 14;

б) х 5 – 7х 3 – 12х 2 + 6х + 36;

в) 2х 4 – 11х 3 + 23х 2 – 24х + 12;

г) 4х 4 – 7х 2 – 5х – 1.

Любое комплексное число задает точку плоскости. Аргументы будут располагаться на одной комплексной плоскости, значения ф-ии распложены на другой комплексной плоскости.

F(z)- комплексная ф-я комплексного переменного. Среди комплексных функций комплексного переменного, особо выделяется класс непрерывных ф-ии.

Опр: комплексная ф-я комплексного переменного называется непрерывной, если , такого что, .+

Геометрический смысл в следующем:

Задает в комплексной плоскости круг, с центром в точке z0 и радиусом < . Аналогично в другой комплексной плоскости неравенство задает круг с радиусом меньше .

Теорема 1: Многочлен f(z)принад. C(z) непрерывен в любой точке комплексной плоскости.

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

Теорема 2: - кольцо многочленов с комплексными коэффициентами, тогда такие значения , что .

Теорема 3.(о неограниченном возрастании модуля многочлена):

Основная теорема алгебры:

Любой многочлен над полем комплексных чисел не 0 степени, имеет в поле комплексных чисел хотя бы один корень.

(При доказательстве будем использовать следующие утверждения):

Д-во: 1. Если a n =0, тогда z=0 – корень f(z).

2. если a n 0, , тогда по Теореме 3 , неравенство задает в комплексной плоскости область, лежащую вне круга радиусом S. В этой области корней нет, т.к. следовательно корни многочлена f(z) следует искать внутри области .

Рассмотрим из Т1. следует, что ф-я f(z) является непрерывной. По теореме Вейерштрасса она достигает в некоторой точке замкнутой области своего минимума, т.е. . Покажем, что точка является точкой минимума. Т.к. 0 Е, то , т.к. вне области Е значения ф-ии , то z 0 – точка минимума, на всей комплексной плоскости. Покажем, что f(z 0)=0. Предположим, что это не так, тогда по Лемме Даламбера , получаем противоречие, т.к. z 0 точка минимума.

Алгебраическая замкнутость:

Опр: поле P называется алгебраически замкнутым, если имеет над этим полем хотя бы один корень.

Теорема: поле комплексных чисел является алгебраически замкнутым. (д-во следует из основной теоремы алгебры).

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

Разложимость:

Теорема: любой многочлен , над полем комплексных чисел, степени выше 1, разложим в произведение линейных множителей.

Следствие 1. Многочлен степени n, над полем комплексных чисел имеет ровно n корней.

След.2: любой многочлен над полем комплексных чисел степени больше 1, всегда приводим.

Опр: Числа мн-ва С\R, т.е. числа вида a+bi, где b не равно 0- называются мнимыми.

2. Многочлены над полем. НОД двух многочленов и алгоритм Евклида. Разложение многочлена в произведение неприводимых множителей и его единственность.

Опр. Многочленом (полиномом) от неизвестного х над полем Р наз. Алгебраическая сумма целых не отрицательных степеней х , взятых с некоторым коэффициентом из поля Р .

Где aiÎP или

Многочлены наз. равными , если равны их коэффициенты при соответствующих степенях неизвестных.

Степенью многочлена наз. наибольшее значение показателя неизвестного, коэффициент при котором отличен от нуля.

Обозначается: N(f(x))=n

Множество всех многочленов над полем Р обозначается: Р[x].

Многочлены нулевой степени совпадают с элементами поля Р , отличными от нуля - нулевой многочлен, его степень неопределенна.

Операции над многочленами.

1. Сложение.

Пусть n³s, тогда , N(f(x)+g(x))=n=max{n,s}.

<P[x],+>

1. операция сложения выполнима и однозначность следует из однозначности сложения элементов поля
2. ассоциативность
3. нулевой элемент
4. многочлен противоположный данному
5. коммутативность

- абелева группа

2. Умножение.

Исследуем алгебраическую структуру <P[x],*>

1. операция выполнима, т.к. поле выполняется операция умножения. Однозначность следует из однозначности операций в поле Р .
2. ассоциативность
3. единичный многочлен
4. обратимыми являются только многочлены в нулевой степени

<P[x],*> - полугруппа с единичным элементом (маноид)

Выполняются дистрибутивные законы, следовательно, <P[x],+,*> - коммутативное кольцо с единицей.

Делимость многочленов

Опр: многочлен f(x), f(x)ÎP[x], P – поле делится на многочлен g(x), g(x)≠0, g(x)ÎP[x], если существует такой многочлен h(x)ÎP[x], что f(x)=g(x)h(x)

Свойства делимости:

Пример: , делим столбиком НОД=(x+3 )

Теорема о делении с остатком: Для любых многочленов f(x), g(x)ÎP[x], cущес-ет единственный многочлены q(x ) и r(x) такие что f(x)=g(x)q(x)+r(x), N(r(x)) или r(x)=0.

Идея док-ва: в существовании рассматриваем два случая n степень g(x)) и делим f(x) на g(x ). Единственность док-ем от противного.

Опр: f(x) и g(x), f(x), g(x)ÎP[x], h(x)ÎP[x] называется НОД f(x) и g(x) если

Алгоритм Евклида

Запишем процесс последовательного деления

f(x)=g(x)q 1 (x)+r 1 (x) (1)

g(x)= r 1 (x) q 2 (x)+r 2 (x) (2)

r 1 (x)= r 2 (x) q 3 (x)+r 3 (x) (3) и т.д.

r k-2 (x)= r k-1 (x) q k (x)+r k (x) (k)

r k-1 (x)= r k (x) q k+1 (x) (k+1)

НОД(f(x),g(x))=d(x)=r k (x)

Идея доказательствава: показываем, что 1) f(x) :(нацело)d(x ) и g(x ):(нацело)d(x); 2) f(x ):(нацело)h(x ) и g(x) :(нацело)h(x) показываем, что d(x):(нацело)h(x ).

Линейное представление НОД

Т: если d(x ) - НОД многочленов f(x) и g(x ), то существуют такие многочлены v(x) и u(x)ÎP[x], что f(x)u(x)+g(x)v(x)=d(x ).

Опр: f(x) и g(x)ÎP[x] всегда имеют общие делители, а именно многочлены нулевой степени, совпадающие с полем Р, если других общих делителей нет, то f(x) и g(x) взаимно просты. (обозначение: (f(x),g(x))=1 )

Т: f(x ) и g(x ) взаимно просты т.и.т.т.к. существуютют такие многочлены v(x) и u(x)ÎP[x], что f(x)u(x)+g(x)v(x)=1.

Свойства взаимно простых многочленов

1. (f(x),g(x))=1, (f(x),q(x))=1, то (f(x),g(x)*q(x))=1
2. f(x)*g(x):(нацело)h(x) и (f(x),g(x))=1, то g(x):(нацело) h(x)
3. f(x):(нацело)g(x), f(x):(нацело)h(x) и (g(x),h(x))=1 , то f(x):(нацело) g(x)*h(x)

Опр: Многочлен f(x), f(x)ÎP[x] называется приводимым над полем Р, если его можно разложить на множители, степени которых больше 0 и меньше степени f(x) т.е.

f(x)=f 1 (x)f 2 (x ), где степени f 1 и f 2 >0,

Приводимость многочленов зависит от поля над которым они рассматриваются. Многочлен неприводим (многочлен, не разлагающийся на множители более низкой степени) над полем Q, и приводим над полем R.

Свойства неприводимых многочленов:

1. Многочлен нулевой степени приводим над любым полем
2. Если многочлен f(x ) не приводим над полем Р , то и многочлен af(x ) также не приводим над полем Р .
3. Пусть даны многочлены f(x) и p(x ) над полем Р , причем p(x ) – неприводим над полем Р , тогда возможны случаи

1) многочлены f(x) и p(x ) взаимно просты

2) f(x ):(нацело)р(x )

Неприводимый многочлен - многочлен, неразложимый на нетривиальные многочлены. Неприводимые многочлены являются неприводимыми элементами кольца многочленов.

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

Многочлен f над полем F называется неприводимым (простым), если он имеет положительную степень и не имеет нетривиальных делителей (т.е., любой делитель либо ассоциирован с ним, либо с единицей)

Предложение 1

Пусть р – неприводимый и а – любой многочлен кольца F[x]. Тогда либо р делит а , либо р и а – взаимно простые.

Предложение 2

Пусть f ∈ F[x], и степень f = 1, значит, f – неприводимый многочлен.

Например : 1. Возьмем над полем Q многочлен х+1. Его степень равна 1, значит, он неприводим.

2. х2 +1 – неприводим, т.к. не имеет корней

СЛУ. Решение системы. Совместные, несовместные, определенные и неопределенные системы. Эквивалентные системы

Системой линейных уравнений над полем F с переменными х1,…хn называется система вида

а11 х1 + … + a1n xn = b1

………………………..

am1 x1 + … + amn xn = bm

где aik , bi ∈ F, m- количество уравнений, а n - количество неизвестных. Кратко эту систему можно записать так: ai1x1 + … + ain xn = bi (i = 1,…m .)

Эта СЛУ является условием с n свободными переменными х1,….хn.

СЛУ делятся на несовместные (не имеют решений) и совместные (определенные и неопределенные). Совместная система вида называется определённой, если она имеет единственное решение; если же у неё есть хотя бы два различных решения, то она называется неопределённой.

Например: над полем Q

х + у =2 - несовместная система

х – у = 0 - совместная определенная (х, у = ½)

2х + 2у = 2 - совместная неопределенная

Две системы л.у. являются эквивалентными, если множества решений этих систем совпадают, то есть, любое решение одной системы одновременно является решением другой. Систему, эквивалентную данной, можно получить:

1. заменив одно из уравнений на это уравнение, умноженное на любое отличное от нуля число.

2. заменив одно из уравнений суммой этого уравнения с другим уравнением системы.

Решение СЛУ осуществляется методом Гаусса.

45* Элементарные преобразования систем линейных уравнений (слу). Метод Гаусса.

Опр. Элементарными преобразованиями С.Л.У н-ся следущие преобразования:

1. Умножения одного из системы уравнений системы на ненулевой элемент поля.

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

3. Добавления к системе или исключение из системы ненулевого уравнения 0*х1+0*х2+…+0*хn=0

4. Перемена местами уравнений

Предл. Пусть система (**)получена ил системы (*) с помощью конечного числа. Элемен-ых преобраз-ий. Тогда система (**)~ система(*). (Без док-ва)

Зам. При записи системы линейных уравнений будем использовать матричную запись.

а11 а12 … а1n в1

а21 а22 … а2n в2

………………….... …

Am1 am2 ... amn вn

Примеры: 1) 2х1 – х3 = 1 2 0 -1 1

х1 – х2 – х3 = 0 1 -1 -1 0

3х1 + 2х2 + 4х3 = 2 3 2 4 2

2) 1 0 1 х1=1

0 1 2 х2=2

3) 1 0 1 2 х1+х3=2 х1=2-х3

0 1 -1 3 х2-х3=3 х2=3+х3

Метод Гаусса

Предл. Пусть имеет система (*)

(а) если все свободные члены равны 0 все вк=0 мн-во решений = F n

(b) k вк=0 0х1+0х2+…+0хn= вк=0 (решений нет)

2. не все aij=0

(a)если в системе есть уравнение вид 0х1+0х2+…+0хn= вк=0 0

(b)если таких уравнений нет b1. Исключим ненулевые уравнения. Найдем самый маленький индекс i1, такой что не все коэф-ты при xij=0.

0……0……….. …. Второй столбец с нулями это i1.

0……0…..*=0….. ….

0……0 ...……… …

1.перестановкой уравнений добьемся, чтобы a1i1 = 0

0 ….. 0… a1i1 = 0 .... .... (1). :=(присваивание) (1) 1/ a1i1 (2). :=(2)-(1)* а2i1

A2i1........... .... 0…. 0…1…. …. 0…. 0..1….. ….. (ступенчатая

0…. 0… а2i1 … 0…..0..0… …. Матрица )

0 ........... 0 .... ami1.. ... ……………… …. …………………… ….

0 ….0 ..аmi1 ... 0……0…………0 ….

Через конечное число шагов получим либо система содержит уравнение вида 0х1+0х2+…+0хn= вк=0 0либо

0……0 1………….. L1 “прямой ход Гаусса” 0....0 1...0..0 .....0........0.... .. “обратный ход

0.......0 0......1..... L2 0....0 0.....1.........0.........0.... .. Гаусса”

0 .......00........0....1 L2 0....0 0......0........1.........0.... ..

.............................. .... ............................................ ..

0........0 0 ............0..1 Lk 0....0 0.......0.........0....0.......1 ..

Переменные xi1, ...... xik назовем главным, остальные свободными.

k=n => c-a определенная

k c-a неопред-ая. Свободным переменным можно предавать производные значения, и вычислять значения главных переменных.

2 0 -1 1 8 (-3) 1 -1 -1 0 *(-2) 1 -1 -1 0

1 -1 -1 0 ~ 2 0 -1 1 ~ 0 2 1 1

3 2 4 2 3 2 4 2 0 5 7 2

Над полем вещественных чисел любой неприводимый многочлен одной переменной имеет степень 1 или 2, причем многочлен 2-й степени неприводим над полем R тогда и только тогда, когда он имеет отрицательный дискриминант, например, многочлен неприводим над полем вещественных чисел, поскольку его дискриминант отрицательный.

Критемрий Эмйзенштейна - признак неприводимости многочлена, названный в честь немецкого математика Фердинанда Эйзенштейна. Несмотря на (традиционное) название, является именно признаком, то есть достаточным условием - но вовсе не необходимым, как можно было бы предположить, исходя из математического смысла слова «критерий»

Теорема (критерий Эйзенштейна) . Пусть - многочлен над факториальным кольцом R (n >0), и для некоторого неприводимого элемента p выполняются следующие условия:

Не делится на p ,

Делится на p , для любого i от 0 до n- 1,

Не делится на.

Тогда многочлен неприводим над F полем частных кольца R .

Следствие. Над любым полем алгебраических чисел существуют неприводимый многочлен любой наперёд заданной степени; например, многочлен, где n >1 и p Ї некоторое простое число.

Рассмотрим примеры применения этого критерия, когда R - кольцо целых чисел, а F - поле рациональных чисел.

Примеры :

Многочлен неприводим над Q.

Многочлен деления круга неприводим. В самом деле, если он приводим, то приводим и многочлен, а так как все его коэффициенты, кроме первого являются биномиальными, то есть делятся на p , а последний коэффициент `амен p и к тому же не делится на то по критерию Эйзенштейна он неприводим вопреки предположению.

Следующие пять многочленов демонстрируют некоторые элементарные свойства неприводимых многочленов:

Над кольцом Z целых чисел, первые два многочлена - приводимые, последние два - неприводимые. (Третий вообще не является многочленом над целыми числами).

Над полем Q рациональных чисел, первые три многочлена являются приводимыми, двое других - неприводимыми.

Над полем R действительных чисел, первые четыре многочлена - приводимые, но является неприводимым. В поле действительных чисел неприводимыми являются линейные многочлены и квадратичные многочлены без действительных корней. Например, разложение многочлена в поле действительных чисел имеет вид. Оба множителя в данном разложении являются неприводимыми многочленами.

Над полем C комплексных чисел, все пять многочленов - приводимые. Фактически, каждый отличный от константы многочлен над C может быть разложен на множители вида:

где n - степень многочлена, a - старший коэффициент, - корни многочлена. Поэтому единственными неприводимыми многочленами над С являются линейные многочлены (основная теорема алгебры).