Algoritmi Veloci per la Risoluzione Numerica di Sistemi Lineari Strutturati

Testo completo

(1)` DEGLI STUDI DI UNIVERSITA ROMA “TOR VERGATA”. ` DI SCIENZE M.F.N. FACOLTA Corso di Laurea in Matematica. ALGORITMI VELOCI PER LA RISOLUZIONE NUMERICA DI SISTEMI LINEARI STRUTTURATI. Relatore Prof. Giuseppe Rodriguez. ANNO ACCADEMICO 1998–1999. Candidato Emiliano Reali (SM960).

(2) Ai mie genitori sostegno della mia brama di sapere.

(3) Indice 1. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 4 5 7 9 10. Matrici strutturate classiche 2.1 Matrici di Toeplitz . . . . . . . 2.1.1 Risultati numerici . . . . 2.2 Matrici di Vandermonde . . . . 2.2.1 Risultati numerici . . . . 2.3 Altre classi di matrici strutturate 2.3.1 Matrici di Cauchy . . . 2.3.2 Matrici di Hankel . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. 11 11 17 22 27 30 30 31. 3. Problemi che conducono a sistemi lineari strutturati 3.1 Risoluzione di equazioni differenziali . . . . . . . . . . . . . . .

(4) . . . . 3.2 Approssimazione polinomiale ai minimi quadrati in. 33 33 35. 4. Struttura di spostamento 4.1 Rango di spostamento . . . . . . . . . . . . . . . . . . . 4.2 Struttura di spostamento . . . . . . . . . . . . . . . . . 4.3 L’algoritmo di Schur . . . . . . . . . . . . . . . . . . . 4.4 Fattorizzazione veloce e stabile di matrici di Cauchy . . 4.4.1 Risultati numerici . . . . . . . . . . . . . . . . . 4.5 Conversione di struttura . . . . . . . . . . . . . . . . . . 4.5.1 Conversione da Toeplitz-like a Cauchy-like . . . 4.5.2 Conversione da Vandermonde-like a Cauchy-like 4.5.3 Risultati numerici . . . . . . . . . . . . . . . . .. 38 38 44 48 52 57 62 63 66 67. 2. Introduzione 1.1 Definizioni preliminari 1.2 Sistemi lineari . . . . . 1.3 Matrici strutturate . . . 1.4 Note Tecniche . . . . .. . . . .. . . . .. . . . .. . . . .. 3. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . ..

(5) Capitolo 1 Introduzione Questa tesi ha come oggetto lo studio delle proprietà di un’ampia classe di matrici strutturate. La nozione di “struttura di spostamento” (displacement structure ), introdotta da Kailath [12], consente infatti di definire classi molto generali di matrici strutturate, che comprendono, come casi particolari, molte matrici strutturate classiche, quali le matrici di Vandermonde, Toeplitz, Cauchy, Hankel, etc. All’interno di tali classi e` possibile individuare importanti quantità invarianti, e costruire algoritmi di fattorizzazione, utilizzabili quindi per la risoluzione numerica di sistemi lineari, aventi complessità computazionale dell’ordine di [6]. Alcune ricerche più recenti, inoltre, sono state incentrate sulla costruzione di algoritmi caratterizzati da una maggiore stabilità numerica [3] e sullo studio dell’influenza del contenuto informativo derivante dalla struttura sul numero di condizionamento associato ad una matrice [4]. Questi studi hanno dato origine ad un importante filone di ricerca che ha coinvolto ricercatori di prim’ordine operanti nel settore dell’Algebra Lineare e dell’Analisi Numerica. Il piano della tesi e` il seguente: nel presente capitolo verranno introdotti i temi trattati nella tesi e verranno date alcune definizioni preliminari. Nel Capitolo 2 fisseremo l’attenzione sulle matrici strutturate più note e presenteremo alcuni algoritmi veloci per la risoluzione di sistemi lineari caratterizzati da alcune di queste classi di matrici. Nel Capitolo 3 saranno presentati alcuni problemi in cui intervengono matrici strutturate. Infine nel Capitolo 4 parleremo della struttura di spostamento, che e` materia di studi piuttosto recente e che riveste grande importanza sia teorica che applicativa. Questa teoria, attraverso la definizione di un opportuno operatore, permette di generalizzare il concetto di struttura e di individuare alcune importanti quan4.

(6) tità invarianti. Sfruttando le proprietà dell’operatore di spostamento, verrà quindi di Schur con pivoting studiata una versione dell’algoritmo di fattorizzazione di colonna, ottimizzato per matrici Cauchy-like. Infine verranno illustrati degli algoritmi che consentono di trasformare alcuni tipi di matrici strutturate in matrici Cauchy-like. Tutti gli algoritmi studiati sono stati implementati e sono stati confrontati sia tra loro che col classico metodo di triangolarizzazione di Gauss, mediante una sperimentazione numerica tesa a verificare la loro performance.. 1.1. Definizioni preliminari. Definizione 1.1 Fissata una norma matriciale, si definisce numero di condizionamento di un sistema lineare la quantità. !"# . essendo A la matrice dei coefficienti del sistema. Il numero di condizionamento di un problema quantifica la sensibilità del risultato rispetto agli errori sui dati. Specificatamente si parlerà di problema malcondizionato se per piccole perturbazioni sui dati si possono avere grandi perturbazioni sui risultati. Viceversa un problema e` ben condizionato se per piccole perturbazioni sui dati si hanno piccole perturbazioni sui risultati. Un esempio chiarificatore di questo concetto e` dato dal seguente sistema. $ %&('*),+ .'*)(/0+ 21. (1.1). con /43.5 . Questo sistema dal punto di vista matriciale si può scrivere nella forma 768:9 con. : ;< -. -. ) )7/. =>. . ;<. -. =>8?. 1. Consideriamo una piccola perturbazione sui dati ed in particolare. - 1@1@1@1A/ " .. 1 D@DED@D@D / C e osserviamo cosa succede ai risultati. Nel caso di / / " $ % & ' F-G1IHKJL+ F-G1 H B. 5. abbiamo.

(7) e con /. / . abbiamo. $ % & ' ) -G1EH0JC+ ) G- 1 H . si ha cioè un errore dell’ordine di -#1 H sulla soluzione a fronte di una variazione di -G1 H sui dati. Infatti in entrambi i casi per il condizionamento si ha il valore. :MN@-G1 H relativamente alla norma O . Le informazioni sul condizionamento di un sistema lineare sono cruciali, in quanto operando su un calcolatore digitale tutti i numeri reali utilizzati sono affetti da un errore relativo dell’ordine della precisione di macchina (circa -G1 "P , se si utilizzano variabili in doppia precisione). Inoltre, nelle applicazioni i dati sono spesso perturbati in modo molto più consistente a causa di errori sperimentali e/o di misura. La successione delle operazioni che porta alla soluzione di un problema e` detta algoritmo di risoluzione. Spesso per uno stesso problema esistono diversi algoritmi e quindi e` cruciale sapere quale degli eventuali candidati risulta il migliore. Per questo ultimo concetto si devono fare una serie di distinzioni, infatti un algoritmo può risultare più veloce dal punto di vista del tempo impiegato da un elaboratore per eseguirlo, ma non essere sufficientemente accurato. Definizione 1.2 Definiremo stabilita` di un algoritmo la sensibiltà dell’algoritmo stesso rispetto agli errori sulle operazioni. La stabilità e` una proprietà intrinseca di un algoritmo e algoritmi differenti risulteranno più o meno stabili. Definizione 1.3 Definiremo complessità computazionale di un algoritmo il numero di operazioni aritmetiche che sono necessarie per il calcolo effettivo della soluzione. Il termine complessità avrà prevalentemente un significato aritmetico come l’intuizione della parola lascia intendere. Nella sua valutazione la complessità di un algoritmo e` sempre legata alla dimensione del problema in esame. Se quest’ultima e` , la funzione di che rappresenta la sua complessità sarà spesso considerata per il suo comportamento asintotico, cioè al crescere indefinito di . Per chiarezza con Q RTSUWVK XWVK Q ZY[1\ si intenderà il fatto che la funzione Q “non cresce più rapidamente di VK ”, cioè che esiste una costante c tale che Q N].^_VK con l’eccezione di un insieme (eventualmente vuoto) di 6.

(8) valori non negativi di . Il simbolo S*`-G denoterà una funzione delimitata, al crescere di , da una costante. Per unità di misura della complessità di un algoritmo _abc si intenderà una singola operazione aritmetica WJ ) , spesso indicata con flop (floating point operation ). La complessità di calcolo può essere riguardata principalmente da due punti di vista: la sintesi e l’analisi di algoritmi. La sintesi consiste nella costruzione di algoritmi sempre più efficienti e veloci; l’analisi consiste invece nello studio di limiti inferiori della complessità di un problema e riguarda più direttamente il grado di difficoltà intrinseca della sua risoluzione.. 1.2. Sistemi lineari. La risoluzione dei sistemi lineari e` il problema più diffuso nelle applicazioni della matematica e completamente noto dal punto di vista teorico. L’Algebra Lineare fornisce condizioni per l’esistenza e l’unicità della soluzione e algoritmi per il suo calcolo effettivo. Il problema di alcuni algoritmi classici e` dato dall’elevato numero di operazioni aritmetiche richiesto per la loro applicazione. E` facile verificare ad esempio che la formula di Cramer richiede un numero di operazioni dell’ordine di JL-de se e` la dimensione del sistema. Tale complessità computazionale rende di fatto non risolubili sistemi di dimensioni moderatamente elevate anche sui computer più veloci attualmente disponibili. Un sistema di equazioni lineari può essere scritto nella forma. h h h g hXi f @ j ' ". k. F- . ?#?#?. . o, in notazione compatta,. l6mC9 @j f dove n e` una matrice po8 e 6 9 3q5 h. . Gli algoritmi numerici per la risoluzione dei sistemi lineari sono basati sulla fattorizzazione della matrice , contenente i coefficienti del sistema, nel prodotto di 2 o più matrici aventi una forma più semplice rispetto alla matrice di partenza. E` necessario inoltre che la fattorizzazione e la risoluzione dei sistemi vengano eseguiti con algoritmi numericamente stabili. L’algoritmo di Gauss, ad esempio, fornisce una fattorizzazione del tipo. C . 7.

(9) jsj. dove e` una matrice triangolare inferiore con elementi diagonali r .- , e matrice triangolare superiore. I sistemi lineari risultanti sono quindi. . una. $ 9 %& Kt : 6p t. che si possono risolvere rispettivamente mediante gli algoritmi di forward e backward substitution. Questo procedimento e` efficace se il costo computazionale della fattorizzazione e` contenuto e se i due sistemi lineari risultanti, come in questo caso, sono in una forma pi` u u semplice di quello di partenza. Per la fattorizzazione * S " u la complessità e` e per la soluzione dei due sistemi triangolari e` S* . La fattorizzazione consente anche di effettuare il calcolo del determinante e della matrice inversa. Infatti poiché la matrice ha tutti 1 sulla diagonale principale, il determinante di si riduce al prodotto degli elementi della diagonale prin cipale di . Invece, riguardo alla matrice inversa, se pensiamo ad " composta ?w?#? di vettori colonna. !" v " xv f ?#?w? ?#?#? si deve avere v " xv f z y "

(10) y f y|{ ?#?w? ? di 5 f dove gli sono i vettori colonna della base canonica v}{ y|{ ~ .- . e quindi. u. Questi sistemi lineari possono essere risolti con complessità SU , effettuando la fattorizzazione della matrice e risolvendo OI sistemi triangolari. L’algoritmo di Gauss applicato ad una qualsiasi matrice non singolare potrebbe bloccarsi nel caso in cui trovi un pivot, cioè un elemento diagonale, uguale a zero. Questo inconveniente e` superabile con l’introduzione del pivoting parziale o di colonna. In pratica questa modifica dell’algoritmo di Gauss prevede che ~ ~ al passo si cerchi l’elemento di massimo modulo nella colonna -esima e si ~ scambi di posto la relativa riga con la riga . Questa variante migliora l’algoritmo di Gauss rendendolo applicabile a qualsiasi matrice non singolare e più stabile numericamente. Dal punto di vista matriciale la fattorizzazione con pivoting si scrive. C . e conduce alla risoluzione dei due sistemi triangolari. $ % & Kt 9 68 t 8. ?.

(11) Quando l’algoritmo di Gauss viene applicato col pivoting di colonna, si può dare un limite superiore per la crescita del numero di condizionamento. ]LM f " . (1.2). dove con indichiamo il numero di condizionamento calcolato con la norma infinito. Anche se questo limite non viene raggiunto nella maggioranza dei casi, esso rende comunque sconsigliabile l’applicazione dell’algoritmo di Gauss a matrici malcondizionate.. 1.3. Matrici strutturate. In molti problemi si presentano sistemi lineari la cui matrice dei coefficienti e` dotata di una particolare struttura, cioè dipende da un numero di parametri inferiore ad . Definizione 1.4 Diremo che una matrice e` strutturata se dipende da / n parametri con / indipendente da n. La struttura di una matrice consente quindi un enorme guadagno nell’occupazione di h memoria, soprattutto per matrici k k di grandi dimensioni. Un semplice esempio di matrici strutturate sono le matrici a banda, i cui ele@j sono nulli per )m* " e )p , essendo " e gli interi che menti indicano le ampiezze di banda. Definizione 1.5 Diremo che un algoritmo per la risoluzione di un sistema lineare, o la fattorizzazione di una matrice, e` “veloce” se ha una complessità SU , con . Alcuni algoritmi veloci classici non risultano numericamente stabili, in quanto non prevedono l’uso del pivoting. L’applicazione del pivoting risulta spesso impossibile in quanto può distruggere la struttura di una matrice. In taluni casi la struttura di una matrice risulta nascosta, pur essendo comunque presente. Ad esempio, in una matrice a banda le cui righe e colonne abbiano subito una permutazione risulta visibile ad un primo esame solo la sparsità, ma non la struttura. Vediamo anche un’altro esempio non banale. Sappiamo che una matrice di Toeplitz non singolare po8 , con i minori principali diversi da zero, si inverte con un numero di operazioni aritmetiche dell’ordine di. che, comparau te all’ordine di necessarie per una matrice generica, rappresentano un enorme vantaggio soprattutto per n abbastanza grande. Ma se sappiamo in qualche modo, che una matrice non di Toeplitz e` l’inversa di qualche matrice di Toeplitz, allora si 9.

(12) mostra che considerando questo aspetto e` possibile invertire la matrice non Toe plitz con S* moltiplicazioni, anche se la struttura non e` di fatto presente. Ad esempio se T e` la matrice di Toeplitz. ;. M . M M < O - O . O . = - O > . M. la sua inversa e`. ". G- 1. ;. . ) -#1 ) 1. ) 1 < -. 1 ) -G1 ) . -. = . 1 > ) . che non e` di Toeplitz. Risulterebbe utile, in casi come questo, un metodo per rilevare la presenza della struttura, e degli algoritmi che traggano vantaggio da essa.. 1.4. Note Tecniche. Gli algoritmi studiati in questa tesi sono stati implementati usando l’ambiente di calcolo e visualizzazione scientifica Matlab [14]. I calcoli sono stati effettuati su un elaboratore Pentium 166 Mhz. Alcune elaborazioni su matrici di grandi dimensione sono state effettuate, sempre in Matlab, sulla workstation Alpha-server 1000 5/266 Mhz (axdid.mat.uniroma2.it) dell’Università di Roma “Tor Vergata”. Per la scrittura della presente tesi e` stato usato il linguaggio di composizione testi LATEX. I grafici presenti nella tesi sono stati prodotti con Matlab a partire dai dati sperimentali e sono stati esportati in formato Encapsulated Postscript (EPS) per essere incorporati nel testo LATEX.. 10.

(13) Capitolo 2 Matrici strutturate classiche 2.1. Matrici di Toeplitz ?#?#?. ?#?#?. . f\If. h hxi. h. h. 3.5 si dice di Toeplitz se esistono Definizione 2.1 Una matrice j j zzz j j scalari f# " f " tali che T = ?#?# ? " f con = ? # # ? ? G f " ; " " " fG ? .. " . . . . > .. < ... ?w. ?#. .? . . . " . f " f " #? ?#? h f " Se la matrice T e` simmetrica, allora dipende da scalari j = t ?#?#? = # ? # ? ? f " " ; " " f ? . " . . . .. > .. < ... ?#. ?#. .? . . . " . f " f " . OI ) -. (2.1). tali che . j. h. (2.2). Le matrici di Toeplitz sono un importante esempio di matrici strutturate. Va subito evidenziato come per queste matrici sia limitata l’occupazione di memoria. Infatti, se per una matrice qualsiasi di ordine le celle di memoria da occupare sono , per una Toeplitz esse sono appunto OI ) - e nel caso di una matrice 11.

(14) di Toeplitz simmetrica. Queste semplici osservazioni, unite alla presenza di queste matrici in numerosi problemi applicativi, giustificano lo studio sistematico di algoritmi per matrici di Toeplitz. Esistono degli algoritmi ormai classici per questa classe di matrici. Nel caso delle matrici di Toeplitz simmetriche definite positive i più ?#noti ?w? sono l’algoritmo - D 1 ) e quello di Levinson ( - D M\¡ ). di Durbin ( h hxi f ¢ tali che L’algoritmo di Durbin, dati i numeri reali ¢# - ¢ " j j z z z t f ¢ " f e` definita positiva, calcola ?w?#? 3£5 tale ? che. ¤t ) ¢". f ¦¥ ¢. Questa equazione e` detta di Yule-Walker ed e` legata a problemi di predizione lineare. Supporre ¢w F- non e` restrittivo in quanto un sistema lineare caratterizzato da una generica matrice di Toeplitz definita positiva del tipo (2.2) può essere ricondotto in questa forma dividendo la matrice dei coefficienti ed il termine noto ?#?#? per l’elemento diagonale . ~ L’algoritmo risolve ricorsivamente, per ?w?# ? , il sistema di Yule~ Walker di ordine. §{t )l¨ { ) ¢". dove. = GG ¢ { " { ? .. . ¢" ¢ . . . . . . . . ¢ . > .. .. .. . . ¢" . { { " ¢ GG ¢ " -. ; . §{ <. ¢. { ¦ ¥ ¢. ¢. ¢" -. Osserviamo che una matrice di Toeplitz e` persimmetrica [1].. f|If. Definizione 2.2 Una matrice 3©5 si dice persimmetrica se e` simmetrica rispetto all’antidiagonale, cioè rispetto alla diagonale che unisce gli elementi dal posto - al posto -G . In sostanza gli elementih di una matrice persimmetrica la relazione ?w?#verificano ? ? h k. @j f. " f j " . F- . . Introduciamo la matrice di scambio ª f di ordine n, che si ottiene dalla matrice identità invertendo l’ordine delle righe. Questa matrice e` idempotente in quanto. 12.

(15) ª f ª f ¬«. . E` immediato verificare che una matrice. se. ª f ª f :l¥. . ?. e` persimmetrica se e solo. Una conseguenza di questa relazione e` che l’inversa di una matrice persimmetrica e` a sua volta persimmetrica. Inoltre se una matrice e` sia simmetrica che persimmetrica (ossia centrosimmetrica ), come ? nel nostro caso, si ha. ª f ª f. ~. Supponiamo di aver risolto il sistema di Yule-Walker di ordine . Mostriamo ~ che il sistema di Yule-Walker di ordine JC-. { ¨ { >= ª ;< { ¨ ¥{ ª §{. si risolve con S*. ~ . =>. ;<® /. ) ;<. => ¨{. { ¢ ". operazioni. Osserviamo innanzitutto che. { " )l¨ { )¯/ ª { ¨ { t )°/ { " ª { ¨ { ? e / ) ¢ { " )°¨ ¥{ ª { { " { " { {± { " Poiché e` persimmetrica, abbiamo ª ª e? di conseguenza t )¯/ ª { { " ¨ { t J / ª {±t Ora, se inseriamo nell’espressione di / il valore della trovato, otteniamo ? { J ¨ ¥{ {±t / ) ¢ { " )(¨ ¥{ ª { t J / ª {±t ) ¢ -" J { t ª ¨#¥ Di questa espressione bisogna notare che il denominatore e` positivo. Infatti, ponendo. ². ;<. « ª 1. {_t =>. -. risulta. ² ¥ ³ { ² ". ;<. ³{ 1 13. 1. -J ¨ { ¥ t. =>m?.

(16) ³{. ². Da questa relazione, essendo " definita positiva e non singolare, segue la t { J ¥ ¨ . positività del numero ~ In questo modo abbiamo illustrato il passo -esimo dell’algoritmo proposto da Durbin. Questo procedimento risolve ricorsivamente il sistema di Yule-Walker. per. ~ .- . ?w?#? . ³{_t´ { µ )l¨ {. come segue. t ´"µ l ) ¨ " ?w?#? ~ ) for F¶ { F-J ¨ ¥{ t ´ { µ { µ {/ ) ¢ { " J ¶ ¨ ¥{{ ª ±{ t ´ ´ { µ t ´ { µ J / { ª {±t ´ { µ ´ { µ => { µ t ´ " ;< / { end. t t ´f µ che conduce a determinare . Procedendo cos`ı si richiedono flops. E` ¶ { possibile tuttavia ridurre la complessità usando un’altra espressione per ¶ { -J ¨ ¥{ t´ { µ t ´ { " µ J / { { t ´ { " µ => " ª " {U¸ ;< -J4· ¨ ¥{ ¢ " / { " { µ { µ `-J ¨ ¥{ " t´ " }J / { " ¨ ¥{ " ª { " t´ " J ¢ { ¶ { " J / { " ) ¶ ? { " / { " `- )°/ { " ¶ { " Questo algoritmo ha una complessità di S* e se usiamo la seguente implementazione in ambiente Matlab function y=dur(r) n=size(r,1); y=zeros(n,1); a=zeros(n,1); y(1)=-r(1); b=1; a=-r(1); for k=1:n-1 14.

(17) b=(1-aˆ2)*b; a=-(r(k+1)+(r(k:-1:1)’*y(1:k)))/b; z(1:k)=y(1:k)+a*y(k:-1:1); y(1:k+1)=[z(1:k);a]; end. . eseguiamo OI operazioni o flops. L’algoritmo di Levinson simme?#?#? consente la risoluzioneh di un sistema lineare 9 8 3 5 f ei trico definito positivo dotato di un termine noto arbitrario. Infatti, dati j \ f I f ¢ f " tali chef ¹ ¢@ 385 numeri reali ¢w ¬- ¢ " e` definita positiva, 6 C 6 º 9 L 3 5 l’algoritmo di Levinson calcola tale che . Supponiamo di aver ~ risolto il sistema di ordine ?#?#?. dove. ³{. §{ 6»:9 { . ". . { ¥ . (2.3). e` la matrice introdotta precedentemente, e di voler risolvere il sistema. =>8? { ¨ { >= v¼ => 9 { ª <; ;< ;<. { {¨ ¥ ª { " ?w?#? ¢ " ¢ { ¥ come prima. Assumiamo anche che ~ ³{. {. Qui ¨ sistema di Yule-Walker di ordine. (2.4). la soluzione del. §{±t )l¨ { ¼. sia disponibile. Dalla relazione. ³{_v J ~. { { {I ª ¨ L9. corrispondente alle prime righe del sistema 2.4, sfruttando la persimmetria della §{ ¼ ¼ matrice , si ottiene che ¼. v { " 9 { ) e quindi. { { ª ¨ ½6 ). { " { ¨ { L6*J ª. ¼. . . . { . { . { . { " )(¨ ¥ { " )(¨ ¥ { " )(¨ ¥ -J ¨#¥{. 15. ª. {±v. { ª 6 ?) { ª 6 t. ¼ ¨ ¥{ t. ª. {±t.

(18) ~ . Resta cos`ı mostrato che per passare da (2.3) a (2.4) e` sufficiente eseguire SU operazioni. In conclusione un metodo efficiente di risoluzione per il sistema 6» 9 si ottiene risolvendo in parallelo i due sistemi. §{ 6 ´ { µ C 9 {. per. e. -!] ~ ] . §{±t´ { µ )7¨ {. . Questi sono i passi dell’algoritmo di Levinson. Come per l’algoritmo di Durbin, la complessità asintotica e` S* do la seguente implementazione Matlab. . Utilizzan-. function x=lev(t,b) if length(t)==1 x = b/t; return end r=t(2:end)/t(1); b=b/t(1); n=size(t,1); x=zeros(n,1); y=zeros(n,1); u=zeros(n,1); a=zeros(n,1); y(1)=-r(1); x(1)=b(1); beta=1; a=-r(1); for k=1:n-1 beta=(1-aˆ2)*beta; u=(b(k+1)-(r(1:k)’*x(k:-1:1)))/beta; x(1:k+1)=[x(1:k)+u*y(k:-1:1);u]; if k<n-1 a=-(r(k+1)+(r(1:k)’*y(k:-1:1)))/beta; z(1:k)=y(1:k)+a*y(k:-1:1); y(1:k+1)=[z(1:k);a]; end end. . vengono eseguite esattamente M flops. Tale implementazione e` applicabile a matrici di Toeplitz simmetriche definite positive?#?wcon qualsiasi. ?#?w? ? elemento ?#diagonale ?#? Si può utilizzare una ricorsione simile anche per il caso non simmetrico. Sup f f f , sia necessaponiamo che, dati gli scalari ¢ " ¢ " , " " e " 16.

(19) rio risolvere il sistema lineare. < ?#?#?. . della forma. = = G G ' f ¢" ¢ " ; " " ¢ f .. .. .. . . . > > .. ¢" . < G G ' f f " f " -. ;. 6mL9. ¢. ; <. = " ? .. . > f. §{I~. Nel procedimento che segue si richiede che le sottomatrici principali , siano non singolari. Usando la notazione~ introdotta precedentemente, si mostra che note le soluzioni dei sistemi di ordine ?w?#? {¥ t §{±¾ §{ 6. . )7¨ { ) ¢ " ¢ ?#?w? ¢ {± ¥ ) ¿ { ) " ?#?#? { ¥ 7 9 { À " . {_ ¥ . si può ottenere la soluzione dei sistemi. >= { ¨ { >= ¥ { => ¨ ª <; <® ; ) <; { { ¿ ¥{ ª / ¢ " ³{. >= { ¨ { >= { => ¿ ª ; Á Â ) <; <; <Z { { " ¿ ¥{ ª §{. { ¨ { >= v¼ >= ª <; <; {¿ ¥ ª { §{. (2.5). >= 9 { <;. { ". con SU operazioni. In questo modo e` possibile risolvere un sistema di Toe plitz non simmetrico con S* operazioni. Tuttavia la stabiltà del processo e` ³{ assicurata solo se le matrici sono sufficientemente ben condizionate.. 2.1.1. Risultati numerici. Per verificare numericamente le prestazioni dell’algoritmo di Levinson e` stato considerato un sistema lineare del tipo. 6mL9 17.

(20) 4. 10. ρ=99/100 3. 10. ρ=9/10 2. 10. ρ=1/2. 1. 10. 0. 10. 0. 5. 10. 15. 20. 25. 30. 35. 40. 45. 50. Figura 2.1: condizionamento delle matrici KMS. . dove la matrice e` stata scelta in alcune?#?#famiglie di matrici test presenti in lettera? 7y , fissando tura [11] e il termine noto e` stato costruito mediante il prodotto 9Ã y ¬`- - -d ¥ . arbitrariamente la soluzione Tale sistema lineare e` stato risolto, al crescere della dimensione, mediante la nostra implementazione dell’algoritmo di Levinson e mediante l’algoritmo di Gauss con pivoting di colonna disponibile nella libreria di Matlab [14]. Nel corso del calcolo sono stati memorizzati il numero di operazioni eseguite dai due algoritmi e gli errori riscontrati nella soluzione numerica ? calcolati in norma- Ä. i y. 6 ) ±2 j Å zÆzzÇ È ' j ) É " fÊÉ. Un primo test e` stato effettuato utilizzando matrici KMS (Kac-Murdock-Szego). Queste matrici dipendono da un parametro Ë , e sono definitive positive per 1 Ë - . Il suo elemento generico e` dato da h k. j Ë D D@D ÍA-G1@1 e per i nostri test abbiamo fissato Ë Ì-GÍ O Íb-G1. . Come evidenziato in Figura 2.1, il condizionamento di queste matrici e` molto sensibile alla variazione del parametro Ë . 18.

(21) 5. 10. 4. numero di operazioni. 10. 3. 10. 2. 10. 1. 10. 0. 10. 0. 5. 10. 15. 20 25 30 ordine della matrice. 35. 40. 45. 50. Figura 2.2: complessità computazionale, Levinson vs. Gauss La Figura 2.2, che riporta la complessità computazionale dei due algoritmi utilizzati, evidenzia il vantaggio computazionale derivante dall’utilizzazione dell’algoritmo veloce: come già detto lau complessità computazionale per Gauss (linea tratteggiata) segue l’ordine di S* e per Levinson (linea continua) segue l’ordi ne di S* . Nelle Figure 2.3, 2.4 e 2.5 sono invece riportati gli errori riportati dai due algoritmi per i vari valori di Ë . Come si può osservare, l’algoritmo di Gauss risulta più accurato al crescere del condizionamento, grazie alla maggiore stabilità assicurata dal pivoting di colonna. Quando il condizionamento e` basso, invece, i due algoritmi hanno la stessa accuratezza. In particolare per Ë F-dÍ O l’algoritmo di Levinson fornisce un errore nullo, mentre l’errore prodotto dall’algoritmo di Gauss e` dell’ordine della precisione di macchina. Il nostro secondo esempio e costituito dalle matrici PROLATE [17] definite h da ~ ¬ j { [Î OIÏ ÕÔ_Ö { µ se 21 ? ÐÒÑzÓ ´ { con ? altrimenti Ô. Esse dipendono da un parametro Ï , da noi fissato a 1 O , e risultano definite positive per 1 Ï -dÍ O . Sono matrici molto mal condizionate, come evidenziato dalla Figura 2.6, e per questo motivo abbiamo limitato la dimensione a ] O . La Figura 2.7 illustra i risultati numerici ottenuti in questo caso, e conferma le 19.

(22) −16. 7. x 10. 6. errore in norma infinito. 5. 4. 3. 2. 1. 0 0. 5. 10. 15. 20 25 30 ordine della matrice. Figura 2.3: errori, KMS, Ë. 35. 40. 45. 50. 40. 45. 50. ×-dÍ O. −14. 3.5. x 10. 3. errore in norma infinito. 2.5. 2. 1.5. 1. 0.5. 0 0. 5. 10. 15. 20 25 30 ordine della matrice. Figura 2.4: errori, KMS, Ë 20. 35. D ÍA-G1.

(23) −12. 1. x 10. 0.9 0.8. errore in norma infinito. 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0. 5. 10. 15. 20 25 30 ordine della matrice. Figura 2.5: errori, KMS, Ë. 35. 40. 45. 50. DED ÍA-G1@1. 18. 10. 16. 10. 14. numero di condizionamento. 10. 12. 10. 10. 10. 8. 10. 6. 10. 4. 10. 2. 10. 0. 10. 0. 5. 10 15 ordine della matrice. 20. Figura 2.6: condizionamento delle matrici PROLATE 21. 25.

(24) 5. 10. 0. errore in norma infinito. 10. −5. 10. −10. 10. −15. 10. −20. 10. 0. 5. 10 15 ordine della matrice. ?. Figura 2.7: errori, PROLATE, Ï. 20. 25. 21 O . osservazioni fatte sul primo esempio riguardo alla superiorità dell’algoritmo di Gauss sull’algoritmo di Levinson in presenza di matrici molto mal condizionate.. 2.2. Matrici di Vandermonde. µ?# ?#´ ? f# µ G f ´ " " p 3 5 Definizione 2.3 Una matrice Ø v 3Ù5 f Úf Ú un vettore , tale che Ø Ø ?#?#? quindi - Ú ?#?#? ; - Ú " ?#?#? Ø - Ú .. .. ?#?#? < . . - Úf. h h xh i h si dice di Vandermonde se esiste ÛÚ j jÒ zzz f con Ú j [Ú j e = Ú f Ú f" ? Ú f > . ... Ú ff. Come già visto per le Toeplitz, anche per queste matrici valgono le considerazioni sui vantaggi di lavorare su uno spazio di memoria molto minore di quello richiesto per matrici generiche.. 22.

(25) I sistemi e quindi le matrici di Vandermonde sorgono spesso in problemi di interpolazione e approssimazione. il sistema Ø!Ü ×Ý e` equivalente ? k Infatti?#?wrisolvere a calcolare un polinomio interpolante. ' j¦ V j per 41 , il problema dell’interpolazione po?#?#? i valori k Fissati j j linomiale consiste nel trovare il polinomio 3ßÞ f tale che ' Ù V per ß1 . Tale polinomio esiste ed e` unico se le ascisse di interpolazione sono distinte. Esprimendo nella base canonicah. f h g X h i ' à ' . ?#?#? h h k ' j :V j 21 . le condizioni di interpolazione. g hxi f. . possono essere riscritte in forma ?#?#? matriciale. = = = - ' #? ?#? V ' f ; ; ; f V ' ' ? # # ? ? " ? " " " - ' ' f ... ... > . > > . . . . . . . < ... < . . ?#?#? < . . f Vf ' ff h - hXi ' f h k j j zzz f e` di Vandermonde ed e` non singolare se e solo se La matrice Ø á ' ' j â ' per â . Un algoritmo veloce per la risoluzione di questo sistema può essere ottenuto esprimendo il polinomio interpolante nella forma di Newton. à ' Ì. ^ Ù J ^ " ')(' } JÙ^ '*),' _ '*)ã' GGGJÙ^ f '*)ã' w ' )(' " §GGw '*)ã'. " }JCGG f " . e cioè. { fgi " à ' ½C^ J ^ ³{ ä å i 'U)(' j Xæ j { " {^ dove i coefficienti del polinomio coincidono ?#?w? con ? le differenze divise ^ { ©V ' ' " ' {± 23. (2.6).

(26) {. I coefficienti ^ possono quindi essere calcolati applicando la definizione ricorsiva delle differenze divise k ?#?#?. V ' j : V jÕ ?#?#? C 1 - V ' j¦ ' j " ' j {± V. . ' j ". ?#?#?. ' j {± ) V ' jÕ ' j { )(' j. ?#?#?. ' j { ". ?. Definiamo ora i polinomi. f ' ½ C^ f { ' ½: ^ { J: ')(' { { " ' . 1. (2.7). ?. e osserviamo che. L’algoritmo. ~ ) - ) . O. ?#?#?. ' ¯ ' ?#?#? ?#?#? ?#?#? WV V ^ ^ f ½. f k ~ :1 - ) - ?#?#? for ~ JCfor ) j j ^ j ' j ^ )() ' ^ j "{ ". (2.8). end. end. {. calcola appunto i coefficienti ^ del polinomio utilizzando la definizione 2.7. Se { esprimiamo il polinomio ' in forma canonicah. fhxi { { µ h g {´ ' { ' ½ (2.9) { µ j´ possiamo ricavare i coefficienti uguagliando i termini di ugual grado nelle due { espressioni di ' . Questo porta alla ricorsione ?w?#? f ´ f µ 2^ f ~ for { µ ) - ) O { µ 1 {´ k :^ { ),' {# {´ " ?#?#? ~ ~ " ) for { µ JL- { J µ O { µ (2.10) j ´ j ´ " ),' {# j ´ " " end f ´ { µ f ´ { " µ end 24.

(27) ?#?#Ü? in ? quanto k che fornisce le componenti del vettore incognito. µ @j ?# ?#j ´ ? 21 ?w?#? ' f ¥ Fissati il vettore 6ç ' w? ,?#? avente elementi distinti, ed il vetto V f ¥ L Ý è V re , la seguente implementazione Matlab dell’algoritmo so?w?#? f ¥ vrascrive Ý con la soluzione Ü del sistema di Vandermonde ' f :Ý ' Ø Ü function f=vsolve(x,f) n=size(x,1); for k=1:n for i=n:-1:k+1 f(i)=(f(i)-f(i-1))/(x(i)-x(i-k)); end end for k=n-1:-1:1 for i=k:n-1 f(i)=f(i)-f(i+1)*x(k); end end. . L’algoritmo richiede Í O flops. E` interessante dare una formulazione matriciale dell’algoritmo espoµ { / 3£5 ´ fG " µ ´ f# "appena sto. Definiamo la matrice bidiagonale inferiore con. «{ ; . { / é < e la matrice diagonale ê. ?#?#?. ) / 7 -. .. .. ... { :ëìÆEí- - ' î { wï ð ñ " Definiamo inoltre le matrici ê f "" f ' ¥. = . é ¥ GG .. 1. ... .. ... .. . ... GG )7/ { ),' ". ?#?#?. " `-G§GG GG f " 25. ê. 1 .. . > .. -. ' f ( ) ' f { " . " -d ' f " ¥. ?.

(28) ?#?w?. ` rispettivamente ?#?#ç ? è^ triangolare ^ f ¥ inferiore e superiore. E immediato verificare che il delle differenze divise può essere ottenuto dal vettore vettore ò ÝóèV V f ¥ mediante la relazione ?. ò . Ý. Inoltre l’algoritmo 2.10 e` equivalente al prodotto matriciale ?. Ü ò. Questo ci permette di concludere che l’algoritmo di risoluzione del sistema ØNÜ Ý e` equivalente alla fattorizzazione della matrice Ø " , e quindi alla fattorizza zione di Ø , in quanto. Ý Ü Ø "Ý. implica le fattorizzazioni. Ø ". Ø . e. " ". ?. Queste considerazioni consentono di risolvere con un algoritmo veloce anche il sistema trasposto. Ø ¥ :9. utilizzando la fattorizzazione appena ottenuta:. Ø "X ¥ 9T ê ¥ õ `G- ¥ " ?#G?wG? ' Dati i vettori 6¯n ' ô. . ¥ 9. ê. f " ` -d ¥ f ""Xö õ f " ' f " §GG ' ?# ?wö ? 9 ?#?w? f ¥ con elementi distinti e 9÷4 f ¥ il ºô ô f ¥ nel sistema seguente algoritmo sovrascrive 9 con la soluzione ? ?#?#? di Vandermonde ' f ¥ C9 Ø ' Una sua implementazione in ambiente Matlab e` function b=vtsolve(x,b) n=size(x,1); for k=1:n for i=n:-1:k+1 b(i)=b(i)-x(k)*b(i-1); end end for k=n:-1:1 for i=k+1:n 26.

(29) 20. 10. 15. numero di condizionamento. 10. 10. nodi equispaziati. 10. nodi di Chebychev 5. 10. 0. 10. 0. 5. 10. 15 20 25 ordine della matrice. 30. 35. 40. Figura 2.8: condizionamento delle matrici di Vandermonde b(i)=b(i)/(x(i)-x(i-k)); end for i=k+1:n b(i-1)=b(i-1)-b(i); end end. . che richiede operazioni. La prima parte del programma calcola i coefficienti del polinomio ed esegue il calcolo di ¥ 9 e la seconda parte calcola la soluzione eseguendo il prodotto ¥ ¥ 9ø .. 2.2.1. Risultati numerici. In modo analogo a quello fatto per le matrici di Toeplitz, sono stati fatti due test per verificare l’efficienza degli algoritmi vsolve e vtsolve comparati con quello di Gauss. Sono state costruite due matrici di Vandermonde, partendo da un campionamento uniforme dell’intervallo ) - -G e dai nodi di Chebychev [15]. L’elevato numero di condizionamento delle matrici ottenute e` illustrato in Figura 2.8. I sistemi lineari caratterizzati da tali matrici e dalle loro trasposte sono stati poi risolti con gli algoritmi vsolve, vtsolve e con l’algoritmo di Gauss. 27.

(30) 6. 10. 5. numero di operazioni. 10. Gauss. 4. 10. vtsolve vsolve 3. 10. 2. 10. 1. 10. 0. 5. 10. 15. 20 25 30 ordine della matrice. 35. 40. 45. 50. Figura 2.9: complessità computazionale Confronto Gauss−vsolve. 5. 10. 0. errore in norma infinito. 10. −5. 10. −10. 10. −15. 10. −20. 10. 0. 5. 10. 15 20 25 ordine della matrice. 30. 35. Figura 2.10: errori, vsolve vs. Gauss, I caso 28. 40.

(31) Confronto Gauss−vtsolve. 10. 10. 5. errore in norma infinito. 10. 0. 10. −5. 10. −10. 10. −15. 10. −20. 10. 0. 5. 10. 15 20 25 ordine della matrice. 30. 35. 40. Figura 2.11: errori, vtsolve vs. Gauss, I caso 0. 10. −2. 10. −4. errore in norma infinito. 10. −6. 10. −8. 10. −10. 10. −12. 10. −14. 10. −16. 10. 0. 5. 10. 15 20 25 ordine della matrice. 30. 35. Figura 2.12: errori, vsolve vs. Gauss, II caso 29. 40.

(32) 5. 10. 0. errore in norma infinito. 10. −5. 10. −10. 10. −15. 10. −20. 10. 0. 5. 10. 15 20 25 ordine della matrice. 30. 35. 40. Figura 2.13: errori, vtsolve vs. Gauss, II caso Il vantaggio computazionale degli algoritmi veloci e` confermato dai grafici riportati in Figura 2.9. Le Figure 2.10 e 2.11 riportano invece gli errori misurati in presenza della prima matrice di Vandermonde, mentre le Figure 2.12 e 2.13 mostrano gli errori riferiti alla matrice costruita a partire da nodi di Chebychev. Questi grafici mostrano una sostanziale equivalenza dei vari metodi, con un leggero svantaggio in termini di accuratezza per gli algoritmi veloci nei sistemi trasposti.. 2.3 2.3.1. Altre classi di matrici strutturate Matrici di Cauchy. h hxi. Definizione 2.4 Una matrice û ü 3mú f tali che ù .è^ j j. ù <. . . ;. 3 ú f|If sih dice di Cauchy se esistono dei vettori ù zz, z j " f con ^ ýÿþ " e quindi = G G " " " ý ý ý ? G G " " " ý X ý X ý x > . . . ... ý " . ... ... GG ý " " ý 30.

(33) Questa definizione classica e` stata estesa per comprendere una classe più ampia di matrici.. f|If. k. ?#?w?. se esistono dei vetDefinizione 2.5 Una matrice ù 3Ùú û

(34) ü 3[ú f e dei vettori j

(35) j 3ºú si, dice Cauchy-like - h hx i , dove / e` h un numero tori þ j jÒ zzzÈ f j ýÿþ e generalmente piccolo rispetto ad , tali che ù 4è^ con ^ " quindi =. ý GG ý ý ; GG ý ý X ý X ù X. .. .. < .. . . ý ý GG ý ?#?#? k E` immediato osservare che la prima definizione e`. j j ×- F- ponendo / F- e , .. . >. ricavabile dalla seconda. Le matrici Cauchy-like non hanno una grande rilevanza applicativa, ma hanno una notevole importanza per il nostro studio in quando, come verrà illustrato nel Capitolo 4, per questa classe di matrici e` possibile utilizzare un algoritmo di fattorizzazione veloce e numericamente stabile, per la possibilità di implementare il pivoting di colonna senza distruggere la struttura della matrice.. 2.3.2. Matrici di Hankel. ?#?w?. h f|IhXf i h h si dice di Hankel se esistono OI ) j " z zzÈ f con j = j e quindi = GG f f " " GG f " f ? .. .. .. . . . > f " GG f f u GG f u f f. Definizione 2.6 Una matrice 3¬5 f j scalari tali che H = . ; . . . . .. .. <. ". . f . f ". . Spesso le matrici di Hankel si trovano inquadrate nella classe più generale delle matrici Toeplitz-plus-Hankel. Definizione 2.7 Una matrice si dice Toplitz-plus-Hankel, o più brevemente ma J trice T+H, se e` esprimibile nella forma ç , dove e` una matrice di Toeplitz e e` una matrice di Hankel. 31.

(36) Le matrici T+H sono estremamente diffuse nelle applicazioni, come ad esempio nei processi di ortogonalizzazione [7], nel campo delle equazioni differenziali a derivate parziali, nel signal processing, etc. Per questo motivo c’è attualmente un grosso interesse per gli algoritmi destinati al trattamento di queste matrici, si veda ad es. [9].. 32.

(37) Capitolo 3 Problemi che conducono a sistemi lineari strutturati 3.1. Risoluzione di equazioni differenziali. Consideriamo l’equazione differenziale con condizioni al contorno (problema di Dirichlet) del second’ordine. $ %&)l+ J ' + ©VK ' (3.1) + / + ¶

(38) . À

(39) ' ÊY dove assumiamo che V 3 ù , cioè sono funzioni continue in ,e 1 per 'ã3 À

(40) . Si tratta della celebre equazione di Sturm-Liouville, per la quale

(41) 5 e` noto che esiste una soluzione unica + .

(42) Per discretizzare l’equazione (3.1) dividiamo l’intervallo in J¬- sottointervalli uguali. ' Ù ' fG " ' " GG ÷' f Ù h con ) ' J C k J j e denotiamo con l’approssimazione della soluzione sull’ -esimo punto della ?#?#? ? k discretizzazione j ! + ' j " . ê :1 + ' 8 + ' Sostituiamo ora l’operatore differenziale con l’operatore alle differenze centrali. #. + ' + ' J . ) O + ' J + 'U) 33. . . (3.2).

(43) che approssima la derivata seconda in quanto si può dimostrare [16] che. + ' + ' JqS* . #.

(44) . se +*3 ù . Operando questa sostituzione nell’equazione (3.1) valutata sul generico punto ' j della discretizzazione, si ottiene ?. j O$ ). j. j " ) " % J ' j j ©VK ' jÕ j ©V j * / + * ¶ e introducendo il simbolo j ' j + Ora, imponendo , arriva al sistema di equazioni lineari &&$ & J ? ?#?#? k O " " ) V " J / % O ) &&&& ) j " J: O J j j ) j " V jÕ ) f " J2 O J f f V f J ¶. si. Questo sistema può essere scritto nella forma matriciale. . )*. con. * *. * ... Á. )* -. * -. * -. * ... -. * .. -. f. .. .. * -. .. .. *. -. *. . *. *. V" J / V . -. * .. + e dove. ,.-. ". *. ('. Á. '. /. . * +. *. V f " Vf J ¶. ,./. J0 " 1 ) O ; ) O J0 ) .. .. .. : . . . .. .. ) < . . 1 ) - O J f . = . >. e` una matrice tridiagonale di Toeplitz. Schemi di discretizzazione differenti da (3.2) producono differenti matrici di Toeplitz, mentre la versione bi-dimensionale del problema ai limiti (3.1) conduce ad un sistema lineare caratterizzato da una matrice con struttura di Toeplitz a blocchi. 34.

(45) 3.2. Approssimazione polinomiale ai minimi quadrati in 1 O32547698;:. Consideriamo lo spazio di Hilbert. <.

(46) . con prodotto interno. V Q>= @?BA VK ' Q ' ED ' C. e con la norma. _V½. <. V V = " F . indotta dal prodotto scalare. Con Þ f denotiamo lo spazio dei polinomi di grado al più . Vogliamo trovare il polinomio f 3(Þ f che approssima meglio la V nel senso dei minimi quadrati, cioè. ÅìG _V ) K óÅìG IH.J I H.J . VK ' ) à ' D '. ?A C. ?. (3.3). E` possibile caratterizzare la migliore approssimazione nel senso dei minimi quadrati mediante il seguente teorema [15].. À

(47) . Teorema 3.1 Sia VK ' 3 , allora senso dei minimi quadrati se e solo se. <. f. e` l’approssimazione di f in. Þ f. nel. V ) f = 21. per ogni . 38Þ f . ?#?w? G ' fML Se dotiamo Þ f della base canonica K - ' ' , il precedente teorema conduce al sistema lineare ?w?#? k j < V ) ' 21 :1 - f = che e` detto sistema delle equazioni normali. Se esprimiamo la migliore approssimazione nella base canonica h. f h g x h i f ' / ' . otteniamo. < ' j f =. <V ' j = 35. k. :1 . ?#?#? .

(48) h h j O / ' ' . g hXi f N. g hXi f. h. j. k. <V ' j =. h. . 21 . k. <' ' / <V ' j = =. ?w?#? ?w?#?. . 21 . . ?. Il sistema delle equazioni normali può essere scritto in forma matriciale. CÝ. QP dove si ha. )* * * *. )* -. *. *. * -. *. Ý +. j V ' = R? <. *. /. / f. e dove. * -. .. .. +. V <V ' <. -. / ". P. , -. / *. C. <. , -. =. =. .. .. V ' f =. /. j ' KV ' ED ' A. h da sono detti i momenti della funzione H e` data h f. La matrice h h. . j . <'. j. ' =. . '. ?%A C. j. ed e` detta matrice di Gram. In particolare h se. h. . j ?. . " j '. D. ' . k ' j D ' J

(49) 1 k. -. J JC-. La matrice cos`ı ottenuta. . ;. -. ". " u" u" ... < ... ... f " fG " ". u" .. . .. . .. .. fG " 36. GG. f". " A JC-SS C S - S. . (3.4). =. fG " " fG " > .. . . ... GG f " ".

(50) e` detta matrice di Hilbert. Questa matrice ha la proprietà di essere simultaneamente di Cauchy e di Hankel. Essa risulta fortemente malcondizionata e si può dimostrare che l’andamento asintotico del suo condizionamento rispetto alla norma 2 e` dato da ?. T@U u H f. 37.

(51) Capitolo 4 Struttura di spostamento 4.1. Rango di spostamento. Definizione 4.1 Il rango di spostamento superiore di una matrice R o V tale che si può scrivere: piccolo intero / N. µ. Xg W i ´ZY. V2. j. j L j XW [´ Y µ ". i. dove K sono matrici di Toeplitz triangolari inferiori e K matrici di Toeplitz triangolari superiori.. 0j L j XW ´[Y µ ". Definizione 4.2 Il rango di spostamento inferiore di una matrice R 8o V tale che si può scrivere: piccolo intero / N. µ. ]g \ i ´[Y. V2. j. i. µ _ j L j XW Z´ Y ". "Q^. = 1 ? >. 1 -. <. . 1. ... .. ... .. 38. e` il più. i. Introduciamo la matrice di spostamento in avanti (forward-shift ). a. sono. j`_j. dove K sono matrici di Toeplitz triangolari inferiori e K ^ matrici di Toeplitz triangolari superiori.. ;. e` il più. Kjèàj. ". i. ... -. .. 1. j L j XW ´[Y µ ". sono.

(52) L’operatore di spostamento per una matrice hermitiana di dimensione definito per la prima volta in [12] come. # VN(V. ). a b. a V acb. e` stato. (4.1). a. dove rappresenta l’aggiunta della matrice , ossia la matrice trasposta coniua a b gata. L’espressione V corrisponde allo spostamento (shift o displacement in inglese) della matrice V verso il basso lungo la diagonale principale di una posi# # zione, il che giustifica il nome attribuito all’operatore . Se la matrice VN ha rango ¢ , indipendente da , allora R e` detta strutturata rispetto allo spostamento definito in (4.1) e il numero ¢ coincide con il rango di spostamento superiore / dVN , come verrà mostrato nel Teorema 4.1. La definizione di operatore di spostamento si può estendere ad una matrice non hermitiana e anche a matrici non quadrate. i i Lemma 4.1 Dati i vettori colonna 6p ciale. K. a V a b. ) V. ' j L j " xt . K. + j L j " , l’equazione matri-. g i 6 j t jb j ". (4.2). ha l’unica soluzione. V©. g i j ". È6 j t jb . (4.3). dove 6à denota una matrice triangolare inferiore di Toeplitz la cui prima co t b lonna e` 6 , e denota una matrice triangolare superiore di Toeplitz la cui t b prima riga e` . Allo stesso modo l’equazione matriciale. V. ). g i 6 jt jb j ". (4.4). g i f 6 e jb g t§e j j ". (4.5). a bV a. ha l’unica soluzione. V2 dove. 6e b ' f . ?#?w?. ' ". quando. 39. 6 b ' " . ?w?#?. ' f. ?.

(53) Dimostrazione. Per l’unicità notiamo che V ) a V a b (V ) a V. ". ". implica. V. " ). V. . a V. " ). V. . a b. a b C1 .. equazione che ammette l’unica soluzione V " ) V Per dimostrare l’esistenza, osserviamo innanzitutto che. 6à 3t b ) a¯À 6 t3b hacb C6 t3b. ? (4.6). Tale proprietà si può verificare per il caso di matrici o ed estendere poi facilmente al caso generale. Sostituendo ora la (4.3) nell’equazione (4.2) si ottiene. g i jè0j ) a õ g i KjWàj a b ö j j " ". g i KjWàj ) aKjèàjda b g i 6 j t jb j j " " j Kj t j b 0j per la (4.6). Per semplicità abbiamo posto 6 e . La seconda parte del teorema si dimostra in modo analogo.. i. Esiste una caratterizzazione del rango di spostamento che fornisce anche un algoritmo per la sua determinazione. Teorema 4.1 I ranghi di spostamento seguenti relazioni. / VN / VN . / . jxÆ]Glk³ V jxÆ]Gl³ k V. e. /. si possono ottenere mediante le. ) ). a V c a b a bV a. . dove jxÆ]Glk§ indica il rango della matrice .. Dimostrazione. La dimostrazione segue immediatamente dal Lemma 4.1. Infatti se V ha una rappresentazione minima XW V gi 2 6 j t jb . j. ". allora. V. ). a V a b. W g i 6 j t j b j " 40.

(54) . che ha rango / in quanto il rango di una matrice con il minimo intero che permette di scrivere. ?. ý. i Viceversa se V j' L j XW t j K K ",. ) ai + j L j XW. V a b. di dimensione , coincide. C g i 6 jt jb j " j ha rango / , allora devono esistere dei vettori 6 . " . tali che. a V a b. ) V. Per il Lemma 4.1 abbiamo allora. g i W. V2. j. ?. XW g i 6 jt j b j ". ?. 6 j t jb ". Si può usare una dimostrazione simile per la rappresentazione di / E` immediato osservare che. a V a b. ) V. ; <. a = > . V. a. GG a. dove V e` la sottomatrice principale di V di Toeplitz si ha. ) ¤ a ma. ;. < b. che ha rango 2, e questo prova che similarmente. V. ). acb V a. ; < a. a .. .. ... 1. ; ) < 1. .. .. = GGÌ1 > V ) -. di ordine . .. i. (4.7). . Perciò per una matrice. = " GG f > .. 1 . f. / . = GG a > V. 41. ; ) <. O. . NelI’altra notazione si ha. 1. V. = 1 ? > .. GGÌ1. ... (4.8).

(55) Le espressioni (4.7) e (4.8) spiegano, anche graficamente, le ragioni che hanno condotto all’introduzione del termine rango di spostamento. Infatti, come già a a b accennato precedentemente, V sposta la matrice di partenza di una posizione verso il basso lungo la diagonale principale, inserendo nella prima riga e colonna a b a un vettore di zeri. Se invece consideriamo V , lo spostamento di V avviene allo stesso modo, ma di una posizione verso l’alto e i vettori di zeri si inseriscono all’ultima riga e colonna. Nel caso delle matrici di Toeplitz, la differenza V ) a V a b risulta essere una matrice che ha rango ¢ O indipendente da . La proprietà interessante, oltre che nuova, e` che questo fatto vale per una classe di matrici più ampia di quella delle matrici di Toeplitz. Poiché sappiamo che la struttura di Toeplitz non e` invariante per svariate operazioni molto frequenti quali la moltiplicazione, l’inversione, la fattorizzazione , etc., vorremmo cercare di capire per quali operazioni risulta invariante il rango di spostamento. Un risultato particolarmente significativo e` fornito dal seguente teorema. Teorema 4.2 Il rango di spostamento superiore ed inferiore di una matrice non singolare e` uguale al rango di spostamento inferiore e superiore, rispettivamente, della sua inversa. / d VR"X ? / dVR"X. / d VNÌ / d VNÌ. Dimostrazione. Notiamo che a b V " a / V " Ì j

(56) Æ]Glk³dV " ) n

(57) j Æ]Gl³k X VR" ) a b VR" a oVN

(58) j Æ]Gl³k « ) a b VR" a VN poiché il rango non e` influenzato dalla moltiplicazione per una matrice non singolare. Applicando la proprietà. jxÆ]Glk³«. ) mpZ½qj

(59) Æ]Glk³« ). p. . possiamo continuare la catena di uguaglianze. / dVR"xÌ . j

(60) Æ]Glk³« j

(61) Æ]Gl³ k X« j

(62) Æ]Gl³ k dV. ) ). ). a V a b VR"X a V a b VR"XoVN a V a b / VN. ?. . ? Nello stesso modo si può dimostrare l’altra uguaglianza del teorema / d VR"X / VN. i 42.

(63) Un’altra proprietà per cui e` invariante il rango di spostamento e` legata alla cosiddetta inerzia di spostamento di una matrice V . Definizione 4.3 L’inerzia di una matrice hermitana V e` la terna di numeri in teri non negativi ÿ ô E che indicano, rispettivamente, il numero di autovalori positivi, nulli e negativi di V . E` immediato osservare che la somma J coincide con il rango di V . Un risultato classico relativo all’inerzia di una matrice e` dato dal seguente teorema [6]. Teorema 4.3 (Legge di inerzia di Sylvester) Se V e` una matrice simmetrica e r r bV r e` una matrice non singolare, allora V e hanno la stessa inerzia.. # d VN e` anch’essa una matrice. Se V e` una matrice hermitiana, sappiamo che hermitiana.. Definizione 4.4 Si definisce inerzia di spostamento di una matrice hermitana V la terna di numeri interi non negativi ÿ ô E che rispettivamente, il # indicano, N V numero di autovalori positivi, nulli e negativi di . Inoltre la somma UJs coincide col rango di spostamento (superiore) di V . Useremo questa definizione per evidenziare un’altra proprietà della struttura di spostamento. Lemma 4.2 L’inerzia di spostamento di una matrice hermitiana non singolare V rispetto a V ) a V a b e` uguale all’inerzia di spostamento rispetto a V " ) a b V " a t , e cioèt ?. G>U.jvu_ìÆdV. . a V a b. ). GlUgjvu_ìÆdVR". a b VR" a. ). . (4.9). Dimostrazione. Consideriamo la seguente relazione. ;<. a b. => a. V V. . ". «. ç<; ç<;. 1 " « =>. a bV. « 1. a V. «. =>. <;. ;< V. 1 ). => 1. V V. a bV. " ). 1. a V a b. 1 V 43. ". =>. <;. " a 7;<. «. «. a bV. a V. 1. 1. «. =>. b. " « . => b.

(64) dove abbiamo utilizzato l’identità V V Ora, per il Teorema 4.3 le matrici. ;<. =>. 1 V. 1 V. " ). " L«(V " V b. a bV. ". ;<. e. a. V. b. .. => 1. a V a b. ). 1 V. ". hanno la stessa inerzia, avendo entrambe la stessa inerzia della matrice. ;<. =>8?. a V. a b V. ". Ma poiché l’inerzia di unat matrice R e` uguale all’inerzia della sua inversa, visto t che gli autovalori della inversa sono gli inversi degli autovalori di R e quindi hanno a V a b GlUgjvuwìÆ V " ) a b V " a lo stesso segno, la tesi che GlUgjvu_ìÆdV ) rimane i provata.. 4.2. Struttura di spostamento. L’operatore di spostamento (4.1), apparso per la prima volta in connessione con le matrici di Toeplitz in [2] e [12] e successivamente formalizzato in una teoria estesa in [10], e` stato generalizzato nella forma. . #7wx ; y z dVN(V 0 ) { X VCG. (4.10). dove { e sono due matrici di ordine , allo scopo di estendere le proprietà dimostrate #|wx y;z per le matrici di Toeplitz ad altre classi di matrici strutturate. L’operatore L e` detto operatore di spostamento di Stein relativo alle matrici K { . Nel nostro studio utilizzeremo lo stesso operatore nella cosiddetta forma di Sylvester, introdotta per la prima volta in [10] ed utilizzata in numerosi lavori successivi, come ad esempio in [3]. Siano { e due matrici di ordine e sia V 3mú f|If una matrice che soddisfi l’equazione. } wx l y z VN { X V. ) VLG:(~2Xp 3¯ú f| e p 3¯ú If. per determinate matrici rettangolari ~ piccolo rispetto a e comunque indipendente da esso. Definizione 4.5 Le matrici ~ piccolo intero. tra tutti gli K { matrice V .. L. / /. e p. sono dette K {. wx l y z VNsj

(65) Æ]Glk§ { V. . L. , dove il numero. /. e`. -generatori di V , e il più. V ) . -generatori e` chiamato rango di K {. 44. (4.11). L. -spostamento della.

(66) Se { e sono matrici non singolari, e` immediato osservare che questa definizione di rango di spostamento e` equivalente a quella basata sull’operatore (4.10). La forma di Sylvester (4.11) dell’operatore di spostamento e` stata in seguito ulteriormente generalizzata in [13] nella forma. } w 0 x ; y z ( qXVC #. )0{ XV:w. che chiaramente include entrambe le definizioni precedenti. Il risultato cruciale, che consente di esprimere in maniera molto più generale il concetto di struttura e` che per ognuno dei modelli di struttura introdotti nel Capi L tolo 2 e` possibile scegliere coppia di matrici K { per definire un operatore } wx ylz `s |una | f I f \ f I f ú ú di spostamento della forma. } wx ; y z dVN { V. V ) . (4.12). L in modo tale che il rango di K { -spostamento delle matrici della classe in esame risulti costante. Questo fatto consente, ad esempio, di memorizzare una matrice strutturata semplicemente mediante i suoi generatori e soprattutto, come vedremo, di sviluppare algoritmi veloci di fattorizzazione che necessitino dell’aggiornamento dei soli generatori. Inoltre, si verifica che l’insieme delle matrici che, per una data scelta di una L L coppia K { , mantengano un rango di K { -spostamento costante risulta essere molto più vasto della classe di matrici di strutturate che ha portato a quella scelta, includendo, ad esempio, anche le inverse delle matrici strutturate di partenza. Per questo motivo ciascun insieme di matrici viene denotato aggiungendo il suffisso -like al nome della classe strutturata di partenza. Per chiarire la situazione, analizzeremo ora le generalizzazioni delle classi di matrici strutturate presentate nel Capitolo 2, presentando le scelte usuali per le L ed illustrando la forma che assumono i generatori in corrisponcoppie K { denza delle matrici strutturate classiche. A questo scopo e` utile introdurre la matrice ?#?#? ;. a. Se ®.- , la matrice. a. ". 1. 1. - 1 1 < ... #? ?#? 1. ?#?#? ?#1 ?#? ... .. ... .. 1. ... -. .. = . . . 1. 1 ? .. . > . ... e` chiamata matrice ciclica di spostamento in avanti. 45.

(67) 1. Matrici Toeplitz-like.. {. Per una matrice di Toeplitz. . a. : a. ? ". ". } w z \. della forma (2.1) si ha. a. ". ) ca (~2Xp ". dove due possibili generatori assumono la forma. ~. = ; µ " J ´ f " 1 J ´ f µ 1 > .. .. < . . f " J " 1. => ? GG 1 pF ;< µ f " ) " f ) GG " ) ´ f " a f a L Questo ci mostra che una matrice di Toeplitz ha rango di K " " -spostae. 1. 1. mento uguale a due.. 2. Matrici Vandermonde-like.ê. {. . 2 a. ". ? :ëìÆIí ' ". Ø Per una matrice di Vandermonde ê classica } w z. Ø 6àX½. 6. ' f si ha. a Ø È6à ) Ø È6à " @~2Xp. dove i generatori assumono la forma. ~. ?w?#?. = ' f " ) - ; ' f ) - > .. < . ' ff ) 46.

(68) e. pF. · 1. - ¸. GGÌ1. ? ê. Si vede, dunque, che una matrice di Vandermonde ha rango di K spostamento uguale ad uno.. ê : {. ". L. -. ?#?w? :ëìÆEí " ?#?#? f ? CëìÆEí " f . ê. 3. Matrici Cauchy-like.. fa. Questo insieme di matrici strutturate coincide esattamente con la classe di matrici Cauchy-like precedentemente definite nel Paragrafo 2.3.1. In questo caso, se ù e` una matrice Cauchy-like, ê abbiamo ê. z } w 9. ù . @~2Xp. ù ) ù. dove i generatori sono della forma. Ì·. ~ b. j

(69) . k. j. p.. 3nú per con Cauchy-like ha rango di K. ·. ". ?#?w" ?. GG GG. f ¸. ê - ê L . f ¸. . Si vede, dunque, che una matrice -spostamento uguale ad / .. 4. Matrici Toeplitz-plus-Hankel-like.. { dove ;. . @ ¦ :@ "¦" . e` definita da. 1. . ; ;. -. 1. <. ?#?#?. 1. 1 .. .. -. ... .. #? . ?#. .?. ... .. 47. 1. ... .. ... .. 1 -. = 1 .. ? . 1 > .

(70) 4.3. L’algoritmo di Schur. . L’algoritmo di Schur per la fattorizzazione di una matrice non singolare consiste essenzialmente in una riformulazione del classico algoritmo di triangolarizzazione di Gauss. µ ´ : C " per cui esista la fattorizzazione , consideriamo Data una matrice il seguente prodotto matriciale, equivalente al primo passo dell’algoritmo di Gauss. µ " ´ " ;<. -. 1. )n " « f ". =>. ;<. D. ". 9 ". =>. b. V. ò". ;<. ". D. 9 " ). ". =>m?. b. D ". ". V. ò". (4.13). b " )0 " ò ". Per annullare gli elementi della prima colonna situati al di sotto della diagonale principale e` necessario assegnare ?. D" " (. " 9 ". Si definisceµ allora complemento di Schur dell’elemento D ´ matrice " la matrice ?. ". di posto. `- -d. nella. b " qV " ) D"" 9 " ò " Questa matrice rappresenta la sottomatrice principale formata dalle ultime ) µ ´ righe e colonne della matrice risultante dalla applicazione del primo passo dell’algoritmo di Gauss alla matrice . ~. Il passo matriciale. dell’algoritmo di fattorizzazione di Gauss consiste nel prodotto. {

(71) µ { µ => >= « { " 1 ´¦" " ´" <; ;< . { µ ;< 1 {e 1 ¦´ il cui blocco di posto O O si può rappresentare nella forma => { {b =>. { µ 1 D D { ò {e ¦´ ;< ;< ;< 9 { V { 1 ) { « f { n { µ

(72) { µ ´ " { ´ . dove. D { @ e la matrice. . {" 9 {. { @V { ) D {" 9 { {b ò 48. { µ {

(73) µ => ´¦" " ´" { µ 1 {e ¦´ ò {b. {. =>.

(74) ´ { µ nella matrice .. {. e` il complemento di Schur dell’elemento D. Si vede dunque che l’algoritmo di Gauss corrisponde alla complementazione di Schur ricorsiva di una sequenza di sottomatrici principali di . { I fattori e della matrice si possono ottenere memorizzando i vettori e { ò ottenuti nel corso dell’algoritmo nelle matrici. =. ;. . . -. .. . .. .. .. . .. .. " ... .. < . . ... . .. -. . .. .. ... {. .. . .. .. .. .. . >. . ... .. -. .. .. e. ;. D. . b " GG G G ò " G G G G G G D GG G G ò b G G G G ... . <. .. { D. GG ... . ?. GG >. ò {b. . ... =. .. D. f. L’applicazione dell’algoritmo di Schur a una generica matrice non comporta nessun vantaggio in termini di complessità rispetto all’algoritmo di Gauss. La situazione e` differente per matrici strutturate che soddisfino particolari tipi di equazioni di spostamento, come evidenziato dal seguente teorema. Teorema 4.4 Sia data la matrice. V. " ;<. =>. b. D . ". " Á ". 49. Ve. ".

(75) che soddisfa l’equazione di spostamento di Sylvester. } w x y z V. " . V ;< " a. =>. 1 {. XV " ). . V. . a =>. (~ " X p " . " " ;< 1 . f\. (4.14). If. e p " 34ú . per determinate matrici triangolari { " e " , con ~ " 34ú a Il simbolo indica una sottomatrice il cui contenuto e` ininfluente ai fini del ragionamento. Se l’elemento D " di posto `- -d e` diverso da zero, allora il complemento di e b Schur V V " ) D " " " Á " soddisfa l’equazione di spostamento di Sylvester. X V ). { con. ;< ~. · 1 dove '. b. ". e9. => 1 . p. G (~ X p . V. q~. h' b" . (4.15). ¸ qp " ) 9 " · - D"" Á b" ¸ . sono la prima riga di ~. ". =>. )" ;< D" " " ". e la prima colonna di p. " , rispettivamente.. Dimostrazione. Dalla formula di complementazione di Schur (4.13) e` possibile ricavare la fattorizzazione. V. " . 1 <; D" « " ". =>. ;<. Sostituendo questa espressione di V associando alcuni termini, si ottiene. V 1 ;< " a { . =>. ". D. 1. " V. 1. =>8?. - D"" b" ;< Á 1 «. . nella equazione di spostamento (4.14) ed. => D " b " Á " ;< " ;< 1 V 1 « => 1 D ;< " ) <; D" « 1 " " D. =>. 1. =>. 50. =>. V. 1 . ;<. 1. ". a => . (~ " X p " .

(76) da cui, utilizzando l’espressione dell’inversa di una matrice elementare di Gauss, si ottiene. =>. ;<. -. 1. V ;< " a. ) D "" " «. D. ) ;<. e. V <; " a . => 1. {. . ;<. 1. D. 1. {. =>. 1 ". ". =>. 1. V. . " 1. V. . => D" b ) " Á " ;< " ;< 1 1 « => => 1 - ) D "" b" <; X ~ X p <; Á " " D " « 1 « ) " ". =>. V. ;<. =>. 1 a =>. . . 1. D. D. ) ;<. . 1. " V. ;<. => 1 . ;<. =>. 1. " 1. a. . => . . ) D "" " «. Scrivendo i generatori in modo da evidenziare la prima riga di ~ colonna di p " , otteniamo. ;<. -. 1. =>. ) D "" " «. ;<. ' b " e~. =>. ". · 9 " ;<. pe. ". ¸ ;< ' b. ~e. " ). ~e. " ) " ). D. => ?. - ) D"" b" X~ " h p " ;< Á 1 «. ". "". 1 " ' b. ) D "" b" Á « => · 9 ". =>. ". (4.16) e la prima. pe. b ¸ " ) D"" 9 " Á ". Definendo. ~ p il blocco di posto. O O . . pe. D. D. "" " ' b" " 9 " b " Á ". dell’equazione (4.16) può essere scritto nella forma. {. X V ) V. G (~ h p 51. ?.

(77) e inoltre si ha. ;< · 1. => 1. ~. p. @~. )" <; D" " ". =>. ' b. ". ¸ @p " ) 9 " · - D"" Á b" ¸. ? i. Resta cos`ı dimostrata la tesi del teorema.. Si vede dunque che il complemento di Schur mantiene la stessa struttura di spostamento delle matrici che l’hanno generato, e che e` possibile ottenere i generatori del complemento di Schur a partire dai generatori delle matrici di partenza con un basso costo computazionale. Questo fatto suggerisce la possibilità di applicare l’algoritmo di Schur ad una matrice strutturata in modo da operare solo sui generatori dei complementi di Schur, senza costruire esplicitamente le matrici intermedie. Un’accorta implementazione di tale algoritmo porterebbe ad un risparmio nell’occupazione di memoria e ad un riduzione della complessità computazionale.. 4.4. Fattorizzazione veloce e stabile di matrici di Cauchy. L’implementazione dell’algoritmo di Schur per la fattorizzazione trice V " che soddisfi un equazione di spostamento. } wx ; y z V. " . { X V. " ) V. . di una ma-. " G2q~ " X p ". (4.17). può essere riassunto con i seguenti passi: 1. Ricavare dai generatori ~ " e p " la prima riga e la prima colonna della matrice V " . Queste forniscono, rispettivamente, la prima colonna di e la prima riga di . 2. Calcolare, mediante le relazioni (4.15), i generatori del complemento di Schur V . 3. Procedere ricorsivamente ripetendo i passi 1. e 2. sulla matrice V. 52. ..

(78) ?#? Per una matrice Cauchy-like, questa?wprocedura consiste nel seguente algoritmo for. ~ F- . ?#?#? {

(79) { × r h ~ JL- for " { r ?#?#ý ? . end ~h . for { ý . end for j= ¡ q¢¤£.¥I¥I ¥¦£

(80) §. ¨Z©oª¬«® ¯ . © «° ©²± ³¨ ©Eª´ ª ¶ª © © « ©µ± ª

(81) ª ª. end end di cui diamo anche una implementazione Matlab, scritta in modo da essere applicabile sia a matrici di Cauchy che a matrici Cauchy-like function [L,U]=lu_c(t,s,phi,psi) n=size(t,1); if ãny(nargin==[2 4]) error( ’errato numero di parametri’) end if nargin==2 phi=ones(1,n); psi=phi; end L=eye(n); U=zeros(n); for k = 1:n for j = k+1:n L(j,k)=phi(:,j)’*psi(:,k)/(t(j)-s(k)); end for j=k:n U(k,j)=phi(:,k)’*psi(:,j)/(t(k)-s(j)); end for j=k+1:n L(j,k)=L(j,k)/U(k,k); phi(:,j)=phi(:,j)-phi(:,k)*L(j,k)’; 53.