Algoritm pentru aflarea coeficientilor unui polinom atunci cand se cunosc radacinile polinomului

Algoritm pentru aflarea coeficientilor unui polinom atunci cand se cunosc radacinile polinomului

Se dau n numere reale x, x, , x, n. Vom construi un polinom f care are ca radacini numerele x, x, , x.

In mod evident, putem aplica relatiile lui Viete, dar va propunem urmatorul algoritm:

Vom considera coeficientul dominant al polinomului ca fiind egal cu 1, de aceea vom lua urmatoarea secventa:

Plasam prima radacina pe linia urmatoare, in stanga si coboram numarul 1. In continuare vom aplica urmatorul calcul: din valoarea aflata in casuta superioara se scade produsul dintre radacina si valoarea din locatia aflata in stanga casutei superioare, conform schemei:

In cazul nostru se obtine:

Pe aceeasi linie se adauga o noua casuta, careia i se atribuie valoarea 0 si se completeaza o noua linie, folosind aceeasi regula de calcul:

Procedeul continua similar:

pana la radacina x:

Se observa ca ultima linie din schema algoritmului contine exact coeficientii polinomului ce are ca radacini numerele x, x, , x.

Ideea algoritmului se bazeaza pe urmatoarea recurenta: daca f = X+ aX+ + a este polinomul de coeficient dominant 1, care are radacinile x, x, , x atunci g = (X+ aX+ + a)(X - x) este polinomul cu radacinile x, x, , x.

Dintr-un calcul simplu

g = X- xX+ aX- axX + aX + + aX - ax,

de unde g = X + (a - x)X + (a - ax)X + - ax.

Daca scriem g = X + b X + bX + +bX + b si identificam coeficientii, se obtine:

Dupa cum se observa, este vorba de calculul pe care l-am folosit in algoritm.

Pentru o mai buna intelegere a algoritmului, sa facem urmatorul exemplu:

Consideram numerele -1, 2, 2, 3 si aplicam algoritmul, obtinand:

Polinomul este f = X- 6X + 9X+ 4X - 12.

Problema aflarii coeficientilor unui polinom atunci cand se cunosc radacinile poate fi tradusa in limbajul informaticii astfel:

Fiind date numerele x, x, , x, n fixat, sa se afle un polinom care are ca radacini aceste numere, folosind un singur vector.

Rezolvare:

Deoarece polinomul are n radacini, rezulta care are gradul n si prin urmare are n + 1 coeficienti. De aceea vom considera un vector v de lungime n + 1 in care stocam valoarea 1 in prima locatie si x, x, , x in urmatoarele n locatii.

Notam acest vector v = (v, v, , v).

Singurul lucru de care mai avem nevoie este o locatie de memorie m, in care, pentru inceput, stocam valoarea x, inlocuind-o in vectorul v cu 0:

Acum aplicam calculul expus in prezentarea algoritmului: in locatia v plasam rezultatul v- mv. Obtinem:

Stocam acum valoarea x in locatia m, inlocuind pe xcu 0:

Pentru ca in calculul nostru avem nevoie de valoarea din locatia anterioara, vom calcula mai intai valoarea v care este egala cu 0 - x= xx si apoi valoarea v care e egala cu - x - 1x= - x- x.

Din acelasi motiv, la fiecare pas componentele vectorului v se calculeaza dinspre v spre v.

In final vectorul v va stoca exact coeficientii polinomului cautat.

In limbajul C++ algoritmul poate fi traspus astfel: