• doubling algorithm
• problema di grandi dimensioni
• equazioni algebriche di Riccati

Le equazioni di Riccati sono tra le equazioni matriciali più note ed analizzate nella matematica applicata. Tale interesse è dovuto tanto alla vasta gamma di campi della matematica applicata in cui le equazioni di Riccati intervengono, tra i quali la teoria del controllo ottimo e stocastico, i giochi differenziali, i modelli di code, la programmazione dinamica, quanto alle innumerevoli relazioni delle suddette equazioni con concetti fondamentali dell'algebra lineare in generale, e dell'algebra lineare numerica in particolare: la nozioni di sottospazi invarianti e sottospazi di deflazione di matrix pencil, split di autovalori.
Le più importanti tipologie di equazioni di Riccati (ARE) sono

- le equazioni algebriche di Riccati non simmetriche (NARE) della forma
C+ XA+ DX - XBX =0,

- le equazioni algebriche di Riccati a tempi continui (CARE) del tipo
C+ XD^*+ DX - XBX =0,

- le equazioni algebriche di Riccati a tempi discreti (DARE) con formulazione
A^*XA + Q - (C + B^*XA)^*(R + B^*XB)^{-1}(C + B^*XA) -X=0,

dove ovviamente i prodotti matriciali presenti nelle equazioni precedenti sono tutti compatibili. Si tratta, come evidente, di equazioni non lineari, in cui l'incognita compare come fattore moltiplicativo sia destro che sinistro tanto nel termine di "primo grado" quanto nel termine di "secondo grado". Tale peculiarità differezia le are dalle equazioni matriciali unilaterali quadratiche (UQME).

Tra le soluzioni delle ARE, particolarmente importanti sono le cosiddette soluzioni estremali, ovvero soluzioni che massimizzano e minimizzano ogni altra soluzione (relativamente ad una specificata relazione d'ordine matriciale). Si dimostra, sotto opportune ipotesi sui coefficienti delle ARE, l'esistenza di tali soluzioni.

Fondamentale, per una comprensione teorica dei metodi risolutivi, è individuare la corrispondenza tra soluzioni delle ARE e sottospazi invarianti o sottospazi di deflazione di matrix pencil: tale corrispondenza risulta particolarmente significativa per le soluzioni estremali, in quanto, utilizzando proprietà di c-splitting o d-splitting, è possibile individuare le suddette soluzioni a partire dal relativo sottospazio, trasformando, quindi, un problema quadratico in un problema lineare.

Particolarmente significativo, tanto nelle applicazioni, tanto nella teoria, è il caso in cui la matrice dei coefficienti associata ad una NARE è una M-matrice.

I metodi risolutivi si dividono sostanzialmente in due macro gruppi: i metodi classici e i doubling algorithm. Tale distinzione si rende necessaria in quanto i primi metodi hanno una rilevanza più storica e teorica che applicativa in quanto presentano un elevato costo computazionale e sono inficiati da problemi di stabilità numerica. Tra i metodi classici sono annoverati

- il metodo di Schur alla base del quale vi è quanto detto sulla corrispondenza tra sottospazi invarianti o di deflazione e soluzioni delle ARE. Il metodo utilizza la fattorizzazione di Schur delle matrici "in gioco" per determinare efficientemente tali sottospazi;

- il metodo delle iterazioni funzionali il quale definisce delle successioni definite per ricorrenza. Ponendo delle opportune ipotesi sui coefficienti, è possibile provare la convergenza di tali successioni alle soluzioni estremali. Inoltre, è possibile comparare la velocità di convergenza delle successioni definite dalle diverse iterazioni funzionali. In generale l'ordine di convergenza è lineare, mentre il costo computazionale è di O(n^3) per iterazione;

- il metodo di Newton applicato all'operatore di Riccati e definito a partire dalla derivata di Fréchet dell'operatore stesso. Anche in tal caso, ponendo ipotesi sui coefficienti, si dimostra la convergenza del motodo alle soluzioni estremali. Il metodo di Newton ha un costo computazionale di O(n^3) operazioni elementari per passo e presenta una convergenza quadratica nel caso "non critico" e lineare nel caso "critico".


I doubling algorithm, così denominati perché presentano convergenza quadratica, sono i metodi più performanti presenti in letteratura,

- il metodo doubling algorithm strutturato (SDA) genera una successione di matrix pencil
con la proprietà che ad ogni iterazione dell’algoritmo i sottospazi di deflazione rimangono
inalterati, mentre i relativi autovalori vengono elevati al quadrato. Tale proprietà risulta
molto utile se il sottospazio di deflazione è d-stabile, in tal caso, infatti, è evidente
che se l’algoritmo può essere iterato senza interruzioni (ovvero senza breakdown), gli
autovalori ad ogni passo hanno norma sempre più piccola, fino a tendere a zero. Questa
proprietà rende particolarmente semplificata la ricerca del sottospazio di deflazione d-stabile
e fornisce, quindi, un valido metodo per calcolare le soluzioni estremali;

- il metodo di riduzione ciclica (CR) si basa sulla medesima filosofia dell'elevamento a quadrato del metodo SDA, generando una successione
di polinomi matriciali quadratici i cui autovalori vengono elevati al quadrato ad ogni iterazione. Dunque, si rende dapprima necessario trasformare la ARE in una UQME ad essa associata, poi si applica il metodo CR per individuare la soluzione di tale UQME per risalire, infine, alla soluzione estremale della ARE di partenza.

Per poter applicare i doubling algorithm è necessario trasformare proprietà di c-stabilità o c-splitting, in proprietà di d-stabilità o d-splitting, a tal fine, si introducono due tipologie di trasformazioni, le trasformazioni affini e le trasformazioni di Cayley, che danno origine a due possibili varianti del metodo SDA e del metodo CR.

I doubling algorithm, come detto, risultano particolarmente efficaci per la risoluzione di equazioni di Riccati in quanto presentano una convergenza quadratica ed hanno un costo computazionale per passo pari a O(n^3) operazioni elementari (se le matrici che definiscono l'equazione hanno dimensione n x n). Tuttavia, per valori molto grandi di n, tale costo computazionale diviene "insostenibile" ed anche i dobling algorithm risultano inapplicabili in quanto impiegherebbero tempi non ragionevoli.

I matematici cinesi Chang-Yi Weng, Tiexiang Li, Eric King-wah Chu e Wen-Wei Lin hanno apportato delle "correzioni" al doubling algorithm strutturato per equazioni di Riccati definite da matrici aventi grandi dimensioni ma con particolari proprietà di struttura. Tali modifiche portano il costo computazionale ad O(n) operazioni per passo rendendo l'algoritmo applicabile anche a ARE di grandi dimensioni. A base del motodo SDA_{ls} vi è un astuto utilizzo della Formula di Sherman-Morrison-Woodbury ed un particolare "meccanismo" di troncamento e compressione per limitare la crescita del rango di alcune matrici definite dall'algoritmo.

Dunque, è studiata la portata di tali modifiche al metodo RC, osservando che anche in tal caso vi è una notevole riduzione del costo computazionale, portato a circa O(n) operazioni elementari per iterazione. Si osserva che le proprietà di struttura delle matrici "si conservano" nel corso dell'algoritmo rendendo particolarmente semplificata la ricerca delle soluzioni. Si conclude, quindi, che il metodo CR_{ls} risponde positivamente se testato a problemi con dimensione elevata e particolari proprietà di struttura.