Anteprima
Vedrai una selezione di 10 pagine su 45
Mat - Prova Pag. 1 Mat - Prova Pag. 2
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 6
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 11
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 16
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 21
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 26
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 31
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 36
Anteprima di 10 pagg. su 45.
Scarica il documento per vederlo tutto.
Mat - Prova Pag. 41
1 su 45
D/illustrazione/soddisfatti o rimborsati
Disdici quando
vuoi
Acquista con carta
o PayPal
Scarica i documenti
tutte le volte che vuoi
Estratto del documento

R R

(~) con triangolare superiore E

y

QT = (~) z

51

- da cui cerco la soluzione del sistema Ra = e minllAa _ Yllz = IIYll

a Z Z

Esempio:

1 -1

A 1 4

= 1 4

r 1 -1

Ricavare la fattorizzazione QR dalla matrice A

Passo 10: r1+#1 n

= = ~ = ~

,

+

a~~ s, e

U, o o

1 3 3

o ~1-~r~

o

2U1Ui 1 1 1 I1=

o o

r 1 6 3 1 1

Hl = -llulll~ = ~

I o o 1 3 1 1

1 1 1 1

-- -- --

-

2 2 2 2

5

1 1 1

-- --

- -

6 6 6

2 5

1 1 1

-- --

- -

6 6 6

2 5

1 1 1

-- -- -

- 6 6 6

2

-2 -3 -2

1 -4

O -

3

I 1

Az = H1A1 = O O

-

3 5 -2

O -

3

l

0:

Passo 2 O

O O

10 10 25

- - -

3 3 3

I + 10

1110 Il

sz = = 5 Uz = 10 5ez = -

3 3 3

5 5 5

- - --

3 3

3 'z 1 O O O

2 2 1

-- --

O -

3 3 3

2uzuI

Ilullz=250 2 11 2

1- z

Hz = =

z z --

3 O - -

Iluzllz 3 15 15

1 2 14

O - - -

3 15 15

-2

-2 -3 -4

-5

O

I 12

O

A3 = HzH1Al = HzAz = O 5

16

O O 5

r 1r 1r 1

0

Passo 3 :

O O O

O O O

12 12 32

+

Il - Il =1 - -

S3 = = 4 U3 4e3 =

5 5 5

16 16 16

-- -- --

5 5

5 'z 1 O O O

O 1 O O

3 4

z 256 2U3UI --

O O

1-

IIu311z -

H3 = =

= -5- 5 5

Ilu311~ 4 3

O O - -

5 5

-3

-2 ~21

r -5

= = = = ~

H3H,H,A, H3A3

R A4 -4

O

O O

1 1 1 1

-- --

- -

2 2 2 2

1 1 1 1

-- --

- -

2 2 2 2

I

H1H2H

Q = =

3 1 1 1 1

-- --

- -

2 2 2 2

1 1 1 1

- - - -

2 2 2 2

Esempio:

Siano date le seguenti coppie di valori, calcolare la retta di regressione:

-5 -3 1 3 4 6 8

Xi

Yi 18 7 O 7 16 50 67

1 -5

1 -3

1 1

Il

+

P(x) 3

ao al x

= A = 1 4

1 6

1 8

Ricavare la fattorizzazione QR dalla matrice A

Passo 10: +..f7

1 1

1

1

1

1

1

1-

=

Hl 2U1Ui

Ilulll~

Completa da solo Metodi Iterativi

Ax

Servono per risolvere sistemi lineari = b.

Se A è fortemente sparsa (cioè, se il numero di elementi diversi da zero è molto minore del

numero degli elementi nulli), i metodi diretti non ne tengono contro (tranne in alcuni casi in cui la

matrice ha una particolare struttura come la matrice tridiagonale).

In questo caso (soprattutto se A è di grandi dimensioni), può essere vantaggioso utilizzare metodi

iterativi. x(k)

I metodi iterativi costruiscono una successione di vettori R'' tale che:

E

+00

k ~

con x' Ax

soluzione di = b

Def. Convergente: x(k) x'

Una successione di vettori di R'' si dice convergente al vettore di R''

Ilx(k) - x' Il

Se una norma T. C. lim =

3 O

k-v+co

Poiché tutte le norme vettoriali in R'' sono equivalenti, questa condizione di convergenza si

traduce in una condizione di convergenza per componenti:

<

(k) - • I Il Il . - 1

xi xi - n

(k) - •

X X l - , ... ,

I 00

Quindi: i=l, ... ,n

Ilx~k) - x;11

lim = O

k-v+co I

Metodi iterativi (lineari) della forma:

vettore iniziale assegnato

x(O) +

{ x(k+l) Bx(k) q k 0,1, ...

= =

Def. Consistente: Ax x(k) x'

Un metodo iterativo si dirà consistente con = b se, nel caso in cui = è soluzione del

> x(k+l) x(k+2) x(k)

sistema per qualche k O Allora: = = ... =

Oss:

Se il metodo è consistente, deve verificarsi che:

+ 1

q

x' Bx" e x' A- b

= =

+

A- BA- A- BA- CI- B)A-

1 b = 1 b q ~ 1 b - 1 b = q ~ 1 b = q

Quindi, un metodo iterativo è consistente solo se:

0- 1

q B)A- b

=

Teorema:

Condizione necessaria e sufficiente affinché un metodo iterativo consistente sia convergente è che il

< 1

raggio spettrale della matrice di iterazione sia strettamente minore di 1: p (B)

I

maxlà,

p(B) := autovalori di B

Ài

Oss:

Calcolare il raggio spettrale sarà però dispendioso. Vedremo condizioni più semplici che saranno

sufficienti a garantire la convergenza.

Dim: +

x(k+l) Bx(k) q

=

- Se il metodo è convergente passando al limite:

+ q

x' Bx"

=

- Facendo la differenza:

x' - x(k+l) B(x' - x(k))

=

e(k+l) Be(k)

= k

e(k) errore al passo

:=

- E anche:

e(k) Be(k-l) ~ e(k+l) B e(k-l) ~

= = 2

Con eCO) x' - x(O) x(O) vettore iniziale

= :=

- Se scelgo x(O) affinché eCO) sia autovettore relativo all'autovalore À:

Be(O) Àe(O)

=

B e(O) ÀBe(O) À e(O)

= =

2 2

Bke(O) Àke(O)

=

- Convergenza:

O lim e(k+l) lim B(k+l)e(O) lim À(k+l)e(O)

= = =

k 00 k 00 k 00

--> --> -->

< <

1 1

Occorre che IÀI da cui p(B)

Teorema: Bk <

Sia B allora lim O p(B) 1

=

E (Cnxn H

k-v+co

- Se il metodo è consistente: Bk

lim e(k) lim Bke(O) eCO) lim O

= = =

00 +00 +00

k-v+ k-» k-»

Oss:

- Dalle proprietà delle norme matriciali indotte:

:2:

IIBII·llxll IIBxl1 IÀI·llxll

=

Quindi, per ogni autovalore di vale IÀI ::; IIBII da cui:

B

p(B) ::; IIBII

< <

1 1

- Se IlB Il allora p (B) e il metodo è consistente (condizione sufficiente).

Una strategia per costruire metodi iteratori consistenti è decomporre matrice del sistema lineare:

A

+

1 1

Nx b

= M- M-

X + ±

Ax b A M- N da cui oppure: x M-

1 Nx M-

1 b M-

1 Ax

= = = =

{ + 1

M- (b -

x Ax)

=

- Da cui il metodo iterativo: + :2:

Mx(k+l) Nx(k) b k O

= +

(Oppure: x(k+l) x(k) M- r(k) con r(k) b - Ax(k) )

= =

1

- Quindi occorrerà che sia invertibile con un basso costo computazionale.

M

Oss: n2 nxn,

R

Poiché il prodotto matrice vettore Bx(k) ha costo computazionale se B E

il metodo iterativo sarà competitivo con un metodo diretto se la "convergenza" avverrà in un

<

numero di passi h.

+ M-1b

= =

x(k+l) M-l Nx(k) con B M-l N

Metodo di Jacobi +

A A)

= = =

M - N D - (D - D - (E F)

D matrice diagonale: >

= j

Eij -aij i

E matrice tridiagonale inferiore: { O

=

Eij altrimenti

<

= j

Fij -aij i

F matrice tridiagonale superiore: { O

=

Fij altrimenti

il

- Quindi processo iterativo sarà:

x(O) vettore iniziale assegnato

{ + + k 0,1, ...

= =

Dx(k+l) (E F)x(k) b

l +

=

BJ D-l (E F)

x(O) vettore iniziale assegnato con

+ +

{ [

D-1(E D-1b 1

qJ D- b

=

x(k+l) F)x(k) =

k 0,1, ...

=

a a1n

a12 13 ...

o -- --

-- a a

a ll ll

ll a23 a2n

a21 ...

-- --

O

-I a a

=

BJ a22 22 22

an1 an2 an3 ... O

-- -- --

ann ann ann

- Metodo di [acobì per componenti:

+ + +

a X1 a12x2 a1nxn : b1

ll + + +

a21 Xl a22x2 a2nxn - b2

{ + + + =

an1xl an2x2 annxn bn n

__2_ '"

n

b

= a .x,

X L

-

a a

n nj J

n nn j=l

j*n

x(O) assegnato n O, ... ,

i = n

1 con

(k+l) _ (k) + =

k 0,1, ...

Xi - - - '" aijx. bi

L

a .. J

r j=l

Il j*i

Oss:

Questo metodo è fortemente parallelo, quindi con n processori posso costruire

contemporaneamente tutte le componenti perché sono indipendenti.

Metodo di Gauss-Seidel

A M - N (D - E) - F

= = (D, E, F vedi metodo [acobì)

il

- Quindi processo iterativo sarà:

x(O) vettore iniziale assegnato

{ +

(D - k 0,1, ...

= =

E)x(k+l) Fx(k) b

l (D -

=

x(O) vettore iniziale assegnato BGS E)-lF

con [

+

{ (D - (D - (D -

=

x(k+l) E)-l Fx(k) E)-lb =

qGS E)-l

=

k 0,1, ...

- Metodo di Gauss - Seidel per componenti:

1 (

(k+l) _ (k) (k) (k) (k))

Xl - - b1 - a1ZxZ - a x3 - a14x4 - ... - a1nxn

13

a

ll

1 (

(k+l) _ (k))

(k) (k) (k)

Xz - - bz - aZ1x1 - aZ3x3 - aZ4x4 - ... - aznxn

a

22 +

k 1

xik+l) ~ utilizzare al passo

1 (

(k+l) _ (k) (k) (k) (k))

x3 - - b3 - a31x1 - a xZ - a34x4 - ... - a3nxn

32

a33 (k+l) (k+l)

Xl Xz

1 (

(k+l) _ (k) (k) (k) (k) )

Xn - - bn - an1x1 - anZxZ - an3x3 - ... - an(n-1)xn-1

ann (k+l) (k+l) (k+l) (k+l)

Xl Xz X3 Xn-1

(k+l) ., (k+l). h' (k+l) .

l l

Q d

- uan o ca co o Xz posso gia usare Xl anzic e Xl OSSIa:

+ +

1(Ex(k+l)

= D-

x(k+l) Fx(k) b)

x(O) vettore iniziale assegnato O, ... ,

i = n

f con

_!_ k 0,1, ...

=

x~k+l) (b. - ~ a ..x(k+l) _ a ..x(k)) =

L L

a ..

I I IJ J IJ J

j=l j=i+l

Il

Oss:

Il metodo di Gauss-Seidel è un metodo sequenziale. Per risparmiare memoria, dal punto di vista

computazionale, mi basta un solo vettore in cui memorizzare i dati per sostituzione:

Xl Xl

(k)ì ( (k+l)

(k) (k+l)

X X

z z

(k) ~ (k+l)

x x

3 3

(k+l)

X n

Convergenza

Come già detto:

- Affinché un metodo iterativo sia convergente deve valere che:

s 1

p(B) < 1

- IlB Il è condizione sufficiente n

n x,

< 1 =

- Idet(B) I è condizione necessaria poiché det(B) i=l L

< tr'(B) =

- Itri n (traccia) è condizione necessaria poiché Ài

Oss:

La convergenza sarà tanto più rapida più piccolo è p(B):

= = =

e(k) Be(k-l) e(k-l) Be(k-Z) ... e(k) Bke(O) da cui:

Ile(k)11 ::; IIBkll·lle(O)11 ~ IIBkl1 fattore di riduzione dell'errore iniziale

:=

Media geometrica (riduzione dell'errore):

._ k/lle(l)II.lle(Z)11 Ile(k)11

k

6 ·- Ile(O)11 Ile(l)II"'lle(k-l)11

Teorema:

Sia B e sia 11·11una qualsiasi norma indotta, Allora:

E (Cnxn

Hm = p(B)

..J

k~ 0

11 --11

k-r+co

Oss: k

Approssimativamente se voglio ridurre l'errore di dovrò effettuare iterazioni:

110

1 1

k- - ----

[p(B)]k-- da cui

10

Def. <

- Il 1

metodo di Jacobi converge se: p(B,) <

- Il 1

metodo di Gauss-Seidel converge se: p(B

Gs)<

Dettagli
Publisher
A.A. 2015-2016
45 pagine
SSD Scienze matematiche e informatiche MAT/08 Analisi numerica

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Mr.Al di informazioni apprese con la frequenza delle lezioni di Calcolo numerico e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Università degli Studi di Parma o del prof Scienze matematiche Prof.