Numerical Methods Problems and Solutions

Cholesky-decomposition of a Matrix When a coefficient matrix of a linear system of equations is positive definite and symmetric, then Cholesky decomposition can be used. A positive definite symmetric matrix satisfies the condition $x^{T}Ax > 0$ and the elements of the lower $L$ and upper $U$ triangular matrix satisfies the condition $L_{i,j}=U_{j,i}$ i.e. $U = L^{T}$ and hence $A = LL^{T}$ . A symmetric matrix is positive definite if all its diagonal elements are positive and the diagonal element is larger than the sum of all other elements in that row (i.e. diagonally dominant). Example: choleskydeco_example function [X,C] = choleskydecomposition(A,B) % Applicable to only symmetric positive definite matrix % Input : % A : Coefficient matrix % B : right hand vector % Output : % X : Solution vector % C : Upper triangular metrix [n,m] = size(A); % rank of matrix A C = zeros(n,n); for i=1:n

Backward Substitution Backward Substitution Consider a Upper Triangular matrix U of dimension n, U x = b $$\begin{bmatrix} u_{1,1}&u_{1,2}&\dots&u_{1,n}\\ 0&u_{2,2}&\dots&u_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\dots&u_{n,n} \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ \vdots\\ x_{n} \end{bmatrix} = \begin{bmatrix} b_{1}\\ b_{2}\\ \vdots\\ b_{n} \end{bmatrix}$$ Solving Procedure: $$x_{n} = \frac{b_{n}}{u_{n,n}}$$ Moving to ${n-1}^{th}$ row, there are two coefficients related to $x_{n}$(already known) and $x_{n-1}$ (unkown). $$u_{n-1,n-1}x_{n-1}+u_{n-1,n}x_{n}=b_{n-1}$$ Solving for unknown $x_{n}$, we have $$x_{n-1} = \frac{b_{n-1}-u_{n-1,n}x_{n}}{u_{n-1,n-1}}$$ Generalizing for $i^{th}$ row, $$x_{i} = \frac{1}{u_{i,i}}\left( b_{i}-\sum_{j=i+1}^{n}u_{i,j}x_{j} \right)$$ A