Appunti di calcolo numerico

X

con non ,

, ,

.

.

delle lungherze

attenere sole

stesse le

vettore compenente

abbie

di che to

possiamo prima

un R di

Noiezione I

I

· ↳ se

- piane Xnx

=

I

I

x 1 GE

. 7

I -gen

v

= xn dove

⑨ G è ottenuta dalla matrice identità posizionando

M negli elementi di indici (1, 1), (1, r), (r, 1) ed (r, r),

S rispettivamente i valori c, s, -s e c

a

a

Altri esempi di matrici ortogonali sono le matrici elementari di permutazione P e le matrici di

rs

permutazione P Q

una matrice Q ortogonale e simmetrica è tale che

proprietà I

=

Matrice elementare di Householder

sia u un vettore di n componenti reali con u≠0; si costruisce la matrice di ordine n

--

- com

tale matrice si chiama matrice elementare di Householder

La matrice U è simmetrica e ortogonale e dunque U =I

2

dimostrazione -

**

I T

è facile verificare che la diade uu è una matrice simmetrica: (uu ) =(u ) u =UU .

-

-

-

- - - -

Dunque U è simmetrica. #

Affinché la matrice U sia ortogonale deve essere U U=I. Dunque

-

Per la definizione di α si ha 2α=u u, allora /Elle

(z)

-O sign

=

Assegnato un vettore z≠0 di n componenti reali, sia σ=+– z e sia z≠-σe ; dove e è primo

11-11

- 2 1 1

- #

vettore unità di n componenti, e =(1, 0, …, 0) .

E 1 --

Ell-112

Posto u=z+σe e α= u si ha che la matrice elementare di Householder U=I-(1/α)uu soddisfa

-

1 2

-

dimostrazione

poiché z≠-σe allora vale che u≠0 e dunque U è la matrice elementare di Householder.

un 2

1

- Il Il

Essendo z z= z =(+– z ) =σ , si ottiene

2

1

- 2 2

=

- z GC

u = +

() (8) **

(

dove con z si è indicata la prima componente di z. Si ha anche che

1 + :

da qui si deduce

Affinché nel calcolo della prima componente di u non ci sia cancellazione di cifre si sceglie

-

2

IIEll

or

·

significato geometrico: la matrice U ruota il vettore z senza riflettore elementare

-

alternarne la norma euclidea. Il vettore Uz non è soltanto il di Householder

-

vettore z ruotato ma è anche il vettore riflesso di z rispetto alla

- -

retta r ortogonale ad u e passante per l'origine degli assi.

-

La matrice di Householder U è anche detta riflettore elementare

se si moltiplica la matrice U, riflettore elementare del vettore z, per un vettore v assegnato, si

-

-

ottiene un vettore della stessa lunghezza di v così fatto

-

(6) i

si nota che non occorre costruire esplicitamente la matrice U; le

"informazioni" sulla matrice U sono "fornite" dal vettore u.

calcolare la

intero matrice

occouve

nov per

·

Fattorizzazione QR

si analizza l'applicazione della trasformazione elementare di Householder per fattorizzare una matrice A,

quadrata di ordine n non singolare, in un prodotto di due matrici Q ortogonale ed R triangolare superiore

La fattorizzazione della matrice A=QR procede in modo simile alla fattorizzazione A=LR.

Si cercherà di triangolizzare la matrice A attraverso n-1 applicazioni delle matrici elementari

di Householdler invece che n-1 applicazioni delle matrici elementari di Gauss come visto per la

fattorizzazione LR.

Al primo passo della fattorizzazione QR, k=1, si considera la matrice elementare di

10 Householder costruita a partire dalla prima colonna a della matrice A:

- 1

si costruisce, a partire da a il vettore u di n componenti definisce

- 1 1 Eran

si

⑧ ed e il primo vettore unità di n componenti

-

1

com

denotando con I la matrice identità di ordine n, si definisce la matrice elementare

n

⑧ di Householder con (2)

moltiplicando U per A si ottiene la matrice A che ha la prima colonna formata da

1

⑧ elementi nulli ad eccezione del primo e le altre colonne con tutti gli elementi modificati

come in (6) differente Lnaltere anche

di

a

la so ziga

-

MxM (2)

secondo passo della fattorizzazione QR, k=2. Indichiamo con a le sottocolonne di ordine n-1

a j

20 -

della matrice A

(2) (a) (a?) Ilâ Ile

= sign

or

= = a(2)

definiamo la matrice elementare di Householder che opera sul vettore a . Mediante il vettore

2

a(2)

a si costruisce il vettore u di n-1 componenti,

2 2

-

- ~erez call

posto e indicata con I la matrice identità di ordine n-1, definiamo la

n-1

matrice elementare di Householder di ordine n-1.

e definiamo la matrice U , m x n, come la matrice nella forma a blocchi

2 (el

->

moltiplicando la matrice U siffatta per la matrice A si ottiene la matrice A :

2

(E)( Azzb "

Bi !.

(Brünn)

)= !

[Azzb )

Auas abbiamo

moto dave = :

.... ,

an un

· on u

si procede al calcolo di dove V è la matrice di Householder di ordine n-2 costruita

3

componenti così definito

dal vettore u di n-2

- 3 com

Al= Al fino

U

: calcole all'ultima

In parso

-

ultim 1)

all'ultimo passo, (n-1)-esimo, k=n-1, calcolata la matrice A

(n -

L

= 1)

(n IElls

anm-trige(a m

-

2 1

v -

si calcola il vettore di 2 componenti

=tünt

dove σ indica la norma Euclidea del vettore moltiplicata per il segno di a .

n-1 n-1n-1

Posto e indicata con I la matrice identità di ordine 2, definiamo la matrice

2

elementare di Householder di dimensione 2

e la matrice U come la matrice nella forma a blocchi

n-1

dove I indica la matrice identità di ordine n-2 e con0 nei blocchi (1, 2) e (2, 1) indichiamo le

n-2

matrici nulle, rispettivamente di dimensione (n-2) x 2 e 2 x(n-2)

si ottiene la seguente matrice:

1

-

Q

-

dunque, posto si ha

siccome le matrici U , k=1, …, n-1, sono ortogonali e simmetriche, allora

k

si conclude allora che la matrice

è ortogonale (in quanto ottenuta come prodotto di matrici ortogonali

Caratteristiche fattorizzazione QR

Im computazionale

complessità

· la

calcolata di

di OlepsY

fattorizzazione ((m)IlAllreps

AtE IEIIf=

fattorizzazione

Q'R' esatta

A +

· é con

:

se la matrice A è non singolare, la fattorizzazione QR permette di calcolare n vettori

⑧ ortonormali q , q , …, q , le colonne della matrice Q, a partire da n vettori linearmente

1 2 n

- -

indipendenti a , a , …, a , le colonne di A

- -

1 2 n

-

Metodo QR per la risoluzione di sistemi lineari --

mediante la fattorizzazione QR di una matrice A si può risolvere il sistema lineare Ax=b

con A, n x n, non singolare.

come per la fattorizzazione LR, la fattorizzazione di A come prodotto di una matrice ortogonale Q e di una

matrice triangolare superiore R con elementi diagonali non nulli, renderebbe facile la determinazione della

soluzione del sistema normale non singolare di n equazioni in n incognite in quanto il sistema lineare si

scriverebbe QRx=b ovvero

-

g Q RI=g

de

g In ricave

· =

il metodo che calcola la soluzione di un sistema lineare che si basa sulla fattorizzazione della

matrice dei coefficienti A nel prodotto QR mediante le matrici elementari di Householder è noto

come metodo QR per sistemi lineari

si hanno n-1 passi.

Al primo passo si costruisce la matrice elementare di Householder U dalla prima colonna di A.

1

(2)

Si calcolano A =U A e b =U b. Allora il sistema equivale a

(2) 1 1

- (3) (2)

(3)

(2)

Al secondo passo si costruisce U dal vettore e si calcolano A =U A e b =U b .

2 2 2

Il sistema ora diventa 1)

(n

(n 1)

si procede fino all(n-1)-esimo passo in cui il sistema è A x=b . Si costruisce allora la

-

-

-n 1)

(n

(n)

1)

(n

matrice U dal vettore . Si calcolano R=A =U A e g=b =U b .

-

-

--

- -

n-1 n-1 n-1

-

Il sistema diventa con R matrice, non singolare, triangolare superiore.

Rx G

= -

-

La soluzione x si ottiene risolvendo il sistema mediante il metodo di sostituzione all'indietro

La matrice Q della fattorizzazione A=QR è data da

e il vettore g è CAPITOLO 13

RISOLUZIONE DEI SISTEMI

SOVRADETERMINATI E SOTTODETERMINATI

Sistemi lineari sovradeterminati e problema dei minimi quadrati

--

consideriamo il sistema lineare Ax=b dove la matrice dei coefficienti A ha dimensione m x n,

con m>n, definito sistema sovradeterminato.

Il sistema può non ammettere soluzione. Allora si cerca un vettore x tale che il vettore residuo r,

o -

-

definito come sia il più piccolo possibile. Denotiamo con l'r più piccolo

-

possibile.

Per determinare quanto sia piccolo r, si usa la norma euclidea *

--- 112

Se x* è soluzione del sistema lineare allora r*=Ax*-b=0. I

- - 0

=

Cerchiamo quindi il vettore x tale che renda minima la norma euclidea del residuo, cioè quel

-

-

de

vettore x che minimiza

-

Formuliamo quindi il problema dei minimi quadrati come il calcolo del vettore x che risolve il

-

-

seguente problema di minimo Irll e

Il vettore x si dice soluzione dei minimi quadrati minlAF-BI

- E win

= =

-

Risoluzione del problema dei minimi quadrati mediante il metodo QR

supponiamo che la matrice A, m x n, con m>n, abbia rango massimo uguale a n.

essendo Q una matrice qualsiasi ortogonale m x m, allora

↑

applichiamo la fattorizzazione QR alla matrice A.

Indichiamo con a , a , …, a le n colonne (linearmente indipendenti) della matrice A di m

u

n 2

1 2 n

componenti ciascuna. Costruiamo la matrice elementare di Householder U di ordine m,

1

Ilällz

dove (an)

oreign

con

↳ unità

vettare d componenti

prive i n dove con 0 indichiamo le

si ottiene matrici nulle di dimensioni

(m–1)x1 e 1x(m–1) per i blocchi,

rispettivamente, (2, 1) e (1, 2) e

u è il vettore di m–1 elementi,

2

-

si costruisce poi la matrice U di ordine m

2 costruito a partire dal vettore

-

(3)

la matrice A che si ottiene dalla *

ign(a?) Il 112

&

(27

moltiplicazione di U con A è data da =

2 2

applicando le n-1 matrici U , U , …, U

1 2 n-1

(n)

abbiamo calcolato la matrice A di espressione

(n)

moltiplichiamo ora la matrice U per A per