V predchádzajúcom článku je opísané hľadanie koreňov polynomických rovníc pomocou takzvaného binárneho hľadania, pričom predpokladáme monotónnosť intervalu. V dnešnom článku si opíšeme oveľa výkonnejšiu metódu - metódu sečníc.
Hľadanie koreňov metódou sečníc má mnoho výhod oproti predchádzajúcej metóde. Snáď najväčšou výhodou je predpoklad, že skúmaný interval polynomickej rovnice nemusí byť monotónny. Vďaka tomu metódu možno využiť na vyhľadávanie koreňov v širokých intervaloch, nie len v aproximáciách.
O čo vlastne ide ? Metóda sečníc nehladá aproximácie koreňov, ale presné korene. Využíva pritom spojitý charakter polynomickej rovnice. Podobne, ako v prípade prvej metódy, aj v tomto prípade treba zadať interval < a , b >, v ktorom sa koreň zaručené nachádza.
Existencia koreňa je podmienená vzťahom f(a) . f(b) < 0, kde f je polynomická funkcia a čísla a, b sú hranice skúmaného intervalu riešení.
Postup hľadania koreňa na intervale < a , b >:
1. krok: Vytvorenie takzvanej "sečnice". Sečnica je úsečka, ktorá spája bod [a , f(a)] a bod [b , f(b)]. Oba body sú na funkcií definované. Sečnica je na obrázku znázornená zelenou farbou.
2. krok: Další významný bod sečnice je bod, v ktorom sa sečnica pretína s osou x. Označme si x-ovú súradnicu tohto bodu ako c. Potom platí y = f(c) = 0, čiže bod na x-ovej súradnici leží. Pre výpočet tohto bodu si naprogramujme funkciu float sec (float x1, y1, x2, y2), kde [x1,y1] [x2,y2] sú body, ktoré definujú sečnicu:
float sec (float x1, float y1, float x2, float y2) {
float c;
c = x1 - y1 * (x2 - x1) / (y2 - y1);
return c;
}
# 3. krok: V predchádzajúcom kroru sme našli, kde sa sečnice pretne s x-ovou osou (bod [c,0]). Poďme teda zmenšiť interval : Ak sečnica preťala os v intervale a,b, presuňme bod a intervalu <a, b> do bodu c
# Ak c leží mimo <a, b>, presuň b do bodu c
(c < a || c > b) ? b = c : a = c ;
Kroky 1., 2., 3. opakujeme dovtedy, pokiaľ funkcia f(c) = 0, prípadne f(c) <= EPS, kde EPS je tolerancia.
while (f(c) <= EPS)
Algoritmus pre vyhľadávanie koreňov metódou sečníc dostávame úpravou algoritmu predchádzajúcej metódy:
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
// Funkcia f vracia hodnotu polynómu o základe x, kde
// degree je stupeň polynómu a koef je pole obsahujúce
// koeficienty.
const float null = 10E-99;
float f(float x, int degree, float koef[]) {
float val = 0;
for (int i=0; i<=degree; i++)
val+=koef[i]*pow(x,i);
return val;
}
float sec (float x1, float y1, float x2, float y2) {
float c;
c = x1 - y1 * (x2 - x1) / (y2 - y1);
return c;
}
// Funkcia polynom testuje definičný obor <a, b>
// polynomickej funkcie.
bool polynom (int stupen, float koef[], float a,
float b, float eps) {
if (f (a, stupen, koef) * f (b, stupen, koef) > 0) {
return false;
} else {
float c;
do {
c = sec(a, f(a, stupen, koef),
b, f(b, stupen, koef));
(c < a || c > b) ? b = c : a = c ;
} while (fabs(f(c, stupen, koef)) > eps);
printf("koren: %10.10f\n",c);
return true;
}
}
int main()
{
// Stupen polynom. funkcie
int stupen = 2;
// Koeficient 0, 1, 2 stupna
// pre rovnicu x^2 + 3x -460
float koef[] = {-460,3,2};
// interval
float a = 0;
float b = 100;
// tolerancia
float eps = 0.0001;
if (!polynom (stupen, koef, a, b, eps))
cout << "V zadanom intervale koren nie je" << endl;
system("PAUSE");
return 0;
}