143 13 1MB
Finnish Pages 130 Year 2011
SYMBOLINEN ANALYYSI Keijo Ruohonen
2003
Sisältö 1 1 2 4 5
I SYMBOLIT JA SYNTAKSI
6 6 7 8
II SYMBOLINEN DIFFERENTIAALLASKENTA
14 14 16 17 22 24 26 29
III KOKONAISLUVUT
38 38 38 40 41 43 46
IV ALGEBRAA
1.1 Symbolit ja aakkostot 1.2 Lausekkeet ja syntaksi 1.3 Tulkinta 1.4 Yhtälöt, listat, jonot, joukot, asetelmat, vektorit, matriisit, . . .
2.1 Symbolinen derivointi 2.2 Taylorin sarja 2.3 Eräitä apufunktioita ja niiden derivaattoja
3.1 Jaollisuus, tekijät, alkuluvut 3.2 Kokonaisluvun esitys eri kannoissa 3.3 Suurin yhteinen tekijä ja pienin yhteinen jaettava 3.4 Kongruenssilaskenta eli moduläärilaskenta 3.5 Kertoma. Stirlingin approksimaatio 3.6 Binomi- ja multinomikertoimet 3.7 (Suurten) kokonaislukujen algoritmeja
4.1 Yleistä 4.2 Renkaat ja kunnati 4.3 Esimerkkejä renkaista ja kunnista 4.4 Alirenkaat ja -kunnat, laajennukset, ihanteet, tekijärenkaat, murtokunnat 4.5 Tekijät, s.y.t. ja p.y.j kokonaisalueissa 4.6 UFD, PID ja ED
47 V POLYNOMIT 47 5.1 Yhden muuttujan polynomit 49 5.2 Polynomien juuret 52 5.3 Algebralliset laajennukset 53 5.4 Rationaalifunktiot ja osamurtokehitelmä 57 5.5 Monen muuttujan polynomit ja rationaalifunktiot 58 5.6 Transsendenttiset laajennukset 59 5.7 Polynomien algoritmeja
i
ii 66 66 68 70 73
VI ESITYS JA SIEVENNYS 6.1 Kanoniset ja normaalit esitykset 6.2 Polynomien ja rationaalifunktioiden esitykset ja sievennys 6.3 Juurilausekkeiden, algebrallisten lukujen ja algebrallisten funktioiden esitys ja sievennys 6.4 Transsendenttifunktiot
75
VII SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
75 75 82 89 90
7.1 Yleistä 7.2 Rationaalifunktioiden integrointi 7.3 Irrationaalisten alkeisfunktioiden integrointi 7.4 Erikoisfunktiot 7.5 Differentiaaliyhtälöt
95 VIII SUMMAUS JA KERTOMINEN 95 8.1 Summat ja differenssit 98 8.2 Rationaalifunktioiden summaus 103 8.3 Hypergeometrinen summaus. Gosperin algoritmi 107 8.4 Tulo 110 IX LINEAARISET REKURSIOKAAVAT 110 9.1 Yleistä 111 9.2 Ensimmäisen kertaluvun lineaarinen rekursiokaava 111 9.3 Vakiokertoiminen lineaarinen rekursiokaava 112 9.3.1 Matriisiesitys 117 9.3.2 Generoiva funktio 120 9.3.3 Eksponentiaalipolynomi 121 Kirjallisuus 123 Hakemisto
Esipuhe Tämä moniste on tarkoitettu TTY:n kurssin 73265 Symbolinen analyysi 1 perusmateriaaliksi. Monisteessa käydään läpi symbolisen laskennan peruskäsitteet sekä suuri joukko algoritmeja. Esitietoina tarvitaan vain peruskurssit, vaikkakin monet muut kurssit (esimerkiksi Algebra 1, Kryptologia ja Algoritmimatematiikka) ovat toki hyödyksi. Tarvittavat lukuteorian ja algebran käsitteet ja tulokset käydään läpi. Symbolinen analyysi on suhteellisen lyhyessä ajassa kehittynyt omaksi hyvin laajaksi alueekseen matematiikan ja laskennallisen fysiikan tai yleisesti tieteellisen laskennan välimaastossa, ks. esimerkiksi E NNS & M C G UIRE tai G RABMEIER & K ALTOFEN & W EISPFENNING . Tästä syystä mikään kovin laaja tai yksityiskohtainen asian käsittely ei ole mahdollista yhden kurssin puitteissa. Tästäkin monisteesta on jätetty pois tai vain maininnalle useat tehokkaat algoritmit, jotka ovat työläitä esittää ja/tai vaativat paljon esitietoja, ja esimerkiksi symbolista lineaarialgebraa tai monen muuttujan polynomien manipulaatiossa keskeisiä Gröbnerin kantoja ei käsitellä ollenkaan.
iii Olennainen osa symbolisen analyysin kurssia on tutustuminen johonkin laajaan symbolisen laskennan ohjelmistoon (Maple, Mathematica, MuPAD, jne.). Moniste on kuitenkin kirjoitettu mahdollisimman ”ohjelmistoriippumattomaksi”. Näissä ohjelmistoissa on myös helppokäyttöinen ohjelmointikieli, jolla käsittelyn voi automatisoida. Symbolisen laskennan rajoitukset johtuvat enimmäkseen siitä, että aivan puhtaan symbolisesti esitettyinä monet tavalliset tehtävät ovat hyvin vaativia tai suorastaan algoritmisesti ratkeamattomia! Pelastuksena on tehtävien formuloiminen algebralliseen muotoon, jolloin ne tulevat helpommiksi tai yleensä ottaen ratkeaviksi. Ohjelmistot tekevät tällaisen formuloinnin usein automaattisesti. Koska puhtaan symbolisen lausekkeen ja tarkoitetun vastaavan algebrallisen muodon välillä ei ole mitään helppoa yhteyttä—tehtävähän pitäisi oikeaoppisesti formuloida alusta alkaen algebralliseen muotoon—tapahtuu tässä toisinaan virheitä, jotka käyttäjän pitäisi huomata. Ohjelmistojen käyttö ei olekaan aivan niin mutkatonta kuin käyttäjät muutaman esimerkin jälkeen usein kuvittelevat ja siinä tarvitaan tiettyä rutiinia ja varovaisuutta. Oikein käytettynä symbolinen analyysi on tavattoman vahva työkalu, jolla selvitetään monia muutoin aivan mahdottomia tehtäviä.
Keijo Ruohonen
Luku 1 SYMBOLIT JA SYNTAKSI 1.1
Symbolit ja aakkostot
Symbolinen laskenta on pohjimmiltaan tiettyjen symbolijonojen manipulaatiota annettujen sääntöjen mukaan. Käytännön syistä perussymboleja voi olla vain tietty äärellinen määrä. Ne muodostavat ns. perusaakkoston Σ = {a1 , a2 , . . . , aN }. Perussymbolien joukossa ovat ainakin englanninkielen aakkoset a,b, . . . ,z sekä numeraalit 0,1,2, . . . ,9, mutta käytännössä tietysti suuri joukko muitakin symboleja (sananväli, sulut, välimerkkejä, jne.). Aakkoston Σ symboleista voidaan muodostaa ns. sanoja1 , ts. äärellisiä symbolijonoja, jotka perinteiseen tapaan kirjoitetaan ilman erottimia: w = ai1 ai2 · · · ain . Tässä n on sanan pituus. Mukana on myös ns. tyhjä sana Λ, jonka pituus on nolla. n-pituisia sanoja on N n kpl. Symbolisen laskennan ohjelmistoissa suurin sallittu sananpituus on äärellinen, mutta niin suuri, ettei sitä käytännössä juurikaan kukaan hätyyttele. Osa sanoista käy muuttujien, vakioiden, funktioiden yms. nimiksi, mutta eivät kaikki. Esimerkiksi sulut eivät yleensä saa esiintyä nimissä, vaan niillä on oma tavanomainen käyttönsä lausekkeissa (tietyt sulut voivat kuitenkin erottaa muuttujan indeksin). Sanojen perusoperaatio on ns. katenaatio, mikä tarkoittaa ”yhdyssanojen” muodostamista: Sanojen w1 = ai1 ai2 · · · ain1 ja w2 = aj1 aj2 · · · ajn2 katenaatio on sana ai1 ai2 · · · ain1 aj1 aj2 · · · ajn2 =merk. w1 w2 . Katenointi on ilmeisesti liitännäinen operaatio, ts. aina (w1 w2 )w3 = w1 (w2 w3 ), mutta se ei ole (yleisesti) vaihdannainen. Kaikki mahdolliset perusaakkoston symboleista muodostetut sanat muodostavat katenaation suhteen algebrallisesti ns. monoidin, ts. operaatio (katenaatio) on liitännäinen ja sillä on identiteettialkio (tyhjä sana). Symbolisen laskennan ohjelmistoissa katenaatiolla on omat merkintänsä, mutta tietysti vain osalle sanoja! (Katenaation merkki on mukana perusaakkostossa.) Samoin tyhjällä sanalla on oma merkkinsä. Näitä käyttäen voidaan esimerkiksi ohjelmallisesti muodostaa uusia muuttujanimiä. 1
Sanojen teoria on sinällään hyvinkin pitkälle vietyä, ks. kurssit Automaattiteoria ja Formaaliset kielet.
1
LUKU 1. SYMBOLIT JA SYNTAKSI
1.2
2
Lausekkeet ja syntaksi
Osa perussymboleista tulkitaan kiinteiksi operaattoreiksi tai funktioiksi. Tuttuja tällaisia operaattoreita ovat esimerkiksi +, -, * (kertolasku), /, ˆ (potenssiin korotus) ja sin (sinifunktio). Operaattoreita ja funktioita voidaan ottaa lisääkin käyttöön antamalla niille nimet ja tarvittaessa määrittelemällä operaattorin toiminta. Määrittelemätöntä operaattoria tarvitaan laskettaessa symbolisesti operaattoreilla tai esimerkiksi annettaessa differentiaaliyhtälön riippuva muuttuja. Operaattori operoi aina argumentteihinsa, joita voi olla yksi tai useampia. (Tai ei yhtään, jolloin operaattori on kuten muuttuja tai vakio.) Argumenttien lukumäärä voi olla kiinteä tai vaihteleva. Argumentit merkitään yleensä järjestyksessä operaattorin perään sulkujen sisään, ns. prefiksimerkintä. Operaattoria, jolla on vain yksi argumentti, kutsutaan unääriseksi. Operaattoria, jolla on kaksi argumenttia, kutsutaan binääriseksi. +, -, *, / ja ˆ ovat binäärisiä, - on myös unäärinen. Binäärinen operaattori esiintyy usein infiksimerkintäisenä, ts. ei esimerkiksi merkitä +(a,b) vaan a + b. Lisäksi esiintyy toisinaan ns. suffiksimerkintä eli puolalainen merkintä, jossa operaattori merkitään argumenttiensa perään. Huomattakoon, että eräät operaattorit eivät hyväksy mitä tahansa argumentteja, vaan tietyllä argumenttipaikalla on aina oltava tietynlainen termi. Vakioihin, muuttujiin tms. operoivat operaattorit ovat ns. 1. kertaluvun operaattoreita. Toisaalta tietyt operaattorit operoivat 1. kertaluvun operaattoreihin, esimerkkinä vaikkapa funktioiden yhdistäminen tai derivointi. Näitä kutsutaan 2. kertaluvun operaattoreiksi. Edelleen jotkin operaattorit (ns. 3. kertaluvun operaattorit) operoivat 2. kertaluvun operaattoreihin, jne. Käytännössä ei kovin korkean kertaluvun operaattoreita juurikaan tarvita, eivätkä ohjelmistot niitä tue. Binäärinen operaattori f voi määrittää liitännäisen operaation, ts. operaattori käyttäytyy siten, että aina f(a,f(b,c)) = f(f(a,b),c), infiksimerkinnässä a f (b f c) = (a f b) f c. Monet operaattorit, varsinkin kiinteät, ajatellaan ilman muuta liitännäisiksi. Esimerkiksi edellisen pykälän katenaatio ja funktioiden yhdistäminen ovat liitännäisiä, samoin + ja *. Liitännäisille operaatioille pitkät peräkkäiset operoinnit voidaan suluttaa missä järjestyksessä tahansa. Jotta päästäisiin tähän, määritellään sulkuopillisesti oikea sulutus infiksioperaattoreille. Lauseke on oikein sulutettu, jos (i) jokaisella sulkumerkillä on lausekkeessa yksikäsitteinen vastapari, (ii) jokaisen sulkeen ja sen vastasulkeen sisällä oleva lauseke on muotoa x f y
x f (. . . )
tai
tai
(. . . ) f y
tai
(. . . ) f (. . . ),
missä f on operaattori ja x ja y eivät sisällä operaattoreita, ja (iii) itse lauseke on muotoa x
tai
x f y
tai
x f (. . . )
tai
(. . . ) f y
missä f on operaattori ja x ja y eivät sisällä operaattoreita.
tai
(. . . ) f (. . . ),
LUKU 1. SYMBOLIT JA SYNTAKSI
3
Lause 1.1. Liitännäisen operaattorin f sulkuopillisesti oikea lauseke, jossa f esiintyy n ≥ 2 kertaa eikä muita infiksioperaattoreita esiinny, voidaan aina kirjoittaa ekvivalenttiin muotoon x1 f (x2 f (x3 f( . . . (xn f xn+1 ) . . . ))). Todistus. Asia on selvä, jos n = 2. Muutoin (kohta (iii) yllä) lauseke on muotoa x f (. . . )
tai
(. . . ) f y
tai
(. . . ) f (. . . ),
missä x ja y eivät sisällä operaattoria f. Jos lauseke on muotoa x f (. . . ), jatketaan sulkujen sisällä olevasta lausekkeesta, jossa on operaattoreita yksi vähemmän. Jos taas lauseke on muotoa (. . . ) f y, voidaan olettaa että sulkujen sisällä oleva lauseke (kohta (ii)) on jo saatettu vaadittuun muotoon x1 f (x2 f (x3 f( . . . (xn−1 f xn ) . . . ))), jolloin lauseke voidaan kirjoittaa muotoon x1 f ((x2 f (x3 f( . . . (xn−1 f xn ) . . . ))) f y), mistä jatketaan. Samoin menetellään muotoa (. . . ) f (. . . ) olevan lausekkeen kanssa, ensimmäinen sulkulauseke saatetaan vaadittuun muotoon, jne. Lauseesta seuraa, että liitännäisen operaattorin tapauksessa sulutuksella ei ole väliä, kunhan se on sulkuopillisesti oikea. Niinpä kirjoitetaankin lauseke usein täysin ilman sulkuja: x1 f x2 f x3 f . . . xn f xn+1 . Ohjelmistot yleensä tukevat tätä merkintätapaa tavallisimpien liitännäisten operaattorien suhteen. Huomautus. Laskujen määrän suhteen ei ole aina ollenkaan yhdentekevää, miten lauseke lopulta sulutetaan (sehän on sulutettava laskuja varten täydellisesti). Esimerkiksi kerrottaessa monia erikokoisia matriiseja, voi laskujen määrässä olla suuria eroja sulutuksesta riippuen. Huomattakoon, että sulkusymboleja voi esiintyä erilaisina alkusulku-loppusulku-pareina. Niille yllä oleva pätee samoin perustein. Itse asiassa, koska jokaisella alkusululla on yksikäsitteinen loppusulkunsa, on yhdentekevää kuinka sulkuja merkitään, kunhan alku- ja loppusulut erotetaan toisistaan merkinnällisesti. Erikoisia sulkupareja käytetään usein matematiikassa myös operaattorien merkintään, esimerkkinä tuttu määräämätön integraali, jota merkitään al kusululla ja loppusululla dx. (Tätä käytäntöä näkee vähemmän symbolisen laskennan ohjelmistoissa.) Samoin sulkupareja käytetään rajoittimina, erityisesti ohjelmistoissa, esimerkiksi joukon määrittelyssä: {a, b, c}. ”Parittomien sulkujen” käyttö on tavallista matematiikassa (esimerkkinä itseisarvo |a| tai normi a), mutta sitä vältetään ohjelmistoissa (miksi muuten?). Sulkuja käyttäen ohjelmisto jäsentää lausekkeen, joko automaattisesti tai vasta pyydettäessä. Huomattakoon, että sulkuja jätetään pois lausekkeista sopimalla operaatioille suoritusjärjestys. Esimerkiksi * ja / sovitaan suoritettaviksi aina ennen operaatiota + ja -, mikä mahdollistaa esimerkiksi lausekkeen (x * y) + (z * (u / v)) kirjoittamisen suluttomaan muotoon x * y + z * u / v. Ohjelmistot tukevat tavallisimpia tällaisia suoritusjärjestyksiä. Huomattakoon myös, että useimmiten * ja / ajatellaan samanarvoisiksi ja yhteisliitännäisiksi, ts. esimerkiksi a * b / c * d / e = a * b * c−1 * d * e−1 . Binäärinen operaattori f on vaihdannainen, jos aina
LUKU 1. SYMBOLIT JA SYNTAKSI
4
a f b = b f a. Monet operaattorit, varsinkin kiinteät, ajatellaan vaihdannaisiksi, esimerkkeinä * ja +. Toisaalta esimerkiksi / ei ole vaihdannainen eikä myöskään ˆ, funktioiden yhdistäminen tai katenaatio. Ohjelmistot tunnistavat tavallisimmat vaihdannaiset operaattorit. Symbolisessa laskussa lausekkeiden koko kasvaa usein valtavaksi, niin isoksi, että niiden kirjoittaminen tai kopiointi on käytännössä mahdotonta. Tästä syystä ohjelmistoissa nimetään lausekkeita muuttujanimillä, joilla niihin voidaan sitten myöhemmin viitata. Huomattakoon, että tällaisen nimeämisen liittäminen varsinaiseen syntaksiin johtaa tiettyihin vaikeuksiin. Näin nimeäminen onkin ajateltava metaoperaatioksi, ts. käyttäjän kannalta, ei ohjelmiston. Myös operaattoreita ja funktioita voidaan nimetä.
1.3
Tulkinta
Ohjelmisto ei voi koskaan täysin tulkita lauseketta, ts. tajuta täydellisesti sen yhteyttä käyttötilanteeseen, vaan tämä jää käyttäjälle. Toisaalta aivan puhtaan symbolinen merkkipeli johtaa varsin työlääseen käyttöön, mikäli joitain tulkinnan osia ei ole valmiina tai kutsuttavissa. Esimerkiksi numeraalit 0,1,2, . . . ,9 liitetään melko automaattisesti lukuihin, kun se on paikallaan, ja lasketaan niillä sen mukaisesti. On kuitenkin huomattava, että valmiit tulkinnan osat voivat olla melko pinnallisia, ts. ohjelmisto ei tunne syvällisempiä ominaisuuksia. Erikoistarkoituksiin tehdyt paketit sen sijaan voivat tuntea alansa ominaisuuksia tarkemminkin. Valmiiksi mukaan otetut tulkinnan osat liittyvät tavallisimmin • kokonaislukuihin (lukuteoria), • reaali- ja kompleksilukujen aritmetiikkaan (numeerinen laskenta), • algebraan (polynomit, kunnat, lineaarialgebra, jne.), • analyysiin (differentiaali- ja integraalilaskenta, differentiaaliyhtälöt, integraalimuunnokset, jne.), • summauslaskentaan (summat, differenssit, differenssiyhtälöt, jne.), • logiikkaan tai • joukko-oppiin. Nämä alat eivät ole kuitenkaan erillisiä, vaan laskennan kuluessa tarvitaan usean alueen tulkintoja, joskus kaikkiakin. Erityisen tavallista on laskea ensin symbolisesti ja, kun on saatu sille otollinen muoto, sitten numeerisesti. Näiden (ja muiden) eri tulkinta-alojen yhteispeli antaa symboliselle analyysille sen tavattoman voiman, mutta tekee sen algoritmien kehittämisen ja käyttämisenkin sangen vaativaksi. Todettakoon, että itse asiassa tulkinta johonkin rajaan asti on teoreettisestikin välttämätöntä laskujen etenemiseksi. Puhtaasti symbolisena ilman tulkintoja annettu tehtävä voi nimittäin olla jopa algoritmisesti ratkeamaton tai laskennallisesti hyvin vaativa, ks. Pykälä 6.1. Monesti ohjelmisto tekee automaattisesti tällaisen tulkinnan, eikä voi edetä ollenkaan, ellei se sitä voi tehdä. Esimerkiksi sopivasti algebrallisesti tulkittu symbolinen alkeisfunktioiden integrointi on algoritmisesti ratkeava tehtävä, mutta puhtaasti symbolinen ei sitä ole, ks. Pykälä 7.1. Jatkossa käsitellään pääasiassa eri tulkinta-alojen piirteitä nimenomaan symbolisen laskennan näkökannalta. Numeerisen laskennan osuus jää vähäiseksi (sille on oma kurssinsa Numeerinen analyysi 1). Algebraa käsitellään sen sijaan enemmänkin, kurssi Algebra 1 on avuksi,
LUKU 1. SYMBOLIT JA SYNTAKSI
5
muttei välttämätön. Lukuteorian, logiikan ja joukko-opin taustatietona kurssi Algoritmimatematiikka on hyödyksi, muttei sekään välttämätön. Keskeisessä asemassa on polynomialgebra, sillä hyvin monet symboliset operaatiot pohjautuvat siihen, esimerkiksi lausekkeessa 3 / 4 * sqrt(2) * sin(x) - y ˆ 3 / 4 * (1 - sin(x) ˆ 2) esiintyvä sin(x) voidaan tulkita yhdeksi muuttujaksi, jolloin kyseessä on sen ja y:n polynomi. Symbolista lineaarialgebraa ei tässä käsitellä.
1.4
Yhtälöt, listat, jonot, joukot, asetelmat, vektorit, matriisit, . . .
Erilaisilla erottimilla lausekkeista voidaan muodostaa uusia käsitteitä, joista monet ovat matematiikasta tuttuja. Kirjoittamalla kahden lausekkeen väliin yhtäläisyysmerkki = saadaan yhtälö, esimerkiksi tan(x) = x. Ohjelmistot tuntevat yhtälön käsitteen ja käsittelevät sitä oikein. (Tavallisinta on tietysti yrittää ratkaista yhtälö numeerisesti tai symbolisesti, mutta yhtälöjä voidaan käsitellä muullakin tavoin.) Lausekkeista voidaan muodostaa erotinta käyttäen jono. Tavallisin erotin on pilkku ,, esimerkiksi 1 - x ˆ 2 , 3 - x , x ˆ 4 , 0 , 0 on viiden polynomin jono. Ohjelmistoissa on yleensä käsky, jolla jonoja voidaan muodostaa ohjelmallisesti. Jonoja tarvitaan mm. operaattorien argumentteina, tiedostorakenteina, yms. Jonojen perusoperaatio on katenaatio, jonka merkkinä on erotin. Tämä operaatio on selvästi liitännäinen, identiteettinä on tyhjä jono. Näin jonotkin muodostavat algebralliselta rakenteeltaan monoidin. Lista on yhdeksi lausekkeeksi merkitty jono. Matemaattisesti lista on järjestetty jono. Ohjelmistoissa on operaattori, joka ottaa listasta sen ”sisällä” olevan jonon eli litistää listan. Joukko taas on matemaattinen joukko, ts. järjestämätön jono, joka ei sisällä samaa termiä monta kertaa. Joukkoihin voidaan soveltaa tavallisia joukko-opin operaatioita: yhdiste, leikkaus ja erotus. Asetelma eli taulu muodostuu taulukon muotoon kirjoitetuista lausekkeista. Tavallisesti tällainen taulukko tulkitaan matemaattiseksi vektoriksi tai matriisiksi. Todettakoon, että jonorakenne on eräänlainen liitännäisen operoinnin prototyyppi, josta helposti saadaan muita. Koska summa (merkkinä +) on liitännäinen, on summarakenne hyvin samantapainen kuin jonorakenne. Toisaalta siihen liittyvät summalle ominaiset tulkinnalliset piirteet, jotka ohjelmistot tunnistavat, ts. summa ”summataan”. Samoin tulorakenne on hyvin samantapainen kuin jonorakenne, mutta siinäkin tulkinta tuo muita piirteitä. Tyhjä summa on nolla ja tyhjä tulo on ykkönen. Myös yhtälöitä, jonoja, listoja ja asetelmia voidaan nimetä. Niiden osiin viitataan tavalliseen tapaan indekseillä.
Luku 2 SYMBOLINEN DIFFERENTIAALILASKENTA 2.1
Symbolinen derivointi
Symbolisista operaatioista periaatteessa yksinkertaisin on derivointi. Tämä johtuu siitä, että peruskursseilla opitut derivointisäännöt ovat selvästi symbolisia: perusoperaatioille saadaan symboliset derivointisäännöt ja toisaalta alkeisfunktioiden derivointi tuottaa toisia alkeisfunktioita. Näin onkin vain tarpeen jäsentää lauseke ja käyttää derivointisääntöjä ja tunnettuja alkeisfunktioiden derivaattoja. Derivaatan raja-arvomäärittelyä ei siten tarvita lainkaan! Sama koske osittaisderivointia. Seuraavassa kertauksen vuoksi derivointisäännöt: D(f (x) ± g(x)) = Df (x) ± Dg(x) D(f (x)g(x)) = g(x)Df (x) + f (x)Dg(x) 1 D(f (x)/g(x)) = (g(x)Df (x) − f (x)Dg(x)) g(x)2 g(x) g(x) g(x) D(f (x) ) = f (x) Df (x) + (ln f (x))Dg(x) f (x) k D(f (g1 (x), . . . , gk (x)) = Di f (g1 (x), . . . , gk (x))Dgi (x) i=1
Df −1 (x) =
1 Df (f −1 (x))
Tässä Di tarkoittaa osittaisderivointia i:nnen muuttujapaikan suhteen. Ohjelmistot osaavat nämä säännöt, myös määräämättömille funktioille. Korkeamman kertaluvun derivaatat saadaan toistamalla derivointia. Lausekkeissa saa myös esiintyä derivoituja määräämättömiä funktioita. Edelleen derivoitavissa lausekkeissa saa esiintyä integraaleja ja näidenkin derivointi on symbolista peruskursseilta tutun kaavan mukaan: b(x) b(x) D f (x, y)dy = D1 f (x, y)dy + f (x, b(x))Db(x) − f (x, a(x))Da(x). a(x)
a(x)
Pulmallisinta symbolisessa derivoinnissa on se, että lopputuloksena saatavat lausekkeet ovat usein hyvin isoja, vaikka ne itse asiassa sieventyisivät huomattavasti pienemmiksi. Näin ni6
LUKU 2. SYMBOLINEN DIFFERENTIAALILASKENTA
7
menomaan sievennyksellä on tärkeä rooli symbolisessa derivoinnissa. Sievennykseen palataan myöhemmin Luvussa 6. Huomautus. Koska derivointi on näin ”symbolinen” operaatio, voidaan funktion laskevasta ohjelmakoodista usein helposti muokata sen derivaatan laskeva koodi. Tätä kutsutaan automaattiseksi derivoinniksi, käyttäjän ei tarvitse sitä tehdä tai edes tietää, että derivointi tehtiin. (Ks. esimerkiksi R ALL .) Vektorilaskennan ”nablauskaavat” ovat kutakuinkin kaikki symbolisia identiteettejä, joten ne olisivat periaatteessa käytettävissä. Nablausta ei kuitenkaan ole yleisesti ohjelmistoissa, johtuen siitä, että kaavojen käyttö ei enää olekaan suoraviivaista vaan vaatii tietyt strategiat ja näitä ei ole saatu mekanisoiduksi tyydyttävästi. Koska nablauskaavat ovat symbolisia, niitä vastaava tulos saadaan toisinaan aikaan derivoinnilla ja sopivalla sievennyksellä.
2.2
Taylorin sarja
Funktion f (x) Taylorin sarja pisteessä x = a saadaan tutulla kaavalla 1 1 Df (a)(x − a) + D2 f (a)(x − a)2 1! 2! 1 3 1 + D f (a)(x − a)3 + · · · + Dn f (a)(x − a)n + · · · 3! n!
f (x) = f (a) +
Koska derivaatat pisteessä x = a ovat symbolisesti laskettavissa, saadaan sarjasta lasketuksi symbolisesti periaatteessa miten tahansa suuri määrä termejä. Ohjelmistot eivät kuitenkaan yleensä pysty laskemaan yleistä termiä, vaan antavat tuloksen n:nnen asteen Taylorin kehitelmänä eli muodossa Taylorin polynomi + virhetermi eli 1 1 Df (a)(x − a) + D2 f (a)(x − a)2 1! 2! 1 3 1 + D f (a)(x − a)3 + · · · + Dn f (a)(x − a)n + O((x − a)n+1 ). 3! n!
f (x) = f (a) +
Tässä virhetermi O((x − a)n+1 ) tarkoittaa kollektiivisesti sellaista ”korjaustermiä” θn (x), että |θn (x)| ≤ C|x − a|n+1 jollain välillä |x − a| ≤ R, missä C on vakio (ns. O-notaatio). Samoin saadaan symbolisesti lasketuksi monen muuttujan funktion Taylorin sarjan termejä. Huomattakoon, että myös määräämättömien funktioiden Taylorin sarjat ovat käytettävissä ja että lausekkeissa saa esiintyä myös integraaleja. On muitakin tapoja saada symbolisesti Taylorin kehitelmiä. Jos esimerkiksi funktio y = y(x) määritellään yhtälöllä g(x)f (y) = h(x), missä f (y):n, g(x):n ja h(x):n Taylorin kehitelmät (pisteissä y = b ja x = a, joille g(a)f (b) = h(a)) tunnetaan, saadaan y(x):n Taylorin kehitelmä pisteessä x = a y(x) = c0 + c1 (x − a) + · · · + cm (x − a)m + O((x − a)m+1 ) lasketuksi iteroiden peräkkäisten approksimaatioiden menetelmällä: Peräkkäisten approksimaatioiden menetelmä: 1. Asetetaan r ← 0 ja y0 ← b.
LUKU 2. SYMBOLINEN DIFFERENTIAALILASKENTA
8
2. Lasketaan g(x):n ja h(x):n Taylorin polynomit P (x) ja Q(x) pisteessä x = a sekä f (y):n Taylorin polynomi R(y) pisteessä y = b. (Polynomien asteen pitää olla riittävän korkea.) 3. Ratkaistaan yhtälöstä P (x)R(yr ) = Q(x) kerroin cr (unohtaen (x − a)r :ää korkeammat x − a:n potenssit). 4. Jos tarvitaan vielä korkeampiasteisia termejä, asetetaan r ← r + 1 sekä
yr ← yr−1 + cr (x − a)r
ja mennään kohtaan 2. Muuten tulostetaan yr ja lopetetaan. Peräkkäisten approksimaatioiden menetelmällä saadaan esimerkiksi lasketuksi funktioiden h(x) ja g(x) osamäärän h(x)/g(x) sekä neliöjuuren f (x) jms. Taylorin kehitelmät, kunhan tunnetaan lähtöfunktioiden kehitelmät. Edellinen saadaan käyttäen yhtälöä g(x)y = h(x) ja jälkimmäinen yhtälöllä y 2 = f (x). On huomattava, ettei menetelmä säilytä aina alkuperäisten Taylorin kehitelmien ”tarkkuutta”. Esimerkiksi ns. sinc-funktion eli kardinaalisinin1 sinc x =
sin x x
2. asteen Taylorin kehitelmää origossa ei saa 2. asteen kehitelmistä sin x = x + O(x3 ) ja
x = x + O(x3 ).
Kuten peruskursseilla on opittu, määräämättömiä raja-arvoja voidaan useinkin laskea Taylorin sarjoja käyttäen, ottaen mukaan sopiva määrä termejä. Näin tämäkin operaatio voidaan suorittaa symbolisesti. Mutkikkaammat raja-arvot vaativat muunkinlaisia sarjakehitelmiä.
2.3
Eräitä apufunktioita ja niiden derivaattoja
(Diracin) deltafunktiota δ(x) käytetään symbolisesti laskettaessa seuraavassa formaalisessa merkinnässä:
b f (c), jos c on integrointivälillä f (x)δ(x − c)dx = 0 muuten. a
Tässä oletetaan, että a ≤ b. Integrointiväli voi olla myös ääretön. Merkinnän etu on se, että integraalin sisään saadaan ”tavaraa”, joka ei sinne normaalisti kuulu. Näin käsittely ja notaatio yksinkertaistuu ja yhtenäistyy. Jotta deltafunktiomerkintä olisi käyttökelpoinen, sovitaan vielä, että b b b (1) (f (x)δ(x − c) + g(x))dx = f (x)δ(x − c)dx + g(x)dx (yhteenlasku), a
b (2) a
a
1
a f (x)δ(x − c)dx = −
a
(translaatio),
a−d
b (3)
a
b−d f (x)δ(x − c)dx = f (y + d)δ(y + d − c)dy
f (x)δ(x − c)dx
(a = b, rajojen vaihto).
b
Nimi lienee englanninkielen sanaleikki, vrt. ”cardinal sin”, peräisin J.M. Whittakerin klassikosta Interpolatory Function Theory. Cambridge University Press (1935).
LUKU 2. SYMBOLINEN DIFFERENTIAALILASKENTA
9
Huomautus. On melko ilmeistä, ettei mikään ”tavallinen” funktio voi käydä yo. deltafunktioksi. Deltafunktio onkin usein vain merkinnällinen apuväline. Matemaattisesti toki voidaan upottaa ”tavalliset” funktiot laajempaan luokkaan, ns. yleistettyihin funktioihin, joihin myös deltafunktio kuuluu. Symbolisesti laskettaessa kumpikin ”tulkinta” on mahdollinen. Funktio g(x) on funktion f (x) ns. heikko derivaatta, jos voidaan kirjoittaa x f (x) = f (a) +
g(y)dy a
jollekin vakiolle a (voi olla −∞). Huomaa, ettei heikko derivaatta ole yksikäsitteinen. Vaikkakin yo. deltafunktiomerkintä on vain merkintä, voidaan sen avulla saada (heikot) symboliset derivaatat monille funktioille. Esimerkiksi x
x 1 · δ(y)dy =
δ(y)dy = −∞
−∞
0, jos x < 0 1, jos x ≥ 0
= H(x),
joten deltafunktio on ns. Heavisiden funktion H(x) symbolinen derivaatta. Samoin D(H(x − c)) = δ(x − c). Tästä syystä voidaan merkitä δ(x − c) = 0 ,
kun x = c,
sillä H(x−c) on vakio, kun x < c tai x > c. Edelleen on mukavaa sopia, että deltafunktio on parillinen funktio, ts. δ(−x) = δ(x), kun x = 0. Vielä, koska suoraan deltafunktion määritelmän mukaan b b f (x)δ(x − c)dx = f (c)δ(x − c)dx, a
a
on tapana kirjoittaa f (x)δ(x − c) = f (c)δ(x − c). Deltafunktioon voidaan soveltaa myös osittaisintegrointia: Lause 2.1. Jos f (x):llä on derivaatta, niin b f (x)δ(x − c)dx = a
b
b f (x)H(x − c) −
a
H(x − c)Df (x)dx
(osittaisintegrointi),
a
kun c = min(a, b). Todistus. Rajoitutaan tapaukseen, missä a < b ja c = 0 (muut menevät samoin). Saadaan kolme alatapausta: • 0 on integrointivälillä. Silloin a < 0 ja b oikea puoli = f (b) −
Df (x)dx = f (0) = vasen puoli. 0
LUKU 2. SYMBOLINEN DIFFERENTIAALILASKENTA
10
• a on positiivinen. Silloin b oikea puoli =
f (x) −
a
b f (x) = 0 = vasen puoli. a
• b on negatiivinen. Silloin b oikea puoli =
b 0−
a
0 dx = 0 = vasen puoli. a
Seuraus. Tulolle f (x)H(x − c) pätee tulon derivointisääntö. Todistus. Lauseen 2.1 nojalla (valitaan b = x) x (f (y)δ(y − c) + H(y − c)Df (y))dy.
f (x)H(x − c) = f (a)H(a − c) + a
Osittaisintegroimalla symbolisesti toisin päin kuin Lauseessa 2.1 (ja olettaen, että a < b) todetaan, että f (c), jos a < c < b 0, jos c < a tai c > b
b f (x)δ(x − c)dx
= a
b =
b F (x)δ(x − c) −
a
F (x)D(δ(x − c))dx a
b F (x)D(δ(x − c))dx,
=− a
missä F (x) on f (x):n integraalifunktio. Näin symbolisesti saadaan deltafunktion derivaatta D(δ(x − c)). Eli derivaatta valitaan siten, että tulon derivointisääntö pätee tulolle f (x)δ(x − c) (vrt. yo. Seuraus). Yleisesti n-kertaisella osittaisintegroinnilla voidaan perustella deltafunktion n:nnen kertaluvun derivaatan seuraava määritelmä:
b (−1)n Dn f (c), jos c on integrointivälillä f (x)Dn (δ(x − c))dx = 0 muuten. a
Huomaa myös, että on ”järkevää” merkitä Dn (δ(x − c)) = 0 ,
jos x = c.
Likeistä sukua Heavisiden funktiolle on signumfunktio 1, jos x > 0 0, jos x = 0 = H(x) − H(−x). sgn(x) = −1, jos x < 0
LUKU 2. SYMBOLINEN DIFFERENTIAALILASKENTA
11
Näin ollen (symbolisesti) D sgn(x) = DH(x) − DH(−x)(−1) = 2δ(x). Huomaa myös, että signumfunktio sgn(x) on itseisarvon |x| heikko derivaatta. Eräänlaiset yleistykset signumfunktiolle ovat katto ja pohja. Reaaliluvun x katto, merkitään x, on pienin kokonaisluku, joka on ≥ x. Vastaavasti luvun x pohja, merkitään2 x , on suurin kokonaisluku, joka on ≤ x. Seuraavassa kuvaajat ja varsin ilmeisiä katon ja pohjan ominaisuuksia:
katto 3
pohja 2 1 x –4
–3
–2
–1
1
2
3
–1 –2 –3
(1) x = x ⇔ x on kokonaisluku ⇔ x = x
1, jos x ei ole kokonaisluku (2) x − x = 0, jos x on kokonaisluku (3) x − 1 < x ≤ x ≤ x < x + 1 (4) −x = −x ja −x = − x
Edelleen, jos k on kokonaisluku, niin saadaan seuraavat ominaisuudet: (5) x = k ⇔ k ≤ x < k + 1 ⇔ x − 1 < k ≤ x (6) x = k ⇔ k − 1 < x ≤ k ⇔ x ≤ k < x + 1 (7) x + k = x + k ja x + k = x + k (8) x < k ⇔ x < k (9) k < x ⇔ k < x 2
Vanha, vieläkin usein käytössä oleva merkintä on [x].
4
LUKU 2. SYMBOLINEN DIFFERENTIAALILASKENTA
12
(10) x ≤ k ⇔ x ≤ k (11) k ≤ x ⇔ k ≤ x
Mitään varsinaisia perustuloksia ei katolle ja pohjalle ole, sievennykseen on kuitenkin toisinaan käytettävissä Lause 2.2. (McEliecen lemma) Jos f (x) on jatkuva ja aidosti kasvava ja jos x on kokonaisluku aina kun f (x) on kokonaisluku, niin f (x) = f ( x )
ja
f (x) = f (x).
Todistus. Näytetään kaava f (x) = f (x). Pohjia koskevan kaavan todistus on kutakuinkin samanlainen (jätetään lukijalle). Jos x = x, niin asia on selvä. Näin ollen voidaan siirtyä tapaukseen x < x. Tällöin f (x) < f (x), sillä f on aidosti kasvava, ja edelleen f (x) ≤ f (x). Asetetaan vastaoletus: f (x) < f (x). Silloin f (x) ≤ f (x) < f (x). Koska f on jatkuva, niin on sellainen luku y väliltä x ≤ y < x, että f (y) = f (x). Mutta tällöin y on kokonaisluku lauseessa mainitun ehdon takia, mikä on ristiriita. Lauseesta saadaan erikoistapauksina mm. kaavat √ x = x
ja (valitaan f (x) = logaritmia, niin
√
√ x = x
x). Edelleen, jos m ≥ 2 on kokonaisluku ja logm merkitsee m-kantaista logm x = logm x
ja
logm x = logm x
(valitaan f (x) = logm x). Vielä, jos k ja n > 0 ovat kokonaislukuja, niin ! ! " # " # x+k x + k x+k x + k = ja = n n n n x+k (valitaan f (x) = ). n Kattoa ja pohjaa käyttäen saadaan ilmaistuksi reaalilukuväleillä olevien kokonaislukujen lukumäärät: Lause 2.3. (i) Välillä [a, b] on b − a + 1 kokonaislukua (a ≤ b). (ii) Välillä [a, b) on b − a kokonaislukua (a ≤ b). (iii) Välillä (a, b] on b − a kokonaislukua (a ≤ b). (iv) Välillä (a, b) on b − a − 1 kokonaislukua (a < b). Todistus. (i) k on välillä [a, b] oleva kokonaisluku tarkalleen silloin, kun a ≤ k ≤ b . (ii) k on välillä [a, b) oleva kokonaisluku tarkalleen silloin, kun a ≤ k < b. (iii) k on välillä (a, b] oleva kokonaisluku tarkalleen silloin, kun a < k ≤ b . (iv) k on välillä (a, b) oleva kokonaisluku tarkalleen silloin, kun a < k < b.
LUKU 2. SYMBOLINEN DIFFERENTIAALILASKENTA
13
Katto ja pohja liittyvät likeisesti Heavisiden funktiosarjoihin, sillä ilmeisesti x =
∞
H(x − n) +
n=0
(H(x − n) − 1)
−∞
n=1
(ja x = − −x ). Siispä symbolisesti D x = Dx =
∞
δ(x − n),
n=−∞
ns. 1-jaksoinen deltafunktio eli deltafunktiokampa (tunnetaan myös ideaalisen näytteenottofunktion nimellä). Kyseessä on erikoistapaus ns. deltafunktiosarjasta, jollaisen yleinen muoto on ∞ an δ(x − n). n=−∞
Luku 3 KOKONAISLUVUT 3.1
Jaollisuus, tekijät, alkuluvut
Symbolisen laskennan tavallisin valmistulkinta on numeraalijonojen tulkinta kokonaisluvuiksi. Näin ollen tietyt lukuteorian1 käsitteet ja tulokset tulevat hyvin usein esille laskettaessa symbolisesti, vaikka lasku sinänsä ei liitykään lukuteoriaan. Kaikkien kokonaislukujen joukkoa merkitään Z:lla. Ei-negatiivisten kokonaislukujen eli ns. luonnollisten lukujen joukkoa {0, 1, 2, . . . } merkitään N:llä. Kokonaislukujen yhteen- ja kertolasku ovat tuttuja vaihdannaisia ja liitännäisiä operaatioita, joiden identiteettialkiot ovat 0 ja 1. Muista myös liitäntälaki x(y +z) = xy +xz sekä vastaluvun ja vähennyslaskun määrittelyt: −x = (−1)x ja x − y = x + (−1)y. Kokonaislukujen jakolasku tarkoittaa seuraavanlaista operaatiota: Jaettaessa kokonaisluku x (jaettava) kokonaisluvulla y = 0 (jakaja) x saatetaan muotoon x = qy + r, missä kokonaisluku r on jakojäännös, joka toteuttaa ehdon 0 ≤ r < |y|. Kokonaisluku q on osamäärä. Lisäämällä x:ään toistuvasti −y:tä tai y:tä nähdään, että x on mahdollista kirjoittaa ko. muotoon. Jos voidaan kirjoittaa x = qy, missä q on kokonaisluku, sanotaan, että x on jaollinen y:llä tai että y jakaa x:n tai että y on x:n tekijä, merkitään y | x. Kokonaisluvun x ns. triviaalit tekijät ovat ±1 ja ±x. Mahdolliset muut tekijät ovat ei-triviaaleja. Seuraavat jakolaskun ja jaollisuuden ominaisuudet ovat melko ilmeisiä: (1) 0 on jaollinen millä tahansa kokonaisluvulla, mutta jakaa vain itsensä. (2) ±1 jakaa kaikki kokonaisluvut, mutta on jaollinen vain itsellään. (3) Jos y | x ja x = 0, niin |y| ≤ |x|. (4) Jos x | y ja y | z, niin myös x | z. (5) Jos x | y ja x | z, niin myös x | y ± z. (6) Jos x | y ja z on kokonaisluku, niin x | yz. 1
Lukuteoria on nimenomaan kokonaislukujen teoriaa.
14
LUKU 3. KOKONAISLUVUT
15
(7) Jakolaskun tulos on yksikäsitteinen. Jos nimittäin x = q 1 y + r 1 = q2 y + r 2 , missä q1 , q2 , r1 , r2 ovat kokonaislukuja ja 0 ≤ r1 , r2 < y, niin y jakaa r1 − r2 :n. Koska |r1 − r2 | < |y|, tästä seuraa että r1 = r2 ja edelleen että q1 = q2 . Kokonaislukua, jolla on vain triviaalit tekijät, kutsutaan jaottomaksi. Jaoton kokonaisluku on alkuluku, jos se on ≥ 2. Ensimmäiset alkuluvut ovat 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, . . . 2 on ainoa parillinen alkuluku. Eräs symbolisen laskennan perustehtävä on testata onko luonnollinen luku alkuluku vai ei. Alkulukujen joukkoa merkitään toisinaan P:llä. Kokonaisluku, joka on ≥ 2 eikä ole alkuluku, on yhdistetty luku. Lause 3.1. Jos kokonaisluku x on itseisarvoltaan ≥ 2, niin sillä on alkulukutekijä eli ns. alkutekijä. Todistus. Jos |x| ≥ 2, alkutekijä p löytyy seuraavalla algoritmilla: 1. Asetetaan z ← x. 2. Jos z on jaoton, tulostetaan p = |z| ja lopetetaan. 3. Jos z ei ole jaoton, etsitään ei-triviaali tekijä u. Asetetaan z ← u ja mennään kohtaan 2. Menettely pysähtyy, sillä kohdan 3. kautta mentäessä aina |z| pienenee ja on lopulta alkuluku, jolloin tullaan ulos kohdasta 2. Seuraus. Alkulukuja on äärettömän monta. Todistus. Äärettömän pitkä jono alkulukuja voidaan saada aikaan seuraavalla jo muinaisten kreikkalaisten tuntemalla menettelyllä (joka ei tietenkään tuota kaikkia alkulukuja): 1. Asetetaan P ← 2. 2. Jos P = p1 , . . . , pn , niin lasketaan x = p1 · · · pn + 1. Huomaa, ettei mikään jonon P alkuluvuista jaa x:ää (jakolaskun yksikäsitteisyys). 3. Lauseen 3.1 mukaisesti x:llä on alkutekijä p, joka ei siis kuitenkaan ole mikään jonon P alkuluvuista. Etsitään jokin p, asetetaan P ← P, p ja palataan kohtaan 2.
Symbolisen laskennan alkulukuihin liittyviä perustehtäviä ovat mm. seuraavat: (1) Laske (suuruusjärjestyksessä) n:s alkuluku. (2) Laske (suuruusjärjestyksessä) n ensimmäistä alkulukua. (3) Laske suurin (vast. pienin) alkuluku, joka on ≤ x (vast. ≥ x). (4) Laske alkuluvut, jotka ovat ≤ x. Jos merkitään π(x):llä niiden alkulukujen lukumäärää, jotka ovat ≤ x, niin saadaan asymptoottinen arvio
LUKU 3. KOKONAISLUVUT Lause 3.2. (Alkulukulause)2 lim
x→∞
16 π(x) =1 x/ ln x
Lause 3.3. Kokonaisluku x = 0 voidaan etumerkkiä vaille kirjoittaa alkulukujen tuloksi, ns. tekijöihinjako. Todistus. Seuraava menettely tuottaa jonon alkulukuja, joiden tulo on = ±x: 1. Asetetaan T ← NULL (tyhjä jono). 2. Jos x = ±1, tulostetaan T ja lopetetaan. (Muista, että tyhjä tulo on = 1.) 3. Etsitään jokin x:n alkutekijä p (Lause 3.1), jolloin x = py. Asetetaan T ← T , p sekä x ← y ja mennään kohtaan 2. Menettely pysähtyy, koska aina kohdan 3. kautta mentäessä |x| pienenee ja on lopulta = 1, jolloin tullaan ulos kohdasta 2. Myöhemmin todetaan vielä, että ko. tekijöihinjako on (tekijöiden järjestystä lukuunottamatta) yksikäsitteinen (ks. Pykälä 3.3). Luonnollisesti eräs symbolisen analyysin perustehtäviä on kokonaisluvun tekijöihinjaon etsiminen. Laskennallisesti tämä on varsin vaativa tehtävä.
3.2
Kokonaisluvun esitys eri kannoissa
Tavallisin tapa esittää kokonaisluku on käyttää tuttua desimaaliesitystä eli 10-kantaista esitystä. Myös 2-kantainen eli binääriesitys on usein esillä, samoin 8-kantainen oktaaliesitys tai 16-kantainen heksadesimaaliesitys. Yleisen kannan esityksen antaa Lause 3.4. Jos k ≥ 2, niin jokainen positiivinen kokonaisluku x voidaan esittää yksikäsitteisesti muodossa x = an k n + an−1 k n−1 + · · · + a1 k + a0 , missä 0 ≤ a0 , a1 , . . . , an ≤ k − 1 ja an > 0. (Kyseessä on x:n k-kantainen esitys, n + 1 on esityksen pituus.) Todistus. Esityksen eli jonon an , an−1 , . . . , a0 antaa seuraava algoritmi: 1. Asetetaan K ← NULL (tyhjä jono). 2. Jaetaan x kantaluvulla k: x = qk + r (osamäärä q, jakojäännös r). Asetetaan K ← r, K ja x ← q. 3. Jos x = 0, tulostetaan K ja lopetetaan. Muussa tapauksessa mennään kohtaan 2. Koska kohdassa 2. aina x pienenee, menettely pysähtyy lopulta kohtaan 3. k-kantainen esitys on yksikäsitteinen. Jos nimittäin x = an k n + an−1 k n−1 + · · · + a1 k + a0 = bm k m + bm−1 k m−1 + · · · + b1 k + b0 , missä 0 ≤ a0 , a1 , . . . , an , b0 , b1 , . . . , bm ≤ k − 1 ja an , bm > 0 ja n ≥ m, niin ensinnäkin voidaan päätellä, että n = m (eli että esityksen pituus on yksikäsitteinen). Jos olisi n > m, niin olisi myös 2
Tämän todistus on varsin hankala!
LUKU 3. KOKONAISLUVUT
17
bm k m + bm−1 k m−1 + · · · + b1 k + b0 ≤ (k − 1)k m + (k − 1)k m−1 + · · · + (k − 1)k + k − 1 = k m+1 − 1 < k m+1 ≤ k n ≤ an k n + an−1 k n−1 + · · · + a1 k + a0 , mikä on ristiriita. Siispä n = m. Samalla tavoin voidaan todeta, että an = bn . Jos nimittäin vaikkapa an > bn , niin bn k n + bn−1 k n−1 + · · · + b1 k + b0 ≤ (an − 1)k n + (k − 1)k n−1 + · · · + (k − 1)k + k − 1 = an k n − 1 < an k n + an−1 k n−1 + · · · + a1 k + a0 , mikä on taas ristiriita. Edelleen voidaan samalla tavoin näyttää, että an−1 = bn−1 , jne. Eo. todistuksen menettely antaa nollan esitykseksi tyhjän jonon, yleensä kuitenkin sovitaan, että ko. esitys on 0. Esitys on usein tapana kirjoittaa sanaksi eikä jonoksi, ts. erotinta (pilkkua) ei käytetä. Konversio eri kantaesitysten välillä (ns. kantamuunnos eli radix-muunnos) on tietysti symbolisen analyysin perustehtäviä. Lause 3.5. Positiivisen kokonaisluvun x k-kantaisen esityksen pituus on logk x + 1 = logk (x + 1), missä logk on k-kantainen logaritmi3 . Todistus. Jos x:n k-kantainen esitys on x = an k n + an−1 k n−1 + · · · + a1 k + a0 , niin pituus on s = n + 1. Ilmeisesti x ≥ k n ja toisaalta x ≤ (k − 1)k n + (k − 1)k n−1 + · · · + (k − 1)k + k − 1 = k n+1 − 1 < k n+1 . Koska siis k s−1 ≤ x < k s , niin s − 1 ≤ logk x < s eli s = logk x + 1. Toisaalta myös k s−1 < x + 1 ≤ k s , joten s − 1 < logk (x + 1) ≤ s eli s = logk (x + 1).
3.3
Suurin yhteinen tekijä ja pienin yhteinen jaettava
Kokonaislukujen x ja y suurin yhteinen tekijä (s.y.t.) on suurin kokonaisluku d, joka jakaa molemmat luvut, merkitään d = syt(x, y). S.y.t. on olemassa, jos ainakin toinen luvuista x ja y on = 0. Huomaa, että s.y.t. on positiivinen. Jos syt(x, y) = 1, sanotaan että luvuilla x ja y ei ole yhteisiä tekijöitä tai että ne ovat keskenään jaottomia. 3
Muistathan, että logaritmien kannan vaihto sujuu kaavalla logk x =
ln x . ln k
LUKU 3. KOKONAISLUVUT
18
Lause 3.6. (Bezout’n lause) Kokonaislukujen x ja y (joista ainakin toinen on = 0) s.y.t. d voidaan kirjoittaa muotoon d = c 1 x + c2 y
(ns. Bezout’n muoto),
missä c1 ja c2 ovat kokonaislukuja (ns. Bezout’n kertoimet). Lisäksi, jos x, y = 0, voidaan olettaa, että |c1 | ≤ |y| ja |c2 | ≤ |x|. Todistus. Bezout’n muodon samoin kuin s.y.t.:nkin antaa seuraava ns. (Yleistetty) Eukleideen algoritmi. Tässä oletetaan, että 0 ≤ x ≤ y, mikä ilmeisesti ei mitenkään rajoita tilannetta. Merkitään SYT(x, y) = (d, c1 , c2 ). (Yleistetty) Eukleideen algoritmi: 1. Jos x = 0, niin tulostetaan SYT(x, y) = (y, 0, 1) ja lopetetaan. 2. Jos x > 0, niin jaetaan y x:llä: y = qx + r, missä 0 ≤ r < x. Ilmeisesti syt(x, y) = syt(x, r) (ajattele jaollisuuksia). Etsitään SYT(r, x) = (d, e1 , e2 ). Silloin d = e1 r + e2 x = e1 (y − xq) + e2 x = (e2 − e1 q)x + e1 y. Tulostetaan SYT(x, y) = (d, e2 − e1 q, e1 ) ja lopetetaan. Rekursio on päättyvä, koska min(r, x) < min(x, y), ts. aina kutsuttaessa SYT ko. minimiarvo pienenee ja on lopulta = 0. Ilmeisesti juuri ennen kuin tullaan kohtaan 1. on y = qx ja r = 0 ja d = x, jolloin c1 = 1 ≤ y ja c2 = 0 ≤ x. Toisaalta, jos y = qx + r ja d = e1 r + e2 x, missä |e1 | ≤ x ja |e2 | ≤ r, niin e1 ja e2 ovat erimerkkiset ja |e2 − e1 q| = |e2 | + |e1 |q ≤ r + xq = y. Suoraan Bezout’n lauseesta näkee seuraavan tuloksen: Seuraus. Jos kokonaisluku z jakaa kokonaisluvut x ja y (joista ainakin toinen on = 0), niin se jakaa myös syt(x, y):n. Huomautus. Tästä johtuen syt(x, y) määritelläänkin usein siten, että se on x:n ja y:n yhteinen tekijä, joka on jaollinen kaikilla näiden lukujen yhteisillä tekijöillä. Tämä johtaa samaan s.y.t.:n käsitteeseen. Vm. määritelmä soveltuu kuitenkin myös tilanteeseen x = y = 0 ja antaa kaavan syt(0, 0) = 0. Toinen seuraus Bezout’n lauseesta on lukujen tekijöihinjaon yksikäsitteisyys (ks. Lause 3.3). Lause 3.7. Kokonaisluvun x = 0 tekijöihinjako on yksikäsitteinen. Todistus. Asetetaan vastaoletus: On kokonaisluku x, jolla on (ainakin) kaksi eri tekijöihinjakoa. Voidaan olettaa, että x on positiivinen ja pienin sellainen positiivinen kokonaisluku, jolla on vastaoletuksessa mainittu ominaisuus. Ilmeisesti x ≥ 2 (sillä ykkösen ainoa tekijöihinjako on tyhjä tulo). Nyt x voidaan kirjoittaa tulomuotoihin jm x = pi11 pi22 · · · pinn = q1j1 q2j2 · · · qm ,
missä p1 , . . . , pn ovat eri alkulukuja ja samoin q1 , . . . , qm ovat eri alkulukuja ja i1 , . . . , in , j1 , . . . , jm ovat positiivisia kokonaislukuja. Itse asiassa edelleen tiedetään, että myös alkuluvut p1 , . . . ,
LUKU 3. KOKONAISLUVUT
19
pn eroavat alkuluvuista q1 , . . . , qm . Jos nimittäin esimerkiksi p1 = q1 , niin kokonaisluvulla x/p1 olisi myös kaksi eri tekijöihinjakoa ja se on pienempi kuin x. Ilmeisesti syt(p1 , q1 ) = 1, joten Bezout’n muodossa 1 = c 1 p 1 + c 2 q1 . Mutta tästä seuraa, että jm jm q1j1 −1 q2j2 · · · qm = c1 p1 q1j1 −1 q2j2 · · · qm + c2 x, jm josta havaitaan, että p1 jakaa tulon q1j1 −1 q2j2 · · · qm , ts. jm = p1 z. q1j1 −1 q2j2 · · · qm jm Koska z:lla ja q1j1 −1 q2j2 · · · qm :llä on yksikäsitteiset tekijöihinjaot (ne ovat pienempiä kuin x), seuraa tästä, että p1 on jokin alkuluvuista q1 , . . . , qm , mikä on ristiriita. Vastaoletus on siis väärä.
Esitettäessä rationaaliluku muodossa x/y, on tapana että syt(x, y) = 1, ts. luku on supistetussa muodossa. Tämä on erityisen tärkeää symbolisessa analyysissä, jotta x ja y eivät pääsisi kasvamaan suuriksi. Supistettu muoto saadaan luonnollisesti jakamalla x ja y syt(x, y):llä, joten pitkissä laskuissa s.y.t. joudutaan etsimään toistuvasti. On tärkeää huomata, että Bezout’n lauseessa mainittu kertoimia koskeva ehto on voimassa eo. Eukleideen algoritmin joka vaiheessa. Välitulokset eivät näin kasva suuriksi. Jotta toisaalta saataisiin mielikuva siitä miten monta askelta eo. Eukleideen algoritmi enintään ottaa, merkitään Yn :llä pienintä sellaista positiivista kokonaislukua y, että jollekin kokonaisluvulle 0 ≤ x < Yn Eukleideen algoritmi tarvitsee n askelta. Ilmeisesti Y0 = 1, Y1 = 2 ja Y2 = 3. Lause 3.8. (Lamén lause) Yn toteuttaa rekursiokaavan Yn = Yn−1 + Yn−2 , ts. Yn on ns. n + 1:s Fibonaccin luku4 Fn+1 . Lisäksi nimenomaan syt(Fn , Fn+1 ):n laskeminen vaatii ne n askelta Eukleideen algoritmilla, kun n > 0. Todistus. Laskettaessa syt(x, Yn ) Eukleideen algoritmilla tehdään jakolaskut y0 = Yn = q1 x + r1 , y1 = x = q2 r1 + r2 , . . . , yn−3 = rn−4 = qn−2 rn−3 + rn−2 , yn−2 = rn−3 = qn−1 rn−2 + rn−1 , yn−1 = rn−2 = qn rn−1 , joten yn−1 ≥ 2 , yn−2 ≥ yn−1 + 1 , yn−3 ≥ yn−2 + yn−1 , . . . Siispä pienin y0 eli Yn saadaan valitsemalla yn−1 = 2 , yn−2 = yn−1 + 1 , yn−3 = yn−2 + yn−1 , . . . , jolloin yn−j = Fj+1 (j = 1, 2, . . . , n) ja erityisesti Yn = y0 = Fn+1 ja x = y1 = Fn . Seuraus. Jos x ja y ovat kokonaislukuja ja 0 ≤ x < y, niin syt(x, y):n laskeminen Eukleideen algoritmilla vie enintään √ √ 1+ 5 ln( 5y) ln −1 2 askelta. Todistus. Jos askelia tarvitaan n, niin y ≥ Yn = Fn+1 . Suoraan laskien voidaan todeta, että 4
Fibonaccin luvut Fn (n = 0, 1, 2, . . . ) määritellään sopimalla ensin, että F0 = F1 = 1 ja jatkamalla määrittelyä rekursiokaavalla Fn = Fn−1 + Fn−2 (n = 2, 3, . . . ), ks. Luku 9.
LUKU 3. KOKONAISLUVUT 1 Fn = √ 5
20
2 √ 5−1
n+1
1 −√ 5
(Ks. myös Pykälä 9.3.3.) Näytetään tätä käyttäen, että n 2 1 √ Fn > √ 5 5−1 Koska
riittää näyttää, että
−2 √ 5+1
2 √ 5−1
1. =√ 2 5−1 5+1 5−1
eli että
Siispä
n+1 1 2 √ √ < Fn+1 ≤ y, 5 5−1 mistä otetaan puolittain logaritmit ja pohjat.
√ Eukleideen algoritmin soveltaminen ei näin ole kovin työlästä, ln( 5y) on verrannollinen y:n pituuteen (Lause 3.5). Tarkemmin Eukleideen algoritmin laskennallista vaativuutta käsittelee esimerkiksi K NUTH . Useamman kuin kahden kokonaisluvun x1 , x2 , . . . , xN suurin yhteinen tekijä d = syt(x1 , x2 , . . . , xN ) määritellään samoin kuin kahdenkin eli se on suurin kokonaisluku, joka jakaa kaikki luvut x1 , x2 , . . . , xN . Jälleen vaaditaan, että ainakin yksi luvuista on = 0, voidaan sopia, että xN = 0. Tällainen s.y.t. voidaan laskea soveltamalla N − 1 kertaa Eukleideen algoritmia: Lause 3.9.
syt(x1 , x2 , . . . , xN ) = syt(x1 , syt(x2 , . . . , xN )) = syt(x1 , syt(x2 , syt(x3 , . . . , syt(xN −1 , xN ) · · · )))
ja lisäksi s.y.t. voidaan kirjoittaa Bezout’n muodossa syt(x1 , x2 , . . . , xN ) = c1 x1 + c2 x2 + · · · + cN xN . Todistus. Merkitään lyhyyden vuoksi d = syt(x1 , x2 , . . . , xN ) ja
d = syt(x1 , syt(x2 , syt(x3 , . . . , syt(xN −1 , xN ) · · · ))).
Bezout’n lauseen nojalla syt(xN −1 , xN ) = e1 xN −1 + e2 xN
LUKU 3. KOKONAISLUVUT
21
ja edelleen syt(xN −2 , syt(xN −1 , xN )) = e3 xN −2 + e4 syt(xN −1 , xN ) = e3 xN −2 + e4 e1 xN −1 + e4 e2 xN , jne., eli lopulta nähdään, että d = c1 x1 + c2 x2 + · · · + cN xN . Tästä seuraa, että d | d ja siis d ≤ d . Toisaalta d jakaa x1 :n ja s.y.t.:n syt(x2 , syt(x3 , . . . , syt(xN −1 , xN ) · · · )). Viimemainittu s.y.t. jakaa x2 :n ja s.y.t.:n syt(x3 , . . . , syt(xN −1 , xN ) · · · ). Jne. Siispä d jakaa kaikki luvut x1 , x2 , . . . , xN ja näin ollen d ≤ d. Kaiken kaikkiaan päätellään, että d = d . Jos lukujen x1 , x2 , . . . , xN tekijöihinjaot ovat xi = ±pj1i1 pj2i2 · · · pjMiM
(i = 1, 2, . . . , N ),
missä sovitaan, että jik = 0, mikäli luku pk ei ole xi :n alkutekijä, niin ilmeisesti min{j11 ,...,jN 1 } min{j12 ,...,jN 2 } p2
syt(x1 , x2 , . . . , xN ) = p1
min{j1M ,...,jN M }
· · · pM
.
Vaikeus tämän tuloksen käytössä on se, ettei tekijöihinjakoja yleisesti tunneta ja niiden etsiminen taas on tunnetusti hyvin työlästä. Kokonaislukujen x1 , x2 , . . . , xN pienin yhteinen jaettava (p.y.j.) on pienin positiivinen kokonaisluku, jonka kaikki luvut x1 , x2 , . . . , xN jakavat, merkitään pyj(x1 , x2 , . . . , xN ). Jotta p.y.j. olisi olemassa, pitää olla x1 , x2 , . . . , xN = 0. Myös p.y.j. saadaan rekursiivisesti Eukleideen algoritmilla, sillä Lause 3.10.
pyj(x1 , x2 , . . . , xN ) = pyj(x1 , pyj(x2 , . . . , xN )) = pyj(x1 , pyj(x2 , pyj(x3 , . . . , pyj(xN −1 , xN ) · · · )))
ja
|x1 x2 | . syt(x1 , x2 ) Todistus. Ajatellen edellä ollutta tekijöihinjakoa on ilmeisesti pyj(x1 , x2 ) =
max{j11 ,...,jN 1 } max{j12 ,...,jN 2 } p2
pyj(x1 , x2 , . . . , xN ) = p1
max{j1M ,...,jN M }
· · · pM
.
Lauseen ensimmäinen kaava seuraa tästä, sillä pk :n eksponentti pyj(x1 , pyj(x2 , . . . , xN )):ssä on max{j1k , max{j2k , . . . , jN k }} ja toisaalta max{j1k , max{j2k , . . . , jN k }} = max{j1k , j2k , . . . , jN k }
(k = 1, 2, . . . , M ).
Samoin toinen kaava seuraa tekijöihinjaosta, sillä alkutekijän pk eksponentti x1 x2 :ssa on j1k + j2k ja toisaalta max{j1k , j2k } = j1k + j2k − min{j1k , j2k }. Seuraus. (Bezout’n lause) pyj(x1 , x2 , . . . , xN ) voidaan esittää lukujen x1 , x2 , . . . , xN harmonisena yhdelmänä, ts. 1 c2 cN c1 + + ··· + (Bezout’n muoto). = pyj(x1 , x2 , . . . , xN ) x1 x2 xN Todistus. Jätetään lukijalle harjoitukseksi. Tavallinen tilanne, missä p.y.j. tulee esille, on etsittäessä rationaaliluvuille yhteenlaskua varten pienintä yhteistä nimittäjää.
LUKU 3. KOKONAISLUVUT
3.4
22
Kongruenssilaskenta eli moduläärilaskenta
Kongruenssilaskennan idea on, että lasketaan vain kokonaislukujen jakojäännöksillä käyttäen (yhtä tai useampaa) kiinteää jakajaa, ns. modulia m ≥ 2. Kongruenssilaskentaa kutsutaan usein myös moduläärilaskennaksi. Sanotaan, että kokonaisluvut x ja y ovat kongruentit modulo m, merkitään x≡y
mod m,
jos x − y on jaollinen m:llä. Tämä luetaan myös ”x on kongruentti y:n kanssa modulo m” tai vain ”x on y modulo m”. x ≡ y mod m sanoo, että jaettaessa x ja y modulilla m:llä saadaan sama (jako)jäännös, ts. x ja y kuuluvat samaan (jako)jäännösluokkaan modulo m. Jokainen kokonaisluku kuuluu aina johonkin jäännösluokkaan modulo m ja vain yhteen sellaiseen. Lause 3.11. (i) Jos x ≡ y mod m ja u ≡ v mod m, niin x + u ≡ y + v mod m. (ii) Jos x ≡ y mod m ja u ≡ v mod m, niin xu ≡ yv mod m. (iii) Jos x ≡ y mod m ja n on positiivinen kokonaisluku, niin xn ≡ y n mod m. Todistus. (i) Jos x − y = km ja u − v = lm, niin (x + u) − (y + v) = (k + l)m. (ii) Jos x − y = km ja u − v = lm, niin xu − yv = (x − y)u + (u − v)y = (ku + ly)m. (iii) Tämä seuraa (ii):sta. Näin ollen, jos ajatellaan jakojäännöksiä, voidaan laskea millä tahansa kokonaisluvuilla, joilla modulilla jaettaessa on kyseiset jakojäännökset, ja tulokset ovat samat, ts. edustajien valinnasta riippumattomat. Tietyt edustajajoukot, ns. jäännössysteemit, ovat kuitenkin usein esillä: • positiivinen jäännössysteemi 0, 1, . . . , m − 1; • symmetrinen jäännössysteemi (parittomalle m:lle) −
m−1 m−3 m−3 m−1 ,− , . . . , −1, 0, 1, . . . , , ; 2 2 2 2
• negatiivinen jäännössysteemi −m + 1, . . . , −1, 0. Tavallisin on positiivinen jäännössysteemi. Yleisesti mitkä tahansa m kokonaislukua, joista mitkään eivät ole keskenään kongruentteja modulo m, muodostavat jäännössysteemin modulo m. Jakolasku ei yleisesti ole sallittua kongruensseissa, vaan vain seuraavassa mielessä: Lause 3.12. xu ≡ yu mod m on sama kuin kuin x ≡ y mod m/syt(u, m), eli kongruenssista saa supistaa pois kokonaisluvun, mikäli samalla jakaa modulin sen ja supistettavan luvun s.y.t.:llä. Todistus. Lähdetään ensin liikkeelle siitä, että xu ≡ yu mod m eli että (x − y)u = km. Merkitään d = syt(u, m) ja u = du1 sekä m = dm1 . Silloin ilmeisesti syt(u1 , m1 ) = 1 ja m1 = m/syt(u, m) ja vielä (x − y)u1 = km1 . Bezout’n lauseen mukaan 1 = c1 u1 + c2 m1 , josta seuraa että x − y = c1 u1 (x − y) + c2 m1 (x − y) = (c1 k + c2 (x − y))m1 , ts. että x ≡ y mod m/syt(u, m). Lähdetään sitten liikkeelle siitä, että x ≡ y mod m/d eli että x − y = km/d. Tästä seuraa, että (x − y)d = km ja edelleen että (x − y)u = u1 km. Siispä xu ≡ yu mod m.
LUKU 3. KOKONAISLUVUT
23
Erityisesti kokonaisluvun, jolla ei ole yhteisiä tekijöitä modulin kanssa, saa supistaa pois kongruenssista (moduliin koskematta). Seuraus. Jos syt(x, m) = 1, niin luvut y + kx (k = 0, 1, . . . , m − 1) muodostavat jäännössysteemin modulo m, olipa y mikä tahansa kokonaisluku. Todistus. Lukuja on m kpl. Jos y + ix ≡ y + jx mod m, missä 0 ≤ i, j ≤ m − 1, niin ix ≡ jx mod m ja Lauseen 3.12 nojalla i ≡ j mod m. Siis j − i = km, mutta koska 0 ≤ i, j ≤ m − 1, tämä on mahdollista vain kun k = 0 eli i = j. Luvut eivät siis ole kongruentteja keskenään. Samantapaisella tekniikalla nähdään välittömästi, että jos syt(x, m) = 1, niin x:llä on inverssi modulo m, ts. on sellainen luku y, että xy ≡ 1
mod m.
Tällöin kirjoitetaan myös x−1 ≡ y mod m tai 1/x ≡ y mod m. Tällainen inverssi saadaan Eukleideen algoritmilla, sillä Bezout’n lauseen nojalla 1 = c1 x+c2 m ja näin x−1 ≡ c1 mod m. Hyvin usein moduli on alkuluku p. Tällöin muut kuin p:llä jaolliset kokonaisluvut voidaan aina supistaa pois kongruensseista modulo p ja niillä on myös inverssi modulo p. Myös potenssien laskenta helpottuu, sillä Lause 3.13. (Fermat’n pieni lause) Jos syt(x, p) = 1 ja p on alkuluku, niin xp−1 ≡ 1
mod p.
Todistus. Otetaan positiivinen jäännössysteemi 0, 1, . . . , p−1 sekä eo. Seurauksen antama jäännössysteemi 0, x, 2x, . . . , (p − 1)x. Nämä luvut ovat keskenään pareittain kongruentteja modulo p jossain järjestyksessä: 0≡0
mod p , 1 ≡ k1 x
mod p , 2 ≡ k2 x
mod p , . . . , p − 1 ≡ kp−1 x
mod p.
Siispä (Lause 3.11 kohta (ii)) 1 · 2 · · · (p − 1) ≡ k1 k2 · · · kp−1 xp−1
mod p.
Mutta k1 k2 · · · kp−1 = 1 · 2 · · · (p − 1) ja ilmeisesti syt(1 · 2 · · · (p − 1), p) = 1, joten Lauseen 3.12 nojalla xp−1 ≡ 1 mod p. Laskettaessa nyt xn modulo p, missä syt(x, p) = 1 ja n on suuri luku, jaetaan n ensin p − 1:llä n = q(p − 1) + r ,
0 ≤ r < p − 1,
jolloin xn ≡ xq(p−1)+r ≡ (xp−1 )q xr ≡ xr
mod p.
xr modulo p onkin sitten jo paljon helpompi laskea. Jos taas syt(x, p) = 1, niin p | x ja xn ≡ 0 mod p. Näin hyvinkin korkeiden potenssien lasku modulo alkuluku on rutiininomaista. Samalla tekniikalla saadaan myös x:n inverssi modulo p, sillä ilmeisesti x−1 ≡ xp−2 mod p. Jos modulin tekijöitä tunnetaan, ts. voidaan kirjoittaa m = m1 m2 · · · mk , seuraa kongruenssista x ≡ y mod m luonnollisesti kongruenssit x ≡ y mod mi (i = 1, 2, . . . , k). Jos moduli on suuri luku, voi usein olla helpompaa laskea käyttäen näitä pienempiä moduleja. Näin voidaan tehdä aivan yleisestikin, jos tekijät m1 , m2 , . . . , mk ovat pareittain keskenään jaottomia:
LUKU 3. KOKONAISLUVUT
24
Lause 3.14. (Kiinalainen jäännöslause) Jos modulit m1 , m2 , . . . , mk ovat pareittain keskenään jaottomia, on täsmälleen yksi kokonaisluku x modulo m1 m2 · · · mk , joka toteuttaa k kongruenssia x ≡ yi mod mi (i = 1, 2, . . . , k). Todistus. Merkitään M = m1 m2 · · · mk ja Mi = M/mi (i = 1, 2, . . . , k), jolloin syt(M1 , M2 , . . . , Mk ) = 1 ja syt(mi , Mi ) = 1 (i = 1, 2, . . . , k) (miksi?). Seuraava menetelmä tuottaa ratkaisun x (jos sellainen on!) ja näyttää myös, että ratkaisu on yksikäsitteinen modulo M : 1. Kirjoitetaan yleistettyä Eukleideen algoritmia käyttäen syt(M1 , M2 , . . . , Mk ) = 1 Bezout’n muotoon 1 = c 1 M1 + c 2 M2 + · · · + c k Mk . 2. Tulostetaan x ≡ c1 M1 y1 + c2 M2 y2 + · · · + ck Mk yk mod M . (Vaikkapa positiivisessa jäännössysteemissä.) Menettely toimii, jos ratkaisu on, sillä kongruensseista x ≡ yi mod mi seuraa suoraan, että ci Mi x ≡ ci Mi yi mod M (i = 1, 2, . . . , k) ja puolittain yhteenlaskien edelleen että x = 1 · x = (c1 M1 + c2 M2 + · · · + ck Mk )x ≡ c1 M1 y1 + c2 M2 y2 + · · · + ck Mk yk
mod M.
Vielä pitää vielä osoittaa, että ratkaisu on olemassa. Koska ilmeisestikin Mi ≡ 0 mod mj , jos i = j, ja toisaalta 1 = c1 M1 + c2 M2 + · · · + ck Mk , niin ci Mi ≡ 1 mod mi (i = 1, 2, . . . , k). Siispä x ≡ c 1 M 1 y 1 + c 2 M2 y 2 + · · · + c k Mk y k ≡ y i
3.5
mod mi
(i = 1, 2, . . . , k).
Kertoma. Stirlingin approksimaatio
n-kertoma n! = 1 · 2 · · · n on tuttu kokonaislukufunktio. Symbolisen laskennan ohjelmistoissa se yleensä tulostuu ja sillä lasketaan gammafunktion avulla. Peruskursseista tuttu gammafunktiohan ∞ Γ(x) =
tx−1 e−t dt
0
saa arvon Γ(x) = (x − 1)!, jos x on positiivinen kokonaisluku (mikä nähdään x − 1-kertaisella osittaisintegroinnilla). Ts. gammafunktio on kertoman jatkuva yleistys. Itse asiassa gammafunktio on määritelty kaikille arvoille x > 0 (ja myös jatkettuna niille negatiivisille x:n arvoille, jotka eivät ole kokonaislukuja). Gammafunktiolle tunnetaan koko joukko (oleellisesti symbolisia) laskusääntöjä5 , joten ohjelmistot käyttävät mielellään näitä, myös kun käsitellään vain kertomaa. Tulos on toisinaan yllättävä. Alla Maple-ohjelmiston piirtämä gammafunktion Γ(x) kuvaaja välillä −4 ≤ x ≤ 4: 5
Ks. esimerkiksi A BRAMOWITZ & S TEGUN .
LUKU 3. KOKONAISLUVUT
25 6 4 y 2 0
–4 –3 –2
1 2 3 4 x
–2 –4 –6
Kertoma n! on hyvin nopeasti kasvava funktio. Toisaalta symbolisen laskennan ohjelmistot pystyvät käsittelemään hyvin suuria kokonaislukuja, joten kertomilla voidaan mainiosti laskea suurillekin n:n arvoilla. Kertoman suuruusluokan, enemmän tai vähemmän tarkasti, antavat erilaiset ns. Stirlingin approksimaatiot. Yksinkertaisin on Lause 3.15. (Heikko Stirlingin kaava) nn e1−n ≤ n! ≤ nn+1 e1−n (n = 1, 2, . . . ) Todistus. Tapaus n = 1 on selvä, joten oletetaan, että n ≥ 2. Koska ln x on kasvava funktio, tiedetään integraalilaskennasta, että k+1 ln k ≤ ln x dx ≤ ln(k + 1) (k = 1, 2, . . . ). k
Lasketaan nämä kaksoisepäyhtälöt puolittain yhteen k:n arvoille k = 1, . . . , n − 1: n ln x dx ≤ ln 2 + · · · + ln n
ln 1 + · · · + ln(n − 1) ≤ 1
eli
n ln x dx ≤ ln(n!)
ln((n − 1)!) ≤ 1
eli ln((n − 1)!) ≤
n
(x ln x − x) ≤ ln(n!)
1
eli ln((n − 1)!) ≤ n ln n − n + 1 ≤ ln(n!). Sama asia toisin kirjoitettuna: n ln n − n + 1 ≤ ln(n!) ≤ (n + 1) ln n − n + 1. Itse kaava saadaan tästä eksponenttifunktiolla kuvaamalla (eksponenttifunktiohan on kasvava funktio).
LUKU 3. KOKONAISLUVUT
26
Arviointia terästämällä (ks. G RAHAM & K NUTH & PATASHNIK tai G REENE & K NUTH tai K NUTH) saadaan vahvempia Stirlingin approksimaatioita, esimerkiksi seuraavat: √ √ 1 1 (1) 2πn nn e−n+ 12n+0.6/n < n! < 2πn nn e−n+ 12n (n = 1, 2, . . . ) √ θn (2) n! = 2πn nn e−n+ 12n , missä 0 < θn < 1 (n = 1, 2, . . . ) √ 1 1 −5 (3) n! = 2πn nn e−n+ 12n − 360n3 +O(n ) √ 139 571 1 1 n −n −5 (4) n! = 2πn n e − − + O(n ) 1+ ++ 12n 288n2 51840n3 2488320n4 Tässä O(f (n)) tarkoittaa kollektiivisesti sellaista ”korjaustermiä” φn , että jostain rajasta n ≥ n0 lähtien |φn | ≤ Cf (n), missä C on vakio (ns. O-notaatio, vrt. sivu 7). Fermat’n pienen lauseen nojalla saatiin helposti lasketuksi korkeatkin potenssit modulo alkuluku. Samantapainen tulos saadaan kertomalle (ja itse asiassa Fermat’n pienen lauseen seurauksena!). Perustana on Lause 3.16. (Wilsonin lause) Kokonaisluku p ≥ 2 on alkuluku tarkalleen silloin, kun (p − 1)! ≡ −1
mod p.
Todistus. Todistus siihen suuntaan, että jos p on alkuluku, niin esitetty kongruenssi pätee, vaatii polynomien juurirakenteen tuloksia. Se on esitetty sivun 50 alaviitteessä. Jos taas kongruenssi pätee, mutta p on yhdistetty luku, sanotaan p = ab, missä a, b ≥ 2, niin saadaan ristiriita. Silloin nimittäin (p − 1)! = 1 · 2 · · · a · · · (p − 1) ≡ 0 mod a, mutta koska toisaalta myös (p − 1)! ≡ −1 mod p ja siis myös mod a, olisi näin 0 ≡ −1 mod a, mikä ei käy. Ilmeisesti n! ≡ 0 mod p, jos n ≥ p. Wilsonin lauseen avulla saadaan muita kertomaa koskevia kongruensseja.
3.6
Binomi- ja multinomikertoimet
Yleisesti binomikerroin6 määritellään seuraavasti: x x(x − 1) · · · (x − k + 1) = . k k! Tässä k on ei-negatiivinen kokonaisluku, mutta x saa olla mitä tahansa. (Kyllä vaan, kompleksiluku, funktio tai vaikkapa neliömatriisi!) Mikäli x on kokonaisluku, niin x! x k!(x − k)! = x − k , jos x ≥ k x = 0, jos 0 ≤ x < k k k (k − 1 − x)! k k−1−x (−1) = (−1) , jos x < 0. (−1 − x)!k! k Luetaan ”x yli k:n”. x on kertoimen osoittaja ja k sen nimittäjä. Lauseke x(x − 1) · · · (x − k + 1) muuten tunnetaan ns. Pochhammerin symbolina, merkitään xk . Ks. Pykälä 8.1. 6
LUKU 3. KOKONAISLUVUT
27
= (−1)k . Siispä esimerkiksi −1 k Symbolisen laskennan ohjelmistoissa käytetään vieläkin yleisempää määritelmää x Γ(x + 1) = , k Γ(k + 1)Γ(x − k + 1) joka ”toimii” myös kun k ei ole kokonaisluku. Jos k on kokonaisluku, antavat määritelmät saman tuloksen. Tämä johtuu gammafunktion laskukaavasta Γ(y + 1) = yΓ(y). Samalla laskukaavalla saadaan edelleen binomikerrointen ”peruskaava”: x+1 x x Lause 3.17. = + k+1 k k+1 Todistus. Suoraan laskien x+1 Γ(x + 2) (x + 1)Γ(x + 1) = = k+1 Γ(k + 2)Γ(x − k + 1) Γ(k + 2)Γ(x − k + 1) (k + 1 + x − k)Γ(x + 1) = Γ(k + 2)Γ(x − k + 1) (k + 1)Γ(x + 1) (x − k)Γ(x + 1) = + Γ(k + 2)Γ(x − k + 1) Γ(k + 2)Γ(x − k + 1) Γ(x + 1) Γ(x + 1) = + Γ(k + 1)Γ(x − k + 1) Γ(k + 2)Γ(x − k) x x = + . k k+1 x Seuraus. Jos x ja k ≥ 0 ovat kokonaislukuja, on sitä myös . k Todistus. Tapaus, jossa x on negatiivinen, palautuu tapaukseen, jossa x on ei-negatiivinen, joten katsotaan vain tapaus x ≥ 0. Peruskaavan nojalla palaudutaan lopulta muotoa n n = 1 ja =1 0 n olevien binomikerrointen summaan, joka on kokonaisluku. Yo. todistuksesta saadaan tuttu Pascalin kolmio, jonka binomikertoimet muodostavat: 1 1 1 1 1 1 1 ...
2 3
4 5
6 ...
1 3
6 10
15 ...
1
...
1 4
10
1 5
1
20 15 6 1 .. . . . . ... .. .. . .
LUKU 3. KOKONAISLUVUT
28
Toisinaan binomikerroin palautuu symbolisessa laskennassa ns. betafunktioon β(x, y), joka määritellään7 kaavalla Γ(x)Γ(y) β(x, y) = . Γ(x + y) Laskien voi todeta, että betafunktio ja binomikerroin liittyvät toisiinsa seuraavasti: x 1 = . k (x − k)β(x − k, k + 1) Tuttu paikka, jossa binomikertoimet tulevat vastaan, on binomikaava: n
(a + b) =
n n i=0
i
ai bn−i .
Samantapainen kaava, ns. multinomikaava, saadaan myös jos yhteenlaskettavia on useampia kuin kaksi. Tätä varten tarvitaan multinomikerroin x x! = , k 1 , k 2 , . . . , km k1 !k2 ! · · · km ! jossa k1 , k2 , . . . , km ovat ei-negatiivisia kokonaislukuja ja x = k1 + k2 + · · · + km . n n ai11 ai22 · · · aimm Lause 3.18. (Multinomikaava) (a1 + a2 + · · · + am ) = i , i , . . . , i 1 2 m i ,i ,...,i ≥0 1 2
m
i1 +i2 +···+im =n
Todistus. Kaava pitää ilmeisesti paikkansa, kun m = 1, sillä multinomikerroin on silloin = 1, ja tietysti myös, kun m = 2 (binomikaava). Riittääkin näyttää, että jos kaava pitää paikkansa m:n arvolla m = l − 1, niin se pitää myös paikkansa yhtä isommalla m:n arvolla m = l. Jos kaava on oikea arvolla m = l − 1, niin n n i1 n n (a1 + a2 + · · · + al ) = (a1 + (a2 + · · · + al )) = a1 (a2 + · · · + al )n−i1 i1 i1 =0 n n i1 n − i1 = a1 ai22 · · · aill i1 i2 , . . . , il i =0 i ,...,i ≥0 1
=
2
i1 ,i2 ,...,il ≥0 i1 +i2 +···+il =n
l
i2 +···+il =n−i1
n ai1 ai2 · · · aill . i1 , i2 , . . . , il 1 2
Näin ollen, jos kaava on oikea arvoilla m = 1, 2, niin se on oikea myös arvolle m = 3 (trinomikaava), ja arvolle m = 4, jne. 7
Jos x, y > 0, voidaan betafunktio määritellä myös integraalina 1 tx−1 (1 − t)y−1 dt.
β(x, y) = 0
Tämä näytetään kirjoittamalla yhtälö β(x, y)Γ(x + y) = Γ(x)Γ(y) kaksinkertaisten integraalien avulla.
LUKU 3. KOKONAISLUVUT
29
Avattaessa potenssi (a + b)n binomikaavalla saadaan n + 1 yhteenlaskettavaa. Avattaessa potenssi (a1 + a2 + · · · + am )n multinomikaavalla saadaan yhtä monta yhteenlaskettavaa kuin on n alkion toistokombinaatioita m:stä eri alkiosta eli tunnetusti m+n−1 (m + n − 1)(m + n − 2) · · · (m + 1)m = kpl. n n! Tämä luku voi olla suurikin, jos m on suuri, jolloin voi olla syytä välttää avaamasta eksplisiittisesti multinomilausekkeita.
3.7
(Suurten) kokonaislukujen algoritmeja Alkulukutestaus
Positiivisen kokonaisluvun n ≥ 2 alkulukutestaukseen on nopeita algoritmeja. Yksinkertainen √ (mutta hidas) tapa on testata jakaako jokin kokonaisluvuista 2, 3, . . . , n luvun n. Tämä voidaan tehdä ns. Eratostheneen seulan muodossa: Eratostheneen seula: 1. Asetetaan J ← [2, 3, . . . , n] (lista) sekä k ← 2. 2. Jos k 2 > n, n on alkuluku ja lopetetaan. 3. Jos n ei ole listalla J , n on yhdistetty luku ja lopetetaan. 4. Jos k 2 ≤ n ja n on listalla J , muodostetaan uusi lista J korvaamalla listalla J k:sta √ lähtien joka k:s termi (ts. k:lla jaolliset luvut) poistomerkillä . (Vaihtoehtoisesti voitaisiin poistaa listalta kaikki k:lla jaolliset luvut.) Asetetaan J ← J sekä k ← k + 1 ja mennään kohtaan 2. Tämä yksinkertainen jo antiikin kreikkalaisten tuntema seulamenetelmä voidaan yleistää tavattoman paljon tehokkaammiksi seulamenetelmiksi (ks. esimerkiksi R IESEL tai VON ZUR G ATHEN & G ERHARD tai C RANDALL & P OMERANCE ). Huomaa, että jos n on yhdistetty luku, tuottaa Eratostheneen seula sen pienimmän alkutekijän p. Ajamalla seula uudelleen luvulle n/p, saadaan uusi alkutekijä, ja tätä toistamalla lopulta luvun n tekijöihinjako. Eräät alkulukutestit ovat probabilistisia, ts. ne tuottavat (oikean) tuloksen vain tietyllä suurella todennäköisyydellä. Tällainen testi on esimerkiksi ns. Miller–Rabin-testi8 . Testi perustuu Fermat’n pieneen lauseeseen. Sen mukaisesti, jos p on alkuluku ja x on sellainen kokonaisluku, että syt(x, p) = 1, niin xp−1 ≡ 1 mod p. Kirjoitetaan p muotoon p = 1 + 2l m, missä m on pariton. Jos p on pariton, niin l ≥ 1 ja l
0 ≡ xp−1 − 1 = x2 m − 1 = (x2
l−1 m
l−1
− 1)(x2 l−1
l−1 m
+ 1)
mod p l−1
ja koska p on alkuluku se jakaa joko x2 m − 1:n tai x2 m + 1:n. Jos p jakaa x2 m − 1:n, niin sama operaatio voidaan toistaa. Jne. Tästä päätellään, että joko jollekin luvulle i = 0, 1, . . . , l−1 i
x2 m ≡ −1 8
mod p
Alkuperäisviitteet ovat M ILLER , G.L.: Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System Sciences 13 (1976), 300–317 sekä R ABIN , M.O.: Probability Algorithms. Algorithms and Complexity (J.F. Traub, toim.). Academic Press (1976), 35–36.
LUKU 3. KOKONAISLUVUT
30
tai sitten, ellei näin ole, lopulta xm ≡ 1 mod p. Jos nyt jollekin sellaiselle kokonaisluvulle x, että syt(x, p) = 1 ja xm ≡ ±1 mod p, onkin kaikille luvuille i = 1, 2, . . . , l − 1 i
x2 m ≡ 1 mod p, niin voidaan vain päätellä, että p ei olekaan alkuluku. (Samoin, kun kohdataan sellainen i > 0, i että x2 m ≡ ±1 mod p.) Toisaalta, kun kokeillaan useita lukuja, esimerkiksi tiettyä määrää ”pieniä” alkulukuja x = 2, 3, 5, 7, 11, . . . , saadaan tietynlainen ”todiste” sille, että p on alkuluku. Itse asiassa tämä todiste voidaan saada erittäin varmaksi käyttämällä kyllin monta hyvin valittua lukua x. (Myös todennäköisyysmielessä, ajatellen luvun x satunnaista valintaa.) Seuraavassa oletetaan, että käytössä ovat testiluvut x1 , x2 , . . . , xN (annetut tai satunnaiset). Miller–Rabin-alkulukutesti: 1. Jos p on parillinen, on asia helppo ja lopetetaan. 2. Jos p on pariton, asetetaan l ← 0 ja m ← p − 1. 3. Asetetaan l ← l + 1 ja m ← m/2. 4. Jos m on parillinen, mennään kohtaan 3. 5. Asetetaan j ← 0. 6. Jos j < N , asetetaan j ← j + 1 ja x ← xj . Muutoin tulostetaan ”ALKULUKU” (arveltu tieto) ja lopetetaan. 7. Jos xm ≡ 1 mod p tai syt(x, p) = 1, niin mennään kohtaan 6. Jos taas 1 < syt(x, n) < n, tulostetaan ”YHDISTETTY LUKU” (varma tieto) ja lopetetaan. 8. Asetetaan i ← l − 1. i
9. Jos x2 m ≡ ±1 mod p, tulostetaan ”YHDISTETTY LUKU” (varma tieto) ja lopetetaan. i
10. Jos x2 m ≡ −1 mod p, mennään kohtaan 6. 11. Asetetaan i ← i − 1 ja mennään kohtaan 9. Huomautus. Tämä on ”top-down”-versio testistä. Siitä on myös ”bottom-up”-versio, jossa i kasvaa (ks. esimerkiksi moniste RUOHONEN , K.: Kryptologia). Näillä ei liene suurta eroa nopeudessa. Testi ei siis ole ”vuoren varma”. Sellaisia yhdistettyjä lukuja, joita testi arvelee alkuluvuiksi, kutsutaan vahvoiksi valealkuluvuiksi testilukujen x1 , x2 , . . . , xN suhteen. Esimerkiksi 25326001 = 2251 · 11251 on vahva valealkuluku testilukujen 3 ja 5 suhteen. Alkulukutestien ”aatelia” ovat Adleman–Pomerance–Rumely-testi9 ja sen seurannaiset. Testi pohjautuu varsin pitkälle menevään lukuteoriaan ja on nopea, luvun n alkulukutestaus vie sillä enintään O((ln n)c ln(ln(ln n)) ) askelta, missä c on (pieni) vakio. Toisaalta, sekä teoreettisesti että implementointia ajatellen, se on vaikea käsiteltävä. 9
Alkuperäisviite on A DLEMAN , L. & P OMERANCE , C. & RUMELY, R.: On Distinguishing Prime Numbers from Composite Numbers. Annals of Mathematics 117 (1983), 173–206. Ks. myös C RANDALL & P OMERANCE .
LUKU 3. KOKONAISLUVUT
31
Viime aikojen suuria lukuteorian tuloksia on se, että alkulukujen tunnistus on polynomiaikainen. Tämän todistivat intialaiset Manindra Agrawal, Neeraj Kayal ja Nitin Saxena v. 2002 käsikirjoituksessaan PRIMES is in P. Algoritmin todistettu kompleksisuus on O((ln n)8 ), mutta heuristisesti sille saadaan kompleksisuus O((ln n)6 ). Kovin nopeita implementointeja ei kuitenkaan toistaiseksi ole, vaikka algoritmi on varsin lyhyt esittää. Tekijöihinjako Kokonaislukujen tekijöihinjako on tuntuvasti työläämpi kuin alkulukutestaus. Eo. Eratostheneen seula käy myös tekijöihinjakoon, mutta on hidas. Toisaalta luvun n tekijöihinjakoon kehitetyt parhaat algoritmitkin vievät tyypillisesti ln(ln n) c ln n O n askelta, missä c on (pieni) vakio. Ks. esimerkiksi R IESEL tai C RANDALL & P OMERANCE . Esimerkkinä hiukan Eratostheneen seulaa nopeammasta menetelmästä otetaan Pollardin ρ-menetelmä. Pollardin ρ-menetelmä: 1. Valitaan kokonaisluku x0 satunnaisesti väliltä 0, . . . , n − 1 ja asetetaan y0 ← x0 sekä i ← 0. 2. Asetetaan i ← i + 1 ja xi ← x2i−1 + 1
mod n
2 sekä yi ← (yi−1 + 1)2 + 1
mod n
ja lasketaan d = syt(xi − yi , n). Tässä käytetään positiivisen jäännössysteemin lukuja. Huomaa, että yi ≡ x2i mod n. 3. Jos d = 1, mennään kohtaan 2. 4. Jos taas 1 < d < n, tulostetaan ei-triviaali tekijä d ja lopetetaan. 5. Jos d = n (eli xi = yi ), lopetetaan ilman tulosta. Luonnollisesti iteraatioiden lukumäärälle (eli laskurille i) pitää asettaa jokin yläraja. Menettely perustuu siihen, että kohdan 2. rekursiiviset kaavat kuljettavat xi :tä ja yi :tä satunnaisesti ja toisistaan riippumattomasti jäännösluokkien joukossa. Jos n on yhdistetty luku, sillä on alkutekijä p ja xi ≡ yi mod n, niin myös xi ≡ yi mod p ja p | d. Ks. esimerkiksi VON ZUR G ATHEN & G ERHARD . Yhteen- ja vähennyslasku Tavallinen koulussa opittu yhteenlasku sekä vähennyslasku ovat sellaisenaankin sopivia myös ohjelmoitaviksi. Kertolasku Tavallinen koulussa opittu kertolasku on sopiva tietokoneellekin, mutta se ei ole likellekään nopein mahdollinen. Lukujen n ja m kertolasku vaatii tällä tavoin noin O(ln n ln m) askelta, mikä voi olla paljon.
LUKU 3. KOKONAISLUVUT
32
Karatsuban algoritmi on nopeampi kuin perinteinen algoritmi. Algoritmi on eräänlainen ”hajoita ja hallitse” -menetelmä. Lukujen n ja m kertomiseksi (desimaaliesityksessä) kirjoitetaan ne ensin muotoon n = a10k + b ja m = c10k + d, missä a, b, c, d < 10k ja lukujen maksimipituus on 2k tai 2k − 1. Toinen luvuista a ja c voi olla nolla, mutta eivät molemmat. (Ts. kirjoitetaan ainakin toinen luvuista 10k -kantaisessa esityksessä.) Silloin nm = (a10k + b)(c10k + d) = y102k + (x − y − z)10k + z, missä x = (a + b)(c + d) ,
y = ac
ja
z = bd,
ts. tarvitaankin vain kolme erillistä ”pitkää” kokonaislukujen kertolaskua (eikä neljä kuten äkkinäisempi luulisi). Kun nämä kolme kertolaskua (a + b)(c + d) ,
ac
ja
bd
edelleen suoritetaan samalla tavoin jakamalla kertolaskut kolmeen lyhyempään kertolaskuun, jne., jolloin lopulta päädytään kertotaulun käyttöön, saadaan varsinainen Karatsuban algoritmi (merkitään TULO(n, m) = nm): Karatsuban algoritmi: 1. Jos n, m < 10, katsotaan TULO(n, m) taulukosta ja lopetetaan. 2. Jos n ≥ 10 tai m ≥ 10, kirjoitetaan n ja m muotoon n = a10k + b ja m = c10k + d, missä a, b, c, d < 10k . (Desimaaliesityksessä tämä on helppoa.) 3. Lasketaan TULO(a + b, c + d), TULO(a, c) ja TULO(b, d) ja tulostetaan (helposti saatava) TULO(n, m) = 102k TULO(a, c) + 10k (TULO(a + b, c + d) − TULO(a, c) − TULO(b, d)) + TULO(b, d). Menettely pysähtyy, sillä kerrottavien lukujen maksimipituus pienenee noin puoleen joka kierroksella. Jos kerrotaan Karatsuban algoritmilla kaksi N -pituista lukua ja merkitään K(N ):llä tarvittavien numeraaleja 0, 1, . . . , 9 koskevien peruslaskutoimitusten enimmäismäärää, niin ilmeisestikin saadaan K(N ):lle seuraava rekursiokaava αN + 3K(N/2), jos N on parillinen K(N ) = , K(1) = 1, αN + 3K((N + 1)/2), jos N on pariton missä kerroin α saadaan tarvittavien yhteen- ja vähennyslaskujen määrästä (käytetystä algoritmista riippuen). Tietyn arvion tarvittavien perusoperaatioiden määrästä antaa Lause 3.19. Jos N = 2l , niin K(N ) = (2α + 1)3l − α2l+1 = (2α + 1)N log2 3 − 2αN . Todistus. Ilmeisesti arvo on oikea, kun N = 1. Jos arvo pätee, kun N = 2l , se pätee myös kun N = 2l+1 , sillä K(2l+1 ) = α2l+1 + 3K(2l ) = α2l+1 + 3(2α + 1)3l − 3α2l+1 = (2α + 1)3l+1 − α2l+2 . (Tässä esiintyvä rekursiokaava on K(N ) = αN +3K(N/2), K(1) = 1, jonkalaisia symbolisen laskennan ohjelmistotkin pystyvät ratkaisemaan. Ks. Pykälä 9.2.)
LUKU 3. KOKONAISLUVUT
33
Luonnollisesti lauseesta suurelle pituudelle N saatava perusoperaatioiden enimmäismäärä (2α + 1)N log2 3 − 2αN on tuntuvasti pienempi kuin O(N 2 ). Esimerkiksi jos N = 100000, niin N 2 /N log2 3 ≈ 119. Karatsuban menetelmästä on vieläkin nopeampia versioita, joissa kertolasku jaetaan useampaan kuin kahteen osaan, ks. esimerkiksi M IGNOTTE . Nopeimmat kertolaskualgoritmit perustuvat ns. nopean Fourier’n muunnoksen (FFT) käyttöön, ks. esimerkiksi L IPSON tai C RANDALL & P OMERANCE . Tällöin perusoperaatioiden lukumäärä on O(N ln N ln(ln N )). (Ks. myös kurssi Fourier’n menetelmät tai Laaja Fourieranalyysi.) Jakolasku Tavanomainen koulussa opetettu ns. ”pitkäjako” on siirrettävissä tietokoneelle, tosin siinä oleva arvausvaihe on jonkin verran hankala toteuttaa tehokkaasti, ks. K NUTH . Perusoperaatioiden lukumäärä on O(N 2 ), missä on N on jaettavan pituus. Peruskursseilta tuttuun Newtonin menetelmään pohjautuva jakolasku on varsin tehokas. Merkitään jaettavan n pituutta N :llä ja jakajan m pituutta M :llä. Koska tapaukset N < M ja N = M ovat helppoja, oletetaan, että N > M . Funktion f (x) = m − 1/x nollakohdan eli 1/m:n etsimiseksi saadaan Newton-iteraatio xi+1 = xi −
f (xi ) = 2xi − mx2i . f (xi )
Käytännössä, jotta voitaisiin käyttää kokonaislukujen kertolaskua, lasketaankin 10M /m, jolle saadaan vastaavasti Newton-iteraatio yi+1 = 2yi −
m 2 y . 10M i
Merkitään
10M = yi + i , m missä i on virhe. Tarkoitus on saada laskettua n/m 1:n tarkkuudella, jolloin ottamalla pohja saadaan osamäärä tai osamäärä ± 1, mistä helpolla korjauksella saadaan oikea osamäärä ja siitä sitten jakojäännös. Näin ollen pitää olla n n n − M yi = M |i | < 1 m 10 10 eli
10M . n Toisaalta 10M /n > 10M −N , joten asetetaankin vaatimukseksi |i |
M , lasketaan 10M /m. Jälleen tämä on helppoa, sillä 1 ≤ 10M /m ≤ 10. (Kokeilemalla tai muuten.) Asetetaan I ← log2 (N − M ) − log2 (log10 2). 5. Jos 10M /m−10M /m ≤ 1/2 eli 2·10M −2m10M /m ≤ m asetetaan y0 ← 10M /m. Muuten asetetaan y0 ← 10M /m + 1. 6. Toistetaan I kertaa rekursiokaavaa yi+1 =
1 yi (2 · 10M − myi ) 10M
lähtien arvosta y0 . Huomaa, että koska jaetaan vain 10M :llä, mikä on helppoa desimaaliluvuille, tarvitaan vain kokonaislukujen kertolasku, halutun tarkkuuden puitteissa. Riittää käyttää N desimaalia. 7. Testataan kertolaskulla kumpi luvuista n yi vai 10M
n yi + 1 10M
on oikea osamäärä q. Tulostetaan q ja jakojäännös r = n − qm ja lopetetaan. Myös Karatsuban algoritmin tapainen jakolaskualgoritmi on mahdollinen ja varsin nopea (ks. esimerkiksi M IGNOTTE tai moniste RUOHONEN , K.: Kryptologia).
LUKU 3. KOKONAISLUVUT
35 Potenssiin korotus
Luvun a potenssiin korotus an peräkkäisillä kertomisilla on liian aikaaviepää, sillä siihen tarvitaan |n| − 1 kertolaskua, kun itse asiassa enintään 2log2 |n| kertolaskuakin riittää: Venäläisten talonpoikien menetelmä: 1. Jos n = 0, tulostetaan potenssi 1 ja lopetetaan. 2. Jos n < 0, asetetaan a ← a−1 sekä n ← −n. 3. Jos n ≥ 1, muodostetaan n:n binääriesitys bj bj−1 · · · b0 , missä j = log2 n (n:n pituus binäärilukuna miinus yksi, ks. Lause 3.5). 4. Asetetaan i ← 0 sekä x ← 1 ja y ← a. 5. Jos i = j, niin tulostetaan potenssi xy ja lopetetaan. 6. Jos i < j ja 6.1 bi = 0, niin asetetaan i ← i + 1 sekä y ← y 2 ja mennään kohtaan 5. 6.2 bi = 1, niin asetetaan x ← xy ja y ← y 2 sekä i ← i + 1 ja mennään kohtaan 5. Algoritmin toimivuus seuraa välittömästi binääriesityksestä: |n| = bj 2j + bj−1 2j−1 + · · · + b1 2 + b0 ja
a|n| = abj 2 abj−1 2 j
j−1
· · · ab1 2 ab0 .
Käytännössä lienee mukavaa laskea n:n binääriesitystä sitä mukaa, kun sitä tarvitaan, eikä kerralla alussa. Itse asiassa tämä menettely toimii kaikenlaisille potensseille ja myös silloin kun kertolasku ei ole vaihdannainen, siis esimerkiksi polynomien tai matriisien potenssiinkorotuksessa. Laskettaessa potensseja modulo m pitää tulot tietysti redusoida koko ajan positiiviseen jäännössysteemiin modulo m, jotteivat välitulokset kasvaisi suuriksi. Näin voidaan laskea hyvinkin korkeita moduläärisiä potensseja. Nimi muuten tulee siitä, että venäläiset talonpojat käyttivät helmitaululla laskiessaan tätä menetelmää kertolaskuun, onhan a · n tulkittavissa a:n n:nneksi ”potenssiksi” yhteenlaskun suhteen. Algoritmi on ilmeisesti hyvin vanha. Satunnaisluvun generointi Satunnaisbittijonoja generoidaan yleisesti käyttäen p:nnen kertaluvun siirtorekisteriä10 modulo 2: ri ≡ a1 ri−1 + a2 ri−2 + · · · + ap ri−p mod 2, missä a1 , a2 , . . . , ap ovat vakiobittejä (0 tai 1, ap = 1). Aluksi tarvitaan tietysti siemenbitit r0 , r1 , . . . , rp−1 . (Tässä lasketaan koko ajan positiivisessa jäännössysteemissä modulo 2 eli biteillä.) Saatava jono rp , rp+1 , . . . ei tietenkään oikeasti ole mitenkään satunnainen, saadaanhan 10
Klassinen viite on G OLOMB , S.W.: Shift Register Sequences. Aegean Park Press (1982)
LUKU 3. KOKONAISLUVUT
36
se täysin deterministisellä menettelyllä ja on periodinen (periodin pituus enintään 2p ). Kun valitaan kertoimet a1 , a2 , . . . , ap−1 sopivasti saadaan jono kuitenkin käyttäytymään monessa mielessä satunnaisesti, periodi on pitkä jne., ks. esimerkiksi K NUTH . Yksinkertaisimmillaan melkein kaikki kertoimet ovat nollia. Tyyppiä ri ≡ ri−q + ri−p mod 2 olevat siirtorekisterit, missä p on alkuluku ja q valitaan sopivasti, tuottavat usein varsin hyviä satunnaisia bittejä. Seuraavassa taulussa on listattuna eräitä valintoja, missä luku q voidaan korvata myös luvulla p − q: p 2 3 5 7 17 31 89 127 521 607
q (myös p − q käy) p 1 1279 1 2281 2 3217 1, 3 4423 3, 5, 6 9689 3, 6, 7, 13 19937 38 23209 1, 7, 15, 30, 63 44497 32, 48, 158, 168 110503 105, 147, 273 132049
q (myös p − q käy) 216, 418 715, 915, 1029 67, 576 271, 369, 370, 649, 1393, 1419, 2098 84, 471, 1836, 2444, 4187 881, 7083, 9842 1530, 6619, 9739 8575, 21034 25230, 53719 7000, 33912, 41469, 52549, 54454
Nämä arvot on löydetty tietokone-etsinnällä.11 Pienet p:n arvot eivät tietenkään ole kovin käyttökelpoisia. Matriisimuodossa siirtorekisteri on seuraavanlainen. Merkitään a1 a2 · · · ap−1 ap ri+p−1 1 0 ··· 0 0 ri+p−2 0 1 ··· 0 0 ri = ja A = . .. .. .. .. .. . . . . . . . . ri 0 0 ··· 1 0 A on ns. siirtorekisterin oheismatriisi. (Ks. Pykälä 9.3.1.) Silloin ri+1 ≡ Ari
mod 2
ja näin ollen ri ≡ Ai r0
mod 2 (i = 0, 1, . . . ).
Matriisipotenssi Ai voidaan laskea nopeasti modulo 2 käyttäen venäläisten talonpoikien algoritmia. Niinpä—ehkä vähän yllättäen—voidaan varsin nopeasti laskea jonoa rp , rp+1 , . . . ”etukäteen” hyvinkin pitkälle. Satunnaisbittijonosta saadaan binääriesityksen kautta satunnaislukuja. Binääriesityksessään n-pituisia satunnaislukuja s0 , s1 , . . . saadaan jakamalla jono peräkkäisiin n bitin lohkoihin ja tulkitsemalla lohkot binääriluvuiksi. Matriisiesityksessä lasketaan An modulo 2 etukäteen, generoidaan jono tj ≡ (An )j r0 mod 2 (j = 0, 1, . . . ) 11
Artikkeliviitteet ovat Z IERLER , N.: On Primitive Trinomials Whose Degree is a Mersenne Exponent. Information and Control 15 (1969), 67–69 ja H ERINGA , J.R. & B LÖTE , H.W.J. & C OMPAGNER , A.: New Primitive Trinomials of Mersenne-Exponent Degrees for Random Number Generation. International Journal of Modern Physics C3 (1992), 561–564.
LUKU 3. KOKONAISLUVUT
37
ja (olettaen, että p ≥ n) lasketaan sj = (2n−1 , 2n−2 , . . . , 2, 1, 0, . . . , 0)tj
(j = 0, 1, . . . ),
missä nollia on lisätty vaakavektoriin p − n kpl. Todettakoon, että vaativiin käyttötarkoituksiin, esimerkiksi kryptologiassa, siirtorekisteripohjaiset satunnaislukugeneraattorit ovat liian heikkoja (liian hyvin ennustettavissa), ks. kurssi Kryptologia.
Luku 4 ALGEBRAA 4.1
Yleistä
Symbolisen laskennan yleinen valmistulkinta on lausekkeiden tulkinta johonkin algebralliseen rakenteeseen liittyväksi, usein tavalla tai toisella polynomiksi. Algebrallisina operaatioina ovat yhteen-, vähennys-, kerto- ja jakolasku, mutta sovellettuina moniin erityyppisiin alkioihin, esimerkiksi kokonais- tai rationaalilukuihin, jäännösluokkiin, polynomeihin, matriiseihin, vektoreihin, funktioihin, potenssisarjoihin, jne. Yhteistä näille on tiettyjen peruslaskusääntöjen käyttö, mutta toisaalta erojakin on, esimerkiksi matriisikertolasku ei ole vaihdannainen, jäännösluokilla ei aina voi jakaa, jne. Erot johtavat siihen, että algebrallisia rakenteita on (käytössäkin) suuri määrä, joista osaan tutustutaan kursseilla Algebra 1&2, Finite Fields, Koodausteoria ja Kryptologia. Symbolisessa laskennassa toisaalta tarvitaan käytäntöä ajatellen enimmäkseen rakenteita, jotka tavalla tai toisella pohjautuvat reaali- tai kompleksilukuihin. Tällaisia ovat erilaiset lukurenkaat ja -kunnat, polynomi- ja potenssisarjarenkaat, rationaalifunktioiden kunnat, funktiokunnat, yms. Algebrallisista struktuureista päästään toisiin erinäisillä muokkausoperaatioilla: Rakennetta voidaan karkeistaa samaistamalla samoin käyttäytyviä alkioita (tekijärenkaat). Rakenteesta voidaan ottaa vain osa unohtamalla muut alkiot (alirenkaat ja -kunnat). Rakennetta voidaan laajentaa ottamalla mukaan uusia alkioita (rengas- ja kuntalajennukset, murtokunnat, polynomirenkaat, rationaalifunktioiden kunnat, formaalisten potenssisarjojen renkaat).
4.2
Renkaat ja kunnat
Joukko R varustettuna binäärisillä laskuoperaatioilla + ja · (joita kutsutaan yhteen- ja kertolaskuksi) on ns. rengas, jos seuraavat laskulait pitävät paikkansa: 1. + on liitännäinen, ts. aina a + (b + c) = (a + b) + c. 2. · on liitännäinen, ts. aina a · (b · c) = (a · b) · c. 3. + on vaihdannainen, ts. aina a + b = b + a. 4. Vasen osittelulaki pätee, ts. aina a · (b + c) = (a · b) + (a · c). 5. Oikea osittelulaki pätee, ts. aina (a + b) · c = (a · c) + (b · c). 6. Joukossa R on ns. nolla-alkio eli nolla 0, jolle pätee a + 0 = a. 7. Jokaisella joukon R alkiolla a on ns. vasta-alkio −a, jolle pätee a + (−a) = 0. 38
LUKU 4. ALGEBRAA
39
Huomaa, että kertolaskulta ei tässä vaadita vaihdannaisuutta. Jos kertolaskukin on vaihdannainen, ts. aina a · b = b · a, niin kyseessä on ns. vaihdannainen rengas (eli kommutatiivinen rengas). Tavalliseen tapaan merkitään tuloa a · b myös ab:llä ja sulkumerkkien vähentämiseksi sovitaan, että kertolasku suoritetaan ennen yhteenlaskua. Koska yhteen- ja kertolasku ovat (yhteis)liitännäisiä, jätetään peräkkäisistä operoinneista sulut pois (ks. Pykälä 1.2). Operaation + ”potenssia” eli ns. monikertaa merkitään tavalliseen tapaan kokonaisluvulla kertomisella, ts. jos k on kokonaisluku, niin a, jos k = 1 0, jos k = 0 · · + a, jos k > 1 a + · ka = k kpl −a, jos k = −1 (−a) + · · · + (−a), jos k < −1. |k| kpl
Samoin määritellään operaation · potenssi: a, jos k = 1 k a = a · · · a, jos k > 1. k kpl
Vähennyslasku määritellään myös tavalliseen tapaan, ts. merkitään a − b = a + (−b). Tällöin merkitään tavalliseen tapaan esimerkiksi −(ab) = −ab, jne. Nolla-alkioita voi olla vain yksi. Jos nimittäin niitä olisi kaksi, merkitään 0 ja 0 , niin 0 = 0 + 0 = 0 + 0 = 0 , eli ne ovatkin samat. Vasta-alkiokin on aina yksikäsitteinen. Jos a:lla olisi kaksi vasta-alkiota −a ja ∼ a, niin −a = (−a) + 0 = (−a) + a + (∼ a) = 0 + (∼ a) =∼ a. Peruslaskusääntöjä käyttäen saadaan lisää sääntöjä, esimerkiksi (totea!) −ab = −(ab) = (−a)b = a(−b) ja
a · 0 = 0 · a = 0.
Huomaa edelleen, että kertolaskulle ei vaadita ykkösalkiota. Jos tällainen ykkösalkio 1 on, ts. aina 1 · a = a · 1 = a, niin sanotaan renkaan olevan ns. ykkösrengas (eli 1-rengas). Potenssimerkintää ajatellen sovitaan tällöin, että a0 = 1. Yleensä (niin tässäkin) oletetaan, että 0 = 1 (muutoinhan rengas on harvinaisen yksinkertainen, eikö vain). On aivan mahdollista, että renkaassa ab = 0, vaikka a, b = 0. Tällaisia alkioita a ja b kutsutaan nollanjakajiksi. Nollanjakajien olemassolo tietää sitä, ettei renkaassa yhtälöistä saa aina supistaa tekijöitä puolittain pois. Itsestään yhtälöstä ab = 0 = 0·b = a·0 ei saa supistaa pois a:ta eikä b:tä, jos a ja b ovat nollanjakajia. Jos vaihdannaisessa 1-renkaassa ei ole nollanjakajia, sitä sanotaan kokonaisalueeksi. Jos 1-renkaassa ab = 1, niin alkioita a ja b kutsutaan yksiköiksi. (Itse asiassa tällöin a on b:n vasen ja b on a:n oikea käänteisalkio.)
LUKU 4. ALGEBRAA
40
Vaikka renkaassa olisi ykkösalkiokin, ei vaadita, että nollasta eroavilla alkioilla olisi käänteisalkio. Jos jokaisella alkiolla a = 0 on käänteisalkio a, ts. a · a = a · a = 1, sanotaan 1-renkaan olevan vinokunta eli jakorengas. Potenssimerkinnässä tällöin merkitään tavalliseen tapaan a, jos k = −1 k a = a · · · a, jos k < −1, |k| kpl
ja erityisesti siis tuttuun tapaan a = a−1 . Huomaa, että vinokunnassa ei voi olla nollanjakajia ja tulomuotoisista yhtälöistä voi supistaa tekijöitä puolittain pois. Uusia laskusääntöjä syntyy entisistä, esimerkiksi (totea!) (ab)−1 = b−1 a−1 . Jakolasku määritellään tavalliseen tapaan vinokunnassa: a/b = ab−1
ja a\b = a−1 b.
Nollalla ei tietenkään saa jakaa! Vinokunta, joka on vaihdannainen rengas, on ns. kunta. Kunnissa ovat voimassa tavalliset luvuille (ja muuttujille ja funktioille) tutut laskusäännöt, joten ne ovat erityisen keskeisessä asemassa symbolisessa analyysissä (ja mm. koodausteoriassa). Kunnassa jakolaskua merkitään myös tavalliseen tapaan, ts. a = ab−1 , b ja sille saadaan tavalliset laskusäännöt, esimerkiksi (totea!) a −1 b
4.3
=
b a
ja
a c ad + bc + = . b d bd
Esimerkkejä renkaista ja kunnista
Kokonaisluvut Z tavallisten laskuoperaatioiden suhteen muodostavat kokonaisalueen, joka ei ole kunta. Yksiköt ovat ±1. Rationaaliluvut Q, reaaliluvut R sekä kompleksiluvut C muodostavat tavallisten laskuoperaatioiden suhteen tutut kunnat, ns. lukukunnat. Kokonaisalkioiset n × n-matriisit (n ≥ 2) muodostavat tavallisten laskuoperaatioiden suhteen 1-renkaan Mn (Z), joka ei ole vaihdannainen ja jossa on nollanjakajia. Yksiköt ovat ne ei-singulääriset matriisit, joiden käänteismatriisi on myös kokonaisalkioinen. Samoin rationaalialkioiset, reaalialkioiset ja kompleksialkioiset n × n-matriisit muodostavat vastaavanlaiset 1-renkaat Mn (Q), Mn (R) ja Mn (C), yksiköinä ei-singulääriset matriisit. Jäännösluokat modulo n muodostavat tavallisten laskuoperaatioiden suhteen vaihdannaisen 1-renkaan Zn , joka ei yleisesti ole kokonaisalue. Jos kuitenkin p on alkuluku, niin Zp on kunta (ns. alkukunta). Kunnilla Zp on tärkeä rooli virheitä korjaavien koodien konstruktiossa, ks. kurssi Koodausteoria. Symbolisen analyysin kannalta tärkeitä renkaita ovat erilaiset polynomirenkaat, kokonais-, rationaali-, reaali- ja kompleksikertoimisten muuttujan x polynomien renkaat Z[x], Q[x], R[x] ja
LUKU 4. ALGEBRAA
41
C[x] sekä vastaavat usean muuttujan polynomirenkaat Z[x1 , x2 , . . . , xn ], jne. Yksiköinä ovat vakiopolynomit (kokonaiskertomisessa tapauksessa vain ±1). Vastaavasti tärkeitä kuntia ovat kuntien (ja kokonaisalueiden) rationaalifunktioiden (polynomien osamäärien) kunnat, mm. Q(x), R(x) ja C(x), sekä myös monen muuttujan rationaalifunktioiden kunnat, R(x1 , . . . , xn ), jne. Merkitään R4 :n luonnollisia kantavektoreita seuraavasti: 0 0 0 1 0 0 1 0 = 1 , = i , = j , = k. 0 1 0 0 1 0 0 0 Kun yhteenlasku on tavallinen vektorien yhteenlasku, skalaarilla kertominen tavallinen vektorin kertominen skalaarilla ja itse vektorien kertolasku määritellään osittelulaeilla sekä taululla · 1 i j k
1 i j k 1 i j k i −1 k −j j −k −1 i k j −i −1
saadaan ns. kvaternionirengas. Se on rakenteeltaan vinokunta. Kvaternioneilla on tärkeä rooli eräissä kolmiulotteisten rotaatioiden mallinnustavoissa, mm. tietokonegrafiikassa.
4.4
Alirenkaat ja -kunnat, laajennukset, ihanteet, tekijärenkaat, murtokunnat
Jos renkaan R osajoukko A on myös itsessään rengas, kutsutaan sitä R:n alirenkaaksi. Tärkeää on silloin, että jos a ja b ovat A:ssa, niin siellä ovat myös a + b, ab ja −a. Esimerkiksi parilliset kokonaisluvut muodostavat Z:n alirenkaan (mutta parittomat eivät). Vastaavasti määritellään alikunta, jolloin vielä alikunnan nollasta eroavan alkion käänteisalkionkin pitää olla alikunnassa. Esimerkiksi Q on R:n alikunta. Toisinpäin asiaa ajatellen, jos rengas R on renkaan S alirengas, sanotaan S:n olevan R:n rengaslaajennus eli ylirengas. Vastaavasti määritellään kuntalaajennus (eli ylikunta). Tärkeä alirengastyyppi on ns. ihanne. Renkaan R alirengas I on ihanne eli ideaali, jos aina kun a on I:n alkio ja r on R:n alkio, niin ra ja ar ovat I:ssä. . Nimi tulee siitä, että tällaisia alirenkaita sanottiin ihanteellisiksi, koska niitä käyttäen renkaan rakennetta voidaan karkeistaa eli muodostaa tekijärenkaita. Renkaan rakenteen karkeistaminen tapahtuu hyvin samaan tapaan kuin kokonaislukujen kongruenssilaskennassa. Siellähän kokonaislukujen renkaan rakennetta karkeistetaan ottamalla kokonaisluvusta huomioon vain sen jäännös modulo m. Itse asiassa m:llä jaolliset kokonaisluvut muodostavatkin Z:n ihanteen. Jos nyt I on renkaan R ihanne, niin sanotaan, että R:n alkiot a ja b ovat kongruentit modulo I, merkitään a≡b
mod I,
mikäli b − a on I:ssä. Karkeistuksessa keskenään kongruentit alkiot samaistetaan. Tuloksena saatua rengasta kutsutaan tekijärenkaaksi ja merkitään R/I:llä. Merkitään aI :llä kaikkien niiden renkaan R alkioiden joukkoa, jotka ovat kongruentteja a:n kanssa modulo I, eli a:n edustamaa tekijärenkaan R/I alkiota, ns. jäännösluokkaa, eli niiden alkioiden joukkoa, jotka karkeistuksessa samaistuvat a:n kanssa. Todetaan seuraavat ominaisuudet:
LUKU 4. ALGEBRAA
42
(1) aI :n alkiot samaistuvat myös keskenään eli ovat kongruentteja keskenään modulo I, sillä jos a ≡ b mod I ja a ≡ c mod I, niin b − a on I:ssä ja c − a on I:ssä, jolloin myös (c − a) − (b − a) = c − b on I:ssä (I on alirengas), ts. b ≡ c mod I. (2) Jos a ≡ b mod I, ts. b − a on I:ssä, niin a − b = −(b − a) = (−b) − (−a) on sekin I:ssä eli b ≡ a mod I ja −a ≡ −b mod I. (3) Jos a≡b
mod I
ja
c ≡ d mod I,
niin (b + d) − (a + c) = (b − a) + (d − c) ja bd − ac = (b − a)d − a(d − c) ovat I:ssä (I on ihanne), ts. a + c ≡ b + d mod I
ja
ac ≡ bd
mod I.
Tämä osoittaa, että tekijärenkaan alkioilla voidaan suorittaa yhteen-, vähennys- ja kertolasku ”edustajien välityksellä” lähtien renkaan R laskuoperaatioista. Tekijärenkaan nolla-alkio on 0I = I. Kokonaisalue on paljolti kuntaa muistuttava, ainoa puute on (mahdollinen) käänteisalkioiden puuttuminen. Näin tulee mieleen, että kokonaisalueelle voisi olla rengaslaajennus, joka on kunta. Näin onkin, jokainen kokonaisalue voidaan laajentaa kunnaksi. Pienintä kuntaa, joka näin laajentaa kokonaisaluetta D, kutsutaan sen murtokunnaksi eli osamääräkunnaksi, merkitään Q(D). Esimerkiksi kokonaisalueen Z murtokunta on tietysti Q, mutta myös R on sen laajennusrengas. Kokonaisalueen D murtokunnan konstruoimiseksi muodostetaan ensin parit (a, b), missä a ja b ovat D:n alkioita ja b = 0, ja samaistetaan sitten sellaiset parit (a, b) ja (c, d), joille ad = bc. Näille pareille määritellään yhteen- ja kertolaskut seuraavalla tavalla: (a, b) + (c, d) = (ad + bc, bd) ja
(a, b) · (c, d) = (ac, bd).
Tämä määrittelee laskuoperaatiot hyvin. Jos nimittäin parit (a, b) ja (a , b ) samaistetaan ja samoin parit (c, d) ja (c , d ), niin ab = ba ja cd = dc . Silloin (ad + bc)b d = (a d + b c )bd
ja
acb d = a c bd,
joten myös parit (ad + bc, bd) ja (a d + b c , b d ) pitää samaistaa ja samoin parit (ac, bd) sekä (a c , b d ). Nyt nolla-alkio on (0, 1) (ja siihen samaistuvat parit (0, b), missä b = 0) ja ykkösalkio (1, 1) (ja siihen samaistuvat parit (a, a), missä a = 0), alkion (a, b) vasta-alkio on (−a, b) (ja siihen samaistuvat parit). Tuloksena on itse asiassa kunta, kuten helposti voidaan todeta, sillä parin
LUKU 4. ALGEBRAA
43
(a, b), missä a, b = 0, käänteisalkio on (b, a). Tämä kunta on D:n murtokunta1 Q(D), kunhan ajatellaan pari (a, 1) (ja siihen samaistuvat parit) D:n alkioksi a. Luonnollisesti parimerkinnän asemasta käytetään yleensä tuttua jakoviivamerkintää eli kirjoitetaan ab tai a/b tai b\a eikä (a, b). Myös kirjoitetaan a/1:n sijasta a ja 1/b:n sijasta b−1 , jne. Huomautus. Tämä konstruktio on itse asiassa täysin formaalinen, ts. mitään murtokuntaa ei tarvitse ”etukäteen” olla odottamassa. Eräänlainen ”bootstrap-operaatio” siis. Symbolisessa laskennassa voidaan näin periaatteessa aina puhtaan symbolisesti muodostaa murtokunta. Itse asiassa symbolisessa laskennassa käyttöön otetut uudet käsitteet pitääkin määritellä vanhojen avulla ja varsinaisia primitiivejä on vain vähän. Kuntien polynomirenkaat ovat kokonaisalueita, kuten on helppo nähdä. Rationaalifunktioiden kunnat ovat näiden murtokuntia, siis esimerkiksi R(x, y) on R[x, y]:n murtokunta, jne. Yleisestikin kokonaisalueen D polynomirengas on kokonaisalue ja sen murtokunta Q(D[x]) voidaan samaistaa kuntiin ja D(x) ja Q(D)(x), siis esimerkiksi Q(Z[x]) = Z(x) = Q(x). Toinen tapa saada aikaan kuntia on karkeistaa kokonaisalueiden rakennetta ihanteita käyttäen. Tämä onnistuu vain tietynlaisille ihanteille. Esimerkiksi Zp on kunta (alkukunta), jos p on alkuluku, mutta vaikkapa Z6 ei ole kunta. Tähän liittyen, eräs tapa saada aikaan uusia kuntia on laajentaa kunta ottamalla mukaan sen polynomirenkaan jonkin polynomin juuret. Tämä tapahtuu yksinkertaisesti karkeistamalla polynomirengasta samaistamalla ko. polynomi nollapolynomiin! Tästä lisää myöhemmin. Tällä tavoin muodostetaan alkukunnista ns. äärelliset kunnat, jotka ovat tärkeitä vaikkapa koodausteoriassa.
4.5
Tekijät, s.y.t. ja p.y.j. kokonaisalueissa
Kokonaislukujen renkaassa (joka on kokonaisalue) lukujen jaollisuus, tekijöihinjako, alkuluvut, jne. ovat keskeisiä. Renkaissa vastaavat käsitteet muodostavat yleisesti ottaen jonkin verran sotkuisen osan teoriaa (ks. kurssi Algebra 1), mutta kokonaisalueille saadaan selkeämmät tulokset. Niinpä tässä pykälässä rajoitutaankin (mielivaltaiseen) kokonaisalueeseen D, vaikka käsitteet olisivat järkeviä muillekin renkaille. Jos D:n alkio a voidaan kirjoittaa muotoon a = bc, niin b on a:n tekijä, merkitään b | a (eli b jakaa a:n eli a on b:n monikerta). Huomaa, että yksikkö jakaa minkä tahansa alkion ja kaikki alkiot jakavat nolla-alkion. D:n alkio d on alkioiden a ja b suurin yhteinen tekijä (s.y.t.), merkitään d = syt(a, b), jos d jakaa a:n ja b:n ja toisaalta d on jokaisen sellaisen alkion monikerta, joka jakaa sekä a:n että b:n. Edelleen D:n alkio m on alkioiden a ja b pienin yhteinen jaettava (p.y.j.), merkitään m = pyj(a, b), jos sekä a että b jakavat m:n ja toisaalta m jakaa jokaisen alkion, joka on sekä a:n että b:n monikerta. Nämä määritelmät kävisivät myös kokonaisluvuille, jos sovitaan, että syt(0, 0) = 0 ja pyj(0, b) = 0. (Huomaa kuitenkin, että alkioilla ei ole ”suuruutta” kuten luvuilla, vaikka puhutaan ”suurimmasta” ja ”pienimmästä”.) S.y.t. ja p.y.j. eivät muuten ole olemassa kaikissa kokonaisalueissa. Alkioiden a ja b sanotaan olevan liitännäisiä, jos ne jakavat toinen toisensa. Yksiköt ovat näin ollen keskenään liitännäisiä. Samoin alkioiden a ja b suurimmat yhteiset tekijät (joita voi siis olla useita) ovat keskenään liitännäisiä, kuten ovat pienimmät yhteiset jaettavatkin. Lause 4.1. Kokonaisalueen alkiot a ja b ovat liitännäiset täsmälleen silloin, kun voidaan kirjoittaa a = ub, missä u on yksikkö. 1
Asia vaan ei ole ihan helppo tarkasti näyttää, ks. kurssi Algebra 1. Murtokunnanhan piti olla pienin laajennuskunta.
LUKU 4. ALGEBRAA
44
Todistus. Tapaus a = 0 on helppo. Muutoin, jos a ja b ovat liitännäiset, niin a = bc ja b = ac . Siispä a = ac c ja 1 = c c (kokonaisalueessa kun saa supistaa). c on näin ollen yksikkö. Jos a = ub, missä u on yksikkö, niin b jakaa a:n ja toisaalta jollekin alkiolle v pitää olla vu = 1. Siispä av = ubv = b eli a jakaa b:n. Kokonaisluvulle k = 0 ainoa sen kanssa liitännäinen luku on −k ja monesti sovitaan, että näistä liitännäisistä luvuista ±k valitaan edustajaksi positiivinen luku (esimerkiksi suurin yhteinen tekijä on positiivinen). Yleiselle kokonaisalueelle tällaista sopimusta ei voida tehdä (positiivisuutta ei ole määritelty). Usein kuitenkin valitaan jollain kriteerillä keskenään liitännäisten alkioiden joukosta yksi, ns. yksikkönormaali. Kunnan yksikkönormaalit ovat tavan mukaan 0 ja 1, mutta muille kokonaisalueille valinta on jonkin verran mielivaltainen. Yksiköiden yksikkönormaali on kuitenkin yleensä 1. Alkiota a vastaavaa yksikkönormaalia merkitään n(a):lla, ns. a:n normaaliosa, jolloin voidaan kirjoittaa a = u(a)n(a), missä yksikkö u(a) on ns. a:n yksikköosa. Lisäksi vaaditaan, että normaaliosa on on multiplikatiivinen, ts. n(ab) = n(a)n(b) (mistä tietysti seuraa, että myös yksikköosa on multiplikatiivinen). Huomautus. Tästä lähin sovitaan, että valitaan alkioiden a ja b suurimmista yhteisistä tekijöistä se, joka on yksikkönormaali, samoin pienimmistä yhteisistä jaettavista, ellei nyt sitten toisin sanota. Useamman kuin kahden alkion s.y.t. ja p.y.j. määritellään yleistäen kahden alkion tapauksen määritelmät: d = syt(a1 , a2 , . . . , aN ), jos d jakaa alkiot a1 , a2 , . . . , aN ja toisaalta d on jokaisen sellaisen alkion monikerta, joka jakaa alkiot a1 , a2 , . . . , aN . m = pyj(a1 , a2 , . . . , aN ), jos alkiot a1 , a2 , . . . , aN jakavat m:n ja toisaalta m on jokaisen sellaisen alkion tekijä, jonka alkiot a1 , a2 , . . . , aN jakavat. Kuten kokonaisluvuillekin, useamman kuin kahden alkion s.y.t. ja p.y.j. ovat olemassa ja voidaan laskea, kunhan vain kahden alkion s.y.t. on olemassa ja laskettavissa. Lause 4.2.
syt(a1 , a2 , . . . , aN ) = syt(a1 , syt(a2 , . . . , aN )) = syt(a1 , syt(a2 , syt(a3 , . . . , syt(aN −1 , aN ) · · · ))) pyj(a1 , a2 , . . . , aN ) = pyj(a1 , pyj(a2 , . . . , aN )) = pyj(a1 , pyj(a2 , pyj(a3 , . . . , pyj(aN −1 , aN ) · · · )))
Todistus. Jos merkitään d = syt(a1 , a2 , . . . , aN ) ja d = syt(a2 , . . . , aN ), niin d jakaa a1 :n sekä alkiot a2 , . . . , aN , ja siis myös d :n. Näin ollen d jakaa syt(a1 , d ):n. Toisaalta syt(a1 , d ) jakaa a1 :n sekä d :n, ja siis myös alkiot a2 , . . . , aN . Näin ollen syt(a1 , d ) jakaa d:n. d ja syt(a1 , d ) ovat siis liitännäiset ja (yksikkönormaalimuotoisina) samat. P.y.j.:tä koskeva kaava todistetaan aivan samoin. Toiset yhtälöt saadaan toistamalla kaavaa. P.y.j.:n ja s.y.t.:n yhteyttä koskevan tuloksen todistus ei menekään samalla tavoin kuin Lauseen 3.10 todistus, sillä yleisesti yksikäsitteistä tekijöihinjakoa ei ole kokonaisalueissa, vaikka s.y.t. olisikin olemassa! Todistus onkin näin vaikeampi. Lause 4.3.
pyj(a, b)syt(a, b) = n(ab)
LUKU 4. ALGEBRAA
45
Todistus. Asia on selvä, jos a = 0 tai b = 0, joten oletetaan, että a, b = 0. Merkitään d = syt(a, b) (yksikkönormaali) ja kirjoitetaan a = da sekä b = db . Silloin (multiplikatiivisuus) n(ab) = n(a b d2 ) = n(a b )d2 . Pitäisi näyttää, että n(a b )d on pyj(a, b). Koska a b d = a b = ab , on a b d sekä a:n että b:n monikerta. Otetaan sitten mielivaltainen a:n ja b:n yhteinen monikerta c ja kirjoitetaan c = ra sekä näytetään, että a b d jakaa c:n. Jotta päästään eteenpäin, todetaan ensin, että syt(a , b ) = 1 (siis yksikkönormaalimuotoisena). Jos nimittäin merkitään d = syt(a , b ), niin d jakaa sekä a :n että b :n ja siitä seuraa, että dd jakaa sekä a:n että b:n. Mutta silloin dd jakaa d:n, ts. d = dd u eli (supistus) 1 = d u ja d on yksikkö. Seuraavaksi todetaan, että syt(rda , rdb ) eli syt(ra, rb) eli syt(c, rb) on n(rd). Jos nimittäin merkitään e = syt(rda , rdb ), niin ilmeisesti rd jakaa e:n, ts. e = rds. Toisaalta e eli rds jakaa rda :n ja rdb :n, ts. rda = vrds ja rdb = wrds, ja (supistamalla rd pois) a = vs ja b = ws. s siis jakaa sekä a :n että b :n ja myös 1:n. Siispä s on yksikkö ja (yksikkönormaalina) syt(rda , rdb ) = n(rd). Mutta nyt b jakaa sekä rb:n että c:n, joten se jakaa myös niiden s.y.t.:n eli n(rd):n ja edelleen rd:n, ts. rd = tb. Niinpä c = ra = rda = tba = ta b d on jaollinen a b d:llä. Kaiken kaikkiaan päätellään, että yksikkönormaalina pyj(a, b) = n(a b )syt(a, b). Näiden lauseiden merkitys symbolisen laskennan kannalta on, että riittää etsiä menettely, jolla saadaan aikaan kahden alkion s.y.t.. Siitä sitten saadaan niin mielivaltaisen monen alkion s.y.t.:t kuin p.y.j.:tkin.
4.6
UFD, PID ja ED
Kokonaislukujen kokonaisalueessa pätee niin yksikäsitteinen tekijöihinjako kuin Bezout’n lausekin ja Eukleideen algoritmi on käytettävissä. Kokonaisalueissa ei näin valitettavasti yleisesti ole. Niinpä ne luokitellaankin sen mukaan mitä ym. ominaisuuksista on käytettävissä: Kokonaisalue, jossa on olemassa yksikäsitteinen tekijöihinjako, on ns. yksikäsitteisen tekijöihinjaon alue eli UFD2 . Kokonaisalue, jossa Bezout’n lause pätee, on ns. pääihannealue eli PID2 . Kokonaisalue, jossa on Eukleideen algoritmi, on ns. Eukleideen alue eli ED2 . Katsotaan kutakin näistä kokonaisaluetyypeistä tarkemmin. UFD Kokonaisalueen alkio p on ns. alkualkio, jos • p ei ole yksikkö ja • kirjoitettaessa p tulomuotoon p = ab aina toinen alkioista a tai b on yksikkö. 2
”UFD” = ”unique factorization domain” ”PID” = ”principal ideal domain” (Oudon nimen perustelu löytyy kurssilta Algebra 1.) ”ED” = ”Euclidean domain”
LUKU 4. ALGEBRAA
46
(Vrt. alkuluvun määritelmä.) Ilmeisesti jos p on alkualkio, ovat sitä myös kaikki sen kanssa liitännäiset alkiot. Jotta päästäisiin eroon turhista vain näennäisesti erilaisista alkualkioista, sovitaan, että ellei toisin sanota, alkualkio on yksikkönormaali. (Samoin kokonaisluvuille sovittiin, että alkuluvut ovat positiivisia.) Kokonaisalue on UFD, jos sen jokaisen alkion a, joka ei ole nolla, normaaliosa voidaan yksikäsitteisesti kirjoittaa alkualkioiden tuloksi (järjestystä lukuunottamatta; tulo on tyhjä, jos a on yksikkö): n(a) = pi11 · · · piMM ja a = u(a)pi11 · · · piMM , missä p1 , . . . , pM ovat eri alkualkioita. Kuten Pykälässä 3.3, todetaan nyt, että jos alkioiden a1 , a2 , . . . , aN tekijöihinjaot ovat i
i
aj = u(aj )p1j1 · · · pMjM
(j = 1, 2, . . . , N ),
missä sovitaan, että jik = 0, mikäli alkualkio pk ei ole ai :n alkutekijä, niin min{i11 ,i21 ...,iN 1 }
· · · pM
max{i11 ,i21 ...,iN 1 }
· · · pM
syt(a1 , a2 , . . . , aN ) = p1 ja
pyj(a1 , a2 , . . . , aN ) = p1
min{i1M ,i2M ...,iN M }
max{i1M ,i2M ...,iN M }
.
UFD:ssä siis s.y.t. ja p.y.j. ovat olemassa ja laskettavissa, jos vain alkioiden tekijöihinjaot saadaan tehdyksi. PID Kokonaisalue on PID, jos alkioiden a1 , a2 , . . . , aN s.y.t. on olemassa ja kirjoitettavissa Bezout’n muotoon syt(a1 , a2 , . . . , aN ) = c1 a1 + c2 a2 + · · · + cN aN . Voidaan näyttää, että PID on aina myös UFD, mutta tämä ei ole helppoa (ks. kurssi Algebra 1). Kokonaiskertoimisten polynomien rengas Z[x] on esimerkki UFD:stä, joka ei ole PID: syt(x + 1, x2 ) = 1, mutta sitä ei voida esittää Bezout’n muodossa. ED Kokonaisalue E on ED, jos sen alkioille (nollaa lukuunottamatta) on määritelty ns. Eukleideen arvotus δ, joka käyttäytyy seuraavasti: 1. δ(a) on luonnollinen luku. 2. δ(ab) ≥ δ(a), kun b = 0. 3. Jos a sekä b ovat E:n alkioita ja b = 0, niin on olemassa sellaiset alkiot q (osamäärä) sekä r (jakojäännös), että a voidaan kirjoittaa muotoon a = qb + r, missä joko r = 0 tai sitten δ(r) < δ(b). Kokonaislukujen Eukleideen arvotus on tietysti itseisarvo. Huomaa, miten Eukleideen arvotus sallii jakolaskun E:ssä, aivan samassa mielessä kuin kokonaisluvuille Pykälässä 3.1. Tästä on se seuraus, että ED:ssä yleistetty Eukleideen algoritmi on käytössä ja Bezout’n lause pätee. ED on siis aina PID. Osamäärän ja jakojäännöksen ei tarvitse kuitenkaan olla yksikäsitteisiä. Huomautus. Kirjallisuudessa on useita erilaisia Eukleideen arvotuksen määritelmiä, käytännössä ne johtavat samaan tulokseen.
Luku 5 POLYNOMIT 5.1
Yhden muuttujan polynomit
Peruskursseilla polynomit ovat funktioita. Algebrassa ne voidaan kyllä tarvittaessa ajatella funktioiksikin (ja niin tehdäänkin), mutta varsinaisesti polynomi on formaalisesti äärellinen jono renkaan alkioita (ns. kertoimet) a0 , a1 , . . . , an , joista viimeinen, ns. johtava kerroin, on = 0. (Oikeastaan kyseessä on lista, ks. Pykälä 1.4.) Jonon pituus vähennettynä yhdellä eli n on ns. polynomin aste. Perinteisesti polynomit esitetään kuitenkin käyttäen jotain (apu)muuttujaa x tutussa muodossa a0 + a1 x + · · · + an xn = p(x) ja astetta merkitään deg(p(x)):llä. an xn on ns. johtava termi. Myös tyhjä jono otetaan mukaan ja sitä kutsutaan nollapolynomiksi, merkitään 0. Polynomeja, joiden aste on nolla, sanotaan vakiopolynomeiksi ja niitä merkitään renkaan alkiolla. Itse asiassa ne samaistetaan renkaan alkioiksi eli polynomirengas on aina myös laajennusrengas. (Nollapolynomi samaistetaan renkaan nollaan.) Nollapolynomin asteeksi sovitaan −1 (usein myös −∞). Jotteivat merkinnät menisi liian mutkikkaiksi, sovitaan että jos p(x) = a0 + a1 x + · · · + an xn , niin an+1 = an+2 = · · · = 0 eli jatketaan jonoa nollilla tarvittaessa. (Toisinaan pitää myös sopia, että a−1 = a−2 = · · · = 0.) Kaikkien renkaan R polynomien joukkoa merkitään R[x]:llä, ns. R:n polynomirengas. (Tässä x tarkoittaa vain, että polynomit esitetään muuttujaa x käyttäen.) Kyseessä on todella rengas, kun polynomien yhteen- ja kertolasku määritellään tuttuun tapaan: Jos p(x) = a0 + a1 x + · · · + an xn ja q(x) = b0 + b1 x + · · · + bm xm ja n ≥ m, niin p(x) + q(x) = (a0 + b0 ) + (a1 + b1 )x + · · · + (an + bn )xn , −p(x) = −a0 + (−a1 )x + · · · + (−an )xn = −a0 − a1 x − · · · − an xn ja p(x)q(x) = c0 + c1 x + · · · + cn+m xn+m , missä ck =
ai bj
(k = 0, 1, . . . , n + m).
i+j=k
Erityisesti p(x) + 0 = p(x) ja
p(x) · 0 = 0 · p(x) = 0.
Seuraavat tosiasiat on varsin helppo todeta: 47
LUKU 5. POLYNOMIT
48
(1) Jos R on vaihdannainen, niin samoin on R[x]. (2) Jos R on 1-rengas, niin samoin on R[x]. (3) Jos R on kokonaisalue, niin samoin on R[x]. Tällöin pätee myös tuttu astelukukaava deg(p(x)q(x)) = deg(p(x)) + deg(q(x)). (4) deg(p(x) + q(x)) ≤ max(deg(p(x)), deg(q(x))) ja yhtäläisyys pätee, jos deg(p(x)) = deg(q(x)) (ja tietysti usein muulloinkin). (5) Jos D on kokonaisalue, niin D[x]:n yksiköt ovat D:n yksiköt. (6) Jos S on R:n rengaslaajennus, niin S[x] on R[x]:n rengaslaajennus. Erityisesti jos D on kokonaisalue, niin Q(D)[x] on D[x]:n rengaslaajennus. (7) Jos D on kokonaisalue, niin D:n alkualkiot ovat myös D[x]:n alkualkioita. D[x]:n muita alkualkioita kutsutaan jaottomiksi polynomeiksi. (8) Jos an on polynomin p(x) johtava kerroin kokonaisalueen polynomirenkaassa, niin p(x):n yksikkönormaali on n(p(x)) = u(an )−1 p(x), jonka johtava kerroin on n(an ). Erityisesti kunnan polynomirenkaan yksikkönormaalin johtava kerroin on aina 1, ts. kyseessä on ns. pääpolynomi. Erityisen mukavia ovat kuntien polynomirenkaat, sillä Lause 5.1. Jos F on kunta, niin F [x] on ED, jonka Eukleideen arvotus on aste. F [x]:ssä on siis Eukleideen algoritmi käytössä. Todistus. Tavallinen koulussa opittu polynomien pitkäjako riittää. Kunnan polynomirenkaassa on siis jakolasku. Koulussa opittu pitkäjako näyttää toisaalta myös, että kokonaisalueen D polynomirenkaassa D[x] voidaan jakaa polynomilla, jonka johtava kerroin on 1 (tai yksikkö) eli pääpolynomilla. Koska muilla polynomeilla ei sitten ehkä voidakaan jakaa, ei D[x] tällöin ole (välttämättä) ED. Huomattavasti vaikeampi on todistaa Lause 5.2. Jos R on UFD, niin samoin on R[x]. Todistus. Ks. kurssi Algebra 1. Eräs symbolisen laskennan perustehtävistä on testata, onko annettu polynomi jaoton vai ei, ja myös jakaa jaolliset polynomit tekijöihin. Kyseessä on tällöin UFD:n tai kunnan polynomirenkaan polynomi. Jos kokonaisalueessa s.y.t. on olemassa, niin voidaan määritellä sen polynomirenkaan polynomin p(x) = a0 + a1 x + · · · + an xn (ei nollapolynomin) ns. sisältö cont(p(x)) = syt(a0 , a1 , . . . , an ). Polynomia, jonka sisältö on yksikkö, kutsutaan primitiiviseksi. Ottamalla sisältö tekijäksi kertoimista polynomi p(x) voidaan kirjoittaa muotoon p(x) = cont(p(x))q(x).
LUKU 5. POLYNOMIT
49
Kuten Lauseen 4.3 todistuksessa, voidaan näyttää, että q(x) on tällöin primitiivinen, ts. sen kerrointen s.y.t. on yksikkö. Monesti laskuissa jaetaan polynomien sisältö pois, jotteivat kertoimet kasvaisi suuriksi. Symbolisia laskuja ajatellen on tärkeää huomata, että polynomi on täysin formaalinen konstruktio, ja jos kerroinrenkaassa R voidaan laskea symbolisesti, niin samoin voidaan laskea R[x]:ssä.
5.2
Polynomien juuret
Polynomien juurten symbolista käsittelyä tarvitaan usein, esimerkiksi silloin kun muodostetaan osamurtokehitelmiä (rationaalifunktioiden symbolinen integrointi, symbolinen käänteinen Laplacen muunnos, jne.). Osa polynomin juurista voi olla kerroinrenkaassa, osa joudutaan ottamaan mukaan sopivalla laajennuksella (ns. algebrallinen laajennus, ks. Pykälä 5.3). Juuria ajatellen polynomirenkaan R[x] polynomia p(x) = a0 + a1 x + · · · + an xn ajatellaankin funktiona, kuten peruskursseilla. Alkio b on polynomin p(x) juuri, jos p(b) = a0 + a1 b + · · · + an bn = 0. Nollanjakajien olemassaolo tekee juurirakenteen oudoksi, joten jatkossa oletetaan, että R on kokonaisalue D. Jos x − b on D[x]:n polynomin p(x) tekijä, niin selvästi b on p(x):n juuri. Myös käänteinen pätee: Lause 5.3. Jos b on D[x]:n polynomin p(x) juuri, niin x − b jakaa p(x):n. Todistus. Jaetaan p(x) pääpolynomilla x − b: p(x) = q(x)(x − b) + r(x), missä r(x) = 0 tai r(x)on vakiopolynomi. (Kuten edellä todettiin, pääpolynomilla voidaan jakaa kokonaisalueen polynomirenkaassa.) Sijoitetaan tähän x = b: 0 = p(b) = (b − b)q(b) + r(b) = r(b). Koska r(x) on joko nolla tai vakio, sen on siis oltava nolla ja x − b jakaa p(x):n. Juuri voi olla moninkertainen: b on polynomin p(x) m-kertainen juuri, jos (x − b)m jakaa p(x):n, mutta (x − b)m+1 ei enää jaa sitä. m on ns. juuren kertaluku. Lause 5.4. Jos b on D[x]:n polynomin p(x) juuri ja p(x) voidaan kirjoittaa tuloksi p(x) = s(x)t(x), niin b on jommankumman polynomin s(x) tai t(x) juuri (ehkä molempienkin). Todistus. Koska 0 = p(b) = s(b)t(b) ja nollanjakajia ei D:ssä ole, on joko s(b) = 0 tai t(b) = 0.
LUKU 5. POLYNOMIT
50
Seuraus. D[x]:n polynomilla, jonka aste on d ≥ 0, on enintään d eri juurta D:ssä. Myös jos monikerrat otetaan mukaan, niin juuria on enintään d kpl. 1 Todistus. Jos D[x]:n polynomilla p(x) on D:ssä n eri juurta b1 , b2 , . . . , bn , joiden kertaluvut ovat vastaavasti m1 , m2 , . . . , mn , niin (x − b1 )m1 jakaa p(x):n eli p(x) = (x − b1 )m1 p1 (x). Mutta silloin b2 on p1 (x):n juuri, joten (x − b2 )m2 jakaa p1 (x):n eli p1 (x) = (x − b2 )m2 p2 (x). Jne. Lopulta nähdään, että p(x) = (x − b1 )m1 (x − b2 )m2 · · · (x − bn )mn pn (x). Siispä d = deg(p(x)) ≥ n ja m1 + m2 + · · · + mn ≤ d. Seuraus. Jos D[x]:n polynomit p(x) ja q(x), joiden aste on enintään n, saavat n+1 eri pisteessä a1 , a2 , . . . , an+1 samat arvot, niin polynomit ovat samat. (Polynomin kertoimien laskeminen sen pisteissä a1 , a2 , . . . , an+1 saamista arvoista on ns. interpolaatiotehtävä, ks. Pykälä 5.7.) Todistus. Merkitään s(x) = p(x) − q(x), jolloin myös s(x):n aste on enintään n. Ilmeisestikin a1 , a2 , . . . , an+1 ovat s(x):n eri juuria, joten s(x):n on oltava nollapolynomi. Jos polynomin p(x) kaikki juuret ovat D:ssä, se voidaan kirjoittaa muotoon p(x) = a(x − b1 )m1 (x − b2 )m2 · · · (x − bn )mn missä a on johtava kerroin. Käänteisesti ajatellen polynomi voidaan ilmoittaa antamalla sen juuret kertalukuineen (sekä johtava kerroin). Jos p(x) = a(x − b1 )(x − b2 ) · · · (x − bn ), missä kukin juuri nyt esiintyy kertalukunsa osoittaman määrän kertoja, niin kertomalla auki tulo havaitaan, että p(x) = a0 + a1 x + · · · + an xn , missä an = a an−1
(1 termi), n = −a bi (n termiä), i=1
an−2 = a
bi b j
n
(
2
termiä),
1≤i 0 tai m > 0. Alalohkossa on n riviä ja ylälohkossa m riviä. (Jos n = 0, jää matriisista alalohko kokonaan pois, ja jos m = 0, niin ylälohko jää pois.) Resultantti on Sylvesterin matriisin determinantti res(f (x), g(x)) = |Sylvester(f (x), g(x))|. Jos n = m = 0 ja kumpikaan polynomeista ei ole nollapolynomi, niin resultantin arvoksi sovitaan 1. Jos taas ainakin toinen polynomeista on nollapolynomi, sovitaan resultantin arvoksi 0. Kammottavasta näöstään huolimatta resultantti on yhtä helppo laskea kuin s.y.t. ja liittyykin polynomien yhteisiin tekijöihin. Lause 7.2. Resultantilla on Bezout’n muoto res(f (x), g(x)) = c1 (x)f (x) + c2 (x)g(x). Todistus. Asia on selvä, jos ainakin toinen polynomeista on nollapolynomi. Jos esimerkiksi f (x) on nollapolynomi, valitaan vain c1 (x) = c2 (x) = 0. Myös tapaukset, joissa (ainakin) toinen polynomeista on vakiopolynomi toisen ollessa = 0, ovat selviä. Jos esimerkiksi f (x) = a0 = 0 (vakio) ja g(x) = 0, niin a0 0 · · · 0 0 a0 · · · 0 m res(a0 , g(x)) = .. .. . . . = a0 . . . .. 0 0 · · · a0 ja valitaan c1 (x) = am−1 ja c2 (x) = 0. Determinantin ominaisuuksista seuraa myös, että 0 res(f (x), g(x)) = (−1)nm res(g(x), f (x)), sillä jälkimmäinen resultantti saadaan edellisestä tekemällä nm rivinvaihtoa ja jokainen niistä vaihtaa determinantin merkin. Bezout’n muodon laskee yleisesti seuraava versio Eukleideen algoritmista, missä merkitään RES(f (x), g(x)) = (res(f (x), g(x)), c1 (x), c2 (x)): Eukleideen algoritmi polynomien resultantille: 1. Jos f (x) on nollapolynomi, tulostetaan RES(f (x), g(x)) = (0, 0, 0) ja lopetetaan. Jos f (x) ei ole nollapolynomi, mutta g(x) on, tulostetaan RES(f (x), g(x)) = (0, 0, 0) ja lopetetaan. 2. Asetetaan n ← deg(f (x)) ja m ← deg(g(x)). 3. Jos n > m, lasketaan RES(g(x), f (x)) = (R, e1 (x), e2 (x)), tulostetaan RES(f (x), g(x)) = ((−1)nm R, (−1)nm e2 (x), (−1)nm e1 (x)) ja lopetetaan. 4. Asetetaan a ← f (x):n johtava kerroin. 5. Jos n = 0, tulostetaan RES(f (x), g(x)) = (am , am−1 , 0) ja lopetetaan. 6. Jaetaan g(x) f (x):llä: g(x) = q(x)f (x) + r(x) ,
missä r(x) = 0 tai deg(r(x)) < n.
Asetetaan k ← deg(r(x)). (Sovitaan vaikkapa, että deg(0) = −1.)
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
81
7. Lasketaan RES(f (x), r(x)) = (R, e1 (x), e2 (x)), tulostetaan RES(f (x), g(x)) = (am−k R, am−k (e1 (x) − e2 (x)q(x)), am−k e2 (x)) ja lopetetaan. Huomaa, että kohdassa 7. todellakin res(f (x), g(x)) = am−k res(f (x), r(x)), sillä deg(q(x)) = m − n ja xi g(x) = q(x)xi f (x) + xi r(x) (i = 0, 1, . . . , n − 1). Jos r(x) on nollapolynomi, ovat ilmeisesti matriisin Sylvester(f (x), g(x)) rivit näin lineaarisesti riippuvia ja siten res(f (x), g(x)) = 0 (asteluvun valinta −1:ksi ei silloin vaikuta mitään). Jos taas r(x) ei ole nollapolynomi, matriisista Sylvester(f (x), g(x)) saadaan muotoa a ∗ ··· ∗ 0 a ··· ∗ .. .. . . .. . . . . 0 0 ··· a O Sylvester(f (x), r(x))
∗
oleva matriisi sellaisilla rivioperaatioilla, jotka eivät muuta sen determinantin arvoa. (Ajattele vain rivioperaatioita polynomien yhteenlaskuina.) Näin res(f (x), g(x)) = |Sylvester(f (x), g(x))| = am−k |Sylvester(f (x), r(x))| = am−k res(f (x), r(x)).
Verrattaessa s.y.t.:n Eukleideen algoritmiin saadaan seurauksena1 välittömästi Seuraus. (Sylvesterin kriteeri) syt(f (x), g(x)) = 1 tarkalleen siinä tapauksessa, että res(f (x), g(x)) = 0 (paitsi kun toinen polynomeista f (x) ja g(x) on nolla ja toinen vakio). Palataan sitten s.y.t.:hen syt(r(x) − cs (x), s(x)), josta lähdettiin. Tehtävänä oli etsiä ne c:n arvot, joille tämä s.y.t. on = 1, eli ne c:n arvot, joille res(r(x) − cs (x), s(x)) = 0. Tämä on polynomiyhtälö c:lle. S.y.t.:n arvoa ei voi laskea suoraan Eukleideen algoritmilla parametristä c johtuen. Samoin ei voida laskea suoraan resultantin arvoa Eukleideen algoritmilla. Determinanttina resultantti voidaan kuitenkin laskea muilla tavoin, usein vaikkapa peruskursseilla esitetyllä eliminaatiomenetelmällä. Kaiken kaikkiaan saadaan seuraava menetelmä integraalin logaritmisen osan laskemiseksi: 1
Samantapaisella todistuksella saadaan monia muitakin mielenkiintoisia resultantin ominaisuuksia. Jos polynomien f (x) ja g(x) juuret (monikerrat mukaan lukien) ovat α1 , α2 , . . . , αn ja β1 , β2 , . . . , βm , niin res(f (x), g(x)) = am n
n i=1
g(αi ) = (−1)nm bnm
m j=1
n f (βj ) = am n bm
n m i=1 j=1
(αi − βj ).
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
82
Rothstein–Trager-algoritmi logaritmisen osan laskemiseksi: 1. Lasketaan res(r(x) − cs (x), s(x)) = R(c). 2. Etsitään R(c):n eri juuret c1 , c2 , . . . , cl . 3. Lasketaan polynomit vj (x) = syt(r(x) − cj s (x), s(x)) (j = 1, 2, . . . , l). 4. Tulostetaan
r(x) ci ln vi (x). dx = s(x) i=1 l
Edellä esitetty menettely sopii sellaisenaan myös silloin, kun vakioina esiintyy muitakin kuin rationaalilukuja. Tällöin ns. vakiokunta on Q:n sijasta jokin sen laajennus K, jossa on liitetty Q:hun sopivasti algebrallisia ja transsendenttisia lukuja (tavallisesti ainakin esimerkiksi π ja e). Integroitavana on silloin K(x):n rationaalifunktio.
7.3
Irrationaalisten alkeisfunktioiden integrointi
Symbolisen integroinnin ohjelmistot aloittavat yleensä integroinnin yrittämällä käyttää peruskursseilta tuttuja temppuja integraalin laskemiseksi. Elleivät nämä onnistu, ohjelmistot käynnistävät yleisen integrointialgoritmin, ns. Rischin integroinnin. Pykälän 2.1:n symbolisista derivointisäännöistä saadaan (enemmän tai vähemmän) tutut symbolisen integroinnin säännöt. Järjestys on sama kuin Pykälässä 2.1: (f (x) ± g(x))dx = f (x)dx ± g(x)dx f (x)Dg(x)dx = f (x)g(x) − g(x)Df (x)dx (osittaisintegrointi) Df (x) f (x) f (x)Dg(x) dx (osittaisintegrointi) dx = + g(x) g(x) g(x)2 g(x)−1 g(x) g(x)f (x) Df (x)dx = f (x) − f (x)g(x) ln f (x) Dg(x)dx (osittaisintegrointi) f (g(x))Dg(x)dx = F (g(x)) , missä F (y) = f (y)dy (sijoitus) −1 −1 −1 f (x)dx = xf (x) − F (f (x)) , missä F (y) = f (y)dy (käänteisintegrointi) Vaikeutena näiden ja muiden tällaisten sääntöjen yhteydessä on se, että sievennysten ja muiden operaatioiden jäljiltä integroitavat funktiot ovat muodoltaan kaukana derivoinnin tuottamista lausekkeista. Näin voi olla hyvin työlästä ”löytää paikkoja”, missä sääntöjä voisi käyttää. Kummituksena on taustalla myös Richardsonin kolmas lause. Jotta päästäisiin eteenpäin, on funktiot esitettävä muutoin kuin pelkästään symbolisesti. Tähän tarvitaan ns. differentiaalikunnan käsite, ks. Pykälä 6.4. Pohjana on jokin ns. vakiokunta, eli kuntien Q ja C välissä oleva lukukunta K. K saadaan yleensä liittämällä Q:hun tietty määrä tarvittavia algebrallisia lukuja ja transsendenttisia lukuja. K:n rationaalifunktioiden kunta K(x)
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
83
laajennetaan edelleen liittämällä siihen joko algebrallisia alkioita (funktioita) tai transsendenttisia alkioita (funktioita). Koska kaikki transsendenttiset laajennukset ovat rakenteeltaan samanlaisia, pitää ne erottaa toisistaan jollain tavalla. Tätä varten otetaan käyttöön derivaattaoperaattori D, joka toteuttaa K(x):ssä (ja sen laajennuksissa) tavalliset derivointisäännöt kunnan laskuoperaatioiden suhteen: Dx = 1, Da = 0 , jos a on vakio (eli vakiokunnan K alkio), D(f (x) + g(x)) = Df (x) + Dg(x), D(f (x)g(x)) = g(x)Df (x) + f (x)Dg(x). Huomaa erityisesti, että jos f (x) h(x) = g(x) k(x)
eli
f (x)k(x) = g(x)h(x),
niin myös Df (x) f (x)Dg(x) Dh(x) h(x)Dk(x) h(x) f (x) −1 = =D = D(f (x)g(x) ) = − − D g(x) g(x) g(x)2 k(x) k(x)2 k(x) (vaatii pientä laskua, jätetään lukijalle). Rationaalifunktioiden samaistus ei siis tuota vaikeuksia. Funktiokuntaa, jossa on tällainen derivaattaoperaattori, kutsutaan differentiaalikunnaksi2 . Jos nyt differentiaalikuntaan F (funktiokunta) liitetään transsendenttinen funktio l(x), niin tulos on algebralliselta kannalta sama olipa l(x) mitä tahansa, kunhan on transsendenttinen. Jos lisätään mukaan jokin l(x):n derivaattaa koskeva ehto, saadaan mukaan rakennetta: • Jos asetetaan ehto Dl(x) = l(x)Df (x), missä f (x) on F :n funktio, niin liitetty funktio on muotoa l(x) = cef (x) , missä c = 0 on vakio. l(x) on tällöin F :n suhteen eksponentiaalinen. • Jos asetetaan ehto Dl(x) = (Df (x))/f (x), missä f (x) on F :n funktio, niin liitetty funktio on muotoa l(x) = ln f (x) + c, missä c on vakio. l(x) on tällöin F :n suhteen logaritminen. (Tässä itse asiassa sallitaan myös kompleksiset logaritmit.) Koska laajennetun kunnan F (l(x)) alkiot ovat l(x):n rationaalifunktioita ja derivaatta Dl(x) on annettu myös F (l(x)):n alkiona, voidaan F (l(x)):n alkioiden derivaatat laskea tavallisin derivointisäännöin ja näin ollen F (l(x)):kin on differentiaalikunta. Näiden laajennusten lisäksi voidaan tietysti tehdä • algebrallisia laajennuksia, ts. liitetään mukaan algebrallisia funktioita, siis F :n polynomirenkaan F [y]:n polynomien juuria (tässä derivaattaoperaattoria ei tarvita). Tällaisenkin laajennuksen jälkeen kunta pysyy differentiaalikuntana. Jos nimittäin algebrallinen alkio l(x) on F [y]:n jaottoman polynomin v(y) = an (x)y n + an−1 (x)y n−1 + · · · + a1 (x)y + a0 (x) juuri, niin v(l(x)) = 0, josta l(x):n derivaatta saadaan implisiittisellä derivoinnilla: 0 = D(v(l(x))) = (Dan (x))l(x)n + (Dan−1 (x))l(x)n−1 + · · · + (Da1 (x))l(x) + Da0 (x) + (nan (x)l(x)n−1 + (n − 1)an−1 (x)l(x)n−2 + · · · + a1 (x))Dl(x) 2
Abstraktin differentiaalikunnan määrittelyssä vaaditaan vain summan ja tulon derivointisäännöt. Tämä ei kiinnitä derivaattaa yksikäsitteisesti.
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
84
ja Dl(x) = −
(Dan (x))l(x)n + (Dan−1 (x))l(x)n−1 + · · · + (Da1 (x))l(x) + Da0 (x) . nan (x)l(x)n−1 + (n − 1)an−1 (x)l(x)n−2 + · · · + a1 (x)
Tässä ei nimittäjä voi olla nolla. Muutoin v(y):llä ja nimittäjän polynomilla w(y) = nan (x)y n−1 + (n − 1)an−1 (x)y n−2 + · · · + a1 (x) on yhteinen juuri, joka Bezout’n muodon syt(v(y), w(y)) = c1 (x)v(y) + c2 (x)w(y) kautta on myös on syt(v(y), w(y)):n juuri. Näin syt(v(y), w(y)) on = 1, alempaa astetta kuin v(y) ja jakaa v(y):n. Tämä ei käy, sillä v(y) on jaoton. Näin myös algebrallisessa laajennuksessa Dl(x) on F (l(x)):ssä. Alkeisfunktioiden perustyyppejä voidaan mukavasti vähentää, jos sallitaan kompleksiset eksponenttifunktiot ja logaritmit. Silloin nimittäin esimerkiksi 1 1 sin x = sinh ix = (eix − e−ix ), i 2i 1 √ 1 arcsin x = arsinh ix = ln( 1 − x2 + ix), i i i x+i π arctan x = ln + . 2 x−i 2 Itse asiassa voidaan rajoittua vain eksponentiaalisiin, logaritmisiin ja algebrallisiin laajennuksiin ja silti saadaan kaikki tutut alkeisfunktiot. F :n kuntalaajennusta F (f1 (x), f2 (x), . . . , fm (x)) kutsutaankin alkeiseksi, jos (1) f1 (x) on F :n suhteen eksponentiaalinen, logaritminen tai algebrallinen ja (2) funktio fi (x) on F (f1 (x), f2 (x), . . . , fi−1 (x)):n suhteen eksponentiaalinen, logaritminen tai algebrallinen (i = 2, 3, . . . , m). Peräkkäiset laajennukset F (f1 (x), f2 (x), . . . , fi (x)) (i = 1, 2, . . . , m) muodostavat kuntalaajennustornin F (f1 (x), f2 (x), . . . , fm (x)) F (f1 (x), f2 (x), . . . , fm−1 (x)) .. . F (f1 (x)) F Klassisessa mielessä x:n funktio on alkeisfunktio, jos se kuuluu johonkin C(x):n alkeiseen laajennukseen. Symbolisessa analyysissä vakiokuntana ei voi olla C, vaan jokin pienempi Q:n laajennus. On jo kauan ollut tunnettua, minkä muotoinen alkeisfunktion integraali on, jos se vain on alkeisfunktio: Lause 7.3. (Liouvillen periaate) Oletetaan, että F on differentiaalikunta, jonka vakiokunta on K (Q:n laajennus ja F :n alikunta). Jos F :n funktiolla g(x) on integraali G(x) jossain F :n alkeisessa laajennuksessa (ts. tässä laajennuksessa DG(x) = g(x)) ja ko. alkeisen laajennuksen vakiokunta on myös K, niin N Dvi (x) g(x) = Dv0 (x) + ci vi (x) i=1
ja
G(x) = v0 (x) +
N
ci ln vi (x),
i=1
missä v0 (x), v1 (x), . . . , vN (x) ovat F :n funktioita ja c1 , c2 , . . . , cN ovat K:n vakioita.
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
85
Todistus. Todistus on pitkä, mutta ei oikeastaan kovin vaikea, ks. esimerkiksi G EDDES & C ZA BOR & L ABAHN . Se perustuu derivaattojen muotojen vertailuun. Huomaa kuitenkin, että edellä esitetty rationaalifunktion integrointi tuottaa juuri Liouvillen periaatteen mukaisen tuloksen. Symbolisen integroinnin kantavana ideana on saada aikaan algoritminen Liouvillen periaate. Jos ajatellaan yo. kuntalaajennustornia, voidaan tornissa edetä ylöspäin askelma kerrallaan liittämällä yksitellen mukaan funktioita fi (x). Rekursiivisesti ajatellen F (f1 (x), f2 (x), . . . , fi (x)):n funktiot voidaan kirjoittaa muotoon p1 (fi (x)) , p2 (fi (x)) missä p1 (y) ja p2 (y) ovat F (f1 (x), f2 (x), . . . , fi−1 (x)):n polynomirenkaan F (f1 (x), f2 (x), . . . , fi−1 (x))[y] polynomeja. Tämä sekä Liouvillen periaatteen antama muoto viittaavat siihen, että integrointi sujuu pääpiirteittäin samoin kuin rationaalifunktioille. Näin onkin, tietysti itse menettely on paljon mutkikkaampi. Alkeisfunktioille, joissa ei esiinny algebrallisia osia, tämän idean toteutti ensimmäisenä R.H. Risch3 (ks. G EDDES & C ZABOR & L ABAHN), puhtaasti algebralliselle alkeisfunktioille J.H. Davenport (ks. DAVENPORT) ja yleiselle, myös algebrallisia osia sisältävälle alkeisfunktiolle M. Bronstein3 . Huomaa, että mukana on myös sen päättäminen, onko integraali lainkaan lausuttavissa alkeisfunktioiden avulla (jolloin se ei ole Liouvillen periaatteen antamaa muotoa). Saatua symbolista testaus-/integrointi-menettelyä kutsutaan usein Rischin integroinniksi. Sitä ei liene aivan yleisesti implementoituna missään ohjelmistossa. Kutakuinkin kaikki ohjelmistot sekoavat vielä toisinaan algebrallisten osien käsittelyssä (ts, sekoittavat keskenään polynomien juuria), mikä voi johtaa pahasti vääriin tuloksiin. Huomautus. Tärkeä ero puhtaasti symbolisiin manipulaatioihin perustuvan integroinnin sekä Rischin integroinnin välillä on seuraava: Edellinen ei yleisesti ottaen voi onnistua aina (johtuen mm. Richardsonin 3. lauseesta). Rischin integrointi on kuitenkin mahdollista aivan yleisesti, sillä funktiot esitetään kuntalaajennustornin avulla, joka estää Richardsonin ratkeamattomuustuloksen syntymisen. Katsotaan Rischin integrointia vain eräässä erikoistapauksessa, ns. puhtaasti logaritmisen funktion integroinnissa. Tällöin differentiaalikuntaan F tehdään (transsendenttinen) logaritminen laajennus F (l(x)), missä siis Dl(x) =
Df (x) f (x)
ja
f (x) on F :n funktio.
Lisäksi oletetaan, että F :n ja laajennuksen vakiokunnat ovat samat (ks. Liouvillen periaate). Vielä oletetaan, että F :ssä voidaan integroida symbolisesti. Kuten todettu, F (l(x)):ssä oleva mielivaltainen integrandi h(x) voidaan (jakolaskulla) kirjoittaa muotoon h(x) =
p1 (l(x)) r(l(x)) = q(l(x)) + , p2 (l(x)) p(l(x))
missä p1 (y), p2 (y), q(y), r(y), p(y) ovat F :n polynomirenkaan F [y] polynomeja, deg(r(y)) < deg(p(y)) ja syt(r(y), p(y)) = 1 (tai sitten r(y) on nollapolynomi). Koska deg(r(y)) < deg(p(y)), sanotaan, että r(y)/p(y) on aidosti rationaalinen. Ensin tarvitaan 3
Alkuperäisviitteet ovat R ISCH , R.H.: The Problem of Integration in Finite Terms. Bulletin of the American Mathematical Society bf 139 (1969), 167–189 ja B RONSTEIN , M.: Integration of Elementary Functions. Journal of Symbolic Computation 9 (1990), 117–173. Vanha klassikko on R ITT, J.F.: Integration in Finite Terms. Columbia University Press (1948), jossa differentiaalikunnan tärkeys jo todettiin.
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
86
Lause 7.4. (Dekompositiolemma) Jos h(x):llä on alkeinen integraali, niin samoin on q(l(x)):llä ja r(l(x))/p(l(x)):llä. Todistus. Jos h(x):llä on alkeinen integraali, niin Liouvillen periaatteen mukaisesti Dvi r(l(x)) h(x) = q(l(x)) + ci . = Dv0 + p(l(x)) v i i=1 N
Tässä voidaan olettaa (tarvittaessa derivoimalla, jakamalla ja indeksoimalla uudelleen), että vi = vi (l(x)) (i = 1, 2, . . . , k), missä v1 (y), v2 (y), . . . , vk (y) ovat F [y]:n pääpolynomeja, ja että vi = vi (x) (i = k + 1, k + 2, . . . , N ) ovat F :n funktioita. Laskien nimittäin todetaan, että jos v=
a(x)u(l(x)) , b(x)w(l(x))
missä a(x) sekä b(x) ovat F :ssä ja u(y) sekä w(y) ovat F [y]:n pääpolynomeja, niin b(x)w(l(x))D(a(x)u(l(x))) − a(x)u(l(x))D(b(x)w(l(x))) Dv b(x)2 w(l(x))2 = a(x)u(l(x)) v b(x)w(l(x)) D(a(x)u(l(x))) D(b(x)w(l(x))) = − a(x)u(l(x)) b(x)w(l(x)) Da(x) D(u(l(x))) D(b(x)) D(w(l(x))) = + − − . a(x) u(l(x)) b(x) w(l(x)) (Tämä on tietysti peruskursseilta tutun logaritmisen derivoinnin suoraan antama tulos, mutta ei sitä tässä noin vain voi käyttää.) Edelleen voidaan olettaa, että v0 on muotoa v0 = q0 (l(x)) +
r0 (l(x)) p0 (l(x))
missä q0 (y), r0 (y), p0 (y) ovat F :n polynomirenkaan F [y] polynomeja, joille r0 (y)/p0 (y) on aidosti rationaalinen. Nyt h(x) = Dv0 +
N i=1
N k r0 (l(x)) Dvi Dvi Dvi ci = D(q0 (l(x))) + ci +D ci . + vi vi p0 (l(x)) vi i=1 i=k+1 polynominen osa
aidosti rationaalinen osa
Koska l(x) on transsendenttinen F :n suhteen, on tämä dekompositio ”polynomi + aidosti rationaalinen funktio” yksikäsitteinen (polynomien jakolasku on yksikäsitteinen). Pitää vain tarkistaa, että aidosti rationaalinen osa todella on nimensä mukainen eli että osoittajan aste on pienempi kuin nimittäjän. Yleisesti, jos v(y) = an (x)y n + an−1 (x)y n−1 + · · · + a1 (x)y + a0 (x)
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
87
on F [y]:n astetta n oleva polynomi, niin v(l(x)):n derivaatta D(v(l(x))) = (Dan (x))l(x)n + (Dan−1 (x))l(x)n−1 + · · · + (Da1 (x))l(x) + Da0 (x) + (nan (x)l(x)n−1 + (n − 1)an−1 (x)l(x)n−2 + · · · + a1 (x))Dl(x) on enintään astetta n l(x):n suhteen ja alempaa kuin n:ttä astetta, mikäli v(y) on pääpolynomi (jolloin an (x) = 1). Näin ollen ensiksi p0 (l(x))D(r0 (l(x)) − r0 (l(x))D(p0 (l(x))) r0 (l(x)) , = D p0 (l(x)) p0 (l(x))2 jossa selvästi osoittajan aste l(x):n suhteen on pienempi kuin nimittäjän. Toiseksi, koska polynomit v1 (y), v2 (y), . . . , vk (y) ovat pääpolynomeja, myös osamäärässä D(vi (l(x))) Dvi = vi vi (l(x)) osoittajan aste l(x):n suhteen on pienempi kuin nimittäjän. Kolmanneksi, laskettaessa yhteen aidosti rationaalisia funktioita, saadaan aidosti rationaalinen funktio (totea!). Siispä N k Dvi Dvi r(l(x)) r0 (l(x)) q(l(x)) = D(q0 (l(x))) + ci ja ci =D + vi p(l(x)) p0 (l(x)) vi i=1 i=k+1 eli q(l(x))dx = q0 (l(x)) +
N
ci ln vi
r(l(x)) r0 (l(x)) ci ln vi . dx = + p(l(x)) p0 (l(x)) i=1 k
ja
i=k+1
Tärkeänä lisätietona saatiin integraalien muodot. Dekompositiolemma todistuksineen osoittaa, että integrointi voidaan tehdä kahdessa osassa, polynomisessa ja aidosti rationaalisessa. Lisäksi nämä osat ovat muodoltaan tunnetut. Aidosti rationaalisen osan integrointi on hyvin samanlainen kuin rationaalifunktion integrointi edellisessä pykälässä. Katsotaan erikseen polynomisen osan ja aidosti rationaalisen osan integroinnit. Aloitetaan polynomisesta osasta ja merkitään q(y) = bn (x)y n + bn−1 (x)y n−1 + · · · + b1 (x)y + b0 (x) sekä q0 (y) = dm (x)y m + dm−1 (x)y m−1 + · · · + d1 (x)y + d0 (x), missä bn (x) ja dm (x) eivät ole nollia. (Jos q(y) on nollapolynomi, on tapaus tietysti selvä.) Silloin yhtälöstä N Dvi q(l(x)) = D(q0 (l(x))) + ci vi i=k+1 saadaan n
i
bi (x)l(x) = D
m
i=0
i=0
=
m i=0
i
di (x)l(x)
+
N
ci
i=k+1
(Ddi (x))l(x)i + (Dl(x))
Dvi (x) vi (x)
m i=1
N Dvi (x) ci . v i (x) i=k+1
idi (x)l(x)i−1 +
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
88
Nyt, jos Ddm (x) = 0 eli dm (x) on vakio, on m = n + 1 (muussa tapauksessa olisi Ddm−1 (x) = −D(mdm (x)l(x)) ja dm−1 (x) ∈ / F ), muuten m = n. Edellisessä tapauksessa merkitään yhdenmukaisuuden vuoksi bm (x) = 0. Kun otetaan l(x):n potenssit erikseen, saadaan yhtälöt bm (x) = Ddm (x), bm−1 (x) = Ddm−1 (x) + mdm (x)Dl(x), bm−2 (x) = Ddm−2 (x) + (m − 1)dm−1 (x)Dl(x), .. . b1 (x) = Dd1 (x) + 2d2 (x)Dl(x), N Dvi (x) b0 (x) = Dd0 (x) + d1 (x)Dl(x) + ci vi (x) i=k+1
eli
dm (x) = dm−1 (x) =
(bm−1 (x) − mdm (x)Dl(x))dx, (bm−2 (x) − (m − 1)dm−1 (x)Dl(x))dx,
dm−2 (x) = .. .
bm (x)dx,
(b1 (x) − 2d2 (x)Dl(x))dx,
d1 (x) = d0 (x) =
(b0 (x) − d1 (x)Dl(x))dx −
N
ci ln vi (x).
i=k+1
Näistä saadaan kerroinfunktiot dm (x), dm−1 (x), . . . , d0 (x) seuraavasti: 1. dm (x) saadaan integroimalla F :n integrointialgoritmilla bm (x). Jollei tulos ole F :ssä, niin kuin sen pitäisi, ei polynominen osa integroidu alkeisesti. Muutoin dm (x) määräytyy integrointivakiota Cm vaille: dm (x) = dˆm (x) + Cm . 2. dm−1 (x) saadaan integroimalla F :n integrointialgoritmilla: dm−1 (x) = (bm−1 (x) − mdˆm (x)Dl(x))dx − mCm l(x) + Cm−1 = dˆm−1 (x) + Cm−1 . Jälleen tulos määräytyy integrointivakiota Cm−1 vaille. Jollei nyt bm−1 (x)−mdˆm (x)Dl(x) integroidu alkeisesti tällaiseen muotoon, ei polynominen osakaan integroidu alkeisesti. Huomaa, että mukana on jo logaritmi l(x), mikä määrää Cm :n valinnan. 3. Näin jatketaan. Aina tulos saadaan integrointivakiota vaille. Lopulta tullaan d0 (x):ään: N ˆ ci ln vi (x). d0 (x) = (b0 (x) − d1 (x)Dl(x))dx − C1 l(x) + C0 − i=k+1
Jollei b0 (x) − dˆ1 (x)Dl(x) integroidu alkeisesti haluttuun muotoon, päätellään jälleen, että polynominen osa ei integroidu alkeisesti. Tästä integroinnista tulee mukaan muitakin logaritmeja kuin vain l(x). Lisäksi lopputulokseen jää yksi integrointivakio C0 , kuten pitääkin (muut kiinnittyvät ”matkan varrella”).
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
89
Aidosti rationaalinen osa integroidaan aivan samalla tavoin kuin rationaalifunktio Pykälässä 7.2, rationaalinen osa Hermiten menetelmällä ja logaritminen osa Rothstein–Trager-algoritmilla. (Horowitzin menetelmä ei oikein tule kysymykseen, keksitkö miksi.) Rothstein–Trager-algoritmissa esiintyvät resultanttipolynomin R(c) juuret voivat periaatteessa riippua x:stä. Jos yksikin juurista riippuu x:stä, ei integraali kuitenkaan voi olla alkeinen, sillä se ei silloin ole Liouvillen periaatteen antamaa muotoa. Näissä menetelmissä derivoinnit suoritetaan x:n suhteen, tulokset ovat silti oikeita. Tämän näyttämiseksi pitäisi läpikäydä Pykälän 7.2 (ja Lauseen 5.11) todistukset uudelleen tässä tapauksessa muutamin helpoin muutoksin, ks. esimerkiksi G EDDES & C ZABOR & L ABAHN . Eksponentiaalinen laajennus on hyvin samankaltainen kuin yllä käsitelty logaritminenkin. Koska eksponentiaaliselle l(x):lle Dl(x) = l(x)Df (x), l(x):n polynomin aste l(x):n suhteen pysyy samana derivoitaessa. Tämä muuttaa Dekompositiolemmaa vähän toisen muotoiseksi, mutta ikävä kyllä aiheuttaa myös sen, ettei riitä olettaa, että F :ssä voidaan integroida symbolisesti, vaan pitää voida ratkaista symbolisesti 1. kertaluvun lineaarinen differentiaaliyhtälö, jonka kertoimet ovat F :ssä, tai sitten todeta, ettei sillä ole alkeisia ratkaisuja. Peruskursseilta tuttu ratkaisukaava (ks. Pykälä 7.5) ei muuten auta, sillä siinä tarvittavat integroinnit ovat juuri sellaisia, että ne edellyttävät ko. differentiaaliyhtälön symbolista ratkaisua! Tätä pulmaa käsittelee esimerkiksi G EDDES & C ZABOR & L ABAHN tai B RONSTEIN . Ratkaisuna on konstruoida omat ratkaisualgoritminsa näille differentiaaliyhtälöille samaan tapaan kuin edellä. Algebrallisen laajennuksen tapaus onkin jo sitten vaikeudeltaan aivan eri luokkaa, ks. esimerkiksi G EDDES & C ZABOR & L ABAHN .
7.4
Erikoisfunktiot
Silloin, kun integraali ei ole alkeinen, se voidaan usein lausua käyttäen tiettyjä perustyyppejä olevia ei-alkeisia integraaleja. Tällaiset integraalit ovat ns. erikoisfunktioita. (Erikoisfunktioksi sanotaan yleisesti ottaen sellaisia funktioita, jotka eivät ole alkeisia C(x):n suhteen.) Tavallisimmat ovat: ∞ 1. vajaa gammafunktio Γ(x, y) = tx−1 e−t dt (gammafunktio on Γ(x) = Γ(x, 0)), y
z tx−1 (1 − t)y−1 dt (betafunktio on β(x, y) = β(x, y, 1),
2. vajaa betafunktio β(x, y, z) = 0
2 3. errorfunktio erf(x) = √ π
x
e−t dt, 2
0
x
x sinc t dt =
4. sini-integraali Si(x) = 0
0
x 5. kosini-integraali Ci(x) = γ + ln x +
γ = lim
n→∞
sin t dt, t
n 1 i=1
i
0
cos t − 1 dt (tässä γ on ns. Eulerin vakio t
− ln n
= 0.5772156649 . . . ),
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT x 6. hyperbolinen sini-integraali Shi(x) =
90
sinh t dt, t
0
x 7. hyperbolinen kosini-integraali Chi(x) = γ + ln x +
cosh t − 1 dt, t
0
∞ 8. eksponentti-integraalit Ei(n, x) =
dt tn ext
(n = 0, 1, . . . ),
1
x 9. Fresnelin sini-integraali FresnelS(x) =
sin
πt2 dt, 2
0
x cos
10. Fresnelin kosini-integraali FresnelC(x) =
πt2 dt, 2
0
x 11. logaritmi-integraali Li(x) =
dt = −Ei(1, − ln x), ln t
0
12. erilaiset elliptiset integraalit. Lisätietoa näistä on esimerkiksi viitteissä A BRAMOWITZ & S TEGUN ja A NDREWS & A SKEY & ROY. Ohjelmistoissa on yleensä ainakin jossain määrin tuettuina yllä olevat ja muitakin erikoisfunktioita. Differentiaaliyhtälöiden ratkaisuina tulee vielä paljon lisää erikoisfunktioita (Besselin funktiot jne.). Huomautus. Periaatteessa on mahdollista yleistää Liouvillen periaate koskemaan erinäisiä erikoisfunktioitakin, jolloin ne ikäänkuin siirtyvät alkeisfunktioiden joukkoon.
7.5
Differentiaaliyhtälöt
Differentiaaliyhtälön (DY:n) symbolisella ratkaisulla tarkoitetaan yleisesti sen kirjoittamista ekvivalenttiin muotoon, jossa ei esiinny derivaattoja eikä integrointeja. Vanhastaan puhutaan DY:n integroinnista, koska menettely vaatii symbolisia integrointeja. Peruskursseilta tutut ratkaisukaavat ovat juuri tällaisia integrointeja: • Separoituvan DY:n Dy = f (x)g(y) yleisen ratkaisun antaa integroinnin jälkeen (implisiittisesti) y(x) x dv = f (u)du. g(v) y(x0 )
x0
(Tällaisella DY:llä voi olla muitakin, ns. singuläärisiä ratkaisuja.)
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
91
• Lineaarisen 1. kertaluvun differentiaaliyhtälön Dy + a(x)y = b(x) ratkaisukaava taas on −
y(x) = e
x
a(u)du
x
v
e x0
x0
−
a(u)du
b(v)dv + y(x0 )e
x
a(u)du
x0
.
x0
• Eksaktissa DY:ssä f (x, y) + g(x, y)Dy = h(x) on oltava ∂g(x, y) ∂f (x, y) = . ∂y ∂x Symbolisesti on (f (x, y), g(x, y)) tällöin jonkin funktion u(x, y) gradientti ja u(x, y) (ns. potentiaali) määräytyy vakiota vaille yksikäsitteisesti. DY:n ratkaisu on (implisiittisesti) u(x, y(x)) = h(x)dx + C. (Jälleen voi olla muitakin, singuläärisiä ratkaisuja.) Tässä esiintyy yksi integrointi ja u(x, y) voidaan löytää integroimalla (symbolisesti) kaksi kertaa: Ensin ∂u(x, y) u(x, y) = dx + c(y) = f (x, y)dx + c(y) = F (x, y) + c(y), ∂x josta saadaan g(x, y) =
∂u(x, y) ∂F (x, y) d = + c(y) ∂y ∂y dy
ja sitten integroimalla y:n suhteen c(y). Näitä tällaisia DY:öiden integrointeja eri tapauksille tunnetaan suuri määrä. Erittäin klassinen viite on K AMKE , E.: Differentialgleichungen: Lösungsmethoden und Lösungen 1. Gewöhnliche Differentialgleichungen. Becker & Erler (1943). Siinä olevia ”temppuja” ja vielä muitakin on ohjelmistoissa valmiina useita. Myös peruskursseilta tuttu DY-tyyppi on vakiokertoiminen lineaarinen DY: an Dn y + an−1 Dn−1 y + · · · + a1 Dy + a0 y = f (x), missä a0 , a1 , . . . , an ovat vakioita ja an = 0. Vastaavan homogeenisen DY:n ratkaisu on tunnetusti aina muotoa k y0 (x) = pi (x)eρi x , i=1
missä ρ1 , ρ2 , . . . , ρk ovat DY:n karakteristisen polynomin r(ρ) = an ρn + an−1 ρn−1 + · · · + a1 ρ + a0 eri juuret ja pi (x) on polynomi, jonka aste on enintään juuren ρi kertaluku vähennettynä yhdellä (i = 1, 2, . . . , k). Ratkaisu y0 (x) siis saadaan välittömästi, kunhan saadaan konstruoiduksi r(ρ):n hajoamiskunta. Tämä on usein erittäin ison työn takana. Tilanteen pelastaa osittain se, että polynomit pi (x) saadaan kuitenkin lausutuksi eri juurten ρ1 , ρ2 , . . . , ρk avulla. Esiintyvät juurten kertaluvut nimittäin saadaan selville r(ρ):n neliöttömiin tekijöihin jaosta (ks. Pykälä 5.7) r(ρ) = an q1 (ρ)q2 (ρ)2 q3 (ρ)3 · · · qm (ρ)m .
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
92
Kertalukua j olevat juuret ovat tarkalleen kaikki qj (ρ):n juuret ja niitä on deg(qj (ρ)) kpl. (Jos qj (ρ):lla olisi moninkertainen juuri, se olisi myös sen derivaatan qj (ρ) juuri ja edelleen Bezout’n muodon kautta syt(qj (ρ), qj (ρ)):n juuri ja Lauseen 5.11 nojalla qj (ρ) ei olisikaan neliötön. Toisaalta polynomeilla q1 (ρ), q2 (ρ), . . . , qm (ρ) ei ole yhteisiä juuria, koska ne ovat pareittain keskenään jaottomia.) Näin eri juuria ρ1 , ρ2 , . . . , ρk voidaan merkitä symboleilla ja kirjoittaa y0 (x) =
k
Pi (x)eρi x ,
i=1
missä Pi (x):n kertoimet ovat määräämättömät (maksimiaste on pienempi kuin ρi :n kertaluku, joka tiedetään), ja ratkaista symbolisesti kertoimet alkuehtojen antamista yhtälöistä k Dj Pi (x)eρi x = yj (j = 0, 1, . . . , n − 1), i=1
x=x0
missä y(x0 ) = y0 , Dy(x0 ) = y1 , . . . , Dn−1 y(x0 ) = yn−1 (lineaarinen yhtälöryhmä, n yhtälöä ja n tuntematonta). Ratkaisu saadaan näin lausutuksi juurten ρ1 , ρ2 , . . . , ρk avulla ja niille voidaan etsiä numeeriset likiarvot. Varsinainen yleinen ratkaisu saadaan etsimällä DY:lle yksittäisratkaisu ja lisäämällä se y0 (x):ään. Yksittäisratkaisun löytämiseksi symbolisesti voi toisinaan käyttää vakioiden variointia. (Ks. kurssi Differentiaaliyhtälöt.) Ns. Kovacicin algoritmi etsii lineaarisen 2. kertalukua olevan homogeenisen DY:n D2 y + a(x)Dy + b(x)y = 0, missä a(x) ja b(x) ovat rationaalisia funktioita, yleisen ns. Liouvillen ratkaisun4 tai sitten osoittaa, ettei sillä ole sellaista (paitsi tietenkin nollafunktio). Algoritmi on erittäin mutkikas, mutta on silti implementoitu useissa ohjelmistoissa käyttökelpoisuutensa takia. Alkuperäisviite on KOVACIC , J.J.: An Algorithm for Solving Second Order Linear Homogeneous Differential Equations. Journal of Symbolic Computation 2 (1986), 3–43 (tulos on kuitenkin alunperin kymmenen vuotta vanhempi). Ks. myös DAVENPORT & S IRET & T OURNIER . Kovacicin algoritmi on yleistetty tapaukseen, jossa kertaluku voi olla korkeampikin ja kertoimina voi olla algebrallisiakin funktioita, ns. Singerin algoritmi, ks. S INGER , M.F.: Liouvillian Solutions of n-th Order Linear Homogeneous Differential Equations. American Journal of Mathematics 103 (1981), 661–682. Jälleen yksityisratkaisujen etsiminen symbolisesti saattaa onnistua vakioiden varioinnilla. Mainittakoon tässä vielä tunnettu sijoitus, jolla voidaan muuntaa lineaarinen DY vakiokertoimiseksi, mikäli se yleensä ottaen on sijoituksella mahdollista: Lause 7.5. (Jeruginin lause) Jos lineaarinen DY Dn y + an−1 (x)Dn−1 y + · · · + a1 (x)Dy + a0 (x)y = f (x), voidaan muuntaa sijoituksella vakiokertoimiseksi, niin kyseessä on sijoitus t = φ(x), missä n ca0 (x)dx (ns. Jeruginin sijoitus) φ(x) = ja c on vakio. 4
Liouvillen ratkaisu on ratkaisu, joka on kuntalaajennustornissa, missä kukin askel on joko eksponentiaalinen tai algebrallinen tai integraalinen. Vm. askel on sellainen, missä liitetään kuntaan jonkin siinä olevan funktion f (x) integraali. Liitettävä funktio l(x) derivoidaan siis kaavalla Dl(x) = f (x). Huomaa, että Liouvillen periaatteen kautta mukaan tulee logaritmejakin. Toisaalta mukaan tulevat myös kaikki ei-alkeiset integraalitkin, vrt. DY:n ratkaisu ”integroimalla”. Eli tarkoituksena on palauttaa DY:n ratkaiseminen integrointiin.
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
93
Todistus. Merkitään y(x) = z(φ(x)). (Jotta φ(x) olisi käypä sijoitus, pitää sen tietysti olla kääntyvä ja n kertaa derivoituva.) Lasketaan Ketjusäännöllä derivaattoja: Dy(x) = Dz(φ(x))Dφ(x), D2 y(x) = D2 z(φ(x))(Dφ(x))2 + Dz(φ(x))D2 φ(x), .. . n D y(x) = Dn z(φ(x))(Dφ(x))n + · · · . Jos sijoitus muuntaa DY:n vakiokertoimiseksi, on erityisesti silloin a0 (x) =b (Dφ(x))n vakio. Valitaan nyt c = 1/b. Lineaarisille DY:öille sopivia sijoituksia tunnetaan lukuisia muitakin ja niitäkin on joitain implementoituina ohjelmistoissa. Usein riittää saada DY:n ratkaisun Taylorin sarja. Lineaarisen alkuarvotehtävän an (x)Dn y + an−1 (x)Dn−1 y + · · · + a1 (x)Dy + a0 (x)y = f (x), y(x0 ) = b0 , Dy(x0 ) = b1 , . . . , Dn−1 y(x0 ) = bn−1 ratkaisun Taylorin sarja 1 1 b1 (x − x0 ) + · · · + bn−1 (x − x0 )n−1 1! (n − 1)! n + cn (x − x0 ) + cn+1 (x − x0 )n+1 + · · ·
y(x) = b0 +
pisteessä x = x0 saadaan peräkkäisten approksimaatioiden menetelmällä olettaen, että kerroinfunktioiden ai (x) sekä pakkofunktion f (x):n Taylorin sarjat tässä pisteessä tunnetaan ja että an (x0 ) = 0 (ja usein muulloinkin). Alkupään kertoimet saadaan alkuehdoista ja DY:stä: ci =
bi i!
cn =
1 (f (x0 ) − an−1 (x0 )bn−1 − an−2 (x0 )bn−2 − · · · − a0 (x0 )b0 ). n!an (x0 )
(i = 0, 1, . . . , n − 1),
Menettely on seuraava: Peräkkäisten approksimaatioiden menetelmä lineaariselle DY:lle: 1. Asetetaan r ← n + 1 ja yn ← c0 + c1 (x − x0 ) + · · · + cn (x − x0 )n . 2. Lasketaan kertoimien ai (x) ja pakkofunktion f (x):n Taylorin polynomit Pi (x) ja Q(x) pisteessä x = x0 . (Asteluvun pitää olla kyllin korkea.) 3. Ratkaistaan yhtälöstä Pn (x)Dn yr + Pn−1 (x)Dn−1 yr + · · · + P1 (x)Dyr + P0 (x)yr = Q(x) kerroin cr (unohtaen (x − x0 )r :ää korkeammat x − x0 :n potenssit).
LUKU 7. SYMBOLINEN INTEGROINTI JA DIFFERENTIAALIYHTÄLÖT
94
4. Jos tarvitaan vielä korkeampiasteisia termejä, asetetaan r ← r + 1 sekä
yr ← yr−1 + cr (x − x0 )r
ja mennään kohtaan 3. Muuten tulostetaan yr ja lopetetaan. Menetelmä voidaan toisinaan modifioida myös tapaukseen, jossa an (x0 ) = 0. Esimerkiksi alkuarvotehtävälle xDy + (sin x)y = x2 , y(0) = b saadaan sarjaratkaisu, sillä se on sama kuin Dy + (sinc x)y = x ,
y(0) = b,
ja sinc-funktiolla on Taylorin sarja. Yleensäkin, jos funktioilla ai (x)/an (x) (i = 0, 1, . . . , n−1) ja f (x)/an (x) on Taylorin sarjat pisteessä x = x0 , saadaan ratkaisun Taylorin sarja pisteessä x = x0 Peräkkäisten approksimaatioiden menetelmällä. Huomautus. Myös Frobeniuksen menetelmä, jossa nimenomaan käsitellään tapausta, missä an (x0 ) = 0, voidaan toteuttaa symbolisesti, ks. esimerkiksi DAVENPORT & S IRET & T OUR NIER ja kurssi Differentiaaliyhtälöt.
”Fortunately, on 20 April 1977, all of this kludgery was rendered obsolete when I found a decision procedure for this problem. (A discrete analog to the Risch algorithm for indefinite integration.)” (R. William Gosper, Jr., Indefinite Hypergeometric Sums in MACSYMA, Proceedings of MACSYMA Users Conference, Berkeley, 1977)
Luku 8 SUMMAUS JA KERTOMINEN 8.1
Summat ja differenssit
Summaus koskee kokonaisluvuille määriteltyjä funktioita1 f (n). Funktion arvot voivat olla mitä tahansa lukuja (tai muutakin). Tavallinen summa on muotoa b
f (n) = f (a) + f (a + 1) + · · · + f (b).
n=a
Kyseessä on ns. määrätty summa (vrt. määrätty integraali). Määräämätöntä integraalia vastaa ns. määräämätön summa f (n)δn, missä δn on integraalin differentiaalia dx vastaava merkinnällinen lausekkeen osa. Määräämätön summa määritellään ottamalla käyttöön derivaattaa vastaava operaatio, ns. differenssi: ∆F (n) = F (n + 1) − F (n). (Kyseessä on ns. etenevä differenssi, takeneva differenssi on ∇F (n) = F (n) − F (n − 1) ja se olisi yhtä käyttökelpoinen.) Määräämätön summa f (n)δn tarkoittaa kollektiivisesti funktioita F (n), jotka toteuttavat yhtälön ∆F (n) = f (n). Koska ainoat funktiot, joiden differenssi on nollafunktio, ovat vakiofunktiot, on määräämätön summa näin yksikäsitteinen summausvakiota vaille (aivan kuten määräämätön integraali on yksikäsitteinen integrointivakiota vaille). Funktion f (n) summaus tarkoittaa yleisesti sen määräämättömän summan F (n) = f (n)δn (+ C) löytämistä. Jos F (n) tunnetaan saadaan sen avulla laskettua kaikki f (n):n määrätyt summat: Lause 8.1. (Summauslaskennan peruslause) Jos F (n) = f (n)δn, niin b
f (n) = F (b + 1) − F (a) =
n=a 1
b+1
F (n). a
Nämä voidaan tarvittaessa jatkaa reaaliluvuille x asettamalla f (x) tai f (x).
95
LUKU 8. SUMMAUS JA KERTOMINEN
96
Todistus. Ilmeisesti b
F (b + 1) − F (a) =
(F (n + 1) − F (n)) =
n=a
b
∆F (n) =
n=a
b
f (n).
i=a
Tämän lauseen mukaisesti on luonnollista merkitä b
f (n)δn =
n=a
ja
b
b−1
f (n) ,
kun b ≥ a
n=a
f (n)δn = −
n=a
a
f (n)δn ,
kun b ≤ a.
n=b
Summauslaskennan peruslause tulee tällöin ”tuttuun” muotoon b
f (n)δn = F (b) − F (a) =
n=a
Huomaa, että
b F (n). a
n−1
f (m) =
m=a
n
f (m)δm
m=a
on aina eräs f (n):n määräämätön summa. Derivointisääntöjä vastaten saadaan differointisäännöt ∆(f (n) ± g(n)) = ∆f (n) ± ∆g(n), ∆c = 0 (c on vakio), ∆(f (n)g(n)) = g(n + 1)∆f (n) + f (n)∆g(n), f (n) g(n)∆f (n) − f (n)∆g(n) ∆ = g(n) g(n)g(n + 1) (mutta ei kuitenkaan Ketjusääntöä eikä käänteisfunktion differointisääntöä). Näistä saadaan edelleen välittömästi summaussäännöt (f (n) ± g(n))δn = f (n)δn ± g(n)δn, cf (n)δn = c f (n)δn, f (n)∆g(n)δn = f (n)g(n) − g(n + 1)∆f (n)δn (osittaussummaus). Alkeisfunktioiden joukossa potenssifunktiot, eksponenttifunktio ja logaritmit ovat keskeisiä (esimerkiksi integroinnissa, kuten edellisessä luvussa todettiin). Nämä eivät kuitenkaan käyttäydy differoidessa samoin kuin jatkuvat vastineensa ja korvautuvatkin summauslaskennassa toisilla funktioilla: • Potenssifunktion na vastine p(n, a), missä a on kokonaisluku, toteuttaa differenssiyhtälön ∆p(n, a) = ap(n, a − 1)
LUKU 8. SUMMAUS JA KERTOMINEN
97
sekä lisäksi ehdot p(n, 0) = 1 ja p(0, a) = 0, jos a > 0. Tällainen funktio ei-negatiivisille a:n arvoille on Pykälässä 3.6 jo esiintynyt Pochhammerin symboli p(n, a) = na = n(n − 1) · · · (n − a + 1). (Erityisesti sovitaan, että n0 = 1 ja n1 = n.) Negatiivisille ”eksponentin” arvoille määrittelyä jatketaan sopivasti: n−a =
1 . (n + 1)(n + 2) · · · (n + a)
Tässäkin tapauksessa differointi antaa tutun tuloksen, kuten on helppo havaita. Ja mukavinta on, että tuttu potenssilaskenta pätee sentään jossain muodossa: na+b = na (n − a)b . (Totea!) Huomautus. On toinenkin Pochhammerin symboli na = n(n + 1) · · · (n + a − 1), jolla on oma käyttönsä, ks. Pykälä 8.3. Sitäpaitsi, ilmeisesti na = ((n − 1)−a )−1 . • Eksponenttifunktion en vastine e(n) toteuttaa differenssiyhtälön ∆e(n) = e(n) ja lisäehdon e(0) = 1. Tällainen funktio on tietysti e(n) = 2n . Yleisemmin ∆an = (a − 1)an . • Logaritmin ln n vastine H(n) toteuttaa differenssiyhtälön ∆H(n) =
1 . n+1
(Että miksikö 1/(n + 1) eikä 1/n? No siksi, että logaritmin ln x derivaatta on x−1 , joten H(n):n differenssin pitää vastaavasti olla n−1 .) Eräs sopiva funktio on tietysti n 1 , H(n) = m m=1
ns. harmoninen funktio. H(n) ja ln n ovat asymptoottisesti aika lähellä toisiaan, sillä lim (H(n) − ln n) = γ = 0.5772156649 . . .
n→∞
(Eulerin vakio).
(Ei ole kovin vaikea näyttää, että ko. raja-arvo on äärellisenä olemassa, ks. myös Pykälä 7.4.) Jossain mielessä parempi valinta olisikin H(n) − γ = Ψ(n − 1), missä Ψ(x) = D(ln Γ(x)) on ns. digammafunktio (ks. Pykälä 8.2). Harmonista funktiota ei muuten saa summatuksi miksikään ”tutummaksi” funktioksi.
LUKU 8. SUMMAUS JA KERTOMINEN
98
Näistä määrittelyistä saadaan seuraavat perusdifferoinnit ja -summaukset: ∆na = ana−1
ja
∆H(n) = n−1
ja
∆an = (a − 1)an
ja
1 na+1 (a = −1), a+1 n−1 δn = H(n), 1 n an δn = a (a = 1). a−1 na δn =
(Ensimmäisestä muuten saadaan edelleen aritmeettisen sarjan summa, keskimmäisestä harmonisen ja viimeisestä geometrisen.) Huomautus. Summausta koskien saadaan oma Liouvillen periaatteensa, ns. Rosenlichtin lause2 , sekä Rischin integrointia vastaava ns. Karrin algoritmi2 . (Jolloin tarvitaan ns. differenssikunta.) Tämä lähestymistapa vaan ei ole kuitenkaan osoittautunut yleisesti kovinkaan hedelmälliseksi. Poikkeuksena on rationaalifunktioiden summaus di- ja polygammafunktioiksi. Usein parempi menettely on ns. Gosperin summaus, joka taas pohjautuu hypergeometristen termien käyttöön (ks. Pykälä 8.3).
8.2
Rationaalifunktioiden summaus
Rationaalifunktioiden summaus polynomeiksi ja ns. polygammafunktioiksi on kauan tunnettu. Ensimmäinen askel rationaalifunktion p1 (n) p2 (n) summaamiseksi on jakaa osoittaja nimittäjällä sekä supistaa pois yhteiset tekijät: p1 (x) r(x) = p(x) + , p2 (x) q(x) missä p(x) on polynomi, deg(r(x)) < deg(q(x)) ja syt(r(x), q(x)) = 1. Lisäksi voidaan olettaa, että q(x) on pääpolynomi. Näin summattavaksi jää polynomi p(n) sekä aito rationaalifunktio r(n)/q(n). Edellisestä tulee tuloksena polynomi ja jälkimmäisestä polygammafunktioiden summa. Katsotaan nämä erikseen. Polynomien summaus Polynomien summauksessa käytetään sitä tietoa, että
na δn =
1 na+1 a+1
(a ≥ 0).
Näin riittää lausua polynomi p(n) (= 0) Pochhammerin symbolien lineaariyhdelmänä. Tämä on aina mahdollista, koska kiinteälle ei-negatiiviselle a:n arvolle xa on astetta a oleva x:n pääpolynomi. Esityksen Pp(x) antaa seuraava algoritmi: 2
Alkuperäisviitteet ovat ROSENLICHT, M.: Liouville’s Theorem on Functions with Elementary Integrals. Pacific Journal of Mathematics 24 (1968), 153–161 ja K ARR , M.: Summation in Finite Terms. Journal of the ACM 28 (1981), 305-350.
LUKU 8. SUMMAUS JA KERTOMINEN
99
Polynomin Pochhammerin esitys: 1. Jos syötepolynomi p(x) on vakio a, asetetaan Pp(x) ← ax0 , tulostetaan Pp(x) ja lopetetaan. 2. Jos p(x) ei ole vakio, asetetaan Pp(x) ← am xm + P(p(x) − am xm ), missä am on p(x):n johtava kerroin ja m sen aste. Algoritmissa oleva rekursio päättyy, sillä p(x) − am xm :n aste on pienempi kuin p(x):n. Jos nyt p(x):n Pochhammerin esitys on Pp(x) = bm xm + bm−1 xm−1 + · · · + b1 x1 + b0 x0 , niin ilmeisesti p(n)δn = (bm nm + bm−1 nm−1 + · · · + b1 n1 + b0 n0 )δn = bm nm δn + bm−1 nm−1 δn + · · · + b1 n1 δn + b0 n0 δn =
bm m+1 bm−1 m b1 + n n + · · · + n 2 + b0 n 1 . m+1 m 2
Näin polynomin summauksen suurimman työn vaatii konversio Pochhammerin esitykseen ja tarvittaessa takaisin summauksen jälkeen. Polygammaosan summaus Polygammaosa tulee summattaessa r(n) , q(n) missä deg(r(x)) < deg(q(x)), syt(r(x), q(x)) = 1 ja q(x) on pääpolynomi. Tällöin jaetaan nimittäjä 1. asteen tekijöihin sopivassa kuntalaajennuksessa (tai neliöttömiin tekijöihin jakoa käyttäen symbolisesti) q(x) = (x − b1 )k1 (x − b2 )k2 · · · (x − bm )km ja kehitetään r(x)/q(x) osamurroiksi kuten Pykälässä 5.4: p(x) a11 a12 a1k1 = + + ··· + 2 q(x) x − b1 (x − b1 ) (x − b1 )k1 a21 a22 a2k2 + + + ··· + 2 x − b2 (x − b2 ) (x − b2 )k2 + ··· am1 am2 amkm + + + ··· + . 2 x − bm (x − bm ) (x − bm )km Näin riittää summata muotoa
1 (n − b)k
LUKU 8. SUMMAUS JA KERTOMINEN
100
olevat rationaalifunktiot, missä k ≥ 1. Näiden summat ovat lausuttavissa polygammafunktioiden avulla. Itse asiassa eräs esimerkki tällaisesta oli jo 1/n:n summaaminen harmonisen funktion tai digammafunktion avulla. Digammafunktio Ψ(x) = D(ln Γ(x)) kun on eräs polygammafunktio. Yleisesti n:s polygammafunktio on Ψ(n, x) = Dn+1 (ln Γ(x)) = Dn Ψ(x) = DΨ(n − 1, x), ja Ψ(x) = Ψ(0, x). Polygammafunktiot ovat paljon käytettyjä erikoisfunktioita ja mm. niiden numeeriset arvot ovat laskettavissa nopeilla algoritmeilla, ks. esimerkiksi A BRAMOWITZ & S TEGUN . Alla on Maple-ohjelmiston piirtämät kuvat funktioista Ψ(3, x), Ψ(1, x), Ψ(x), Ψ(2, x) ja Ψ(4, x), tässä järjestyksessä vasemmalla ylhäältä alas. 14 12 10 y8 6 4 2 0 –2 –4 –6 –8 –10 –12 –14
2 4 6 8 101214 x
Koska D(x + 1) = 1, on Ketjusäännön nojalla Ψ(k − 1, x + 1) = DΨ(k − 2, x + 1) · 1 = D(Ψ(k − 2, x + 1)) = ··· = Dk (ln Γ(x + 1)) = Dk (ln(xΓ(x))) = Dk (ln x + ln Γ(x)) = Dk ln x + Ψ(k − 1, x) 1 = (−1)k−1 (k − 1)! k + Ψ(k − 1, x). x Toistamalla tätä saadaan Ψ(k − 1, x + n) = (−1)
k−1
(k − 1)!
n−1 i=0
1 + Ψ(k − 1, x). (x + i)k
(Tämä toimii, jos x ei ole negatiivinen kokonaisluku eikä nolla. Jos x on negatiivinen kokonaisluku tai nolla, pitää summaus aloittaa arvosta i = 1 − x.) Viimeinen termi Ψ(k − 1, x) voidaan tulkita summausvakioksi, jolloin tästä saadaan edelleen summauskaava 1 (−1)k−1 δn = Ψ(k − 1, x + n). (x + n)k (k − 1)! Näin ollen erikoisesti valitsemalla x = −b saadaan haluttu summauskaava 1 (−1)k−1 δn = Ψ(k − 1, n − b). (n − b)k (k − 1)! Menettelyn haittapuolena on osamurtoihinjaon hyvin usein vaatima suuri laskenta.
LUKU 8. SUMMAUS JA KERTOMINEN
101
Rationaalisen osan summaus Osa polygammafunktioista voi yhdistyä rationaalifunktioksi (ns. rationaalinen osa). Tätä voidaan etsiä suoraankin seuraavanlaisella Hermiten menetelmän muunnelmalla. Yleisesti määritellään funktion f (x) a:s Pochhammerin potenssi seuraavasti: f a (x) = f (x)f (x − 1) · · · f (x − a + 1), jos a ≥ 0. (Ei pidä sekoittaa Pochhammerin symboliin f (x)a !) Funktion f (x) Pochhammerin neliö on näin ollen f 2 (x) = f (x)f (x − 1). Polynomi on Pochhammer-neliötön, jos sillä ei ole tekijänään (yksiköitä lukuunottamatta) minkään polynomin Pochhammerin neliötä. Lausetta 5.11 vastaava tulos pätee: Lause 8.2. UFD:n polynomirenkaan primitiivinen polynomi p(x) on Pochhammer-neliötön tarkalleen silloin, kun syt(p(x), ∆p(x)) = 1. (Huomaa, että syt(p(x), ∆p(x)) = syt(p(x), p(x + 1) − p(x)) = syt(p(x), p(x + 1)).) Todistus. Jos q(x)2 (x) jakaa p(x):n, niin p(x) on muotoa p(x) = q(x)q(x − 1)s(x) ja ∆p(x) = q(x + 1)q(x)s(x + 1) − q(x)q(x − 1)s(x), mistä nähdään, että q(x) jakaa tällöin ∆p(x):n ja siis myös syt(p(x), ∆p(x)):n. Näin ollen, jos q(x) ei ole yksikkö, ei sitä ole myöskään syt(p(x), ∆p(x)). Toisaalta, jos p(x) on Pochhammer-neliötön ja syt(p(x), ∆p(x)) = d(x), niin p(x):n alkutekijöihinjako on muotoa p(x) = q1 (x)q2 (x) · · · qk (x), ja ellei d(x) ole yksikkö, niin sen alkutekijät ovat tässä mukana. Asia on selvä, jos d(x) on yksikkö, joten oletetaan, että se ei sitä ole. Ilmeisesti p(x + 1):n tekijöihinjako on p(x + 1) = q1 (x + 1)q2 (x + 1) · · · qk (x + 1) ja jokin näistä alkutekijöistä, sanotaan qi (x + 1), on myös d(x):n tekijä ja näin ollen edelleen p(x):n tekijä. Siispä on sellainen j, että qj (x) = qi (x + 1). Näin p(x):llä on tekijänään Pochhammerin neliö qi (x+1)qi (x), josta seuraa ristiriita. (Huomaa, että koska p(x) on primitiivinen, sillä ei ole alkutekijöinään vakiopolynomeja. Näin ollen ei voi olla qi (x) = qj (x) = qi (x + 1), koska silloinhan qi (x) olisi vakio.) Ristiriita näyttää, että d(x):n on oltava yksikkö (ja yksikkönormaalina edelleen = 1). Seuraava algoritmi laskee polynomin jaon Pochhammer-neliöttömiin tekijöihin: Pochhammer-neliöttömiin tekijöihin jako primitiiviselle polynomille: 1. Asetetaan L ← NULL (tyhjä jono). 2. Lasketaan syt(p(x), p(x − 1)) ja asetetaan d(x) ← syt(p(x), p(x − 1)) ja
r(x) ←
p(x) . d(x)
LUKU 8. SUMMAUS JA KERTOMINEN
102
3. Jos d(x) on vakio, tulostetaan L, r(x) ja lopetetaan. 4. Jos d(x) ei ole vakio, lasketaan s(x) = syt(d(x + 1), r(x)) sekä asetetaan L ← L, r(x)/s(x) ,
d(x) ←
d(x + 1) s(x)
ja r(x) ← s(x).
Mennään kohtaan 3. Algoritmi on toiminnaltaan hyvin samantapainen kuin Pykälässä 3.7:ssä oleva. Tuloksena polynomi p(x) on muodossa p(x) = q11 (x)q22 (x)q33 (x) · · · qkk (x) missä q1 (x), q2 (x), . . . , qk (x) ovat Pochhammer-neliöttömiä primitiivisiä polynomeja (mahdollisesti = 1). Jos p(x) on neliötön tai neliöttömän polynomin potenssi, tiedetään lisäksi, että qii (x):t ovat keskenään jaottomia (i = 1, 2, . . . , k). Tällöin p(x):n juuret ovat kaikki samaa kertalukua. q1 (x):ssä ovat ne p(x):n tekijät x − b, joille x ± 1 − b ei ole tekijä. q2 (x):ssä ovat ne tekijät x − b, joille myös x − 1 − b on tekijä, mutta x − 2 − b ja x + 1 − b eivät ole. Jne. Edelleen, jos p(x) on neliöttömän polynomin potenssi, tiedetään vielä, että syt(qi (x), qi (x − j)) = 1 (j = 1, 2, . . . , i − 1). Jos nimittäin olisi syt(qi (x), qi (x − j)) = 1, niin s.y.t.:llä olisi juuri b ja tekijä x − b. Näin ollen qi (x):llä olisi tekijät x − b ja x + j − b. p(x):llä olisi siis tekijänä (x − b)i ja (x + j − b)i ja näin myös (x + j − b)i+j , mikä ei käy. Hermiten summausmenetelmä: 1. Suoritetaan nimittäjän q(x) jako ”tavallisiin” neliöttömiin tekijöihin q(x) = q1 (x)q2 (x)2 q3 (x)3 · · · qk (x)k (ks. Pykälä 5.7). Nämä tekijät ovat keskenään jaottomia. 2. Jaetaan kukin neliötön tekijä qi (x) Pochhammer-neliöttömiin tekijöihin eo. algoritmilla. Sama jako pätee potensseille qi (x)i . Yhdistämällä nämä saadaan q(x):n jako keskenään jaottomiin Pochhammerin potenssia oleviin tekijöihin: t
t
t
q(x) = s11 (x)s22 (x) · · · sl l (x). 3. Jaetaan r(x)/q(x) osamurtoihin käyttäen kohdan 2. antamaa q(x):n jakoa (ks. Pykälä 5.4): r(x) a2 (x) al (x) a1 (x) + t2 + · · · + tl = t1 . tl t1 t2 s1 (x) s2 (x) s1 (x)s2 (x) · · · sl (x) s1 (x) t
Rationaalista osaa tulee silloin niistä osamurroista ai (x)/sii (x), joissa ti ≥ 2. Käydään ne läpi yksi kerrallaan. 4. Kuten yllä todettiin, nyt tiedetään, että syt(si (x), si (x − j)) = syt(si (x − j), si (x) − si (x − j)) = 1 (j = 1, 2, . . . , ti − 1). Etsitään Bezout’n muoto arvolle j = ti − 1 (muita j:n arvoja tarvitaan myöhemmin): 1 = ci (x)si (x − ti + 1) + di (x)(si (x) − si (x − ti + 1)).
LUKU 8. SUMMAUS JA KERTOMINEN
103
5. Osittaissummataan: ai (n)(ci (n)si (n − ti + 1) + di (n)(si (n) − si (n − ti + 1))) ai (n) δn = δn ti t si (n) sii (n) ai (n)ci (n) 1 = δn − ai (n)di (n)∆ δn t −1 t −1 sii (n) sii (n − 1) ai (n)ci (n) ∆(ai (n)di (n)) ai (n)di (n) = δn − + δn t −1 t −1 t −1 sii (n) sii (n − 1) sii (n) ai (n)ci (n) + ∆(ai (n)di (n)) ai (n)di (n) = δn − ti −1 . ti −1 si (n) si (n − 1) Koska si (x):n Pochhammerin eksponentti on laskenut yhdellä, voidaan näin jatkaa, kunnes se on = 1. Silloin loput summat siirtyvätkin polygammaosaan. Huomautus. Tämä menetelmä ei yleensä ottaen saa summaa muotoon, jossa on vähiten polygammafunktioita, vaan tähän tarvitaan lisäksi polygammafunktioiden laskusääntöjä. Se kuitenkin löytää keskeisen rationaalisen osan.
8.3
Hypergeometrinen summaus. Gosperin algoritmi
Gosperin algoritmi3 sopii tapauksiin, joissa summattavassa lausekkeessa on Pochhammerin symboleita, kertomia, binomikertoimia ja potensseja. Summaus tapahtuu sangen yleisessä lausekeluokassa, ns. hypergeometrisissa termeissä4 , ts. muotoa ak · · · akm z k a1 , . . . , am F z = 1 b 1 , . . . , bn bk1 · · · bkn k! k olevissa termeissä, missä on käytössä se toinen Pochhammerin symboli xk = x(x + 1) · · · (x + k − 1). Tässä on sallittua, että m = 0 tai/ja n = 0 (tyhjä tulo). Voit todeta, että esimerkiksi binomikertoimet, Pochhammerin symbolit, kertomat ja potenssit ovat hypergeometrisia termejä: x 1, −x 1, 1 −x k −1 , x =F −1 , n! = F 1 =F k k k n ja
n
a =F
1
a
. n
Hypergeometristen termien summausprobleemaa kutsutaan hypergeometriseksi summaukseksi. Summausmuuttujana on tällöin k, muut esiintyvät suureet ovat parametrejä. Ts. kun on annettu parametrit a1 , . . . , am , b1 , . . . , bn sekä z, on selvitettävä onko 3
Alkuperäisviite on G OSPER , W.R.: Decision Procedure for Indefinite Hypergeometric Summation. Procee˘ & W ILF dings of the National Academy of Sciences of the USA 73 (1978), 40–42. Ks. myös mainio P ETKOV SEK & Z EILBERGER , joka on saatavana verkossakin. 4 Nimitys tulee siitä, että näistä termeistä muodostettu potenssisarja on ns. hypergeometrisen funktion Maclaurinin sarja. a1 , . . . , am ja b1 , . . . , bn ovat funktion parametrejä. Sopivasti parametrejä valitsemalla saadaan valtava joukko funktioita, niin alkeis- kuin erikoisfunktioitakin. Lisäksi hypergeometristen funktioiden joukolle on tavattoman paljon laskusääntöjä, ks. esimerkiksi G RAHAM & K NUTH & PATASHNIK .
LUKU 8. SUMMAUS JA KERTOMINEN
F
a1 , . . . , am b 1 , . . . , bn
104
z
δk = cF k
A1 , . . . , AM B1 , . . . , BN
Z k
joillekin parametrien A1 , . . . , AN , B1 , . . . , BM sekä Z arvoille ja jollekin vakion c arvolle, vai ei, ja positiivisessa tapauksessa etsittävä nämä arvot. Merkitään lyhyyden vuoksi a1 , . . . , am A1 , . . . , AM t(k) = F z ja T (k) = F Z . b 1 , . . . , bn B1 , . . . , BN k k Jos summaus onnistuu, on ∆(cT (k)) = cT (k + 1) − cT (k) = t(k). Nyt
t(k + 1) (k + a1 )(k + a2 ) · · · (k + am )z = . t(k) (k + b1 )(k + b2 ) · · · (k + bn )(k + 1)
Algoritmin ensimmäinen tehtävä on kirjoittaa tämä muotoon t(k + 1) p(k + 1) q(k) = , t(k) p(k) r(k + 1) missä p(x), q(x) ja r(x) ovat polynomeja, ja q(x) ja r(x) toteuttavat seuraavan ehdon: (∗) Jos α on q(x):n juuri ja β on r(x):n juuri, niin β − α ei ole positiivinen kokonaisluku. Tämän tarkoitus on vain saada t(k + 1)/t(k) kirjoitettua jatkoa ajatellen mukavaan muotoon. Se käy seuraavasti: 1. Asetetaan p(x) ← 1, q(x) ← (x + a1 )(x + a2 ) · · · (x + am )z ja r(x) ← (x + b1 − 1)(x + b2 − 1) · · · (x + bn − 1)x. 2. Jos ehto (∗) toteutuu, on asia selvä ja lopetetaan. 3. Jos ehto (∗) ei toteudu, on q(x):llä tekijä x − α ja r(x):llä tekijä x − β, joille β − α = u on positiivinen kokonaisluku. Asetetaan p(x) ← p(x)(x − α − 1)u−1 = p(x)(x − α − 1)(x − α − 2) · · · (x − β + 1), q(x) q(x) ← ja x−α r(x) . r(x) ← x−β Huomaa, että silloin
Mennään kohtaan 2.
p(x + 1)(x − α) p(x + 1) ← . p(x) p(x)(x − β + 1)
LUKU 8. SUMMAUS JA KERTOMINEN
105
Menettely pysähtyy, sillä q(x):n ja r(x):n aste laskee aina joka kierroksella yhdellä. Seuraavaksi kirjoitetaan tentatiivisesti cT (k) muotoon cT (k) =
r(k)s(k)t(k) p(k)
Tämähän on aina mahdollista, valitsemalla s(k) sopivasti. cT (k) toteuttaa (jos se vain on olemassa!) rekursiokaavan cT (k + 1) − cT (k) = t(k) eli s(k) toteuttaa rekursiokaavan p(k) = q(k)s(k + 1) − r(k)s(k). Nyt riittää löytää sellainen s(x), joka toteuttaa vastaavan ”jatkuvan” rekursiokaavan p(x) = q(x)s(x + 1) − r(x)s(x). T (k + 1)/T (k) on k:n rationaalifunktio, joten samoin on r(k)s(k) T (k) = T (k + 1) − T (k) p(k) ja edelleen s(k). Kirjoitetaan (edelleen tentatiivisesti) s(x) =
f (x) g(x)
missä f (x) ja g(x) ovat polynomeja ja syt(f (x), g(x)) = 1. Mutta itse asiassa s(x) on polynomi. Asia on selvä, jos g(x) on vakio. Tehdään vastaoletus: g(x) ei ole vakio. Valitaan suurin sellainen positiivinen kokonaisluku v, että β ja β − v + 1 ovat molemmat g(x):n juuria jollekin luvulle β. (Tällainen v on tietysti olemassa, jossei muuten, niin v = 1.) Kirjoitetaan nyt s(x):n rekursiokaava muotoon p(x)g(x + 1)g(x) = q(x)f (x + 1)g(x) − r(x)g(x + 1)f (x). Kun asetetaan x = β ja x = β − v, saadaan r(β)g(β + 1)f (β) = 0 ja
q(β − v)f (β − v + 1)g(β − v) = 0.
Tässä f (β) = 0 ja f (β − v + 1) = 0, sillä g(x):llä ja f (x):llä ei ole yhteisiä juuria (muutoin niiden s.y.t. ei olisi = 1). Toisaalta myös g(β + 1) = 0 ja g(β − v) = 0, sillä muussa tapauksessa g(x):llä olisi juurena joko β + 1 tai β − v. Tämä ei ole mahdollista, sillä v valittiin suurimmaksi mahdolliseksi. Edelleen r(β) = q(β − v) = 0 on ristiriidassa ehdon (∗) kanssa, joten r(β) = 0 tai q(β − v) = 0. Ristiriita osoittaa vastaoletuksen vääräksi, joten, jos s(x) on olemassa, se on polynomi. Näin tehtävänä on etsiä polynomi s(x) tai todeta, ettei sellaista ole olemassa. Asia olisi helppo, jos s(x):n enimmäisaste vain tunnettaisiin: Sijoitetaan määräämättömin kertoimin varustettu s(x) rekursiokaavaan p(x) = q(x)s(x + 1) − r(x)s(x) ja ratkaistaan kertoimet. (Jollei kertoimia löydy, ei hypergeometrinen summaus onnistu.)
LUKU 8. SUMMAUS JA KERTOMINEN
106
Jotta saataisiin s(x), pitää sen aste siis ensin selvittää. Kirjoitetaan tätä varten s(x):n rekursiokaava vielä muotoon 2p(x) = Q(x)(s(x + 1) + s(x)) + R(x)(s(x + 1) − s(x)), missä Q(x) = q(x) − r(x) ja
R(x) = q(x) + r(x).
Nyt, jos s(x):n aste on d, niin summan s(x + 1) + s(x) aste on myös d, kun taas differenssin s(x + 1) − s(x) aste on d − 1. (Oletetaan nollapolynomin asteeksi −1.) Kaksi mahdollisuutta: • deg(Q(x)) ≥ deg(R(x)). Silloin deg(p(x)) = deg(Q(x)) + d, josta saadaan kysytty aste: d = deg(p(x)) − deg(q(x) − r(x)). • deg(Q(x)) < deg(R(x)) = δ. Silloin voidaan kirjoittaa Q(x) = αxδ−1 + · · · ,
R(x) = βxδ + · · ·
ja
s(x) = γxd + · · · ,
missä β, γ = 0, jolloin (muista binomikaava) s(x + 1) + s(x) = 2γxd + · · ·
ja
s(x + 1) − s(x) = dγxd−1 + · · ·
ja 2p(x) = (2γα + βdγ)xd+δ−1 + · · · . Taas kaksi mahdollisuutta: – 2α + βd = 0. Silloin deg(p(x)) = d + δ − 1 eli
d = deg(p(x)) − deg(q(x) + r(x)) + 1.
– 2α + βd = 0 eli d = −2α/β. Silloin deg(p(x)) < d + δ − 1 eli
d > deg(p(x)) − deg(q(x) + r(x)) + 1.
Tämä tapaus luonnollisesti ei tule kysymykseen, ellei −2α/β ole kokonaisluku ja vähintään deg(p(x)) − deg(q(x) + r(x)) + 2. Varsinainen algoritmi on sitten seuraava: Gosperin summausalgoritmi: 1. Kirjoitetaan t(k + 1)/t(k) muotoon t(k + 1) p(k + 1) q(k) = , t(k) p(k) r(k + 1) missä ehto (∗) toteutuu, edellä esitetyllä menetelmällä. 2. Jos deg(q(x) − r(x)) ≥ deg(q(x) + r(x)), niin asetetaan d ← deg(p(x)) − deg(q(x) − r(x)).
LUKU 8. SUMMAUS JA KERTOMINEN
107
3. Jos deg(q(x) − r(x)) < deg(q(x) + r(x)), niin etsitään q(x) − r(x):n johtava kerroin α sekä q(x) + r(x):n johtava kerroin β. 3.1 Jos −2α/β ei ole vähintään deg(p(x)) − deg(q(x) + r(x)) + 2 oleva kokonaisluku, asetetaan d ← deg(p(x)) − deg(q(x) + r(x)) + 1. 3.2 Jos −2α/β on vähintään deg(p(x)) − deg(q(x) + r(x)) + 2 oleva kokonaisluku, asetetaan d ← −2α/β. 4. Sijoitetaan määräämättömin kertoimin varustettu tarkalleen d-asteinen polynomi s(x) rekursiokaavaan p(x) = q(x)s(x + 1) − r(x)s(x) ja ratkaistaan sen kertoimet. Ellei ratkaisua ole, tulostetaan ”EI HYPERGEOMETRISTA SUMMAA” ja lopetetaan. Muutoin tulostetaan r(k)s(k)t(k) p(k) ja lopetetaan.
8.4
Tulo
Kuten summaus, myös tulo koskee kokonaisluvuille määriteltyjä funktioita f (n). Tavallinen tulo on muotoa b f (n) = f (a)f (a + 1) · · · f (b). n=a
Kyseessä on ns. määrätty tulo (vrt. määrätty integraali tai määrätty summa). Määräämätöntä summaa/integraalia5 vastaa ns. määräämätön tulo f (n)ρn, missä ρn on integraalin differentiaalia dx tai summan differenssiä δn vastaava merkinnällinen lausekkeen osa. Määräämätön tulo määritellään ottamalla käyttöön derivaattaa/differenssiä vastaava operaatio, ns. suhde: F (n + 1) RF (n) = . F (n) (Kyseessä on ns. etenevä suhde, takeneva suhde on F (n)/F (n−1) ja se olisi yhtä käyttökelpoinen.) Määräämätön tulo f (n)ρn tarkoittaa kollektiivisesti funktioita F (n), jotka toteuttavat yhtälön RF (n) = f (n). Koska ainoat funktiot, joiden suhde on yksi, ovat vakiofunktiot, on määräämätön tulo näin yksikäsitteinen vakiokertojaa vaille (aivan kuten määräämätön integraali on yksikäsitteinen integrointivakiota vaille ja määräämätön summa on yksikäsitteinen summausvakiota vaille). 5
On olemassa myös tuloa tarkasti vastaava integraali, ns. tulointegraali, ks. esimerkiksi D OLLARD , J.D.& F RIEDMAN , C.N.: Product Integration with Applications to Differential Equations. Addison–Wesley (1979).
LUKU 8. SUMMAUS JA KERTOMINEN
108
Funktion f (n) kertominen tarkoittaa yleisesti sen määräämättömän tulon F (n) = (C) f (n)ρn löytämistä. Jos F (n) tunnetaan, saadaan sen avulla laskettua kaikki f (n):n määrätyt tulot: Lause 8.3. (Kertolaskennan peruslause) Jos F (n) = f (n)ρn, niin b+1
F (b + 1)
f (n) = = F (n) F (a) n=a b
a
Todistus. Ilmeisesti b b b F (b + 1) F (n + 1) = = RF (n) = f (n). F (a) F (n) n=a n=a n=a
Tämän lauseen mukaisesti on luonnollista merkitä b
f (n)ρn =
n=a
kun b ≥ a
f (n) ,
n=a
ja b
b−1
f (n)ρn =
n=a
a
−1 f (n)ρn
,
kun b ≤ a.
n=b
Kertolaskennan peruslause tulee tällöin ”tuttuun” muotoon
b F (b)
f (n)ρn = = F (n). F (a) n=a b
a
Huomaa, että
n−1 m=a
f (m) =
n
f (m)ρm
m=a
on aina eräs f (n):n määräämätön tulo. Kaksi tavallisinta tulokaavaa ovat (n + a)ρn = Γ(n + a) (a on vakio). a ρn = an ja Edellinen on ilmeinen ja jälkimmäinen seuraa gammafunktion laskukaavasta Γ(n + a + 1) = (n + a)Γ(n + a) eli RΓ(n + a) = n + a. Derivointisääntöjä ja differointisääntöjä vastaten saadaan suhdesäännöt: R(f (n)g(n)±1 ) = (Rf (n))(Rg(n))±1 , Rc = 1 (c = 0 on vakio), R(f (n)c ) = (Rf (n))c (c on vakio), R(f (n)g(n) ) = (Rf (n))g(n+1) f (n)∆g(n) ,
LUKU 8. SUMMAUS JA KERTOMINEN
109
ja näistä edelleen kertosäännöt
±1 f (n)ρn g(n)ρn , f (n)g(n)±1 ρn = c f (n)ρn , f (n)c ρn =
f (n)g(n) f (n)∆g(n) ρn = (Rf (n))g(n+1) ρn
(osittaiskertominen).
Lisäksi saadaan kertosäännöt, jotka liittävät summan ja tulon toisiinsa: af (n) ρn = a f (n)δn , loga f (n)δn = loga f (n)ρn (jälkimmäinen on ilmeinen, edellinen saadaan vaikkapa osittaiskertomisella). Huomautus. Varsinaisia vahvoja kertoalgoritmeja ei oikeastaan tunneta. Periaatteessa kertominen voidaan aina palauttaa summaukseen yo. kaavoilla, mutta se johtaa usein hankaliin summauksiin. Huomaa kuitenkin, että rationaalifunktioiden tulo on aina periaatteessa helppo muodostaa yo. säännöillä jakamalla sen osoittaja ja nimittäjä 1. asteen tekijöihin (kuntalaajennuksilla tai neliöttömiin tekijöihin jaon jälkeen symbolisesti). Tämä tietysti voi olla suuritöinen tehtävä.
Luku 9 LINEAARISET REKURSIOKAAVAT 9.1
Yleistä
Rekursiokaavoja käytetään määrittelemään (luku)jonoja lähtien tietyistä jonon alkupään termeistä, ns. alkuarvoista. Lineaarinen rekursiokaava on muotoa f (n + k) = c1 (n)f (n + k − 1) + c2 (n)f (n + k − 2) + · · · + ck (n)f (n) + g(n) oleva rekursiokaava. Se määrittelee jonon f (0), f (1), f (2), · · · , kun kerroinfunktiot c1 (n), · · · , ck (n) ja pakkofunktio g(n) tunnetaan ja alkuarvot f (0), . . . , f (k − 1) on annettu. k on rekursiokaavan kertaluku. Jonon f (0), f (1), f (2), · · · sanotaan toteuttavan rekursiokaavan. Jos g(n) on nollafunktio, sanotaan rekursiokaavaa homogeeniseksi, muuten epähomogeeniseksi. Välittömästi nähdään lineaaristen rekursiokaavojen kolme perusominaisuutta, jotka vastaavat lineaaristen differentiaaliyhtälöiden ominaisuuksia: • Jos jonot f1 (0), f1 (1), . . . ja f2 (0), f2 (1), . . . toteuttavat saman lineaarisen homogeenisen rekursiokaavan, niin myös summajono f1 (0) + f2 (0), f1 (1) + f2 (1), . . . toteuttaa tämän rekursiokaavan. • Jos jono f (0), f (1), f (2), · · · toteuttaa tietyn lineaarisen homogeenisen rekursiokaavan ja C on vakio, niin myös C:llä kerrottu jono Cf (0), Cf (1), . . . toteuttaa tämän rekursiokaavan. • Jos jonot f1 (0), f1 (1), . . . ja f2 (0), f2 (1), . . . toteuttavat tietyn lineaarisen rekursiokaavan, niin erotusjono f1 (0) − f2 (0), f1 (1) − f2 (1), . . . toteuttaa vastaavan homogeenisen rekursiokaavan. Rekursiokaava, joka ei ole lineaarinen, on epälineaarinen. Epälineaaristen rekursiokaavojen (+ alkuarvojen) ratkaiseminen siinä mielessä, että saataisiin lauseke f (n):lle, on vaikeaa ja usein mahdotonta. Ratkaisu vaatii yleensä onnistuessaan tehtävälle ominaisia erikoismenetelmiä. Ks. G REENE & K NUTH ja G RAHAM & K NUTH & PATASHNIK . Myöskään yleisen lineaarisen rekursiokaavan ratkaisu tässä mielessä ei ole helppoa. Toisaalta usein on tarpeen esimerkiksi vain saada lasketuksi nopeasti f (n) jo(i)llekin n:n arvo(i)lle. Jatkossa rajoitutaankin lineaarisiin rekursiokaavoihin, jotka voidaan ratkaista, ainakin jossain mielessä. Monia epälineaaristen ja muunkinlaisten rekursiokaavojen ratkaisumenetelmiä löytyy ym. viitteistä.
110
LUKU 9. LINEAARISET REKURSIOKAAVAT
9.2
111
Ensimmäisen kertaluvun lineaarinen rekursiokaava
Tällainen rekursiokaava on muotoa f (n + 1) = c(n)f (n) + g(n), missä c(n) ja g(n) ovat annettuja funktioita. Oletetaan, että c(n) = 0 ja merkitään −1 n 1 . c(n) = M (n) = c(n)c(n − 1) · · · c(0) i=0 M (n) on ns. summaava tekijä1 . Kerrotaan rekursiokaava puolittain M (n):llä ja merkitään h(n) = M (n − 1)f (n) ja
h(0) = f (0).
Silloin h(n + 1) = h(n) + M (n)g(n) eli
∆h(n) = M (n)g(n)
ja saadaan ratkaisukaava
h(n) =
f (0) + M (n)g(n)δn
eli
f (n) =
n−1
M (i)g(i)
i=0
(n = 0, 1, . . . ),
M (n − 1)
joka muistuttaa 1. kertaluvun lineaarisen differentiaaliyhtälön ratkaisukaavaa (ks. Pykälä 7.5). Vaikeutena ratkaisukaavan käytössä on siinä esiintyvän summan summaaminen ”suljettuun muotoon”, mikäli mahdollista; aivan kuten vastaavassa differentiaaliyhtälön ratkaisukaavassa vaikeutena on saada siinä esiintyvä integraali lasketuksi. Tietysti myös M (n):ssä oleva tulo pitäisi myös saada kerrotuksi suljettuun muotoon. Ns. hajoita–ja–hallitse-rekursiokaavat f (n) = a(n)f (n/k) + b(n) ,
f (c) = f0 ,
missä k ≥ 2 on kokonaisluku, palautuvat eo. muotoon, kun merkitään n = ck m . Silloin saadaan lineaarinen rekursiokaava jonolle F (0), F (1), . . . , missä F (m) = f (ck m ): F (m + 1) = a(ck m+1 )F (m) + b(ck m+1 ) ,
F (0) = f0 .
Tällainen on esimerkiksi Lauseen 3.19 rekursiokaava.
9.3
Vakiokertoiminen lineaarinen rekursiokaava
Kertalukua k oleva vakiokertoiminen lineaarinen homogeeninen rekursiokaava (lyhyesti LHVR) on muotoa f (n + k) = c1 f (n + k − 1) + c2 f (n + k − 2) + · · · + ck f (n) oleva rekursiokaava, missä c1 , · · · , ck ovat vakiokertoimet. Lisäksi oletetaan, että ck = 0 (muutoin ensimmäinen alkuarvo f (0) ei vaikuttaisi seuraaviin jonon termeihin). Alkuarvot ovat f (0), . . . , f (k − 1). Tällainen rekursiokaava voidaan muodostaa missä tahansa renkaassa. Vrt. 1. kertaluvun differentiaaliyhtälöiden integroiva tekijä, ks. peruskurssit. Mainittu oletus c(n) = 0 on varsin luonnollinen. Jos nimittäin esimerkiksi c(100) = 0, niin f (101) ei riipukaan lainkaan sitä jonossa edeltävistä termeistä, vaan on aina = g(100). 1
LUKU 9. LINEAARISET REKURSIOKAAVAT
112
Yo. rekursiokaavan ns. karakteristinen yhtälö on rk − c1 rk−1 − · · · − ck−1 r − ck = 0 ja yhtälön vasemmalla puolella oleva r:n polynomi on ns. karakteristinen polynomi. (Vrt. vakiokertoimisen lineaarisen differentiaaliyhtälön karakteristinen polynomi pykälässä 7.5.) Vakiokertoimisia lineaarisia rekursiokaavoja käsitellään tavallisesti käyttäen joko ns. generoivia funktioita2 ja osamurtokehitelmiä, eksponentiaalipolynomeja tai matriisiesitystä. Katsotaan ensin viimeinen tapa.
9.3.1
Matriisiesitys
Tässä tarkastellaan rekursiokaavoja kunnassa K. Rekursiokaavan f (n + k) = c1 f (n + k − 1) + c2 f (n + k − 2) + · · · + ck f (n) ns. oheismatriisi on k × k-matriisi
C=
c1 c2 1 0 0 1 .. .. . . 0 0
· · · ck−1 ck ··· 0 0 ··· 0 0 . .. .. ... . . ··· 1 0
Koska ck = 0, C on ei-singuläärinen matriisi. Kehittämällä determinantti
c1 − λ c2 · · · ck−1 ck
1 −λ · · · 0 0
1 ··· 0 0
|C − λIk | = 0
..
.. .. .. ...
.
. . .
0 0 ··· 1 −λ
viimeisen sarakkeensa mukaan nähdään, että oheismatriisin karakteristinen yhtälö on sama kuin rekursiokaavan karakteristinen yhtälö. Kertolasku osoittaa, että f (n + k − 1) f (n + k) f (n + k − 2) f (n + k − 1) = C (n = 0, 1, . . . ). .. .. . . f (n) f (n + 1) Näin ollen, jos merkitään
p=
f (k − 1) f (k − 2) .. .
ja
f (0) niin
f (n + k − 1) f (n + k − 2) .. . f (n)
2
Oleellisesti sama kuin z-muunnos.
0 .. e = . , 0 1
= Cn p
(n = 0, 1, . . . )
LUKU 9. LINEAARISET REKURSIOKAAVAT
113
ja saadaan jonon f (0), f (1), . . . ns. matriisiesitys f (n) = eT Cn p
(n = 0, 1, . . . ).
Käänteinenkin tulos pätee: Lause 9.1. Jos d ja q ovat k-vektoreita ja M ei-singuläärinen k × k-matriisi, niin jono g(n) = dT Mn q (n = 0, 1, . . . ) toteuttaa LHVR:n, jonka kertaluku on ≤ k. Todistus. Asia on selvä, jos q = 0, joten siirrytään tapaukseen q = 0. Tällöin myös Mn q = 0. Koska vektoreita q, Mq, M2 q, . . . , Mk q on k + 1 kpl, ne ovat lineaarisesti riippuvia. Valitaan pienin sellainen luku m ≥ 1, että Mm q voidaan kirjoittaa vektorien q, Mq, M2 q, . . . , Mm−1 q lineaariyhdelmänä: Mm q = am−1 Mm−1 q + · · · + a1 Mq + a0 q. Silloin a0 = 0, koska muussa tapauksessa m ei olisi pienin mahdollinen (miksei?). Kertomalla yhtälö vasemmalta dT Mn :llä saadaan haluttu rekursiokaava: g(n + m) = am−1 g(n + m − 1) + · · · + a1 g(n + 1) + a0 g(n). Koska m ≤ k, rekursiokaavan kertaluku ei ylitä k:ta. Huomautus. Yllä olevassa todistuksessa saatu rekursiokaava riippuu myös alkuvektorista q, ei pelkästään matriisista M. Ottamalla käyttöön vahvempi tulos saadaan rekursiokaava, joka ei riipu alkuvektorista q. Ns. Cayley–Hamilton-lauseen mukaan nimittäin matriisi M toteuttaa oman karakteristisen yhtälönsä (ks. kurssit Matriisilaskenta 1&2). Ts. jos matriisin M karakteristinen yhtälö on λk − c1 λk−1 − · · · − ck−1 λ − ck = 0, niin Mk − c1 Mk−1 − · · · − ck−1 M − ck Ik = Ok . Kertomalla tämä yhtälö puolittain vasemmalta dT :llä ja oikealta Mn q:lla nähdään, että g(n) toteuttaa myös kertalukua k olevan rekursiokaavan g(n + k) = c1 g(n + k − 1) + · · · + ck−1 g(n + 1) + ck g(n), joka ei riipu alkuvektorista q. (Huomaa, että ck = ±|M| = 0.) Matriisiesitystä käyttäen saadaan enemmän tai vähemmän helposti useita käyttökelpoisia tuloksia. Seuraavassa eräitä tällaisia. Matriisiesityksen avulla voidaan laskea jonon termi f (n) nopeasti. Kyseessähän on oikeastaan vain matriisipotenssin Cn (n > 0) laskeminen ja se sujuu nopeasti Venäläisten talonpoikien menetelmällä (ks. Pykälä 3.7). Matriisien lohkomista käyttäen saadaan näytetyksi eräitä rekursiokaavojen ominaisuuksia. Esitellään lohkomatriisien kertolasku, esimerkkinä 2 × 2-lohkojen tapaus: Jos matriisit A11 A12 B11 B12 A= ja B = A21 A22 B21 B22
LUKU 9. LINEAARISET REKURSIOKAAVAT
114
on lohkottu siten, että lävistäjälohkot A11 ja B11 ovat kerrottavissa ja samoin A22 sekä B22 ovat kerrottavissa, niin matriisitulon AB lohkoesitys on seuraava: A11 B11 + A12 B21 A11 B12 + A12 B22 AB = . A21 B11 + A22 B21 A21 B12 + A22 B22 Vastaava kaava pätee yleisestikin. Kertolaskukaavaa tarvitaan mm. tapauksessa, jossa A = B, lohkot A11 sekä A22 ovat neliömatriiseja ja lohko A21 on nollamatriisi O21 . Tällöin 2 A11 A11 A12 + A12 A22 2 A = O21 A222 ja jos vielä erikoisesti myös lohko A12 on nollamatriisi O12 , niin 2 A11 O12 2 A = O21 A222 ja yleisesti
n
A =
An11 O12 O21 An22
Vielä voidaan todeta, että jos vektorit e1 e= e2
.
p=
ja
p1 p2
on lohkottu kahteen osaan vastaten A:n lohkomista, niin T T A11 A12 T e A = e1 e2 = eT1 A11 eT1 A12 + eT2 A22 O21 A22
sekä Ap =
A11 A12 O21 A22
p1 p2
=
A11 p1 + A12 p2 A22 p2
ja erikoisesti (jos myös A12 = O12 ) eT A =
eT1 A11 eT2 A22
sekä Ap =
A11 p1 A22 p2
.
Lause 9.2. Jos jono f1 (0), f1 (1), . . . toteuttaa kertalukua k1 olevan LHVR:n ja jono f2 (0), f2 (1), . . . kertalukua k2 olevan LHVR:n, niin summajono f1 (0) + f2 (0), f1 (1) + f2 (1), . . . toteuttaa enintään kertalukua k1 +k2 olevan LHVR:n ja tulojono f1 (0)f2 (0), f1 (1)f2 (1), . . . enintään kertalukua k1 k2 olevan LHVR:n. Todistus. Muodostetaan jonoille matriisiesitykset: f1 (n) = eT1 Cn1 p1
ja
f2 (n) = eT2 Cn2 p2 .
Silloin summajonolle f1 (0) + f2 (0), f1 (1) + f2 (1), . . . saadaan matriisesitys T T C1 O1 n p1 f1 (n) + f2 (n) = e1 e2 O2 C2 p2
LUKU 9. LINEAARISET REKURSIOKAAVAT
115
ja sitä vastaavan LHVR:n kertaluku on Lauseen 9.1 mukaan enintään k1 + k2 . Tulojonoa koskeva tulos todistetaan matriisien ns. Kroneckerin tuloa käyttämällä. Yleisesti n1 × m1 -matriisin a11 · · · a1m1 .. .. A = ... . . an1 1 · · · an1 m1 ja n2 × m2 -matriisin B Kroneckerin tulo on n1 n2 × m1 m2 -matriisi a11 B · · · a1m1 B .. .. .. A⊗B= . . . an1 1 B · · · an1 m1 B (lohkomuoto). Lohkomatriisien kertolaskukaavasta seuraa melko välittömästi, että mikäli matriisitulot AC ja BD ovat määritellyt, niin (A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD), ja lohkomatriisin transponointikaavasta puolestaan, että (A ⊗ B)T = AT ⊗ BT . Edelleen, jos AB on määritelty, niin (A ⊗ B)n = An ⊗ Bn . Tulojonolle saadaan nyt matriisiesitys f1 (n)f2 (n) = (eT1 Cn1 p1 ) ⊗ (eT2 Cn2 p2 ) = ((eT1 Cn1 ) ⊗ (eT2 Cn2 ))(p1 ⊗ p2 ) = (eT1 ⊗ eT2 )(Cn1 ⊗ Cn2 )(p1 ⊗ p2 ) = (e1 ⊗ e2 )T (C1 ⊗ C2 )n (p1 ⊗ p2 ) ja sitä vastaavan LHVR:n kertaluku on Lauseen 9.1 mukaan enintään k1 k2 . Huomautus. Itse asiassa, kuten edelläkin, eo. lauseessa olevalle summajonolle saadaan myös nimenomaan kertalukua k1 + k2 oleva LHVR, jonka karakteristinen yhtälö on matriisin C1 O1 O2 C2 karakteristinen yhtälö. Näin ollen silloin vastaava karakteristinen polynomi on C1 :n karakteristisen polynomin ja C2 :n karakteristisen polynomin tulo. Vastaavasti tulojonolle saadaan myös nimenomaan kertalukua k1 k2 oleva LHVR, jonka karakteristinen yhtälö on matriisin C1 ⊗ C2 karakteristinen yhtälö. Toinen lohkomistekniikan antama tulos koskee tiettyjä epähomogeenisia lineaarisia vakiokertoimisia rekursiokaavoja f (n + k) = c1 f (n + k − 1) + c2 f (n + k − 2) + · · · + ck f (n) + g(n), nimittäin sellaisia, missä jono g(0), g(1), . . . toteuttaa jonkin LHVR:n.
LUKU 9. LINEAARISET REKURSIOKAAVAT
116
Lause 9.3. Jos jono f (0), f (1), . . . toteuttaa rekursiokaavan f (n + k1 ) = c1 f (n + k1 − 1) + c2 f (n + k1 − 2) + · · · + ck1 f (n) + g(n), (missä ck1 = 0) ja jono g(0), g(1), . . . puolestaan toteuttaa kertalukua k2 olevan LHVR:n, niin f (0), f (1), . . . toteuttaa myös enintään kertalukua k1 + k2 olevan LHVR:n. Todistus. Muodostetaan jonolle g(0), g(1), . . . matriisiesitys g(n) = eT2 Cn2 p2 ja merkitään c1 c2 · · · ck1 −1 ck1 f (k1 − 1) 1 0 ··· 0 0 f (k1 − 2) 0 1 ··· 0 0 sekä p = C1 = . .. 1 .. .. . . .. .. . . . . . . f (0) 0 0 ··· 1 0 Lohkomatriisiin ei nyt kelpaakaan oikeaksi k1 × k2 -matriisi 0 0 D = .. . 0
ylälohkoksi nollamatriisi, vaan siksi pitää valita ··· 0 1 ··· 0 0 . . . . .. .. . . ··· 0 0
Kertolaskulla havaitaan silloin, että f (n + k1 ) f (n + k1 − 1) f (n + k1 − 1) f (n + k1 − 2) .. .. . . C1 D f (n) f (n + 1) = O C2 g(n + k2 − 1) g(n + k2 ) g(n + k2 − 1) g(n + k2 − 2) . .. .. . g(n + 1) g(n)
.
Jos otetaan käyttöön k1 + k2 -vektorit 0 .. . 0 e = 1 ← k1 :s alkio 0 . .. 0
f (k1 − 1) f (k1 − 2) .. .
f (0) sekä p = g(k2 − 1) g(k2 − 2) .. . g(0)
,
niin saadaan jonolle f (0), f (1), . . . matriisiesitys n C1 D T f (n) = e p. O C2 Lauseen 9.1 mukaan f (0), f (1), . . . toteuttaa silloin enintään kertalukua k1 + k2 olevan LHVR:n.
LUKU 9. LINEAARISET REKURSIOKAAVAT
117
Huomautus. Jälleen eo. lauseessa olevalle jonolle f (0), f (1), . . . saadaan myös nimenomaan kertalukua k1 + k2 oleva LHVR, jonka karakteristinen yhtälö on matriisin C1 D O C2 karakteristinen yhtälö. Näin ollen vastaava karakteristinen polynomi on C1 :n karakteristisen polynomin ja C2 :n karakteristisen polynomin tulo.
9.3.2
Generoiva funktio
Jonon f (0), f (1), . . . generoiva funktio on x:n potenssisarja ∞
f (n)xn .
n=0
(Vaihtamalla x:n tilalle z −1 saadaan tavanomainen ns. z-muunnos.) Potenssisarja voidaan käsittää formaaliseksi, ts. sen suppenemista ei tarkastella ja sarjoilla lasketaan formaalisesti käyttäen tavallisia potenssisarjojen laskuoperaatioita: ∞
∞
f (n)x ± n
n=0
n=0
f (n)xn
∞
n
g(n)x =
∞n=0
g(n)xn
=
n=0
∞
(f (n ± g(n)))xn
n=0 ∞ n=0
ja
f (i)g(j) xn
(Cauchyn tulo).
i+j=n
On helppoa (mutta vähän työlästä) todeta, että minkä tahansa renkaan R formaaliset potenssisarjat muodostavat yo. laskuoperaatioiden suhteen myös renkaan, ns. R:n formaalisten potenssisarjojen renkaan R x . R:n ominaisuudet periytyvät R x :lle aivan samoin kuin polynomirenkaalle R[x]. Lisäksi R x voidaan myös ajatella R:n rengaslaajennukseksi samaistamalla R:n alkio a jonon a, 0, 0, . . . potenssisarjaan. R x voidaan myös ajatella R[x]:n rengaslaajennukseksi ilmeisellä tavalla. Symbolisen laskennan ohjelmistot tukevat myös formaalisia potenssisarjoja (tai erikseen z-muunnoksia). Toisaalta, jos kyse on luvuista ja sarjan suppenemissäde on = 0, voidaan generoiva funktio käsittää tavalliseksi suppenevaksi potenssisarjaksi, jolloin yo. laskuoperaatiot ovat sallittuja. Cauchyn tuloa vastaava operaatio jonoille on ns. konvoluutio. Jonojen f (0), f (1), . . . ja g(0), g(1), . . . konvoluutio on siis jono f (0)g(0) , f (i)g(j) , f (i)g(j) , . . . i+j=1
i+j=2
Lause 9.4. Jos kunnan jono f (0), f (1), . . . toteuttaa kertalukua k olevan LHVR:n, jonka karakteristinen polynomi on P (r), niin sen generoiva funktio on x:n rationaalifunktio Q(x)/R(x), missä nimittäjä R(x) = xk P (1/x) ja Q(x):n aste on korkeintaan k − 1. (Lun kukunnan tapauksessa sarja ∞ n=0 f (n)x on itse asiassa Q(x)/R(x):n Maclaurinin sarja.) Todistus. Käytetään jonon f (0), f (1), . . . matriisiesitystä f (n) = dT Mn q, jolloin ±P (λ) on M:n karakteristinen polynomi. Matriisijonon I, M, M2 , . . . alkiojonot toteuttavat Lauseen 9.1 nojalla eräät LHVR:t. Mainittujen alkiojonojen generoivat funktiot muodostavat potenssisarja n n alkioisen k × k-matriisin ∞ M x . Koska (formaalisesti) n=0 (I − xM)
∞ n=0
Mn x n =
∞ n=0
Mn x n −
∞ n=0
Mn+1 xn+1 = I,
LUKU 9. LINEAARISET REKURSIOKAAVAT on
∞
118
Mn xn = (I − xM)−1 .
n=0
Näin ollen ∞
f (n)xn =
n=0
∞
dT Mn qxn = dT
n=0
∞
Mn qxn = dT (I − xM)−1 q.
n=0
Cramerin säännön (ks. peruskurssit) nojalla dT (I − xM)−1 q on x:n rationaalifunktio, jonka nimittäjä on
1 k 1 k |I − xM| = x I − M
= x P x x ja jonka osoittaja on asteeltaan enintään k − 1. Yo. todistus antaa erään menetelmän LHVR:n toteuttavan jonon generoivan funktion etsimiseksi matriisiesityksen f (n) = dT Mn q kautta. (Tässä käy mikä tahansa matriisiesitys.) Generoivan funktion laskeminen matriisiesityksestä: 1. Lasketaan matriisi (I − xM)−1 . Matriisin alkiot ovat x:n rationaalifunktioita. 2. Tulostetaan rationaalifunktio dT (I − xM)−1 q. Toinen tapa on seuraava: Generoivan funktion laskeminen rekursiokaavasta + alkuarvoista: 1. Kerrotaan rekursiokaava f (n + k) = c1 f (n + k − 1) + c2 f (n + k − 2) + · · · + ck f (n) puolittain xn+k :lla: f (n + k)xn+k = c1 xf (n + k − 1)xn+k−1 + c2 x2 f (n + k − 2)xn+k−2 + · · · + ck xk f (n)xn . 2. Summataan yli arvojen n = 0, 1, 2, . . . ja ratkaistaan saadusta yhtälöstä k−1 k−2 G(x) − f (n)xn = c1 x G(x) − f (n)xn n=0
+ c2 x2
G(x) −
n=0 k−3
f (n)xn
+ · · · + ck xk G(x)
n=0
generoiva funktio G(x). Lauseelle 9.4 käänteinenkin tulos pätee lukukunnissa: Lause 9.5. Jos Q(x)/R(x) on lukukunnan rationaalifunktio, jonka osoittajan Q(x) aste on pienempi kuin nimittäjän R(x) aste k ja jonka nimittäjän R(x) vakiotermi a0 on = 0, niin Q(x)/R(x) on erään kertalukua k olevan LHVR:n toteuttavan jonon generoiva funktio (Maclaurinin sarjana). Lisäksi ko. LHVR:n karakteristinen polynomi on 1/a0 xk R(1/x).
LUKU 9. LINEAARISET REKURSIOKAAVAT
119
Todistus. Tarvittaessa supistamalla a0 :lla voidaan olettaa, että R(x):n vakiotermi on 1. Näin ollen R(x) on muotoa 1 + a1 x + · · · + ak xk , missä ak = 0. Kehitetään Q(x)/R(x) Maclaurinin sarjaksi: ∞ Q(x) = f (n)xn R(x) n=0 (onnistuu, sillä R(0) = 1 = 0). Silloin R(x)
∞
n
f (n)x =
n=0
∞
n
R(x)f (n)x =
n=0
= =
∞ n=0 k−1
∞
(1 + a1 x + · · · + ak xk )f (n)xn
n=0
f (n)xn + f (n)xn +
n=0 ∞
+
∞ n=0 k−2
a1 f (n)xn+1 + · · · +
∞
ak f (n)xn+k
n=0
a1 f (n)xn+1 + · · · + ak−1 f (0)xk−1
n=0
(f (n + k) + a1 f (n + k − 1) + · · · + ak f (n))xn+k
n=0
= Q(x). Koska Q(x) on enintään astetta k − 1 oleva polynomi, pitää olla f (n + k) + a1 f (n + k − 1) + · · · + ak f (n) = 0.
Seuraus. Jos kaksi jonoa toteuttavat LHVR:t, joiden karakteristiset polynomit ovat P1 (r) ja P2 (r), niin niiden konvoluutio toteuttaa LHVR:n, jonka karakteristinen polynomi on P1 (r)P2 (r). Todistus. Mainittujen jonojen konvoluution generoiva funktio on jonojen generoivien funktioiden tulo. Seuraus. Jos jonof (0), f (1), . . . toteuttaa LHVR:n, jonka karakteristinen polynomi on P (r), niin sen summa f (n)δn (jonona) toteuttaa LHVR:n, jonka karakteristinen polynomi on P (r)(r − 1). Todistus. Vakiojono 1, 1, . . . eli g(n) = 1 toteuttaa 1. kertaluvun LHVR:n g(n + 1) = g(n), jonka karakteristinen polynomi on r − 1, ja
f (i)g(i) =
i+j=n−1
n−1
f (i).
i=0
n−1
Näin ollen i=0 f (i) toteuttaa (jonona) LHVR:n, jonka karakteristinen polynomi on P (r)(r − 1). Vakiojono C, C, . . . toteuttaa myös LHVR:n jonka karakteristinen polynomi on P (r)(r − 1) (totea!). Näin ollen edelleen myös summa
f (n)δn =
n−1
f (i) + C
i=0
toteuttaa sen (jonona). Näin summa f (n)δn saadaan summatuksi funktioksi F (n), jota vastaava jono toteuttaa tunnetun LHVR:n. Itse asiassa, jos ajatellaan seuraavan pykälän eksponentiaalipolynomiesitystä eksplisiittisenä lausekkeena, saadaan f (n)δn summatuksi ”suljettuun muotoon”.
LUKU 9. LINEAARISET REKURSIOKAAVAT
9.3.3
120
Eksponentiaalipolynomi
Lukukunnan tapauksessa generoiva funktio Q(x)/R(x) voidaan Pykälässä 5.4 esitetyllä tavalla jakaa osamurtoihin: i i aij aij Q(x) = . = j j R(x) (x − b ) (x − 1/ρ ) i i i=1 j=1 i=1 j=1
m
k
m
k
Lauseen 9.5 nojalla ρi = 1/bi on Q(x)/R(x):tä vastaavan LHVR:n karakteristisen polynomin juuri. Muotoa a/(x−1/ρ)j oleva osamurto on siinä määrin yksinkertainen, että sen Maclaurinin sarja (binomisarja) saadaan helposti: a a Dn = (−j)(−j − 1) · · · (−j − n + 1) , (x − 1/ρ)j (x − 1/ρ)j+n joten Maclaurinin sarjan kerroin on 1 a (−j)(−j − 1) · · · (−j − n + 1) n! (−1/ρ)j+n −j a j n+j −1 = = a(−1) ρj+n . n (−1/ρ)j+n n (ks. Pykälä 3.6). Näin saadaan f (n):lle eksplisiittinen lauseke, ns. eksponentiaalipolynomi: k m m i n + j − 1 j j n aij (−1) ρi pi (n)ρni , ρi = f (n) = j − 1 i=1 j=1 i=1 missä pi (x) on enintään ki − 1-asteinen polynomi (i = 1, 2, . . . , m). Yo. menettely tarjoaa algoritmin eksponentiaalipolynomin etsimiseksi lähtien generoivasta funktiosta. Toinen tapa on käyttää määräämättömiä kertoimia lähtien suoraan LHVR:stä f (n + k) = c1 f (n + k − 1) + c2 f (n + k − 2) + · · · + ck f (n) ja alkuarvoista f (0), f (1), . . . , f (k − 1): Eksponentiaalipolynomin etsiminen määräämättömien kerrointen menetelmällä: 1. Etsitään karakteristisen polynomin rk − c1 rk−1 − · · · − ck−1 r − ck eri juuret ρ1 , ρ2 , . . . , ρm sekä näiden kertaluvut k1 , k2 , . . . , km . 2. Muodostetaan enintään ki − 1 asteinen polynomi pi (x), jossa on määräämättömät kertoimet (ki kpl; i = 1, 2, . . . , m). 3. Ratkaistaan kertoimet yhtälöistä f (j) =
m
pi (j)ρji
(j = 0, 1, . . . , k − 1)
i=1
(lineaarinen yhtälöryhmä, k yhtälöä ja k1 + k2 + · · · + km = k tuntematonta). Eksponentiaalipolynomin saaminen edellyttää karakteristisen polynomin juurten liittämistä kerroinkuntaan ja voi näin olla sangen suuritöinen operaatio. Kuten lineaaristen vakiokertoimisten differentiaaliyhtälöiden tapauksessakin (ks. Pykälä 7.6), voidaan kuitenkin ensin etsiä eri juurten kertaluvut k1 , k2 , . . . , km käyttäen karakteristisen polynomin neliöttömiin tekijöihin jakoa, merkitä eri juuria symboleilla ja ratkaista polynomit p1 (x), p2 (x), . . . , pm (x) kuten yllä.
Kirjallisuus 1. A BRAMOWITZ , M. & S TEGUN , I.A. (toim.): Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover (1974) 2. A KRITAS , A.G.: Elements of Computer Algebra. Wiley (1989) 3. A NDREWS , G.F. & A SKEY, R. & ROY, R.: Special Functions. Cambridge University Press (1999) 4. B ECKER , T. & W EISPFENNING , V.: Gröbner Bases: A Computational Approach to Commutative Algebra. Springer–Verlag (1993) 5. B RONSTEIN , M.: Symbolic Integration I. Transcendental Functions. Springer–Verlag (1996) 6. B UCHBERGER , B. & C OLLINS , G.E. & L OOS S.R. (toim.): Computer Algebra. Symbolic and Algebraic Computation. Springer–Verlag (1983) 7. C OHEN , H.: A Course in Computational Algebraic Number Theory. Springer–Verlag (1993) 8. C OX , D. & L ITTLE , J. & O’ SHEA , D.: Ideals, Varietes, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer–Verlag (1994) 9. C RANDALL , R. & P OMERANCE , C.: Prime Numbers. A Computational Perspective. Springer–Verlag (2001) 10. DAVENPORT, J.H. & S IRET, Y. & T OURNIER , E.: Computer Algebra. Systems and Algorithms for Algebraic Computation. Academic Press (1993) 11. DAVENPORT, J.H.: On the Integration of Algebraic Functions. Lecture Notes in Computer Science 102. Springer–Verlag (1981) 12. E NNS , R. & M C G UIRE , G.: Computer Algebra Recipes. A Gourmet’s Guide to the Mathematical Models of Science. Springer–Verlag (2001) 13. G EDDES , K.O. & C ZABOR , S.R. & L ABAHN , G.: Algorithms for Computer Algebra. Kluwer (1992) 14. G RABMEIER , J. & K ALTOFEN , E. & W EISPFENNING , V. (toim.): Computer Algebra Handbook. Springer–Verlag (2003) 15. G RAHAM , R.L. & K NUTH , D.E. & PATASHNIK , O.: Concrete Mathematics. Addison– Wesley (1994) 121
122 16. G REENE , D.H. & K NUTH , D.E.: Mathematics for the Analysis of Algorithms. Birkhäuser (1990) 17. G REGORY, R.T. & K RISHNAMURTHY, E.V.: Methods and Applications of Error-Free Computation. Springer–Verlag (1984) 18. K NUTH , D.E.: The Art of Computer Programming Vol. 2: Seminumerical Algorithms. Addison–Wesley (1998) 19. K RISHNAMURTHY, E.V.: Error-Free Polynomial Matrix Computations. Springer–Verlag (1985) 20. K ROMMER , A.R. & U EBERHUBER , C.W.: Computational Integration. SIAM (1998) 21. L IPSON , J.D.: Elements of Algebra and Algebraic Computing. Addison–Wesley (1981) 22. M IGNOTTE , M.: Mathematics for Computer Algebra. Springer–Verlag (1991) ˘ , D.: Polynomials: An Algorithmic Approach. Springer– 23. M IGNOTTE , M. & S¸ TEFANESCU Verlag (1999) ˘ , M. & W ILF, H.S. & Z EILBERGER , D.: A = B. A.K. Peters (1996) 24. P ETKOV SEK
25. P OHST, M. & Z ASSENHAUS , H.: Algorithmic Algebraic Number Theory. Cambridge University Press (1990) 26. R ALL , L.B.: Automatic Differentiation: Techniques and Applications. Lecture Notes in Computer Science 120. Springer–Verlag (1981) 27. R IESEL , H.: Prime Numbers and Computer Methods for Factorization. Birkhäuser (1994) 28.
G ATHEN , J. & G ERHARD , J.: Modern Computer Algebra. Cambridge University Press (1999) VON ZUR
123
Hakemisto 1-jaksoinen deltafunktio 13 1-rengas 39 aakkosto 1 Abelin lause 70 Adleman–Pomerance–Rumely-testi 30 aidosti rationaalinen 85 algebra 4,38 algebrallinen funktio 70 algebrallinen laajennus 53,83,89 algebrallinen luku 51 Algebran peruslause 51 alikunta 41 alirengas 41 alkeisfunktio 84 alkualkio 45 alkukunta 40 alkuluku 15 Alkulukulause 16 alkulukutestaus 29 alkutekijä 15 analyysi 4 argumentti 2 asetelma 5 aste 47,58 automaattinen derivointi 7 Berlekampin algoritmi 63 betafunktio 28,89 Bezout’n kertoimet 17 Bezout’n lause 18,21 Bezout’n muoto 17,20,21,80 binomikaava 28 binomikerroin 26 binääriesitys 16 binäärinen 2 Buchbergerin algoritmi 58 Cardanon kaavat 70 Cauchyn tulo 117 Cayley–Hamilton-lause 113 Dekompositiolemma 86 deltafunktio 8 deltafunktiokampa 13 deltafunktiosarja 13 derivaatta 6,63 derivaattaoperaattori 83 desimaaliesitys 16 differenssi 4,95 differenssiyhtälö 4,90 differentiaali- ja integraalilaskenta 4 differentiaalikunta 74,82 differentiaaliyhtälö 4
differointi 96 digammafunktio 97 ED 46 ei-triviaali tekijä 14 eksakti differentiaaliyhtälö 91 eksponentiaalinen laajennus 83,89 eksponentiaalipolynomi 120 eksponentti-integraali 90 eksponenttimuoto 73 elliptinen integraali 90 epähomogeeninen 110 epälineaarinen rekursiokaava 110 Eratostheneen seula 29,62 errorfunktio 89 esitys 66 etenevä differenssi 95 etenevä suhde 107 Eukleideen algoritmi 17,80 Eukleideen alue 45 Eukleideen arvotus 46,48 Eulerin vakio 89,97 Fermat’n pieni lause 23 FFT 33,59 Fibonaccin luku 19 formaalinen derivaatta 63 formaalinen potenssisarja 117 formaalisten potenssisarjojen rengas 117 Fresnelin kosini-integraali 90 Fresnelin sini-integraali 90 funktio 2 Galois’n teoria 70 gammafunktio 24,89 Gaussin kokonaisluku 71 Gaussin lemma 62 generoiva funktio 117 Gosperin algoritmi 103,106 Gröbnerin kanta 58 hajoamiskunta 53 hajoita–ja–hallitse-rekursiokaava 111 harmoninen funktio 97 harva polynomi 68 Heavisiden funktio 9 Heikko Stirlingin kaava 25 heikko derivaatta 9 heksadesimaaliesitys 16 Hermiten menetelmä 76,89,102 homogeeninen 110 Hornerin esitys 68 Horowitzin menetelmä 77,89 hyperbolinen kosini-integraali 90 hyperbolinen muoto 73 hyperbolinen sini-integraali 90
124 hypergeometrinen funktio 103 hypergeometrinen summaus 103 hypergeometrinen termi 103 ideaali 41 ideaalinen näytteenottofunktio 13 ihanne 41 infiksimerkintä 2 integraalimuunnos 4 integrointi 90 interpolaatio 59 inverssi 23 jaettava 14 jakaja 14 jakojäännös 14,46 jakolasku 14,33,40,59 jakorengas 40 jaollisuus 14,43 jaoton 15 Jeruginin lause 92 johtava kerroin 47,58 johtava monomi 58 johtava termi 47,58 jono 5 joukko 5 joukko-oppi 4 juuri 49 juurilauseke 70 jäännös 22 jäännösluokka 22,41 jäännössysteemi 22 kanoninen esitys 66 kanta 16 kantaesitys 16 karakteristika 64 karakteristinen polynomi 91,112 karakteristinen yhtälö 112 kardinaalisini 8 Karatsuban algoritmi 32,34,59 Karrin algoritmi 98 katenaatio 1,5 katto 11 kerroin 47,110 kertaluku 2,49,110 Kertolaskennan peruslause 108 kertolasku 31,59 kertoma 24 kertominen 108 Kiinalainen jäännöslause 24,59 kokonaisalue 39 kokonaisaste 58 kokonaisastejärjestys 58 kokonaisluku 4,14
kommutatiivinen rengas 39 kompleksiluku 4,40 kompleksinen rationaaliluku 53 kongruenssilaskenta 22 kongruentti 22,41 konvoluutio 117 kosini-integraali 89 Kovacicin algoritmi 92 Kroneckerin algoritmi 61 Kroneckerin tulo 115 kunta 4,40 kuntalaajennus 41 kuntalaajennustorni 53,84 kvadraattinen algoritmi 33 kvaternionirengas 41 käänteisalkio 39 käänteisintegrointi 82 käänteisleksikograafinen järjestys 58 Lagrangen interpolaatiokaava 61 Lamén lause 19 leksikograafinen järjestys 58 liittoluku 71 normi 71 liitännäinen 43 liitännäisyys 2 lineaarialgebra 4 lineaarinen differentiaaliyhtälö 91 lineaarinen rekursiokaava 110 Liouvillen periaate 84 lista 5 logaritmi-integraali 90 logaritminen laajennus 83 logaritminen osa 77 logiikka 4 lukukunta 40 lukuteoria 4,14 luonnollinen luku 14 Matijasevits–Tshudnovski-lause 67 matriisi 5 matriisiesitys 112 McEliecen lemma 12 metaoperaatio 4 Miller–Rabin-testi 29 moduli 22 modulo 22,41 moduläärilaskenta 22 monen muuttujan polynomi 57 monikerta 39,43 moninkertainen juuri 49 monoidi 1 monomi 57 Multinomikaava 28 multinomikerroin 28
125 multiplikatiivinen 44 murtokunta 42 määrätty summa 95 määrätty tulo 107 määräämättömien kerrointen menetelmä 57,120 määräämätön summa 95 määräämätön tulo 107 nablaus 7 negatiivinen jäännössysteemi 22 neliökunnan kokonaisluku 71 neliökunta 71 neliöttömiin tekijöihin jako neliötön 63 Newtonin interpolaatiokaava 61 Newtonin menetelmä 33 nimittäjien tekeminen erinimisiksi 54 nolla-alkio 38 nollanjakaja 39 nollapolunomi 47 nopea Fourier’n muunnos 33,59 normaaliesitys 66 normaaliosa 44 numeerinen laskenta 4 numeraali 1 O-notaatio 7,26 oheismatriisi 36,112 oikea sulutus 2 oktaaliesitys 16 operaattori 2 osamurtokehitelmä 56 osamäärä 14,46 osamääräkunta 42 osittaisintegrointi 9,82 osittaiskertominen 109 osittaussummaus 96 osittelulaki 38 p.y.j 21 pakkofunktio 110 Pascalin kolmio 27 perussymboli 1 peräkkäisten approksimaatioiden menetelmä 7,93 PID 46 pienin yhteinen jaettava 21,43 pituus 1.17 Pochhammer-neliöttömiin tekijöihin jako 101 Pochhammer-neliötön 101 Pochhammerin esitys 26,99 Pochhammerin potenssi 101 Pochhammerin symboli 26,68,97 pohja 11 Pollardin ρ-menetelmä 31 polygammafunktio 100 polygammaosa 99
polynomi 4,47,57 polynominen osa 88 polynomirengas 40,47,57 positiivinen jäännössysteemi 22 potenssi 39 potenssiin korotus 35 potentiaali 91 prefiksimerkintä 2 primitiivinen polynomi 49,62 probabilistinen 29 puhtaasti logaritminen laajennus 85 puolalainen merkintä 2 pääihanne 52 pääihannealue 45 pääpolynomi 48 radikaali 70 rationaalifunktio 41,53,58,75,98 rationaalifunktioiden kunta 53 rationaaliluku 40 rationaalinen osa 76,101 reaalikertoiminen 57 reaaliluku 4,40 reaalinen osamurtokehitelmä 57 rekursiivinen esitys 57 rekursiokaava 32 rekursiokaava 110 rengas 38 rengaslaajennus 41 resultantti 80 Richardsonin 2. lause 67 Richardsonin 3. lause 75 Rischin integrointi 85 Rischin rakennelause 73 Rosenlichtin lause 98 Rothstein–Trager-algoritmi 82 s.y.t. 17 sana 1 satunnaisluvun generointi 35 separoituva differentiaaliyhtälö 90 signumfunktio 10 siirtorekisteri 35 sijoitus 82 sinc-funktio 8 Singerin algoritmi 92 sini-integraali 75,89 sisältö 48 Stirlingin approksimaatio 25 suffiksimerkintä 2 suhde 107 suhdesäännöt 108 summa 4,95 summaava tekijä 111
126 summaus 95 Summauslaskennan peruslause 95 summauslaskenta 4,95 suurin yhteinen tekijä 17,43 Sylvesterin kriteeri Sylvesterin matriisi 79 symboli 1 symbolinen integrointi 75 symbolinen osamurtokehitelmä 57 symmetrinen jäännössysteemi 22 takeneva differenssi 95 takeneva suhde 107 taulu 5 Taylorin kehitelmä 7 Taylorin polynomi 7 Taylorin sarja 7,93 tekijä 14,43 tekijärengas 41 tekijöihinjako 31,61 tiheä polynomi 68 Tragerin algoritmi 63 transsendenttifunktio 73 transsendenttinen alkio 58 transsendenttinen laajennus 59 transsendenttinen luku 51 triviaali tekijä 14 tulkinta 4 tulo 107 tulointegraali 107 tyhjä jono 5 tyhjä sana 1 UFD 45 unäärinen 2 vahva valealkuluku 30 vaihdannainen rengas 39 vaihdannaisuus 3 vajaa betafunktio 89 vajaa gammafunktio 89 vakiokertoiminen lineaarinen differentiaaliyhtälö 91 vakiokertoinen lineaarinen rekursiokaava 111 vakiokunta 82 vakiopolunomi 47 vasta-alkio 38 vektori 5 Venäläisten talonpoikien menetelmä 35 vinokunta 40 virhetermi 7 vähennyslasku 31,39,59 Wilsonin lause 26,50 yhdistetty luku 15 yhteenlasku 31,59 yhtälö 5
ykkösalkio 39 ykkösrengas 39 yksikkö 39 yksikkönormaali 44 yksikköosa 44 yksikäsitteisen tekijöihinjaon alue 45 yleistetty funktio 9 ylikunta 41 ylirengas 41 ympyräkunta 72