Ha hallgattál már zenét vagy néztél filmet online, esetleg próbáltál kiszámolni egy hiteltörlesztést, akkor már találkoztál a végtelen sorokkal – csak épp nem biztos, hogy tudtál róla. Minden digitális hang és kép szinuszjelek végtelen összegeként írható le. A kamatos kamat képlete mögött is egy végtelen geometriai sor rejlik. És bizonyos irracionális számok értékének (pl. π, e) közelítése is lehetséges végtelen sorokkal. E kiragadott példákon felül még számos más alkalmazási területe van a végtelen numerikus soroknak.
A számítógép viszont nem tud „végtelenig” számolni, ezért a végtelent kezelhetővé kell tenni. A következőkben megnézzük, hogyan lehet egy végtelen numerikus sor összegét programban kiszámítani úgy, hogy „elég közel” legyünk az egzakt értékhez.
Ahhoz, hogy egy olyan programot tudjunk írni, ami a sorösszeget jól közelíti, néhány fogalmat és tételt ismerni kell. (Ha valaki felsőbb szintű matematikát tanult, annak mindez nem lesz újdonság).
A sorozatokkal és sorokkal kapcsolatban talán a legfontosabb fogalom a konvergencia. A precíz matematikai definíciónál kicsit lazábban fogalmazva egy végtelen sorozat konvergens, ha az értékei egy bizonyos számértéket (a határértéket) egyre jobban, azaz tetszőlegesen megadott pontossággal megközelít. E korlátnak általában a görög ε (epsilon) a jele. Tehát van olyan index érték, amelynél nagyobb indexű sorozatelemek eltérése az adott ε pontosságnál nem nagyobb. A nem konvergens sorozatokat divergens sorozatoknak nevezik.
Egy végtelen sor akkor konvergens, ha a tagok részösszegeinek sorozata konvergens.
A végtelen sorokat a matematikában a tagok előjele alapján szokták csoportosítani, mert az egyes csoportokra eltérő (lazább vagy szigorúbb) feltételek határozhatók meg a konvergenciára vonatkozóan. Ezekből az egyik a váltakozó előjelű (alternáló) sorok csoportja. Ezek olyan számsorok, amelyekben az egymást követő tagok előjele ellentétes.
Miért érdekesek az alternáló sorok? Azért, mert ha teljesítik még azt a követelményt is, hogy a sor tagjainak abszolút értéke monoton csökken, és a tagok sorozata nullához tart, akkor a sor biztos, hogy konvergens. Az ilyen sorozatokat Leibniz-típusú soroknak (vagy rövidebben Leibniz soroknak) nevezik a konvergencia kritériumot elsőként megfogalmazó Gottfried Wilhelm Leibniz matematikusról. Ilyen sorokra mutat példát a következő ábra. Ezeknél a sorösszeg egzakt formában kifejezhető.
Az alábbi ábrán olyan sorok láthatók, amelyek bár konvergensek és az összeg egzakt formában kifejezhető, de nem Leibniz sorok.
Mindezeket tudva, most már nekiállhatunk a sorösszegszámítás programmal történő megvalósításához. Ez két lépésből fog állni.
Először megpróbáljuk az adott sort Leibniz sorként kezelni. Ez azt jelenti, hogy vesszük a tagok sorozatát és megnézzük egyrészt, hogy a tagok váltakozó előjelűek-e, másrészt, hogy monoton csökkenők-e. Ezeket könnyen, két szomszédos tag vizsgálatával eldönthetjük. Ha ezek teljesülnek, akkor azt kell még megállapítani, hogy a tagok sorozata a nullához tart. Ez sem nehéz, hiszen meg tudjuk mondani, hogy mikor tartunk annál a tagnál, amely már a meghatározott epsilon konvergencia-hibahatáron belül van. Azonban az esetleges kerekítésből adódó hibák kiküszöbölésére az epsilon korláton belülre kerülést adott számú tagra fogjuk vizsgálni, és csak akkor adjuk vissza a sorösszeget, ha minden vizsgált tag már biztosan benne van a toleranciasávban.
A második lépésre akkor kerül sor, ha menet közben kiderül, hogy nem Leibniz-típusú a sor. Ebben az esetben a sorösszegzést egy megadható számú tagra fogjuk végezni, és ezt tekintjük a sorösszegnek.
Miért van értelme e két lépésnek? Azért, mert ha Leibniz sorról van szó, akkor tudjuk, hogy biztosan konvergens. Ezért az epsilon értékétől függően tetszőleges pontossággal ki tudjuk számolni a sorösszeget. A számítási igény, vagyis az, hogy hány tagot szükséges az adott pontossághoz figyelembe venni, a konvergencia gyorsaságától fog függni. Gyorsnál kevés tagot, lassúnál többet kell összegezni. Ha túl lassú lenne a konvergencia, akkor erre vonatkozóan is be állíthatunk egy korlátot, amit elérve ezt jelezzük.
Ha viszont kiderül, hogy nem Leibniz sorral van dolgunk, akkor nem lehetünk biztosak még abban sem, hogy egyáltalán konvergens-e a sor. Ezért nem tudunk más tenni, minthogy az igényeinknek megfelelő, előre megadott számú tagra végezzük el az összegzést. Ilyenkor azonban még ha konvergens is a sor, a tényleges és a számolt sorösszeg eltérését nem tudjuk pontosan megmondani. De minél több tagra számolunk, annál jobban közelítünk.
Ezen elvek alapján definiálunk egy SeriesSumCalculator osztályt az alább látható módon. Ebben a series_sum() nyilvános metódus egy paraméter nélküli függvényt fogad argumentumként, ami egy olyan iterálható objektummal tér vissza, amely a sor tagjainak értékét folyamatosan tudja szolgáltatni. Azért nem közvetlenül az iterálható objektumot lehet megadni, mert ha menet közben kiderül, hogy nem Leibniz sorról van szó, akkor az alternatív ágban történő összegzés hibás lenne, hiszen a tagsorozat elemeinek egy része már fel lett használva. Azzal, hogy a leírt tulajdonságú függvényt adjuk át argumentumként, annak meghívásakor a sorozatot generáló objektum újra előáll, és így ismét az első elemtől kezdve lehet kikérni a sor tagjait.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
from itertools import islice from math import isclose from typing import Iterable, Callable class SeriesSumCalculator: """ Numerikus sorösszegek számítására szolgáló osztály. Mivel a Leibniz-típusú sorok mindig konvergensek, először ez alapján próbálja meghatározni a sor összegét, figyelembe véve a beállított 'epsilon' konvergencia hibahatárt. Ha a sor nem felel meg a Leibniz-kritériumoknak, akkor az általános sorösszeg-képlettel számol tovább. Ebben az esetben a konvergencia nem garantált, ezért csak a 'max_terms' által meghatározott számú tag kerül összegzésre. A számítás után a megfelelő attribútumok jelzik, hogy a sor megfelelt-e a Leibniz-kritériumnak. Ha igen, lekérdezhető a konvergencia gyorsaságát jellemző index is. Ha nem, akkor ennek oka a 'remark' attribútumban olvasható. Paraméterek: epsilon (float): Leibniz-típusú sorok esetén az a hibahatár, amelyen belülre eső tagokat már nem vesszük figyelembe az összegzésnél. Alapértelmezés: 1e-7. convergence_check_limit (int): Az a legnagyobb index, ameddig vizsgáljuk, hogy a sor tagjai az `epsilon` értéken belülre esnek-e. Ha ezt nem érik el, akkor a sor vagy nem konvergens, vagy a konvergencia nagyon lassú. Alapértelmezés: 100_000_000. max_terms (int): Nem Leibniz-típusú sorok esetén az összeadandó tagok maximális száma. Alapértelmezés: 10_000. Attribútumok: is_leibniz (bool): True, ha a sor megfelelt a Leibniz-kritériumoknak az összegzés során. remark (str): A sorösszeg számítása után ebből olvasható ki a magyarázat, hogy miért nem minősült a sor Leibniz-típusúnak. cutoff_index (int): Az az index, amelytől kezdve a sorösszeghez a tagokat már nem vesszük figyelembe. Leibniz soroknál ez a konvergencia sebességére utal. """ def __init__(self, epsilon: float = 1e-7, convergence_check_limit: int = 100_000_000, max_terms: int = 10_000): self.epsilon = epsilon self.convergence_check_limit = convergence_check_limit self.max_terms = max_terms self.is_leibniz: bool = False self.remark: str = '' self.cutoff_index: int = 0 def series_sum(self, infinite_sequence_factory: Callable[[], Iterable[int | float]]) -> float: """ Egy adott numerikus sor összegét számítja ki. Először megkísérli a sor összegét a Leibniz-kritérium alapján meghatározni. Ha ez nem teljesül, mert a sor tagjai nem váltakozó előjelűek vagy abszolútértékük nem monoton csökkenő, akkor a sorösszeget a beállított maximálisan figyelembe veendő számú tag ('max_terms') alapján számítja. Paraméterek: series (callable): Paraméter nélküli függvény, amely egy olyan iterálható objektummal tér vissza, amely a sor tagjainak értékét szolgáltatja. E sorozatnak végtelen hosszúságúnak kell lenni, mivel a sorösszegzés potenciálisan korlátlan számú tagot vesz figyelembe. Az iterátor elemei int vagy float típusúak lehetnek. Visszatérési érték: float: A sor összege a számítási módszernek megfelelő pontossággal. Kivétel: TypeError: Ha a 'series()' által visszaadott értékek nem iterálhatók. """ # Annak ellenőrzése, hogy az argumentum iterálható objektum-e. if not self._is_iterable(infinite_sequence_factory()): raise TypeError(f'Az argumentum nem iterálható objektumot szolgáltat.') try: s_sum = self._leibniz_series_sum(infinite_sequence_factory()) self.is_leibniz = True self.remark = '' return s_sum except ValueError as ve: s_sum = self._non_leibniz_series_sum(infinite_sequence_factory()) self.is_leibniz = False self.remark = str(ve) return s_sum @staticmethod def _is_iterable(obj) -> bool: """A visszatérési értéke True, ha az argumentum iterálható objektum, egyébként False.""" try: iter(obj) return True except TypeError: return False def _leibniz_series_sum(self, infinite_sequence: Iterable[int | float], epsilon=1e-7): """Leibniz-típusú sor összegét számolja annyi tagból, amennyi esetén a tagok értéke megfelelően közel van a nullához. Ezért az argumentumnak folyamatosan szolgáltatni kell tudni elemeket. """ checked_values = [] window_size = 10 result = n = 0 prev_item: int | float | None = None for n, item in enumerate(infinite_sequence, 1): result += item # A sor tagjai abszolútértékei monoton csökkenésének ellenőrzése. if prev_item is not None: if item * prev_item >= 0: raise ValueError('Nem Leibniz-típusú sor, mert a tagok nem váltakozó előjelűek.') if abs(item) > abs(prev_item): raise ValueError('Nem Leibniz-típusú sor, mert a tagok sorozata nem monoton csökkenő.') # Annak ellenőrzése, hogy a sor tagjainak sorozata nullához tart. # Kerekítésből adódó esetleges hibák kiküszöbölésére az 'epsilon' hibahatáron belülre kerülést adott # számú tagra vizsgáljuk, és csak akkor térünk vissza a sorösszeggel, ha minden tag már benne van a toleranciasávban. if len(checked_values) <= window_size: checked_values.append(item) else: b = all(isclose(val, 0, abs_tol=epsilon) for val in checked_values) checked_values.clear() if b: break if n > self.convergence_check_limit: raise ValueError('A sor tagjai nem, vagy nagyon lassan tartanak a nullához.') prev_item = item self.cutoff_index = n - window_size return float(result) def _non_leibniz_series_sum(self, infinite_sequence: Iterable[int | float]): """A 'max_terms' által meghatározott elemszámra számítja ki és adja vissza a sorösszeget.""" self.cutoff_index = self.max_terms return sum(islice(infinite_sequence, self.max_terms)) |
A teszteléshez a következő kódrészletben mutatott módon definiáltunk függvényeket, amelyek különböző sorok tagjainak sorozatát szolgáltató iterátorokkal térnek vissza. Ezek között a fenti ábrán mutatott minden Leibniz sor szerepel, az utána következő ábrán láthatókból pedig három.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
from itertools import count, cycle, repeat from math import factorial, sin from typing import Iterable, Generator import operator as op def fibonacci() -> Generator[int]: """A Fibonacci sorozat elemeit szolgáltató generátorobjektummal tér vissza.""" a, b = 1, 1 while True: yield a a, b = b, a + b def alternating_ones(a=1, b=-1) -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a és b értékeit váltakozva adja ki.""" return cycle([a, b]) def alternating_signed(iterable_object: Iterable[int | float], positive_starting_sign: bool = True) -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az 'iterable_object' értékeit váltakozó előjellel adja ki. Ha a második argumentum True, akkor a kiadott elemek előjelei megegyeznek az 'iterable_object' elemeinek előjelével, egyébként azok előjeleivel ellentétesek lesznek. """ return map(op.mul, iterable_object, alternating_ones(*[1, -1] if positive_starting_sign else [-1, +1])) def infinite_sequence1() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = (-1)^(n+1)/n képlettel definiált sorozatelemeket szolgáltatja. A ^ a képletben a hatványozást jelöli. """ return map(op.truediv, alternating_ones(), count(1)) def infinite_sequence2() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = (-1)^(n+1)/(2n-1) képlettel definiált sorozatelemeket szolgáltatja. A ^ a képletben a hatványozást jelöli. """ return map(op.truediv, alternating_ones(), ((2 * n - 1) for n in count(1))) def infinite_sequence3() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = (-1)^(n+1)/(n-1)! képlettel definiált sorozatelemeket szolgáltatja. A ^ a képletben a hatványozást jelöli. """ return map(op.truediv, alternating_ones(), (factorial(n - 1) for n in count(1))) def infinite_sequence4() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = (-1)^(n)n/2^n képlettel definiált sorozatelemeket szolgáltatja. A ^ a képletben a hatványozást jelöli. """ return map(op.truediv, alternating_signed(count(1), positive_starting_sign=False), (2 ** n for n in count(1))) def infinite_sequence5() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = (-1)^(n+1)(2n-1)/((2n-1)^2+1) képlettel definiált sorozatelemeket szolgáltatja. A ^ a képletben a hatványozást jelöli. """ return map(op.truediv, alternating_signed(count(1, 2)), ((2 * n - 1) ** 2 + 1 for n in count(1))) def infinite_sequence6() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = (-1)^(n+1)fibonacci(n)/2^n képlettel definiált sorozatelemeket szolgáltatja, ahol fibonacci(n) a Fibonacci sorozat elemeit adja. A ^ a képletben a hatványozást jelöli. """ return map(op.truediv, alternating_signed(fibonacci()), (2 ** n for n in count(1))) def infinite_sequence7() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = (-1)^(n+1)(2n-1)/2^(n-1) képlettel definiált sorozatelemeket szolgáltatja. A ^ a képletben a hatványozást jelöli. """ return map(op.truediv, alternating_signed(count(1, 2)), (2 ** (n - 1) for n in count(1))) def infinite_sequence8() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = 1/(n(n+1)) képlettel definiált sorozatelemeket szolgáltatja. """ return map(op.truediv, repeat(1), (n * (n + 1) for n in count(1))) def infinite_sequence9() -> Iterable[int | float]: """Egy iterálható objektummal tér vissza, amely az a(n) = sin(n)/(n(n+1)) képlettel definiált sorozatelemeket szolgáltatja. """ return map(op.truediv, map(sin, count(1)), count(1)) __all__ = [fn_name for fn_name in globals() if fn_name.startswith('infinite_sequence')] |
A tesztkód és az eredmények alább láthatók.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
from math import pi, e, cosh, log import infinite_sequences as infseq series_sum_calculator = SeriesSumCalculator() all_series = [(infseq.infinite_sequence1, 'ln(2)', log(2)), (infseq.infinite_sequence2, 'π/4', pi / 4), (infseq.infinite_sequence3, '1/e', 1 / e), (infseq.infinite_sequence4, '-2/9', -2 / 9), (infseq.infinite_sequence5, 'π/4/cosh(π/2)', pi / 4 / cosh(pi / 2)), (infseq.infinite_sequence6, '2/5', 2 / 5), (infseq.infinite_sequence7, '2/9', 2 / 9), (infseq.infinite_sequence8, '1', 1), (infseq.infinite_sequence9, '(π-1)/2', (pi - 1) / 2), ] print('{:^28}{:^22}{:^20}{:^15}'.format('Elvi sorösszeg', 'Számított sorösszeg', 'Sorlevágás index', 'Leibniz sor')) for series_data in all_series: sequence_gen_factory, theoretical_sum_str, theoretical_sum_value = series_data print('{:13} = {:11.8f}{:^25.8f}{:14_}{:^20}{}'.format(theoretical_sum_str, theoretical_sum_value, series_sum_calculator.series_sum(sequence_gen_factory), series_sum_calculator.cutoff_index, 'Igen' if series_sum_calculator.is_leibniz else 'Nem', series_sum_calculator.remark)) # Eredmény: # Elvi sorösszeg Számított sorösszeg Sorlevágás index Leibniz sor # ln(2) = 0.69314718 0.69314713 10_000_010 Igen # π/4 = 0.78539816 0.78539811 5_000_006 Igen # 1/e = 0.36787944 0.36787944 14 Igen # -2/9 = -0.22222222 -0.22222222 38 Igen # π/4/cosh(π/2) = 0.31301008 0.31301003 5_000_006 Igen # 2/5 = 0.40000000 0.40000000 74 Igen # 2/9 = 0.22222222 0.22222222 10_000 Nem Nem Leibniz-típusú sor, mert a tagok sorozata nem monoton csökkenő. # 1 = 1.00000000 0.99990001 10_000 Nem Nem Leibniz-típusú sor, mert a tagok nem váltakozó előjelűek. # (π-1)/2 = 1.07079633 1.07086819 10_000 Nem Nem Leibniz-típusú sor, mert a tagok nem váltakozó előjelűek. |
Megfigyelhetjük, hogy a Leibniz-típusú sorok között vannak, amelyek nagyon gyorsan konvergálnak, és vannak, amelyek meglehetősen lassúak. A nem Leibniz-típusú sorok esetében a konvergencia sebességére nem tudunk következtetni, hanem csak azt tudjuk nézni, hogy a megadott számú tag összegzése esetén mennyire tudtuk megközelíteni az elméleti sorösszeg értékét.
Ebben a bejegyzésben az iterálható objektumok, iterátorok és generátorok, valamint az itertools modul iterátorai domináltak. A fogalmakról egy rövid összefoglalót ad a „Mi az iterátor, generátor, generátor-iterátor és iterátor generátor, generátorfüggvény és -kifejezés?” című korábbi blog bejegyzés. Részleteiben, példákkal magyarázva a Python tudásépítés lépésről lépésre című e-könyvben a „Kérem a következőt! – iterálható objektumok”, a „Kifogyhatatlan sorozatlövők – generátorfüggvények” fejezetekben, valamint a „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” fejezeten belül a „Speciális iterátorok” című alfejezetben lehet olvasni.