Funktion som linearkombination

se
http://peecee.dk/?id=21080

Du skal bruge Euklids algoritme baglæns.

Euklid viste, at sfd(a,b) altid kan udtrykkes som en linearkombination af heltallene a og b. Der findes altså altid heltal x og y sådan at ax + by = d hvor d = sfd(a,b). Givet to heltal a og b producerer Euklids algoritme sfd(a,b). Udføres processen baglæns finder man netop linearkombinationen. Først illustreres Euklids algoritme på heltal og derefter kigges på polynomier.

Som eksempel ønsker vi at bestemme sfd(6,112). Euklids algoritme forløber så

112 = 18*6 + 4

6 = 1*4 + 2

4 = 2*2 + 0

så sfd(6,112) = 2. Som nævnt kan 4 skrives som en linearkombination af 6 og 112, altså 2 = 6x + 112y. Måden at finde x og y på, er ved at anvende metoden baglæns. Tag udgangspunkt i anden linie og løs mht største fælles divisor:

2 = 6 - 1*4

Gå én linie op i algoritmen til linien 112 = 18*6 + 4 og løs mht resten: 4 = 112 - 18*6. Indsæt dette udtryk i udtrykket for sfd'en ovenfor:

2 = 6 - 1*4

2 = 6 - 1*(112 - 18*6)

2 = 19*6 - 1*112

og vi har fundet de ønskede heltal (x=19 og y=-1).

Metoden virker også på polynomier. Givet to polynomier F0(x) og F1(x), hvor F1 ikke er nulpolynomiet, konstrueres en følge af polynomier Q2(x), Q3(x),... og F2(x), F3(x), ... ved at bruge divisionsalgoritmen i hvert skridt:

F0(x) = Q2(x)*F1(x) + F2(x), 0 <= deg(F2) < deg(F1)
F1(x) = Q3(x)*F2(x) + F3(x), 0 <= deg(F3) < deg(F2)
F2(x) = Q4(x)*F3(x) + F4(x), 0 <= deg(F4) < deg(F3)
:
Fn-2(x) = Qn(x)*Fn-1(x) + Fn(x), 0 <= deg(Fn) < deg(Fn-1)
Fn-1(x) = Qn+1(x)*Fn(x)

Så er sfd(F0,F1) = Fn(x) pånær en eventuel konstant faktor. Ved at udføre processen baglæns som i ovenfor anførste eksempel, kan man finde polynomier U(x) og V(x) så Fn(x) = U(x)*F0(x) + V(x)*F1(x).

I det aktuelle eksempel er

F0(x) = f(x) = x^5+2x^3+x^2+x+1
F1(x) = g(x) = x^4+x^3+x-1

og man finder

x^5+2x^3+x^2+x+1 = (x-1)*(x^4+x^3+x-1) + 3(x^3+x)

x^4+x^3+x-1 = 1/3(x+1)*(3x^3+3x) + (-x^2-1)

3x^3+3x = -x/3*(-x^2-1) + 0

hvor det som ventet afsløres at det oplyste polynomium d(x) er sfd(f,g) pånær en konstant. Udfør nu algoritmen baglæns. Man finder

U(x) = (x+1)/3
V(x) = -(2+x^2)/3

#1 Det er ikke en linearkombination idet dine u og v ikke ligger i polynomiumsringen.

#2 Korrektion
"Som nævnt kan 4 skrives "

->

"Som nævnt kan 2 skrives"

Mange tak for svarene begge to. d(x), f(x) og g(x) tilhørte faktisk Q[x], så svarene var korrekte til sidst.

#4
Jep, det glemte du at skrive, og jeg glemte at skrive, at jeg antog det.

Med hensyn til bemærkningen angående besvarelsen i #1 er det måske på plads at uddybe.

Q[x] er ringen af polynomier med rationale koefficienter. Det er ikke et brøklegeme, så de i #1 fundne rationale funktioner er ikke elementer heri. Ethvert integritetsområde R kan udvides til et brøklegeme F ved at lade F være mængden af ækvivalensklasser a/b, a,b \in R, b
eq 0, og to brøker a1/b1 og a2/b2 er ækvivalente netop hvis a1b2=a2b1. Addition og multiplikation indføres i F på den fra Q kendte måde. Brøklegemet kaldes F(x) og elementerne deri er rationale funktioner.

Aha, her ser vi det igen: foraet spiser ganske frækt \ n - hvormed menes en slash efterfulgt af n uden mellemrum. Jævnfør problemer observeret i "Test af LaTeX" trådene.

#6
Uddybning: For jeg havde skrevet a,b \in R, b \ neq 0, sidstnævnte uden mellemrum. Det resulterede i omtalte spisning og et linieskift genereret midt i det hele.