Che materia stai cercando?

Calcolo numerico

Appunti di Calcolo numerico basati su appunti personali del publisher presi alle lezioni della prof. Ruggero dell’università degli Studi di Ferrara - Unifi, facoltà di Scienze matematiche fisiche e naturali, Corso di laurea in informatica. Scarica il file in formato PDF!

Esame di Calcolo Numerico docente Prof. V. Ruggero

Anteprima

ESTRATTO DOCUMENTO

6 Metodo dei Grafi

Fattori di Amplificazione y

x ±

Somma: ε =

x±y ε ε

x±y x±y

Prodotto: ε = ε + ε

xy x y

Divisione: ε = ε ε

xy x y

= αε

Potenza: ε α x

x

√ 1

n

Radice: x = ε x

n

7 Metodi di convergenza

Condizione necessaria sufficiente per una matrice convergente:

ρ(A) < 1

Condizione necessaria ma non sufficiente: 1

|det(G)| |tr(G)|

< 1 e < n Velocitá di convergenza: R (G)

7.1 Metodo di Iacobi ⇒

Se il raggio spettrale ρ < 1 Metodo di Iacobi converge

−logρ(J)

Velocitá di convergenza= −

Teorema: Sia A di ordine n simmetrica e sia 2D A definita positiva.

Allora A é definita positiva se e solo se il metodo di Iacobi converge.

7.2 Metodo di Gauss - Seidel

−1

G = (D L) U

Se A é:

• strettamente diagonale dominante

• irriducibilmente diagonale dominante ||G|| ||J||

allora sia Iacobi che Gauss-Seidel convergono e <

∞ ∞

Teorema: Sia A quadrata di ordine n simmetrica con a > 0 allora a é

ii

definita positiva, se e solo se, il metodo di Gauss-Seidel é convergente.

6

7.3 SOR

Tecnica di rilassamento o estrapolazione:

• ω = 1: fornisce il metodo di partenza

• ω > 1: sovrarilassamento

• ω < 1: sottorilassamento Teorema: Sia A simmetrica con a > 0 e

ii

sia 0 < ω < 2 allora A é definita positiva se e solo se il metodo SOR

converge.

7.4 Convergenza Globale di Newton

f (x )

− k

Iterazione di Newton: x m

k f (x )

k+1

Newton converge globalmente se

• f (a) < 0 e f (b) < 0

0

• 6 ∈

f (x) = 0 [a, b]

00 00

• ≤ ≥

f (x) 0 oppure f (x) 0

0 0

• |f ≤ − |f ≤ −

(b)| (b a)|f (b)| oppure (a)| (b a)|f (a)|

7.5 Altre considerazioni

Se A é tridiagonale con elementi diagonali non nulli, valgono le seguenti

asserzioni:

• −µ

se µ é autovalore della matrice di Iacobi J anche é autovalore di J

• se µ é autovalore di J e vale la relazione:

2 2 2

(λ + ω 1) = ω λµ allora λ é autovalore di G(ω)

• se λ é un autovalore non nullo di G(ω) e vale la relazione

2 2 2

(λ + ω 1) = ω λµ allora µ é un autovalore di J

8 Info Generali

Problema di malcondizionamento: permutando di poco i dati iniziali si

trovano soluzioni diverse r=b-Aw

Se r tende a 0 allora probabilmente w é soluzione attendibile, infatti:

7

||x−w|| ||r||

−1

||A||||A ||

Err = <=

relativo ||x|| ||b|| ||r||

−1

||A||||A || ||A||

k(A) = oppure k(A) = ||b|| ≥

In una norma naturale (per matrici quadrate), vale che k(A) 1

−1

||I|| ||AA || ≤

1 = = k(A)

se k(A) 1 é malcondizionata

'

se k(A) 1 é bencondizionata

Il numero di condizionamento di una matrice esprime quanto una matrice

é vicina alla singolaritá

Piú in generale:

max||Ax||

k(A) = min||Ax||

Tuttavia il calcolo dell’inversa é molto complesso, si occorre dunque ad

una stima del numero di condizione:

||x−w||

Sottostima: ||r|| 8

9 Codici Utili

% es 1

clear all

close all

for n=0:2:16

s=1+sum(1./[2:2:n])-log(n);

fprintf(’n=%g appr=%g\n’,n, s);

end

% es 2

close all

clear all

n=10;

A=hilb(n);

sol=[1:2:2*n-1]’;

%%%%%%%%%%%%%

b=A*sol;

[R,p] = chol(A);

if p~=0

error(’A non definita positiva’);

else

y=sollower(R’,b);

x=solupper(R,y);

fprintf(’Soluzione calcolata con operatore Matlab\n’)

xx=A\b;

for i=1:n

fprintf(’x=%g xx=%g\n’,x(i),xx(i));

end

fprintf(’\n’);

r=b-A*x;

resnorm=norm(r,inf)/norm(b,inf);

fprintf(’norm(r)/norm(b)=%g\n’,resnorm);

ee=sollower(R’,r);

ee=solupper(R,ee);

KA=norm(ee,inf)/norm(r,inf)*norm(A,inf);

fprintf(’ stima del numero di condizione =%g\n’, KA);

fprintf(’stima dell’’errore relativo=%g\n’, KA*resnorm);

end 9

%es 3

clear all

close all

A=[1 0 1

0 1 1

2 -1 2];

b=[1 0 1]’;

[L,R,P]=gauss2(A);

y=sollower(L,b(P));

x=solupper(R,y);

% es 4

close all

clear all

n=30;

D=10+1:2:10+2*n-1;

D=D’;

D_1=-1+1./[2:n+1];

D_1=D_1’;

D1=-sqrt(1:2:2*n-2);

D1=[0;D1’];

A=spdiags([D_1, D,D1],[-1 0 1],n,n);

xex=ones(n,1);

b=A*xex;

x=sparse(n,1);

maxit=100;

tol=1e-6;

[ x, k ] =g_s(A,b,x,maxit,tol);

err=norm(x-xex,inf);

fprintf(’errore=%g\n’,err);

fprintf(’numero iterazioni=%g\n’,k);

fprintf(’residuo normalizzato=%g\n’,norm(b-A*x,inf)/norm(b,inf));

10


PAGINE

12

PESO

238.65 KB

PUBBLICATO

5 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Ferrara - Unife
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher alan.bimbati 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à Ferrara - Unife o del prof Ruggero Valeria.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in informatica

Data mining
Appunto
Sistemi operativi
Appunto