[Citat]
Buna ziua
Daca reluam problema din data de 17 ianuarie de calcularea cmmdc si cmmmc am descompus polinoamele x^5+x^4+1 si x^5+x^3+x^2+3x+2.
Eu nu am inteles prea bine cum se poate face aceasta descompunere (fara schema lui Horner sau algoritul Euclid) daca este posibil?
Ca in definitiv problema se reduce la o astfel de descompunere.
Bineinteles daca este posibil acest lucru.
Daca nu se poate sa mi se explce concret pe aceste polinoame schema care se potriveste?
|
O sa scriu cateva randuri, sper sa raspund la intrebare, insa in orice caz trebuie sa reusesc sa dau un "feeling", un mod de percepere intuitiva, de simt practic in cadrul de fata.
Polinoamele erau polinoame peste R[X] unde R era inelul ZZ/5 al intregilor modulo 5. Acest inel este un inel cu descompunere unica in factori primi. Se poate demonstra, la nivel de liceu se poate accepta. (Demonstratia nu este grea, se bazeaza pe algoritmul de diviziune cu rest al lui Euclid. Ori de cate ori avem un astfel de algoritm, am castigat, avem descompunere unica in factori primi. Un element prim este ireductibil, aritmetica este "usoara".)
Sa observam ca avem un cadru "FINIT" de lucru.
Cele doua polinoame au grad 5, deci cmmdc are grad posibil de la 0 la 5, cmmmc are grad posibil de la 5 la 10 (gradul produsului), deci daca avem un calculator imediat putem sa scriem toate divizibilitatile in acest cadru restrans si de aici putem deduce tot ce se cere.
Drumul cel mai scurt, algoritmic, de indicat in aceasta situatie este folosirea algoritmului lui Euclid. Este un algoritm! In plus, dupa cel mult cinci pasi de acelasi fel am terminat. Este ceea ce recomand, dar daca tot ne apucam sa facem calcule brute, le putem lasa pe mana calculatorului...
Data trecuta m-am bagat in vorba doar pentru a arata ca exista si o alta metoda care poate fi pusa pe lista metodelor de lucru. Anume factorizarea.
Sa factorizam impreuna. (Nu recomand asa ceva cu mana, cum am spus, calculatorul se simte acasa intr-o lume cu un numar finit de posibilitati!)
Cautam mai intai pentru
f = x^5 + x^4 + 1
factori. Daca nu gasim factori liniari chiar recomand algoritmul lui Euclid. (Macar un pas, o mica scadere, poate dam de un rest cu factori...)
Un factor liniar este de forma
(x-a)
unde conform teoremei lui Bezout, a este radacina a polinomului in acest caz (si numai in acest caz).
Patratele in R = ZZ/5 sunt:
- pentru zero :: 0
- pentru +/- unu :: 1
- pentru +/- doi :: -1
Deci ridicand la a patra dam de x^4 este 0 sau 1.
a=0 nu intra in discutie ca radacina pentru f. Celelalte valori posibile pentru a conduc la a^4 = 1, deci
f(a) = a^5 + a^4 + 1 = a.1 + 1 + 1 = a+2 .
Deci a=-2 = 3 este radacina.
Trebuie sa calculam catul f / (x-3) . Eu fac aici repede cu Horner.
:: | 1 1 0 0 0 1
-------------------------
3 | se coboara 1
:: | 1 1 0 0 0 1
-------------------------
3 | 1
se calculeaza mereu intr-o astfel de situatie
- | ? C
---------
A | B
valoarea de dupa B prin formula
- | ? C
---------
A | B AB+C
La noi deci pe rand:
:: | 1 1 0 0 0 1
-------------------------
3 | 1 4 2 1 3
0
Deci avem factorizarea
f = (x-3) ( x^4 - x^3 + 2*x^2 +x + 3 ) .
Putem acum sa mai cautam radacini, dar nu dam de nici una.
Atunci singura sansa de descompunere mai departe este sub forma
f ?=? (x-3) ( x^2 + ax + b) ( x^2 + sx + t )
Pentru problema noastra:
- Daca putem descompune, atunci vedem doi factori si se pune problema doar daca unul din ei este si in celalalt polinom.
- Daca nu, mai trebuie sa avem de grija de factorul (x-3) si de acest factor de grad 4 ramas - si AM TERMINAT.
Sa vedem cum putem lucra.
Cautam necunoscutele a,b;s,t cu cele de mai sus.
Atunci desigur vrem sa avem:
- coincidenta in grad 0, deci bt = 3, deci avem patru cazuri:
( b=1, t=3 ),
( b=3, t=1 ),
( b=2, t=-1=4 ),
( b=4, t=2 ) .
- coincidenta in grad 3 : vrem a+s = -1 . Avem cinci cazuri. (0,4), (1,3), (2,2), (3,1), (4,0) . Ne putem usura din munca spunand asa, unul dintre cele doua numere este 0,1,2. Avem doar trei cazuri.
- mai calculam termenul in x, at+bs si deja din cele 3x4 cazuri raman mult mai putine. Ramane in fiecare caz sa vedem daca se potriveste si gradul doi. Gata. dar acestea fiind scrise, nu-i asa ca mult mai bine lucram cu Euclid - sau mai bine cu un computer...
Obtinem mai devreme sau mai tarziu descompunerea:
f = (x-3) ( x^2 + x + 1) ( x^2 + 3x + 3 )
In acest punct calculam g / (x-3) mai intai, g fiind
g = x^5 + x^3 + x^2 + 3x + 2 .
Este o impartire de polinoame. Se face ca pe a VIII-a, cu toata schema, sau daca vrem sa izolam doarpartea cu numere din schema (si stim ce facem) :: Horner:
::| 1 0 1 1 3 2
------------------
3 | 1 3 0 1 1
0
Deci:
g = (x-3) ( x^4 + 3 x^3 + x + 1 )
Pentru cmmdc ajunge acum sa vedem daca unul din factorii (primi, entru ca nu avem factori liniari (nici in f))
f1 = ( x^2 + x + 1 ) sau f2 = ( x^2 + 3x + 3 )
divide ( x^4 + 3 x^3 + x + 1 ) .
Daca primul factor, f1, divide, atunci f1 divide
x^4 + 3x^3 - x^2 . Nu este cazul, deoarece impartim cu x^2, factor relativ prim cu f1, dam de ceva ce nu se divide cu f1 si nici nu mai este loc de impartit.
Daca al doilea factor, f2, divide, atunci f2 divide
( x^4 + 3 x^3 + 3x^2 - 3x^2 + x + 1 )
=
( x^4 + 3 x^3 + 3x^2 ) - restul
unde restul este ... -3(x^2 + 3x + 3 ) . Am castigat, divide.
Calculele nu sunt sistematice, deci acest mod de abordare nu se recomanda (nici macar pentru cei ce stiu ce fac). Asa ceva se poate recomanda insa daca trebuie sa ne verificam (si nu avem computer), de exemplu daca este miza mare pe puncte, olimpiada sau bacalaureat sau examen si punctele pentru bursa...
Metoda de factorizare a unui polinom de grad patru descrisa mai sus este insa deseori foarte utila! Ea ajuta des la factorizarea unui polinom de grad IV peste ZZ sau IR, in orice caz este mica parghie in aceasta cautare.
Ma gat aci.
P.S. Scheme lui Horner se invata in 5 minute,
nu se mai uita,
economiseste in fiecare examen (de exemplu bac) in care avem de calculat valoarea unui polinom intr-un punct sau catul impartirii la un factor liniar (x-a) ... cel putin 5 minute si o cantitate de nervi direct proportionala cu miza pe examen.
resupun ca gr4=gr1xgr3,deci admitem pentru inceput ca din acea inmultire care da gr.4 un grad este unu.Aceasta ar insemna ca exista o valoare sa zicem r pentru care ar exista x-r=zero.Am incercat cu toate valorile 0,1,2,3,4 pentru x(respectiv pt.r)si nu am reusit sa gasesc nici o valoare r care sa verifice x-r=0,deci ma gandesc atunci ca polinomul pe care l-am luat drept x-a(deci de gradul unu)nu poate exista si atunci ma mut la un grad superior adica 2.Idem si pentru celalalt polinom deci gr4nu poate fi decat gr2xgr2.
Access general
Conţine mesaje necitite
