home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / MISC / MATH / CLA20.ZIP / CLA20.DOC < prev    next >
Encoding:
Text File  |  1991-02-08  |  17.6 KB  |  418 lines
  1.  
  2.          ####      ####           ##            ####           #####
  3.         ##  ##      ##           ####          ##  ##         ##   ##
  4.        ##           ##          ##  ##             ##         ##   ##
  5.        ##           ##          ##  ##           ###          ##   ##
  6.        ##           ##   #      ######          ##            ##   ##
  7.         ##  ##      ##  ##      ##  ##         ##  ##    ##   ##   ##
  8.          ####      #######      ##  ##         ######    ##    #####
  9.  
  10.  
  11.        The CLA uses constants, types, procedures and functions defined  in 6
  12. units. Some of them are described below. The *.PAS files are samples showing
  13. how to use these objects in user Turbo Pascal programs.
  14.         Every program that uses these objects, must have the compiler direc-
  15. tives {$E+,N+} and {$M 65520, 0, 655200}.
  16.  
  17.  
  18. ------------------------------ BASFPTC UNIT ----------------------------------
  19.  
  20.  (BASic Functions, Procedures, Types and Constants - is used by the others
  21.   units too)
  22.  
  23. const
  24.   MaxM = 20;  { maximal value of the  quantity  of rows  in each matrix }
  25.   MaxN = 20;  { maximal value of the quantity of columns in each matrix }
  26.  
  27. type
  28.   matrix = record
  29.     m, n: byte;             { m, n = quantities of rows, columns of matrix }
  30.     a: array[1..MaxM, 1..(MaxN + 1)] of real;          { matrix's elements }
  31.   end;
  32.  
  33.   vector = array[1..MaxN] of real;
  34.  
  35.   answer = record                { RECORD USED TO SOLVE LINEAR SYSTEMS     }
  36.     ParticularSolution: vector;  { system's particular solution            }
  37.     x: matrix;                   { general solution matrix                 }
  38.     homogenous,                  { tells whether the system is homogeneous }
  39.     impossible,                  { tells whether the system is  impossible }
  40.     DetSyst,                     { tells whether the system is  determined }
  41.     ManyEq: boolean;             { tells whether the system  has too  many }
  42.   end;                           {                               equations }
  43.  
  44.   function Rat(x: real; tam1, tam2: byte): string;
  45.            ---> Writes the real x in  rational format  p/q  if  p = 1  or
  46.            q <= MaxQ = 200 (can be  changed in  CONFIG.EXE).  Is  used  a
  47.            field of width tam1. If x can't be  write in  p/q  form,  then
  48.            Rat returns x in the real format x:tam1:tam2.
  49.            Ex.: Rat(0.5, 3, 0) = '1/2', Rat(-0.333333333, 4, 0) = '-1/3',
  50.                 Rat(0.25, 6, 0) = '   1/4', Rat(Pi, 7, 2) = '   3.14'
  51.  
  52.  
  53. ------------------------------- MATRICES UNIT --------------------------------
  54.  
  55.  procedure TriangularMatrix(var mat: matrix; option: byte); ---> Calculates
  56.            a triangular form to matrix mat;  option = 1, 2 or 3 and defines
  57.            the triangularization method.
  58.  
  59.  procedure InverseMatrix(var mat: matrix; var inversible: boolean);
  60.            ---> Finds the  inverse  matrix  of mat;  the boolean  parameter
  61.            inversible is false if mat has no inverse.
  62.  
  63.  procedure SolveSystem(mat: matrix; var solution: answer); ---> Solves  the
  64.            linear system whose  complete  matrix  is  mat; the  solution is
  65.            given by the second parameter.
  66.  
  67.  function Det(mat: matrix): real; ---> Determinant of mat.
  68.  
  69.  function DimNullSubespace(mat: matrix; lambda: real; n: byte): byte;
  70.                                                                 n
  71.            ---> dimension  of  the  kernel  of  (mat - lambda*I)
  72.  
  73.  
  74. -------------------------------- EQUATION UNIT -------------------------------
  75.  
  76. const
  77.   MaxDegree = 30;  { the greatest degree allowed to a polynomial equation }
  78.  
  79. type
  80.   polynomial = record
  81.     coef: array[0..MaxDegree + 1] of real;   { equation's coefficients }
  82.     degree: byte;                            { equation's degree       }
  83.   end;
  84.  
  85.   complex = record
  86.     Re, Im: real;        { real and imaginary parts of each root       }
  87.     method: string[5];   { method used to solve the equation           }
  88.   end;
  89.  
  90.   solutions = record     { RECORD USED TO SOLVE POLYNOMIAL EQUATIONS   }
  91.     x: array[1..MaxDegree] of complex;              { equation's roots }
  92.     solved: boolean;     { tells whether the resolution was successful }
  93.   end;
  94.  
  95.   procedure SolveEquation(p: polynomial; option: byte; var roots: solutions);
  96.            ---> Calculates the roots of polynomial p. option = 0 (fast
  97.            solution) or option = 1.
  98.  
  99. -------------------------------- LINALG UNIT -------------------------------
  100.  
  101. type
  102.   RealEigenvalue = record
  103.     x: real;     { eigenvalue   }
  104.     mult: byte;  { multiplicity }
  105.   end;
  106.  
  107.   ComplexEigenvalue = record
  108.     a, b: real;  { real and imaginary parts of eigenvalue }
  109.     mult: byte;  { multiplicity }
  110.   end;
  111.  
  112.   eigenvalues = record
  113.     QuantRe, QuantComplex: byte;
  114.     EigenvalueRe: array[1..MaxM] of RealEigenvalue;
  115.     EigenvalueCx: array[1..(MaxM div 2)] of ComplexEigenvalue;
  116.   end;
  117.  
  118.   RealEigenvector = record
  119.     dim, n: byte;
  120.     v: array[1..MaxM] of vector;
  121.   end;
  122.  
  123.   minimal = record
  124.     expo: array[1..MaxM] of byte; { expoents of minimal polynomial }
  125.   end;
  126.  
  127.  procedure CharPoly(mat: matrix; var p: polynomial);     --->  Calculates  the
  128.            characteristic polynomial p of matrix mat.
  129.  
  130.  procedure CalcEigenvalues(p: polynomial; var w: eigenvalues); ---> Calculates
  131.            the eigenvalues w of (characteristic) polynomial p.
  132.  
  133.  procedure CalcEigenvectors(mat: matrix; lambda: real;
  134.                                     var vec: RealEigenvector); ---> Calculates
  135.            the real eigenvectors of matrix mat related to lambda eigenvalue.
  136.  
  137.  procedure MinPoly(mat: matrix; w: eigenvalues; var min: minimal);
  138.            ---> Calculates the expoents  of  the  irredutible  factor  of  the
  139.            minimal polynomial related with a specifyed eigenvalue.
  140.  
  141.  
  142. ------------------------------ JORDAN UNIT ----------------------------------
  143.  
  144. type
  145.   block = record
  146.     lambda: real;                  { real eigenvalue                          }
  147.     QuantBlocksLambda: byte;       { quantity of blocks related to lambda     }
  148.     order: array[1..MaxM] of byte; { order[i] = quantity of blocks  of  order }
  149.   end;                             {            i  related  to lambda         }
  150.  
  151.   DiagBlocks = record
  152.     a: array[1..MaxM] of block;    { blocks of real eigenvalues. Each a[i]    }
  153.                                    { corresponds to a different eigenvalue    }
  154.     QuantTotalBlocks: byte;        { block's total                            }
  155.     QuantEigenvalues: byte;        { quantity of real eigenvalues             }
  156.   end;
  157.  
  158.  procedure CalculatesJordanForm(mat: matrix; w: eigenvalues; min: minimal;
  159.                          var HappenedError: boolean; var diagonal: DiagBlocks);
  160.            ---> Calculates the Jordan form of the matrix mat, whose eigenvalues
  161.            are given by w, minimal polynomial expoents are given by min; if  no
  162.            approximation error occurs, HappenedError  is  false;  the  diagonal
  163.            parameter has all the information wanted. Calls to  many  procedures
  164.            (CharPoly, MinPoly, ...) must be made before.
  165.  
  166.  
  167.  procedure FormatsJordanMatrix(diagonal: DiagBlocks; var FJordan: matrix;
  168.                                 MatOrder: byte; w:  eigenvalues; min: minimal);
  169.            ---> Formats a matrix FJordan that is the Jordan form of the matrix
  170.            mat in the last procedure. One call to CalculatesJordanForm must be
  171.            made before.
  172.  
  173.  procedure CalculatesJordanBasis(mat: matrix; diagonal:DiagBlocks; min:minimal;
  174.                                    var basis: matrix; var FoundBasis: boolean);
  175.            ---> if the parameter FoundBasis is true, then the parameter  basis
  176.            is the Jordan basis of matrix mat. One call to CalculatesJordanForm
  177.            must be made before.
  178.  
  179.  
  180.  -------------------- NUMERICAL EXAMPLES AND OBSERVATIONS --------------------
  181.  
  182.            (All the following matrices are n x n, except the (2))
  183.  
  184.  
  185.  
  186.   1)      | x 1 0 0 ... 0 |
  187.           | 0 x 1 0 ... 0 |         k
  188.       J = | 0 0 x 1 ... 0 |   =>   J    is the matrix whose general term a
  189.           | ... ...    ...|                                               ij
  190.           | 0 0 0 0 ... x |
  191.  
  192.                               k                            k-n+i
  193.   is  0, if  i < j;   a    = x  if i = j;    a    = C     x        if i > j,
  194.                        ij                     ij     k,n-i
  195.  
  196.   where   C    = m!/(n!(m - n)!).
  197.            m,n
  198.  
  199.  
  200.   2)
  201.           | cos(x)  -sen(x) |          k    |  cos(kx)  -sen(kx) |
  202.       M = |                 |   ==>   M  =  |                    |
  203.           | sen(x)   cos(x) |               |  sen(kx)   cos(kx) |
  204.  
  205.  
  206.   3)  | 1 -2  1  0  0  ...  0 | -1     |  1  2  3  4  ...    n  |
  207.       | 0  1 -2  1  0  ...  0 |        |  0  1  2  3  ...   n-1 |
  208.       | 0  0  1 -2  1  ...  0 |    =   |  0  0  1  2  ...   n-2 |
  209.       | ...  ...  ...      ...|        |   ...   ...        ... |
  210.       | 0  0  0  0  0  ...  1 |        |  0  0  0  0  ...    1  |
  211.  
  212.  
  213.   4)  | 0  1  1  1 ...  1 | -1           |  2-n   1   1    ...  1  |
  214.       | 1  0  1  1 ...  1 |              |   1   2-n  1    ...  1  |
  215.       | 1  1  0  1 ...  1 |     = 1/(n-1)|   1    1  2-n   ...  1  |
  216.       | ...  ... ...   ...|              |  ...  ...  ...      ... |
  217.       | 1  1  1  1 ...  0 |              |   1    1   1    ... 2-n |
  218.  
  219.  
  220.   5)  |  2 -1  0  0     ...   0  | -1
  221.       | -1  2 -1  0     ...   0  |
  222.       |  0 -1  2 -1     ...   0  |
  223.       |  ...    ...     ...      |     =
  224.       |  ...    ...    -1  2  0  |
  225.       |  0  0  0  0 ... 0 -1  2  |
  226.  
  227.                           |    1.n    1.(n-1)  1.(n-2)  1.(n-3) ...  1.1  |
  228.                           |  1.(n-1)  2.(n-1)  2.(n-2)  2.(n-3) ...  2.1  |
  229.                           |  1.(n-2)  2.(n-2)  3.(n-2)  3.(n-3) ...  3.1  |
  230.                    1/(n+1)|  1.(n-3)  2.(n-3)  3.(n-3)  4.(n-3) ...  4.1  |
  231.                           |    ...      ...      ...     ...         ...  |
  232.                           |    1.1      2.1      3.1      4.1   ...  n.1  |
  233.  
  234.  
  235.   6)    | 1  2  3  ...  n |
  236.         | 2  3  4  ...  1 |        n(n-1)/2  n-1
  237.      det| 3  4  5  ...  2 |  = (-1)        .n   .(n+1)/2
  238.         | ...  ...     ...|
  239.         | n  1  2  ... n-1|
  240.  
  241.  
  242.   7)    | 1+a     1     1    ...  1  |
  243.         |    1                       |
  244.         |  1     1+a    1    ...  1  |
  245.      det|           2                |  =  a a ...a (1 + 1/a  + ... + 1/a )
  246.         | ...    ...   ...       ... |      1 2    n        1            n
  247.         |  1      1     1    ... 1+a |
  248.         |                           n|
  249.  
  250.  
  251.   8)   | a+b   ab    0    0   ...  0 |
  252.        |   1  a+b   ab    0   ...  0 |      n+1   n+1
  253.     det|   0    1  a+b   ab   ...  0 | =  (a   - b   )/(a-b)
  254.        |  ...    ....    ...     ... |
  255.        |   0    0    0   ...  1  a+b |
  256.  
  257.  
  258.   9)     | a 1 0 0 ... 0 |
  259.          | 0 a 1 0 ... 0 |
  260.      J = | 0 0 a 1 ... 0 |  => the characteristic or minimal polynomial of J is
  261.          | ... ...    ...|                            n
  262.          | 0 0 0 0 ... a |     given by p(x) = (x - a)   (n = order of matrix).
  263.  
  264.  
  265.  10)     | a    a    a    ... a  a  |          | 0   1   0   0  ...  0    0  |
  266.          |  n-1  n-2  n-3      1  0 |          | 0   0   1   0  ...  0    0  |
  267.          |                          |          | 0   0   0   1  ...  0    0  |
  268.      M = |  1    0   0    ... 0   0 |  or  M = | 0   0   0   0  ...  0    0  |
  269.          |  0    1   0    ... 0   0 |          | 0   0   0   0  ...  0    1  |
  270.          |  0    0   1    ... 0   0 |          |  ...    ...         ...     |
  271.          |  ...   ...          ...  |          | a   a   a   a  ... a    a   |
  272.          |  0    0   0    ... 1   0 |          |  0   1   2   3      n-2  n-1|
  273.  
  274.   => the characteristic or minimal polynomial of M is
  275.  
  276.                      n        n-1        n-2            2
  277.              p(x) = x  - a   x    - a   x    - ... - a x  - a x - a
  278.                           n-1        n-2              2      1     0
  279.  
  280.  
  281.  11)     | a  b  b  ...  b |
  282.          | b  a  b  ...  b |
  283.      M = | b  b  a  ...  b |  => the eigenvalues of  M     are  a + (n-1)b with
  284.          | ... ...     ... |                          nxn
  285.          | b  b  b  ...  a |
  286.  
  287.      multiplicity 1  and  (a - b)  with  multiplicity  n - 1.  The  eigenvector
  288.      related to  (a + (n - 1)b)  is  (1, 1, 1, ..., 1)  and  those  related  to
  289.      (a - b)    are    (1, -1, 0, 0, 0, ..., 0),      (1, 0, -1, 0, 0, ..., 0),
  290.      (1, 0, 0, -1, 0, ..., 0),   ...,   (1, 0, 0, ..., 0, -1).
  291.      The characteristic polynomial of M is
  292.                                                          n-1
  293.                      p(x) = (x - (a + (n-1)b))(x - a + b)
  294.  
  295.      and the minimal polynomial is m(x) = (x - (a + (n-1)b))(x - a + b).
  296.  
  297.  12) Let M be the block matrix   M = |  A  O  | where O is the 2x2 null matrix
  298.                                      |  O  B  |
  299.  
  300.   this is, if A is r x r  with general term a  ,  and   B   is   s x s    with
  301.                                              ij
  302.  
  303.   general term b   , then m   = a   if i <= r and j <= r ; m   = b    if i > r
  304.                 ij          ij    ij                        ij    ij
  305.  
  306.   and j > r; m   = 0 if (i > r  and j <= r) or (i <= r and j > r).
  307.               ij
  308.  
  309.           In this case if p (x), p (x) are the characteristic  polynomials  of
  310.                            1      2
  311.   A, B respectively and m (x), m (x)  be  the minimal polynomials  of  A and B
  312.                          1      2
  313.   respectively , then  the  characteristic  polynomial   of  M  is   given  by
  314.   product p (x)p (x)   and the minimal polynomial of M  is  the  least  common
  315.            1    2
  316.   multiple   of   m (x) ,  m (x) .
  317.                    1        2
  318.  
  319.  13) The eigenvalues of L =  |  a  b |  , b <> 0, are a + bi and a - bi.
  320.                              | -b  a |
  321.  
  322.      The minimal and characteristic polynomials of the blocks matrix
  323.  
  324.                            |  L  I  O  ...  O   O  |
  325.                            |  O  L  I  ...  O   O  |
  326.                            |  O  O  L  ...  O   O  |
  327.                            |  ...  ...       ...   |
  328.                            |  O  O  O  ...  L   I  |
  329.                            |  O  O  O  ...  O   L  |
  330.  
  331.      where I is the 2 x 2 identity matrix, O  is the  2 x 2  null  matrix  are
  332.                                     s            s       2          2    2 s
  333.           p(x) = m(x) = (x - a - bi) (x - a + bi)   =  (x  - 2ax + a  + b )
  334.  
  335.      where  s  is the quantity of blocks L.
  336.      This can be used with some itens above to  construct an infinite quantity
  337.      of examples or exercices, all them with previously known answer.
  338.  
  339.      For example,a matrix whose eigenvalues  are  3 + 5i,  3 - 5i, 7, 7, -4 is
  340.  
  341.                              |   3   5   0   0   0  |
  342.                              |  -5   3   0   0   0  |
  343.                      M  =    |   0   0   7   1   0  |
  344.                              |   0   0   0   7   0  |
  345.                              |   0   0   0   0  -4  |
  346.  
  347.      The minimal or characteristic polynomial of M is
  348.  
  349.                                  2         2
  350.                    p(x) = (x - 7) (x + 4)(x  - 6x + 34).
  351.  
  352.      Other example: a matrix whose minimal and  characteristic polynomials are
  353.   both equal to
  354.                          2   2          2
  355.                   (x - 4)  (x  - 3x + 5)      is
  356.  
  357.                          |  4  1  0  0  0  0  |
  358.                          |  0  4  0  0  0  0  |
  359.                          |  0  0  1  2  1  0  |
  360.                   M  =   |  0  0 -2  1  0  1  |
  361.                          |  0  0  0  0  1  2  |
  362.                          |  0  0  0  0 -2  1  |
  363.  
  364.      If we want a matrix with the same minimal or characteristic polynomial as
  365.                            -1
  366.   this, just calculate a  P  MP  similar matrix to M.
  367.  
  368.  
  369.  
  370.  14)   If  J  is  the  Jordan  form  of  a matrix M and B is a basis such that
  371.   [M]   = J   and  if  we think about B as  a matrix with the same order as M,
  372.      B
  373.  then   the   transpose    matrix    P    of   B    will    be    such    that
  374.      -1
  375. J = P  MP. This basis is not unique. For example, the matrix
  376.  
  377.                             |  5   -9  -4  |
  378.                       M  =  |  6  -11  -5  |
  379.                             | -7   13   6  |
  380.  
  381.  is such that                        |  0   1   0 |
  382.                      [M]  = [M]   =  |  0   0   1 |
  383.                         B      B'    |  0   0   0 |
  384.  
  385.  where
  386.  
  387.                B  = { (1, 1, -1), (-4, -5, 6), (0, 0, 1) }
  388.  and
  389.                B' = { (-1, -1, 1), (5, 6, -7), (1, 0, 0) }
  390.  
  391.  
  392.  
  393.  15)  The following P and Q  matrices have the same characteristic polyunomial
  394.                  4                                                     2
  395.  ( p(x) = (x - 5)   ),  the  same  minimal  polynomial  (m(x) = (x - 5)  ) but
  396.  
  397.  they are not similar, because their Jordan forms are not the same.
  398.  
  399.  
  400.             |  43  24  12   4  |                         |  5  1  0  0  |
  401.         P = | -95 -55 -30 -10  |   ( Jordan form of P =  |  0  5  0  0  | )
  402.             |  76  48  29   8  |                         |  0  0  5  0  |
  403.             | -19 -12  -6   3  |                         |  0  0  0  5  |
  404.  
  405.  
  406.             |   53/7   15/7   -1/7    2/7  |
  407.         Q = |   45/7   76/7    1/7    5/7  |   ( Jordan form of Q =
  408.             |  -45/7  -41/7   34/7   -5/7  |
  409.             | -522/7 -463/7    1/7  -23/7  |
  410.                                                             |  5  1  0  0  |
  411.                                                             |  0  5  0  0  | )
  412.                                                             |  0  0  5  1  |
  413.                                                             |  0  0  0  5  |
  414.  
  415.  
  416. ---------------------------- END OF "CLA20.DOC" ------------------------------
  417.  
  418.