Széchenyi István Egyetem. Számítástudomány. 1. előadás. Numerikus és szimbolikus számítások, számítási pontosság, megoldhatóság. Dr

Számítástudomány

Széchenyi István Egyetem

1. előadás Numerikus és szimbolikus számítások, számítási pontosság, megoldhatóság

Dr. Kallós Gábor

2014–2015 11



Tartalom Függvény alatti terület meghatározása A gépi integrálás problémája

Mátrix inverzének meghatározása Gépi epszilon Egy numerikus rendszer határai (Matlab) Legkisebb és legnagyobb ábrázolható szám, Inf, NaN

Pi közelítések Nagypontosságú aritmetika

Egyenletrendszerek megoldása Az egyszerűsítés problémája

Maple – áttekintés Matlab Symbolic Math Toolbox – áttekintés Szimbolikus környezetben használható fontosabb parancsok Feladatok Irodalom 2



Függvény alatti terület meghatározása Feladat: Határozzuk meg az y = x2 függvény alatti területet a [0, 1] intervallumon! 1. megoldási lehetőség: Közelítő számítás Nézzük meg Excelben, Matlabban!

Mi kell a közelítő megoldáshoz Excelben? x adatsor, y adatsor Megfelelően sűrű lépésközzel

Közelítés a területre, ami könnyen számolható, pl.: trapézmódszer (numerikus integrálás) Ellenőrzés (becsléssel): jó eredményt kaptunk-e? Mennyire pontos az eredmény?

Kapcsolódóan: ábrakészítés, „hangolások”, feliratok, esetleg jelölők stb.

Mi kell a közelítő megoldáshoz Matlabban? (Matlab használat számológép szinten, ablakok, konstansok, változók, környezeti parancsok, aktuális könyvtár, sorozatképzés, vektorok és mátrixok, egyszerű grafika – fv.rajzolás) Függvény megadása Alkalmas beépített parancs, ami megoldja a numerikus integrálási feladatot Lehet a Súgóban nézelődni, keresgélni

Nekünk most jó: quad Paraméterek szerepe (mi a jó számítási pontosság?)

Az Excel és Matlab programoknál (numerikusan) 15-16 jegy pontosságot várhatunk 3



Függvény alatti terület meghatározása Feladat: y = x2 függvény alatti terület (folyt.) 2. megoldási lehetőség: Pontos számítás Nézzük meg papír-ceruza módszerrel, ill. alkalmas programmal!

Papír-ceruza módszer Tudunk integrálni :-) Megj: legalábbis egyszerűbb esetekben (!)

Így nyilván pontos megoldást kapunk

Számítógépes megoldás Probléma: az „x” változót kell kezelnünk, mint megfelelő objektumot! Persze aritmetika is kell ilyen objektumokkal, pl. 2*x, x^2 stb.

A Matlab szimbolikus modulja tudja ezt, és a Maple is

Mi kell a pontos megoldáshoz Matlabban? Szimbolikus objektumok definiálása (aritmetika) Alkalmas beépített parancs, ami megoldja a szimbolikus integrálási feladatot (int) Paraméterek

Mi kell a pontos megoldáshoz Maple-ben? (Alapvető Maple használat) A többit már tudjuk

(Sok más jó eszközt is találhatunk, pl. Wolfram Alpha) 4



A gépi integrálás problémája Természetes kérdések: Milyen bonyolult feladatokat tud a gép megoldani? Milyen algoritmussal tud a gép integrálni?

Példa: vegyünk egy Matek 2. vizsgafeladatot! Oldassuk meg a Maple megfelelő tutorjával!

5



A gépi integrálás problémája Természetes kérdések (folyt): Mi van akkor, ha a gép nem talál megoldást a szimbolikus integrálási feladatra?

Példa: egy Infó 2. vizsgafeladat (két fv. közötti terület, numerikus számolásra) Szimbolikusan nem tudjuk kiszámolni…

6



Mátrix inverzének meghatározása Meghatározások, tulajdonságok Inverz mátrix (csak négyzetes mátrixokra): az a mátrix, amelyet az eredetivel összeszorozva egységmátrixot kapunk Jelölés: A–1 Érvényes: A ⋅ A–1 = A–1 ⋅ A = E

Egységmátrix: a főátlóban csupa 1-es, más helyeken 0-ák Jelölés: E vagy I Az egységmátrixra teljesül: A ⋅ E = E ⋅ A = A; E ⋅ E=E

Inverz akkor létezik, ha a determináns nem 0, illetve a mátrix rangja megegyezik a sorainak (oszlopainak) számával

Papír-ceruza módszer Az adjungált mátrixot osztjuk a determinánssal Az egységmátrixból indulva megengedett műveletekkel eljutunk az eredeti mátrixig Így pontos megoldást kapunk (ellenőrzés!)

A Maple tutor be tudja mutatni 7



Mátrix inverzének meghatározása Számítógépes megoldás – numerikusan Tudja az Excel és a Matlab (persze a Maple is) Megvalósítás Excelben Adatok bevitele (bemásolása, betöltése) Determináns ellenőrzése Inverz területének kijelölése Inverz képletének megadása (blokkművelettel!) Célszerűen: ellenőrzés Extra lehetőség: valódi tört formátumú megjelenítés (pontos aritmetika, de csak 3 jegyig)

Megvalósítás Matlabban Adatok bevitele (bemásolása, betöltése) Rang vagy determináns ellenőrzése Inverz számolása a megfelelő paranccsal (inv) Lebegőpontos eredményt kapunk, de kérhető valódi törtes megjelenítés (rats vagy format rat; 5-6 jegyig pontos aritmetika)

8



Mátrix inverzének meghatározása Számítógépes megoldás – pontos aritmetikával Excel és Matlab – láttuk Maple A parancs neve és a mátrix megadása itt más, de a lényeg uaz Sok finomabb opció beállítható

Kötelező: lineáris algebra csomag használata (Plusz kényelmi lehetőség: a mátrix palettáról is beszúrható)

Számítógépes megoldás – szimbolikusan Matlab és Maple A megszokott módon 9



Mátrix inverzének meghatározása, gépi epszilon Egy „kellemetlen” mátrix: A = [1 2 3; 4 5 6; 7 8 9] Determináns (Excel): nagyon kicsi érték Ez most tényleg nem nulla, vagy valójában 0 (csak nem pontosan annak látszik)?

Másik hasonló példa: a B = [1 2 3; 4 5 6; 7 8 8] mátrixot és numerikusan számított inverzét szorozzuk össze (Excel, Matlab) 1-hez és 0-hoz nagyon közeli értékeket is látunk

Tudnunk kell értelmezni ezeket az eredményeket! A második példánál ez nyilvánvaló Az elsőnél: a rang árulja el, hogy valóban 0-e a determináns (összefüggő-e a rendszer) Mátrix rangja: lineárisan független oszlopvektorok (sorvektorok) maximális száma

Feladat: igazoljuk, hogy valóban csak 2 fgtlen sor/oszlopvektora van a rendszernek! (Pl. Állítsuk elő az első sor/oszlop valahányszorosának kivonásával a 2. és 3. sorból/oszlopból ugyanazt a …) 10



Gépi epszilon Numerikus rendszerekben létezik egy olyan legkisebb érték, amelyet 1-hez hozzáadva még éppen nem 1 lesz az eredmény, ez a gépi epszilon A rendszer beépítve is ismerheti, de algoritmikusan is meghatározható (Szemléltetés Matlabban hex kijelzéssel is)

Feladatok Hogyan érdemes elvégezni géppel a következő összeadást: eps/3 + 1 + eps/2 + 2 + eps/2 + 2 + eps? *Határozzuk meg az eps_2, eps_3 számot (2-höz, 3-hoz hozzáadva …)

11



Egy numerikus rendszer határai (Matlab) A probléma hagyományos programozási környezetben is előjön Egész (előjeles, előjel nélküli) és valós típusok, szabványok (1, 2, 4 stb. bájton, tudjuk)

A Matlabban használatos egész és lebegőpontos típusok (alapértelmezés: double):

Speciális értékek: Inf és NaN Feladatok Hogyan értelmezhetők a következők (mi lenne a jó eredmény): Inf + Inf, Inf – Inf, Inf/Inf, NaN + Inf stb. Állítsunk elő a realmax('double') értéknél egy picit nagyobb számot!

12



A pi közelítése Feladat: határozzuk meg a π számot sok (pl. 500 vagy 1000 vagy …) tizedesre! Papír-ceruza módszerek Archimédesz módszere (ókor, trigonometria) Iteratív közelítések (középkor és újkor, speciális sorok) Érdemes megpróbálni párat (bár inkább géppel…)

*Pi-versek, novellák :-) (Szász Pál, 1952) Nem a régi s durva közelítés, 3 1 4 1 5 9 Mi szótól szóig így kijön, 2 6 5 3 5 Betűiket számlálva. 8 9 Ludolph eredménye már, 7 9 3 Ha itt végezzük húsz jegyen. 2 3 8 4 6 De rendre kijő még tíz pontosan, 2 6 4 3 3 8 Azt is bízvást ígérhetem. 3 2 7 9

*Buffon tűdobási problémája Legyen x = l/d. Annak valószínűsége, hogy a tű vonalra esik: P(x) = 2x/π (számolható) (Ez csak „rövid” tű esetén igaz) Kísérlet, 500 dobás, x = 1/3, 107 metszéssel. Ebből: π-köz = 3,116

13



A pi közelítése Feladat: π meghatározás (folyt.) Számítógépes megoldás A Matlab és a Maple számára ez nem probléma (Matlabban a nagypontosságú aritmetikához szükséges a vpa parancs)

14



A pi közelítése Természetes kérdések 1.: Hogyan dolgozik a gép?

A π közelítésére alkalmas képletek

2

π

=

1 1 1 1 + 2 2 2 2

1 1 1 1 1 + + L 2 2 2 2 2

Viete-formula: π 2 ⋅ 2 ⋅ 4 ⋅ 4 ⋅ 6 ⋅ 6 ⋅ 8 ⋅ 8 ⋅K = Wallis módszere (1650 körül): 2 1⋅ 3 ⋅ 3 ⋅ 5 ⋅ 5 ⋅ 7 ⋅ 7 ⋅ 9 ⋅K Gregory-Leibniz módszer (1670 körül), Indiában már 1500 körül is ismert volt: π 1 1 1 1 Egyszerű és hatékony módszer, jól algoritmizálható = 1− + − + −L 4 3 5 7 9 Maple: a sorozat első 1000 tagjának összegzésével a π/4 közelítésére 0,78514… adódik a pontos 0,78539… érték helyett π 1  1  Machin módszere (1706-tól): = 4 arctan  − arctan  5  239  Lényegében még ma is használatos módszer (változatai) 4 Maple: ezzel a képlettel néhány tizedmp alatt ki tudjuk számolni a π első 10000 jegyét

Speciálisan számítógépre optimalizált módszerek J. Borwein és P. Borwein (1985-től) Legyen a0 = 6 − 4 2 és y0 = 2 − 1 Iteráljuk a következő kifejezéseket: 1 − (1 − yk4 )1/ 4 y = a k +1 = a k (1 + y k +1 ) 4 − 2 2 k +3 y k +1 (1 + y k +1 + y k2+1 ) k +1 A sorozat határértéke 1/π 4 1/ 4 1 + (1 − yk ) Negyedrendűen konvergens ak-ra (minden iteráció négyszeresére növeli a pontos jegyek számát)

D. Bailey, P. Borwein és S. Plouffe (1996) Kiszámítható a π tetszőleges számjegye (16-os szr.-ben) az előzőek ismerete nélkül ∞ 1  4 2 1 1  − − − π =∑ n  8n + 4 8n + 5 8n + 6  n=0 16  8n + 1

15



A pi közelítése A π jegyeinek a meghatározása (történeti áttekintés) Számítógép előtti időszak Egyiptom (Rhind-papirusz, i.e. 2000~)

2^8/3^4 = 3,1605...

Archimédesz (i.e. 250~)

3,1418 (átlagszámítással, 3 jegy pontos)

Csu Csung Csi (Kína, 480~)

3,14159292 (6 jegy pontos)

Al-Kashi (Szamarkand, 1430)

3,14159265358979 (14 jegy)

Viete (1593)

3,1415926536 (9 jegy)

Ludolph van Ceulen (1610)

35 jegy!

Sharp (1699)

71

Machin (1706)

100

von Vega (1794)

140 (136 helyes)

Strassnitzky, Dase (1844)

200 (fejben!!!)

Clausen (1847)

248

Rutherford (1853)

440

Shanks (1874)

707 (527 helyes)

Ferguson (1946)

620

16



A pi közelítése A π jegyeinek a meghatározása (történeti áttekintés, folyt.) Miért jó ez? Verseny, kihívás, rekordok Szuperszámítógépek tesztelése, korrekt működés ellenőrzése Szabályosságok keresése Gépi számolással Ferguson, asztali számológép (1947 jan.)

710

Reitwiesner és társai, ENIAC (1949)

2037

Genuys, IBM 704 (1958)

10 000

Shanks, Wrench, IBM 7090 (1961)

100 265

Goilloud, Bouyer, CDC 7600 (1973)

1 001 250

Kanada és Tamura, HITACHI S-810/20 (1986)

67 108 839

Chudnovsky testvérek, Cray-2, IBM 3090-VF (1989)

1 011 196 691

Kanada és Takahashi, HITACHI SR2201 (1997)

51 539 600 000

Kanada, HITACHI SR8000 (2002 szept.)

1 241 100 000 000

Takahashi, TK2 szupergép (2009 ápr.)

2 576 980 377 524

Yee és Kondo (2011 okt.)

10 000 000 000 050 17



A pi közelítése Természetes kérdések 2.: Hogyan lehet megvalósítani általában a nagypontosságú aritmetikát?

Amit át kell gondolni Adatreprezentáció (egészek, racionális törtek, polinomok, hatványsorok) Hatékony tárolás

Hatékony algoritmusok (összeadás, szorzás, osztás) Néhány további kérdés: egyszerűsítések (!)

Mi kell a nagypontosságú egészek gépi reprezentációjához? Egy lista, amely hagyományos egészekből áll (d0, d1, …, dl–1) és egy előjel (s) Egy rögzített – célszerűen nagy – β alapszám Leggyakrabban 2 vagy 10 hatvány úgy, hogy β – 1 még tárolható legyen hagyományos egészként (pl. 231 vagy 109, ha 32 bitünk van)

A lista lehet statikus (szekvenciális) vagy dinamikus (láncolt)

Láncolt dinamikus lista

l −1

d = s∑ di β i

Eltároljuk a di-ket, egy listaelem a következőre mutat Pl. N = 1234567890, β = 103, N → 890 | → 567 | → 234 | → 1 | x A fordított sorrend megfelel a műveletekhez szükséges természetes elérésnek

i =0

Fix méretű helyet foglalunk le, a nem használt pozíciók 0-át tartalmaznak Pl. N → 890 | 567 | 234 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

Előnyök és hátrányok mindkét esetben… Dinamikus tömb: mindkét módszer előnyeit ötvözi (Maple) 18



Egyenletrendszer megoldása Egy nemlineáris egyenletrendszer megoldása és tanulságai Feladat: Oldjuk meg az alábbi harmadfokú, nemlineáris egyenletrendszert! Lépések (Maple) Solve parancs RootOf-os eredményt kapunk – elsőre nehezen értelmezhető

Numerikusan: fsolve Látjuk, hogy kaptunk valós megoldást (mindig csak egyet)

Ugyanígy több más mo. is előállítható (6 db) 19



Egyenletrendszer megoldása Egy nemlineáris egyenletrendszer megoldása és tanulságai (folyt.) Lépések (Maple, folyt.) Kiszedjük a RootOf-ból a gyököket A fenti szimbolikus mo-ból: a 6 gyök valóban előáll Numerikusan látszik, hogy a komplex rész valójában 0 Mindez direkt trigonometrikus úton is igazolható (?) *Mutassuk meg!

20



Az egyszerűsítés problémája Egyszerűsítések, különböző felírások Szimbolikus kifejezéseknél (pl. polinom) nem feltétlenül nyilvánvaló, hogy melyik alak tekinthető a legegyszerűbbnek A feladat jellegétől is függ, hogy milyen felírásra van szükségünk (pl. Heck 7.)

A probléma általánosan sem egyszerű

Kiterjesztett (összeg) vagy faktorizált (szorzattá alakított) felírás? (Helyigény, ill. valamelyik x hatvány együtthatójára vagyunk kíváncsiak) x1000 – 1 vagy (x – 1)(x999 + x998 + … + x2 + x + 1) (x + 1)1000 vagy (x1000 + 1000x999 + … + 1000x + 1)

Többváltozós eset (Újabb kérdés: melyik a „fő” ismeretlen?) p(x, y) = 12x2y – 4xy + 9x – 3 p(x, y) = (3x – 1)(4xy + 3) p(x, y) = (12y)x2 – (4y + 9)x – 3

Általános transzformációs és egyszerűsítő függvények Az expand parancs segítségével összeg formájú felírást kérhetünk, a factor paranccsal pedig szorzattá alakítottat Egyszerűsítő függvények: simplify (simple) 21



Az egyszerűsítés problémája Egyszerűsítések, különböző felírások (folyt.) Zéró ekvivalencia probléma Az általános egyszerűsítési probléma speciális esete (jól definiált, nincs reprezentációs kérdés) „Szép” objektumokra (polinomokra, racionális törtfüggvényekre, hatványsorokra stb.) viszonylag egyszerű A függvényosztály bővítésével (trigonometrikus, exponenciális függvények) azonban ez a feladat nagyon nem triviálisnak tűnik!!! Pl. log(tan(x/2 + π/4) – sinh–1(tan x) = 0?

22



Az egyszerűsítés problémája Néhány automatikus egyszerűsítés/kiértékelés a Maple rendszerben Ha egyértelmű a szabály, akkor egyszerűbb esetekben a várt eredményt kapjuk De vigyázzunk, néha az egyszerűnek tűnő eset is lehet bonyolultabb!

23



Az egyszerűsítés problémája Hogyan tudunk mi egyszerűsíteni/egyszerűsíttetni?

24



Az expand parancs alkalmazásai Trigonometrikus azonosságok (addíciós szabályok), amelyeket a rendszer ismer (válogatás)

25



Az expand parancs alkalmazásai Exponenciális-logaritmikus és gyökös-hatványos azonosságok, amelyeket a rendszer ismer (válogatás) Tanulság: vigyázni kell!

26



Az egyszerűsítés problémája Feladat: Kapjuk vissza a tan(3⋅x) kifejtett alakjából az eredetit!

*Feladatok: Heck 370, 371

27



Egyenletek megoldhatósága Másodfokú Megoldóképlet, már az ókorban ismert volt (Mezopotámia, Kr. e. 2000 k.)

Harmadfokú Fibonacci (1230 k.): egy harmadfokú egyenletet általában nem lehet a négy alapművelettel, hatványozással és négyzetgyökvonással megoldani 1400-as évek vége (itáliai matematikusok): a harmadfokú egyenletek visszavezethetők x3 + px + q típusúakra Scipione del Ferro, Tartaglia, Cardano (1500-as évek eleje): megoldóképlet Először sikerült túlszárnyalni az ókori matematika eredményeit! (Komplex számok kezelése csak később)

Negyedfokú Ferrari: megoldóképlet

2

3

2

q q  q  p  q  p u + v = 3 − + −  +   + 3 − − −  +   2 2  2  3   2  3 

3

Harmadfokúra való visszavezetés

Ötöd- és magasabb fokú Lagrange (1770 k.): indoklás, hogy általában miért nem használhatók az alacsonyabbfokú esetek módszerei Ruffini, Abel, Galois (1820-30 k.): az általános ötödfokú egyenlet algebrai módszerekkel nem oldható meg Általában csak a közelítő módszerek maradnak

Feladat: ötödfokú egyenletek megoldhatóságának vizsgálata 28



Egyenletek megoldhatósága Ötöd- és magasabb fokú (folyt.) Feladat: ötödfokú egyenletek megoldhatóságának vizsgálata

29



Maple – áttekintés A Maple felületének fontos jellemzője: (mostanra már) nagyon igényes munkalapok (dokumentumok) kialakítását teszi lehetővé Dokumentum mód (alapértelmezés) Elemei a dokumentum blokkok (View/Markers), a parancsok részletei rejtettek Egy dokumentum blokk kinyitható/becsukható

Worksheet (munkalap) mód (bekapcsolás: File/New) Maple input prompt és csoport használható

„Vegyes” használat is lehetséges Munkalap módban is elrejthetők a számítás részletei (Format/Create Docum. Block) Dokumentum módban is lehet Maple input promptot beszúrni (Insert/Execution Group)

2-D Math bevitel (alapértelmezés) Törtek, kitevők, alsó indexek, gyökös kifejezések, integrálok stb. írhatók igényes módon

1-D Math bevitel (hagyományos Maple környezet) Kulcsszavakból, zárójelezéssel kell összeállítani a kifejezéseket

Intelligens kiegészítés a beíráskor (Esc) Inline (sorközi) kiértékelés: CTRL + =; „sima” kiértékelés: ENTER

30



Maple – áttekintés Helyzetérzékeny menük hívhatók az objektumokon (nem kell paranccsal megadni a funkciót) Pl.: egyenlet megoldására, függvény ábrázolására A lehetőségek – természetesen – függenek az adott objektumtól

Parancs befejezés (intelligens beírás, képletek): CTRL + space Paletták, beszúrható objektumokkal Állandó kernel + a parancsok egy része: külső könyvtárakból Nagyon jó súgó

31



Maple – áttekintés Komoly támogatás a matematikai problémamegoldáshoz „Clickable math”

Tools menü Tutorok Taskok A munkalapokba beilleszthetők

32



Maple – áttekintés A súgó („kézikönyv”) a program nélkül, online módon is elérhető (maplesoft oldal)

33



Matlab Symbolic Math Toolbox – áttekintés (Matlab – numerikus számítási környezet, programrdsz.) A S. M. Toolbox szimbolikus számítások elvégzését teszi lehetővé A Matlab alapból numerikusan számol (mátrixos reprezentáció), a double float adattípus pontosságáig

Szimbolikus változók definiálása syms vált.név vált = sym('vált') Konstansnál csak ez alkalmazható, az aposztrófok elhagyhatók 15 jegyig Feladat: Nézzük meg, hogy mi történik, ha ennél jóval nagyobb konstans számra is elhagyjuk az aposztrófokat!

Változó törlése: clear vált.név Matlab felület Ablakok (ki- és bekapcs.) Aktuális könyvtár beállítása History ablak

Karakterméret (Desktop/Toolbars) Compact kijelzés A felület karakteres, a (régi) Maple 1D-hez hasonló, „pretty” kijelzés is kérhető

Súgó rendszer, demók, … 34



Szimbolikus környezetben használható fontosabb parancsok Felbontók Expand: összeg formájú felírás Factor: szorzat formájú felírás Polinom együtthatói (coeff, lcoeff, tcoeff, collect) Polinom foka (degree)

Kiértékelők Eval: általános kiértékelő (egyszerűsít is) Evalf: lebegőpontos kiértékelő

Egyszerűsítők Simplify, simple: általános egyszerűsítő Körülmények/feltételek beállítása, megadása (assume)

Normal: normalizáló Combine: kifejezések egyesítése

Helyettesítők Subs: általános helyettesítő Subsop: megadott operandusok helyettesítésére

Megoldók Solve: általános megoldó Fsolve: lebegőpontos megoldó

Egyéb fontosabb parancsok Limit: határérték számítás Diff, Int: differenciálás, integrálás 35



Ajánlott irodalom Berggren, Borwein: Pi – a source book, Springer, New York, 2004 Geddes, Czapor, Labahn: Algorithms for Computer Algebra (6th pr./ed.), Kluwer Acad. Press, Boston, 1999 Joachim Gathen, Jürgen Gerhard: Modern Computer Algebra (3rd ed.), Cambridge Univ. Press, 2013 Edward Kofler: Fejezetek a matematika történetéből, Gondolat, Budapest, 1965 Sain Márton: Matematika-történeti ábécé, Tankönyvkiadó, Budapest, 1974 Szörényi Miklós, Kallós Gábor: Mérnöki számítások, jegyzet és órai segédanyagok (Excel és Matlab rész), SZE, 2013–2014 Molnárka Győző és társai: A MapleV és alkalmazásai, Springer, Budapest, 1996 Andre Heck: Bevezetés a Maple használatába, JGYF kiadó, Szeged, 1999 Maple User Manual, Maplesoft, 2013 Matlab Symbolic Math Toolbox User’s Guide, MathWorks, 2013 36

Széchenyi István Egyetem. Számítástudomány. 1. előadás. Numerikus és szimbolikus számítások, számítási pontosság, megoldhatóság. Dr

Recommend Documents