Calcolo numerico

Condizionamento, matrici di Hilbert e Vandermonde

cond(A) Calcola il condizionamento con norma 2

cond(A,n) Calcola il condizionamento con norma n

cond(A,inf) Calcola il condizionamento con norma ∞

format rat

format short e

format long e

Matrice di Hilbert

A=hilb(n) Genera la matrice di Hilbert

H_n = (1 1/2 ... 1/n)(1/2 1/3 ... 1/n+1)(... ... ... ...)(1/n+1 1/n+2 ... 1/2n+1)

Matrice di Vandermonde

A:=vander(x) Genera la matrice di Vandermonde, partendo dal vettore x

V_n = (1 x₁ x₁² ... x₁ⁿ)(1 x₂ x₂² ... x₂ⁿ)(... ... ... ... ...)(1 x_n x_n² ... x_nⁿ)

x=[1 1,5 2 2,5 3,0] ⇒ V(x)=( 1 1 1 1 1 1)( 1 3,0635 3,3750 2,25 1,5 1)( 36 8 4 2 1 1)( 36 33,0625 15,6250 6,25 2,5 1)( 81 27 9 3 1 1)

Risoluzione con il metodo delle eliminazioni di Gauss

A=hilb(5)

b=sum(A,2);

x=A\b;

format rat

hilb

A=: hilb(6)

b=sum(A)

x=A\b

v=vander(x)

cond(A) calcola il condizionamento con norma 2

cond(A,n) calcola il condizionamento con norma n

cond(A,inf) calcola il condizionamento con norma ∞

format rat

format short e

format long e

Matrice di Hilbert

A = hilb(n) Genera la matrice di Hilbert

H_n = ¹⁄₁ ¹⁄₂ ¹⁄_n ¹⁄_n+1 1 ¹⁄₃ ¹⁄_n+1 ¹⁄_2n+1

Matrice di Vandermonde

= vander(x) Genera la matrice di Vandermonde, partendo dal vettore x

Vn = 1⁄x11 1⁄x2 1⁄1

x = [1 1.5 2 2.5 3 0] ⇒ V(x) =1 3,0615 3,3750 2,25 1,5 136 8 236 39,0625 15,6250 6,25 3,15 181 9 3

Risoluzione con il metodo delle eliminazioni di Gauss

A = hilb(5)

b = sum(A,2)

x = A\b

condizionamento

format rat

hilb

A = hilb(5)

b = sum(A)

x = A\b

format short e

format long e

Matrice dei coefficienti

A triangolare inferiore

a_ii ≠ 0 i = 1, ..., n

| a₁₁ x₁ = b₁

{ a₂₁ x₁ + a₂₂ x₂ = b₂

| ...

{ a_n1 x₁ + a_n2 x₂ + ... + a_nn x_n = b_n

x₁ = ^b₁/_a11 ; x₂ = ^{b₂ - a₂₁ x₁}/_a22 ; ... ; x_n = ^{b_n - ∑_j=1n-1a_njx_j}/_ann

Metodo di sostituzione in avanti

x₁ = ^b₁/_a11 ; x_i = ^{b_i - ∑_j=1i-1a_ijx_j}/_aii ; i = 2, ..., n

Costo computazionale ⁿ²/₂

Script

function x = avanti(A, b)

n = length(b);

x = zeros(n, 1);

x(1) = b(1)/A(1, 1);

for i = 2:n

s = A(i, 1:i-1) * x(1:i-1);

x(i) = (b(i) - s)/A(i, i);

end

Schema riassuntivo

K = 1, ..., n-1 i = k+1, ..., n

m_ik = a_ik (k) / a_kk (k)

a_ij (k+1) = a_ij (k) - m_ik a_kj (k), j = k+1, ..., n

b_i (k+1) = b_i (k) - m_ik b_k (k)

x_k = b_k (k) / a_kk (k)

x_k = x_k - a_ji ^(k) x_j (k)

k = n-1, ..., 1

Se A è simmetrica e non si effettuano scambi, la sottomatrice degli elementi (( (3x3 matrix)) è simmetrica ∀k. Il costo computazionale diventa n³/6

A ogni passo k gli elementi a_ij ^(k) e b_i ^(k) possono essere memorizzati all'interno della matrice A e del vettore b nelle posizioni i e i rispettivamente. I moltiplicatori m_ik possono essere memorizzati nella matrice A nelle posizioni ik.

Script

function x = gauss_noscambi (A,b)

n = length(b);

for k = 1:n-1

for i = k+1:n

A (i,k) = A (i,k) / A (k,k);

for j = k+1:n

A (i,j) = A (i,j) - A (i,k) * A (k,j);

end

end

x = zeros (n,1);

x(n) = b(n) / A (n,n);

for i = n-1:-1:1

x(i) = (b(i) - A (i,i+1:n) * x(i+1:n)) / A (i,i);

end

Osservazione

Affinché si possa applicare il metodo di Gauss è necessario che al passo k risulti a_kk ^(k) ∗ 0 della matrice diagonale dominante per righe, diagonale dominante per colonne

Condizione soddisfatta se A è simmetrica e definito positiva

Risol