La risoluzione di equazioni algebriche di grado elevato

Cristiano Teodoro

cristianoteodoro@virgilio.it

La risoluzione di equazioni algebriche di grado elevato

Con l’algoritmo del Quoziente-Differenza e l’algoritmo di Bairstow

Nel presente articolo vengono illustrati e considerati due metodi per il calcolo delle radici di una equazione polinomiale algebrica a coefficienti reali di grado superiore al 4°.

Sommario

I due algoritmi presi in esame sono, il primo noto come algoritmo del Quoziente-Differenza (Q-D), il secondo noto come algoritmo di Bairstow. Tutti e due i metodi implicano operazioni di tipo iterativo tramite le quali si possono far convergere i calcoli a dei risultati che presentano valori numerici molto vicini od uguali alle effettive radici dell’equazione algebrica considerata.

L’algoritmo Q-D risulta interessante perché è uno dei pochi metodi numerici che non necessita di parametri iniziali legati in qualche maniera alle radici dell’equazione stessa, a differenza del metodo di Bairstow per il quale occorre iniziare le operazioni di iterazione con opportuni parametri affinché i calcoli portino a dei valori uguali o prossimi a quelli effettivi della radici anziché a risultati di overflow.

Nell’articolo, dopo aver accennato all’utilizzazione della risoluzione delle equazioni algebriche nel campo della tecnica, vengono descritti i due algoritmi e si mettono in evidenza pregi, difetti e limitazioni inerenti ciascuno di essi. Da quanto esposto si evince che risulta preferibile il metodo di Bairstow, con la dotazione però di opportuni accorgimenti realizzati nel programma in Qbasic e mostrato nell’Allegato 2. Tale algoritmo risulta valido per tutte le equazioni algebriche che sono state provate e sottoposte a verifica.

Può anche essere interessante in diversi casi di risoluzione di equazioni sfruttare i risultati trovati con l’algoritmo Q-D per accelerare le operazioni di calcolo da eseguire con l’algoritmo di Bairstow.

Per avere dei risultati concreti l’articolo presenta due programmi in linguaggio Qbasic, uno relativo all’algoritmo Q-D, il cui listato è riportato nell’Allegato 1, l’altro a quello di Bairstow, riportato nell’Allegato 2. In essi per i calcoli ci si limita ad utilizzare la doppia precisione messa a disposizione dal software in Qbasic. È necessario pertanto fare attenzione ai risultati ottenuti per evitare il pericolo di andare in overflow o di avere addirittura errori di calcolo, quando i coefficienti dell’equazione sono o numeri interi molto grandi o numeri decimali composti da molte cifre.

Nel programma relativo all’algoritmo di Bairstow si è introdotta una ricerca esaustiva ed automatica dei due parametri “r” ed “s” riguardanti ciascun fattore quadratico di cui è composta l’equazione superando inoltre la difficoltà di eventuali possibili trabocchi di calcolo.

Oltre ad aver verificato l’efficienza dei due programmi tramite la risoluzione di diverse equazioni di cui si conoscevano a priori gli effettivi valori delle loro radici, nel listato del programma relativo all’algoritmo di Bairstow sono stati inseriti esempi di equazione di grado diverso (dal 3° al 25° grado).

Tale programma presenta quindi due opzioni, una relativa al calcolo delle radici di una equazione introducendo dall’esterno con l’istruzione INPUT il suo grado e i suoi coefficienti, l’altra riguardante la risoluzione della equazione scelta fra gli esempi proposti che compaiono nel listato.

Nel mostrare alcuni esempi di risoluzione di equazioni si fa ricorso all’algoritmo di Horner riportato in Allegato 3 tramite il quale si può effettuare una verifica nei riguardi dei valori numerici trovati al fine di accettarli o no come valori uguali o molto prossimi alle effettive radici dell’equazione, tenendo però presente che si possono avere risultati non soddisfacenti dovuti alle limitazioni di precisione od addirittura agli errori di calcolo dovuti al tipo disponibile di aritmetica utilizzata. Si presentano infine alcuni esempi relativi alla risoluzione di equazioni algebriche facendo presente che con il programma in Allegato 2 relativo all’algoritmo di Bairstow si riescono a risolvere con soddisfacente precisione equazioni algebriche di grado anche elevato come mostrato negli esempi.

Abstract

In this paper we propose two methods for the solution of an algebraic polynomial equation with real coefficients and degree higher of the fourth. The envisaged methods are the Quotient-Difference and the Bairstow algorithms. The both algorithms involve iterative operations, by which the computation converge toward numerical values that will give improving estimates of the equation roots.

The Q-D algorithm is interesting because it doesn’t need to supply any appropriate parameter for the iterative starting operations, differently from the Bairstow algorithm which wants some parameters for working out with success the course of the iterative arithmetical operations to avoid an overflow output.

In the paper we hint some employment of the algebraic equations in the technical field; then we give a description of the two algorithms and we highlight their advantage, restrictions and failings and we infer that it is preferable

www.matematicamente.it 1

the Bairstow algorithm, provided with the suitable some trick, as we have implemented in the Qbasic language program, displayed in Allegato 2.

This algorithm is proved efficient for all equations which we have tested. It is interesting also for some equations to utilize the results (outputs) founded by Q-D algorithm in order to quicken the computation pertinent to the Bairstow algorithm.

Then we present two programs in Qbasic language: the former is pertinent to QD algorithm and is showed in Allegato 1, the latter in Allegato 2 regards the Bairstow algorithm. The computation for both is implemented in double-precision arithmetic, available in the Qbasic software.

If the equation coefficients are large integer or large floating-point numbers, with this type of arithmetic we must take care to avoid possible overflow or wrong results.

We have inserted in the Bairstow algorithm program the performances for an exhaustive and automatic pursuit concerning the two parameters, “r” and “s” of every quadratic factor regarding the equation at issue and for avoiding the overflow output.

We check the efficiency of two programs by resolution of several equations with already their true roots and we insert in the Bairstow algorithm program several examples of equations of different degree (3° ÷ 25°). This program has two choices, the one related to the zeros computation of the equation by INPUT statement, the other pertinent to the resolution of an equation sorted out from several proposed examples inserted in the program list.

Then we outline the control of the founded zeros (roots) by Horner algorithm realized by the program in Allegato 3 for the aim to consider them as same or near real zeros of the equation, but considering that also the used double-precision arithmetic shows wrong computation results for arithmetical operations carried out with large floating-point numbers having fixed word length.

Finally we show some examples of solved algebraic equations, as well as of high degree.

1 - Introduzione

1.1 – Generalità sulle equazioni algebriche

Nella letteratura tecnica e precisamente nel campo dell’analisi numerica esistono vari algoritmi dedicati alla risoluzione con metodi iterativi delle equazioni algebriche di grado superiore al quarto. È noto infatti che per le equazioni di forma generale di grado superiore al quarto si ha l’impossibilità di risolverle per radicali (Teorema di Ruffini-Abel) [0].

In effetti per alcuni tipi particolari di equazioni algebriche, anche di grado superiore al 4°, si possono ricavare attraverso opportuni accorgimenti e formule le relative radici, come per l’equazione binomia xⁿ - a = 0, o come per le equazioni reciproche che si possono ridurre dal grado 2n al grado n, per cui ad esempio un’equazione di 6° grado può ricondursi alla risoluzione di una di 3° grado.

Le equazioni di 2°, 3° e 4° grado possono poi essere risolte con formule implicanti radicali: si vedano ad esempio i testi scolastici per la risoluzione delle equazioni di primo e secondo grado e testi o articoli più specializzati per quelle di terzo e quarto grado per le quali si può fare riferimento ad una vasta bibliografia [1], [2], [3], [4], [5].

Questa nota è pertanto dedicata al calcolo delle radici di una equazione algebrica a coefficienti reali di forma generale e di grado superiore al quarto, affrontando il problema di trovare i valori numerici delle sue radici reali o complesse con una approssimazione sufficientemente elevata, vale a dire con un errore fra l’effettivo valore della radice ed il valore trovato per la maggior parte delle volte inferiore in valore assoluto a 10^-8:

Si vuole far notare che con gli algoritmi proposti nel presente articolo si possono facilmente risolvere anche le equazioni di 3° e 4° grado, con una precisione sul valore delle radici non certo inferiore a quella ottenuta con le classiche soluzioni analitiche per radicali.

È noto che una equazione algebrica di grado n a coefficienti reali ha n radici che possono essere di valore reale od essere formate da coppie di valori complessi e coniugati, intendendo per coppia di radici complesse coniugate due radici una del tipo α + i β e l’altra del tipo α - i β dove α e β sono numeri razionali e i = −1.

Nell’impiego dei diversi metodi iterativi, come ad esempio il metodo di Bairstow od altri ancora, risulta auspicabile partire con opportuni valori dei parametri implicati nelle iterazioni allo scopo di poter convergere attraverso un limitato numero di iterazioni verso gli effettivi valori delle radici.

In questi metodi la scelta ottimale dei suddetti parametri tuttavia dipende in qualche modo dall’effettivo valore delle radici dell’equazione. Pertanto il maggior inconveniente di questi algoritmi sta proprio nel fatto che non conoscendo evidentemente a priori il valore delle radici non si possono conoscere e quindi scegliere i valori più convenienti dei suddetti parametri al fine di poter far convergere i risultati con un numero piccolo di iterazioni

www.matematicamente.it 2

verso i valori più o meno approssimati delle radici. Si parte allora di solito da valori convenzionali che possono portare in diversi casi addirittura ad una divergenza dei risultati con la conseguenza di avere un overflow nei calcoli. Si potrebbe quindi procedere per tentativi fino a trovare dei valori iniziali fortunati per i parametri di partenza tramite i quali, attraverso le opportune iterazioni proprie dell’algoritmo, si riesce a convergere verso gli effettivi valori delle radici. Può essere interessante allora utilizzare un algoritmo che non richiede a priori la conoscenza dei valori approssimati delle radici.

Un efficace algoritmo che possiede questa caratteristica è quello conosciuto nella letteratura tecnica come il metodo del Quoziente-Differenza (QD method) [6], [7], [8].

Poiché tuttavia questo metodo, anch’esso di tipo iterativo, presenta una convergenza lenta verso gli effettivi valori delle radici, potrebbe risultare opportuno, una volta trovati i valori anche se non molto approssimati delle radici, proseguire nella ricerca con l’algoritmo di Bairstow, tramite il quale si può arrivare generalmente ad una migliore approssimazione di tali valori.

Risulta conveniente così in diversi casi utilizzare la combinazione dei due algoritmi, l’algoritmo Q-D a cui far seguire l’algoritmo di Bairstow.

Qui di seguito ci limiteremo ad illustrare le relazioni e le formule iterative esistenti fra gli opportuni parametri che vengono impiegati nei due algoritmi, senza entrare nel merito delle giustificazioni teoriche relative ai due algoritmi, per i quali esiste una idonea letteratura [6], [7], [8], [9], [10].

1.2 – Cenni sull’utilizzo delle equazioni algebriche nella tecnica

Prima di passare alla descrizione dei due algoritmi, si vuole accennare all’importanza che assume la risoluzione delle equazioni algebriche con coefficienti reali, non solo nel campo prettamente matematico dell’analisi numerica, ma anche in svariati campi della tecnica. In effetti nella descrizione di molti fenomeni fisici, e quindi nello sviluppo di modelli matematici che li riguardano, trova ampia applicazione una particolare classe di equazioni differenziali, precisamente quella delle equazioni differenziali lineari a coefficienti costanti.

È noto che per risolvere un tale tipo di equazione si può utilizzare la sua associata equazione caratteristica che risulta essere una equazione algebrica di opportuno grado a coefficienti reali costanti. È pure altrettanto noto che nel campo delle tecniche circuitali elettriche, invece di descrivere un sistema fisico con un modello matematico che si evolve nel tempo e quindi come forma differenziale nella variabile temporale t, lo si può studiare come forma algebrica nella variabile di tipo complesso convenzionalmente denominata con il simbolo s = σ + i w, utilizzando la trasformata di Laplace,

n 1

∑ + −

⋅ =

(n 1)^k

a(k) s 0

risolvendo così al posto di equazioni differenziali delle equazioni algebriche del tipo

k 1

dove a(k) sono costanti reali ed s è la variabile che nell’ambito della trasformata di Laplace prende il posto della x.

Nel vasto campo poi dei Servomeccanismi, o più in generale in quello dei Sistemi di controllo lineare, la funzione di trasferimento F(s), quale rapporto tra la trasformata della segnale in uscita di un Sistema e la trasformata del segnale d’ingresso al Sistema stesso, sia esso controreazionato o meno, è costituita dal rapporto fra due polinomi

N(s).

È noto ad esempio che per lo studio della stabilità di un Sistema a controreazione occorre conoscere dove sono dislocate nel piano complesso s le radici del polinomio D(s), che prendono il nome di poli di F(s).

algebrici D(s)

È pertanto opportuno se non indispensabile risolvere l’equazione algebrica D(s) = 0 che può essere anche di grado superiore al 4°.

2 - Algoritmo Quoziente-Differenza (Q-D)

Sia da risolvere la seguente equazione algebrica di grado n:

− −

⋅ ⋅ ⋅ ⋅ ⋅

n n 1 n 2 3 2

x x a x x x

(3) x

a(1) + a(2) + +…………………a(n-2) + a(n-1) + a(n) + a(n+1) = 0

dove i coefficienti a(k) con l’indice k = 1, 2, 3, ………………… n + 1 sono numeri reali.

Si prendano in considerazione due matrici bidimensionali:

Una, che chiameremo Matrice Q, è formata da elementi relativi ad un parametro che indicheremo q(h, k) con h = 1, 2, 3 ….. it; k = 1, 2, 3, ……… n.

L’altra, che chiameremo Matrice D, è costituita da elementi relativi ad un parametro indicato con d(h, j) con h = 1, 2, 3, … it; j = 0, 1, 2, 3, ……… n.

dove n = grado dell’equazione e it = numero di iterazioni richieste

www.matematicamente.it 3

Utilizzando i coefficienti a(k) dell’equazione si costruisca la riga iniziale della matrice Q con i seguenti n valori q(1, k):

q(1,1) = -a(2)/a(1), q(1,2) = q(1,3) = q(1,4) = …………………q(1, n-1) = q(1, n) = 0 (1)

e la riga iniziale della matrice D con i seguenti n + 1 valori d(1, j):

+

a a a n

(3) (4) (1)

d(1,0) = 0, d(1,1) = , d(1,2) = ….. ….d(1,n-1) = , d(1,n) = 0 (2)

a a a n

(2) (3) ( )

Le due matrici risultano intimamente connesse fra di loro in quanto per le successive righe fra gli elementi q(h, k) e d(h, j) sussistono le due seguenti relazioni di tipo iterativo, una per il calcolo del valore di q(h, k):

q(h, k) = d(h-1, k) – d(h-1, k-1) + q(h-1, k) (1a)

con h variabile da 2 a it e k variabile da 1 a n.

L’altra relativa al calcolo del valore d(h, j):

d(h, j) = d(h-1, j) · q(h, j + 1) / q(h, j) (2a)

con h variabile da 2 a it e j variabile ora da 1 a n.

Dall’esame delle due formule (1a) e (2a) si deve considerare quanto segue:

Una volta noti con la (1) i valori degli elementi relativi alla prima riga della matrice Q e con (2) i valori degli elementi relativi alla prima riga della matrice D, si possono calcolare con la (1a) gli elementi relativi alla seconda riga della matrice Q; per calcolare però con la (2a) gli elementi relativi alla seconda riga della matrice D risulta necessario avere disponibili tutti i valori q(h, k) della seconda riga della matrice Q; utilizzando poi sempre le relazioni (1a) e (2a), si possono ricavare gli elementi delle successive righe delle due matrici calcolando comunque sempre tutti gli elementi della h-esima riga relativa alla matrice Q prima di passare al calcolo degli elementi relativi alla h-esima riga della matrice D.

Effettuando poi un opportuno numero it di iterazioni si riescono a trovare tutte insieme simultaneamente le n radici dell’equazione con valori tanto più approssimati ai loro valori effettivi quanto maggiore è il numero it delle iterazioni effettuate. Per trovare tali valori si tenga conto di quanto esposto qui di seguito.

Per il calcolo delle radici x(k) si prendono in considerazione dopo un congruo numero di iterazioni i valori ottenuti per q(h, k) nell’ultima iterazione it ed in quella precedente e vale quanto segue:

- 1R: si ha una radice di tipo reale ed il suo valore risulta essere x(k) = q(it, k) se si constata che nella colonna k presa in considerazione, il valore q(it, k) risulta essere costituito da numeri sempre o tutti negativi o tutti positivi per un opportuno insieme di valori q(h, k) precedenti q(it, k), vale a dire se non si sono avuti cambiamenti di segno nei valori di q(h, k) rilevati in un opportuno numero di valori numerici precedenti l’ultima iterazione; inoltre le varie differenze relative a q(h, k) – q(h-1, k) risultano normalmente in valore assoluto sempre più piccole.