%% Hatodik gyakorlat
%% Nemlineáris egyenletek: intervallumfelezés, fixpont iteráció
%
% Cél: Az f(x)=0 egyenlet megoldása, ahol f adott, szép tulajdonságú (pl. folytonosan deriválható) függvény, azaz keressük az f függvény gyökeit/zérushelyeit. A mai gyakorlaton kizárólag f(x): \mathbb{R} \rightarrow \mathbb{R} függvényeket vizsgálunk.
%
%% Intervallumfelezés
% Tegyük fel, hogy tudjuk, hogy egy adott [a,b] intervallumon a függvényünknek van egy gyöke: például ezt onnan tudhatjuk, hogy f(a)<0 és f(b)>0. Az általános eset megszorítása nélkül ez feltehető (a másik esetben hasonlóan megy az algoritmus).
% Alapgondolat: Vizsgáljuk meg a függvény előjelét az \frac{a+b}{2} pontban! Ha itt pozitív, az azt jelenti, hogy a keresett zérushely az \left[a,\; \frac{a+b}{2}\right) intervallumban van, azaz itt érdemes folytatni a keresést. Ugyanakkor ha itt negatív, akkor a zérushely az \left( \frac{a+b}{2},\; b\right] intervallumban található, és itt kell tovább keresnünk. Ezt követően az előbbi gondolatot folytatjuk az új, kisebb intervallumokon, azaz vagy az \frac{a+b}{4}, vagy a \frac{3 (a+b)}{4} pontban vizsgáljuk a előjelet, és így tovább.
% Az algoritmus addig fut, amíg f értéke a vizsgált pontban nulla lesz (ez programok esetén a gépi hibák miatt nem reális), vagy amikor a vizsgált intervallum már nagyon kicsi ("kvázi nulla hosszúságú"). Természetesen megadhatunk maximális lépésszámot is, amely után álljon le mindenképpen a program.
% % tol: az elvárt pontosság.
%
% while (b - a)>tol
%      x = (b-a)/2;
%      f = f(x);
%
%      if f == 0
%         return x; % Ha véletlenül pont a felezőponton van a zérushely, akkor megállunk
%      else
%         if f>0
%              b = x;
%         else
%              a = x;
%         end
%      end
% end
% A módszer mindenképpen megtalál egy zérushelyet (ha több is van, akkor a zérushelyek közül valamelyiket).
%
% 1. feladat: Fibonacci egyik cikkében szerepel az alábbi állítás: az
% f(x) = x^3 + 2 x^2 + 10 x - 20
% egyenlet gyöke x = 1.368808107... Ellenőrizzük le az intervallumfelezéses módszerrel, hogy jól számolt-e!
% Megoldás: Legyen a toleranciánk 10^{-10}, és indítsuk az iterációt az [1,2] intervallumon!

...

%
%% Fixpont iteráció
% Alapgondolat: A korábbi f(x)=0 egyenletünket átírhatjuk
% x + c f(x) = x
% alakba, ahol c egy, a módszer közben meghatározandó konstans. Vegyük észre, hogy így a feladat tulajdonképpen az F(x) = x+ c f(x) függvény fixpontjának megkeresésével ekvivalens.
% Másik módszer: Ha az f(x) függvényből kifejezhető x, azaz pl. f(x) = k(x)  + x\;g(x), akkor egy másik lehetőség egy fixpont-egyenlet felírására az alábbi:
% x = - \frac{k(x)}{g(x)}
% Ekkor tehát az F(x) = - \frac{k(x)}{g(x)} függvény fixpontját keressük.
% Tétel: Ha F függvény ráképezés (tehát ha  [a,b]-n van értelmezve, akkor értékei is az [a,b] intervallumban vannak) és kontrakció a vizsgált [a,b] intervallumon, akkor az x_{k+1}=F(x_k) iteráció tart az F függvény fixpontjához.
% Állítás: Ha F függvény folytonos [a,b]-n, differenciálható (a,b)-n és van egy olyan 0 \leq q < 1 érték, amelyre |F'(x)|< q, akkor F kontrakció.
% 2. feladat: Keressük meg az első feladatban szereplő
% f(x) = x^3 + 2 x^2 + 10 x - 20
% egyenlet gyökét fixpont iteráció segítségével is! Legyen a vizsgált intervallum [a,b]=[1,2], és addig lépjünk, amíg a hiba kisebb, mint 10^{-10}.
% Megoldás (első módszer):

...

% Megoldás (második módszer):

...

%
% 3. feladat: Határozzuk meg azon pontot, ahol az f(x)=x^5 - x függvény értéke 2 lesz. Használjunk intervallumfelezést és fixpont iterációt is!
% Megoldás (intervallumfelezés):

...

% Megoldás (fixpont):

...