Факторизацията на многочлени или полиномната факторизация в математиката и компютърната алгебра е изразяване на многочлен (полином) с коефициенти в дадена област или в целите числа като произведение на неприводими множители с коефициенти в същата област. Това е крайно разлагане на многочлена на множители (фактори) и един от основните компоненти на компютърните системи за алгебрично смятане.

Основната теорема на алгебрата гласи, че всеки многочлен над полето от комплексни числа може да бъде представен като произведение на линейни многочлени, еднозначно с точност до постоянен множител и реда на множителите.

Популярни примери за факторизация на многочлени са формулите за съкратено умножение и формулите на Виет.

Противоположното на факторизацията на полиноми е разширяването им, умножаването на полиноми по множители, за да се получи „разширен“ полином, записан като сума от членове. Пример за разширяване е биномът на Нютон.

Математическо описание Целта на факторизацията е за даден полином от полиномен пръстен да се намери краен набор от неприводими полиноми , , такива че .

Множителите не е необходимо всички да са различни, т.е. могат да се появят в тази факторизация с кратност, по-голяма от 1.

Ако пръстенът на коефициентите е факториален пръстен, тогава, съгласно теоремата на Гаус, също е факториален пръстен. В този случай съществува система от прости елементи, такава че това представяне е уникално с точност до реда и асоциативността, и всяко е елемент от системата от прости числа. В пръстени, които не са факториални пръстени, обикновено не е възможно да се намери уникална факторизация.

В областта на комплексните числа всеки полином от -та степен може да бъде записан като произведение на точно линейни множителя .

Това е едно от твърденията на основната теорема на алгебрата. Казва се, че полиномът се разлага на своите линейни множители, а са точно нулите на съответната полиномна функция.

Класически методи

Получаване на линейни множители Метод на Кронекер

Съвременни методи

Разлагане на едномерни полиноми върху цели числа Разлагане върху алгебрични разширения (метод на Трагер)

Примери

История Първият алгоритъм за факторизация на многочлени е публикуван от Теодор фон Шуберт през 1793 г.FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, pp. 172–182(1793) Леополд Кронекер преоткрива алгоритъма на Шуберт през 1882 г. и го разширява до многомерни полиноми и коефициенти в алгебрично разширение. Но по-голямата част от знанията по тази тема не са по-стари от около 1965 г. и първите компютърни алгебрични системи:Kaltofen, Erich (1990), "Polynomial Factorization 1982-1986", in D. V. Chudnovsky; R. D. Jenks (eds.), Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics, vol. 125, Marcel Dekker, Inc., CiteSeerX 10.1.1.68.7461

Съвременните алгоритми и компютри могат бързо да факторизират едновариантни многочлени от степен над 1000, имащи коефициенти с хиляди цифри. Пример за степен 2401, отнемаща 7,35 секунди, се намира в раздел 4 в: Харт, ван Хой, Новоцин: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, pp. 163–170 (2011). За тази цел, дори за факторизиране върху рационални числа и числови полета, основна стъпка е факторизацията на полином върху крайно поле.

Вижте също Факторизация Формули за съкратено умножение Формули на Виет Нютонов бином

Източници

Категория:Аритметика Категория:Елементарна алгебра Категория:Полиноми