Metodo di Newton per N ARE

Si consideri la N ARE (2.24), e si supponga che la Matrice dei Coefficienti M ad essa relativa sia una M-matrice non singolare o singolare irriducibile. Il metodo di Newton

per N ARE genera la seguente successione definita per ricorrenza

X0∈ V1

Xk+1= Xk− (R0Xk)

−1_{[C + X}

kA + DXk− XkBXk],

(2.35)

dove V1 è un’opportuna regione di Cm×n e R0X è la derivata di Fréchet dell’operatore di

Riccati definita in (2.26). La precedente formulazione equivale a R0_X

k[Xk+1− Xk] = (Xk+1− Xk)A + D(Xk+1− Xk) − (Xk+1− Xk)BXk− XkB(Xk+1− Xk)

= −C − XkA − DXk+ XkBXk,

da cui

Xk+1A + DXk+1− Xk+1BXk− XkBXk+1= −C − XkBXk, (2.36)

e quindi, con le notazioni di (2.27)

∆Xkvec(Xk+1) = vec(−C − XkBXk). (2.37)

Alla luce delle precedenti argomentazioni si enuncia il teorema dovuto a Guo e Laub ([29]) che dimostra la convergenza del metodo di Newton alla soluzione minimale non negativa Xmin, cui si premette il seguente lemma dovuto ai medesimi autori.

Lemma 2.4.1. Si supponga che la N ARE (2.24) abbia Matrice dei Coefficienti M

M-matrice irriducibile. Allora la soluzione minimale non negativa Xmin è strettamente

positiva.

Teorema 2.4.2. Si consideri la N ARE (2.24) e si supponga che la rispettiva Matrice dei

Coefficienti M sia una M-matrice non singolare o una M-matrice singolare irriducibile e sia Xmin la soluzione minimale non negativa.

La succesione { Xk}_k∈N definita dal metodo di Newton con valore iniziale X0 = 0

rispetta le seguenti proprietà:

• la successione {Xk}k∈N è ben definita,

• Xk≤ Xk+1≤ Xmin per ogni k ∈ N,

2.4. METODO DI NEWTON 41

Dimostrazione. Si consideri dapprima il caso in cui M sia una M-matrice non singolare. La dimostrazione si svuilluppa in tre parti, la cui verifica è provata per induzione:

a) Xk≤ Xmin,

b) ∆Xk è una M-matrice non singolare,

c) Xk≤ Xk+1.

Per k = 0 si ha:

a) il primo termine della successione definita per ricorrenza è X0= 0 pertanto X0≤

Xmin;

b) le matrici A e D sono M-matrici non singolari, pertanto ∆X0= (A

T_{⊗ I}

m+ In⊗ D)

risulta una M-matrice non singolare;

c) per la (2.36) il secondo termine della successione è definito da: X1A + BX1= −C, dunque (AT ⊗ Im+ In⊗ D)vec(X1) = vec(−C). Si conclude, quindi vec(X1) = (∆X0) −1 vec(−C) ≥ 0 = X0. essendo C ≤ 0 e (∆X0)

−1 _{≥ 0 per le ben note proprietà delle M-matrici.}

Si supponga che le proprietà sopra indicate siano verificate per ogni i ≤ k, allora a) Dalla (2.36)) seguono le uguaglianze:

(Xk+1− Xmin)(A − BXk) + (D − XKB)(Xk+1− Xmin) =

−C − XkBXk− XminA + XminBXk− DXmin+ XkBXmin=

−C − XkBXk+ C − XminBXmin+ XminBXk+ XkBXmin=

−(Xk− Xmin)B(Xk− Xmin).

Utilizzando la funzione vec per primo e ultimo membro si ottiene: ∆Xkvec(Xk+1− Xmin) = −vec (Xk− Xmin)B(Xk− Xmin)
.

Per ipotesi induttiva si ha che Xk ≤ Xmine che ∆Xkè una M-matrice non singolare,

pertanto:

vec(Xk+1− Xmin) = (∆Xk)

−1 _{−vec (X}

k− Xmin)B(Xk− Xmin)

≤ 0

da cui segue la tesi.

b) Per il punto precedente Xk+1≤ Xmin, dunque:

A − BXk+1≥ A − BXmin e D − Xk+1B ≥ D − XminB

e allora:

(A−BXk+1)T⊗Im+In⊗(D−Xk+1B)
≥ (A−BXmin)T⊗Im+In⊗(D−XminB)
.

Le matrici ∆Xk+1 e ∆Xmin sono rispettivamente una Z-matrice ed una M-matrice

per costruzione, pertanto la disuguaglianza precedente implica che ∆Xk+1 è una

42 CAPITOLO 2. METODI RISOLUTIVI CLASSICI

c) È immediato verificare la seguente catena di uguaglianze uguaglianze: Xk+1(A − BXk+1) + (D − Xk+1B)Xk+1=

Xk+1(A − BXk− B(Xk+1− Xk)) + (D − XkB − (Xk+1− Xk)B)Xk+1=

−C − XkBXk− Xk+1B(Xk+1− Xk) − (Xk+1− Xk)BXk+1=

−C − Xk+1BXk+1− (Xk+1− Xk)B(Xk+1− Xk).

Dalle eguaglianze precedenti segue che:

(Xk+1− Xk+2)(A − BXk+1) + (D − Xk+1B)(Xk+1− Xk+2) =

−C − Xk+1BXk+1− (Xk+1− Xk)B(Xk+1− Xk) + C + Xk+1BXk+1=

−(Xk+1− Xk)B(Xk+1− Xk),

e dunque, essendo per il punto precedente ∆Xk+1 una M-matrice non singolare e

per ipotesi induttiva Xk≤ Xk+1, si ottiene:

Xk+1≤ Xk+2.

Per quanto riguarda il caso in cui la Matrice dei Coefficienti M sia una M-matrice singolare irriducibile la dimostrazione è analoga: si prova per induzione su k che

a) Xk< Xmin,

b) ∆Xk è una M-matrice non singolare,

c) Xk≤ Xk+1.

Per k = 0 si ha

a) è evidente essendo X0= 0 < Xminper il Lemma 2.4.1;

b) le matrici A e D sono M-matrici non singolari, pertanto: ∆X0 = (A

T_{⊗ I}

m+ In⊗ D)

è una M-matrice non singolare;

c) la dimostrzione è analoga al caso in cui M sia una M-matrice non singolare. Si supponga di aver dimostrato le tre proprietà per ogni i ≤ k e le si verificano per k + 1.

a) È possibile rifarsi al caso precedente sostituendo la maggiorazione (minorazione) stretta alla maggiorazione (minorazione) semplice.

b) Si osservi che vale la seguente serie di uguaglianze:

(Xmin− Xk+1)(A − BXk+1) + (D − Xk+1B)(Xmin− Xk+1) =

C + Xk+1BXk+1+ (Xk+1− Xk)B(Xk+1− Xk)+

−C + XminBXmin− XminBXk+1− Xk+1BXmin=

(Xk+1− Xk)B(Xk+1− Xk) + (Xk+1− Xmin)B(Xk+1− Xmin).

Essendo Xmin− Xk+1 > 0 per il punto precedente, e, Xk+1 ≥ Xk per ipotesi

induttiva, risulta:

∆Xk+1vec(Xmin− Xk+1) > 0

e dunque, per le caratterizzazioni delle M-matrici, ∆Xk+1 è una M-matrice non

singolare.

2.4. METODO DI NEWTON 43

In entrambi i casi le proprietà sono quindi verificate per ogni k = 0, 1, . . . pertanto la successione {Xk}k∈N è ben definita e monotona crescente e limitata, risulta, pertanto,

convergente. Si supponga

lim

k→+∞Xk = X∗

allora X∗è una soluzione non negativa della N ARE (2.24) e poiché si avrebbe X∗≤ Xmin,

e Xmin è la soluzione minimale si ottiene:

lim

k→+∞Xk = Xmin.

Dunque il metodo di Newton con valore iniziale X0= 0 è convergente.

Per quanto riguarda l’analisi sull’ordine di convergenza del metodo di Newton, vale il seguente risultato ([29])

Teorema 2.4.3. Sia M la Matrice dei Coefficienti associata alla N ARE (2.24) e sia

{ Xk}_k∈N la successione generata dal metodo di Newton. Allora

• se M è una M-matrice non singolare o singolare irriducibile con drift non nullo il metodo di Newton ha convergenza quadratica, ovvero esiste una costante γ tale che

kXk+1− Xmink ≈ γkXk− Xmink2,

• se M è una M-matrice irriducibile con drift nullo e quindi se la soluzione minimale Xmin è critica il metodo di Newton ha convergenza lineare con raggio 1₂, ovvero

kXk+1− Xmink ≈

1

2kXk− Xmink.

È possibile applicare tecniche particolari nel caso in cui Xmin sia critica in modo

da ottenere una convergenza quadratica. Una prima strategia è quella si ‘shiftare’ la Matrice Hamiltoniana H in una matrice ˜H che abbia medesimo autospazio invariante c-antistabile e tale che la dericata di Fréchet del nuovo operatore di Riccati R0_X sia non singolare in Xmin. Un’altra tecnica è quella di individuare un valore opportuno di X0 in

modo da baipassare la singolarità della matrice ∆Xmin. Per un approfondimento di tali

artifici si rimanda a [10].

Riassumendo gli aspetti numerici del metodo si ha:

costo computazionale per passo per individuare Xk+1è necessario risolvere il siste-

ma (si veda (2.23))

Hk(A − BXk) + (D − XkB)HK= R(Xk)

Xk+1= Xk+ Hk.

Si osservi che la prima relazione è una equazione di Sylvester, la cui risoluzione richiede circa 60n3 _{operazioni con l’algoritmo di Bartels e Stewart. Il calcolo del}

termine noto e dei coefficienti che definiscono l’equazione è di circa 6n3 _opera-

zioni. Il costo totale è dunque di circa 66n3 _{operazioni aritmetiche. Si osservi,}

inoltre, che il calcolo di R(Xk) fornisce, ad ogni passo, una stima della bontà della

approssimazione.

convergenza Il metodo presenta convergenza quadratica nel caso non critico, e con-

vergenza lineare (con raggio 1₂) nel caso critico pertanto in tal caso si rendono necessarie tecniche per mantenere la convergenza quadratica.

stabilità numerica La stabilità del metodo dipende dal condizionamento della matrice

R0

44 CAPITOLO 2. METODI RISOLUTIVI CLASSICI