Calculul unui polinom din mai multe variabile

În forma cea mai generală, un polinom de putere al mai multor variabile poate fi scris ca

Adică, polinomul include toate monomialele în care suma gradelor variabilelor nu depășește ordinea polinomului. Luați în considerare algoritmi pentru calculul unui astfel de polinom, precum și obținerea unei serii de valori ale monomialelor individuale care intră într-un astfel de polinom.







Pentru a calcula fiecare monomial separat nu este cea mai bună idee. Dacă credeți în renumita carte Rețete numerice. atunci când mașinile captează lumea, oamenii vinovați de o astfel de batjocură a computerului vor fi executați imediat.

De fapt, fiecare monomial al ordinului k poate fi calculat de la unul din monomialele ordinului k -1 cu doar o multiplicare. De exemplu, monomialele primei ordini sunt obținute prin înmulțirea unui monomial de ordinul zero (unul) cu una din variabile. Înmulțind din nou fiecare dintre aceste monomiale cu una dintre variabile, obținem toate monomialele secundare posibile și așa mai departe. Monomialele ordinului k-1

se înmulțește cu una dintre variabile și se obțin monomalii ale ordinului k.

Totuși, din moment ce a doua ordine există o problemă: monomialul va fi primit de două ori. De fapt, există atâtea variante de permutare a factorilor din formula (2), de câte ori și câte un monomial va fi primit. Pentru a nu face astfel de calcule repetitive, suntem de acord, din toate secvențele de calcul al monomialului (2), să alegem una pentru care indicii variabilelor sunt aranjate în ordine ascendentă. Pentru a realiza acest lucru, se înmulțește numai acele monomiale care nu conțin variabile cu numere mai mari decât i. Apoi numai cei care sunt puteri se înmulțesc - numai conținând și așa mai departe.







Cu această abordare, fiecare monomial servește pentru a calcula mai multe altele simultan. Gradele sunt înmulțite cu toate variabilele D. Monomiale care conțin și pe toate variabilele, începând cu. Etc. Procesul de calcul în acest caz poate fi reprezentat ca un copac:

Fig. 1. Procesul de calcul al monomialelor unui polinom multidimensional, reprezentat ca un copac. Fiecare nod corespunde unui monomial, iar fiecare margine este înmulțită cu una dintre variabile.

Procesul de calcul reprezentat ca un copac este cel mai natural realizat cu ajutorul unui algoritm recursiv. În cea mai simplă formă, o procedură recursivă calculează un monomial și se solicită să calculeze toate monomaliile copilului. Această procedură este prezentată mai jos:

Numărul total al monomialelor într-un polinom de ordine n din variabilele D poate fi calculat din formula

Calculul unei game de monomiale utilizând procedura de mai sus arată astfel:

Dacă trebuie efectuate calcule de mai multe ori pentru valori diferite de x. apoi pentru a accelera munca ar trebui să scape de recurs. O modalitate ușoară de a face acest lucru este de a face o traversare recursivă a copacului o singură dată și pentru fiecare monomial, amintiți-vă numărul monomială părinte și numărul variabilei la care s-a înmulțit. Apoi, această informație poate fi utilizată pentru a calcula monomiale fără recurs.

Codul corespunzător arată astfel:

Numim această procedură după cum urmează:

Un calcul al unui șir de monomiale pentru fiecare valoare a variabilelor x este după cum urmează:

Practica arată că un astfel de calcul nerecursiv se realizează mult mai rapid decât cel recursiv.

Să revenim acum la calculul polinomului propriu-zis. Un astfel de calcul va fi obținut prin traversarea nodurilor arborelui monomialelor prin înmulțirea lor cu coeficienții corespunzători și prin însumare. Aceasta ne conduce la următoarea formulă:

Aici indicii sunt numerele ramurilor arborelui prin care ajungem la monomialul corespunzător.

Această formulă este o generalizare a cazului multidimensional al binecunoscutului scheme Gorner pentru calculul unui polinom unidimensional:

Funcția care calculează în conformitate cu formula (4) este prezentată mai jos:

Pentru a ascunde parametrii MN, adâncime, i_depth, în general, trebuie să apelați această funcție prin alta:







Articole similare

Trimiteți-le prietenilor: