Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.1
Lecture 11
Numerical Techniques : Solving Sets
of Eq u ations - Linear Alg ebra and
Matrix Computin g II
Normal Modes of Coupled Oscillation
IKC-MH.55 Scientific Computing with Python at January 05,
2024
Dr. Cem Özdo
˘
gan
Engineering Sciences Department
˙
Izmir Kâtip Çelebi University
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.2
Contents
Using the LU Matrix for Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and Eigenvectors of a Matrix
Normal Modes of Coupled Oscillation
Iterative Methods
Jacobi Method
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.3
Solving Sets of Equations
•
Solving sets of linear equations and eigenvalue problems
are the most frequently used numerical procedures when
real-world situations ar e modelled.
1 Matrices and Vectors
2 Elimination Methods
Continued.
3 The Inverse of a Matrix
Shows how an important derivative of a matrix, its inverse, c an
be computed. It shows when a matrix cannot be inverted and
tells of situations where no unique solution exists to a system
of equations.
4 Iterative Met hods
It is described how a linear system can be solved in an
entirely different way, by beginning with an initial estimate of
the solution.
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.4
Gaussian Elimination XIII
Continue with the previous example.
•
If we had replaced the zeros below the main diagonal w ith
the ratio of coefficients at each step, the resulting
augmented matrix would be
6 1 −6 −5 6
(0.66667) −3.6667 4 4.3333 −11
(0.33333) (−0.45454) 6.8182 5.6364 −9.0001
(0.0) (−0.54545) (0.32) 1.5600 −3.1199
•
This gives a LU decomposition as
1 0 0 0
0.66667 1 0 0
0.33333 −0.45454 1 0
0.0 −0.54545 0.32 1
6 1 −6 −5
0 −3.6667 4 4.3333
0 0 6.8182 5.6364
0 0 0 1.5600
•
It should be noted that the product of these matrices
produces a permutation of the original matrix, call it A
′
,
where
A
′
=
6 1 −6 −5
4 −3 0 1
2 2 3 2
0 2 0 1
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.5
Gaussian Elimination XIV
•
The determinant of the original matrix of coefficients can
be easily computed according to the formula
det(A) = (−1)
2
∗ (6) ∗ (−3.6667) ∗ (6.8182) ∗ (1.5600) = −234.0028
which is close to the exact solution: -234.
•
The exponent 2 is required, because there were two row
interchanges in solving this system.
•
To summar ize
1 The solution to the four equations
2 The determinant of the coefficient matrix
3 A LU decomposition of the matrix, A
′
, which is just the
original matrix, A, after we have interchanged its rows.
•
"These" are readily obtained after solving the system
by Gaussian elimination method.
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.6
Gaussian Elimination XV
Example py-files: LU factorization without pivoting.
myLUshow.py LU factorization with pivoting.
myLUPivShow.py
Figure: (a) Without Pivoting (b) With Pivoting.
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.7
Using th e LU Matrix for Multiple Right-Hand Sides I
•
Many physical situations are modelled with a large set of
linear equations.
•
The equations will depend on the geometry and cer tain
external factors that will determine the right-hand sides.
•
For example, in electrical circuit problems, the resistors at
the circuit (A matrix) are unchanged with the varying
applied voltages (b vector). (e.g., Kirchhoff’s Rule)
•
If we want the solution for many different values of these
right-hand sides,
•
it is inefficient to solve the system from the start with each
one of t he rig ht-hand-side values.
•
Using the LU equivalent of the coefficient matrix is
preferred.
•
Suppose we have solved the system Ax = b by Gaussian
elimination.
•
We now know the LU equivalent of A: A = L ∗ U
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.8
Using th e LU Matrix for Multiple Right-Hand Sides II
•
We can write
Ax = b
LUx = b
Ly = b
•
e.g., Solve Ax = b, where we already have its L and U
matrices:
1 0 0 0
0.66667 1 0 0
0.33333 −0.45454 1 0
0.0 −0.54545 0.32 1
∗
6 1 −6 −5
0 −3.6667 4 4.3333
0 0 6.8182 5.6364
0 0 0 1.5600
•
Suppose that the b-vector is [6 − 7 − 2 0]
T
.
•
We first get y(= Ux) from Ly = b by forward substitution:
y = [6 − 11 − 9 − 3.12]
T
•
and use it to c ompute x from Ux = y :
x = [−0.5 1 0.3333 − 2]
T
.
•
Exercise: b = [1 4 − 3 1]
T
=⇒
x = [0.0128 − 0.5897 − 2.0684 2.1795]
T
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.9
Using th e LU Matrix for Multiple Right-Hand Sides III
Phyton Code:
1 impo rt numpy as np
2 from s cip y . l i n a l g im por t lu
3 A = np . a r ra y ([ [ 0 . 0 , 2. 0 , 0 . 0 , 1 . 0 ] , [ 2 . 0 , 2.0 , 3 . 0 , 2 . 0] , [ 4 . 0 , −3.0, 0. 0 , 1 . 0] , [ 6 . 0 , 1. 0 ,
−6.0, − 5.0] ])
4 P , L , U = l u (A)
5 p r i n t ( " SciPy LU−decomposition : P − P ermu tation Mat r ix \ n" , P)
6 p r i n t ( " SciPy LU−decomposition : L − Lower T r i a n g u l a r wit h u n i t di ag on a l elements \ n" , L )
7 p r i n t ( " SciPy LU−decomposition : U − Upper T r i a n g u la r \ n " , U)
8 def f orward ( L , b ) :
9 y=np . ze ros ( np . shape ( b ) , dt ype= f l o a t )
10 f o r i in range ( len ( b ) ) :
11 y [ i ]=np . copy ( b [ i ] )
12 f o r j i n range ( i ) :
13 y [ i ] = y [ i ]−(L [ i , j ]
*
y [ j ] )
14 y [ i ] = y [ i ] / L [ i , i ]
15 re t ur n y
16 b = np . arr a y ( [ [ 6 . 0 ] , [ − 7. 0] , [ − 2.0] , [ 0 . 0 ] ] )
17 # b = np . ar ray ( [ [ 1 . 0 ] , [ 4 . 0 ] , [ − 3.0] , [ 1 . 0 ] ] )
18 y=forward ( L , b)
19 p r i n t ( " y ve ct o r from Ly=b by forward s u b s t i t u t i o n : " , np . t ranspose ( y ) )
20 de f backward (U, y) :
21 x=np . zeros ( np . shape ( y ) ,dtype= f l o a t )
22 yl en = le n ( y )−1
23 x [ yle n ] =y [ ylen ] /U [ y len , yle n ] # P r i n t the l a s t stage x value
24 f o r i in range ( y len −1,−1,−1):
25 x [ i ]=np . copy ( y [ i ] )
26 f o r j i n range ( ylen , i ,−1) :
27 x [ i ] = x [ i ]−(U[ i , j ]
*
x [ j ] )
28 x [ i ] = x [ i ] / U[ i , i ]
29 r et u rn x
30 x=backward (U, y )
31 p r i n t ( " x ve ct o r from Ux=y by b ackward s u b s t i t u t i o n : " , np . transpose ( x ) )
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.10
The Inverse of a Matrix I
•
Division by a matrix is not defined but the equivalent is
obtained from the inverse of the matrix.
•
If the product of two square matrices, A ∗ B, equals to the
identity matrix , I, B is said to be the inverse of A (and also
A is the inverse of B).
•
By multiplying each element with its cofactor to find the
inverse of the matrix is not useful since N
3
multiplication
and division are required for an N-dimensional matrix.
•
To find the inverse of matrix A, use an elimination method.
•
We augment the A matrix with the identity matrix of the
same size and solve. The solu tion is A
−1
. Example;
A =
1 −1 2
3 0 1
1 0 2
→
1 −1 2 1 0 0
3 0 1 0 1 0
1 0 2 0 0 1
R
2
− (3/1)R
1
→
R
3
− (1/1)R
1
→
1 −1 2 1 0 0
0 3 −5 −3 1 0
0 1 0 −1 0 1
1 −1 2 1 0 0
0 1 0 −1 0 1
0 3 −5 −3 1 0
|
{z }
Row Int erchange
R
3
− (3/1)R
2
→
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.11
The Inverse of a Matrix II
•
Contd.
1 −1 2 1 0 0
0 1 0 −1 0 1
0 0 −5 0 1 −3
R
3
/(−5) →
R
1
− (2/1)R
3
→
1 −1 0 1 2/5 −6/5
0 1 0 −1 0 1
0 0 1 0 −1/5 3/5
R
2
− (1/ − 1)R
1
→
1 0 0 0 2/5 −1/5
0 1 0 −1 0 1
0 0 1 0 −1/5 3/5
•
We confirm the fact that we have found the inverse by
multiplication:
1 −1 2
3 0 1
1 0 2
|
{z }
A
∗
0 2/5 −1/5
−1 0 1
0 −1/5 3/5
|
{z }
A
−1
=
1 0 0
0 1 0
0 0 1
|
{z }
I
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.12
The Inverse of a Matrix III
•
It is more efficient to use Gaussian elimination. We show
only the final triangular matrix; we used pivoting:
1 −1 2 1 0 0
3 0 1 0 1 0
1 0 2 0 0 1
→
3 0 1 0 1 0
(0.333) −1 1.667 1 −0.333 0
(0.333) (0) 1.667 0 −0.333 1
•
After doing the back-substitutions, we get
3 0 1 0 0.4 −0.2
(0.333) −1 1.667 −1 0 1
(0.333) (0) 1.667 0 −0.2 0.6
•
If we have the inverse of a matrix, we can use it to solve a
set of equations, Ax = b,
•
because multiplying by A
−1
gives the answer (x):
A
−1
Ax = A
−1
b
x = A
−1
b
•
Phyton Code:
1 impo rt numpy as n p
2 A = np . arr ay ( [ [ 1. 0 , − 1 . 0 , 2 .0] , [ 3 . 0 , 0 . 0 , 1 . 0 ] , [1. 0 , 0 . 0 ,2. 0 ] ] )
3 b = np . a rray ( [ [ 1 . 0 , 0 . 0 , 0 . 0 ] , [ 0 . 0 , 1 . 0 , 0 . 0 ] , [ 0 . 0 , 0 . 0 , 1 . 0 ] ] )
4 x = np . l i n a l g . solve ( A, b )
5 p r i n t ( "NumPy − Inv ers e Mat rix : \ n " , x )
6 from s cip y i mport l i n a l g
7 x= l i n a l g . solve (A, b )
8 p r i n t ( " SciPy − I nvers e M atrix : \ n " , x )
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.13
Eigenvalues and Eigenvectors I
•
For a square matrix A,
A
~
u = λ
~
u
~
u vectors satisfying this condition are called the
eigenvectors of the matrix A, and the lambda scalar
coefficients are called the eigenvalues.
•
An N × N matrix has N different eigenvectors. However,
the corresponding lambda eigenvalues for these
eigenvectors may not be different.
•
State of a system can be expressed in terms of the
eigenvectors of the system of linear equations and in
terms of their eigenvalues for the measured quantities.
•
Create an U matrix by arranging eigenvectors side by side:
U =
~
u
1
~
u
2
...
~
u
n
z }| {
u
11
u
12
. . . u
1n
u
21
u
22
. . . u
2n
.
.
.
.
.
.
.
.
.
.
.
.
u
n1
u
n2
. . . u
nn
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.14
Eigenvalues and Eigenvectors II
•
When we multiply the matrix A with the matrix U and its
inverse matrix U
−1
from both sides, we get
A
′
= U
−1
AU =
λ
1
0 . . . 0
0 λ
2
0
.
.
.
.
.
.
.
.
.
.
.
.
0 0 . . . λ
n
•
That is, the similarity transformation with the eigenvectors
matrix makes A as being diagonalized and the elements
on the diagonal become the eigenvalues of A.
•
In principle, the eigenvalue problem is easy to solve.
So-called characteris tic equation is to be solved:
det|A − λI| = 0
•
After finding the roots of this n-degree polynomial
equation, the corresponding eigenvectors can be obtained
by solving the following system of equations:
(A − λI)
~
v = 0
•
Since this method requires determinant calculation, it
is not useful for large dimensional matrices.
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.15
Normal Modes of Oscillation I
•
Consider the coupled oscillations problem of two equal
masses m connected by springs of constant k (see
Figure).
Figure: Mass-Spring system.
•
The differential equation provided by each mass is written
using Newton’s law of motion as follows
k(x
2
− x
1
) − kx
1
= m
d
2
x
1
dt
2
−kx
2
− k(x
2
− x
1
) = m
d
2
x
2
dt
2
•
In this system, the frequencies (ω) that both masses
oscillate as in common are called normal oscillation
modes.
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.16
Normal Modes of Oscillation II
•
To find the normal mode frequencies, try a solution for
both unknowns as:
x
1
= x
10
cosωt & x
2
= x
20
cosωt
•
Substitute these solutions into the system of linear
equations above and simplify by removing cosωt,
2k
m
x
10
−
k
m
x
20
= ω
2
x
10
−
k
m
x
10
+
2k
m
x
20
= ω
2
x
20
•
This system of equations can be written as the product of
a matrix and a column vector as follows (replace ω
2
by λ ):
2k/m −k /m
−k/m 2k/m
x
10
x
20
= λ
x
10
x
20
•
This structure can also be written as:
2k/m − λ −k/m
−k/m 2k/m − λ
x
10
x
20
= 0
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.17
Normal Modes of Oscillation III
•
The determinant must be zero for this linear system of
equations to have a unique solution:
det
2k/m − λ −k/m
−k/m 2k/m − λ
= 0
−→ (2k/m − λ)
2
− k
2
/m
2
= 0
•
There are two oscillation frequencies (ω) and their
corresponding amplitudes
~
x
0
= (x
10
, x
20
):
λ
1
= k /m −→
~
x
0,1
=
0.71
0.71
λ
2
= 3k/m −→
~
x
0,2
=
−0.71
0.71
•
The first of these solutions represents the mode in which
the two masses oscillate in the same phase (–> –>)
•
and the second represents the mode in which they
oscillate in the opposite phase (–> <–).
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.18
Normal Modes of Oscillation IV
Phyton Code:
1 p r i n t ( "
* * * * * * * * * * * * * * * *
SymPy S olu ti o n f o r C har a c t e r i s tic Equation :
" )
2 from sympy i mport Matrix , symbols , p pr int , fa c t o r
3 M = Ma trix ( [ [ 2 , −1], [ −1, 2 ] ] )
4 lamda = symbols ( ’ lamda ’ )
5 pol y = M. ch arpo ly ( lamda ) # Get the c h a r a c t e r i s t i c polynomial
6 p r i n t ( pol y ) # P r i n t i n g polynomial
7 pp r i n t ( f a c t o r ( pol y . as_expr ( ) ) ) # P r i nts expr in pr e t t y form .
8 p r i n t ( "
* * * * * * * * * * * * * * * *
NumPy S o lu t io n fo r C h a rac t e r i s t i c Equation :
" )
9 impo rt numpy as n p
10 A = np . arra y ( [ [ 2 , −1], [−1, 2 ] ] )
11 p r i n t ( np . p oly (A) )
12 p r i n t ( "
* * * * * * * * * * * * * * * *
NumPy S o lu t io n fo r Eigenvalues and
Eigenvectors : " )
13 w, v=np . l i n a l g . ei g (A)
14 p r i n t ( ’ Eigenvalue : ’ , w)
15 p r i n t ( ’ Eigenvector1 : ’ , v [ 0 ] )
16 p r i n t ( ’ Eigenvector2 : ’ , v [ 1 ] )
17 p r i n t ( "
* * * * * * * * * * * * * * * *
SciPy So lut ion f or Eigenvalues and
Eigenvectors : " )
18 imp ort sci py . l i n a l g as la
19 w, v = la . eig (A)
20 p r i n t ( ’ Eigenvalue : ’ , w)
21 p r i n t ( ’ Eigenvector1 : ’ , v [ 0 ] )
22 p r i n t ( ’ Eigenvector2 : ’ , v [ 1 ] )
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.19
Iterative Methods
•
Gaussian elimination and its variants are called direct
methods.
•
An entirely different way to solve many systems is through
iteration.
•
In this way, we start with an initial estimate of the solution
vector and proceed to refine this estimate.
•
An n × n matrix A is diagonally dominant if and only if;
|a
ii
| >
n
X
j=1,j6=i
|a
ij
|, i = 1, 2, . . . , n
•
Example. Given matrix & After reordering;
6x
1
− 2x
2
+ x
3
= 11
x
1
+ 2x
2
− 5x
3
= −1
−2x
1
+ 7x
2
+ 2x
3
= 5
&
6x
1
− 2x
2
+ x
3
= 11
−2x
1
+ 7x
2
+ 2x
3
= 5
x
1
+ 2x
2
− 5x
3
= −1
•
The solution is x
1
= 2, x
2
= 1, x
3
= 1 (for both cas es?).
•
Before we begin our iterative sc heme we must fir st
reorder the equations so that the coefficient matrix is
diagonally dominant
.
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.20
Jacobi Method I
•
The iterative methods depend on the rearrangement of the
equations
in this manner:
x
i
=
b
i
a
ii
−
n
X
j=1,j6=i
a
ij
a
ii
x
j
, i = 1, 2, . . . , n, 7→ x
1
=
11
6
−
−2
6
x
2
+
1
6
x
3
(1)
•
Each equation now solved for the variables in succession:
x
1
= 1.8333 + 0.3333x
2
− 0.1667x
3
x
2
= 0.7143 + 0.2857x
1
− 0.2857x
3
x
3
= 0.2000 + 0.2000x
1
+ 0.4000x
2
•
We begin with some initial approximation to the value of
the variables.
•
Say initial values are; x
1
= 0, x
2
= 0, x
3
= 0. Each
component might be taken equal to zero if no better initial
estimates are at hand.
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.21
Jacobi Method II
•
The new values are substituted in the right-hand sides to
generate a second approximation,
•
and the process is repeated until successive values of
each of the variables are sufficiently alike.
•
Now, general form
x
(n+1)
1
= 1.8333 + 0.3333x
(n)
2
− 0.1667x
(n)
3
x
(n+1)
2
= 0.7143 + 0.2857x
(n)
1
− 0.2857x
(n)
3
x
(n+1)
3
= 0.2000 + 0.2000x
(n)
1
+ 0.4000x
(n)
2
(2)
•
Starting with an initial vector of x
(0)
= (0, 0, 0, ), we obtain
Table 1
First Second Third Four th Fifth Sixth . . . Ninth
x
1
0 1.833 2.038 2.085 2.004 1.994 . . . 2.000
x
2
0 0.714 1.181 1.053 1.001 0.990 . . . 1.000
x
3
0 0.200 0.852 1.080 1.038 1.001 . . . 1.000
Table: Successive estimates of solutio n (Jacobi method)
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.22
Jacobi Method III
•
Rewrite in matrix notation; let A = L + D + U,
Ax = b =⇒
6 −2 1
−2 7 2
1 2 −5
x
1
x
2
x
3
=
11
5
−1
L =
0 0 0
−2 0 0
1 2 0
, D =
6 0 0
0 7 0
0 0 −5
, U =
0 −2 1
0 0 2
0 0 0
Ax = (L + D + U)x = b
Dx = −(L + U)x + b
x = −D
−1
(L + U)x + D
−1
b
•
From this we have, identifying x on the left as the new
iterate,
x
(n+1)
= − D
−1
(L + U)x
(n)
+ D
−1
b
Numerical Techniques:
Solving Sets of
Equations - Linear
Algebra and Matrix
Computing II
Dr. Cem Özdo
˘
gan
LOGIK
Using the LU Matrix for
Multiple Right-Hand Sides
The Inverse of a Matrix
Eigenvalues and
Eigenvectors of a Matrix
Normal Modes of Coupled
Oscillation
Iterative Methods
Jacobi Method
11.23
Jacobi Method IV
•
In Eqn. 2,
b
′
= D
−1
b =
1.8333
0.7143
0.2000
D
−1
(L + U) =
0 −0.3333 0.1667
−0.2857 0 0.2857
−0.2000 −0.4000 0
•
This procedure is known as the Jacobi method, also called
”the method of simultaneous displacements”,
•
because each of the equations is simultaneously changed
by us ing the most recent set of x -values (see Table 1).
•
Example py-file: The Jacobi approximation to the solution
of AX = B. myJacobi.py
