Software Publications For Students Links About Author
PL
EN
For Students → PMiKNoM Seminars → Class 4
The content of this page is available under the Creative Commons Attribution-ShareAlike License. Valid XHTML 1.0 Transitional Valid CSS! Last modified: 23rd of March 2020
PMiKNoM Seminars
Class 1
Class 2
Class 3
Class 4
Class 5
Class 6
Class 7 - Colloquium I
Class 8
Class 9
Class 10
Class 11 and 12
Class 13 - Colloquium II
Class 14 - The retake of the Colloquium
Class 15 - Assessment Colloquium
PMiKNoM Project
Sustainable Development
MSc and BSc theses
Print content

Numerical solution for systems of linear equations

PMiKNoM seminars - class 4

Introduction

Gauss Method

Exercises
Solve the following equations using Gauss method:
a) $$ \left[ \begin{array}{ccc|c} 2&2&1&1 \\ 1&3&2&2 \\ 2&4&2&2 \\ \end{array} \right] = $$
b) $$ \left[ \begin{array}{ccc|c} 2&3&4&2 \\ 4&5&6&3 \\ 3&2&3&5 \\ \end{array} \right] = $$
c) $$ \left[ \begin{array}{ccc|c} 2&2&2&2 \\ 21&2&2&2 \\ 2&22&2&2 \\ \end{array} \right] = $$
d) $$ \left[ \begin{array}{ccc|c} 2&4&0&2 \\ 1&4&1&2 \\ 0&1&1&3 \\ \end{array} \right] = $$
e) $$ \left[ \begin{array}{cccc|c} 2&3&0&0&1 \\ 1&2&1&0&2 \\ 0&3&2&4&5 \\ 0&0&1&3&4 \\ \end{array} \right] = $$

Tri-diagonal matrix

General equations describing the tri-diagonal matrix reads:
$$ \left\{ \begin{array}{l} d_1 x_1 + c_1 x_2 = b_1 \\ a_{i-1} x_{i-1} + d_i x_i + c_i x_{i+1} = b_i \text{, for } i=2..n-1\\ a_{n-1} x_{n-1} + d_n x_n = b_n \end{array} \right. $$
$$ \left[ \begin{array}{ccccccccc|c} d_1 & c_1 & 0 & 0 & \cdots & 0 & 0 & 0 & 0 & b_1 \\ a_1 & d_2 & c_2 & 0 & \cdots & 0 & 0 & 0 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & \cdots & 0 & 0 & 0 & 0 & b_3 \\ 0 & 0 & a_3 & d_4 & \cdots & 0 & 0 & 0 & 0 & b_4 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & d_{n-3} & c_{n-3} & 0 & 0 & b_{n-3} \\ 0 & 0 & 0 & 0 & \cdots & a_{n-3} & d_{n-2} & c_{n-2} & 0 & b_{n-2} \\ 0 & 0 & 0 & 0 & \cdots & 0 & a_{n-2} & d_{n-1} & c_{n-1} & b_{n-1} \\ 0 & 0 & 0 & 0 & \cdots & 0 & 0 & a_{n-1} & d_n & b_n \\ \end{array} \right] $$

Thomas Method - eduction

Solution of tri-diagonal matrix `n \times n` shown using the example of the set of `n=4` linear equations:

$$ \left[ \begin{array}{cccc|c} d_1 & c_1 & 0 & 0 & b_1 \\ a_1 & d_2 & c_2 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$
We divide the first row by `d_1`, obtaining:
$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ a_1 & d_2 & c_2 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$
where:
`\text{new } c_1=c_1/d_1 `
`\text{new } b_1=b_1/d_1 `
From the second row, we substract the first row multiplied by `a_1`, obtaining:
$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & d_2 & c_2 & 0 & b_2 \\ 0 & a_2 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$
where:
` \text{new } d_2=d_2 - c_1 \cdot a_1 `
` \text{new } b_2=b_2 - b_1 \cdot a_1 `
This way, in the first column we have `1` at the diagonal and `0` directly below it.

We perform analogical calculations for the second column, obtaining:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & d_3 & c_3 & b_3 \\ 0 & 0 & a_3 & d_4 & b_4 \\ \end{array} \right] $$
where:
` \text{new } c_2=c_2/d_2 `
` \text{new } b_2=b_2/d_2 `
` \text{new } d_3=d_3 - c_2 \cdot a_2 `
` \text{new } b_3=b_3 - b_2 \cdot a_2 `
And we perform analogical calculations for the third column, obtaining:
$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & d_4 & b_4 \\ \end{array} \right] $$
where:
` \text{new } c_3=c_3/d_3 `
` \text{new } b_3=b_3/d_3 `
` \text{new } d_4=d_4 - c_3 \cdot a_3 `
` \text{new } b_4=b_4 - b_3 \cdot a_3 `

Then, we divide the last row by `d_4`, obtaining:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$
where:
` \text{new } b_4=b_4/d_4 `

In order to remove the value of `c_3`, substrast the last row multiplied by `c_3` from the third row, to get:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & 0 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$
where:
` \text{new } b_3 = b_3 - c_3 \cdot b_4 `
Analogical operations are performed for all the other rows, to obtain:
$$ \left[ \begin{array}{cccc|c} 1 & 0 & 0 & 0 & b_1 \\ 0 & 1 & 0 & 0 & b_2 \\ 0 & 0 & 1 & 0 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$
where:
` \text{new } b_2= b_2 - c_2 \cdot b_3`
` \text{new } b_1= b_1 - c_1 \cdot b_2`

Thomas Method - summary

First Loop

After the set of instructions are performed for all rows `(i)` starting from the first `(1)` until the last but one `(n-1)`, we obtain:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & d_4 & b_4 \\ \end{array} \right] $$
after performing `i=1` to `n-1` sets of instructions:
$$ \left\{ \begin{array}{l} c_i=c_i/d_i \\ b_i=b_i/d_i \\ d_{i+1}=d_{i+1} - c_i \cdot a_i \\ b_{i+1}=b_{i+1} - b_i \cdot a_i \end{array} \right. $$
Instruction

Now we divide the last row by `d_n`, obtaining:

$$ \left[ \begin{array}{cccc|c} 1 & c_1 & 0 & 0 & b_1 \\ 0 & 1 & c_2 & 0 & b_2 \\ 0 & 0 & 1 & c_3 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$
after performing:
` b_n=b_n/d_n `
Second Loop

After the set of instructions are performed for all rows `(i)` starting from the last but one `(n-1)` until the first `(1)` with step `(-1)` we obtain:

$$ \left[ \begin{array}{cccc|c} 1 & 0 & 0 & 0 & b_1 \\ 0 & 1 & 0 & 0 & b_2 \\ 0 & 0 & 1 & 0 & b_3 \\ 0 & 0 & 0 & 1 & b_4 \\ \end{array} \right] $$
after performing `i=n-1` to `1` (step `-1`) instructions:
$$ b_i = b_i - c_i \cdot b_{i+1} $$

Thomas Method - program's algorithm

  1. Declare constant `n` and the arrays `a(1 \text{ to } n-1)`, `d(1 \text{ to } n)`, `c(1 \text{ to } n-1)` and `b(1 \text{ to } n)`.
  2. Assign the values from the spreadsheet to all elements of arrays `a`, `b`, `c` oraz `d`.
  3. Write the first loop (see eduction).
  4. Write the instruction `b(n)=b(n) \text{/} d(n)`.
  5. Write the second loop (see eduction).
  6. Display results.

Additional materials: