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

Zadání:

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

Je dán interval pro hledání průsečíku. Předpokládáme, že v zadaném intervalu je pouze jeden průsečík. Rozdělení funkce na úseky s jedním průsečíkem by se řešilo jiným algoritmem.
Pro testy použijte funkci f(x)=10*(x-200)³=10x^{3 -} 6000x² + 1200000x – 80000000.  Počáteční podmínky krajních bodů intervalu 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 délka intervalu 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, přičemž průsečík s osou zůstane mezi krajními body. 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, který je dostatečně blízko skutečnému řešení. Proto se zvolí přesnost Tolerance nalezení hodnoty x od skutečné hodnoty. Potom ukončíme algoritmus, pokud se krajní body intervalu na ose x k sobě přiblíží na hodnotu menší než zvolená Tolerance. Samozřejmě se ukončí při f(x) = 0.

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.
Vhodný vstup je například -1000;1000;0.1
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 2.

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].
Ve funkci main ověřte správné fungování výpočtu pro polynom s koeficienty 10;-6000;1200000;-80000000 voláním s parametry x, které jsou zde uvedeny s výsledky (vstup,vystup): (0,-80000000),(1,-78805990), (-1,-81206010) .
Tuto funkci budou využívat následující funkce.

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.
Ve funkci main zavolejte tuto funkci a vytiskněte výsledek.

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.
Ve funkci main zavolejte tuto funkci a vytiskněte výsledek.

DU pro další procvičení:
5. Upravte program tak, aby pracoval pro libovolný řád od 1 do MAXRAD (nastavte jako konstantu pomocí #define, v programu volte hodnotu 10). Jako první tedy načtěte ze vstupu celočíselnou hodnotu – řád polynomu funkce (pro uvedenou funkci tedy hodnotu řádu = 3 (celočíselný typ)). Při hodnotě řádu mimo stanovené meze, vraťte chybový kód 4. Následně načtěte koeficienty funkce, kdy jejich počet musí odpovídat zadanému řádu.

Poznámka 2: 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ístit 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).
Bohužel, v současné době daný mechanizmus nezastaví na konci programu, aby bylo možné si prohlédnout výsledky. Proto je nutné použít obdobného mechanizmu pro přesměrování výstupu do souboru a výsledky si prohlédnout v prohlížeči. program.exe < input.stdin >output.txt.
(Méně vhodné řešení s horší možností změny parametrů: Po dobu ladění programu je také možné zakomentovat načítání z klávesnice, zadat testovací hodnoty v definici proměnných a po odladění vrátit načítání ze standardního vstupu).

V případě zájmu o další rozšíření programu a procvičení dalších vlastností můžete zkusit naprogramovat
Zobrazování proměnných během ladění

Po dobu ladění si pro kontrolu činnosti algoritmu tiskněte aktuální hodnoty mezí. K tisku použijte makro LOG1, LOG2..., kde číslo v názvu udává počet tisknutých parametrů pomocí funkce printf. Pro toto makro použijte mechanizmus podmíněného překladu – v případě nadefinování proměnné LADENI (pomoci #define) bude makro tisknout hodnoty (tj. program bude obsahovat printf), v opačném případě bude makro „prázdné“ (tj. při překladu se na jeho místo neumístí žádný text).

Pozn.: funkci LOGX lze nahradit funkcí univerzální pro libovolný počet parametrů LOG(format, …) printf(format, __VA_ARGS__). „Parametr“ tři tečky značí, že na tomto místě může být libovolný počet parametrů. Tyto parametry se umístí do místa označeného __VA_ARGS__.

Poslední změna 2019-02-11