Алгоритм Кронекера разложения многочлена над кольцом целых чисел.

Метод Шуберта–Кронекера — это классический метод нахождения разложения многочлена с целыми коэффициентами на неприводимые множители. Он основан на двух простых наблюдениях. Пусть f ∈ Z[x], deg f = n. Если f = gh, где g ∈ Z[x] и h ∈ Z[x], то deg g ≤ s или deg h ≤ s, где

s = ⌊n/2⌋. Далее, если x₀ ∈ Z, то f(x₀):g(x₀) и f(x₀):h(x₀).

Метод заключается в следующем. Выбираем x₀, x₁, . . . , x_s — некоторые попарно различные целые числа. Составлям всевозможные наборы c₀, c₁, . . . , c_s, такие, что c_j — произвольный делитель числа f(x_j ) (j = 0, 1, . . . , s). Для каждого такого набора восстанавливаем многочлен g, такой, что g(x_j ) = c_j (j = 0, 1, . . . , s) (например, по формуле интерполяционного многочлена Лагранжа). Делением проверяем f: g. Если f = gh, то применяем к многочленам g и h ту же процедуру. Если f не делится ни на один из построенных многочленов g, то f неприводим над Q.

 

 

34. Геометрические векторы. Линейные операции над ними. Коллинеарные и компланарные векторы < Школьная программа >

Базис. Аффинная (общая декартова) и прямоугольная системы координат.

Теорема. Пусть e₁, e₂ образуют базис на плоскости. Тогда для любого вектора a на плоскости существуют, причем единственные, скаляры α₁ и α₂, такие, что

a = α₁e₁ + α₂e₂

Доказательство. Существование. Отложим векторы из одной точки O. Через конец вектора a проведем прямую параллельно вектору e₂ до пересечения с прямой, на которой лежит e₁. Аналогично, через конец вектора a проведем прямую параллельно вектору e₁ до пересечения с прямой, на которой лежит e₂. Получаем, что a = α₁e₁ + α₂e₂ для некоторых чисел α₁, α₂.

Единственность. Предположим, что имеется два разложения:

т. е. векторы e₁ и e₂ коллинеарны, что невозможно, так как они образуют базис. К аналогичному выводу приходим, предположив, что α₂ <> β₂. Следовательно, α₁ = β₁, α₂ = β₂,  т. е. разложение по базису единственно.

Равенство называется разложением вектора a по базису e₁, e₂, а скаляры α₁ и α₂ —координатами вектора a в базисе e₁, e₂.

Тот факт, что координаты вектора a в базисе e₁, e₂ суть α₁ и α₂, будем записывать следующим образом:

или (чтобы уточнить, в каком базисе заданы координаты)

Совокупность некоторой фиксированной точки O (полюса) и базиса e1, e2 на плоскости называется (аффинной) системой координат. При этом точка O называется началом системы координат, а прямые, проходящие через O параллельно базисным векторам, — ее осями. На каждой из осей задается направление, определяемое направлением соответствующего базисного вектора. Оси системы координат на плоскости традиционно называются осью абсцисс (или осью Ox) и осью ординат (или осью Oy). Координатами точки A в некоторой системе координат O, e1, e2 называются координаты ее радиус-вектора:

[A] = [OA ]

Имеем AB =OA −OB , поэтому координаты вектора равны координатам его конца минус координаты начала.

Базис e1, e2 называется ортогональным, если векторы e1 и e2 ортогональны. Базис e1,e2 называется ортонормированным, если векторы e1 и e2 суть ортогональные единичные векторы. Если базис e1, e2 ортонормированный, то система координат O, e1, e2 называется прямоугольной, или декартовой системой координат.

 

⇐ Предыдущая1234567Следующая ⇒

Поделиться: