Определитель матрицы

From

Vova Kasatochkin (2:5020/600.3)

To

Vladimir Chizhov

Date

2002-08-08T16:53:20Z

Area

RU.ALGORITHMS

Hello Vladimir.

31 Jul 02 02:03, you wrote to all:

 VC> Народ, есть ли какой-нить алгоритм нахождения определителя матрицы?
 VC> Все умные книжки, бывшие в наличии, перерыл, ничего нет.


=== Cut ===
DECLARE FUNCTION SolveLinearEquation%(A() AS DOUBLE,b() AS DOUBLE)
DECLARE FUNCTION Determinant%(A() AS DOUBLE,det AS DOUBLE)


=== Cut ===

=== Cut ===
'$INCLUDE:'matrix.bi'

DECLARE FUNCTION UpTriangTrans%(A() AS DOUBLE)
DECLARE FUNCTION BackSolve%(A() AS DOUBLE, b() AS DOUBLE, x() AS DOUBLE)

REDIM SHARED RowIndex(0) AS INTEGER
REDIM SHARED ColIndex(0) AS INTEGER

DIM SHARED LoIndex AS INTEGER '1 normally
DIM SHARED UpIndex AS INTEGER 'N normally

DIM SHARED Sign AS INTEGER


FUNCTION UpTriangTrans%(A() AS DOUBLE)
  DIM Column AS INTEGER
  DIM Row AS INTEGER
  DIM pvt AS INTEGER
  DIM c AS INTEGER
  DIM r AS INTEGER
  DIM Maximum AS DOUBLE
  DIM RowMax AS INTEGER
  DIM ColMax AS INTEGER
  DIM i AS INTEGER
  DIM j AS INTEGER
  DIM CPivot AS INTEGER
  DIM RPivot AS INTEGER
  UpTriangTrans%=-1
  Sign=1

  FOR pvt=LoIndex TO (UpIndex-1)
    Maximum=0#
    FOR i=pvt TO UpIndex
      FOR j=pvt TO UpIndex
        IF ABS(A(RowIndex(i),ColIndex(j)))>Maximum THEN
          Maximum=ABS(A(RowIndex(i),ColIndex(j)))
          RowMax=i
          ColMax=j
        END IF
      NEXT j
    NEXT i
    IF Maximum=0# THEN EXIT FUNCTION
    IF ColMax<>pvt THEN
      SWAP ColIndex(ColMax),ColIndex(pvt)
      Sign=-Sign
    END IF
    IF RowMax<>pvt THEN
      SWAP RowIndex(RowMax),RowIndex(pvt)
      Sign=-Sign
    END IF
    CPivot=ColIndex(pvt)
    RPivot=RowIndex(pvt)
    FOR r=pvt+1 TO UpIndex
      Row=RowIndex(r)
      A(Row,CPivot)=-A(Row,CPivot)/A(RPivot,CPivot)
      FOR c=pvt+1 TO UpIndex
        Column=ColIndex(c)
        A(Row,Column)=A(Row,Column)+A(Row,CPivot)*A(RPivot,Column)
      NEXT c
    NEXT r
  NEXT pvt
  UpTriangTrans%=0
END FUNCTION


FUNCTION BackSolve%(A() AS DOUBLE, b() AS DOUBLE, x() AS DOUBLE)
  DIM pvt AS INTEGER
  DIM row AS INTEGER
  DIM col AS INTEGER
  DIM CPivot AS INTEGER
  DIM RPivot AS INTEGER
  FOR pvt=LoIndex TO (UpIndex-1)
    CPivot=ColIndex(pvt)
    FOR row=(pvt+1) TO UpIndex
      RPivot=RowIndex(row)
      b(RPivot)=b(RPivot)+A(RPivot,CPivot)*b(RowIndex(pvt))
    NEXT row
  NEXT pvt
  FOR row=UpIndex TO LoIndex STEP -1
    CPivot=ColIndex(row)
    RPivot=RowIndex(row)
    x(CPivot)=b(RPivot)
    FOR col=(row+1) TO UpIndex
      x(CPivot)=x(CPivot)-A(RPivot,ColIndex(col))*x(ColIndex(col))
    NEXT col
    x(CPivot)=x(CPivot)/A(RPivot,CPivot)
  NEXT row
  BackSolve%=0
END FUNCTION


FUNCTION SolveLinearEquation%(A() AS DOUBLE,b() AS DOUBLE)
  DIM Low AS INTEGER
  DIM High AS INTEGER
  DIM ErrCode AS INTEGER
  DIM x(0) AS DOUBLE
  DIM i AS INTEGER
  Low=LBOUND(A,1)
  High=UBOUND(A,1)
  IF LBOUND(A,2)<>Low OR UBOUND(A,2)<>High OR _
     LBOUND(b)<>Low OR UBOUND(b)<>High THEN
    SolveLinearEquation%=-1
    EXIT FUNCTION
  END IF
  ON LOCAL ERROR GOTO CannotRedim
  LoIndex=1
  UpIndex=High-Low+1
  REDIM x(LoIndex TO UpIndex) AS DOUBLE
  REDIM RowIndex(LoIndex TO UpIndex) AS INTEGER
  REDIM ColIndex(LoIndex TO UpIndex) AS INTEGER
  FOR i=LoIndex TO UpIndex
    RowIndex(i)=Low+i-LoIndex
    ColIndex(i)=Low+i-LoIndex
  NEXT i
  ON LOCAL ERROR GOTO MAthError
  ErrCode=UpTriangTrans%(A())
  IF ErrCode<>0 THEN
    SolveLinearEquation%=-4
    ERASE RowIndex
    ERASE ColIndex
    ERASE x
    LoIndex=0
    UpIndex=0
    EXIT FUNCTION
  END IF
  ErrCode=BackSolve%(A(),b(),x())
  IF ErrCode<>0 THEN
    SolveLinearEquation%=-5
    ERASE RowIndex
    ERASE ColIndex
    ERASE x
    LoIndex=0
    UpIndex=0
    EXIT FUNCTION
  END IF
  FOR i=LoIndex TO UpIndex
    b(i)=x(i)
  NEXT i
  ERASE RowIndex
  ERASE ColIndex
  ERASE x
  LoIndex=0
  UpIndex=0
  SolveLinearEquation%=0
  ExitingSolveLinearEquation:
  EXIT FUNCTION
  CannotRedim:
  SolveLinearEquation%=-2
  RESUME ExitingSolveLinearEquation
  MAthError:
  SolveLinearEquation%=-3
  RESUME ExitingSolveLinearEquation
END FUNCTION

FUNCTION Determinant%(A() AS DOUBLE,det AS DOUBLE)
  DIM Low AS INTEGER
  DIM High AS INTEGER
  DIM ErrCode AS INTEGER
  DIM i AS INTEGER
  Low=LBOUND(A,1)
  High=UBOUND(A,1)
  IF LBOUND(A,2)<>Low OR UBOUND(A,2)<>High THEN
    Determinant%=-1
    EXIT FUNCTION
  END IF
  ON LOCAL ERROR GOTO DeterminantCannotRedim
  LoIndex=1
  UpIndex=High-Low+1
  REDIM RowIndex(LoIndex TO UpIndex) AS INTEGER
  REDIM ColIndex(LoIndex TO UpIndex) AS INTEGER
  FOR i=LoIndex TO UpIndex
    RowIndex(i)=Low+i-LoIndex
    ColIndex(i)=Low+i-LoIndex
  NEXT i
  ON LOCAL ERROR GOTO DeterminantMAthError
  ErrCode=UpTriangTrans%(A())
  IF ErrCode<>0 THEN
    Determinant%=-4
    ERASE RowIndex
    ERASE ColIndex
    LoIndex=0
    UpIndex=0
    EXIT FUNCTION
  END IF
  det=1#
  FOR i=LoIndex TO UpIndex
    det=det*A(RowIndex(i),ColIndex(i))
  NEXT i
  det=Sign*det
  ERASE RowIndex
  ERASE ColIndex
  LoIndex=0
  UpIndex=0
  Determinant%=0
  ExitingDeterminant:
  EXIT FUNCTION
  DeterminantCannotRedim:
  Determinant%=-2
  RESUME ExitingDeterminant
  DeterminantMAthError:
  Determinant%=-3
  RESUME ExitingDeterminant
END FUNCTION



=== Cut ===


 VC> ЗЫ: Бэктрэкинг не предлагать, эт я и сам могу.



Vova

... np: 01 - Dazed And Confused
--- Got no time for spelling rules
 * Origin:  (2:5020/600.3)