LU factorization and iterative methods

LU factorization and iterative methods

LU factorization and iterative methods

Emma Perracchione

Corso di Calcolo Numerico per Ingegneria Meccanica - Matr. PARI (Univ. PD)

Gli esercizi sono presi dal libro: S. De Marchi, D. Poggiali, Exercices of numerical calculus with solutions in Matlab/Octave.

A.A. 2018/2019

Materiale

Materiale

TUTTO IL MATERIALE SI TROVA AL SEGUENTE LINK E VERRA’

AGGIORNATO AD OGNI LEZIONE.

https://www.math.unipd.it/~emma/CN1819.html

LU factorization and iterative methods Remarks

Gauss and LU

Let us suppose that we need to solve a system of the form Ax = b, with b = (b1, . . . bn)^T.

We first see that if A admits a LU factorization (WITHOUT

PIVOTING), then we have LUx = b. Thus we reduce to solving two diagonal systems of the form

Ly = b.

and

Ux = y.

The Matlab function lu recalled as [L, U, P] = lu(A);

automatically makes the pivoting. In that case y = L \ (P*b); x = U \ y;

Exercises

Exercise 1

Exercise

Given Ax = b, with x = (x1, x2, x3)^T,b = (b1, b2, b3)^T and A ∈ R^3×3 given by





13 13 0

2 2 − ε 4

1 3 17



,

and ε ∈ R. Use the function for LU factorisation without pivoting (LUnoPiv). Then, write a script Esercizio1.m so that:

1 Fixed ε = 10⁻¹⁵, computes b such that the exact solution is xVera = [2;5;7];. Then compute[L, U] = LUnoPiv(A);

2 Using the above factorization, find the solution of the linear system xLUnoPiv and compute the relative error in 2-norm.

3 Repeat the exercise with the function Matlab lu.m.

LU factorization and iterative methods Remarks

Jacobi

Let us suppose that we need to solve a system via Jacobi scheme of the form Ax = b, with b = (b1, . . . , b_n)^T.

We have that Jacobi generates a sequence x^(k+1) = Jx^(k)+b1,

where J = M⁻¹N. b1 = M⁻¹b and M and N are so that A = M − N = D − (D − A),

where D=diag(A).

Observe that for its implementation we need A, b, an initial condition x0, a tolerance tol, and a maximum number of iterations kmax.

Exercises

Exercise 2

Exercise

Given Ax = b, with x = (x1, x₂, x₃, x₄, x₅, x₆)^T,

b = (b1, b2, b3, b4, b5, b6)^T and A ∈ R^6×6 given by A = toeplitz([4 1 zeros(1,4)]);. Use the function for Jacobi’s method Jacobi.m and write a script Esercizio2.m so that:

1 Computes b such that the exact solution is xVera = [2;2;2;2;2;2];.

2 Solve the system and check the convergence via Jacobi.

LU factorization and iterative methods Jacobi

The function

function [x,iter,err]=Jacobi(A,b,x0,tol,kmax)

% Jacobi’s iterative method for the solution of Ax=b

% with tolerance ’tol’ and maximum number of iteration

% ’kmax’

D=diag(diag(A)); DI=diag(1./diag(A));

J=-DI*(A-D);

disp([’Spectral radius of the iteration matrix = ’,...

num2str(max(abs(eig(J))))]);

b1=DI*b; x1=J*x0+b1; k=1;

while(norm(x1-x0)>tol*norm(x1) && k<=kmax) x0=x1;

x1=J*x0+b1;

err(k)=norm(x1-x0,inf);

k=k+1;

end