Riešenie polynomických rovníc

V praxi sa často stretávame s polynomickými rovnicami vyššieho stupňa, pre ktoré neexistujú riešenia vo forme vzorcov, resp. predpísaných postupov. V takýchto prípadoch nastupuje algoritmizácia a analytické postupy.


Za polynomickú rovnicu možno považovať každú rovnicu, ktorá má vo svojom zápise viacero polynomických členoch. Polynomický člen je každá mocnina neznámej x.

Každú polynomickú rovnicu možno upraviť do tvaru:

a.xn + b.xn-1 + c.xn-2 + ... + k.x2 + l.x1 +m.x0 = 0

polynomickú rovnicu môžeme chápať aj ako funkciu f:

f(x) = a.xn + b.xn-1 + c.xn-2 + ... + k.x2 + l.x1 +m.x0

pričom čísla a, b, c, ... sú koeficienty špecifické pre každý prípad takejto funkcie.



Je zrejmé, že korene takejto polynomickej rovnice sa nedajú vypočítať podľa nejakého vzorca. V mnohých prípadoch sa nedá určiť ani presný koreň, ale len interval, v ktorom sa koreň zaručene nachádza. Približné hodnoty koreňa (hodnoty v intervale) sa nazývajú aproximácie koreňa

Pre koreň x musí platiť f(x) = 0. Ak vezmeme do úvahy toleranciu E (epsilon) pre hodnoty f(x), potom všetky aproximácie z intervalu musia spĺňať podmienku abs (f (aprox)) = E.

Našou úlohou je napísať program, ktorý pre danú funkciu analytickým riešením čo najpresnejšie určí interval koreňov <a;b>. Keďže je matematicky nemožné vypočítať z hodnoty funkcie f(x) parameter x, bude treba nájsť taký parameter x, pre ktorý f(x) bude čo najbližšie k 0.

Pozn: Ak pre koreň x platí, že f(x) = 0, pre interval riešenia spojitej funkcie platí f(a) * f(b) < 0

napíšme teda program, ktorého vstupom bude polynomická rovnica, resp. jej koeficienty, presnosť(počet krokov algoritmu) a interval na ktorom sa bude výpočet uskutočnovať. Zdrojový kód programu môže vyzerať napríklad takto :
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

const float null = 10E-99;


   // Funkcia f vracia hodnotu polynómu o základe x, kde
   // degree je stupeň polynómu a koef je pole obsahujúce
   // koeficienty.

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;
}


   // Funkcia polynom testuje definičný obor <a, b>
   // polynomickej funkcie. Predpokladá sa že funkcia je
   // na tomto obore monotónna. Výstupom funkcie je
   // čo najpresnejší odhad koreňa.

bool polynom (int stupen, float koef[], float a,
	      float b, int presnost) {
     if (f (a, stupen, koef) * f (b, stupen, koef) > 0) {
	return false;  
	// Ak sa koreň nenachádza v zadanom intervale,
	// funkcia vracia false
     } else {
	int drv;
	(f (a, stupen, koef) < f (b, stupen, koef)) ?
	    drv = 1 : drv = -1;
	    // Výraz určí, či je funkcia rastúca alebo klesajúca
	for (int i=0; i<presnost; i++) {
	    // Binárne hľadanie koreňa
	    float s = a/2+b/2;
	    if (f (s, stupen, koef) == null) {
	       cout << "Koren: " << s << endl;
	    } else {
	     if ((f (s, stupen, koef) < null && drv == 1) ||
	     (f (s, stupen, koef) > null && drv == -1))
		   a = s;
	       else
		   b = s;
	    }
	    printf("%5i.: < %10.10f , %10.10f >\n",i,a,b);
	}
	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;
      // pocet krokov algoritmu
      int presnost = 20;

      if (!polynom (stupen, koef, a, b, presnost))
	 cout << "koren nie je v intervale" << endl;
      system("PAUSE");
      return 0;
}


Dev, noemail@noemail.com
Stiahnuté z Developer.sk