Numerical Methods for Science and
Engineering
Chapter Two
Solutions to Linear System
Iterative Method
Solution of Linear System by Iterative Method
Objective: Solve the system of linear equations
An iterative method converges, for any choice of the first approximation,
• if every equation satisfies the condition that the magnitude of the coefficient of solving
variable
▪ is greater than the sum of the absolute values of the coefficients of the other variables.
• A system satisfying this condition is called diagonally dominant.
• A linear system can always be reduced to diagonally dominant by elementary operations.
For example, in the system
𝑥 + 2𝑦 + 10𝑧 = 10 (E1) 1 < 2 + |10|
𝑥 − 10𝑦 − 𝑧 = 24 (E2) −10 > 1 + | − 1|
11𝑥 + 5𝑦 + 8𝑧 = 31 (E3) 8 < 11 + |5|
is not diagonally dominant. Rearranging the system as (E3)-(E1), (E2), (E1)
10𝑥 + 3𝑦 − 2𝑧 = 21 10 > 3 + | − 2|
𝑥 − 10𝑦 − 𝑧 = 24 −10 > 1 + | − 1|
𝑥 + 2𝑦 + 10𝑧 = 10 10 > 1 + |5|
Output : By applying Iterative Method, system of linear equations can be
solved to find roots (approximately) of the system.
1
10𝑥 + 3𝑦 − 2𝑧 = 21 𝑥= 21 − 3𝑦 + 2𝑧
10
𝑥 − 10𝑦 − 𝑧 = 24 1
𝑥 + 2𝑦 + 10𝑧 = 10 𝑦=− 24 − 𝑥 + 𝑧
10
1
𝑧= 10 − 𝑥 − 2𝑦
10
Jacobi Iterative Method:
In this method, a fixed set of values is used to calculate all the variables
and then repeated for the next iteration with the values obtained
previously. The iterative formulas of the above
1
𝑥𝑛+1 = 21 − 3𝑦𝑛 + 2𝑧𝑛
10
1
𝑦𝑛+1 = − 24 − 𝑥𝑛 + 𝑧𝑛
10
1
𝑧𝑛+1 = 10 − 𝑥𝑛 − 2𝑦𝑛
10
Gauss-Seidel iterative method is more efficient than Jacobi’s
iterative method and explained through an example.
Gauss-Seidel Iterative Method
In this method, the values of each variable is calculated using
the most recent approximations to the values of the other
variables. The Gauss-Seidel iterative formulas of the
above system are
1 1
𝑥= 21 − 3𝑦 + 2𝑧 𝑥𝑛+1 = 21 − 3𝑦𝑛 + 2𝑧𝑛
10
10 1
1 𝑦𝑛+1 = − 24 − 𝑥𝑛+1 + 𝑧𝑛
𝑦=− 24 − 𝑥 + 𝑧 10
10 1
1 𝑧𝑛+1 = 10 − 𝑥𝑛+1 − 2𝑦𝑛+1
𝑧= 10 − 𝑥 − 2𝑦 10
10
If initial values are not supplied we can start with initial values
𝑥0 = 0, 𝑦0 = 0, 𝑧0 = 0.
and perform the iterations until required accuracy is achieved.
6𝑥 + 5𝑦 + 3𝑧 = 7 Eq(1)
Example: Given the linear system 8𝑥 − 3𝑦 + 2𝑧 = 16 Eq(2) .
10𝑥 − 7𝑦 − 8𝑧 = 15 Eq(3)
a. Reduce the above system to diagonally dominant form.
b. Write the corresponding Gauss-Seidel iteration formula.
c. Compute two iterations to estimate the roots to 2 d.p. with 𝑥0 = 1.5, 𝑦0 = −1
and 𝑧0 = 1.
d. Write MATLAB code to iterate the above formula four times.
Solution: Rearranging the system as Eq(2), Eq(1)-Eq(2), Eq(2)-Eq(3)
a. Eq(2) 8𝑥 − 3𝑦 + 2𝑧 = 16, 8 > −3 + |2|
Eq(1)-Eq(2) −2𝑥 + 8𝑦 + 𝑧 = −9, 8 > −2 + |1|
Eq(2)-Eq(3) −2𝑥 + 4𝑦 + 10𝑧 = 1, 10 > −2 + |4|
Gauss-Seidel formula
1 1
𝑥 = 16 + 3𝑦 − 2𝑧 𝑥𝑛+1 = 8 16 + 3𝑦𝑛 − 2𝑧𝑛
8
1 1
𝑦 = −9 + 2𝑥 − 𝑧 𝑦𝑛+1 = −9 + 2𝑥𝑛+1 − 𝑧𝑛
8 8
1 1
𝑧= [1 + 2𝑥 − 4𝑦] 𝑧𝑛+1 = 1 + 2𝑥𝑛+1 − 4𝑦𝑛+1
10
10
c.
Starting with initial values 𝑥0 = 1.5, 𝑦0 = −1, 𝑧0 = 1
When 𝑛 = 0, we have 1
𝑥𝑛+1 = 8 16 + 3𝑦𝑛 − 2𝑧𝑛
1 1
𝑥1 = 8 16 + 3 −1 − 2 1 = 1.375 𝑦𝑛+1 = 8 −9 + 2𝑥𝑛+1 − 𝑧𝑛
1 1
𝑦1 = −9 + 2 1.375 − 1 = −0.906 𝑧𝑛+1 = 10 1 + 2𝑥𝑛+1 − 4𝑦𝑛+1
8
1
𝑧1 = 10 1 + 2 1.375 − 4 −0.906 = 0.737
For 𝑛 = 1, we have
1
𝑥 2 = 8 16 + 3 −0.906 − 2 0.737 = 1.476
1
𝑦2 = 8 −9 + 2 1.476 − −0.906 = −0.848
1
𝑧2 = 10 1 + 2 1.476 − 4 −0.848 = 0.734
Solution to 2 d.p. is
𝑥 = 1.48, 𝑦 = −0.85, 𝑧 = 0.73.
d. MATLAB
>> clear
>> x(1)=1.5; %Initial values of x, y, z
>> y(1)= -1;
>> z(1)=1;
>> iter(1)=0;
>> for n=1:4
iter(n+1)=n;
x(n+1)=(16+3*y(n)-2*z(n))/8;
y(n+1)=(-9+2*x(n+1)-z(n))/8;
z(n+1)=(1+2*x(n+1)-4*y(n+1))/10;
end
>> Solution = [iter',x',y',z’]
Solution =
0 1.5000 -1.0000 1.0000
1.0000 1.3750 -0.9063 0.7375
2.0000 1.4758 -0.8482 0.7345
3.0000 1.4983 -0.8422 0.7366
4.0000 1.5000 -0.8421 0.7368
SAMPLE MCQ
1. To solve the system of equation by iterative method, the system must be in
a) Diagonally Dominant
b) Iterative equation
c) Maximum value eqation
d) None
2. In Gauss-Seidel Iterative Method the values of each variable is calculated
using the values of the other variables
a) Most recent
b) old
c) Both
d) None
3. Which method is more convenient?
a) Gauss-Seidal Method
b) Gauss Jacobi method
c) Both
d) None
Exercise
1.
a. 𝑥 + 8𝑦 + 3𝑧 = 10, 3𝑥 − 5𝑦 + 7𝑧 = 4, 3𝑥 − 𝑦 − 𝑧 = 1.
using 𝑥0 = 0.85, 𝑦0 = 0.8 and 𝑧0 = 0.75
b. 2𝑥 + 10𝑦 − 7𝑧 = 20, 3𝑥 − 7𝑦 − 5𝑧 = 18, 8𝑥 − 5𝑦 − 2𝑧 = 12.
using 𝑥0 = 0.6, 𝑦0 = −0.1 and 𝑧0 = −3.
c. 5𝑥 + 9𝑦 + 12𝑧 = 9, 8𝑥 − 4𝑦 − 11𝑧 = 14, −2𝑥 + 5𝑦 + 𝑧 = 10.
using 𝑥0 = 0.75, 𝑦0 = 2.5 and 𝑧0 = −1.5.
d. 𝟏𝟎𝑥 + 𝟓𝑦 + 𝟑𝑧 = 𝟐𝟏, 𝟔𝒙 + 𝟑𝑦 − 𝟕𝑧 = 𝟐𝟐, 𝟑𝑥 + 𝟏𝟔𝑦 + 𝟒𝑧 = 1𝟒.
using 𝑥0 = 𝟐, 𝑦0 = 𝟎. 𝟖 and 𝑧0 = −1.
e. 𝟔𝑥 + 𝟓𝑦 − 𝟖𝑧 = 𝟐𝟒, 𝟏𝟎𝒙 + 𝟑𝑦 + 𝟒𝑧 = 𝟏𝟏, 𝟖𝑦 + 𝟑𝑧 = 1𝟎.
using 𝑥0 = 𝟏, 𝑦0 = 𝟏. 𝟓 and 𝑧0 = −1.
i. Reduce the above system to diagonally dominant form.
ii. Write the corresponding Gauss-Seidel and Jacobi iteration formula.
iii. Compute two iterations to estimate the roots to 3 d.p. with the given initial
values.
iv. Justify your result by direct substitution in the original equations.
v. Write MATLAB codes to solve by left division (backslash) operator.
2. Consider the linear system: 4x + 2y + z = 7, 4x + 5y + 3z =
4, 4x + 5y + 7z = 3
i. Reduce the above system to diagonally dominant form.
ii. Write the corresponding Gauss-Seidel iteration formula.
iii. Compute two iterations to estimate the roots to 2 d.p with the
following initial values x= 2, y=-0.75, z=-0.2.
iv. Justify your result by direct substitution in the original equations.
v. Write MATLAB codes to iterate the above formula four times.
3. Consider the linear system: 5x + 2y + z = 7, 2x − 4y + 3z = 6, 3x + 5y + 7z = 6
i. Reduce the above system to diagonally dominant form.
ii.Write the corresponding Gauss-Seidel iteration formula.
iii. Compute two iterations to estimate the roots to 3 d.p. with the following initial values x= 1.4, y=-
0.35, z=0.5.
iv. Justify your result by direct substitution in the original equations.
v. Write MATLAB codes to iterate the above formula four times.
