Insinöörimatematiikkaa tiivistettynä

Jarno Elonen <elonen@iki.fi>, 31.5.2007 (versio 1.2)

Hyvä lukija,

Olen kirjoittanut nämä muistiinpanot alunperin itselleni ja julkaisen ne nyt yksinkertaisesti siltä varalta, että niistä sattuisi olemaan jollekulle muullekin jotain iloa.

Kyseessä ei ole oppikirja vaan asioita on jätetty pois, oiottu ja yksinkertaistettu sen mukaan miten olen niitä itse katsonut tarvitsevani ja kuinka hyvin olen muistanut asiat entuudestaan. Tarkoituksena on ollut lähinnä luetteloida erilaisten ongelmien ratkaisutapoja käytännön (tietotekniikka-)insinöörintyötä ajatellen eikä niinkään osoittaa tai johtaa niitä. En myöskään väitä ymmärtäväni kaikkea kirjoittamaani – mikä on tietysti harmi, sillä matematiikka on kiinnostavaa vaikka ainakin itselläni muut työt ovat aina vieneet ajan ja energian paneutua siihen kunnolla.

Tekstiä saa kopioida, muokata ja vaikka myydä vapaasti kunhan minut mainitaan alkuperäisen version toimittajana ja kerrotaan, että alkuperäinen on vapaasti kopioitavaa materiaalia. Uusin versio löytyy osoitteesta:

http://iki.fi/elonen/articles/insimat/

Valituksille finglishistä ja muista muotoseikoista en luultavasti lotkauta korvaanikaan ellei valitusten mukana tule korjaustiedostoa, sillä tämän dokumentin päivittämiseen käytetty aika on aina pois muilta töiltä. Tekstiin on epäilemättä kuitenkin jäänyt myös varsinaisia asiavirheitä – niistä saa mielellään huomauttaa sähköpostitse. GNU Diff:llä muodostetut korjaustiedostot suoraan .tm-tiedostoon ovat tietysti vieläkin tervetulleempia.

–

Jarno Elonen

Sisältö

1Lineaarialgebra

Tässä kappaleessa käsitellään lähinnä reaalisia avaruuksia mutta suurin osa kohdista pätee myös myös kompleksisille avaruuksille tai vaikka alkiot olisivat funktioita (funktioavaruus). Oleellista on vain, että alkiot toteuttavat lineaarialgebran aksioomat, joiden mukaan mm. täytyy löytyä nolla-alkio ja ykkösalkio, jokaiselle alkiolle täytyy olla vasta-alkio, alkion kertominen skalaarilla täytyy kommutoida yms.

1.1Matriisien perusteet

• transpoosi on :n peilaus diagonaalin (lävistäjän) suhteen
• säännöllinen vs. singulaarinen matriisi: on olemassa käänteismatriisi vs. ei ole olemassa. Älä sekoita säännöllistä ja symmetristä (ts. ).
• ortogonaalinen matriisi: (pystyvektorit ovat kohtisuorassa eli ortogonaaliset)
• ortonormeeratut vektorit: toisiaan vastaan kohtisuorassa (ortogonaalimatriisi) ja normit (pituus) ovat 1
• rangi tai rankki (rank) eli säännöllisyysaste: yhtälöryhmän ratkaisun ei-vapaiden muuttujien määrä eli Gaussin eliminaation tuloksen yksikköneliömatriisin koko.
• lineaarikuvaus on funktio, jolle a) ja b) ja koska molemmat pitävät paikkansa matriisikertolaskussa: kun .
• lineaarikuvauksen ydin (kernel) on :n ratkaisujoukko.
• avaruuden dimensio: vapaiden muuttujien määrä, esim. :lle 2 ja 3.
• lineaarikombinaatio tai -yhdistely on vektoreiden painotettu summa. Älä sekoita lineaarikombinaatiota lineaarikuvauksen kanssa!
• kanta: kappaletta avaruuden lineaarisesti riippumatonta vektoria (mitkä tahansa). Sanonta: "koordinaatit kannan suhteen".
• luonnollinen kanta: avaruuden vektorit (eli tavallinen koordinaatisto).

• matriisin normi on mikä tahansa eräät ehdot täyttävä skalaari-”mittari” matriisille. Tässä kolme tärkeintä (vastaavista vektorinormeista johdettua) matriisinormia:

  

  

  

1.1.1Tulo

Matriisien tulo tapahtuu "kertomalla rivit sarakkeisiin" ja :ssä, :n korkeus on :n korkeus ja leveys :n leveys. Jos :n leveys :n korkeus, tulo on määrittelemätön. Esim:

Toisin sanoen: matriisivektori -operaatio on siis matriisin leveys -kokoisen vektorin kuvaus matriisin korkeus -kokoiseksi vektoriksi.

Pystyvektorien pistetulo cos(

1.1.2Käänteismatriisi

Määritelmä: . Vain neliömatriiseilla voi olla käänteismatriisi ja niilläkin vain joss sarakkeet/rivit ovat lineaarisesti rippumattomia (sama asia). Sääntöjä:

Käänteismatriisin voi laskea Gauss-Jordan-algoritmilla (ks. alempana)...

...tai hitaasti determinantin (ks. alempana) avulla (Cramerin sääntö):

2x2-kokoiselle matriisille Cramerin sääntö tosin on vielä selvästi helpompi: .

1.1.3Lineaarialgebran derivointisääntöjä

Perussääntöjä:

Matriisilausekkeiden derivaattoja vektorin suhteen:

1.1.4Gaussin eliminaatio

Yhtälöryhmä kirjoitetaan matriisiksi...

...ja väännetään sitten yläkolmiomuotoon vähentämällä "nykyinen" rivi alemmista riveistä aina kerrottuna ylänurkan sopivasti kerrotulla tukialkiolla...

...ja soveltamalla sitten alhaalta ylöspäin peräkkäisiä sijoituksia tai toistamalla eliminointi alhaalta ylös, jolloin saadaan yksikkömatriisi (kuten Gauss-Jordan:ssa). Huom:

• rivin vaihto ei muuta tulosta
• sarakkeen vaihto muuttaa muuttujien järjestystä kirjanpito tarpeen
• Tulosrivi EI tarkoita, että ryhmä olisi ratkaisematon vaan se poistetaan ja tulkitaan jäljelle jääneitä rivejä yhtälöryhmänä
• Ristiriitainen tulosrivi (esim. ) tarkoittaa ratkaisematonta ryhmää
• Jos tuloksia on äärettömästi, esitetään ratkaisu vapaan muuttujan (tai useamman) avulla:

1.1.5Determinantti

Determinantti on neliömatriisin vektorien määräämän suoran/suunnikkaan/särmiön pituus/ala/tilavuus (ja vastaava luku moniulotteisemmille avaruuksille). Yksinkertaisin tapaus, -determinantti on helppo laskea: . Yleisiä sääntöjä:

• rivin/sarakkeen vaihto muuttaa etumerkin
• determinantin kertominen skalaarilla kertoo yhden rivin tai sarakkeen: ja esim. jne.
• rivin/sarakkeen lisääminen toiseen skaalattuna ei muuta tulosta (Gauss toimii)
• transponointi ei muuta determinanttia (ts. )
• 
• sarakkeet/rivit ovat lin. riippumattomiaon olemassa käänteismatriisi

Ison determinantin voi laskea vääntämällä se Gaussin algoritmilla yläkolmiomuotoon ja laskemalla lävistäjän tulo...

...tai hitaammin alideterminanttikehitelmän avulla minkä tahansa rivin tai sarakkeen suhteen...

...missä termien etumerkit määräytyvät elementin koordinaateista näin:

Vektorien ristitulo =||sin(, missä .

1.1.6Kanta

Avaruuden kanta (koordinaatisto) muodostuu mistä tahansa :stä, lineaarisesti riippumattomasta vektorista. Luonnollinen kanta on "tavallinen koordinaatisto" . Kannan vaihto luonnollisesta kantaan on...

...eli tehdään kantamatriisi pystyvektoreista ja ratkaistaan - tai jos halutaan kannanvaihtomatriisi, lasketaan :n käänteismatriisi.

1.1.7Gram-Schmidt-ortonormalisointi

Kanta on ortonormaali, jos sen kaikki vektorit ovat kohtisuorassa toisiaan vastaan ja jokainen vektorin on :n mittainen (kuten luonnollisella kannalla). Minkä tahansa kannan voi pakottaa ortonormaaliksi Gram-Schmidt ortonormalisointi-algoritmilla. Sitä käytetään erityisesti numeerisessa laskennassa hieman ”epävireeseen” menneen kannan korjaamiseen. Merkitään alkuperäisiä vektoreita ja uusia :

1. merkitään ja ja aloitetaan kohdasta 3
2. vähennetään :nnestä vektorista kaikkien jo ortonormalisoitujen vektorien projektio:
3. normalisoidaan :s vektori:
4. Lisätään :tä yhdellä eli siirrytään seuraavaan vektoriin. Jos , jatketaan kohdasta 2.

1.1.8Ominaisarvot ja -vektorit (eigenvalues & vectors)

Neliömatriisin ominaisarvon määritelmä: , eli koska :lla transformointi ei muuta ominaisvektorin suuntaa (paitsi ehkä negatoi), transformaation voi (kaikille :n suuntaisille vektoreille) tiivistää skalaariksi: ominaisarvoksi . Koska , löytää ominaisarvot ratkaisemalla ja -vektorit ratkaisemalla tuloksen perusteella yhtälöryhmä . Siis:

1. laske eli :stä riippuva :n karakteristinen polynomi
2. ratkaise polynomin juuret (eli :n ominaisarvot)
3. muodosta (nyt tunnetuista) ominaisarvoista yhtälöryhmät ja ratkaise :t (Huom: matriisi on singularinen, joten :t eivät ole yksiselitteisiä, vaan ne voi skaalata mielivaltaisella vakiolla)

Matriisin on diagonalisoituva, jos sillä on ominaisarvoa. Diagonalisoitu matriisi on koottu ominaisarvoista: . Vastaavasti sen similariteettimuunnos(-matriisi) on koottu ominais(pysty)vektoreista . Matriisit ja ovat similaariset, jos on olemassa siten, että , joten ja ovat aina similaariset: . Esimerkki ominaisarvojen laskemista, diagonalisoinnista ja similaarisuuden hyödyntämisestä on seuraavassa kappaleessa.

1.1.9Matriisifunktiot

Matriisifunktiot on määritelty -neliömatriisille seuraavasti:

...josta :t voi laskea ominaisarvojen avulla, sillä:

Toisaalta, jos ominaisarvot eivät ole moninkertaisia (onko välttämätön ehto?), voi saman laskea diagonalisoinnin avullakin:

Tällä tavalla voidaan laskea esim. matriisieksponentti , , mielivaltaisen suuri matriisipotenssi tai vaikka neliöjuurimatriisi (). Esimerkki:

Huom: matriisin derivaatta ja integraali lasketaan kuitenkin ottamalla ne erikseen jokaiselle alkiolle.

1.2Vektorit ja analyyttinen geometria

1.2.1Vektoritulot

• Pistetulo eli skalaaritulo eli sisätulo cos(.

  • Yhdensuuntaisuus:
  • Skalaariprojektio: :n pituus :llä on .

• Ristitulo eli vektoritulo on määritelty vain 3-vektoreille:

  (Huom: sanotaan, että ristitulomatriisi saadaan :sta ristioperaattorilla)

  
  • Suunnikkaan ala: , kolmion ala = .

• Skalaarikolmitulo: .

  Särmiön tilavuus: , tetraedrin tilavuus: .

  Huom: alat voi laskea myös determinantilla: .

1.2.2Suora

• Parametrimuoto: , missä on suoran suunta

• Normaalimuoto: koska jokainen :sta pisteeseen johtava vektori on kohtisuorassa normaalia vastaan, on :ssa:

  eli eli , missä ovat :n komponentit ja on normaalin ja :n pistetulo (eli :n projektio :lle, suoran siirto origosta).

• Painopistekoordinaatit: , missä

  Jos , piste on :n ja :n välissä. Keskipisteessä .

• Suoraparvi on usemman suoran ryhmä ja suoraviuhka kulkee tietyn pisteen läpi.

• Avaruudessa suoran voi esittää parametrimuodossa tai kahden tason leikkauksena:

  

1.2.3Taso

• Parametrimuoto: , missä tietysti

• Normaalimuoto: koska jokainen :sta pisteeseen johtava vektori on kohtisuorassa normaalia vastaan, on (:ssa!): eli eli

  , missä ovat :n komponentit ja on normaalin ja :n pistetulo.

• Painopistekoordinaatit: vektoreilla tai , missä .

  Annetun pisteen sijainnin -pisteiden muodostamaan kolmioon nähden voi päätellä painokertoimien merkistä - kolmion sisällä se on "". Kolmion painopisteessä .

1.2.4Tetraedri

• Tetraedrissä on 4 tahkoa ja 4 kärkipistettä ("kolmiopohjainen pyramidi"):

• Kun kärkipisteistä johdetaan kolme särmävektoria saadaan sekä kanta, että auki kertomalla painopistekoordinaattiesitys:

  , missä . Kuten 3D-tason ja 2D-suoran tapauksissakin, painopisteessä on ja annetun pisteen paikan tetraedrin suhteen voi päätellä :n etumerkeistä – tetraedrin sisällä se on "".

1.2.5Projektio

• Yhdensuuntaisprojektion määrittää projektiotason normaali ja projektiosäteiden suuntavektori . Laskukaava: tai matriisina . on yhdensuuntaisprojektio joss .
• Jos suuntavektori on lisäksi kohtisuorassa tasoon nähden, on kyseessä ortogonaalinen projektio (joss ).

1.3Homogeeniset koordinaatit

projektiivinen taso, projektiivinen avaruus, Pappuksen lause, projektiviteetti, kiintopiste

Euklidisen tason pistettä vastaa projektiivisen tason piste, eli homogeeninen koordinaatti . Grafiikkakirjoissa ylimääräinen ("nollas") elementti kirjoitetaan usein viimeiseksi: [x,y,w].

Sekä affinitransformaatiot (siirto, peilaus, rotaatio, skaalaus, skew) että projektio ovat homogeenisissa koordinaateissa palautettavissa (projektiossa aiheuttaa tavallisen pisteen muuttumisen idaalipisteeksi, ideaalipisteen muuttumisen tavalliseksi ja lopuissa koodautuu :hen) – siitäkö lienee nimi "projektiivinen taso"? Molemmat voidaan esittää esim. :n tapauksessa -matriisilla.

1.3.1Ideaalipisteet, -suorat ja tasot

Pystyvektorilla esitetään pisteitä ja vaakavektorilla (transponoiduilla) suoria: . Suoran tavallinen yhtälö on . Ideaalipisteet ovat kuviteltuja "äärettömän kaukana sijaitsevien samansuuntaisten suorien leikkauksia", toimivat laskennassa aivan kuten muutkin pisteet ja sijaitseva ideaalisuoralla (tai projektiivisessa avaruudessa ideaalitasolla).

1.3.2Duaalisuus ja lauseiden dualisointi

Projektiivisen tason pisteet ja suorat ovat duaalisia eli niitä koskevissa lauseissa sanan "suora" ja "piste" (:ssa "taso" ja "piste") voi vaihtaa keskenään (eli lause voidaan dualisoida):

• suora kahdesta pisteestä: / (leikkaus-)piste kahdesta suorasta: .
• piste on suoralla / suora on pisteellä:
• pisteet samalla suoralla: / suorat yhdensuuntaisia:

1.4Kuvaukset (transformaatiot)

1.4.1Lineaarikuvaus

Lineaarikuvaus tai tuttavallisesti matriisikertolasku (ilman homogeenisia koordinaatteja), on määritelty kahdella ehdolla:

Lineaarikuvauksen ydin (kernel) on :n ratkaisujoukko.

Yleisiä lineaarikuvauksia:

• Skaalaus: tai symmetrisessä (uniform) tapauksessa

• Kierto (rotaatio): rotaatiomatriisilla ortogonaalisella matriisilla on aina (oikeakätinen, vasenkätinen) ja yksi ominaisarvo . Kyseistä ominaisarvoa vastaava ominaisvektori on rotaatioakseli (koska :n ominaisvektori = vektori, jonka suunta ei muutu :llä kerrottaessa). Toisaalta on:

  • akseli + kulma: , missä , kun
  • kolme akselia:

1.4.2Affiniteetti (affinikuvaus)

Affiniteetti on kahden tason () tai avaruuden () välinen kuvaus . Tasot/avaruudet, jotka saadaan affiniteetilla toisistaan ovat affinisia.

Suunnikkaan pinta-ala tai yhdensuuntaissärmiön tilavuus kertoutuvat affinikuvauksessa :lla.

Projektiivisessa avaruudessa/tasossa affiniteetin voi kuvata matriisikertolaskulla:

1.5Matriisien sekalaisia sovelluksia

1.5.1Pienimmän neliösumman sovitus (least squares fit)

Jos yritetään sovittaa -kertoiminen funktio liian moneen havaintoon ( kappaletta, ), saadaan sijoittamalla havainnot polynomiin ylimäärätty yhtälöryhmä: , missä =sijoittamalla saadut kertoimet, ja funktion havaitut arvot. Pienimmän neliosumman sovitus: haetaan :lle neliömatriisi , :lle pienempi vektori ja ratkaistaan tavalliseen tapaan.

1.5.2Markovin ketjut

Markovin ketju (Markov Chain) on joukko tiloja, joiden välisten siirtymien todennäköisyys ei riipu toteutuneesta siirtymä-historiasta. Yksi kätevä esitystapa on stokastinen matriisi: neliömatriisi, jossa jokaisen rivin summa on 1. Esim:

Lyhyt mies saa lyhyen pojan todenäköisyydellä 0.75 ja pitkän todennäköisyydellä 0.25. Pitkä taas saa lyhyen todennäköisyydellä 0.1 ja pitkän varmuudella 0.9. Lyhyitä ja pitkiä on aluksi saman verran: . Stokastinen matriisi . Toisen sukupolven jakauma on , kolmannen sukupolven jakauma on jne.

Stokastisella matriisilla on aina ominaisarvo 1 ja stabiili tila äärettömän monen siirtymän jälkeen voidaan laskea diagonalisoimalla.

2Differentiaalilaskentaa yleisesti

2.1Differentiaali

Differentiaali on funktion linearisaation (yhden muuttujan funktion tapauksessa tangentin, kahden tapauksessa 3D-tason jne.) kasvun määrä muuttujansa/muuttujiensa muutoksen suhteen. Esim. . Jos , saadaan kaavasta eli . Siksi voidaan kirjoittaa . Huom: differentiaalin ei välttämättä tarvitse olla pieni, koska kyse on linearisaation kasvusta (siis esim. eikä )!

Kahden muuttujan tapauksessa differentiaali on määritelty osittaisderivaattojen avulla seuraavasti: eli ja samalla tavalla useammille muuttujille.

Differentiointi (vs. derivointi) tarkoittaa differentiaalin (siis esim. ) laskemista ja siinä käytetään derivointia (tai osittaisderivointia) ja jos halutaan arvo, eikä kaavaa, :n muutos (). Esim. jos , niin

2.2Jacobian-matriisi

Jacobian-matriisi on usean muuttujan vektoriarvoisen funktion derivaatta eli käytännössä matriisi, joka sisältää funktion tulosvektorin jokaisen elementin ( kpl.) derivaatat jokaisen sisääntulevan vektorin elementin ( kpl.) suhteen:

Jacobian-matriisille mm. pätee ketjusääntö .

Huom! älä sekoita Jacobian-matriisia yhtälöryhmien implisiittisessä derivoinnissa käytettävään Jacobian-determinanttiin .

2.3Monen muuttujan ketjusääntö

Yhden muuttujan ketjusäännön yleistettyjä versioita:

• Jos ja ja riippuvat molemmat muuttujasta (eli ), on:

  

• Jos ja riippuuvat kahdesta muuttujasta (eli ), on:

  

3ODEt - ”tavalliset” differentiaaliyhtälöt

Tiivistelmä: lineaariselle, 1. asteen ODElle on ratkaisukaava, samoin kuin (vakiokertoimiselle) ryhmälle niitä. Muissa tapauksissa Laplace-muunnos on usein kätevin tapa ellei likiarvoratkaisu riitä.

Tässä kappaleessa käytetään vapaana muuttujana välillä :ää ja välillä :ta – älä hämäänny. Kirjain on yleinen käytäntö, koska differentiaaliyhtälöitä käytetään usein ajasta riippuvien ilmiöiden mallintamiseen.

3.1Peruskäsitteitä

• Tavallinen differentiaaliyhtälö: (yhden muuttujan funktio)
• Kertaluku (tässä ): , ts. monenettako derivaattaa funktiosta löytyy
• Eksplisiittinen ODE: yhtälö on muodossa (eikä esim. )
• Osittaisdifferentiaali: on differentiaali yhden muuttujan suhteen (monen muuttujan funktiossa)
• Yleinen ratkaisu vs. erityisratkaisu/erikoisratkaisu (eng. particular/special solution)
• Alkuarvo-ongelma: määritelty :n ja derivaattojen arvot yhdessä pistessä
• Reuna-arvo-ongelma: määritelty :n ja derivaattojen arvot kahdessa pisteessä

3.2Yksittäisen ODEn tarkka ratkaiseminen

3.2.1Separoituva: integrointi puolittain

ODE on separoituva, jos ja ovat erotettavissa eri puolille yhtälöä kohtelemalla differentaalia :n :n osamääränä:

Kun molemmat puolet on integroitu, ratkaistaan . Toisinaan vakiofunktio tuotta, esim. tapauksessa: kun . (Huom: separoituva ODE on itse asiassa eksaktin ODE:n erikoistapaus )

3.2.2Tasa-asteinen: muuttujan vaihto

ODE on tasa-asteinen, jos sen voi saattaa muotoon , jolloin sen voi ratkaista vaihtamalla :n ja :n seuraavasti:

Vaihdon jälkeen yhtälö on separoituva. Ratkaistaan saadusta yhtälöstä , sijoitetaan takaisin ja ratkaistaan . Huom. triviaaliratkaisu: , jos .

3.2.3Eksakti: osittaisderivointi

ODE on eksakti, jos se on muotoa eli eli ja on olemassa funktio , jolle .

Jos ja ovat tiedossa, eksaktiuden voi tarkistaa kaavalla eli (kyllä, derivaatat "menevät ristiin" aiemman kanssa) ja ratkaista seuraavasti:

Lopuksi ratkaistaan yhtälöstä . Ideana on siis soveltaa peräkkäin

3.2.4Eksaktiksi muuttaminen: integroiva tekijä

Jos ODE:n voi muuttaa eksaktiksi kertomalla funktiolla , on ODE:n integroiva tekijä. Sellaisen voi löytää systemaattisesti jos se riippuu vain joko :stä tai :stä:

Sekä :stä että :stä riippuvia tekijöitäkin voi olla, mutta niitä ei tällä kaavalla löydä.

3.2.51. kertaluvun lineearinen ODE: yleinen ratkaisu

• Homogeeninen (, ts. ei :stä riippumattomia termejä) separoituu. Yleinen ratkaisu: ja vakiokertoimiselle (): , missä on mielivaltainen vakio (integrointivakio). Johto:

  
• Homogeenisen (mutta ei epähomogeenisen) ODEn erikoisratkaisujen lineaarikombinaatio on myös ratkaisu yleinen ratkaisu on . Sanotaan, että on ratkaisun kanta kun ovat lineaarisesti riippumattomia. Funktioiden lineaarinen riippumattomuus selviää, kun lasketaan Wronskian-determinantti (esimerkin vuoksi kolmella funktiolla): , joka on 0 joss funktiot ovat lineaarisesti riippuvia.
• Ei-homogeeniselle () on aina integroiva tekijä: . Jos eli vakio, on yleinen ratkaisu .

3.3Yksittäisen yhtälön likiarvoratkaisut

3.3.1Suuntakenttä - erikoisratkaisu graafisesti

Valitaan sopiva ruudukollinen , ratkaistaan ODEsta kullekin ruudukon pisteelle ja piirretään vastaava nuoli tai viiva. Alkuarvo-ongelman ratkaisun voi hahmotella seuraamalla kenttää alkuarvopisteestä. Tietokoneella voi käyttää tämän (huonon) ns. Eulerin menetelmän sijaan vaikkapa 4. asteen Runge-Kuttaa.

Isocline (tasa-arvokäyrä) on jokin :n suhteen vakioarvoinen käyrä suuntakentällä (esim. ns. nullcline eli käyrä ).

3.3.2Picardin iteraatio - approksimoiva algebrallinen erikoisratkaisu

Picardin iteraatiolla saadaan tarkentuva approksimaatio alkuarvo-ongelman ratkaisulle

...eli joka askeleella integroidaan välillä funktiolle , missä on korvattu :llä ja edellisen iteraation tuloksella.

Ratkaisun olemassaolon testaus suljetulla välillä eli Picardin lause: jos on jatkuva laatikon sisällä, iteraatio suppenee yksikäsitteiseen ratkaisuun välillä .

3.42. asteen ODE

Muotoa oleva ODE ratkeaa muuttujaa vaihtamalla: . Korkeamman asteen ODEn voi tällä tavalla muuttaa ensimmäisen asteen ODE-ryhmäksi jonka voi sitten ratkaista vaikka Laplace-muunnoksella tai ominaisarvojen avulla. Esim:

Toisen asteen homogeenisessa tapauksessa: .

3.51. asteen lineearinen homogeeninen ODE-ryhmä

Ryhmä voidaan esittää matriisimuodossa:

Matriisin sarakkeet ovat ryhmän erikoisratkaisuja ja kun on vektorillinen alkuarvoja, on alkuarvo-ongelman ratkaisu. Yleinen ratkaisu saadaan myös suoraan ominaisarvoista ja -vektoreista jos ne ovat erillisiä (ei-moninkertaisia) tai on symmetrinen:

...missä ovat mielivaltaisia vakioita, matriisin ominaisarvoja ja niitä vastaavia ominaisvektoreita. Kaksinkertaisen ominaisarvon tapauksessa toinen ratkaisu saadaan kaavalla , missä ja . (Epäselvää: onko varmasti ?)

Epähomogeenisessa tapauksessa ja erikoisratkaisun saa kaavalla . (Epäselvää: saako yleisen ratkaisun lisäämällä ja mikä silloin on ?) Yleisen saa (muun muassa) ODE:n diagonalisointimenetelmällä: ratkaistaan ensin uuden yhtälöryhmän, ( on :n diagonalisoitu versio eli ominaisarvomatriisi ja , missä on vastaavista ominaispystyvektoreista koottu matriisi), diagonalisoinnin ansiosta nyt toisistaan riippumattomat, yhtälöt yksittäisen yhtälön ratkaisukaavalla (tai vaikka Laplace-muunnoksella) ja sitten “epädiagonalisoidaan” tulos: .

3.5.1Vaihekuvaaja

Kahden muuttujan lineaariselle 1. asteen ODE-ryhmälle voidaan piirtää kaksiulotteinen vaihekuvaaja, jossa on parvi erikoisratkaisukäyriä: . Kohtia, joissa sanotaan tasapainopisteiksi (myös: kriittinen piste). Homogeenisessä tapauksessa piste on aina . Tasapainopisteiden luokittelu riippuu :n ominaisarvoista:

• Piste on stabiili jos molempien reaalinen osa on , muuten epästabiili. Jos ne reaaliosa on nolla, piste on attraktiivisesti stabiili (piste on napa tai spiraali ja lähistön ratkaisut päätyvät siihen) ja muuten oribitaalisesti stabiili (lähistön ratkaisut pysyvät pisteen lähellä kun ).
• Lähiympäristön käytöksestä voidaan sanoa enemmänkin: reaaliset ja samanmerkkisetnapa (stabiilisisäänpäin tai epästabiiliulospäin), reaaliset ja erimerkkisetsatulapiste (kaksi käyrää sisään, kaksi ulos, muut ”hipovat”), keskus (soikion tai ympyrän) ja spiraali (sisään tai ulos).

ODEn linearisointi mahdollistaa myös epälineaarisen ODEn tasapainopisteiden luokittelun: yhtälöiden tasapainopiste luokitellaan matriisin mukaan em. tavalla paitsi, että 1) ympyräpisteet voivat olla myös spiraaleja ja 2) tapaus voi olla joko spiraali tai napa.

3.6Laplace-muunnos

Laplace-muunnoksessa differentiaaliyhtälö (tai -ryhmä) muunnetaan ensin aika-alueesta s-tasoon (kirjoitetaan: ), ratkaistaan sitten saadusta yhtälöstä F ja tehdään lopuksi käänteismuunnos (kirj. ). Usein käänteismuunnosta varten tarvitaan osamurtokehitelmää. Tulos pätee (tässä annetulla määritelmällä) vain alueella ! Alla muutamia tärkeimpiä muunnoksia:

			:n määritelmä
			Derivointi
			2. derivaatta
			Määrätty integraali
			Derivointi taajuusalueessa
			:n skaalaus
			Konvoluutio,
			Konvoluutiolause toiseen suuntaan
		1	Diracin delta”funktio”,
			Heavisiden askelfunktio ()
			Siirto taajuusalueessa
			Aikasiirto, huomaa !
			huom:

Esimerkki: ratkaistaan yksinkertainen epähomogeeninen ODE:

4Sarjat

• Lukujono suppenee, jos sillä on raja-arvo äärettömyydessä, muuten hajaantuu. Vaihtoehtoinen määritelmä: suppenee, jos on , missä voidaan valita mielivaltaisen pieneksi, ja aina löytyy sen sisältä.
• Sarja on äärettömän lukujonon summa. Se suppenee, jos sen osasumista muodostettu jono suppenee. Tällöin .
• Eikö luku ei kasva äärettömäksi äärettömällä summauksella vaikka summattava pienenisikin? Vastaus: ei, koska esim.
• Äärettömät sarjat ovat usein ratkaisuja differentiaaliyhtälöihin, joita ei voi muuten esittää alkeisfunktioilla.

Koska sarja voidaan tulkita jonon osasummasarjan raja-arvoksi äärettömyydessä, saadaan raja-arvon laskusäännöistä (kun ja ):

• 
• 
• Jos kaikille , niin

4.1Suppenemisen testaus

Suppenemista voi testata helpommin kuin laskea summan, ja positiivis-termisen sarjan suppeneminen on helpompi laskea kuin vaihtelevatermisen. Jos :

Integraalitesti

suppenee joss suppenee. ( voidaan valita mielivaltaisesti, koska suppeneminen ei koskaan riipu jonon alusta.)

Osamäärätesti

, eli perättäisten termien osamäärä

n:s juuri-testi

, eli alkion äärettömäs juuri äärettömässä

Molemmille sarja suppenee, jos , saattaa hajaantua, jos ja hajaantuu varmasti, jos . Luku on olemassa useammin kuin , mutta kun molemmat ovat olemassa, on .

Jos taas summassa on sekä positiivisia että negatiivisia termejä, se suppenee ainakin jos suppenee (suppenee absoluuttisesti), ja toisinaan muulloinkin (suppenee ehdollisesti). Erityisesti: (eli joka toinen termi negatiivinen) suppenee, jos ja (Leibnizin lause).

4.2Yleisimpiä sarjoja

Aritmeettinen sarja

(ts. ). Perättäisten termien erotus on vakio. Hajaantuu aina, mutta osasumma on .

Geometrinen sarja

. Perättäisten termien osamäärä on vakio.

Suppenee arvoon , kun . Osasumma .

p-sarja

. Suppenee, kun ja hajaantuu muuten. Huomaa erityisesti, että eli harmoninen sarja (), hajaantuu (vaikkakin hitaasti). Summan yleistä kaavaa ei ole, mutta .

4.3Potenssisarjat

Potenssisarja on muotoa , missä on sarjan suppenemiskeskus.

Potenssisarja suppenee aina ja vain suppenemiskeskuksensa ympäristössä säteellä (), missä (kts. ”osamäärätesti” ylempää). Päätepisteet voivat joko kuulua tai olla kuulumatta :n määräämään suppenemisintervalliin.

Yhteenlaskettujen potenssisarjojen suppenemissäde on . Sama pätee myös keskenään kerrotuille potenssisarjoille (Cauchyn tulo):

Huom: Taylorin sarja on potenssisarja, jolle .

Erityisen tärkeä (geometrinen/Taylorin/McLaurinin) potenssisarja on:

4.4Fourier-sarja

t

• Määritelmä: -jaksoisen funktion Fourier-sarja (alueella ) on:

  

  ...tai kompleksimuodossa lyhyemmin:

  
• Jos on parillinen funktio (eli ), aina ja sarja supistuu “fourier-kosinisarjaksi”:
• Jos on pariton funktio (eli ), aina ja sarja supistuu “fourier-sinisarjaksi”: . (Huom: parittomuuden seuraus: )
• Kertoimien skaalaaminen vakiolla vasta :n skaalaamista

5Monen muuttujan analyysi

5.1Avaruuspinta

Kahdella muuttujalla parametrisoitu avaruuspinta:

Normaali:

Pinta-ala lasketaan seuraavasti:

5.2Raja-arvo

• Monen muuttujan funktion raja-arvo määritellään -ulotteisen, rajatta pienenevän pallon avulla
• Yleinen raja-arvo on olemassa vain, jos se on sama lähestymissuunnasta riippumatta. Esim. funktiolle , -akselia ja -akselia pitkin lähesteyttäessä, mutta suoraa pitkin lähestyttäessä, sillä , mutta .
• Raja-arvo voi myös olla olemassa kaikkia suoria pitkinä lähestyttäessä, mutta ei muita käyriä pitkin. Esim. , mutta .
• Funktio on jatkuva tietyssä pisteessä joss raja-arvo on siinä sama kuin funktion arvo. Funktiosta voi siksi tehdä jatkuvan määrittelemällä arvo epäjatkuvassa pisteessä sopivasti, joss raja-arvo on olemassa.

5.3Monen muttujan funktion differentiaalit

5.3.1Osittaisderivaatta

• Osittaisderivaatta on derivaatta jonkin muuttujan suhteen ja sitä merkitään "doo":lla, esim. .
• Korkeamman kertaluvun osittaisderivaatat voivat olla myös ns. sekaderivaattoja, esim. on derivoituna ensin :n ja sitten :n suhteen.
• Jos itse funktio ja sen alemman kertaluvun osittaisderivaatat ovat jatkuvia tietyssä pisteessä, eri järjestyksessä otetut sekaderivaatat ovat samoja. Epäjatkuvassa tapauksessa näin ei ole.

5.3.2Gradientti ja suunnattu derivaatta

N:n muuttujan funktion gradientti on -ulotteinen vektori, joka on koottu funktion osittaisderivaatioista. Gradienttia merkitään nabla- eli del-symbolilla:

• Funktio kasvaa aina nopeiten gradienttinsa suuntaan. Derivaatta k.o. suuntaan on .
• Gradienttivektori on aina tasokäyrän normaali (vrt. kukkula, jonka huipulta valuu vettä)
• Funktion derivaatta (kasvunopeus) mielivaltaiseen suuntaan on
• Liikkuvan tarkkailijan kokema kasvunopeus (nopeus ei välttämättä yksikkövektori!) on samoin

5.4Napakoordinaatisto

Kahden muuttujan funktioiden tasa-arvokäyriä voi toisinaan esittää kätevästi napakoordinaateilla. Muunnokset karteesisten ja napakoordinaattien välillä sujuvat seuraavilla kaavoilla:

5.5Monen muuttujan ääriarvotehtävät

5.5.1Ääriarvopisteiden luokittelu (Hessian)

Ääriarvopisteitä voivat myös monen muuttujan tapauksessa olla derivaatan (gradientin) nollakohdat () tai reunapisteet. Yhden muuttujan tapauksessa kriittisen pisteen tyypin voi määritellä toisesta derivaatasta:

• maksimi
• minimi
• ei tietoa (jos vaihtaa merkkiä :n kohdallasatulapiste)

Monen muuttujan tapauksessa luokittelu hoituu kyseisessä pisteessä lasketun Hessian-matriisin ominaisarvojen () avulla:

• kaikki maksimi
• kaikki minimi
• osa positiivisia, osa negatiivisia ei tietoa

5.5.2Rajoitetut ääriarvotehtävät (Lagrange-kertoimet)

Jos ääriarvotehtävässä vastauksiksi kelpaa vain osa kriittisistä pisteistä, voidaan tehtävä ratkaista muotoilemalla rajoitusfunktio ja minimoimalla/maksimoimalla alkuperäisen sijaan Lagrangen funktio...

...missä on nimeltään Lagrangen kerroin. Jos rajoituksia on enemmän, myös kertoimia ja rajoitusfunktioita voidaan ottaa mukaan enemmän. Esim:

6Skalaari- ja vektorikentät

• skalaarikenttä on ja vektorikenttä on .
• Skalaarikenttä on vektorikentän potentiaali, joss kaikissa pisteissä. (On ilmeisesti olemassa myös kaikille kentille määritelty vektoripotentiaali , jolle . Käyttötavasta ei käsitystä.)

• Vektorikenttä (tai esim. voima) on konservatiivinen, jos sillä on potentiaalikenttä (kaikilla vektorikentillä ei ole). Integraalin tapaan potentiaali ei ole yksikäsitteinen, vaan siihen voi lisätä mielivaltaisen vakion. Konservatiiviselle vektorikentälle pätee:

  

  Tai toisaalta: . Jos kenttä on konservatiivinen, potentiaalin voi laskea seuraavasti:

  

  (lopuksi ilmeisesti voi merkitä ja lisätä integrointivakion C)

• Vuo (Flux) on vektorikentän vektoreiden ja käyrän (2D) tai pinnan (3D) normaalin pistetulon summa (ts. paljonko vektoreita “virtaa” käyrän/pinnan läpi sen suuntaisesti). ja .

6.1Viivaintegraali

Viivaintegraali on viivan differentiaalisten tangenttivektorien () ja kentän tulon summa. Skalaarikentän tapauksessa tulo ja vektorikentän tapauksessa .

Viivaintegraali lasketaan parametrisoimalla :n -komponentin, derivoimalla ne :n suhteen, ottamalla tulo (piste- tai skalaari) ja integroimalla. Esim:

Joskus vektorikentän yli viivaintegraalia merkitään , mikä tarkoittaa samaa kuin ja se lasketaan samalla tavalla parametrisoidun :n ja :n pistetulona kuin yllä.

Tyypillinen esimerkki viivaintegraalista vektorinkentän yli on fysikaalinen työ, jonka voima tekee kuljettaessaan pistemäistä kappaletta käyrää pitkin.

6.1.1Greenin lause (suljetun käyrän viivaintegraali)

Tasolla suljetun käyrän viivaintegraalin voi joskus laskea helpommin seuraavasti:

...missä on käyrän sisään jäävä alue ja käydään läpi vastapäivään. Oikea puoli on siis pinta-integraali, jossa lasketaan ensin vaakasuuntainen integraali ja sitten pystysuuntainen (tai päinvastoin). Jos on reikäinen, lasketaan reikien seintän mukaan, mutta myötäpäivään.

6.1.2Stokesin lause (moniulotteiset pinnat)

Stokesin lause on Greenin lauseen laajennus moniulotteisille pinnoille:

6.2”Vektoriderivaatat” - grad, div, curl

Kentille voidaan määritellä kolme eri “derivaattaa”, joista jokainen on eri kerto-operaattorin ja nabla-operaattorin “formaali tulo”:

• Gradientti on vektorikenttä, joka osoittaa skalaarikentän nopeimman kasvun suunnan (kasvunopeus on k.o. vektorin pituus):

  

• Divergenssi on skalaarikenttä, joka kertoo kuinka paljon toinen vektorikenttä “etääntyy pisteestä ” eli tarkemmin sanottuna vuo äärettömän pienen -keskisen pallon (tasossa kiekon) sisältä:

  

  Divergenssin voi siis myös tulkita lähteen (esim. pistevarausten tapauksessa Diracin delta-funktio tai jatkvassa tapauksessa varaustiheys) voimakkuudeksi yksikkötilavuutta kohti.

• Curl (karmeasti suomennettuna roottori) on vektorikenttä, joka kertoo kuinka paljon kenttä “pyörii pisteen ympäri” eli tarkemmin sanottuna kiekon reunan muodostavien äärettömän monen tangenttivektorin () ja vektorikentän vektorien pistetulo kerrottuna kiekon () yksikkönormaalilla ():

  

Näille pätee kaikenlaisia yhtälöitä, mm.:

• eli
• eli
• ns. laplacian: tai vektorikentälle: . Skalaarikenttä on harmoninen jollain alueella, joss siellä pätee laplace-yhtälö .

6.3Divergenssilause (aka. Gaussin laki)

Vuo jonkin alueen D pinnan S läpi on yhtä suuri kuin kaikkien sen pisteiden divergenssien summa (=tilavuusintegraali):

Erityisesti: jos suljetun pinnan sisällä ei ole yhtään lähdettä (positiivista tai negatiivista, source tai sink), on kokonaisvuo sen läpi 0 kentästä riippumatta (mikä tulee sisään, menee myös ulos). Huomaa, että esim. pistevarausten tapauksessa lähteet ovat pistemäisiä Diracin delta-funktioita, joiden integraalilla on arvo vaikka niitä ympäröivä kiekko pienennettäisiin kuinka pieneksi tahansa.

Variaatioita (”curl-lause” ja ”gradienttilause”??), joiden tulos on vektori:

7Kompleksiluvut

• Imaginääriyksikkö ja
• moduli = , argumentti =vaihekulma=

• polaariesitys: (Eulerin kaava, muistisääntö: )

  ja

• pääarvo = = :n se arvo, joka on välillä

• liittoluku eli konjugaatti on . Sille pätee:

  , , ,

• kertolasku: =

  

• jakolasku: =

  . Huom. erityisesti:

• käänteisluku: tai
• potenssiin korotus () (De Moivren kaava):
• 

• :s juuri:

  Arvoja on siis kappaletta ja ne sijaitsevat tasaisin välein -säteisellä ympyrällä.

• kolmioepäyhtälö:

7.1Kompleksiset funktiot

• Merkitään , missä
• Jos on differentioituva tietyssä pisteessä . Lisäksi (Cauchy-Riemann-osittaisderivaattayhtälö).
• Jos ja on jatkuva on differentioituva.
• on analyyttinen, jos se on differentioituva :n naapurustossa (-säteisen kiekon sisällä kaikissa pisteissä). Lisäksi: on differentioituva äärettömässä jos on analyyttinen origossa.
• Jos on analyyttinen ja ovat harmonisia (ks. kahden muuttujan funktiot).
• 
• Ns. conformal mapping määräytyy yksiselitteisesti kolmella pisteellä: (:n sisältävät osamäärät korvataan :llä!). K.o. kuvaus muuttaa suoria ympyröiksi ja päinvastoin.

• Suljetun polun viivaintegraalin laskemiseen on kasa erilaisia sääntöjä, joista residuaalimenetelmä vaikuttaa erityisen hyödylliseltä. Kun polku ei leikkaa itseään ja on positiivisesti orientoitu ja on polun sisällä muuten analyyttinen, mutta :ssa pisteessä on singulaarinen napa (eng. pole), pätee Cauchyn residuaalilause:

  

  Jos polku on negatiivisesti orientoitu, lasketaan residuaalit negatiivisina. Huom: jos singulariteettejä ei ole, on integraali .

8Abstrakti algebra

= algebrallisia rakenteita (eli alkioiden ja niihin kohdistuvien operaatioiden yhdistelmiä) aksiomaattisesti (eli pieneen määrään perusoletuksia nojaavasti) käsittelevä oppi.

8.1Ryhmät (groups) ja monoidit (monoids)

Joukon ja siihen vaikuttavan jonkin operaation yhdistelmä, , on nimeltään:

• puoliryhmä (semigroup), jos on assosiatiivinen eli

• monoidi, jos lisäksi on olemassa neutraalialkio , jolle

  • jos on (additiivinen ryhmä), niin merkitään
  • jos on (multiplikatiivinen ryhmä), niin merk. 1. Merkitään myös .

• ryhmä (group), jos lisäksi kaikille alkioille on käänteisalkio:

  • jos on , niin käänteisalkiota nimitetään vasta-alkioksi ja merkitään
  • jos on , niin voidaan merkitä myös ja
• abelin ryhmä, jos se on lisäksi kommutatiivinen eli kaikille . Huom: myös puoliryhmä ja monoidi voivat olla kommutatiivisia.

Jos on äärellinen niin välttämättä ”pyörähtää ympäri” (kongruenssin tapaan) koska kaikille . Esim. ryhmässä ({0,2,4}, +) on mutta .

Lisää määritelmiä ja lauseita:

• alkion potenssi yhteensä kertaa.

  • jos on , niin potenssia merkitään
• ryhmän kertaluku (order) on sen alkioiden määrä
• aliryhmä on :n jonkin ei-tyhjän osajoukon ja ryhmän operaattorin yhdistelmä, jos myös kyseinen osajoukko on ryhmä kyseisellä operaattorilla (joss on ko. alijoukko ja ).
• triviaali aliryhmä on nimitys aliryhmille ja )
• suora tulo , on uusi ryhmä (jolla on uusi operaattori ) siten, että:
• homomorfismi on funktio ryhmien välillä, jos kaikille pätee .
• isomorfismi on homomorfismi, joka on lisäksi bijektio (eli kääntäen yksikäsitteinen, ts. on olemassa myös isomorfismi ). (esim. on isomorfismi , koska – ts. logaritmilla voidaan muuttaa :n kertolasku :n yhteenlaskuksi (kuten oli tapana ennen laskimia).
• ryhmiä sanotaan isomorfisiksi, jos niiden välillä olemassa isomorfismi ja ne voidaan tällöin samaistaa (rakenteellisesti).

• syklinen ryhmä on ryhmä, jonka kaikki alkiot ovat jonkin sen alkion potensseja. Kyseinen alkio virittää ryhmän (generates the group) ja merkitään . Viritetyn (usein ali-)ryhmän suuruus eli alkion kertaluku on .

  • jos on ääretön, syklinen ryhmä on isomorfinen :n kanssa
  • jos taas äärellinen ja , niin :n kanssa.
  • virittävälle alkiolle on
  • Syklisen ryhmän kaikki aliryhmät ovat syklisiä.
  • Kleinin ryhmä on pienin ei-syklinen ryhmä (yksikäsitteinen, kertaluku 4, en piirrä tähän).
  • Jokainen ryhmä, jonka on alkuluku, on syklinen. Syy:
• Lagrangen lause: jos on ryhmän aliryhmä, niin jakaa :n (eli )

Esimerkki: syklinen ryhmä , virittäjänä , on isomorfinen :n kanssa kun määritellään: :

ja aliryhmät :

8.2Renkaat (ring) ja kunnat (field)

Joukon ja sen kahden operaation ja yhdistelmä, , on algebrallinen rengas, jos:

1. on kommutatiivinen ryhmä ja
2. on puoliryhmä ja

3. distribuutiosäännöt pätevät:

   • 
   • 

Lisäksi:

• Renkaan ykkösalkio (ei aina olemassa) merkitään 1 ja määritellään
• Alkio on aito nollatekijä jos on olemassa , jolle tai .

• Yksikkö (unit) on alkio , jolla on jokin käänteisalkio (missä ).

  Huom: “yksikkö” “ykkösalkio” (:n neutraalialkio, unity)

• Kommutatiivinen rengas on rengas, jolle (ei esim. matriisirenkaissa).
• Kunta (field ) on kommutatiivinen rengas jonka kaikki ovat yksiköitä. (Esim. on kunta, mutta ei, koska esim. eli 4 ei ole yksikkö eli sillä ei ole kokonaisluku-käänteisalkiota.)
• Kokonaisalue (integral domain) on kommutatiivinen rengas, jolla ei ole nollatekijöitä (ekvivalentti ehto: ).
• Kaikki kunnat ovat kokonaisalueita ja kaikki äärelliset kokonaisalueet ovat kuntia.
• Jos alkiolla on käänteisalkio, se ei voi olla nollatekijä kunnassa ei ole lainkaan aitoja nollatekijöitä.
• on kommutatiivinen, ykkösalkiolla varustettu rengas ja sen alkiolla on käänteisluokka joss . Joss on alkuluku, on (myös) kunta (eli kaikilla alkioilla, ts. kongruenssiluokilla, on käänteisalkio).
• Kaikkien äärellisten kuntien koko on muotoa , missä on alkuluku ja .
• Alirangas on rengas, jonka alkioina on jonkin toisen renkaan alkioiden osajoukko.
• Ideaali alirengas on :n alirengas, jolle 1) kaikkien sen alkioiden erotuksetkin kuuluvat :hin (ts. kaikille ) ja 2) myös kaikille pätee .

• Kaikki :n alirenkaat ovat ideaaleja ja niiden alkiot ovat muotoa .

  Tästä johtuu: .

• Renkaan karasteristika on on pienin , jolle . Jos yhtään tällaista lukua ei ole olemassa, .
• Jos kyseessä on kunta ja , on alkuluku. Kuntien , ja karasterika on , mutta on olemassa äärettömiä kuntia, joiden (esim. ).
• Rengashomomorfismi on funktio (missä ja ovat renkaita), jos kaikille on ja . Jos on lisäksi bijektio (kääntäen yksikäsitteinen kuvaus), se on isomorfismi. Renkaat ovat keskenään isomorfisia jos niiden välillä on olemassa isomorfismi.
• “Matriisirengas renkaan yli” eli on -neliömatriiseista koottu rengas, jonka matriisialkiot ovat :n alkioita. Matriisikertolaskun epäkommutatiivisuudesta johtuen on harvoin kommutatiivinen vaikka olisikin.

8.3Polynomirenkaat

Jos on rengas (vaika -kunta, tai äärellinen -rengas tai vaikka matriisirengas):

• ”Muuttujan -polynomi” on muotoa , missä .
• Johtokerroin on polynomin korkeinta astetta oleva termin kerroin .
• Vakiotermi on (nollapolynomi, jos ).
• Merkintätapa: = muuttujan kaikkien -polynomien (ääretön) joukko.
• Äärettömällekin joukolle :n polynomeja on yleisessä tapauksessa useita esitystapoja. Esim. jos niin , koska .
• Jos polynomin kertoimet ovat ja :n kertoimet niin :n tulon termien kertoimet ovat . Huom: jos -renkaassa on aitoja nollatekijöitä, tulon aste saattaa olla pienempi kuin :n ja :n asteiden summa.
• ”Polynomirengas yli ”:n on rengas .
• Juuri on :n arvo, jolla polynomin arvoksi tulee nolla-alkio. Huom: yleisessä tapauksessa (kun -rengas ei ole kokonaisalue) :n polynomeilla voi siis olla niiden astetta enemmän juuria.
• on redusoituva eli jaollinen, jos sen aste on ja joillekin , joiden aste on . Jaoton polynomi on redusoimaton. Huom: redusoituvuus riippuu :stä: esim. on jaoton, mutta jaollinen: .
• Jos on kunta ja polynomi on astetta 2 tai 3, se on redusoituva/jaollinen joss sillä on juuri :ssä.
• Polynomien suhteellinen redusoimattomuus: vakio (eli astetta nolla).
• Normeerattu polynomitulo on tekijöihin jaetun polynomin yksikäsitteinen esitysmuoto, jossa koko lauseke on kerrottu vakiolla ja kaikkien tekijöiden (redusoimattomia, ts. jaottomia polynomeja) johtokerroin on :

• Eri polynomirakenteiden määrä voidaan rajata (tavallisesti äärettömästä :stä) äärelliseksi kongruenssilla: valitaan jokin polynomi ja määrätään, että kaikkien renkaan operaatioiden tuloksesta otetaan lopuksi jakojäännös :llä. Merkitään: . Jos on redusoituva, tulos on rengas ja jos taas redusoimaton niin kunta. Esim. polynomikunnan operaatiot ovat:

  ja

  Jos on ääretön, on tietysti myös ääretön vaikka eri polynomimuotoja onkin rajallisesti. Esim. on isomorfinen :n kanssa.

• Galois-kunta polynomikunta , missä on, kertalkua oleva redusoimaton, normeerattu polynomi. :n löytäminen ei ole yleensä helppoa, mutta siihen on olemassa algoritmeja. Galois-kunnan karasteristika .
• :n fundamentaalikunta on sen alikunta . Erityistapaus: eli yksinkertaisen (siis ”ei-moninkertaisen”) alkuluvun Galois-kunta on oma fundamentaalikuntansa.
• Jokainen kokoinen (eli “kertalukua oleva“) kunta on isomorfinen :n kanssa.

8.4Kooditeoria

Boolen algebran (symbolien jonoista sekä operaatioista koottu logiikka-algebra) sovellus: siirretään -bittisiä viestejä () häiriöisellä linjalla, joka voi aiheuttaa mihin tahansa siirrettävään bittiin virheen (ts. ) todennäköisyydellä , bitin sijainnista ja alkuperäisestä arvosta riipumatta.

• Virherakenne :ssä on niissä kohdissa joissa siirretyssä viestissä on virhe ja niissä, joissa bitti siirtyi oikein. Kun =virhebittien (-bittien) määrä eli virheen paino:

  • Tietyn virherakenteen esiintymisen todennäköisyys on
  • Tasan virhettä sisältävän siirron todennäköisyys on
• -blokkikoodaus muuttaa -bittiset viestit -bittisiksi jonoksi lisäämällä niihin kpl. tarkistusbittejä jolloin koodauksen tehosuhde on ().
• Hamming-etäisyys on kahdessa bittijonossa toisistaan eroavien bittien määrä.

• Kun viestejä välitetään käyttäen joukkoa koodisanoja, kaikki painoa olevat virheet voidaan:

  • havaita, jos eri koodisanojen minimietäisyys on vähintään
  • korjata, jos eri koodisanojen minimietäisyys on vähintään
• Koodaus on ryhmäkoodi joss sen tuottamat koodisanat ovat :n aliryhmä. Ryhmäkoodeilla koodisanojen Hamming-minimietäisyys on niiden nollasta eriävien koodisanojen minimipaino (eli niiden keskinäisiä etäisyyksiä ei tarvitsekaan laskea).

• Koodauksen generoiva matriisi on jolla oikealta kertominen tuottaa viestisanoista koodisanat: (missä on -vaakavektorina esitetty viesti ja on -vektorina esitetty koodisana). Esim: eräs -koodaus:

  
• Generoiva matriisi on normalisoitu eli systemaattinen jos se on muotoa eli vasemmalla on alimatriisina yksikkömatriisi. Minkä tahansa generoivan matriisin voi normalisoida ja tuloksena on ekvivalentti koodaus.
• Tarkistusmatriisi on , jolle :n syndrooma eli joss on jokin käytetyistä koodisanoista. Normalisoitu muoto on . Huom: syndrooman laskussa pystyvektorina esitetty viesti kerrotaan :lla vasemmalta.
• Jos vastaanotetussa viestissä on virhe vain yhdessä bitissä, i , on :n :s pystyrivi. (Yleisesti: syndrooma on virhebittejä vastaavien :n pystyrivien summa.)
• Generoivalla matriisilla esitetty koodaus on ryhmäkoodi.
• Hamming-koodaus: tarkistusmatriisi ] eli Hammingin matriisi on kokoa ja sen pystyrivit on koottu lukujen binääriesityksistä jossain järjestyksessä. Vastaava generoiva (eli koodaus-) matriisi on . Hamming-koodauksella siirretään -mittaisia viestejä, sillä voidaan korjata yksi virhe ja sen tehosuhde on .

9Kombinatoriikka

9.1Permutaatiot ja kombinaatiot

• permutaatio = uudelleenjärjestely/sekoitus
• kombinaatio = yhdistelmä, jossa järjestyksellä ei ole väliä
• R-permutaatioiden määrä = “montako erilaista :n pituista järjestettyä jonoa voidaan muodostaa :stä eri alkiosta“ = . Huom:
• R-kombinaatioiden määrä = “montako erilaista :n kokoista joukkoa voidaan valita :stä eri alkiosta kun järjestyksellä ei ole väliä“ = . Huom:

• Toistopermutaatioiden määrä = “monellako toisistaan erottuvalla tavalla voidaan järjestää kpl. :sta eri luokasta valittua alkiota, kun luokasta 1 valitaan kpl, luokasta 2 valitaan jne.” =

  (missä siis )

• Kyyhkyslakkaperiaate: “Jos on kyyhkystä ja pesää, vähintään yhdessä pesässä on 2 kyyhkystä” (kaikki voivat olla myös samassa pesässä!)

• ”:n eri alkion mahdollisten luokittelujen määrä :hon luokkaan jaettaessa kun osa luokista saa olla tyhjiä“ =

  “:sta eri merkistä koottujen :n pituisten merkkijonojen pituus“ =

• Yhtälön ratkaisujen määrä, kun =

  “Monellako tapaa voidaan järjestää pallon ja erottimen muodostama jono” =

  

  “Monellako tavalla voidaan valita pallojen paikat” =

  “Monellako tavalla voidaan valita erotinten paikat” = .

  Esim:

  “Monellako tavalla 7 eri henkilöä voi valita 4:stä eri ruokalajista?“ =

  “Montako ratkaisua on positiivisella kokonaislukuyhtälöllä ?”=

  “Monellako (erottuvalla) tavalla voidaan järjestää jono '|||ooooooo'?” =

• Väärinjärjestysten määrä = “Monellako tapaa voi järjestää alkiota niin, ettei mikään ole omalla paikallaan“ =
• “:n eri alkion mahdollisten luokittelujen määrä :hon ei-tyhjään luokkaan jaettaessa” (esim. ) eli 2. lajin Strilingin luvut = (rekursiokaavana:
• “:n eri alkion kaikkien mahdollisten luokittelujen määrä” eli Bellin luvut =

9.2Inkluusio-ekskluusio-periaate

Inkluusio-ekskluusio-periaatteella lasketaan osittain päällekkäisiä ehtoja täyttävien alkioiden / tapausten määriä: ensin päällekäisten joukkojen koot lasketaan yhteen ja sitten tuloksesta vähennetään niille yhteisten alkioiden määrä (ettei sitä oteta mukaan kahteen kertaan). Ongelmia kannattaa visualisoida Venn-diagrammilla. Merkintätapoja:

Joukko , jonka koko , koostuu alkioista, jotka toteuttavat kukin joitain (tai vaikka kaikki tai ei yhtään) :stä eri ehdosta (esim. esinettä ja 4 ehtoa: =“alkio on pallo“, =“alkio on vihreä“, ”alkio on sininen“, =”alkio on painava” jne). Vähintään yhden ehdoista toteuttavien alkioiden määrää merkitään ja niitä, jotka eivät toteuta niistä mitään (mutta voivat toteuttaa jotain muita!) merkitään .

Ei yhtään ehtoa täyttäviä alkioita on:

Yleisesti: tasan ehtoa täyttäviä alkioita on:

9.3Binomi- ja multinomikertoimet

Binomilause määrää termien kertoimet kun binomi kerrotaan auki polynomiksi:

Kerroin :nnen asteen :lle on siis n:n k-kombinaatio. Binomikertoimia kuvataan usein Pascalin kolmiolla, jonka jokainen reuna-alkio on 1 ja jokainen sisäalkio aina kahden heti sen yläpuolella olevan alkion summa. Multinomilause yleistää tuloksen:

Joskus tarvitaan “binomikertoimia“, joissa tai : yleistetyt binomikertoimet:

...tai jos :n tilalla onkin negatiivinen kokonaisluku () eikä desimaaliluku, niin:

9.4Generoivat funktiot eli emäfunktiot

Emäfunktiolla voi ratkaista mekaanisesti erilaisia kombinatorisia tehtäviä (“montako erilaista / monellako tavalla“ ja jopa “luettele kaikki“ eli enumerointi) esittämällä jonot polynomeina. Algebrallisen pyörityksen jälkeen tulos katsotaan suoraan polynomin halutun asteisteisten termien kertoimista eikä itse polynomiin sijoiteta mitään!

• tavallinen emäfunktio (sopii kombinaatiolle)
• eksponentiaalinen emäfunktio (permutaatioille)
• muitakin emäfunktoita on (esim. kahden muuttujan versio)

Esim. (tavallinen emäfunktio): ”Montako positiivista kokonaislukuratkaisua on yhtälöllä , kun ja ?” Tämä ratkeaa kertomalla auki polynomi (tavallinen emäfunktio)...

...ja ottamalla siitä :n kerroin (14). Muuttujan potenssit esittävät :n, :n ja :n arvoja ja niiden kertoimet (, tässä tapauksessa 1 kaikille mainituille ja muille 0) merkitsevät “monellako tavalla kyseinen arvo voi tulla valituksi kyseiselle muuttujalle”. Ym. lauseen voi siis lukea tulkitsemalla =“tai“, =“ja“ (kuten Boolen algebrassa): “jos (a=4 tai a=5 tai ...) ja (b=2 tai b=3 tai ..) ja ...“. Auki kerrottu polynomi esittää näiden eri kombinaatioita ja siitä näkee myös, että esim. ratkaisuja olisi 16 kpl.

Polynomien kertominen keskenään on työlästä, joten laskemisessa hyödyllisiä ovat potenssisarjojen laskusäännöt (Huom: suppenevuusehdoilla ei tässä ole mitään väliä, koska :ään ei oikeasti sijoiteta mitään):

A) äärettömät jonot (sarjat):

B) äärelliset jonot:

C) (permutaatioiden laskemista varten) eksponenttifunktiot:

Epäsäännöllisempiä sarjoja voi esittää laskemalla eri emäfunktioita yhteen tai vähentämällä yksittäisiä termejä, esim. .

Ongelmassa esiintyvät jonot kirjoitetaan ensin emäfunktioiksi (eli ”siirrytään taulukossa oikealta vasemmalle”), sievennetään sitten niiden yhdistelmä (esim. summa) ja muutetaan tulos sitten takaisin sarjamuotoon (ts. “taulukossa takaisin vasemmalta oikealle”). Menettely muistuttaa siis hieman Laplace-muunnoksen käyttöä ja myös emäfunktioissa “käänteismuunnos” vaatii usein osamurtokehitelmää (esimerkki differenssiyhtälöt-kappaleen lopussa).

Joitain generoivia funktioita (Huom! nämä siis määrittelevät lukujonoja, eivätkä annan itse määriä!):

• Väärinjärjestysten määrä:
• Fibonaccin luvut (): ()
• Catalanin luvut ( eli esim. “Erilaisten -kärkisten binääripuiden määrä“): ()
• “Luvun ositusten määrä ”: . Ositus = luvun kokoaminen termeistä (esim. 4=1+3=1+1+2=2+2=4). Tekijät eivät vaikuta vastaukseen, joten äärettömän tulon voi katkaista ja käyttää (kertomalla versiot yhteen) sarjaa .

9.5Tornipolynomit (rook polynomials)

• Tornipolynomi = emäfunktio, jolla lasketaan “Monellako tavalla voidaan asettaa toisiaan uhkaamatonta (nontaking) tornia tietyn muotoiselle shakkilaudalle kun osa ruuduista on kiellettyjä ()?”
• ”Uhkaamaton” = mikään nappula ei saa olla samalla rivillä eikä sarakkeella toisen kanssa.
• Vastausta merkitään kun on lauta. Esim. ja , kun .

• Tornipolynomi generoi :n kaikille . Esim:

  (tarkoittaa: 1 tapaa asettaa 0 tornia, 6 tapaa 1 torni, 8 tapaa 2 ja 2 tapaa 3 tornia)

• Jos kiellettyjä ruutuja on vähemmän kuin sallittuja, voidaan laskea käänteisen (vaihdetaan kielletytsallitut) laudan polynomi ja solveltaa inkluusio-ekskluusio-kaavaa:

  

  (MUTTA: miten saa :n mielivaltaiselle eikä vain tapaukselle ??)

• Jos lauta koostuu erillisistä osista (ts. ei yhteisiä rivejä eikä sarakkeita), on koko laudan polynomi sen erillisten osien polynomien tulo:

  

• Lautaa voidaana jakaa kahdella tekniikalla vaikka erillisiä osia ei heti näkyisikään:

  1. siirtelemällä rivejä ja sarakkeita (ei vaikuta tulokseen)

  2. valitsemalla yksi rutuu jostain strategisesta paikasta ja laskemalla yhteen tapaukset, joissa siinä a) on nappula [poistetaan myös kaikki sen uhkaamat ruudut] tai b) ei ole nappulaa [poistetaan vain kyseinen ruutu]

     

Esimerkki: Johdetaan ym. :n tornipolynomi ilman käänteisen laudan temppua, sijoittamalla kokeeksi nappula vasemmalle ylös laudanjakotekniikan 2 mukaisesti:

9.6Differenssiyhtälöt eli rekursiot

(...eli rekurrenssiyhtälöt eli palautuskaavat)

• Alkion arvo riippuu :sta edellisestä alkiosta ja :stä: . Vakio on differenssiyhtälön kertaluku.
• Terminologia pitkälti samaa kuin differentiaaliyhtälöissä
• Homogeenisten, lineaaristen yhtälöiden yleiset ratkaisut saa erityisratkaisujen lineaarikombinaationa (kuten differentiaaliyhtälöissäkin)
• Helpoille tapauksille on ratkaisukaavoja ja hankalampiin voi usein käyttää emäfunktioita

9.6.1Lineaariset ja vakiokertoimiset

Ratkaisukaavoja:

• Ensimmäisen kertaluvun vakiokertoimisen, lineaarisen ja homogeenisen yhtälön eli

  (tai ) yleinen ratkaisu on (kun ). Huom: .

• Toisen kertaluvun vakiokertoiminen, lineaarinen ja homogeeninen yhtälö (kuten Fibonaccin luvut) eli (missä ) ratkeaa sijoittamalla :n tilalle yritefunktioksi ensimmäisen kertaluvun ratkaisu :

  

  Tämä on karakteristinen polynomi ja rekursion ratkaisu riippuu sen juurista ja lineaarikombinaatiolla:

  • 2 reaalista, erisuurta juurta ( ovat mielivaltaisia vakioita)
  • kompleksikonjugaatit samalla tavalla ( ja eliminoivat toistensa imaginääriosat), mutta laskeminen on vähän hankalampaa ja se kannattaa tehdä polaarikoordinaateissa kompleksiluvun potenssiin korotuksen takia
  • kaksinkertainen juuri (eli )

  Sama konsti toimii korkeammankin kertaluvun yhtälöille, mutta polynomin ratkaisu menee turhan hankalaksi.

• Epähomogeenisten versioiden ratkaisut saa kaavasta eli homogeenisen version yleinen ratkaisu + epähomogeenisen jokin yksittäisratkaisu. Jos epähomogeeninen osa sattuu olemaan muotoa , niin:

  • Ensimmäinen kertaluku (eli ):

    1. jos se ei satu olemaan myös :n ratkaisu tai
    2. , jos sattuu

  • Toinen kertaluku:

    1. jos se ei satu olemaan myös :n ratkaisu tai
    2. jos sattuu, ja on muotoa tai
    3. jos sattuu, ja on muotoa

9.6.2Ratkaisu emäfunktioilla

Ideana on etsiä ensin rekursiota esittävä emäfunktio suljetussa muodossa (potenssisarjojen laskusäännöillä) ja sitten etsiä toiseen suuntaan sitä vastaava sarja.

Esimerkki: “Mikä on sarjan :s alkio?”

1. Valitaan ja nimetään sarjaan “sovitettava” emäfunktio – valitaan tässä: (eli tavallinen emäfunktio)

2. Esitetään molemmat puolet :n avulla (siten, ettei yhtään :ää jää jäljelle). Aloitetaan kertomalla :llä ja summataan sitten yli.

   

3. Ratkaistaan :n suhteen:

   

4. Etsitään saadulle emäfunktiolle sarjaesitys. Käytetään osamurtokehitelmää (Heaviside) ja potenssisarjojen laskusääntöjä:

   

Viimeisestä summasta nähdään suoraan, että emäfunktion sarjaesityksen :s kerroin, eli alkuperäisen sarjan , on .

9.7Permutaatioryhmät ja ekvivalenssiluokat

Tulkitaan geometrisen objektin (esim. neliön) eri värisiksi värjättyjen kärkien kiertoja ja peilauksia/3D-rotaatiota (eli liikeryhmää) permutaatioina ja lasketaan montako erinäköistä objektia voidaan tehdä jos niitä saadaan pyöritellä vapaasti. Määritelmiä:

• symmetrinen ryhmä on bijektioiden muodostama algebrallinen ryhmä (ts. :n alkion kaikkien erilaisten permutaatiofunktioiden ryhmä)
• permutaatioryhmä tarkoittaa :n aliryhmää, ts. , vaikka olisikin
• tulo (”tyhjä operaattori”) tarkoittaa yhdistettyä (2 peräkkäin tehtyä) permutaatiota
• permutaatioryhmä ei ole kommutatiivinen (aabelin ryhmä), jos . Suomeksi: permutaatioiden järjestyksen vaihtaminen voi muuttaa tulosta.
• Caleyn lause: ”jokainen ryhmä voidaan esittää permutaatioryhmänä” eli sille on isomorfismi viimeistään :ään (ja usein jo :ään, missä ).
• permutaation matriisiesitys: , josta näkee mikä alkio vaihtuu minkäkin paikalle.
• Toinen esitystapa: erillisten syklien tulo eli erilliset esittäjät: (sama permutaatio kuin edellisen esimerkin matriisissa). Tässä edellinen vaihtuu aina seuraavan paikalle ja viimeinen pyörähtää ensimmäisen tilalle. Esim: . Yhden mittainen sykli = alkio ei vaihda paikkaa.

Kun merkitään kärkien eri väritystapoja (konfiguraatioita) :llä (neliön ja kahden värin tapauksessa niitä on yhteensä kpl: ) ja permutaatioita :llä (neliön tapauksessa 8 kpl, kun lasketaan erilaiset kierrot ja peilaukset: , missä = kierto = ”ei muutosta”), niin:

• Ekvivalenssiluokka on niiden väritystapojen joukko, jotka voidaan muttaa toistensa näköisiksi :n permutaatioilla. Ts. ekvivalenssiluokkien määrä = “oikeasti erilaisten” väritysten määrä.
• Väritystavan -rata on niiden väritystapojen joukko, joiden näköisiksi :n permutaatiot voivat :n muuttaa. Sen -rata () taas on niiden väritysten joukko, joiksi ryhmä (eli :n potenssien muodostama :n aliryhmä) voi sen muuttaa.
• Värityksen/konfiguraation stabilisaattori on aliryhmä , jonka sisältämät permutaatiot eivät muuta :stä lainkaan
• :n kiintopiste on jokin , joka ei muutu millään permutaatiolla . Tasaväritykset ovat tietysti aina kiintopisteitä.

• Burnsiden lemma: = ekvivalenssiluokkien määrä, kun = “:tä sovellettaessa muuttumattomien konfiguraatioiden määrä”.

  Esimerkki: “monellako tavalla 6 ihmistä voi sijoittaa pyöreän pöydän ympärille?”. kierto, kun . Erilaisia konfiguraatioita pyörittämättömälle pöydälle on , joten ja koska kukaan ei pysy paikallaan vähänkään pyöritettäessä, . Vastaus: . (Yleisesti: syklinen järjestys voidaan valita tavalla.)

• Sykli-indeksi helpottaa laskemista: :n sykli-indeksiesitys on , :n esitys on ja esim. :n on . Sykli–indeksi...

  

  ...antaa :n eri värin värityksen ekvivalenssiluokkien määrän sijoituksella .

• Polyan lause: kun on käytettävissä eri väriä, erilaisten väritysten inventaariolle, eli eri kombinaatioiden määrien luetteloinnille, saadaan emäfunktio sijoituksella...

  

  ...missä on väriä esittävä muuttuja. Huom: :n ei sijoiteta mitään vaan tulos katsotaan kertoimista, koska kyseessä on emäfunktio.

  Esim.: “Montako eri tapaa on värittää 3-lapainen potkuri kun väreinä on r,g ja b?” Permutaatioryhmä eli kierrot , ja , joiden sykli-indeksiesitykset ovat ja . Inventaario-emäfunktio saadaan siis seuraavasti:

  

  Polynomista nähdään, että on 2 eri tapaa (termi ) kun käytetään kaikkia kolmea väriä (ja 1 tapa kaikilla muilla värikombinaatioilla). Termien kertoimia voi usein laskea multinomilauseen avulla kertomatta koko polynomia auki.

10Jaollisuus ja moduloaritmetiikka

• Jos on jaollinen :llä, sanotaan " jakaa :n" ja merkitään: . Jos , jakaa sanotaan :n jakavan aidosti (vrt. "aito osajoukko ( vs. )").
• Alkuluku on luku, jolla ei ole yhtään :stä poikkeavaa aitoa tekijää.
• Aritmetiikan peruslause: jokainen positiivinen kokonaisluku voidaan esittää yksikäsitteisesti alkulukujen tulona (eli ) jokainen ei-alkuluku on jaollinen jollain alkuluvu(i)lla

10.1Jaollisuussääntöjä

• 
• 
• Jos ja jakaa kaksi muuttujista, jakaa se kaikki kolme.
• Jos jakaa luvut , jakaa se myös näiden lineaarikombinaatiot: .
• Luvut ja ovat suhteellisia alkulukuja eli keskenään jaottomia, jos niiden suurin yhteinen tekijä on eli eli on olemassa siten, että .

10.1.1Suurin yhteinen tekijä (GCD) ja pienin yhteinen jaettava (LCM)

Suurin yhteinen tekijä (syt tai gcd, Greatest Common Denominator) merkitään tai ja on suurin luku , joka jakaa kaikki eli . Kahdelle muuttujalle voidaan merkitä myös , missä .

S.y.t löytyy Euklideen algoritmilla: jaetaan joka askeleella jäljellä oleva luku edellisen askeleen jakojäännöksellä ja lopetetaan kun jäännöksestä tulee 0. Viimeinen ei-nolla jäännös on s.y.t. Algoritmi toimii myös useammalle kuin kahdelle luvulle, sillä . Esim. :

Lineaarikombinaatioesityksen kertoimet ja (ja sen avulla Diophanteen yhtälön ratkaisun) löytää tästä peruuttamalla. Aluksi ratkaistaan ketjun toiseksi viimeinen rivi jakojäännöksen suhteen, sitten ratkaistaan edellinen rivi samalla tavalla, yhdistetään ne ja supistetaan, ratkaistaan kolmanneksi viimeinen rivi ja jatketaan samaan tapaan alkuun asti:

Pienin yhteinen jaettava (pyj tai lcm, Least Common Multiple) merkitään tai ja on pienin luku, jonka kaikki jakavat eli li .

10.1.2Lineaariset Diophanteen yhtälöt

Diophanteen yhtälö on yhtälö, jonka ratkaisuksi sallitaan vain kokonaislukja. Lineaarinen kahden muuttujan versio: , jossa .

• Ratkaisuja on olemassa (äärettömästi) joss .

• Yksittäisratkaisun jälkeen yleisen ratkaisun saa kaavalla

  

  ...missä ja tarkoittavat s.y.t:llä jaettuja versioita kertoimista. Huom! :n kohdalla on ja :n kohdalla eikä päinvastoin!

• Yksittäisratkaisun saa mekaanisesti ratkomalla Euklideen algoritmin jälkeen peruutuksella :n ja :n yhtälöstä ja kertomalla ne sitten :llä. Esim: ratkaistaan :

  1. Etsitään edellisen kappaleen Euklid-esimerkin mukaan
  2. Etsitään peruutustekniikalla ratkaisut väliaikaiselle yhtälölle (myöskin edellisen kappaleen esimerkin mukaan)
  3. Todetaan, että ja sen perusteella, että eli

10.2Kongruenssi eli moduloaritmetiikka

• "kongruenssi modulo " merkitään ja tarkoittaa, että eli
• Kongruenssiluokka (eli jäännösluokka eli ekvivalenssiluokka) merkitään , ja se tarkoittaa kongruenssiaritmetiikan numeroa. Esim: modulin suhteen (koska ja )
• Kongruensiluokan käänteisluokka on siten, että . Esim: , koska
• Kongruenssiyhtälö vastaa Diophanteen yhtälöä .
• Kongruenssiaritmetiikka tietyllä modulolla vastaa algebrallista rengasta (tai kun on alkuluku niin kuntaa) (ks. ”renkaat ja kunnat” kappaleesta ”abstrakti algebra”).
• Käänteisluokka on olemassa kaikille luokille joss (=moduli) on alkuluku. Tällöin vain 1 ja -1 ovat itsensä käänteisalkioita (ts. ). Muillakin moduleilla voi kyllä olla yksittäisiä käänteistyviä luokkia.
• Korkea potenssi lasketaan ottamalla välituloksista jakojäännös ja jatkamalla siitä. Tehokas tapa :n laskemiseen on laskea ensin peräkkäisillä neliöinneillä ja kertoa niitä sitten yhteen :n binääriesityksen mukaan ottamalla joka askeleen jälkeen.
• Wilsonin lause: , kun on alkuluku. Ei ole käytännöllinen alkulukutesti, koska kertoman laskeminen on hidasta.
• Fermat'n pieni lause: , kun (ei joss!) on alkuluku ja (ts. ei ole :n tekijä, ts. )

• Eulerin fii-funktio on alkioiden , joille , eli :ää pienempien suhteellisten alkulukujen, määrä. Sääntöjä:

  • joss on alkuluku. Tällöin myös:
  • jos , niin
  • (kun ) eli :n alkutekijöistä
  • Eulerin lause: , kun . (Jos , saadaan mod .)

10.3Suuret alkuluvut

• Alkulukuja on äärettömän paljon.
• On olemassa sekä alkulukukaksosia, joiden erotus on 2, että mielivaltaisen pitkiä lukujonoja joissa ei ole yhtään alkulukua.

• Luvun hajottaminen alkutekijöihin on erittäin raskas operaatio. Huomioita:

  • Jos pienillä alkuluvuilla testatessa tulee osuma, ts. , hakua :lle pitää jatkaa :stä (sama tekijä voi esiintyä useita kertoja)
  • :n alkutekijöissä voi olla max. 1 alkuluku . Kaikki muut ovat tätä pienempiä on alkuluku ellei mukaan lukien ole löytynyt yhtään tekijää
  • Tehokkain tunnettu tekijöintialgoritmi on työmäärältään
• Fermat'n pienellä lauseella (, kun on alkuluku) voi usein todeta, että ei ole alkuluku, mutta se ei ole pitävä testi.
• ”Pseudoalkuluku kannassa ” on jaollinen luku , joka läpäisee Fermat'n pienen lauseen testin ja jolle . Niitäkin on äärettömän monta, mutta paljon harvemmassa kuin oikeita alkulukuja.
• Carmichaelin luku on pseudoalkuluku kaikissa kannoissa . Erittäin harvinaisia, mutta niitäkin oletetaan olevan äärettömästi. Fermat'n pieni lause ei teoriassakaan ole aivan täydellinen alkulukutesti.

• Millerin testi: pariton ei ole alkuluku jos, kun on pariton, joko:

  1. tai
  2. jollekin
• ”Vahva pseudoalkuluku kannassa ” on jaollinen luku , joka läpäisee Millerin testin kannassa . Vain oikeat alkuluvut läpäisevät testin kaikissa kannoissa .
• Rabinin todennäköisyystesti: todennäköisyys sille, että jaollinen luku on vahva pseudoalkuluku kaikissa kannoissa on pienempi kuin .

10.3.1RSA-salakirjoitus

• Avaimien luonti: valitaan kaksi alkulukua ja lasketaan niiden tulo .

  • Julkinen avain eli salakirjoitusavain on pari , missä on jokin luku, jolle .
  • Salainen avain eli purkuavain on pari , missä .
• Viesti muutetaan/jaetaan lohkoiksi
• Salaus:
• Purku:
• Allekirjoituksessa käytetään avaimia nurinperin: salataan purkuavaimella ja puretaan salausavaimella.
• Luvuilla ja pitää olla suuria tekijöitä ja :n ja :n on oltava jonkin verran eri pituisia, ettei ratkea liian helposti. Luvut ovat niin suuria, että käytännössä sovelletaan Rabinin todennäköisyystestiä, koska täydellisen Millerin testin ajo kestäisi liian kauan.

11Graafit

• Silmukka (loop) on sivu, joka alkaa ja päättyy samaan solmuun (älä sekoita kierrokseen (cycle)!)
• Kierros on polku, jonka alku- ja loppusolmu ovat samat
• Lineaarinen eli yksinkertainen graafi on sellainen, jossa jokaista mahdollista sivua on korkeintaan yksi eikä siinä ole yhtään silmukkaa - ei-lineaarinen graafi on multigraafi
• Kaksi solmua ovat naapureita, jos niiden välillä on sivu
• Kaksi solmua on yhdistetty, jos niiden välillä on jokin polku
• Graafi on täydellinen, joss kaikki kärjet on yhdistetty kaikkiin muihin kärkiin
• Graafin ja sen aligraafin komplementti on muuten sama kuin , mutta siitä on poistettu :n sivut
• Graafi on yhtenäinen, jos kaikkien solmujen välillä on polku
• Puu on suunnistamaton, lineaarinen, yhtenäinen, kierrokseton graafi, metsä muuten sama, mutta ei yhtenäinen
• Suunnistamattoman graafin kärjen aste on siihen tulevien sivujen määrä - suunnistetulle on määritelty erikseen tuloaste ja lähtöaste.
• Graafit ovat isomorfisia (, jos niillä on sama rakenne (eli voidaan määritellä kääntäen yksikäsitteiset funktiot, jotka mappaavat solmut ja sivut graafista toiseen)
• Graafin sulkeuma on yleistetyn naapurimatriisin :s potenssi ja ilmaisee solmusta toiseen olevien n-pituisten polkujen määrän
• Graafien konfiguraatio on sama, jos ne ovat isomorfisia kun molemmista poistetaan ne ja poistetaan astetta 2 olevat kärjet
• Eulerin polku käsittää kaikki sivut tasan kerran (vastaavasti Eulerin kierros)
• Hamiltonin polku käsittää kaikki solmut tasan kerran (vastaavasti Hamiltonin kierros)

11.1Lauseita

• Eulerin kierros suunnistamattomassa graafissa on olemassa joss graafi on yhtenäinen ja kaikkien solmujen asteet ovat parillisia. Eulerin polku joss tasan kaksi paritonta kärkeä (jotka voitaisiin periaatteessa yhdistää, jolloin saadaan kierros).

• Hamiltonin polulle/kierrokselle ei ole yksikäsitteistä olemassaololausetta, mutta:

  • polkua ei ole ainakaan, jos on yli 2 kärkeä, joiden aste
  • kierros on olemassa ainakin, jos kaikkien kärkien aste
• Graafi on tasograafi (eli levitettävissä tasoon ilman leikkaavia sivuja) joss se ei sisällä kaksijakoisen graafin (3+3 solmua kahdessa rivissä, ylärivin kaikki solmut yhdistetty kaikkiin alarivin solmuihin mutta ei toisiin ylärivin solmuihin, ts. 9 sivua) eikä täydellisen 5-graafin konfiguraatiota. (=Kuratowskin lause)
• Yhtenäinen tasograafi rajaa tasolle aluetta, ääretön alue mukaan lukien (=Eulerin kaava)
• Jos tasograafissa on yli 1 sivu ja tasoalueita kpl, on ja .
• Jos graafin kaikkien kärkien aste on , voi sivujen määrän laskea kaavalla , sillä "jokainen kärki on yhteinen :lle sivulle ja yhden sivun määräämiseen tarvitaan kaksi kärkeä".

11.2Algoritmeja (ei-negatiivisesti) painotetuille graafeille

Seuraavat klassiset graafialgoritmit ovat ns. ahneita algoritmeja:

• Primin algoritmi minimaalisen virittäjäpuun hakemiseen (eli priority first search): ensin lisätään jonoon kaikki naapureihin johtavat sivut joiden paino on pienempi kuin jo jonossa ehkä olevan, samaan solmuun johtavan sivun, sitten valitaan jonosta pienimmän painoinen sivu ja toistetaan kunnes kaikki solmut on käyty läpi.
• Dijkstran minimipolkualgoritmi: kuin Primin algoritmi, mutta lähdetään tietystä solmusta, lisätään jonoon aina painojen summa (eikä pelkästään sivun omaa painoa) ja lopetetaan kun tultu kohdesolmuun.
• Kruskalin algoritmi minimaalisen viritäjäpuun hakemiseen: valitaan yksitellen pienin jäljellä oleva sivu, joka ei muodosta kierrosta jo valittujen kanssa. (Kierrostarkistus voidaan tehdä merkitsemällä jokaiseen sivuun mihin tulosmetsän puuhun se kuuluu ja yhdistämällä vain eri alipuita keskenään. Alipuiden yhdistämisessä toisen puun tunnus aina hävitetään, joten lopuksi on jäljellä vain yksi puu.)

11.3Kaksijakoinen graafi (bipartite graph)

• Graafi on kaksijakoinen joss se voidaan jakaa kahteen joukkoon siten, että sivuja on vain niihin kuuluvien kärkien välillä (ei siis saa olla esim. kierroksia)
• Kärjet piirretään yleensä kahteen riviin niin, että joukon 1 () kärjet ovat ylhäällä ja joukon 2 alhaalla.
• Tyypillinen käyttöesimerkki on avioliitto-/opiskelupaikkaongelma, jossa henkilöt luettelevat heille kelpaavat puolisot/koulut :stä (ts. preferenssit esitetään sivuina) ja sitten yritetään löytää kaikille sopiva järjestely.
• Kaksijakoisen graafin sovitus on joukko sivuja, joilla ei ole yhteisiä kärkiä
• Sovitus on maksimaalinen, jos ei ole olemassa enemmän sivuja sisältäviä sovituksia.
• :n jonkin osajoukon ulottuvuus on kaikkien siihen sivuilla kytkettyjen -kärkien joukko.
• Osajoukon vaje on kokonaisluku . Huom: voi olla negatiivinen!
• Koko graafin vaje on kaikkien :n osajoukkojen vajeiden maksimi. Koska niihin kuuluu myös tyhjä joukko ja , on .

• Graafin täydellinen sovitus on sellainen, jossa jokaisesta :n kärjestä lähtee sivu ja sellainen on olemassa joss kaikille (eli ). Täydellisen sovituksen etsimiseen on olemassa useita ns. polunlaajennusalgoritmeja. Tässä eräs:

  Käydään läpi kaikki kärjet :

  Jos :lle ei ole jo valittu esittäjäsivua:

  Käydään läpi :ään yhdistetyt kärjet jotka eivät jo kuulu sovitukseen:

  Jos löytyy :hyn yhdistetty kärki joka ei jo kuulu sovitukseen:

  Lisätään sivu sovitukseen ja palataan uloimpaan silmukkaan

• Jos -kärjet korvataan joukoilla ja -kärjet niistä yhteen tai useampaan kuuluvilla alkioilla (ts. ei käsitellä enää varsinaista graafia vaan merkitään “preferenssejä“ esim. ), puhutaan täydellisen sovituksen sijaan joukkojen esittäjäsysteemistä.
• Joskus sivuihin yhdistetään painot, jolloin yleinen ongelma on etsiä joko painojen summan maksimoiva (tai minimoiva) sovitus. Siihen sopii mm. unkarilainen algoritmi, joka iteroi graafin matriisiesitystä (sivujen painot matriisialkioina).

12Sekalaisia laskutekniikoita

12.1Induktiotodistus

1. Julistetaan induktiohypoteesi (esim. )
2. Induktion perusta: osoitetaan, että (tai tai joku muu helppo tapaus) on tosi (esim. ).

3. Induktioaskel: osoitetaan, että jos induktiohypoteesi (tai -oletus) on tosi, myös on tosi sijoittamalla :n toinen puoli :n sisään ja pyörittelemällä algebrallisesti. Esim.

   

12.2Neliöksi täydentäminen

Esim. toisen asteen yhtälön ratkaisukaavan johtaminen:

12.3Osamurtokehitelmä

Jokaiselle rationaalifunktiolle ( on alempaa astetta kuin ) voi muodostaa osamurtokehitelmän missä termit ovat muotoa tai ja ja (jos sallitaan , jälkimmäistä muotoa ei tarvita). Kehitelmästä on hyötyä varsinkin integroinnissa.

Aluksi faktoroidaan nimittäjä ensimmäisen tai toisen asteen termeihin kaavalla (tai sen suoraviivaisella laajennuksella korkeamman asteen polynomeille). Hajotelman termit määräytyvät saatujen tekijöiden mukaan – tapauksia on kolme:

1. reaalinen (), ei-toistuva juurilineaarinen nimittäjä, vakioarvoinen osoittaja:

   

2. imaginäärinen juuri toisen asteen nimittäjä, lineaarinen osoittaja:

   

3. -kertainen juuri termiä, joissa nimittäjän aste laskee:

   

   

Hajotelman termien osoittajiin tulevat vakiot () eli residyt (eng. residue) voidaan lasskea monella tavalla. Seuraavat kolme tapaa on esitetty kahden eri suuren, reaalisen juuren avulla (ts. ), mutta ne toimivat myös korkeamman asteen tapauksissa (ts. ). Heavisiden menetelmää lukuunottamatta ne toimivat myös moninkertaisille ja epälineaarisille tapauksille.

12.3.1Tapa 1: :n valitseminen strategisesti

Lavennetaan osamurrot samannimisiksi alkuperäisen kanssa, eliminoidaan nimittäjät ja ratkaistaan osoittajista muodostuvan polynomin tuntemattomat () valitsemalla aina siten, että se hävittää kerrallaan yhden muuttujista:

Valitaan strategisesti :

Sama temppu B:lle: :

Eli:

12.3.2Tapa 2: yhtälöryhmä eri asteisista termeistä

Etsitään murtofunktiota vastaava yhtälö kuten tavassa 1 ja ryhmitellään se :n polynomiksi (tässä esimerkin vuoksi toisen asteen, vaikka ensimmäisen asteenkin riittäisi):

Sitten tehdään :n eri asteisista termeistä (vakiot, :t, :t yms) lineaarinen yhtälöryhmä:

Ratkaistaan saatu lineaarinen yhtälöryhmä (esimerkkinä näytetty turha on poistettu):

12.3.3Tapa 3: Heavisiden peittomenetelmä

Heavisiden menetelmä on helppo, mutta ei toimi moninkertaisten () eikä epälineaaristen () termien kanssa. Murtofunktiota ei tarvitse vääntää yhtälöksi kuten edellisissä tavoissa:

Pyyhitään vain aina yksi tekijä pois nimittäjästä ja sijoitetaan sen nollaamiseen tarvittava vakio jäljelle jääneeseen kaavaan :n tilalle. Poistettua tekijää vastaava residy saadaan suoraan:

12.4Logaritmi

• Määritelmä: eli "mihin potenssiin pitää korottaa, että saadaan "
• Ehdot: kantaluvulle ja numerukselle
• 
• 
• 
• . Esim. .
• 
• 
• (eli kantaluvun vaihto)

12.5Raja-arvo

• Summa, erotus, tulo ja osamäärä ovat triviaaleja:

  

• 
• :n raja-arvon saa jakamalla molemmat polynomit nimittäjän korkeimman asteen muuttujalla. Esim:
• ääretöntä lähestyttäessä myös neliöjuuresta voi usein päästä eroon vastaavalla jakolaskulla:
• polynomin raja-arvo(n merkki: ) äärettömyydessä määräytyy vain ja ainoastaan korkeimman asteen tekijän mukaan, koska esim.

• jotain ei-määrättyä arvoa lähestyvän raja-arvon saa yleensä joko faktoroimalla polynomeja juuriensa avulla tai viimeistäänkin muuttamalla laskun raja-arvoksi äärettömyydessä:

  tai

  .

• eli "eksponentti voittaa potenssiin korotuksen"
• , eli "potenssiin korotus voittaa logaritmin"
• l'Hospitalin 1. sääntö: . Huom: toimii vain -muotoisille lauseille!
• l'Hospitalin 2. sääntö: . Huom: toimii vain -muotoisille lauseille ja on käytännöllinen vain -muotoisille! Tyyppien -muotoiset voi kuitenkin muuttaa muotoon tai ottamalla logartimin.

12.6Trigonometristen funktioiden ominaisuuksia

13Merkintätapoja

13.1Tavalliset lukujärjestelmät

• = kokonaisluvut =
• = positiiviset kokonaisluvut =
• = luonnolliset luvut =
• = rationaaliluvut
• = reaaliluvut
• = kompleksiluvut =

13.2Kreikkalaiset kirjaimet

(Roomalaisten kirjainten kanssa yhteiset merkit harmaalla, etsimisen helpottamiseksi.)

		alfa					nyy
		beeta					ksii
		gamma					omikron
		delta					pii
		epsilon					rhoo
		zeeta					sigma
		eeta					tau
		theeta					ypsilon
		ioota					fii
		kappa					khii
		lambda					psii
		myy					omega

Hakemisto