Metodi numerici per il calcolo di punti di intersezione di curve razionali piane di B&eacutezier

(1)

Universit`

a degli studi di Pisa

Facolt`

a di Scienze Matematiche Fisiche e Naturali

Corso di Laurea in Matematica

tesi di laurea

Metodi numerici per il calcolo di

punti di intersezione di curve piane

razionali di B´

ezier

Candidato

Francesca Boccalini

Relatore

Controrelatore

Prof. Luca Gemignani

Prof. Dario Andrea Bini

(2)

(3)

Indice

Introduzione iii

1 Polinomi di Bernstein e curve di B´ezier 1

1.1 Polinomi di Bernstein . . . 1

1.2 Curve razionali piane di B´ezier . . . 5

1.2.1 Algoritmo di de Casteljau . . . 11

1.3 Punti multipli . . . 12

2 Calcolo di autovalori e autovettori 15 2.1 Algoritmo QR . . . 15

2.2 Algoritmo QZ . . . 24

2.3 Condizionamento degli autovalori . . . 32

2.4 Decomposizione agli autovalori singolari . . . 34

3 Risultante di Bezout 37 3.1 Introduzione . . . 37

3.2 Risultante di Bezout in base di potenze . . . 38

3.3 Risultante di Bezout in base di Bernstein . . . 44

4 Intersezione di curve di B´ezier: algoritmo di Manocha e Demmel 49 4.1 Implicitizzazione . . . 51

4.2 Problema agli autovalori associato . . . 52

4.3 Calcolo degli autovettori e dei sottospazi invarianti associati . 58 5 Intersezione di curve di B´ezier: algoritmi in base di Bern-stein 65 5.1 Implicitizzazione . . . 66

5.2 Problema agli autovalori associato . . . 67 5.3 Calcolo degli autovettori e dei sottospazi invarianti associati . 71

(4)

6 Risultati numerici 75

6.1 Implementazione . . . 75

6.1.1 Caso base di potenze . . . 75

6.1.2 Caso base di Bernstein . . . 78

6.2 Risultati numerici . . . 80

6.2.1 Intersezione semplice . . . 80

6.2.2 Intersezione multipla . . . 86

6.3 Conclusioni . . . 90

A Listati dei programmi 91

(5)

Introduzione

Le curve di Bézier sono degli oggetti matematici molto interessanti perchè al-lo stesso tempo potenti e semplici. Infatti con poco sforzo è possibile ottenere curve analiticamente “buone” (continue e derivabili). Ogni curva è comple-tamente determinata da un poligono detto poligono (di controllo) di Bézier, i cui vertici vengono anche detti punti di controllo o punti di Bézier. Infine i metodi per calcolare e disegnare una curva sono computazionalmente molto semplici ed efficienti. Queste caratteristiche rendono le curve di Bézier il prin-cipale strumento matematico utilizzato nella grafica computerizzata (CAGD) e nella modellizzazione geometrica assistita al calcolatore [17, 24, 28].

Nella pratica i disegnatori o gli utenti non si preoccupano della matema-tica (e quindi delle equazioni) che sono alla base di una curva. Essi si concen-trano pi`u o meno sullo svolgimento del proprio lavoro. Pertanto un sistema che voglia essere di ausilio agli utenti nel disegnare curve deve risultare:

1. Intuitivo. Ci si aspetta che ogni passo ed ogni algoritmo abbia un’in-terpretazione intuitiva e geometrica.

2. Flessibile. Il sistema dovrebbe fornire agli utenti un maggiore controllo per il disegno e la modifica della forma di una curva. La creazione e modifica di una curva dovrebbero essere semplici, intuitive e geome-triche, piuttosto che avvenire manipolando equazioni.

3. Approccio unificato. Il modo di rappresentare, creare e modificare tipi differenti di curve (per esempio linee, coniche, sezioni di coniche e cu-biche) deve essere uguale. Vale a dire non deve richiedere strumenti diversi per manipolare curve differenti (per esempio coniche e cubiche). 4. Invariante. La curva rappresentata non dovr`a modificare la sua ge-ometria a seguito di trasformazioni geometriche quali la traslazione, la rotazione e le trasformazioni affini.

5. Efficienza e stabilit`a numerica. Un utente di un sistema di disegno pu`o non curarsi della bellezza della geometria alla base, tuttavia si aspetta

(6)

che fornisca la curva desiderata in modo veloce ed accurato. Inoltre una grande quantit`a di calcoli non deve distorcere la forma della curva (stabilit`a numerica).

I prodotti software attualmente disponibili per il CAGD sono basati es-senzialmente sulla manipolazione di curve e superfici di Bézier e generalmente soddisfano i requisiti sopra esposti. Le curve di Bézier furono scoperte con-temporaneamente da Paul de Casteljau alla Citroen e Pierre E. Bézier alla Renault attorno alla fine degli anni ’50 ed inizio degli anni ’60. Le curve di Bézier sono curve parametriche polinomiali facilmente rappresentabili me-diante i polinomi di Bernstein. Le forme parametriche polinomiali non pos-sono rappresentare alcune forme semplici quali il cerchio. Introducendo coor-dinate omogenee che le rendono razionali, le curve di Bézier si generalizzano in curve razionali di Bézier che ovviamente risultano più potenti delle curve di Bézier dal momento che le prime possono rappresentare cerchi ed ellissi.

La presente tesi affronta il problema computazionale del calcolo degli eventuali punti di intersezione di due curve razionali piane di Bézier. In letteratura esistono diversi algoritmi per il calcolo dei punti di intersezione di curve parametriche che si basano principalmente su tre approcci differenti: l’implicitizzazione [27], la divisione di Bézier [20] e l’intervallo aritmetico [18]. La loro accuratezza è illustrata in [28]. In particolare l’approccio basato sull’implicitizzazione risulta più efficiente rispetto agli altri per curve di grado maggiore di quattro.

Date due curve razionali piane di B´ezier P (t) e Q(u), 0 ≤ t, u ≤ 1, espresse in forma parametrica, la tecnica basata sull’implicitizzazione procede attraverso i seguenti passi.

1. Si determina l’equazione implicita della curva P (t) come F (x, y) = 0, con F polinomio.

2. Si sostituisce la rapresentazione parametrica della curva Q(u) nell’e-quazione F (x, y) = 0 ottenendo un polinomio p(u) in una variabile le cui radici individuano i punti di intersezione cercati.

Il calcolo dell’equazione implicita pu`o effettursi mediante il concetto di risultante utilizzato nella teoria classica dell’eliminazione per sistemi di equa-zioni polinomiali [27, 30]. In particolare utilizzando la formulazione di Cayley del risultante di Bezout [26] si ottiene F (x, y) = det(xM1+ yM2+ M3), dove M = xM1 + yM2+ M3 `e una matrice di Bezout con coefficienti simbolici.

Per il passo 2 sono allora possibili due differenti strategie risolutive. La prima si basa sul calcolo esplicito dei coefficienti del polinomio p(u) mediante

(7)

Introduzione

manipolazioni simboliche della matrice M [12]. Questa classe di metodi for-nisce un approccio risolutivo di tipo ibrido dove manipolazioni simboliche si alternano a procedimenti numerici. In generale si osserva che il costo computazionale risulta dominato dalla fase simbolica che pu`o essere partico-larmente onerosa in termini di tempo e risorse di calcolo richieste. Inoltre la disponibilit`a di ambienti software che permettano contemporaneamente di lavorare con manipolazioni simboliche e numeriche limita l’interesse pratico degli algoritmi “ibridi”.

Un metodo interamente numerico per la risoluzione del problema F (x, y) = 0 è stato recentemente proposto da D. Manocha e J. Demmel nei lavori [22] e [23]. L’idea fondamentale è quella di trattare il problema F (x, y) = det(xM1+yM2+M3) = 0 come un problema generalizzato agli autovalori sen-za determinare esplicitamente i coefficienti del polinomio p(u), ma piuttosto lavorando direttamente sugli elementi delle matrici Mi con procedimenti it-erativi. In particolare, dopo la sostituzione della rappresentazione esplicita della curva Q(u) nell’equazione det(xM1 + yM2 + M3) = 0 il problema si riconduce ad un problema generalizzato agli autovalori del tipo Ax = λEx ove A è diagonale a blocchi e E è una matrice di Frobenius a blocchi. Per la risoluzione numerica del problema generalizzato agli autovalori uno strumen-to efficiente e numericamente robusstrumen-to risulta essere l’algoritmo QZ introdotstrumen-to da G. B. Moler e G. W Stewart [25] come variante del classico metodo QR per il calcolo degli autovalori di una matrice. Il calcolo dei sottospazi in-varianti associati agli autovalori della coppia (A, E) mediante tecniche di SVD permette l’analisi dei punti di intersezione ed una loro seppur parziale classificazione.

Si osserva che sia nella fase di implicitizzazione che nella risoluzione del problema generalizzato agli autovalori i polinomi si esprimono naturalmente nella forma di Bernstein. Nei lavori [22] e [23] si suggerisce pertanto di effet-tuare cambiamenti di base espliciti o semi-espliciti che riducono i polinomi nella usuale forma in base di potenze. Tali trasformazioni risultano numeri-camente mal condizionate e pertanto possono introdurre rilevanti errori nel calcolo.

Il principale risultato della tesi consiste nella modifica dell’algoritmo di D. Manocha e J. Demmel in modo tale da evitare qualsiasi cambiamento di base e operare sempre nella base dei polinomi di Bernstein. A tal fine si intro-ducono ed utilizzano opportune generalizzazioni degli strumenti utilizzati per la manipolazione dei polinomi nella base di potenze. Per l’implicitizzazione, si generalizza il concetto di matrice Bezoutiana per polinomi espressi nella base di potenze a polinomi espressi nella base di Bernstein. Riguardo invece il problema agli autovalori, si considera la generalizzazione delle matrici di Frobenius al caso di polinomi espressi nella base di Bernstein. Queste

(8)

ge-neralizzazioni erano gi`a note in letteratura [4, 35], ma la loro applicazione al problema in oggetto ha richiesto di ottenere nuove propriet`a e risultati concernenti sia la costruzione della matrici coinvolte che la caratterizzazione dei sottospazi invarianti associati agli autovalori calcolati.

Esperimenti numerici sono stati condotti per comparare il comportamen-to dell’algoritmo di D. Manocha e J. Demmel e della variante proposta. A tal fine si `e sviluppato un pacchetto di programmi MATLAB [15] che con-sentono la rappresentazione delle curve razionali, il calcolo dei loro punti di intersezione e l’analisi e la classificazione di tali punti mediante il calcolo dei sottospazi invarianti associati.

La tesi è organizzata come segue. I primi tre capitoli forniscono le definizioni preliminari e gli strumenti necessari per l’esecuzione dell’algorit-mo di D. Manocha e J. Demmel e della variante introdotta. In particolare nel capitolo 1 si introduce la base dei polinomi di Bernstein come alternativa alla base di potenze comunemente utilizzata per la rappresentazione dei poli-nomi, citandone alcune tra le proprietà principali. Di seguito si introduce anche la classe delle curve razionali piane di Bézier enunciandone le princi-pali proprietà numeriche. Nel capitolo 2 si descrivono i principrinci-pali algoritmi utilizzati per il calcolo degli autovalori e autovettori di un problema standard o genrelalizzato: l’algoritmo QR e l’algoritmo QZ. Tali algoritmi verranno utilizzati nei metodi descritti nei capitoli successivi. Infine nel terzo capitolo è stato introdotto il concetto di risultante, sia nel caso di polinomi in base di potenze, sia nel caso di base di Bernstein.

Nel capitolo 4 `e descritto l’algoritmo elaborato da D. Manocha e J. Dem-mel mediante la divisione in tre parti che corrispondono ai passi principali dell’algoritmo: implicitizzazione della curva P (t); riduzione ad un problema agli autovalori (generalizzato); determinazione dei parametri e dei punti di intersezione rispetto alle due curve.

Il capitolo 5 contiene una descrizione del nuovo algoritmo costruita in analogia al capitolo precedente.

Infine nel capitolo 6 sono riportati i risultati numerici ottenuti mediante l’implementazione in MATLAB di entrambi gli algoritmi che confermano la bont`a della modifica proposta.

(9)

Capitolo 1

Polinomi di Bernstein e curve

di B´

ezier

1.1 Polinomi di Bernstein

L’insieme Πndei polinomi p(x) a coefficienti reali di grado al più n costituisce uno spazio lineare su R di dimensione n + 1. La base comunemente usata per la rappresentazione di tali polinomi, detta base di potenze, è formata dall’insieme dei monomi {1, t, t2_{, · · · , t}n_{}. Quindi si può scrivere:}

p(t) = n X

i=0 aiti_,

con a0, . . . , an ∈ R. Questa rappresentazione, però, non è l’unica possibile né la migliore, soprattutto nel campo della modellizzazione di curve e super-fici. In questo ambito, infatti, risulta più conveniente e utilizzata la base di Bernstein.

Definizione 1.1. ([7]) Dato un intero k, si definisce base di Bernstein di Πk l’insieme dei polinomi

B_i(k)(t) = k i ti_{(1 − t)}k−i , i = 0, 1, · · · , k . (1.1)

dove B(k)i (t) `e detto i-esimo polinomio di Bernstein di grado k rispetto al-l’intervallo [0, 1].

La definizione (1.1) pu`o essere generalizzata a polinomi di Bernstein rispetto ad un intervallo [a, b] qualsiasi considerando la trasformazione affine

[a, b] → [0, 1] (1.2)

t 7→ x = x(t) := t − a b − a.

(10)

L’i-esimo polinomio di Bernstein B_i(k)(t, a, b) di grado k rispetto all’intervallo [a, b] `e dato per composizione dalla relazione

B(k)i (t, a, b) := B (k) i (x(t)) = 1 (b − a)k k i (t − a)i(b − t)k−i.

Senza perdere di generalit`a, nel seguito ci limiteremo a considerare polinomi di Bernstein rispetto all’intervallo [0, 1]. Tali polinomi saranno indicati come polinomi di Bernstein senza esplicitare l’intervallo di riferimento.

La rappresentazione di un polinomio p(t) di Πk, con k ≤ n nella base di Bernstein di Πn `e data da p(t) = n X i=0 c(n)_i n i ti_{(1 − t)}n−i = n X i=0 c(n)_i B_i(n)(t),

in cui i coefficienti c(n)_i sono detti coefficienti di Bernstein di p(t) nella base di Bernstein di Πn. Se k = n per semplicit`a scriviamo ci al posto di c(n)_i .

Sia Tn ∈ R(n+1)×(n+1) _{la matrice di ordine n + 1 tale per cui} [1, t, · · · , tn_{] Tn}₌h_B(n) 0 (t), B (n) 1 (t), · · · , Bn(n)(t) i . (1.3)

Vale il seguente teorema.

Teorema 1.1. ([5]) La matrice Tn `e triangolare inferiore e invertibile. Inol-tre Tn e T−₁

n sono simmetriche rispetto all’antidiagonale, cio`e [Tn]n+2−j,n+2−i= [Tn]i,j e [T−₁ n ]n+2−j,n+2−i= [T −₁ n ]i,j per 1 ≤ i, j ≤ n + 1 e si ha [Tn]ij =    0 se i < j (−1)i−j n i − 1 i − 1 j − 1 altrimenti (1.4) e [T−₁ n ]ij =    0 se i < j i − 1 j − 1 n j − 1 −₁ altrimenti

Dimostrazione: Per prima cosa osserviamo che l’elemento tij della ma-trice Tn`e il coefficiente del termine di grado (i−1) del (j −1)-esimo polinomio di Bernstein. Applicando la regola del binomio di Newton si ottiene

n j − 1

(11)

Polinomi di Bernstein = n j − 1 k−(j−1) X s=0 (−1)n−(j−1)−stn−s n − (j − 1) s

da cui segue che, se i ≥ j, il coefficiente di ti _`e n j − 1 n − (j − 1) n − (i − 1) (−1)i−j _{= (−1)}i−j n i − 1 i − 1 j − 1 . Nel caso in cui i < j il coefficiente di ti_{`e nullo. In modo analogo si ottengono} i coefficienti di T−1

n .

La propriet`a di simmetria segue pertanto per verifica diretta degli ele-menti delle matrici.

2 Dall’invertibilit`a di Tn per la condizione (1.3) segue che

Teorema 1.2. ([5]) I polinomi dell’insieme (1.1) sono linearmente indipen-denti e costituiscono una base di Πk.

Inoltre valgono le seguenti propriet`a.

Teorema 1.3. ([8]) I polinomi di Bernstein B0(n)(t), . . . , B (n)

n (t) godono delle seguenti propriet`a.

(i) Assumono valori non negativi:

∀t ∈ [0, 1] Bi(n)(t) ≥ 0. (ii) Formano una partizione dell’unit`a, cio`e

n X

i=0

B_i(n)(t) ≡ 1.

(iii) Sono simmetrici rispetto a t e a (1 − t), cio`e Bi(n)(t) = B

(n)

n−i(1 − t), 0 ≤ i ≤ n. (iv) Verificano la formula ricorsiva

B(n)i (t) = (1 − t)B (n−1)

i (t) + tB (n−1)

(12)

(v) Si ha d dtB (n) i (t) = n h B(n−1)_i−1 (t) − B_i(n−1)(t)i. dove si assume che Bi(n)(t) ≡ 0 se i /∈ {0, 1, · · · , n}. (vi) Per ogni 0 ≤ i ≤ n

Bi(n)(0) = δ0,i e B (n)

i (1) = δi,n, dove δi,j denota il delta di Kronecker.

(vii) B_i(n)(t) ha esattamente un punto di massimo per t = i/n. Dimostrazione:

(i) Segue immediatamente dal fatto che t ∈ [0, 1].

(ii) Utilizzando la formula del binomio di Newton si ottiene 1 = (t + (1 − t))n= n X i=0 n i ti(1 − t)n−i= n X i=0 Bi(n)(t). (iii) Segue in modo immediato dalla definizione.

(vi) B_i(n)(t) = n i ti_{(1 − t)}n−i₌ = n − 1 i ti_{(1 − t)}n−i₊ n − 1 i − 1 ti_{(1 − t)}n−i ₌ = (1 − t)B_i(n−1)(t) + tB_i−1(n−1)(t) (v) d dtB (n) i (t) = d dt n i ti_{(1 − t)}n−i ₌ = i n! i!(n − i)!t i−1 (1 − t)n−i−(n − i)n! i!(n − i)!t i (1 − t)n−i−1 = = n(n − 1)! (i − 1)!(n − i)!t i−1_{(1 − t)}n−i₋ n(n − 1)! i!(n − i − 1)!t i_{(1 − t)}n−i−1 ₌ = nhB(n−1)_i−1 (t) − B_i(n−1)(t)i

(13)

Curve razionali piane di B´ezier

(vi) Segue in modo immediato sostituendo t = 0 oppure t = 1 nella defini-zione.

(vii) Si ottiene in modo immediato per B₀(n)(t) e Bn(n)(t). Segue invece dalle propriet´a (v) e (vi) per B_i(n)(t), 1 ≤ i ≤ n − 1.

2

1.2 Curve razionali piane di B´

ezier

I polinomi di Bernstein intervengono nella rappresentazione delle curve di Bézier, che devono il nome all’ingegnere francese Pierre Bézier e furono utiliz-zate negli anni Sessanta dalla casa automobilistica Renault per il design della carrozzeria e di altre parti di automobili. Ancora oggi risultano molto impor-tanti nella grafica computazionale e nella modellizzazione geometrica per la facile rappresentabilità tramite computer e per la capacità di approssimare curve più generali [1, 8].

Definizione 1.2. ([1]) Dati n + 1 punti Pi = (xi, yi) ∈ R2 _{e i rispettivi pesi} wi ≥ 0 con Pn_i=0wiBi(n)(t) 6= 0 per t ∈ [0, 1], una curva razionale piana di B´ezier di grado n `e definita da

P : [0, 1] → R2, P (t) = (X(t), Y (t)) = x(t) w(t), y(t) w(t) = Pn i=0wiPiB (n) i (t) Pn i=0wiB (n) i (t) . (1.6) Le terne (xi, yi, wi) sono chiamate punti di controllo generalizzati della curva P (t) e la spezzata che si ottiene collegando tra loro con segmenti i punti Pi, seguendo l’ordine, è nota come poligono di controllo. Nel caso in cui tutti i pesi wi risultano uguali a 1 la curva è detta curva piana di Bézier.

I polinomi di Bernstein B_i(n)(t) che intervengono nella rappresentazione parametrica di una curva piana razionale di B´ezier (1.6) sono anche detti blending function [11].

Esempio 1.1. Nel caso n = 3 si ha che una curva razionale piana di B´ezier `e definita come

P (t) = P0w0(1 − t)

3_{+ 3P1w1t(1 − t)}2 _{+ 3P2w2t}2_{(1 − t) + P3w3t}3 w0(1 − t)3_{+ 3w1t(1 − t)}2 _{+ 3w2t}2_{(1 − t) + w3t}3 . In tale caso P (t) `e detta curva cubica razionale piana di B´ezier.

(14)

La Figura 1.1 rappresenta la curva cubica razionale piana di B´ezier asso-ciata ai punti di controllo generalizzati (4, 1, 1), (5, 3, 3), (5, 1, 3) e (6, 2, 1).

3 3.5 4 4.5 5 5.5 6 6.5 7 0 0.5 1 1.5 2 2.5 3 3.5 4 P0 P1 P2 P3

(15)

In Figura 1.2 `e raffigurata la curva razionale piana di B´ezier di punti di controllo generalizzati (1, 2, 1), (2, 4, 1/6), (4, 6, 1/15), (6, 4, 1/20), (7, 4, 1/15), (9, 3, 1/6) e (10, 1, 1) e il suo poligono di controllo.

0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7

(16)

In Figura 1.3 `e raffigurata la curva razionale piana di B´ezier che ap-prossima una circonferenza. I punti di controllo generalizzati sono (0, 0, 1), (4, 0, 1/5), (2, 4, 1/5), (−2, 4, 1/5), (−4, 0, 1/5) e (0, 0, 1). −5 −4 −3 −2 −1 0 1 2 3 4 5 −1 0 1 2 3 4 5 P0=P5 P1 P2 P3 P4

Figura 1.3: Approssimazione di una circonferenza

Dalla definizione (1.2) segue che una curva piana di B´ezier `e rappresentata dall’equazione P (t) = (X(t), Y (t)) = n X i=0 PiBi(n)(t).

In questo caso i punti di controllo generalizzati sono sostituiti dai Pi detti semplicemente punti di controllo.

Curve razionali piane di B´ezier in forma parametrica P : [a, b] → R2,

P (t) = (X(t), Y (t)),

(17)

Si ha che P : [a, b] → R2 _{`e data da}

P (t(x)) = (X(t(x)), Y (t(x))) = Pn i=0wiPiB (n) i (x, a, b) Pn i=0wiB (n) i (x, a, b)) = Pn i=0wiPiB (n) i (t(x)) Pn i=0wiB (n) i (t(x)) .

Una curva piana razionale di Bézier verifica alcune proprietà che seguono immediatamente dalla definizione e dalle proprietà dei polinomi di Bernstein. Teorema 1.4. ([8]) Le curve razionali piane di Bézier verificano le seguenti proprietà.

(i) Simmetria. La curva non cambia invertendo l’ordine dei punti di controllo.

(ii) Inviluppo convesso. La curva `e completamente contenuta nell’invi-luppo convesso dei vertici Pi del poligono di controllo.

(iii) Interpolazione degli estremi. La curva passa per i punti di controllo P0 e Pn.

(iv) Invarianza affine. Una curva di Bézier è invariante per trasfor-mazioni affini. In particolre, sia Φ : R2 _{→ R}2 _{è una trasformazione} affine, ossia una mappa tale che se x = P

jαjaj con x, aj ∈ R2 e P

jaj = 1, allora Φx = P

jαjΦaj con Φx, Φaj ∈ R2. Si ha

Φ(P (t)) = ( ˆX, ˆY ) = Pn i=0wiPiB˜ (n) i (t) Pn i=0wiB (n) i (t) , con ˜Pi = Φ(Pi).

Considerando la proprietà dell’inviluppo convesso è possibile fornire una condizione necessaria affinchè due curve razionali piane di Bézier si inter-sechino.

Teorema 1.5. ([8]) Condizione necessaria affinchè due curve razionali piane di Bézier P (t) e Q(u) si intersechino è che si intersechino i rispettivi poligoni di controllo.

Esempio 1.2. In Figura 1.4 è raffigurata la curva razionale piana di Bézier P (t) di grado 3 definita dai punti di controllo generalizzati (1, 1, 1), (3, 4, 1/3), (6, 3, 1/3), (8, 1, 1) e la curva razionale piana di Bézier Q(u) di grado 4 di pun-ti di controllo generalizzapun-ti (0, 3, 1), (2, 1, 1/4), (4, 0, 1/6), (6, 1, 1/4), (9, 3, 1). Si nota che sia le curve che i rispetivi poligoni di controllo si intersecano.

(18)

−1 0 1 2 3 4 5 6 7 8 9 10 −1 0 1 2 3 4 5 6 P0 P1 P2 P3 Q4 Q1 Q0 Q2 Q3

Figura 1.4: Intersezione di curve piane razionali di B´ezier

Nelle applicazioni ha una particolare importanza la proprietà detta di pseudo-controllo locale secondo la quale i punti di una curva razionale piana di Bézier P (t) che sono maggiormente sensibili al cambiamento di un vertice Pi del poligono di controllo sono nella regione circostante il punto P (i/n)[8]. Questa proprietà viene illustrata nel seguente esempio.

Esempio 1.3. In figura 1.5 è rappresentata con la linea continua la curva razionale piana di Bézier P (t) definita dai punti di controllo generalizzati P0 = (4, 3, 1), P1 = (1, 1, 2), P2 = (3, 0, 2), P3 = (2, −2, 2), P4 = (0, 1, 2), P5 = (3, 3, 2), P6 = (4, 0, 2), P7 = (5, −2, 2) e P8 = (4, 1, 1). La linea trat-teggiata raffigura la curva razionale piana di Bézier ˜P (t) che ha come punti di controllo ˜Pi = Pi per 0 ≤ i ≤ 8 con i 6= 4 e ˜P4 = (1, 1, 2). L’asterisco indica il punto P (4/8) in prossimità del quale si verifica il massimo distanziamento tra le due curve rappresentate.

(19)

Curve razionali piane di B´ezier 1 2 3 4 5 6 −1 −0.5 0 0.5 1 1.5 2 2.5 3 3.5

Figura 1.5: Propriet`a di pseudo-controllo locale

1.2.1 Algoritmo di de Casteljau

Sia P : [0, 1] → R2 _{una curva razionale piana di B´ezier di grado n con} punti di controllo P0, . . . , Pn. Il calcolo di P (t0) per t0 ∈ [0, 1] pu`o essere effettuato in modo numericamente efficiente e robusto mediante l’algoritmo di De Casteljau [8].

Algoritmo 1

Input:

Gli n + 1 punti P0, . . . , Pn, i pesi wi che definiscono la curva P (s),

s∈ [0, 1] e t0 ∈ [0, 1]. Output: (X0, Y0) = P (t0) = Pn i₌₀PiwiB(n)i (t0) Pn i₌₀wiB_i(n)(t₀)

(20)

Calcolo: Si pone P_i0(t) = Piwi W_i0(t) = wi per r = 1, . . . n e i = 1, . . . , n − r. forr= 1, . . . , n do for_i_{= 1, . . . , n − r do} P_ir(t0) = (1 − t0)Pir−1(t0) + t0Pi+1r−1(t0) Wr i(t0) = (1 − t0)Wir−1(t0) + tWi+1r−1(t0) end for end for Si ha

Teorema 1.6. ([8]) Sia P (t) la curva razionale piana di B´ezier di punti di controllo P0, . . . , Pn e pesi w0, . . . , wn. Si ha P (t) = P 0 n(t) W0 n(t) 0 ≤ t ≤ n I coefficienti intermedi Pr

i(t) possono essere scritti in modo conveniente in un vettore triangolare chiamato schema di de Casteljau, di cui forniamo un esempio nel caso in cui n = 3.

P0 P1 P1 0 P2 P1 1 P02 P3 P1 2 P12 P03.

Il costo computazionale dell’algoritmo di De Casteljau per il calcolo del valore di una curva in un punto `e di O(n2_{) flops}1_.

1.3 Punti multipli

In Figura 1.6 `e riportato un esempio di curva razionale piana di B´ezier con punti di controllo generalizzati (2, 1, 1), (−1, 3, 5), (−1, 1, 5) e (2, 3, 1).

1

Numero di operazioni floating point x ∗ y, dove x e y sono numeri di macchina e ∗ `e un operazione tra +, −, ·, ÷

(21)

Punti multipli −1 −0.5 0 0.5 1 1.5 2 2.5 3 0.5 1 1.5 2 2.5 3 3.5 p

Figura 1.6: Punto multiplo

Definizione 1.3. ([22]) Una curva razionale piana di B´ezier nella forma parametrica P (t) si dice propriamente parametrizzata se ad ogni valore del parametro t nel dominio corrisponde un unico punto sulla curva, eccetto per un numero finito di valori.

La peculiarità del punto P è illustrata dalla seguente definizione. Definizione 1.4. Il punto P = (X1, Y1) = x(s1) w(s1), y(s1) w(s1) appartenente alla curva razionale propriamente parametrizzata P (t) di grado n ha molteplicità k se e solo se le equazioni

X1w(t) − x(t) = 0

(1.7) Y1w(t) − y(t) = 0

hanno k radici comuni, contate con la loro molteplicità. Se k = 1 il punto P è detto regolare. Se 1 < k < n allora P è detto punto multiplo di ordine k oppure punto singolare di molteplicità k.

(22)

Si verifica in modo immediato che P è un punto di molteplicità 2 per la curva P (t) e che invece ogni altro punto Q ∈ P (t), Q 6= P , è un punto regolare.

(23)

Capitolo 2

Calcolo di autovalori e

autovettori

Il calcolo dei punti di intersezione di curve complanari di B´ezier sar`a ricondot-to nel seguiricondot-to alla risoluzione di problemi agli auricondot-tovalori. In quesricondot-to capiricondot-tolo si introducono i principali metodi numerici utilizzati per risolvere tale tipo di problemi e se ne studia il condizionamento.

2.1 Algoritmo QR

L’algoritmo QR, introdotto da Francis nel 1961 [10, 2, 32, 33], `e il metodo pi`u usato per approssimare tutti gli autovalori di una matrice A ∈ Cn×n_.

Nella sua forma pi`u semplice, il metodo QR applicato ad A genera una successione {Ak} di matrici nel modo seguente:

Algoritmo 2

Input:

La matrice A ∈ Cn×n_.

Calcolo: Si pone A1 = A.

fork = 1, 2, . . . , do

1) Si calcola una fattorizzazione QR di Ak:

A_k= QkRk (2.1)

in cui Qk`e una matrice unitaria e Rk `e triangolare superiore;

2) Si costruisce Ak+1 come

(24)

end for

Si pu`o osservare che

Ak+1 = QH k AkQk

e quindi le matrici della successione hanno tutte gli stessi autovalori, essendo simili tra loro.

Il seguente teorema analizza la convergenza di questo metodo.

Teorema 2.1. ([2]) Sia A ∈ Cn×n _{tale che i suoi autovalori λi, i = 1, . . . , n,} abbiano moduli tutti distinti, cio`e:

| λ1 |>| λ2 |> . . . >| λn |> 0. Indicata con X la matrice degli autovettori di A, tale che:

A = XDX−1 ,

dove D `e la matrice diagonale il cui i-esimo elemento principale `e λi, si supponga che la matrice X−1

ammetta fattorizzazione LU . Allora esistono delle matrici di fase Sk tali che:

lim k→∞S H k RkSk−1 = lim k→∞S H k−1AkSk−1 = T, e lim k→∞S H k−1QkSk = I,

dove T è triangolare superiore con gli elementi principali uguali a λ1, λ2, . . . , λn. Quindi gli elementi principali di Ak tendono agli autovalori di A. Se A è una matrice hermitiana, allora T è diagonale.

Le ipotesi piuttosto restrittive di questo teorema hanno il solo scopo di facilitarne la dimostrazione e possono essere rilassate. Ad esempio se la ma-trice X−₁

non ammettesse fattorizzazione LU il metodo QR risulta ancora convergente [33]. Inoltre, in tale caso, la matrice T ha ancora come elemen-ti principali gli autovalori λi che però non sono più distribuiti in ordine di modulo decrescente. Un’altra ipotesi fatta nel Teorema 2.1 è che tutti gli au-tovalori abbiano modulo distinto; se questo non fosse verificato la successione formata dagli elementi principali di Ak non converge. Questo evidenzia la necessità di introdurre modifiche al metodo QR per essere utilizzato in casi particolarmente importanti nelle applicazioni, come quelli in cui la matrice A ha elementi reali e autovalori complessi. In particolare supponiamo ad esempio che

(25)

Algoritmo QR

dove λre λr+1 sono due numeri complessi coniugati oppure due numeri reali. Da questo segue che le matrici SH

k−1QkSk non convergono alla matrice I per la presenza in posizione (r + 1, r) di elementi che non tendono a zero. Si consideri allora la sottomatrice principale di ordine 2 di Ak formata dalle righe e colonne di indici r e r + 1, ossia la matrice

A(k)_r = " a(k)rr a(k)_rr+1 a(k)_r+1r a(k)_r+1r+1 # .

Si pu`o dimostrare [33] che la successione nA(k)r o

non converge, ma gli auto-valori delle sottomatrici A(k)r convergono a λr e λr+1. Gli elementi principali di Ak di indice diverso da r e r + 1 convergono agli altri autovalori. In modo analogo, nel caso in cui la matrice A abbia pi`u autovalori di modulo uguale, il metodo QR genera matrici Rk triangolari a blocchi, in cui gli autovalori dei blocchi diagonali convergono ad autovalori di A.

Il costo computazionale dell’algoritmo QR in generale `e di O(n3_{) flops per} passo. Tale costo diminuisce in modo sensibile trasformando inizialmente la matrice A di partenza in forma di Hessenberg superiore in quanto tale struttura rimane invariata ad ogni passo. Infatti vale il seguente teorema. Teorema 2.2. ([32]) Sia Ak una matrice non singolare in forma di Hessen-berg superiore e supponiamo che Ak+1 sia ottenuta da Ak mediante un passo dell’Algoritmo 1. Allora anche Ak+1 `e in forma di Hessenberg superiore.

Dimostrazione: Da (2.1) si ha che Qk = AkR−₁

k . Si dimostra facilmente che R−₁

k è triangolare superiore. Quindi Qk è in forma di Hessenberg supe-riore, essendo il prodotto tra una matrice in forma di Hessenberg superiore e una triangolare superiore. Allora, per lo stesso motivo, Ak+1 = RkQk è in forma di Hessenberg superiore.

2 L’ipotesi di non singolarit`a della matrice Ak nel Teorema 2.2 risulta piut-tosto restrittiva. Nel caso in cui la matrice Ak`e singolare in generale esistono decomposizioni QR di Ak per le quali Ak+1 perde la struttura di Hessenberg superiore; tale problema viene superato scegliendo opportunamente i fattori Qk e Rk [33].

La riduzione preliminare della matrice in forma di Hessenberg richiede O(n3_{) flops [33].} _{Il metodo QR, applicato ad una matrice in forma di} Hessenberg, richiede O(n2_{) flops per passo [2] anzich`e O(n}3_).

Nelle ipotesi del Teorema 2.1, durante l’esecuzione dell’Algoritmo 1 l’ele-mento a(k)_nn−1 della matrice Ak, in forma di Hessenberg superiore, diventa

(26)

trascurabile poichè gli elementi sottodiagonali tendono a zero. In tale caso a(k)_nn−1 viene considerato nullo e a(k)nn può essere preso come approssimazione dell’autovalore λn. Gli autovalori rimanenti coincidono con gli autovalori del-la sottomatrice principale di testa di ordine n − 1 che ha anch’essa forma di Hessenberg. Nuovamente, poichè gli elementi sottodiagonali tendono a zero, anche a(k)_n−1n−2 diventa trascurabile, a(k)_n−1n−1 apprrossima l’autovalore λn−1 e gli autovalori rimanenti coincidono con gli autovalori della sottomatrice prin-cipale di testa che ha ordine n − 2. In questo modo si esegue un processo, detto deflazione [33], che calcola gli autovalori uno alla volta lavorando su matrici il cui ordine diminuisce progressivamene.

Per accelerare la velocit`a di convergenza si usa una tecnica di traslazione dello spettro degli autovalori della matrice A, detta tecnica di shift. Il metodo QR con shift procede come segue.

Algoritmo 3

Input:

La matrice A ∈ Cn×n _{e il numero complesso ρ ∈ C.}

Calcolo: Si pone A1= A.

for_k_{= 1, 2, . . . , do}

1) Si calcola una fattorizzazione QR di Ak:

A_k− ρI = QkRk (2.3)

in cui Qk `e una matrice unitaria e Rk `e triangolare superiore;

2) Si costruisce Ak+1 come

A_k+1 = RkQk+ ρI.

end for

Anche in questo caso, con semplici conti, si ottiene che

Ak+1 = QHkAkQk. (2.4)

La determinazione della matrice Ak+1 mediante la relazione (2.4) anzich`e mediante (2.3) definisce il metodo del QR implicito [32].

Le matrici Qk possono essere considerate come prodotto di matrici di rotazione di Givens oppure di matrici elementari di Householder [32].

(27)

Algoritmo QR

Definizione 2.1. ([2]) Siano 1 ≤ i, j ≤ n con i 6= j, φ ∈ R e ψ ∈ C, con |ψ| = 1. La matrice Gij =            Ii−1 c −s 1 . .. 1 s c In−j           

in cui c = cos φ e s = sin ψ, `e detta matrice di rotazione di Givens. Definizione 2.2. ([2])Una matrice P della forma

P = I − 2vv H

kvk2₂, v 6= 0 `e detta matrice elementare di Householder.

Si pu`o dimostrare che le matrici di rotazione di Givens e le matrici elementari di Householder sono unitarie.

Un passo del metodo QR esplicito con shift consiste nel determinare la fattorizzazione QR della matrice A − ρI, in cui si suppone che A sia in forma di Hessenberg superiore, ossia

A − ρI = QR, RQ + ρI = ˆA e

ˆ

A = QHAQ. (2.5)

Come prima cosa si trasforma la matrice A − ρI in forma triangolare su-periore moltiplicandola a sinistra per una successione di matrici di rotazione di Givens {Gk} = {Gkk+1} tali che l’i-esima matrice GH

i agisce sulle righe i e (i + 1) annullando l’elemento in posizione (i + 1, i). In particolare si ottiene che

R = GH

n−1· · · GH1 (A − ρI) (2.6)

Q = G1G2· · · Gn−1 (2.7)

Al primo passo la matrice di rotazione GH

1 agisce sulle prime due righe di A − ρI nel modo seguente:

a11− ρ a21 → ? 0 .

(28)

Calcolata tale matrice G1 si ottiene A1 = GH

1 AG1 =

a(1)_ij . Si pu`o osservare che GH

1 A rimane in forma di Hessenberg superiore, mentre la moltiplicazione a destra per G1 ne modifica la forma, ossia crea un elemento non nullo in posizione (3, 1). A → GH₁ AG1 = A1 =           a(1)₁₁ a(1)₁₂ a(1)₁₃ · · · a(1)_1n a(1)21 a (1) 22 a (1) 23 · · · a (1) 2n a(1)₃₁ a(1)₃₂ a(1)₃₃ · · · a(1)_3n a(1)43 · · · a (1) 4n . .. .._. a(1)_n−1n a(1)nn           . Indicata con R1 = r_ij(1)= GH

1 (A − ρI) la matrice che avr`a la forma:

R1 =           r₁₁(1) r₁₂(1) r₁₃(1) · · · r(1)_1n r₂₂(1) r₂₃(1) · · · r(1)_2n r₃₂(1) a(1)₃₃ − ρ · · · a(1)_3n a(1)₄₃ · · · a(1)_4n . .. ... a(1)_n−1n a(1)nn − ρ           ,

l’algoritmo procede creando una matrice di rotazione di Givens GH

2 , che agisce sulla seconda e terza riga di R1 per annullare r32(1). Questo pu`o essere fatto senza calcolare esplicitamente R1. Infatti `e facile dimostrare che i vettori

" a(1)₂₁ a(1)₃₁ # e " r₂₂(1) r₃₂(1) #

sono proporzionali tra loro [32]. Quindi GH

2 si ottiene come la matrice che compie la trasformazione " a(1)₂₁ a(1)₃₁ # → ? 0 . Nuovamente, GH

2 A1 rimane in forma di Hessenberg superiore mentre in A2 = GH

2 A1G2 si crea un elemento non nullo in posizione (4, 2). In generale, al passo i + 1, GH

i+1 `e la matrice di rotazione di Givens che trasforma Ri = GH

(29)

Algoritmo QR " r(i)_i+1,i+1 r(i)_i+2,i+1 # → r (i+1) i+1,i+1 0 .

La matrice Ri+1 si ottiene senza calcolare effettivamente Ri, ma osservando anche nel caso generale che i vettori

" a(i)_i+1,i a(i)_i+2,i # e " r(i)_i+1,i+1 r(i)_i+2,i+1 #

sono proporzionali tra loro. Infine, per i = n − 1 si ha che R = Rn−1, ottenendo la decomposizione desiderata.

Il metodo QR con shift presenta un inconveniente. Infatti, anche se la matrice A di partenza ha elementi reali, durante il processo si può creare una matrice Ak con elementi complessi. Questo può essere evitato utilizzando una tecnica di doppio shift che permette di rimanere in aritmetica reale. La tecnica può esssere descritta nel modo seguente.

• Si applicano due passi dell’algoritmo QR con shift ρ, τ ∈ C, ossia A − ρI = QρRρ, RρQρ+ ρI = ˇA, (2.8) ˇ A − τ I = QτRτ, RτQτ + τ I = ˆA. Dalle relazioni ˇ A = QH ρ AQρ, A = Qˆ Hτ AQτ segue immediatamente che

ˆ

A = QH_AQ, con Q = QρQτ. Si ha

Lemma 2.1. ([32]) Siano Q = QρQτ e R = RτRρ, con Qρ, Qτ, Rρ e Rτ le matrici date da (2.8). Allora

(A − τ I)(A − ρI) = QR. Lemma 2.2. ([32]) Se A ∈ Rn×n _{e τ = ρ allora}

(a) (A − τ I)(A − ρI) `e una matrice reale;

(b) Se ρ e τ non sono autovalori della matrice A, allora Q e R definite nel Lemma 2.1 sono reali, e anche la matrice ˆA ottenuta con (2.8) `e reale.

(30)

L’algoritmo QR implicito con doppio shift applicato ad una matrice reale A di ordine n trasformata in forma di Hessenberg superiore procede quindi cercando la fattorizzazione QR della matrice

B = (A − ρI)(A − ρI) = =              b11 b12 b13 · · · b1n b21 . .. ... ... ... b31 . .. ... ... ... ... . .. ... ... · · · . .. .._. . .. ... ... . .. bn−2n . .. ... . .. bn−1n bnn−2 bn−1n bnn              .

Per prima cosa si considera la matrice di Householder HT

1 che agisce sulle prime tre righe di B in modo da annullare gli elementi sottodiagonali. Come passo successivo devono essere annullati gli elementi (3, 2) e (4, 2) della matrice HT

1 B. Questo pu`o essere fatto analogamente a prima con una matrice di Householder HT

2 che agisca sulle righe dalla seconda alla quarta. In generale, ponendo Ri = HT

i · · · H1T, al passo (i + 1)-esimo si costruisce la matrice di Householder HT

i+1 che agisce sulle righe dalla (i + 1)-esima alla (i + 3)-esima di Ri. Continuando in questo modo, dopo n − 1 passi otteniamo una matrice

R = HT

n−1· · · H2TH1TB

che è in forma triangolare superiore. In particolare si può osservare che tutte le matrici di Householder Hi agiscono su tre colonne eccetto l’ultima che agisce su due. La matrice ortogonale Q della fattorizzazione QR di B è data da

Q = H1H2· · · Hn−1.

L’algoritmo QR con doppio shift si basa sull’osservazione che le matrici Hi possono essere determinate senza calcolare esplicitamente la matrice B. Come gi`a osservato, la prima colonna ha solo gli elementi b11, b21e b31diversi da zero che, con semplici conti, risultano uguali a

b11 = a21 (a11− ρ)(a11− τ )

a21 − a12

, b21 = a21[(a11− τ )(a22− ρ)] ,

(31)

Algoritmo QR

Quindi la matrice di Householder H1 cercata fornisce la trasformazione   b11 b21 b31  →   r11 0 0  .

Grazie alla matrice H1 cos`ı ottenuta `e possibile calcolare A1 = HT

1AH1 che `e quasi in forma di Hessenberg superiore in quanto ci sono elementi in posizione (3, 1), (4, 1) e (4, 2) non nulli. A → HT 1AH1 = A1 =              a(1)11 a (1) 12 a (1) 13 · · · a (1) 1n a(1)₂₁ a(1)₂₂ a(1)₂₃ · · · a(1)_2n a(1)₃₁ a(1)₃₂ a(1)₃₃ · · · a(1)_3n a(1)₄₁ a(1)₄₂ a(1)₄₃ . .. ... . .. ... ... . .. . .. a(1) n−1n a(1)_n−1n a(1)nn              .

Come passo successivo si cerca la matrice di Householder H2 che fornisce la trasformazione    r(1)₂₂ r(1)₃₂ r(1)₄₂   →   ? 0 0  ,

dove (rij) sono gli elementi della matrice R1 = HT

1B. Si pu`o osservare che i vettori    r22(1) r₃₂(1) r₄₂(1)    e    a(1)21 a(1)₃₁ a(1)₄₁   

sono proporzionali [32]. Quindi H2 non `e altro che la matrice che effettua la trasformazione    a(1)₂₁ a(1)₃₁ a(1)₄₁   →   ? 0 0  ,

ossia `e la matrice che agisce sulle righe dalla seconda alla quarta di A1 e restituisce HT

2A1 in forma di Hessenberg superiore. Trovata la matrice H2, `e possibile calcolare A2 = HT

2 A1H2, che `e quasi in forma di Hessenberg superiore eccetto per gli elementi in posizione (4, 2),

(32)

(5, 2) e (5, 3). Adesso H3 sar`a la matrice agente sulla terza, quarta e quinta riga che esegue la trasformazione

   a(1)₃₂ a(1)₄₂ a(1)₅₂   →   ? 0 0  .

Passando da A3 ad A4 si ha lo spostamento degli elementi non nulli in-desiderati verso il fondo della matrice. Quindi, con tale procedimento, al passo (n − 1)-esimo si ha che ˆA = An−1, completando un passo dell’algoritmo QR con doppio shift.

2.2 Algoritmo QZ

Una variante dell’algoritmo QR creata per la risoluzione di problemi agli autovalori generalizzati `e l’algoritmo QZ, introdotto da C. B. Moler e G. W. Stewart [25, 6, 32, 13].

Definizione 2.3. ([6]) Date due matrici A, B ∈ Cn×n_{, il problema} genera-lizzato agli autovalori consiste nel determinare i numeri λ ∈ C per cui esiste x ∈ Cn_{, x 6= 0, con}

Ax = λBx (2.9)

I numeri λ associati alla coppia (A, B) e indicati con λ(A, B), sono detti autovalori del problema generalizzato o semplicemente autovalori generaliz-zati e le soluzioni x 6= 0 di (2.9) sono chiamate autovettori destri. Se λ `e un autovalore della coppia (A, B) e

yH_{A = λy}H_B con y 6= 0 allora y `e detto autovettore sinistro.

Se la matrice B `e non singolare il problema generalizzato pu`o essere ridut-to al problema agli auridut-tovalori per la matrice B−₁

A, dove la moltiplicazione può essere fatta ad esempio risolvendo il sistema BC = A rispetto a C mediante l’eliminazione gaussiana con strategie di pivot [2]. Se invece B è singolare non è possibile attuare tale riduzione in quanto B non è invert-ibile. Esistono altre ragioni, oltre al problema della singolarità della matrice B, che fanno preferire un approccio diretto senza riduzione ad un problema agli autovalori standard: se le matrici A e B sono simmetriche o sparse, il prodotto B−1

(33)

Algoritmo QZ

In questa sezione viene descritto un algoritmo, detto algoritmo QZ, che permette il calcolo di tutti gli autovalori generalizzati senza effettuare la riduzione iniziale ad un problema agli autovalori standard.

Il metodo QZ è una generalizzazione del metodo QR e richiede inizial-mente la riduzione della coppia (A, B) in una coppia ( Ã, ˜B) in cui Ã è in forma di Hessenberg superiore e ˜B è triangolare superiore.

Per prima cosa calcoliamo la fattorizzazione QR della matrice B, utiliz-zando una successione di matrici di Householder per annullare tutti i suoi elementi sottodiagonali.

Scriaviamo B come segue:

B =         ? · · · ? .. . ... b1 ... ... .. . ... ? · · · ?         .

Esiste una matrice di Householder H1 tale che H1b1 = γe1. Di consegenza:

H1B =        γ ? ? · · · ? 0 ? · · · ? 0 b1 2 ... ... 0 ... ... 0 ? · · · ?        , dove b1

2 indica la seconda colonna della matrice modificata H1B a partire dall’elemento diagonale. Come passo successivo si cerca una matrice di Householder H2 che annulla gli elementi sottodiagonali della seconda colonna. Procedendo in questo modo, dopo n − 1 passi la matrice B ha assunto una forma triangolare superiore.

Per preservare gli autovalori della coppia (A, B) `e necessario applicare le stesse trasformazioni anche alla matrice A. Quindi, se indichiamo con H = Hn−1. . . H1, abbiamo che

A → HA = ˆA `e una matrice qualsiasi mentre

B → HB = ˆB ha assunto forma triangolare superiore.

(34)

Il passo successivo consiste nel trasformare la matrice ˆA in forma di Hes-senberg superiore non alterando la forma triangonale di ˆB. Questo pu`o essere fatto usando una serie di rotazioni di Givens.

Inizialmente si considera la matrice di Givens Gn1 che annulla l’elemento in posizione (n, 1) di ˆA. ˆ A → GT n1A = ˆˆ A11=         ? · · · ? .. . ... .. . ... ? ... 0 ? · · · ?         , B → GT n1B = ˆˆ B11         ? · · · ? 0 . .. ... .. . . .. ... ... .. . 0 . .. ... 0 · · · 0 + ?         .

Ma come si può notare un elemento non nullo si è creato nella posizione (n, n − 1) della matrice ˆB11. Per risolvere tale problema basta moltiplicare per un’altra rotazione di Givens che annulli tale elemento, ma che non cambi lo zero introdotto nella matrice Â11. Usando quindi questa rotazione, che indichiamo con Gnn−1 = Znn−1 solo l’(n − 1)-esima e l’n-esima colonna di

ˆ

A11 e ˆB11 sono interessate ottenendo:

ˆ A11Znn−1 = ˆA12=         ? · · · ? .. . ... .. . ... ? ... 0 ? · · · ?         , ˆ B11Znn−1 = ˆB12=         ? · · · ? 0 . .. ... .. . . .. ... ... .. . . .. ... ... 0 · · · 0 ?         .

(35)

Algoritmo QZ

Ad ogni passo appare in ˆB un elemento indesiderato che pu`o essere tolto moltiplicando per un’altra rotazione di Givens che lo annulli, ma che non disturbi gli zeri introdotti in ˆA come visto prima.

Supporremo di seguito che (A, B) sia una coppia di matrici con A in forma di Hessenberg superiore e B triangolare superiore. Si pu`o supporre inoltre che B sia non singolare, altrimenti il problema pu`o essere trasformato in un problema di dimensione inferiore mediante la tecnica detta ‘zero-chasing’ [6]. Un passo dell’algoritmo QZ applicato alla coppia (A, B) consiste nell’e-seguire parallelamente un passo del metodo QR con shift applicato alle ma-trici AB−1

e B−1

A senza calcolare tali prodotti. Si inizia quindi considerando le decomposizioni QR

AB−₁

− ρI = ˆQR e B−₁

A − ρI = ˆZS con ˆQ, ˆZ matrici unitarie e R e S matrici triangolari superiori.

Definiamo ˆ A = ˆQ−₁ A ˆZ, (2.10) ˆ B = ˆQ−₁ B ˆZ. Allora segue immediatamente che

ˆ A ˆB−1 = ˆQ−1 AB−1ˆ Q = R ˆQ + ρI (2.11) ˆ B−₁ˆ A = ˆZ−₁ B−₁ A ˆZ = S ˆZ + ρI (2.12) ossia le trasformazioni AB−1 → A ˆˆB−1 e (2.13) B−₁ A → Bˆ−₁ ˆ A

sono entrambe passi dell’algoritmo QR con shift ρ. Inoltre ˆQ e ˆZ sono il prodotto di matrici di rotazione di Givens

ˆ

Q = ˆQ1· · · ˆQn−1 e Z = ˆˆ Z1· · · ˆZn−1.

Un modo alternativo per effettuare le trasformazioni (2.13) `e fornito dalla facile osservazione [32] che la prima colonna di ˆQ `e proporzionale alla prima

(36)

colonna di AB−₁ − ρI data da        a11b−₁ 11 − ρ a21b−₁ 11 0 ... 0        .

Sia Q1 una matrice di Householder con prima colonna proporzionale alla prima colonna di AB−1

− ρI. La trasformazione di (A, B) in (QH

1 A, QH1 B) lascia invariata la forma di Hessenberg superiore in QH

1 A ma altera quella triangolare superiore in QH

1 B facendo comparire un elemento non nullo in posizione (2, 1). A → QH 1 A = Â1 =         ˆ a(1)₁₁ · · · aˆ(1)_1n ˆ a(1)21 â (1) 22 · · · aˆ (1) 2n ˆ a(1)₃₂ â(1)₃₃ · · · aˆ(1)_3n . .. . .. .._. ˆ a(1)_nn−1 aˆ(1)nn         , B → QH 1 B = ˆB1 =         ˆb(1) 11 · · · ˆb (1) 1n ˆb(1) 21 ˆb (1) 22 · · · ˆb (1) 2n ˆb(1) 33 · · · ˆb (1) 3n . .. ... ˆb(1) nn         .

Per annullare l’elemento indesiderato si applica a destra una matrice di rotazione di Givens Z1 = G12 che, agendo sulle prime due colonne, resti-tuisce la matrice ˆB1Z1 in forma triangolare superiore creando un elemento indesiderato non nullo in posizione (3, 1) nella matrice ˆA1Z1.

ˆ A1 → ˆA1Z1 = A1 =         a(1)₁₁ · · · a(1)_1n a(1)₂₁ a(1)₂₂ · · · a(1)_2n a(1)₃₁ a(1)₃₂ a(1)₃₃ · · · a(1)_3n . .. . .. ... a(1)_nn−1 a(1)nn         ,

(37)

Algoritmo QZ ˆ B1 → ˆB1Z1 = B1 =         b(1)₁₁ · · · b(1)_1n b(1)₂₂ · · · b(1)_2n b(1)₃₃ · · · b(1)_3n . .. ... b(1)nn         .

Quindi viene presa in considerazione la matrice di Householder Q2, che agisce sulla seconda e terza riga, tale che QH

2 A1ha nuovamente forma di Hes-senberg superiore. Questo per`o provoca la comparsa di un nuovo elemento non nullo in posizione (3, 2) nella matrice QH

2 B1. Applicando a destra una matrice di rotazione Givens, agente sulla seconda e terza colonna, si ottiene che la matrice ˆB2Z2 `e nuovamente triangolare superiore, mentre appare un elemento non nullo in posizione (4, 2) nella matrice ˆA2Z2. Questo procedi-mento va avanti fino alla moltiplicazione per la matrice di rotazione di Givens Zn−1agente sulle ultime due colonne. Tale prodotto restituisce la forma trian-golare alla matrice trasformata Bn−1 = QH

n−1. . . QH1 BZ1· · · Zn−1 e non crea nuovi elementi indesiderati nella matrice An−1 = QH

n−1. . . QH1 BZ1· · · Zn−1 che risulta avere forma di Hessenberg superiore.

Il procedimento descritto rappresenta un passo dell’algoritmo QZ impli-cito che determina la trasformazione della coppia (A, B) nella coppia ( ˜A, ˜B) data da

˜

A = ˜QH_{A ˜}_Z _e _{B = ˜}_˜ _QH_{B ˜}_Z _(2.14) dove ˜Q = Q1Q2· · · Qn−1 e ˜Z = Z1Z2· · · Zn−1 sono matrici unitarie. Il teo-rema che segue infatti garantisce che la coppia ( Ã, ˜B) calcolata con l’algo-ritmo implicito sia essenzialmente uguale alla coppia ( Â, ˆB) data dalla re-lazione (2.10), nel senso che esistono matrici diagonali unitarie D e E tali che Â = D−₁ ˜

AE e ˆB = D−₁˜ BE.

Teorema 2.3. ([32]) Siano A, B ∈ Cn×n_{, con A in forma di Hessenberg} superiore e B triangolare superiore non singolare. Siano ˜A, ˆA, ˜B, ˆB, ˜Q, ˆQ,

˜

Z e ˆZ le matrici definite dalle relazioni (2.10) e (2.14).

Se ˜Q e ˆQ hanno essenzialmente la stessa prima colonna, cio`e ˜q1 = ˆq1d1 con |d1| = 1, allora esistono due matrici diagonali unitarie D e E tali che

ˆ Q = ˜QE, Z = ˜ˆ ZE, ˆ A = D−₁˜ AE e B = Dˆ −₁˜ BE.

Dopo aver eseguito alcuni passi dell’algoritmo QZ, si `e creata una succes-sione di coppie (Ak, Bk) equivalenti. Scegliendo opportunamente gli shifts

(38)

le matrici Ck = AkB−₁

k e Ek = B

−₁

k Ak convergeranno alla forma trian-golare superiore o triantrian-golare superiore a blocchi [32]. In particolare, una scelta conveniente al k-esimo passo consiste nel prendere un autovalore della sottomatrice di ordine 2 in basso a destra di AkB−₁

k oppure B −₁ k Ak.

Anche per il metodo QZ si pu`o manifestare l’inconveninte della comparsa di elementi complessi anche se la matrice di partenza ha elementi reali. Per evitare il problema `e sufficiente utilizzare l’algoritmo QR con doppio shift invece dell’algoritmo QR con shift singolo.

Posto C = AB−₁

, siano a e b gli autovalori di C = cn−1n−1 cn−1n

cnn−1 cnn

.

Allora si applica il metodo del QR implicito con doppio shift utilizzando come shift a e b. In particolare valgono le relazioni:

C − aI = U1R1, C1 = R1U1+ aI, C1− bI = U2R2,

C2 = R2U2+ bI,

da cui si ottiene

M = (C − aI)(C − bI) = (U1U2) (R2R1) , che `e la fattorizzazione QR di M .

Il passo del metodo QZ quindi inizia calcolando la prima colonna di M e gli autovalori a e b che possono anche essere visti come gli zeri del problema 2 × 2 det(A − λB) = 0 con A = an−1,n−1 an−1,n an,n−1 an,n , B = bn−1,n−1 bn−1,n 0 bn,n .

Per ottenere la prima colonna di M non `e necessario calcolare interamente C, ma `e sufficiente sfruttare la struttura di A e B. Infatti vale che

c1 c2 = a1 a2 b11 b12 0 b22

−1 ,

(39)

Algoritmo QZ

dove con ci è stata indicata l’i-esima colonna di C e con ai l’i-esima colonna di A. Inoltre si può osservare anche che, poichè C è di Hessenberg superiore, la prima colonna di M è della forma m1 = (x, y, z, 0, · · · , 0)T_{, dove valgono} le seguenti relazioni.

x = (c11− a)(c11− b) + c12c21, y = c21(c11− b) + c21(c11− a), z = c21c32.

Calcolato m1, si determina una matrice di Householder H1 tale che H1m1 = γe1.

Come passo successivo si moltiplica tale matrice per A e B. In particolare si ha che A → H1A = Â1 =         ˆ a(1)₁₁ · · · aˆ(1)_1n ˆ a(1)₂₁ â(1)₂₂ · · · aˆ(1)_2n ˆ a(1)₃₁ â(1)₃₂ â(1)₃₃ · · · aˆ(1)_3n . .. . .. ... ˆ a(1)_nn−1 aˆ(1)nn         , B → H1B = ˆB1 =          ˆb(1) 11 · · · ˆb (1) 1n ˆb(1) 21 . .. ... ˆb(1) 31 ˆb (1) 32 . .. ... . .. ... ˆb(1) nn          .

Per`o si sono creati elementi non nulli in posizione (2, 1), (3, 1) e (3, 2) della matrice ˆB1. Quindi si cerca una matrice di Householder Z1 che annulli gli elementi indesiderati sulla terza riga di ˆB1, ossia tale che

ˆ A1 → ÂZ1 = Ã1           ˜ a(1)11 · · · a˜ (1) 1n ˜ a(1)₂₁ ã(1)₂₂ · · · a˜(1)_2n ˜ a(1)₃₁ ã(1)₃₂ a˜(1)₃₃ · · · a˜(1)_3n ˜ a(1)₄₁ ã(1)₄₂ . .. ... ... . .. . .. ... ˜ a(1)_nn−1 a˜(1)nn           ,

(40)

ˆ B1 → ˆBZ1 = ˜B1 =          ˜b(1) 11 · · · ˜b (1) 1n ˜b(1) 21 ˜b (1) 22 ... . .. ... . .. ... ˜b(1) nn          .

Adesso, con un’altra matrice di Householder Z2 si annulla l ’elemento in posizione (2, 1) di ˜B1 ˜ A1 → Ã1Z2 = Ã2 =           ˜ a(2)11 · · · ã (2) 1n ˜ a(2)₂₁ ã(2)₂₂ · · · ã(2)_2n ˜ a(2)₃₁ ã(2)₃₂ a˜(2)₃₃ · · · ã(2)_3n ˜ a(2)₄₁ ã(2)₄₂ . .. ... ... . .. . .. ... ˜ a(2)_nn−1 ã(2)nn           , ˜ B1 → ˜B1Z2 = ˜B2 =          ˜b(2) 11 · · · ˜b (2) 1n ˜b(2) 22 ... . .. ... . .. ... ˜b(2) nn          .

Il procedimento continua moltiplicando a destra per matrici di House-holder Hi e a sinistra per matrici di Householder Zi fino ad ottenere una coppia ( ˇA, ˇB) essenzialmente uguale alla coppia di partenza. In particolare, posto QH _{= Hn−1}_{· · · H1} _{e Z = Z1}_{· · · Zn−1} _{, si ha che ˇ}_{A = Q}H_{AZ `e in forma} di Hessenberg superiore e ˇB = QH_{BZ `e triangolare superiore.}

2.3 Condizionamento degli autovalori

In generale, prima di affrontare un problema computazionale numerico, `e conveniente studiarne il suo condizionamento, ossia misurare la sensibilit`a della soluzione rispetto a piccoli cambiamenti nei dati iniziali. A questo scopo viene introdotto un numero, detto numero di condizionamento, che ne fornisce una stima.

Nel problema agli autovalori si analizza la variazione provocata sugli autovalori da una perturbazione degli elementi della matrice.

(41)

Condizionamento degli autovalori

Teorema 2.4. ([29])Data la matrice A ∈ Cn×n_{, siano λ un autovalore} sem-plice di A e x, y ∈ Cn _{rispettivamente un autovettore destro ed uno sinistro} di A associati a λ con kxk₂ = kyk₂ = 1. Allora si ha che yH_{x 6= 0 ed inoltre} per ogni F ∈ Cn×n _{esiste nel piano complesso un intorno V dello zero e una} funzione λ(ε) : V → C, analitica, tale che

(i) λ(ε) `e un autovalore con molteplicit`a uno di A + εF , (ii) λ(0) = λ,

(iii) λ0

(0) = y_yHHF x_x ,

(iv) a meno dei termini di ordine superiore in ε vale che λ(ε) − λ = εy

H_{F x} yH_x .

Dal teorema 2.4 segue quindi che la variazione nell’autovalore semplice λ di A dovuta alla perturbazione εF `e proporzionale a ε. Inoltre il condizio-namento del problema dipende dalla quantit`a

yH_{F x} yH_x ,

che, data la matrice F , risulta tanto più grande quanto più è piccola la quantità yHx

. Per questo si definisce numero di condizionamento di un autovalore come segue.

Definizione 2.4. ([13]) Sia λ un autovalore semplice della matrice A ∈ Cn×n_{, ossia con molteplicit`a algebrica 1, e siano x, y ∈ C}n _{rispettivamente} un autovettore destro ed uno sinistro di A associati a λ con kxk₂ = kyk₂ = 1. Il numero

s(λ) = 1 |yH_x|

`e detto numero di condizionamento dell’autovalore λ.

Si pu`o notare che s(λ) `e il coseno dell’angolo tra l’autovettore destro e quello sinistro associati all’autovalore λ.

Siano λ e µ due autovalori della matrice A ∈ Rn×n _{con λ autovalore} semplice tale che

|µ − λ| ≤ εs(λ) kAk₂.

In questo caso diciamo che λ e µ sono indistinguibili nel calcolo. Per questo si considerano i cluster di autovalori semplici, definiti come segue.

(42)

Definizione 2.5. ([23]) Sia λ un autovalore semplice della matrice A ∈ Cn×n_. Si definisce cluster dell’autovalore λ come l’insieme:

C(λ) = {µ ∈ ρ(A) : |µ − λ| ≤ εs(λ) kAk₂} ,

dove ε rappresenta la precisione di macchina e ρ(A) indica lo spettro della matrice A, ossia l’insieme di tutti i suoi autovalori.

Lo studio del condizionamento nel caso di problema generalizzato agli autovalori consiste nuovamente nell’analizzare la variazione provocata sugli autovalori dalla perturbazione degli elementi della coppia di matrici (A, B). In particolare si definisce il numero di condizionamento di un autovalore generalizzato come segue.

Definizione 2.6. ([16]) Sia λ un autovalore generalizzato semplice della coppia (A, B), con A, B ∈ Cn×n_{, e siano x, y ∈ C}n _{rispettivamente un} au-tovettore destro ed uno sinistro di (A, B) associati a λ con kxk₂ = kyk₂ = 1. Il numero

s(λ) = 1

|yH_Bx|

`e detto numero di condizionamento dell’autovalore generalizzato λ. In analogo al caso standard si ha

Definizione 2.7. ([23]) Sia λ un autovalore generalizzato della coppia (A, B) con A, B ∈ Cn×n_{. Si definisce cluster dell’autovalore generalizzato λ come} l’insieme:

Cg(λ) = {µ ∈ ρ(A, B) : |µ − λ| ≤ εs(λ) kA, Bk₂} ,

dove ε rappresenta la precisione di macchina, ρ(A, B) indica lo spettro della coppia (A, B), ossia l’insieme di tutti gli autovalori generalizzati e kA, Bk₂ `e la norma della matrice ottenuta giustapponendo A e B.

2.4 Decomposizione agli autovalori singolari

Uno strumento potente per la determinazione di sottospazi invarianti asso-ciati all’autovalore λ di molteplicit`a k > 1 della matrice A `e costituito dalla decomposizione ai valori singolari (SVD).

Teorema 2.5. ([2]) Sia A ∈ Cm×n_{. Allora esistono una matrice unitaria} U ∈ Cm×m _{e una matrice unitaria V ∈ C}n×n _{tali che}

(43)

Decomposizione agli autovalori singolari

dove la matrice Σ ∈ Rm×n _{ha elementi σij} _{nulli per i 6= j e per i = j ha} elementi σii= σi, con

σ1 ≥ σ2 ≥ . . . ≥ σp ≥ 0 e

p = min{m, n}.

Definizione 2.8. ([2]) Data una matrice A ∈ Cm×n_{, la decomposizione (2.15)} `e detta decomposizione ai valori singolari di A, mentre i valori σi, per i = 1, . . . , p sono detti valori singolari di A. Inoltre, indicate con ui per i = 1, . . . , m e vj per j = 1, . . . , n rispettivamente le colonne di U e V , i vettori ui e vj sono detti ripettivamente vettori singolari sinistri e vettori singolari destri di A.

Si osserva che le matrici U e V non sono univocamente determinate dalla decomposizione ai valori singolari di A.

Teorema 2.6. ([2]) Sia A ∈ Cm×n _{e sia} A = U ΣVH la sua decomposizione ai valori singolari, dove

σ1 ≥ σ2 ≥ . . . ≥ σk = σk+1 = . . . = σp = 0. Allora valgono le seguenti propriet`a

1. A = UkΣkVH k = k X i=1 σiuivH i , dove

• Uk ∈ Cm×k _{`e la matrice le cui colonne sono u1, . . . , uk,} • Vk ∈ Cn×k _{`e la matrice le cui colonne sono v1, . . . , vk,}

• Σk ∈ Rk×k _{`e la matrice diagonale i cui elementi principali sono} σ1, . . . , σk.

2. L’immagine di A `e generata dai vettori u1, . . . , uk, e quindi rango(A) = k.

Il Teorema 2.6 viene applicato al calcolo dei sottospazi invarianti associati ad un autovalore λ della matrice A. Infatti la molteplicit`a di λ e una base di ker(A − λI) possono essere ottenuti mediante il calcolo della decomposizione ai valori singolari di (A − λI). Questo continua a valere anche nel caso in cui λ sia un autovalore generalizzato della coppia (A, E): la sua molteplicit`a geo-metrica ed una base di ker(A − λE) si ottengono mediante la decomposizione ai valori singolari della matrice (A − λE).

(44)

(45)

Capitolo 3

Risultante di Bezout

3.1 Introduzione

Uno strumento importante nello studio delle soluzioni di sistemi di equazioni, nella teoria della stabilit`a e nella teoria classica dell’eliminazione per sistemi di equazioni polinomiali `e dato dal concetto di risultante e matrice risultante introdotta di seguito [21, 19].

Definizione 3.1. ([14]) Dati due polinomi p(x) e q(x) in Πnsi dice risultante tra p(x) e q(x) una funzione dei coefficienti di p e q che si annulla se e solo se i due polinomi p(x) e q(x) hanno zeri in comune.

Nella letteratura sono conosciuti diversi risultanti, dovuti a Bezout, Cay-ley e Sylvester. In questa tesi verr`a presa in considerazione la formulazione di Cayley della risultante di Bezout [26].

Definizione 3.2. ([14]) Siano p(x) e q(x) due polinomi in Πn. Il polinomio in due variabili

P (z, w) = p(z)q(w) − p(w)q(z) z − w

`e chiamato risultante in forma di Bezout tra p(x) e q(x).

Nel corso di questo capitolo verranno descritte le formulazioni matriciali del risultante di Bezout prima applicata a polinomi in base di potenze e in seguito applicata a polinomi in base di Bernstein.

(46)

3.2 Risultante di Bezout in base di potenze

Siano p(x) ∈ Πn e q(x) ∈ Πm p(x) = n X i=0 pixi e q(x) = m X i=0 qixi, (3.1) con pn 6= 0 e qm 6= 0. Si ha che P (z, w) = p(z)q(w) − p(w)q(z) z − w = k−1 X i,j=0 bi+1j+1zi_wj ₌ (3.2) = 1 w · · · wk−1 _{Bp(p, q)}      1 z .. . zk−1      ,

dove Bp(p, q) = (bij) ∈ Rn×n _{e k = max (deg(p(x)), deg(q(x))) = max(n, m).} Definizione 3.3. ([14]) La matrice Bp(p, q) = (bij) definita in (3.2) `e chia-mata matrice Bezoutiana in base di potenze. Il determinante di tale matrice `e noto con il nome di Bezoutiano.

Il pedice p indica che Bp(p, q) `e riferita alla base di potenze. In seguito indicheremo con Bb(p, q) la matrice Bezoutiana nella base di Bernstein.

La relazione tra gli elementi bij e i coefficienti dei polinomi p(x) e q(x) `e espressa nel seguente teorema.

Teorema 3.1. ([14]) Gli elementi della matrice Bezoutiana Bp(p, q) soddis-fano le relazioni seguenti.

 



bi1 = piq0− qip0 per 1 ≤ i ≤ k,

bij+1 = (piqj − pjqi) + bi+1j per 1 ≤ i, j ≤ k − 1,

bnj+1 = pnqj − pjqn per 1 ≤ k − 1.

Inoltre Bp(p, q) `e una matrice simmetrica, ossia bij = bji per 1 ≤ i, j ≤ k. Dimostrazione: Per la regola del prodotto tra due polinomi si ha che

p(z)q(w) − p(w)q(z) = k X

i,j=0

(47)

Risultante di Bezout in base di potenze

dove si pone pi = 0 per i = k + 1, . . . , n e qj = 0 per j = k + 1, . . . , m. D’altra parte da (3.2) segue che

p(z)q(w) − p(w)q(z) = (z − w) k−1 X

i,j=0

bi+1j+1ziwj. (3.4) Allora, eguagliando (3.3) e (3.4), si ottiene che

(z − w) k−1 X i,j=0 bi+1j+1zi_wj ₌ k X i,j=0 (piqj− pjqi)zi_wj_, ossia k−1 X i,j=0 bi+1j+1zi+1wj ₋ n−1 X i,j=0 bi+1j+1zi_wj+1₌ k X i,j=0 (piqj − pjqi)zi_wj_. _(3.5) Considerando entrambi i membri di (3.5) come polinomi nell’incognita w con coefficienti dati da polinomi nell’incognita z, si pu`o scrivere:

k X i=1 bi1zi₊ k−1 X j=1 k X i=1 bij+1zi₋ k−1 X i=0 bi+1jzj ! wj₋ k−1 X i=0 bi+1kzi ! wk ₌ = k X j=0 k X i=0 (piqj− pjqi)zi ! wj da cui, eguagliando i coefficienti, si ha che

• Per j = 0: k X i=1 bi1zi ₌ k X i=0 (piq0− p0qi)zi_; _(3.6) • Per 1 ≤ j ≤ k − 1: k X i=1 bij+1zi₋ k−1 X i=0 bi+1jzj ₌ k X i=0 (piqj− pjqi)zi_; _(3.7) • Per j = k: − k−1 X i=0 bi+1kzi ₌ k X i=0 (piqk− pkqi)zi_. _(3.8)

(48)

Da (3.6), eguagliando i coefficienti, si ottiene • Per 1 ≤ i ≤ k:

bi1 = piq0− p0qi. Da (3.7), per 1 ≤ j ≤ k − 1 si ha

• Per i = 0:

−b1j = p0qj− pjq0; • Per 1 ≤ i ≤ k − 1:

bij+1 = (piqj − pjqi) + bi+1j; • Per i = k:

bkj+1 = pkqj − pjqk. Infine da (3.8) deriva che

• Per 0 ≤ i ≤ k − 1:

−bi+1k = piqk− pkqi; La simmetria segue da P (z, w) = P (w, z).

2 Esempio 3.1. Si consideri i polinomi

p(x) = 1 + 2x + 4x2− x3+ 3x5, q(x) = 4 + x − 2x2+ 3x5+ x6. Allora si ha che Bp(p, q) =         7 18 −4 0 9 −1 18 4 −1 9 −4 −2 −4 −1 11 −4 −20 −4 0 9 −4 −20 −1 1 9 −4 −20 −1 1 0 −1 −2 −4 1 0 −3         .

Come si pu`o notare la matrice risulta simmetrica.

Dalla definizione 3.2 segue immediatamente un’interessante propriet`a del-la matrice Bezoutiana che `e descritta nel seguente teorema.

(49)

Risultante di Bezout in base di potenze

Teorema 3.2. ([14]) Siano p(x) e q(x) due polinomi in base di potenze rispettivamente di grado n e m. Allora la matrice Bezoutiana `e tale che

Bp(p, q) = −Bp(q, p). Esempio 3.2. Si considerino i polinomi

p(x) = 1 + x − 2x2 − x3 + x4+ 3x5+ x6, q(x) = 1 + 2x + 2x2− x3+ 3x5+ x6+ 2x7. Allora si ha che Bp(p, q) =           1 4 0 −1 0 0 2 4 6 0 −2 −3 1 2 0 0 2 −5 −11 −2 −4 −1 −2 −5 −10 −2 −4 −2 0 −3 −11 −2 −1 −1 2 0 1 −2 −4 −1 2 6 2 2 −4 −2 2 6 2           , Bp(q, p) =           −1 −4 0 1 0 0 −2 −4 −6 0 2 3 −1 −2 0 0 −2 5 11 2 4 1 2 5 10 2 4 2 0 3 11 2 1 1 −2 0 −1 2 4 1 −2 −6 −2 −2 4 2 −2 −6 −2           .

Si nota immediatamente che vale la propriet`a espressa nel Teorema 3.2. Il risultato che segue mostra che il Bezoutiano verifica la Definizione 3.1 e quindi `e effettivamente un risultante.

Teorema 3.3. ([14]) Siano dati due polinomi non nulli p(x) e q(x) rispetti-vamente di grado n e m. Condizione necessaria e sufficiente affinch`e p(x) e q(x) abbiano radici comuni `e che il Bezoutiano si annulli.

Dimostrazione: Supponiamo che n ≥ m e che il polinomio p(z) abbia radici semplici. Allora

p(z) = pnY i=1

(z − λi) con λi 6= λj per i 6= j.

Si ha

(50)

e

P (λi, λi) = lim h>0

p(λi+ h)q(λi) − p(λi)q(λi+ h)

h =

= lim h>0

p(λi+ h)q(λi) − p(λi)q(λi) + p(λi)q(λi) − p(λi)q(λi+ h)

h = = lim h>0p 0 (λi)q(λi) − p(λi)q0 (λi) = = p0 (λi)q(λi).

Quest’ultima relazione pu`o essere riscritta in forma matriciale

V Bp(p, q)VT =      1 λ1 · · · λn−1₁ ... ... ... ... 1 λn · · · λn−1n      Bp(p, q)      1 · · · 1 λ1 λn−1 ... ... λn−1₁ · · · λn−1 n      = =      p0 (λ1)q(λ1) . .. . .. p0 (λn)q(λn)      .

Essendo V una matrice di Vandermonde, `e invertibie. Quindi si ottiene che Bp(p, q) `e invertibile se e solo se q(λj) 6= 0 per j = 1, . . . , n.

2 Esempio 3.3. Si consideri i seguenti polinomi

p(x) = −4 + 8x − 5x2_{+ x}3 _{= (x − 2)}2_{(x − 1)} q(x) = −24 + 44x − 30x2+ 9x3− x4 = (x − 2)3(3 − x) Allora Bp(p, q) =     −16 0 12 −4 0 32 −32 8 12 −32 23 −5 −4 8 −5 1     ,

da cui segue che det(Bp(p, q)) = 0.

Dalla dimostrazione del Teorema 3.3 segue che se x0`e una radice comune di p(x) e q(x) allora      1 x0 .. . xk−1₀     