Algoritmus hledání průsečíku funkce f(x) s osou x metodou půlení intervalu



(2017)



Zadání:

Metodou půlení intervalu nalezněte průsečík funkce dané polynomem s osou x.

Předpokládáme, že v zadané části je pouze jeden průsečík. Rozdělení funkce na úseky s jedním průsečíkem by se řešilo jinde.
Pro testy použijte funkci f(x)=10*(x-200)3=10x3 - 6000x2 + 1200000x – 80000000.  Počáteční podmínky krajních bodů pro testy nastavte na -1000 a +1000.


Představu o průběhu funkce lze získat například pomocí online nástroje http://wolframalpha.com .


Popis algoritmu:
Je dána funkce f(x) a interval <a,b> na ose x, kde a < b. Funkce f() musí mít na intervalu <a,b> právě jeden průsečík s osou x.

1.      Vypočtěte hodnoty funkce f(a) a f(b) v krajních bodech intervalu a, b.

2.      Vypočtěte hodnotu funkce f(xs) v bodě xs = (a+b)/2 (xs je střed intervalu <a,b>).

3.      Je-li absolutní hodnota f(xs) menší než zadané číslo Tolerance nebo algoritmus proběhl MAXKROKU krát, výpočet ukončete.

4.      Hodnota xs nahradí ten z původních krajních bodů, jehož funkční hodnota má stejné znaménko. Tím se prohledávaný úsek zmenší na polovinu. Má-li hodnota f(xs) stejné znaménko jako hodnota f(a), pak a=xs. V opačném případě b=xs.

5.      Pokračujte opět bodem 1.



Poznámka 1: Vzhledem k tomu, že počítač vždy pracuje s čísly s omezenou přesností, nemusí se ani při teoreticky nekonečném počtu opakování kroků 1 až 4 algoritmu podařit nalézt bod x, kde by f(x) měla přesně hodnotu 0. Proto se musíme spokojit s nalezením bodu x, kde funkce nabývá dostatečně malé hodnoty (v absolutní hodnotě menší než zadané dostatečně malé číslo Tolerance).

Poznámka 2: Pokud bychom uvažovali, že průběh v okolí průsečíku bude velice strmý (například 1/x v okolí nuly), bylo by vhodnější použít jako podmínku ukončení výpočtu dosažení intervalu na ose x menšího než Tolerancex.

 

Postup řešení:

0.      Vytvořte projekt a v něm soubory mainpul.c, funkcepul.c a funkcepul.h. Soubor mainpul.c bude obsahovat funkci main a volání funkcí ostatních funkcí. Soubor funkcepul.c bude obsahovat funkce popsané v bodech 2 a 3. V souboru funkcepul.h. budou hlavičky funkcí definovaných v souboru funkcepul.c. Hlavičkový soubor ošetřete proti vícenásobnému načtení.

1.      Načtěte ze standardního vstupu koeficienty polynomu 3. řádu (4 koeficienty). Vstup bude mít tvar např. 10;-6000;1200000;-80000000. Koeficienty uložte do pole typu double. Při psaní programu uvažujte možnost snadného rozšíření na polynom N-tého řádu.
Dojde-li k chybě při načítání koeficientů, ukončete program s návratovou hodnotou 1.
Dále načtěte tři čísla. První dvě čísla určující levý resp. pravý okraj intervalu, třetí číslo je hodnota Tolerance. Čísla jsou opět oddělena znakem středník. Pro ukládání výše uvedených čísel použijte typ double, hodnoty intervalu uložte do pole.
Dojde-li k chybě při načítání Tolerance, ukončete program s návratovou hodnotou 1.
Budou-li špatně zadány hodnoty okrajů (a>b), ukončete program s návratovou hodnotou 2.
Bude-li špatně zadán Tolerance (<=0), ukončete program s návratovou hodnotou 3.
Pro načítání dat použijte funkci scanf, kontrolujte návratovou hodnotu (počet skutečně načtených parametrů).
Vstupní data nezadávejte ručně z klávesnice, ale postupujte dle poznámky 3.

2.      Napište funkci s prototypem double HodnotaFunkce(unsigned int aRad, double aKoef[], double aX), která vypočte hodnotu polynomu. Např. pro polynom 2. řádu se hodnota polynomu počítá dle vztahu: f(x)=(k[2]*x+k[1])*x+k[0]. Ověřte správné fungování výpočtu pro testovací hodnoty (vstup,vystup): (0,-80000000),(1,-78805990), (-1,-81206010) a polynom s koeficienty 10;-6000;1200000;-80000000.

3.      Napište funkci s prototypem double Prusecik(unsigned int aRad, double aKoef[],double aOkraje[2], double aTolerance). Funkce realizuje výše popsaný algoritmus hledání průsečíku funkce s osou x metodou půlení intervalu. Návratovou hodnotou je nalezený průsečík s osou x.

4.      Napište funkci s prototypem double PrusecikRek(unsigned int aRad, double aKoef[],double aOkraje[2], double aTolerance). Funkce realizuje výše popsaný algoritmus hledání průsečíku funkce s osou x metodou půlení intervalu s využitím rekurzivního způsobu výpočtu.

 

Poznámka 3: Jelikož vstup z klávesnice je dosti rozsáhlý, byl by při testování programu problém s neustálým zadáváním hodnot. Proto použijte pro načítání hodnot mechanizmus přesměrování vstupu místo klávesnice ze souboru. Vytvořte si soubor (například vstup.input s daty „ 10;-6000;1200000;-80000000 -1000;1000;0.1“. (Vstupní řetězce z minulých bodů jsou odděleny mezerou)
Pro přesměrování vstupu na soubor se na příkazové řádce používá symbol pro přesměrování „<“ program.exe < input.stdin. Tento mechanizmus funguje i v ladícím modu. Soubor input.stdin je ovšem nutné umístnit do pracovního adresáře, kterým je adresář se zdrojovými texty (standardně by tento soubor byl ve stejném adresáři jako spustitelný soubor). Přesměrování provedeme uvedením textu „<input.stdin“ do parametru argumenty překladače (u projektu volba properties/ configuration properties/ debugging/command arguments).

 

 

V případě zájmu o další rozšíření programu a procvičení dalších vlastností můžete zkusit naprogramovat ze staršího zadání této úlohy bod číslo 5 a sekci „Zobrazování hodnot během ladění“. Starší zadání je zde.















Poslední změna 2017-02-16