home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The World of Computer Software
/
World_Of_Computer_Software-02-386-Vol-2of3.iso
/
c
/
cla20.zip
/
CLA20.DOC
< prev
next >
Wrap
Text File
|
1991-02-08
|
18KB
|
418 lines
#### #### ## #### #####
## ## ## #### ## ## ## ##
## ## ## ## ## ## ##
## ## ## ## ### ## ##
## ## # ###### ## ## ##
## ## ## ## ## ## ## ## ## ## ##
#### ####### ## ## ###### ## #####
The CLA uses constants, types, procedures and functions defined in 6
units. Some of them are described below. The *.PAS files are samples showing
how to use these objects in user Turbo Pascal programs.
Every program that uses these objects, must have the compiler direc-
tives {$E+,N+} and {$M 65520, 0, 655200}.
------------------------------ BASFPTC UNIT ----------------------------------
(BASic Functions, Procedures, Types and Constants - is used by the others
units too)
const
MaxM = 20; { maximal value of the quantity of rows in each matrix }
MaxN = 20; { maximal value of the quantity of columns in each matrix }
type
matrix = record
m, n: byte; { m, n = quantities of rows, columns of matrix }
a: array[1..MaxM, 1..(MaxN + 1)] of real; { matrix's elements }
end;
vector = array[1..MaxN] of real;
answer = record { RECORD USED TO SOLVE LINEAR SYSTEMS }
ParticularSolution: vector; { system's particular solution }
x: matrix; { general solution matrix }
homogenous, { tells whether the system is homogeneous }
impossible, { tells whether the system is impossible }
DetSyst, { tells whether the system is determined }
ManyEq: boolean; { tells whether the system has too many }
end; { equations }
function Rat(x: real; tam1, tam2: byte): string;
---> Writes the real x in rational format p/q if p = 1 or
q <= MaxQ = 200 (can be changed in CONFIG.EXE). Is used a
field of width tam1. If x can't be write in p/q form, then
Rat returns x in the real format x:tam1:tam2.
Ex.: Rat(0.5, 3, 0) = '1/2', Rat(-0.333333333, 4, 0) = '-1/3',
Rat(0.25, 6, 0) = ' 1/4', Rat(Pi, 7, 2) = ' 3.14'
------------------------------- MATRICES UNIT --------------------------------
procedure TriangularMatrix(var mat: matrix; option: byte); ---> Calculates
a triangular form to matrix mat; option = 1, 2 or 3 and defines
the triangularization method.
procedure InverseMatrix(var mat: matrix; var inversible: boolean);
---> Finds the inverse matrix of mat; the boolean parameter
inversible is false if mat has no inverse.
procedure SolveSystem(mat: matrix; var solution: answer); ---> Solves the
linear system whose complete matrix is mat; the solution is
given by the second parameter.
function Det(mat: matrix): real; ---> Determinant of mat.
function DimNullSubespace(mat: matrix; lambda: real; n: byte): byte;
n
---> dimension of the kernel of (mat - lambda*I)
-------------------------------- EQUATION UNIT -------------------------------
const
MaxDegree = 30; { the greatest degree allowed to a polynomial equation }
type
polynomial = record
coef: array[0..MaxDegree + 1] of real; { equation's coefficients }
degree: byte; { equation's degree }
end;
complex = record
Re, Im: real; { real and imaginary parts of each root }
method: string[5]; { method used to solve the equation }
end;
solutions = record { RECORD USED TO SOLVE POLYNOMIAL EQUATIONS }
x: array[1..MaxDegree] of complex; { equation's roots }
solved: boolean; { tells whether the resolution was successful }
end;
procedure SolveEquation(p: polynomial; option: byte; var roots: solutions);
---> Calculates the roots of polynomial p. option = 0 (fast
solution) or option = 1.
-------------------------------- LINALG UNIT -------------------------------
type
RealEigenvalue = record
x: real; { eigenvalue }
mult: byte; { multiplicity }
end;
ComplexEigenvalue = record
a, b: real; { real and imaginary parts of eigenvalue }
mult: byte; { multiplicity }
end;
eigenvalues = record
QuantRe, QuantComplex: byte;
EigenvalueRe: array[1..MaxM] of RealEigenvalue;
EigenvalueCx: array[1..(MaxM div 2)] of ComplexEigenvalue;
end;
RealEigenvector = record
dim, n: byte;
v: array[1..MaxM] of vector;
end;
minimal = record
expo: array[1..MaxM] of byte; { expoents of minimal polynomial }
end;
procedure CharPoly(mat: matrix; var p: polynomial); ---> Calculates the
characteristic polynomial p of matrix mat.
procedure CalcEigenvalues(p: polynomial; var w: eigenvalues); ---> Calculates
the eigenvalues w of (characteristic) polynomial p.
procedure CalcEigenvectors(mat: matrix; lambda: real;
var vec: RealEigenvector); ---> Calculates
the real eigenvectors of matrix mat related to lambda eigenvalue.
procedure MinPoly(mat: matrix; w: eigenvalues; var min: minimal);
---> Calculates the expoents of the irredutible factor of the
minimal polynomial related with a specifyed eigenvalue.
------------------------------ JORDAN UNIT ----------------------------------
type
block = record
lambda: real; { real eigenvalue }
QuantBlocksLambda: byte; { quantity of blocks related to lambda }
order: array[1..MaxM] of byte; { order[i] = quantity of blocks of order }
end; { i related to lambda }
DiagBlocks = record
a: array[1..MaxM] of block; { blocks of real eigenvalues. Each a[i] }
{ corresponds to a different eigenvalue }
QuantTotalBlocks: byte; { block's total }
QuantEigenvalues: byte; { quantity of real eigenvalues }
end;
procedure CalculatesJordanForm(mat: matrix; w: eigenvalues; min: minimal;
var HappenedError: boolean; var diagonal: DiagBlocks);
---> Calculates the Jordan form of the matrix mat, whose eigenvalues
are given by w, minimal polynomial expoents are given by min; if no
approximation error occurs, HappenedError is false; the diagonal
parameter has all the information wanted. Calls to many procedures
(CharPoly, MinPoly, ...) must be made before.
procedure FormatsJordanMatrix(diagonal: DiagBlocks; var FJordan: matrix;
MatOrder: byte; w: eigenvalues; min: minimal);
---> Formats a matrix FJordan that is the Jordan form of the matrix
mat in the last procedure. One call to CalculatesJordanForm must be
made before.
procedure CalculatesJordanBasis(mat: matrix; diagonal:DiagBlocks; min:minimal;
var basis: matrix; var FoundBasis: boolean);
---> if the parameter FoundBasis is true, then the parameter basis
is the Jordan basis of matrix mat. One call to CalculatesJordanForm
must be made before.
-------------------- NUMERICAL EXAMPLES AND OBSERVATIONS --------------------
(All the following matrices are n x n, except the (2))
1) | x 1 0 0 ... 0 |
| 0 x 1 0 ... 0 | k
J = | 0 0 x 1 ... 0 | => J is the matrix whose general term a
| ... ... ...| ij
| 0 0 0 0 ... x |
k k-n+i
is 0, if i < j; a = x if i = j; a = C x if i > j,
ij ij k,n-i
where C = m!/(n!(m - n)!).
m,n
2)
| cos(x) -sen(x) | k | cos(kx) -sen(kx) |
M = | | ==> M = | |
| sen(x) cos(x) | | sen(kx) cos(kx) |
3) | 1 -2 1 0 0 ... 0 | -1 | 1 2 3 4 ... n |
| 0 1 -2 1 0 ... 0 | | 0 1 2 3 ... n-1 |
| 0 0 1 -2 1 ... 0 | = | 0 0 1 2 ... n-2 |
| ... ... ... ...| | ... ... ... |
| 0 0 0 0 0 ... 1 | | 0 0 0 0 ... 1 |
4) | 0 1 1 1 ... 1 | -1 | 2-n 1 1 ... 1 |
| 1 0 1 1 ... 1 | | 1 2-n 1 ... 1 |
| 1 1 0 1 ... 1 | = 1/(n-1)| 1 1 2-n ... 1 |
| ... ... ... ...| | ... ... ... ... |
| 1 1 1 1 ... 0 | | 1 1 1 ... 2-n |
5) | 2 -1 0 0 ... 0 | -1
| -1 2 -1 0 ... 0 |
| 0 -1 2 -1 ... 0 |
| ... ... ... | =
| ... ... -1 2 0 |
| 0 0 0 0 ... 0 -1 2 |
| 1.n 1.(n-1) 1.(n-2) 1.(n-3) ... 1.1 |
| 1.(n-1) 2.(n-1) 2.(n-2) 2.(n-3) ... 2.1 |
| 1.(n-2) 2.(n-2) 3.(n-2) 3.(n-3) ... 3.1 |
1/(n+1)| 1.(n-3) 2.(n-3) 3.(n-3) 4.(n-3) ... 4.1 |
| ... ... ... ... ... |
| 1.1 2.1 3.1 4.1 ... n.1 |
6) | 1 2 3 ... n |
| 2 3 4 ... 1 | n(n-1)/2 n-1
det| 3 4 5 ... 2 | = (-1) .n .(n+1)/2
| ... ... ...|
| n 1 2 ... n-1|
7) | 1+a 1 1 ... 1 |
| 1 |
| 1 1+a 1 ... 1 |
det| 2 | = a a ...a (1 + 1/a + ... + 1/a )
| ... ... ... ... | 1 2 n 1 n
| 1 1 1 ... 1+a |
| n|
8) | a+b ab 0 0 ... 0 |
| 1 a+b ab 0 ... 0 | n+1 n+1
det| 0 1 a+b ab ... 0 | = (a - b )/(a-b)
| ... .... ... ... |
| 0 0 0 ... 1 a+b |
9) | a 1 0 0 ... 0 |
| 0 a 1 0 ... 0 |
J = | 0 0 a 1 ... 0 | => the characteristic or minimal polynomial of J is
| ... ... ...| n
| 0 0 0 0 ... a | given by p(x) = (x - a) (n = order of matrix).
10) | a a a ... a a | | 0 1 0 0 ... 0 0 |
| n-1 n-2 n-3 1 0 | | 0 0 1 0 ... 0 0 |
| | | 0 0 0 1 ... 0 0 |
M = | 1 0 0 ... 0 0 | or M = | 0 0 0 0 ... 0 0 |
| 0 1 0 ... 0 0 | | 0 0 0 0 ... 0 1 |
| 0 0 1 ... 0 0 | | ... ... ... |
| ... ... ... | | a a a a ... a a |
| 0 0 0 ... 1 0 | | 0 1 2 3 n-2 n-1|
=> the characteristic or minimal polynomial of M is
n n-1 n-2 2
p(x) = x - a x - a x - ... - a x - a x - a
n-1 n-2 2 1 0
11) | a b b ... b |
| b a b ... b |
M = | b b a ... b | => the eigenvalues of M are a + (n-1)b with
| ... ... ... | nxn
| b b b ... a |
multiplicity 1 and (a - b) with multiplicity n - 1. The eigenvector
related to (a + (n - 1)b) is (1, 1, 1, ..., 1) and those related to
(a - b) are (1, -1, 0, 0, 0, ..., 0), (1, 0, -1, 0, 0, ..., 0),
(1, 0, 0, -1, 0, ..., 0), ..., (1, 0, 0, ..., 0, -1).
The characteristic polynomial of M is
n-1
p(x) = (x - (a + (n-1)b))(x - a + b)
and the minimal polynomial is m(x) = (x - (a + (n-1)b))(x - a + b).
12) Let M be the block matrix M = | A O | where O is the 2x2 null matrix
| O B |
this is, if A is r x r with general term a , and B is s x s with
ij
general term b , then m = a if i <= r and j <= r ; m = b if i > r
ij ij ij ij ij
and j > r; m = 0 if (i > r and j <= r) or (i <= r and j > r).
ij
In this case if p (x), p (x) are the characteristic polynomials of
1 2
A, B respectively and m (x), m (x) be the minimal polynomials of A and B
1 2
respectively , then the characteristic polynomial of M is given by
product p (x)p (x) and the minimal polynomial of M is the least common
1 2
multiple of m (x) , m (x) .
1 2
13) The eigenvalues of L = | a b | , b <> 0, are a + bi and a - bi.
| -b a |
The minimal and characteristic polynomials of the blocks matrix
| L I O ... O O |
| O L I ... O O |
| O O L ... O O |
| ... ... ... |
| O O O ... L I |
| O O O ... O L |
where I is the 2 x 2 identity matrix, O is the 2 x 2 null matrix are
s s 2 2 2 s
p(x) = m(x) = (x - a - bi) (x - a + bi) = (x - 2ax + a + b )
where s is the quantity of blocks L.
This can be used with some itens above to construct an infinite quantity
of examples or exercices, all them with previously known answer.
For example,a matrix whose eigenvalues are 3 + 5i, 3 - 5i, 7, 7, -4 is
| 3 5 0 0 0 |
| -5 3 0 0 0 |
M = | 0 0 7 1 0 |
| 0 0 0 7 0 |
| 0 0 0 0 -4 |
The minimal or characteristic polynomial of M is
2 2
p(x) = (x - 7) (x + 4)(x - 6x + 34).
Other example: a matrix whose minimal and characteristic polynomials are
both equal to
2 2 2
(x - 4) (x - 3x + 5) is
| 4 1 0 0 0 0 |
| 0 4 0 0 0 0 |
| 0 0 1 2 1 0 |
M = | 0 0 -2 1 0 1 |
| 0 0 0 0 1 2 |
| 0 0 0 0 -2 1 |
If we want a matrix with the same minimal or characteristic polynomial as
-1
this, just calculate a P MP similar matrix to M.
14) If J is the Jordan form of a matrix M and B is a basis such that
[M] = J and if we think about B as a matrix with the same order as M,
B
then the transpose matrix P of B will be such that
-1
J = P MP. This basis is not unique. For example, the matrix
| 5 -9 -4 |
M = | 6 -11 -5 |
| -7 13 6 |
is such that | 0 1 0 |
[M] = [M] = | 0 0 1 |
B B' | 0 0 0 |
where
B = { (1, 1, -1), (-4, -5, 6), (0, 0, 1) }
and
B' = { (-1, -1, 1), (5, 6, -7), (1, 0, 0) }
15) The following P and Q matrices have the same characteristic polyunomial
4 2
( p(x) = (x - 5) ), the same minimal polynomial (m(x) = (x - 5) ) but
they are not similar, because their Jordan forms are not the same.
| 43 24 12 4 | | 5 1 0 0 |
P = | -95 -55 -30 -10 | ( Jordan form of P = | 0 5 0 0 | )
| 76 48 29 8 | | 0 0 5 0 |
| -19 -12 -6 3 | | 0 0 0 5 |
| 53/7 15/7 -1/7 2/7 |
Q = | 45/7 76/7 1/7 5/7 | ( Jordan form of Q =
| -45/7 -41/7 34/7 -5/7 |
| -522/7 -463/7 1/7 -23/7 |
| 5 1 0 0 |
| 0 5 0 0 | )
| 0 0 5 1 |
| 0 0 0 5 |
---------------------------- END OF "CLA20.DOC" ------------------------------
