Sistemi lineari

Esempio

Algoritmo di sostituzione in avanti

Per i sistemi triangolari inferiori si usa l’algoritmo di eliminazione in avanti, ove si ricava x1 dalla

prima equazione, si sostituisce nella seconda e si ricava x2 e così via (algoritmo per righe).

Si può anche, dopo aver ricavato x1 dalla

prima equazione, sostituire in tutte le

successive ottenendo un sistema

triangolare inferiore di dimensione n−1; da

questo si ricava la prima incognita x2 dalla

prima equazione e si sostituisce nelle

successive equazioni e così via (algoritmo

di eliminazione in avanti per colonne).

La complessità è anch’essa O(n2/2)

Esemplo Sostituisco

E 1 attenendo

x1 1

Xe =

= :

4)x 5 1

1 1

x2

x

xz

1 + = Xz

1 = =

= ,

,

3xz

3 X3 7

+

x1 =

-

• Stabilità

Per entrambi gli algoritmi in tutte e due le versioni (per righe e per colonne) serve lo stesso

numero di operazioni, date da n(n−1)/2 prodotti e altrettante somme e n divisioni. Si dice che

sono algoritmi per cui servono O(n2/2) flops. Entrambi gli algoritmi sono metodi diretti, che, in

un numero finito di passi, in aritmetica esatta, calcolano la soluzione esatta del sistema.

Quando si usa aritmetica finita, invece di calcolare la soluzione esatta x del sistema Rx = b

oppure Lx = x si determina una soluzione approssimata z. Essa può essere interpretata come

soluzione esatta di un sistema perturbato:

(R + δR)z = b oppure (L + δL)z = b

1.3 Metodi diretti: generalizzazione

Nel caso generale possiamo distinguere diverse metodologie di risoluzione che vedono come

protagonisti diverse fattorizzazioni. Difatti l

’idea di base è fattorizzare la matrice A nel prodotto di due

matrici “semplici”, in modo che sia facile risolvere i due sistemi associati; in particolare si ha il metodo di

eliminazione di Gauss che può essere interpretato come un metodo di fattorizzazione.

Metodo di Eliminazione di Gauss

Questo metodo trasforma un sistema lineare generale in un sistema triangolare superiore equivalente,

che può poi essere risolto con la sostituzione all’indietro.

Il metodo di eliminazione gaussiana si basa sull’idea di ridurre il sistema Ax=b ad un sistema

-

equivalente (avente cio`e la stessa soluzione) della forma Rx=b, dove R è triangolare superiore e

-

b è un nuovo termine noto. Quest’ultimo sistema potrà essere risolto con il metodo delle

sostituzioni all’indietro. Indichiamo il sistema originario come A(1)x = b(1). Durante la riduzione

sfrutteremo in modo essenziale la proprietà per la quale sostituendo un’equazione del sistema

con la differenza tra l’equazione stessa ed un’altra, moltiplicata per una costante non nulla, si

ottiene un sistema equivalente (cioè con la stessa soluzione) a quello di partenza.

Algoritmo di eliminazione di Gauss

Consideriamo dunque una matrice A Rn×n, non singolare, e supponiamo che l’elemento

∈

diagonale a11 sia diverso da zero. Introducendo i seguenti moltiplicatori:

Per consistenza con le notazioni precedentemente introdotte indicheremo con R la matrice triangolare

*

superiore A(n). Gli a vengono detti elementi pivotali e devono essere ovviamente tutti non nulli per

k = 1,... ,n− 1, per cui l’eliminazione di Gauss si può portare a termine (strategia diagonale)

xt

Inoltre per k = 1,... ,n−1, assumiamo che a 0 e definiamo il moltiplicatore:

Per ottenere un sistema triangolare superiore si ricorre all’uso delle trasformazioni elementari di

gauss

Trasformazione elementare di Gauss

Innanzitutto si introduce quella che è la trasformazione elementare di gauss per la quale:

Sia x con x1 ̸ = 0. Una trasformazione elementare di Gauss è una matrice triangolare inferiore

∈Rn

con 1 sulla diagonale tale che L1x = (x1,0,...,0)T con X=(x1,…,xn)

la

Solo I

> componente

I nulla

non

A questo punto il MEG può essere interpretato come metodo di fattorizzazione e usando le

trasformazioni elementari di Gauss si può costruire quella che è la fattorizzazione LR

Fattorizzazione LR

si fattorizza la matrice A nel prodotto di una matrice triangolare inferiore per una triangolare

superiore; se A= LR, si ha:

Questo richiede O(n2) operazioni una volta ottenuta la fattorizzazione

Data A , si vogliono trovare le condizioni per cui A si può fattorizzare nel prodotto di una matrice

∈Rn×n 2

triangolare inferiore L con una triangolare superiore R. Poichè deve essere A= LR occorre imporre n

uguaglianze per determinare n2 + n parametri (numero di elementi non nulli di L e di R).

Pertanto occorre fissare n elementi, attribuendo ad essi un valore arbitrario.

In genere, per convenzione, si fissano uguali a 1 gli elementi diagonali della matrice triangolare inferiore o

superiore. In realtà si cerca la fattorizzazione A= LDU

dove L è una matrice triangolare inferiore con elementi diagonali 1, D è una matrice diagonale, U è una

matrice triangolare superiore con elementi diagonali 1. = like

aij divij

rij =

- lijdj

Dij =

Condizioni per l’esistenza della fattorizzazione LR

Complessità Computazionale

La fattorizzazione di Gauss ha una complessit`a di O( ) somme e prodotti. Il calcolo del determinante è

↳

O(n) dopo la fattorizzazione.

Inoltre ci sono due classi di matrici per il cui il metodo di Gauss si può portare a termine

senza che nessun perno o pivot si annulli:

• le matrici strettamente diagonali dominanti per righe (per colonne) o le matrici non singolari diagonali

dominanti per righe (o per colonne);

• le matrici simmetriche definite positive.

1.4 Pivoting e stabilità

Un perno nullo ferma l’algoritmo di Gauss. Inoltre un perno molto piccolo può causare un’amplificazione

degli errori di arrotondamento, rendendo l’algoritmo instabile. Per questo motivo occorre ricorrere alla

tecnica di ricerca del perno per il quale si adoperano delle strategie di pivoting che riordinano le righe e/o le

colonne della matrice per scegliere un perno ”grande” e migliorare la stabilitá dell’algoritmo. Inoltre

scambiare tra loro righe e colonne permette di avere elementi pivotali non nulli

Strategia di pivoting parziale

Al passo k, si sceglie come perno l’elemento di modulo massimo nella colonna k (dal rigo k in giù ) e si

scambia la riga corrente con quella che contiene il perno scelto. Questo garantisce che i moltiplicatori siano in

quella dell’algoritmo con

modulo minori o uguali a 1 (|mik |≤1 ). La complessità computazionale è uguale a A

strategia diagonale. In più vengono eseguiti una serie di confronti per determinare i perni, pari a O( ).

Questa strategia è più usata rispetto al pivoting totale per la sua efficienza computazionale.

Strategia di pivoting totale

Al passo k, si cerca l’elemento di modulo massimo nell’intera sottomatrice restante (dalla riga k e colonna k in

poi) e si scambiano sia le righe che le colonne per portare il perno in posizione diagonale. Richiede un

riordinamento finale delle incognite. Ha un costo computazionale pi`u elevato e viene utilizzato solo in casi

particolari.

Pertanto lo scopo del pivoting è:

1. Permettere all’algoritmo di eliminazione di Gauss di essere completato anche su matrici dove i perni

diagonali potrebbero essere nulli.

2. Rendere l’algoritmo di fattorizzazione pi`u stabile limitando l’amplificazione degli errori di arrotondamento.

Residuo

Si definisce residuo il vettore r = b−Aw , dove w è il vettore calcolato. Con la strategia che sceglie

come perno l’elemento di modulo massimo sulla colonna, il residuo resta piccolo.

1.4 stabilità dei metodi diretti

Se esistono costanti positive a e b indipendenti dagli elementi di A e dalla sua dimensione tali

che allora la fattorizzazione LR si dice stabile in senso forte.

Ilijka /zijkb

,

Contrariamente se le costanti a,b dipendono dall’ordine di A si dice stabile in senso debole.

L’eliminazione di Gauss con pivoting parziale `e stabile in senso debole perch´e gli elementi

di R possono crescere esponenzialmente con la dimensione n. Contrariamente quello totale è stabile in

senso forte

1.5 condizionamento dei sistemi lineari

Quando risolviamo un sistema lineare Ax=b, uno degli aspetti fondamentali è di quanto la soluzione

dipenda dai dati iniziali. Se cambiano la matrice A o quanto cambia la soluzione x? Per capire questo,

introduciamo il concetto di condizionamento che può essere di due tipi:

Problemi Mal Condizionati: Un sistema lineare è mal condizionato se piccole perturbazioni

•

nei dati iniziali (matrice A o termine noto b) causano grandi variazioni nella soluzione.

Geometricamente, le rette (o piani) sono quasi parallele.

• problemi ben condizionati: Un sistema lineare è ben condizionato se piccole perturbazioni

nei dati iniziali (matrice A o termine noto b) causano piccole variazioni nella soluzione.

CirhXn

Si definisce numero di condizionamento di una matrice A la quantità:

~ M(A) -

11

IIA-

11 All Fornisce una stima del rapporto tra l’errore

= . relativo nella soluzione e l’errore relativo

Questo se A non è singolare nei dati.

Si può estendere la definizione al caso di matrici qualunque:

Il numero di condizione è il rapporto tra la perturbazione massima e la pertubazione minima non nulla

che ogni vettore x subisce per effetto della trasformazione lineare associata ad A.

∈Rn

– Se µ(A) A `e mal condizionata; se µ(A) ≈1, A `e ben condizionata.

≫1,

– Il numero di condizionamento indica quanto una matrice è ”vicina” alla singolarità

– Per la norma euclidea, µ2(A) = σmax/σmin, dove σ sono i valori singolari di A (radici quadrate degli autovalori

T

di A A).

– Attenzione: Un determinante piccolo non significa necessariamente che una matrice sia mal condizionata, e

viceversa.

Residuo vs. Errore: Un residuo piccolo (r = b−Aw), w soluzione perturbata di un sistema perturbato, non

implica necessariamente che la soluzione calcolata wsia vicina alla soluzione esatta x. L’errore assoluto

1 1

e= x−w é legato al residuo da e= A r. Se ||A || è grande, anche un piccolo residuo può portare a un

- -

grande errore. V

il residuo è piccolo ma l’errore è grande: questa è una caratteristica dei sistemi mal condizionati.

1.6 Metodi iterativi per sistemi lineari

I metodi iterativi a differenza dei metodi diretti consentono di trovare soluzioni approssimate di un

generico sistema lineare di questo tipo:

Pertanto