Faktorizacija
Faktorizacija u matematici je razlaganje nekog objekta (na primer, broja, polinoma, ili matrice) u produkt nekih drugih objekata, ili faktora, koji kada se međusobno pomnože daju origanal. Na primer, broj 15 faktorišemo na proste brojeve 3 × 5, a polinom x2 − 4 na (x − 2)(x + 2). U svakom slučaju je dobijen jednostavniji oblik.
Cilj faktorisanja je obično, pojednostavljenje nečega na “njegove polazne elemente”, kao što su za brojeve, prosti brojevi, ili za polinome, neraščlanjivi polinomi. Faktorisanje celih brojeva pokriveno je u okviru osnovne teoreme aritmetike i faktorisanje polinoma u okviru osnovne teoreme algebre. Vijetove formule vezuju koeficijent polinoma sa njegovim korenom.
Suprotno od faktorizacije polinoma je proširenje, množenje zajedničkih faktora polinoma kako bi se proširio polinom, napisan kao zbir članova.
Rastavljanje na faktore za velike brojeve se ispostavilo kao veliki problem. Ne postji poznata metoda koji bi mogla da izvrši to za kratko vreme. Njena složenost je osnova zaštite nekih asimetrično kriptografskih algoritama, kao što je RSA (algoritam).
Matrica može takođe biti faktorisana u produkt specijalnih tipova matrica, za aplikaciju u kojoj je takav objekat pogodan. Jedan dobar primer ovoga je ortogonalna ili jedinična matrica , i trougaona matrica. Postoje različiti tipovi: QR dekompozicija, LQ, QL, RQ, RZ.
Još jedan primer je fatkorisanje funkcija kao kompozicije drugih funkcija koje imaju određene osobine; na primer, svaka funkcija se može posmatrati kao kompozicija surjektivne funkcije sa nekom injektivnom funkcijom. Ovakav oblik je generalizovan pomoću sistema faktorizacije.
Celi brojevi
urediPrema osnovnoj teoremi aritmetike, svaki pozitivan ceo broj veći od 1 ima jedinstveno rastavljanje na faktore. Dati algoritam za faktorisanje celih brojeva može da faktoriše bilo koji ceo broj na njegove proste primenom ponavljanja ovog algoritma.[1] Za velike brojeve, nije poznat nijedan efikasan algoritam.
Polinomi
urediModerne tehnike za faktorisanje polinoma su brze i efikasne, ali koriste sofisticirane matematičke ideje (videti faktorizaciju polinoma). Ove tehnike se koriste za konstrukciju kompjuterskih rutina za faktorisanje polinoma u sistemima za kompjutersko izračunavanje. Klasične metode se zasnivaju ili na tome da se polinomi faktorišu tako da imaju niže stepenove ili da se prepoznaju kao deo neke klase poznatih primera i te metode nisu pogodne za kompjutersku implementaciju. Ovaj članak je vezan za ove, klasične tehnike.
Dok je uopšteno značenje faktorisanja predstavljeno samo kao pisanje nekog izraza kao proizvod prostijih izraza, nejasan termih prostijih će biti definisan preciznije kod specijalnih klasa izraza. Kod faktorisanja polinoma, faktori treba da budu polinomi nižeg stepena. Dok jeste faktorisanje izraza, ali to nije polinomska faktorizacija jer faktori nisu polinomi.[2] Takođe, faktorisanje konstanti npr. se ne bi smatralo polinomskom faktorizacijom jer jedan od faktora nema niži stepen od originalnog izraza.[3] Postoji još jedan problem, koji je vezan za koeficijente faktora. U klasičnom rešavanju poželjlno je da koeficijenti faktora budu istog tipa kao koeficijenti originalnih polinoma, a to je faktorisanje polinoma sa celobrojnim koseficijentima u faktore sa celobrojnim koeficijentima, ili faktorisanje polinoma sa realnim koeficijentima u faktore sa realnim koeficijentima. To nije moguće uvek uraditi, i za polinom koji koji ne može biti faktorisan na ovaj način se kaže da je nesvodljiv preko ovog tipa koeficijenta. Recimo, x2 -2 je nesvodljivo na cele brojeve i x2 + 4 je nesvodljivo na relane brojeve. U prvom primeru, celi brojevi 1 i -2 mogu da se smatraju i kao realni brojevi, i ako jesu, onda pokazuje da je faktorisanje ovog polinoma nad realnim brojevima moguće (ponekad se kaže da se polinom deli preko realnih brojeva). Slično, kako su celi brojevi 1 i 4 takođe i realni a stoga i kompleksni brojevi, x2 + 4 se deli preko kompleksnih brojeva, npr. .
Osnovna teorema algebre se može razumeti kao: Svaki polinom stepena n sa kompleksnim brojevima kao koeficijentima se deli kompletno, na n linearnih faktora.[4] Uslovi u ovim faktorima, koji su koreni polinoma, mogu biti realni i kompleksni. Kako se kompleksni koreni polinoma sa realnim koeficijentima nalaze u obliku konjugovano kompleksnih parova, rezultat implicira na to da se svaki polinom sa realnim koeficjentima deli na linearne i/ili nesvodljive kvadratne faktore sa realnim koeficijentima (jer kad se dva linearna faktora sa konjugovano kompleksnim uslovima pomnože međusobno, rezultat je kvadratan sa realnim koeficjentima). Iako je struktura faktorizacije poznata u ovim slučajevima, nalaženje faktora može biti kompjuterski izazov, i prema Abel-Rufinijevoj teoremi koeficijenti i dodatni članovi u faktorima ne mogu biti izraženi preko n-tog korena .
Istorija o faktorisanju polinoma
urediStudenti koji su upoznati sa faktorisanjem kao primarnom metodom prilikom rešavanja kvadratnih jednačina će možda biti iznenađeni saznanjem da je to jedna od najnovijih metoda rešavanja istih. Vera Sanford ističe u svojoj knjizi A Short History of Mathematics (1930).[5] “s obzirom na dosadašnji napredak u polju rešavanja kvadratnih jednačina faktorisanjem, interesantno je istaći da ovaj metod nije korišćen sve do Hariotovog rada 1631. U ovom slučaju, autor ignoriše činjenice koje si doprinele razvoju negativnih korena.” Hariot je umro 1621, i kao i ostale njegove knjige, ova knjiga, Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas, je objavljena nakon njegove smrti. Članak o Hariotu na veb stranici Univerziteta svetog Andreja vezanog za istoriju matematike, govori da je u njegovom ličnom spisu vezanom za rešavanje kvadratnih jednačina Hariot koristio pozitivna i negativna rešenja, ali njegov urednik, Valter Varner, to nije predstavio u njegovoj knjizi. Hariotov metod faktorisanja možda izgleda drugačije od onoga što današnji studenti očekuju. U svom prvom delu (Sectio Prima) Hariot crta tabele kako bi ilustrovao sabiranje, oduzimanje, množenje i deljenje monoma, binoma i trinoma. Zatim u drugom delu pokazuje preciznije množenje koje predstavlja osnove njegovog metoda faktorisanja. On postavlja jednačinu aa − ba + ca = + bc, i pokazuje da se ovaj način podudara sa oblikom množenja koji je on prethodno predstavio kao,
a − b aa − ba (===) (Hariot koristi dugačak znak jednakosti preuzetog od Roberta Rekorda) a + c ca − bc
faktorisanje četiri uslova prilagođenog izraza aa − ba + ca − bc. Ovaj primer se može videti na strani 16 Artis Analyticae Praxis ad Aequationes Algebraicas Resolvendas.
Hariot ispisuje oblik svake mogućnosti (a ± b)(a ± c) gde je a nepoznata (gde danas koristimo x ) a kada mu zatreba za faktorisanje, uzima jedan od oblika koji se podudaraju. Razdvajanjem linearnog koeficijenta na dva dela on može da razloži problem na jedan od oblika.
Uopštene metode
urediPostoji svega par uopštenih metoda koje se mogu primeniti na bilo koji polinom u bilo kojoj promenljivoj (jednovarijantan slučaj) ili veći broj promenljivih (viševarijantan slučaj).
Najveći zajednički delilac
urediNaći, pregledanjem, monom koji je najveći zajednički delilac (poznat i kao nzd) za sve date polinome i faktorisati ga kao zajednički faktor je u domenu distributivnosti. Ovo je najčešće korišćena tehnika faktorisanja. Na primer:[6]
Faktorisanje grupisanjem
urediMetod koji je ponekad koristan, ali ne garantuje rešavanje problema, je faktorisanje grupisanjem.
Faktorisanje grupisanjem je odrađeno kada se uslovi u okviru polinoma razvrstaju u dve ili više grupa, gde svaka grupa može biti faktorisana poznatom metodom. Kombinovanjem rezultata parcijalnih faktorisanja se može doći do faktorisanja orignalnog izraza.
Na primer, faktorisati polinom
- :
- grupusanje sličnih oblika,
- izvlačenje najvećeg zajedničkog delioca iz svake zagrade,
- izvlačenje zajedničkog binoma,
Grupisanje možda neće svaki put dovesti do rešenja, ako se polinom koji treba da se faktoriše sastoji od četiri člana i ako je on rezultat prilikom množenja dva binoma (preko FOIL metode na primer), onda tehnika grupisanjem može voditi ka faktorisanju, kao u primeru iznad.
Korišćenje teoreme faktora
urediZa jednistven polinom, p(x), teorema faktora glasi da je a koren polinoma (tj., p(a) = 0, takođe i nulti polinom) ako i samo ako je (x - a) faktor od p(x). Drugi faktor u faktorisanju p(x) se može naći preko deljenja složenih polinoma ili sintetičkog deljenja.
Na primer, posmatrajmo polinom Pregledanjem vidimo da je 1 koren ovog polinoma (posmatrati kao da je koeficijent sabran sa 0), tako da je (x - 1) faktor polinoma. Putem deljenja složenih polinoma imamo
Jednovarijantni slučaj, koristeći se karakteristikama korena
urediKada je jednovarijantni polinom kompletno faktorisan u linearne faktore (faktori prvog stepena), svi koreni polinoma su poznati i množeći faktore zajedno, odnos između korena i koeficjenta se može razmatrati. Formalno, ovakvi odnosi su poznati i kao Vijetove formule. Ove formule ne pomažu u faktorisanju polinoma osim kao pomoć prilikom nagađanja mogućih korena. Ipak, ako je neka informacija o korenima poznata, ona može biti kombinovana sa formulama kako bi se dobili traženi koreni .
Na primer, možemo faktorisati ako znamo da je zbir dva korena nula. Neka su i tri korena polinoma. Onda Vijetove formule glase :
Pretpostavljjući da je odmah dobijamo da je i svodimo druge dve jednačine na Pošto su koreni 5, 4 i -4 imamo
Nalaženje racionalnih korena
urediAko (jednovarijantni) polinom, f(x), ima racionalan koren, p/q (p i q su celi brojevi i q ≠ 0), onda po teoremi faktora f(x) ima faktor,
Ako, prilikom sabiranja, polinom f(x) ima celobrojne koeficijente, onda q mora da jednako podeli cele brojeve prema najvećem zajedničkom deliocu članova polinoma, i, u faktorisanju f(x), samo član (qx - p) će biti poznat.
Ako (jednovarijantni) polinom sa celobrojnim koeficijentima, recimo,
ima racionalan koren p/q, gde su p i q celi brojevi koji su uzajamno prosti, onda prema teoremi racionalnih korena, p je celobrojni delilac od an i q je celobrojni delilac od a0.[7]
Ako želimo da faktorišemo polinom možemo da potražimo racionalne korene p/q gde p deli -6, q deli 2 i p i q nemaju zajedničkog delioca većeg od 1. Pregledanjem, vidimo da ovaj polinom ne može imati negativne korene. Pretpostavimo da je q = 2 (u suprotnom bismo tražili celobrojne korene), zamenimo x = p/2 i postavimo da je polinom jednak 0. Deljenjem sa 4, dobijamo polinomsku jednačinu koja će imati celobrojno rešenje 1 ili 3 ako je originalni polinom imao racionalne korene traženog tipa. Kako je 3 rešenje ove jednačine (a 1 nije), originalni polinom je imao racionalne korene 3/2 i odgovarajući član (2x - 3). Preko deljenja složenog polinoma imamo faktorisanje
Za kvadratne polinome sa celoborjnim koeficijentima koji imaju racionalne korene, prethodna razmatranja vode ka tehnikama faktorisanja poznatim kao ac method faktorisanja.[8] Pretpostavimo da je kvadratni polinom sa celobrojnim koeficijentima:
i da ima racionalne korene, p/q i u/v. (ako je diskriminanta, , kvadrat oni postoje, u suprotnom imamo iracionalna ili kompleksna rešenja, i onda neće biti racionalnih korena.) I q i v moraju biti delioci od a tako da možemo pisati ove delove sa zajedničkim imeniocem od a, koji može biti napisan kao -r/a i -s/a (korišćenje negativnih je bolje i vodi ka lepšem krajnjem rešenju) Onda,
Pa, imamo :
gde je rs = ac i r + s = b. Ac metod za faktorisanje kvadratnih polinoma je nalaženje r i s, dva člana broja ac čiji je zbir b i njihovo korišćenje u faktorizacionoj formuli za gore prikazan kvadratni polinom.
Kao primer posmatrajmo kvadratni polinom :
Pregledanjem faktora za ac = 36 dovodi do 4 + 9 = 13 = b.
Prepoznatljivi obrasci
urediRešavanje dva (ili više) izraza se može izvršiti pomoću algoritma za množenje, suportan proces od faktorisanja, oslanja se na prepoznavanje obrasca u izrazu koji treba da se faktoriše i zapažanjem kako nastaje ovakav obrazac. Ovo su neki od dobro poznatih obrazaca.[9]
Razlika kvadrata
urediKlasičan tip algebarskog faktorisanja se primenjuje na razliku kvadrata . Tako što se primenjuje formula:
na bilo koja dva izraza, i ako jesu i ako nisu prefektni kvadrati.
Ovakva jednostavna forma se često koristi i za mnogo komplikovanije izraze koji na prvi pogled ne izgledaju kao razlika dva korena. Na primer,
Zbir/razlika dva kuba
urediJoš jedna formula faktorisanja i to za zbir ili razliku dva kuba. Zbir se može faktorisati kao:
a razlika kao:
Razlika dva četvrta stepena
urediJoš jedna formula, za razliku dva četvrta stepena, kao što su:
Zbir/razlika dva n-ta stepena
urediPrethodne faktorizacije razlika i zbirova stepenova se mogu proširiti na bilo koji pozitivan ceo broj stepena n.
Za bilo koje n, uopštena faktorizacija je:
Odgovarajuća formula za zbir dva n-ta stepena zavisi od toga da li je n paran ili neparan. Ako je n neparan, b se može zameniti sa −b u formuli iznad, i to daje:
Ako je n paran, razmatramo dva slučaja:
- Ako je n stepen broja 2 onda se ne može faktorisati (preciznije, nesvodljivo za racionalne brojeve).
- U suprotnom, gde je m neparan. U ovom slučaju, imamo,
Specifično, za neke male vrednosti za n imamo:
Zbir/razlika dva n-ta stepena preko polja algebarskih brojeva
urediPrethodne faktorizacije daju članove sa koeficijentima istog tipa kao što su izrazi koji treba da se faktorišu—na primer, polinom sa racionalnim koeficijentima (±1 u mnogim slučajevima) je podeljen na članove koji imaju racionalne koeficijente. Međutim, faktorizacija u kojoj su koeficijenti članova algebarski brojevi, može dovesti do članova nižih stepena, kao u formulama koje slede i to se može dokazati preko teoreme konjugovano kompleksnih korena
Zbir dva člana koji imaju jednake stepenove se faktoriše kao:
Razlika dva člana koji imaju jednake stepenove se faktoriše kao:
Zbir ili razlika dva člana koji imaju jednake stepenove se faktoriše kao:
Na primer, zbri ili razlika dva peta stepena se faktoriše kao:
i zbir dva četvrta stepena se faktoriše kao:
Proširenje binoma
urediBinomna teorema sadrži obrazac za koeficijente koji omogućava lako prekoznavanje faktorizacija kada je polinom stepen nekog binoma.
Na primer, perfektani kvadrati trinoma su kvadratni polinomi koji mogu da se faktorišu kao:
i
Neki kubni polinomi su četvoročlani perfektni kubovi koji mogu da se faktorišu kao:
i
Generalno, koeficijenti proširenih polinoma su dati kao n-ti red Paskalovog trougla. Koeficijenti od imaju iste apsolutne vrednosti ali se menjaju u znaku.
Ostale formule faktorizacije
urediKorišćenje formula za korene polinoma
urediBilo koji jednovarijantni kvadratni polinom (polinom oblika ) može biti faktorisan preko polja kompleksnih brojeva korišćenjem kvadratne formule, sledi:
gde su i dva korena polinoma, ili oba realna ili oba kompleksna u slučaju gde su a, b, c svi realni, nađeni pomoću kvadratne formule.
Kvadratna formula važi za sve polinome sa koeficijentima bilo kog polja (posebno, realni i kompleksni brojevi) osim onih koji imaju karakteristiku dva.[10]
Takođe postoje i formule za kubne polinome i polinome četvrtog stepena koje se mogu koristiti na isti način. Međutim, nema algebarskih formula za koeficijente koji odgovaraju svim jednovarijantnim polinomima višeg stepena, prema Abel-Rufinijevoj teoremi.
Faktorisanje preko kompleksnih brojeva
urediZbir dva kvadrata
urediAko a i b predtavljaju realne brojeve, onda zbir njihovih kvadrata može biti napisan kao proizvod kompleksnih brojeva. Ovaj proizvod je formula faktorizacije:
Za primer, može se faktorisati u .
Vidi još
uredi- Dopuna do potpunog kvadrata
- Ojlerova metoda faktorizacije
- Fermatova metoda faktorizacije
- Rastavljanje na faktore
- Faktorizacija monoma
- Neodređena faktorizacija
- Particija (teorija brojeva) - način pisanja broja kao zbir pozitivnih celih brojeva.
- Prost delilac
- Sinteza programa
- Tabela Gausove faktorizacije celih brojeva
Reference
uredi- ^ Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (5th izd.), Oxford Science Publications, ISBN 978-0198531715
- ^ Fite 1921, str. 20.
- ^ Even if the 3 is thought of as a constant polynomial so that this could be considered a factorization into polynomials.
- ^ Klein 1925, str. 101–102
- ^ Sanford, Vera (2008) [1930]. A Short History of Mathematics. Read Books. ISBN 978-1-4097-2710-1.
- ^ Fite 1921, str. 19.
- ^ Dickson 1922, str. 27.
- ^ Stover, Christopher AC Method - Mathworld
- ^ Selby 1970, str. 101.
- ^ In these fields 2 = 0 so the division in the formula is not valid.
Literatura
uredi- Burnside, William Snow; Panton, Arthur William (1960) [1912], The Theory of Equations with an introduction to the theory of binary algebraic forms (Volume one), Dover
- Dickson, Leonard Eugene (1922). First Course in the Theory of Equations. New York: John Wiley & Sons.
- Fite, William Benjamin (1921). College Algebra (Revised). Boston: D.C. Heath & Co.
- Klein, Felix (1925). Elementary Mathematics from an Advanced Standpoint; Arithmetic, Algebra, Analysis. Dover..
- Selby, Samuel M., CRC Standard Mathematical Tables (18th ed.), The Chemical Rubber Co.
Spoljašnje veze
uredi- Hazewinkel, Michiel , "Factorization of polynomials", ur. (2001). Encyclopedia of Mathematics. Springer. ISBN 978-1-55608-010-4. .
- One hundred million numbers factored on html pages.
- WIMS Factoris je onlajn alat za faktorizaciju.
- Wolfram Alpha can factorize too.