7. Predikáty a vzory, interpolace a aproximace

Predikáty

Predikát je funkce jedné nebo více proměnných, která vrací True nebo False. 
Několik příkladů:

EvenQ[14] (* Je 14 sudé číslo? *)

OddQ[14] (* Je 14 liché číslo? *)

PrimeQ[11] (* Je 11 prvočíslo? *)

MemberQ[{1,2,4,5},3] (* Je 3 prvkem seznamu {1,2,4,5}? *)

Porovnávací operátory <, >, <=, >=, ==, != jsou také predikáty.

Např. vnitřní reprezentace a<b je Less[a,b], kde Less je predikát dvou proměnných.

FullForm[a<b]

1<2

Predikáty jsou užitečné např. ve spojení s funkcí Select, která vybere všechny prvky zadaného seznamu, pro které predikát dává hodnotu True.

Select[Range[100],PrimeQ] (* Výběr všech prvočísel ze seznamu {1,...,100} *)

Příklad: Nalezení všech prvočísel menších než 100, která mají tvar 4k+1.

Definujeme vhodný predikát:

p[n_]:=(Mod[n,4]==1 && PrimeQ[n])

p[5]

Použijeme predikát ve spojení s funkcí Select:

Select[Range[100],p]

Clear[p]

Vzory

Vzory jsou obecné konstrukce používané v situacích, kdy je potřeba specifikovat jistou množinu přípustných výrazů. Vyskytují se např. v definicích funkcí.

Vzor typu identifikátor_

Tento vzor říká, že na daném místě může stát libovolný výraz.

f[x_]:=x^2

f[10]

Clear[f]

Identifikátor může být i prázdný, např. u konstantní funkce:

f[_]:=0

f[1]

Clear[f]

Složitější příklad - otočení vektoru v rovině o 90° proti směru hodinových ručiček:

rotace[{a_,b_}]:={-b,a}

rotace[{1,2}]

Zadáme-li jako argument něco jiného než dvojici, pak výraz zůstane nevyhodnocen:

rotace[1] (* výraz 1 nevyhovuje vzoru {a_,b_}, neboť se nejedná o dvojici libovolných výrazů *)

Clear[rotace]

Vzor typu identifikátor_hlava

Tomuto vzoru vyhovuje libovolný výraz s předepsanou hlavou. Připomeňme, že každý výraz v Mathematice má tzv. hlavu (viz 6. lekci), např. seznamy mají hlavu List, celá čísla hlavu Integer, atd.

V 5. lekci jsme naprogramovali rekurzivní výpočet faktoriálu:

f[1]:=1

f[n_]:=n f[n-1]

f[5]

Tato definice má nevýhodu – při zadání desetinného čísla se zacyklí:

f[2.5]

Clear[f]

Zde je náprava:

f[1]:=1

f[n_Integer]:=n f[n-1] (* Levá strana říká, že argumentem f může být pouze výraz s hlavou Integer, tj. celé číslo *)

f[2.5] (* 2.5 nemá hlavu Integer, nýbrž Real *)

Ani tato definice ještě není zcela odolná proti chybám, zacyklí se při zadání záporného čísla (brzy tento problém napravíme).

f[-1]

Clear[f]

Vzor typu identifikátor_ _ _

Na místě tohoto vzoru může stát nula nebo více libovolných výrazů oddělených čárkami. Tento vzor se používá např. pro funkce s volitelným počtem argumentů.

Příklad: Následující funkce slouží k vykreslení hypocykloidy. Jde o rovinnou křivku, jejíž tvar závisí na parametru n.

hypocykloida[n_]:=ParametricPlot[1/n{(n-1)Cos[t]+Cos[(n-1)t],(n-1)Sin[t]-Sin[(n-1)t]},{t,0,2Pi},PlotRange->{{-1,1},{-1,1}}]

Table[hypocykloida[n],{n,3,6}]

Nevýhodou této funkce je, že uživatel nemůže měnit vzhled obrázku (barvu, tloušťku čáry, apod.), aniž by funkci předefinoval.

Clear[hypocykloida]

Následující upravená definice umožnuje uživateli zadat další nepovinné argumenty, které následně předáme funkci Plot.

hypocykloida[n_,options___]:=ParametricPlot[1/n{(n-1)Cos[t]-Cos[(n-1)t],(n-1)Sin[t]+Sin[(n-1)t]},{t,0,2Pi},PlotRange->{{-1,1},{-1,1}},options]

hypocykloida[6] (* options jsou nepovinné, zde jsou prázdné *)

hypocykloida[6,PlotStyle->Red,Axes->False,Frame->True] (* zde se uplatní options *)

Clear[hypocykloida]

Konstrukce vzor?predikát

Na místě této konstrukce může stát libovolný výraz, který vyhovuje zadanému vzoru, a pro nějž zadaný predikát nabývá hodnoty True.

Příklad: Naprogramujte funkci, jejímž argumentem je celé číslo n. Funkce vrátí funkce n/2, pokud n je sudé, jinak nulu.

f[n_Integer?EvenQ]:=n/2

f[n_Integer?OddQ]:=0

Table[f[n],{n,1,10}]

Clear[f]

Konstrukce vzor/;podmínka

Na místě této konstrukce může stát libovolný výraz, který vyhovuje zadanému vzoru a splňuje zadanou podmínku.

Definice faktoriálu odolná vůči chybnému zadání:

f[1]:=1

f[n_Integer /; n>1]:=n f[n-1]

f[-1]

Clear[f]

Konstrukce vzor?predikát a vzor/;podmínka jsou podobné, ale nelze je zaměňovat. Za otazníkem následuje predikát (tj. název funkce), za středníkem následuje podmínka (tj. výraz, který má hodnotu True či False). Např. funkci z předchozího oddílu by bylo možné definovat i následujícím způsobem:

f[n_Integer/;EvenQ[n]]:=n/2

f[n_Integer/;OddQ[n]]:=0

Table[f[n],{n,1,10}]

Clear[f]

Vzory v lokálních pravidlech

Vzory můžeme používat i u lokálních přepisovacích pravidel.

Příklad: Funkce, která dostane seznam čísel a seřadí je podle velikosti.

Připomeňme, že výraz //. pravidlo znamená opakovanou aplikaci lokálního pravidla (viz 5. lekci). Následující definice opakovaně prohledává zadaný seznam. Hledá v něm dvojice sousedních čísel, která nejsou ve správném pořadí, a navzájem je vyměňuje.

sort[seznam_List]:=seznam //. {a___,b_,c_,d___}/; b>c ->{a,c,b,d}

sort[{4,7,0,1,3}]

Clear[sort]

Funkce Count, Cases a DeleteCases

Count[seznam,vzor] vrací počet prvků seznamu, které vyhovují zadanému vzoru:

Count[Range[100],_?PrimeQ] (* Počet prvočísel v seznamu {1,...,100} *)

Cases[seznam,vzor] (resp. DeleteCases[seznam,vzor]) najde (resp. odstraní) všechny prvky seznamu, které vyhovují (nevyhovují) zadanému vzoru:

Příklad: Nalezení všech prvočísel menších než 100, která mají tvar 4k+1.

Tuto úlohu jsme již řešili pomocí Select. Výhoda následujícího řešení pomocí Cases je v tom, že nemusíme definovat pomocný predikát.

Cases[Range[100],n_/;(Mod[n,4]==1 && PrimeQ[n])]

DeleteCases[Range[100],n_/;(Mod[n,4]==1 && PrimeQ[n])] (* čísla, která nejsou prvočísla nebo nemají tvar 4k+1 *)

Interpolace

Nejjednodušší úlohou interpolace je nalezení funkce, která prochází zadanými body {(Subscript[x, 1]),(Subscript[y, 1])}, ..., {(Subscript[x, n]),(Subscript[y, n])}. Často se požaduje, aby hledaná funkce byla polynom, tzv. Lagrangeův interpolační polynom. Lze jej najít pomocí InterpolatingPolynomial (výsledkem je polynom stupně ≤n-1):

data={{0,0},{1,2},{2,6},{3,2}}

InterpolatingPolynomial[data,x]

Expand[%]

Je-li bodů hodně, má Lagrangeův polynom vysoký stupeň a interpolace bývá nekvalitní (polynomy vysokého stupně oscilují).

data=Table[{i, RandomReal[{-1,1}]},{i,0,20}]

lagrange=InterpolatingPolynomial[data,x];
Show[Plot[lagrange,{x,0,20},PlotRange->{-5,5}],ListPlot[data,PlotStyle->{Black,PointSize[Medium]}]]

Clear[lagrange]

Chceme-li se vyhnout velkým oscilacím, můžeme hledat funkci, která není polynomiální, ale po částech polynomiální, tj. je poskládána z polynomů nízkého stupně.

Funkce Interpolation najde po částech polynomiální interpolaci; stupeň polynomů je implicitně 3, lze změnit pomocí InterpolationOrder.
Výstupem není vzorec, ale objekt typu InterpolatingFunction, se kterým lze pracovat jako s funkcí.

f=Interpolation[data] (* po částech kubická interpolace *)

Show[Plot[f[x],{x,0,20},PlotRange->{-5,5}],ListPlot[data,PlotStyle->{Black,PointSize[Medium]}]]

g=Interpolation[data,InterpolationOrder->1] (* po částech lineární interpolace *)

Show[Plot[g[x],{x,0,20},PlotRange->{-5,5}],ListPlot[data,PlotStyle->{Black,PointSize[Medium]}]]

S interpolační funkcí můžeme zacházet jako s jakoukoliv jinou funkcí, např. počítat funkční hodnoty, derivovat apod.

g[0.5]

dg[x_]=D[g[x],x] (* derivace po částech lineární interpolační funkce je po částech konstantní interpolační funkce *)

Plot[dg[x],{x,0,20},PlotRange->{-5,5}]

Clear[data,f,g,dg]

Numerické řešení diferenciálních rovnic

S objekty typu InterpolatingFunction se můžeme setkat také při numerickém řešení diferenciálních rovnic.

Funkce NDSolveValue má podobnou syntaxi jako DSolveValue (viz 5. lekci), kromě názvu proměnné je ale potřeba specifikovat interval, na jakém chceme rovnici řešit.

Najdeme numerické řešení rovnice x''(t)+0.1(((x(t))^2)-1)x'(t)+x(t)=0 (van der Polova rovnice) na intervalu [0, 150] s počátečními podmínkami x(0)=0.2, x'(0)=0.

NDSolveValue[{x''[t]+0.1(x[t]^2-1)x'[t]+x[t]==0,x[0]==0.2,x'[0]==0},x[t],{t,0,150}]

Plot[ %,{t,0,150}]

Aproximace

Aproximace je úloha podobného typu, jako interpolace. Netrváme na tom, aby funkce procházela zadanými body {(Subscript[x, 1]),(Subscript[y, 1])}, ..., {(Subscript[x, n]),(Subscript[y, n])}, ale chceme, aby její odchylka od těchto bodů byla co nejmenší (metoda nejmenších čtverců). Typické použití: Zkoumáme závislost mezi dvěma veličinami, ale měření jsou zatížena chybou.

data=Table[{x,3+2x+Sin[x]+RandomReal[{-1,1}]},{x,-20,20}] (* pomocí RandomReal simulujeme chybu měření *)

Fit[data,seznam funkcí,x] najde lineární kombinaci zadaných funkcí, která minimalizuje odchylku od zadaných dat.

f[x_]=Fit[data,{1,x,Sin[x]},x]

Koeficienty v lineární kombinaci jsou podobné těm, se kterými jsme začínali. Lineární kombinace dobře aproximuje data:

Show[Plot[f[x],{x,-20,20}],ListPlot[data]]

Obecnější než Fit je FindFit, který se neomezuje na lineární kombinace. Jeho vstupem je tzv. model - vzorec popisující požadovaný tvar funkce, ve kterém vystupují názvy proměnných a parametry.

FindFit[data,model,parametry,proměnné] najde hodnoty parametrů pro zadaný model tak, aby odchylka od zadaných dat byla minimální.

Příklad: Zkusme najít hodnoty parametrů a a c tak, aby funkce c·(a^n) co nejlépe aproximovala Fibonacciho čísla.

data=Table[{n,Fibonacci[n]},{n,0,20}]

koef=FindFit[data,c*a^n,{a,c},n]

Show[Plot[c*a^n/.koef,{n,0,20}],ListPlot[data]]

Porovnání s přesným vzorcem pro Fibonacciho čísla ukazuje, že aproximace je velmi dobrá:

Simplify[FunctionExpand[Fibonacci[n]],Element[n,Integers]]

N[%]