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 ∈ R3×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−15, 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, . . . , bn)T.
We have that Jacobi generates a sequence x(k+1) = Jx(k)+b1,
where J = M−1N. b1 = M−1b 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, x2, x3, x4, x5, x6)T,
b = (b1, b2, b3, b4, b5, b6)T and A ∈ R6×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
