matrix algebra
Numerical Methods for IT
solution of linear algebraic equations
Gaussian elimination with Back-substitution
The basic idea of Gauss-Jordin elimination is to add or subtract linear combination of the given
equations = until each equation contains only one of the unknown, thus giving an
immediate solution.
Gauss-Jordin elimination produces both the solution of the equations for one or more right-hand
side vector , = [ … ], and the matrix inverse .
Gaussian elimination reduces a matrix not all the way to the identity matrix, but only halfway, to a
matrix whose components on the diagonal and above.
=
· = ⟹ 0 · =
0 0 −∑ ị ∗
0 0 0 =
Iterative improvement of a solution
Suppose that a vector is the exact solution of
· =
We only know some lightly wrong solution
+! ,
where ! is the unknow error.
So
· +! = +! .
·! =! .
·! = · +! − .
Let " = ! , # = · + ! −
Solve · " = # using Gaussian elimination with Back-substitution.
inverse matrix
definition
$∈ℝ ×
is invertible ⟺ ∃* ∈ ℝ ×
: * · $ = , = $ · *. Denote * = $
Given an invertible $ ∈ ℝ ×
,$ = * = [* … * ] will be the solution of $ · * = , = [. … . ]
Sherman-Morrison formula
Suppose that we have $ which is invertible matrix of $ ∈ ℝ × .
Now we want to make a small change in $, for example change one element , or a few
elements, or one row, or one column:
$ → $ + 0 ⊗ 2 ; 0, 2 ∈ ℝ , where 0 ⊗ 2 = 4 = 0 × 2 ∈ ℝ ×
.
The Sherman-Morrison formula give the inverse $ + 0 ⊗ 2 :
567 ·8 ⊗ 9·567
$+0⊗2 = , where ; = 2 · $ · 0.
:
Given $ and the vectors 0 and 2, we need only perform two matrix multiplications and a vector
dot product, < ≡ $ · 0, 4 ≡ $ > · 2, ; = 2 · <, to get the desired change in the inverse:
?⊗@
$ →$ − :
.
For some other sparse problem, the Sherman-Morris formula cannot be directly applied for the
simple reason that the storage of whole inverse matrix $ is not feasible.
To add only a single correction ò the form 0 ⊗ 2 and solve the linear system $ + 0 ⊗ 2 · = :
. Solve the two auxiliary problem $ · A = and $ · = 0 for the vectors A and <.
9·B
. And =A− 9·?
.
eigen value and eigen vector
Definition
Given $ ∈ ℝ ×
,G = 1
det $ = F
Σ −1 det J =Σ −1 det J ,G > 1
,
where J is a matrix of order (G − 1) extracted from $ by removing row N and column O.
Given $ ∈ ℝ × . If there are 0 ∈ ℝ and ; ∈ ℝ such that $ · = ; , then ; is called an
eigenvalue of $, and – eigenvector corresponding to ;.
To find ; and , because
A · = ; ⟺ $ · = ; · , ⟺ ;, − $ · = 0, ; 0 GQ 0,
So det ;, − $ = 0 = R ; = ; + S ; + ⋯ + S ;U . R(;) is called the characteristic
polynomial of $.
. Eigenvalue ; is a solution of the equation R ; = 0.
. Given eigen ;, equation system ;, − $ · = 0 has a non-trivial solution which is eigenvector.
Matrix Diagonalization
Given $, V ∈ ℝ ×
are called similar if there exists an invertible matrix W such that V = W ·$·W
; ⋯ 0
Let W = R … R and suppose that X = ⋮ ⋱ ⋮ ,
0 ⋯ ;
$ · W = $ · R … R = [$ · R … $ · R ] and W · X = [; R … ; R ].
If R , … , R are linearly independent, and ; , … , ; are eigenvalue of $, then
$ · W = $ · R …R = $ · R …$ · R = ; R …; R = W · X
Algorithm (Diagonalization)
. If R , … , R are distinct eigenvectors then $ is diagonalizable.
. Let W = R … R
. Then X = W · $ · W
matrix decomposition
QR decomposition
Problem: Given 0 , … , 0[ ∈ ℝ . Find 2 , … , 2[ : < 2 , 2 ] > = 0, if 0 , … , 0[ is a family of linearly
independent vectors.
Algorithm (Gram-Schmidt)
. 2 = 0 (if 2 = 0 then {0 , … , 0[ } is linearly dependent family).
`8a ,9b c
.2 = 0 −Σ d 2 , N = 2, … , f (if 2 = 0 then {0 , … , 0[ } is linearly dependent family).
9b
9a
.g = 9a
, N = 1, … , f (if we need a family of orthonormal vectors).
Proposition: If $ = [0 … 0 ] ∈ ℝh× has n linearly independent column vectors, then $ can
decompose to $ = i · j, where i = g … g ∈ ℝh× which has n orthonormal vectors, and j ∈
ℝ × is an invertible upper triangular matrix.
Algorithm (QR-decomposition)
.u ,…,0 ← $
. i ← Gram-Schmidt(0 , … , 0 )
.g ,…,g ← i
< 0 , g > Nn N ≤ O
.j = m
0, .pq.
LU decomposition
Problem: Given $ ∈ ℝ ×
. Find a lower triangular r and a upper triangular s such that $ = r · s:
t 0 0 0 u u u u
t t 0 0 0 u u u
t t t 0 · 0 0 u u
= ⟺ t u + t u + ⋯ = ; N, O = 1, … , G
t t t t 0 0 0 u
N < O: t u + ⋯+ t u =
We have: N = O: t u + ⋯+ t u = . There are total G equations for G + G unknows t, u.
N > O: t u + ⋯+ t u =
Algorithm (LU decomposition) Application of LU decomposition: = z · {
. Set t = 1, ∀N = 1, … , G (1.) Determinant
. For each O = 1,2, … , G: det $ = det r · s = det r × det s = Π u .
(a) ∀N = 1, … , O: u = − Σw t w uw , (2.) Solve equations
(b) ∀N = O + 1, … , x: t = ( − Σw U t w uw ) $ · = ⟺ r · s = ⟺ r s · =
ybb
r·A=
⟺m
s· =A
SVD – Singular Value Decomposition
In many cases where Gaussian elimination and LU decomposition fail to satisfactory results. SVD
will diagnose precisely what the problem is.
SVD is also the method of choice for solving most linear least-square problems.
Theorem. Any $ ∈ ℝ}×~ can be written as the product of a column-orthogonal matrix s ∈ ℝ}×~ ,
a diagonal matrix W ∈ ℝ~×~ with positive or zero elements (the singular), and the transpose of
orthogonal matrix € ∈ ℝ~×~ .
Algorithm (SVD)
(a) € = 2 … 2 ← •f ‚ − ƒSℎ‚NQ of $> · $
… ⋯ 0
(b) Let … = ; , … , …w = ;w , with ; , … , ;w are eigenvalues of $> · $, then X = ⋮ ⋱ ⋮
0 ⋯ …w
(c) The column vectors of V are arranged in order corresponding to … ≥ … ≥ ⋯ ≥ …w > 0.
5·9
(d) 0 = 5·9a = ‡ $ · 2 , N = 1, … , ˆ.
a a
(e) 0 , … , 0w is an orthogonal basis for A.
(f) 0 , … , 0w , 0w , … , 0} is a span of 0 , … , 0w to an orthonormal basis for ℝ~ .