Contents

• 1  Introduction
  • 1.1  Linear systems
  • 1.2  Numerical methods for solving linear systems
  • 1.3  Gaussian method
• 2  Exercise
  • 2.1  Gaussian elimination
  • 2.2  Back-substitution

Introduction

Linear systems

In this unit, we will solve systems of linear equations with the same number of equations as unknowns with a non-singular coefficient matrix. Therefore, the system will have a unique solution.

Given the numbers $a_{ij}$ and $b_{j}$ for $i,j=1,2,\ldots,n$ we try to find the values $x_{1},x_{2},\ldots,x_{n}$ that fulfill the set of $n$ linear equations

$$ \begin{array}{cll} a_{11}x_{1}+a_{12}x_{2}+\ldots+a_{1n}x_{n} & = & b_{1},\\ a_{21}x_{1}+a_{22}x_{2}+\ldots+a_{2n}x_{n} & = & b_{2},\\ \vdots\\ a_{n1}x_{1}+a_{n2}x_{2}+\ldots+a_{nn}x_{n} & = & b_{n}. \end{array} $$

The system, in matrix notation, will be

$$ \left(\begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n1} & \ldots & a_{nn} \end{array}\right) \left(\begin{array}{c} x_{1}\\ x_{2} \\ \vdots \\ x_{n} \end{array}\right) = \left(\begin{array}{c} b_{1}\\ b_{2} \\ \vdots \\ b_{n} \end{array}\right) $$

that is

$$A\mathbf{x}=\mathbf{b}$$

Numerical methods for solving linear systems

The methods can be:

Direct methods

• Solution is computed in a finite number of steps.
• The only errors are from rounding.
• Good for solving
  • small systems,
  • large systems with a full (with few zeros) coefficients matrix.

We will study the methods of Gauss, Gauss-Jordan and LU Decomposition.

Iterative methods

• They build a sequence of approximate solutions converging to the exact solution.
• In addition to rounding, truncation errors arise.

We will study the methods of Jacobi and Gauss-Seidel.

Gaussian method

The Gaussian method performs two steps:

1. Gaussian elimination or Triangularization. Transformation of the original system of linear equations into a upper triangular matrix system with the same solutions. For this, the following operations are carried out:
   • Multiply a row by a real one and add it to another row: $r_{i}\rightarrow r_{i}+\lambda r_{j},\quad j\neq i$
   • Swap rows: $r_{i}\leftrightarrow r_{j}$ (if we use the pivot strategy)
2. Back-substitution. Resolution of the upper triangular system using the back-substitution algorithm. It consists of obtaining the unknowns starting with the last and proceeding upwards until the first equation obtaining a new unknown per equation.

Exercise

Consider the system $A\mathbf{x}=\mathbf{b}$ with

$\require{xcolor}$

$$ A=\left(\begin{array}{crc} 1 & 1 & 3\\ 3 & 0 & 1\\ 1 & -2 & 1 \end{array}\right) \quad \mathbf{b}=\left(\begin{array}{c} -2\\ -1\\ -3 \end{array}\right) $$

Find $\mathbf{x}$ using Gauss method.

---

The system we want to solve is

$$ \begin{array}{rrrrrrr} x & + & y & + & 3z & = & -2\\ 3x & & & +& z & = & -1\\ x & -& 2y &+& z & = & -3 \end{array} $$

Gaussian elimination

We construct the augmented matrix of the system, which is the matrix $A$ with the column matrix $\mathbf{b}$ added as the fourth column.

The pivot is always an element of the main diagonal. The first pivot is in the first row and therefore in the first column.

We make zeros below the pivot, $\mathbf{{\color{red}1}},$ in the first column.

• The row of the pivot is the first row. And the pivot is now ${\color{red}{a_{11}}}.$
• The row of the pivot is left as it is.
• The row of the pivot is added to the other rows multiplied by a factor that is constructed with the pivot in the denominator and the element below the pivot in the numerator ($\mathbf{\color{blue}3}$ for the row $2$ and $\mathbf{\color{ForestGreen}1}$ for row $3$).

$$ \begin{array}{c} r_{1}\\[5pt] r_{2}\\[10pt] r_{3} \end{array}\left(\begin{array}{rrr|r} \mathbf{{\color{red}1}} & 1 & 3 & -2\\[5pt] \mathbf{\color{blue}3} & 0 & 1 & -1\\[10pt] \mathbf{\color{ForestGreen}1} & -2 & 1 & -3 \end{array}\right)\begin{array}{rrl} r'_{1} & = & r_{1}\\ r'_{2} & = & r_{2}-\dfrac{\mathbf{\color{blue}3}}{\mathbf{{\color{red}1}}}r_{1}\\ r'_{3} & = & r_{3}-\dfrac{\mathbf{\color{ForestGreen}1}}{\mathbf{{\color{red}1}}}r_{1} \end{array} $$

We make zeros under the pivot $\mathbf{{\color{red}{-3}}}$ in the second column.

• The pivot row is the second row. And the pivot is now ${\color{red}{a_{22}}}.$
• The row of the pivot and the rows above the pivot are left as they are.
• The row of the pivot is added to the remaining row multiplied by a factor that is constructed with the pivot in the denominator and the element below the pivot in the numerator, $\mathbf{\color{blue}{-3}}$.

$$ \begin{array}{c} r'_{1}\\[5pt] r'_{2}\\[5pt] r'_{3} \end{array}\left(\begin{array}{rrr|r} 1 & 1 & 3 & -2\\[5pt] 0 & \mathbf{{\color{red}{-3}}} & -8 & 5\\[5pt] 0 & \mathbf{\color{blue}{-3}} & -2 & -1 \end{array}\right)\begin{array}{rrl} r''_{1} & = & r'_{1}\\[5pt] r''_{2} & = & r'_{2}\\ r''_{3} & = & r_{3}-\dfrac{\mathbf{\color{blue}{-3}}}{\mathbf{{\color{red}{-3}}}}r'_{2} \end{array} $$

And we already have an upper triangular matrix (with zeros below the main diagonal).

$$ \begin{array}{c} r''_{1}\\ r''_{2}\\ r''_{3} \end{array}\left(\begin{array}{rrr|r} 1 & 1 & 3 & -2\\ 0 & -3 & -8 & 5\\ 0 & 0 & 6 & -6 \end{array}\right) $$

Back-substitution

Let's go back to the notation with equations. The triangular system is

$$ \begin{array}{rrrrrrr} & x & + & y & + & 3z & = & -2\\ & & - & 3y & - & 8z & = & 5\\ & & & & & 6z & = & -6 \end{array} $$

Solving for $z$ in the third equation

$$z = -1$$

Solving for $y$ in the second equation

$$y =\frac{5+8z}{-3}=\frac{5-8}{-3}=1$$

And $x$ in the first one

$$x = -2-y-3z = -2-1+3=0$$

and the solution of the system is

$$\fbox{ $x = 0 \quad y = 1 \quad z = -1$}$$