FOXES TEAM
Tutorial on Numerical Analysis with Matrix.xla
Matrices
and
Linear Algebra
Volume
TUTORIAL ON NUMERICAL ANALYSIS WITH MATRIX.XLA
Matrices and Linear Algebra
TUTORIAL FOR MATRIX.XLA
2
Index
About this Tutorial....................................................................................................................5
Matrix.xla.................................................................................................................................5
Linear System...........................................................................................................................6
The Gauss-Jordan algorithm...................................................................................................7
The pivoting strategy..........................................................................................................................8
Integer calculation.............................................................................................................................10
Several ways to use the Gauss-Jordan algorithm................................................................12
Solving a non-singular linear system................................................................................................12
Solving m simultaneous linear systems............................................................................................12
Inverse matrix computing..................................................................................................................12
Determinant computing.....................................................................................................................13
Linear independence checking.........................................................................................................13
Non-singular Linear system..................................................................................................14
Round-off errors................................................................................................................................14
Full pivoting or partial pivoting?........................................................................................................15
Solution stability................................................................................................................................17
The Condition Number......................................................................................................................19
Complex systems.............................................................................................................................20
About the complex matrix format......................................................................................................22
Determinant...........................................................................................................................23
Gaussian elimination........................................................................................................................23
Ill-conditioned matrix.........................................................................................................................24
Laplace's expansion.........................................................................................................................27
Simultaneous Linear Systems...............................................................................................28
Inverse matrix........................................................................................................................28
Round-off error.................................................................................................................................29
Homogeneous and Singular Linear Systems........................................................................32
Parametric form................................................................................................................................33
Rank and Subspace.........................................................................................................................34
General Case - Rouché-Capelli Theorem.............................................................................36
Homogeneous System Cases..........................................................................................................37
Non Homogeneous System Cases...................................................................................................38
Triangular Linear Systems....................................................................................................39
Triangular factorization.....................................................................................................................39
Forward and Backward substitutions................................................................................................39
LU factorization.................................................................................................................................40
Overdetermined Linear System............................................................................................43
The normal equation.........................................................................................................................43
QR decomposition............................................................................................................................44
SVD and the pseudo-inverse matrix.................................................................................................45
Underdetermined Linear System..........................................................................................46
Parametric Linear System.....................................................................................................49
Cramer's rule....................................................................................................................................49
Block-Triangular Form...........................................................................................................50
Linear system solving.......................................................................................................................50
TUTORIAL FOR MATRIX.XLA
3
Computing the determinant..............................................................................................................50
Permutations.....................................................................................................................................51
Eigenvalue Problems........................................................................................................................51
Several kinds of block-triangular form...............................................................................................51
Permutation matrices........................................................................................................................52
Matrix Flow-Graph............................................................................................................................52
The score-algorithm..........................................................................................................................53
The Shortest Path algorithm.............................................................................................................59
Limits in matrix computation..................................................................................................60
Sparse Linear Systems.........................................................................................................61
Filling factor and matrix dimension...................................................................................................61
The dominance factor.......................................................................................................................62
Algorithms for sparse systems..........................................................................................................63
Sparse Matrix Generator..................................................................................................................65
How to solve sparse linear systems..................................................................................................66
How to solve tridiagonal systems......................................................................................................71
Eigen-problems.......................................................................................................................73
Eigenvalues and Eigenvectors..............................................................................................73
Characteristic Polynomial......................................................................................................73
Roots of the characteristic polynomial..............................................................................................74
Case of symmetric matrix.................................................................................................................74
Example – How to check the Cayley-Hamilton theorem...................................................................76
Eigenvectors..........................................................................................................................77
Step-by-step method........................................................................................................................77
Example - Simple eigenvalues..........................................................................................................77
Example - How to check an eigenvector...........................................................................................78
Example - Eigenvalues with multiplicity............................................................................................79
Example - Eigenvalues with multiplicity not corresponding to the number of eigenvectors..............80
Example - Complex Eigenvalues......................................................................................................80
Example - Complex Matrix................................................................................................................82
Example - How to check a complex eigenvector..............................................................................83
Similarity Transformation......................................................................................................84
Factorization methods......................................................................................................................85
Eigen problems versus resolution methods..........................................................................85
Jacobi transformation of symmetric matrix.......................................................................................86
Orthogonal matrices.........................................................................................................................88
Eigenvalues with the QR factorization method.................................................................................89
Real and complex eigenvalues with the QR method........................................................................91
Complex eigenvalues of a complex matrix with the QR method.......................................................92
How to test complex eigenvalues.....................................................................................................92
How to find polynomial roots with eigenvalues.................................................................................94
Rootfinder with QR algorithm for real and complex polynomials.......................................................94
The power method............................................................................................................................95
Eigensystems with the power method..............................................................................................98
Complex Eigensystems....................................................................................................................99
How to validate an eigen system....................................................................................................100
How to generate a random symmetric matrix with given eigenvalues............................................101
Eigenvalues of a tridiagonal matrix.................................................................................................102
Eigenvalues of a tridiagonal Toeplitz matrix ).................................................................................103
Generalized eigen problem.................................................................................................108
Equivalent asymmetric problem.....................................................................................................108
Equivalent symmetric problem........................................................................................................109
Diagonal matrix...............................................................................................................................110
References.............................................................................................................................116
4