Diszkrét matematikai algoritmusok

A két szám (vagy polinomok) megszorításának szokásos módja O (n 2) időt vesz igénybe. Az alábbiakban leírjuk, hogyan csökkenthetjük a szorzási időt O (n log n) -ra a Fourier Jean Baptiste Joseph segítségével.

Meg kell jegyeznünk, hogy a polinomok sokszorosítását is figyelembe vesszük, mert bármelyik egész szám egy adott pont polinomjának értéke lehet. A legtöbb számrendszer esetében célszerű a rendszer alapját ebben a pontban venni (például egy tizedes rendszer esetében ez a pont 10 lesz). Ezután a hosszú szám lesz a kívánt polinom együtthatóinak összekapcsolása, és az egyes koefficiensek értéke nem negatív, és kisebb, mint a rendszer alapja. Ugyanakkor a nem nullázott együtthatók száma nem haladja meg az eredeti számok számát.

Polinomok ábrázolása

Először is, meghatározzuk a polinomiális kulcs fogalmát a további érveléshez. Az x változó A (x) polinomja az F mező fölött van:

A (x) = a 0 x 0 + a 1 x 1 + ... + a n -1 x n -1

Az értékek az F mezőhöz tartoznak. Ezeket az értékeket a polinom együtthatóinak nevezik. A nem exponenciális együtthatókkal rendelkező legnagyobb exponens a polinom mértéke. A két polinom összegét egy polinomnak nevezzük, amelynek minden együtthatója megegyezik az eredeti polinomok megfelelő koefficienseinek összegével. Vagyis, ha

A két polinom megszorzásának eredménye a termék - C (x) = A (x) B (x). A szorzást az alábbiak szerint végezzük: az A (x) polinom minden egyes kifejezését megszorozzuk a B (x) polinom minden egyes idejével, majd a hasonló feltételek ugyanolyan hatáskörökkel való csökkentését végezzük.

jóváhagyás

A polinomi termék mértéke megegyezik a faktorok fokának összegével:

fokozat (C) = fokozat (A) + fokozat (B)

A polinom meghatározása az együtthatók vektorával

Adjon polinomiát

akkor az együtthatóvektor a = (a 0. a 1. ..., an).

Polinom megadása egy sor értékekkel

Meghatározzuk az x különböző x pontokat. X 1 ..., x n -1. Az n-nél kisebb fokú A (x) polinomot ezekben a pontokban az értékek egyedileg határozzák meg, vagyis az n paraméter-érték párokat.

ahol yk = A (xk), ahol k = 0, 1, ..., n-1.

polinom ábrázolása az értékeket előre meghatározott pont ideális számos művelet: különösen szorzás polinomok elegendő szaporodnak az értéket az egyes pontok (értékek polinomok kell adni az ugyanazon helyszínen). Mindazonáltal szem előtt kell tartani, hogy a polinomok fokának szorzása hozzáadódik, és az n-nél kisebb fokú két polinomok terméke n fokkal nagyobb lehet, mint n. Továbbá ismert, hogy kevesebb mint 2 n. így 2 n pont elegendő a termék rekonstruálására. Így két, n-nél kisebb fokú polinom szaporodik. Kezdetben hasznos, hogy polinomiális értékek nem n-ben legyenek. de 2 n ponton. Ezután ezeket az értékeket az O (n) időszakonként megszorozzuk, és megkapjuk a termék reprezentációját argumentum-érték párok formájában.

Tétel (az interpoláció egyedisége)

Bármely meghatározott 0. y 0), (x 1 y 1), ..., (x n -1. Y n -1)> argumentum érték párt (x i mind különbözőek) létezik egy egyedülálló polinom A (x) foka kisebb, mint n. amelyre yk = A (xk), a k = 0, 1, ..., n-1 esetében.

Bizonyítás. Ezt a tételt igazolhatjuk az egyenérték yk = A (xk) bevezetésével a mátrix formában.

Ezután meg kell győződnünk arról, hogy a polinom összes gyökeit tartalmazó matrix meghatározója nem nulla, feltéve, hogy minden xi különböző. Ebből következik, hogy ez a mátrix nem degenerált. Ez azt jelenti, hogy a mátrix reverzibilis. Más szavakkal, az oszlopban az együtthatók oszlopát találjuk.

megjegyzés

Nem lehet ezt a tételt bizonyítani, hanem csak a Lagrange interpolációs képlet igazságát.

Polinomok szorzása

Ha megtanulod, hogyan mozog gyorsan az együtthatókról az értékekre és vissza, akkor a polinomok szorzata több pontot adhat az adott pontokon (az együtthatók értékekre, szorzókra, vissza).

Lehet használni bármilyen halmaza N pontok, hanem a hagyományos módon, csökkentheti a konverziós mindkét irányban a O (n log n). Amint később látni fogjuk, ez kényelmes, hogy a pontok komplex egységgyök, ebben az esetben, mind az átmenet csökken az úgynevezett diszkrét Fourier-transzformáció és annak inverz transzformációs, amelyek figyelembe O (n log n) műveleteket.

A koefficiens vektor által megadott polinomok szorzásának rendjét ábrázoljuk.

Itt az ω i 2 n szimbólumok a 2. fokú egység összetett gyökereit jelölik. az i. Ha két, n-nél kisebb fokú polinomot megszorozunk, egy 2n-nál kisebb fokú polinomot kapunk. ezért kezdetben polinomok-tényezõkkel egészíthetjük ki a nullás együtthatókat. Ezután foglalkozunk a 2 n alatti fokú polinomokkal. és ezért a n n fokú komplex gyökereket használjuk az egységből, amelyet ω i 2 n jelöli i = 0, 1, ..., 2 n -1.

A két polinom gyors szorzására szolgáló algoritmus a következőképpen írható:

1. Az együtthatók számának megduplázása. Komplement polinomok A (X) és B (x) nulla vezető együtthatók úgy, hogy az elemek száma az egyes polinom van 2 n elemek.
2. Az értékek kiszámítása. A gyors Fourier-transzformáció segítségével számolja ki az A (x) és B (x) polinomok értékeit az olyan pontokon, amelyek a 2. n fokú gyökerekből származnak.
3. Pontochechenoe szorzás. Az A (x) és a B (x) polinomok értékeit pontosan szorozzuk egymással. Ennek eredményeképpen a C n × x = A (x) B (x) polinom értékei a 2. n n fokú gyökerekből származnak.
4. Interpoláció. A C polinom (x) együtthatóit az inverse Fourier transzformációval kapjuk meg.

Komplex gyökerek az egységből

Az egység n fokú komplex gyökerével az összetett ω szám olyan, hogy ω n = 1. Nyilvánvaló, hogy pontosan n komplex gyökerek vannak az adott egyenlethez. Ezek a gyökerek egyenletesen oszlanak el a nulla sugarú körön belüli körkörön, ahogy azt az alábbi ábra szemlélteti.

Az ω n = 1 egyenlet megoldásai az exp (2π ik / n) forma, a k = 0, 1, ..., n -1. Az ω = exp (2π i / n) érték az n fokú gyökér fő értéke az egységből.

Bevezetünk néhány kiegészítő állítást.

Lemma 1 (a csökkentéskor)

Minden k ≥ 0, n ≥ 0, d> 0 egész számra igaz