Funktionale Programmierung als Beispiel für die Arbeit mit Matrizen aus der Theorie der linearen Algebra

Einführung


Die Grundlage für die Arbeit mit Matrizen (in diesem Artikel werden nur zweidimensionale Matrizen betrachtet) ist eine leistungsfähige mathematische Theorie aus dem Bereich der linearen Algebra. Eine Definition oder Aktion folgt aus einer anderen, eine Funktion ruft eine andere auf. Für die funktionale Implementierung der Funktion mathematischer Operationen auf Matrizen passen funktionale Sprachen daher sehr gut. In diesem Artikel werden wir uns spezifische Beispiele in F # ansehen und detaillierte Kommentare dazu geben, wie dies funktioniert. Da F # Teil der .NET-Familie ist, kann die resultierende Funktionalität problemlos in anderen wichtigen Sprachen verwendet werden, z. B. C #.

Matrixdefinition und Implementierung in F #


Matrizen sind der grundlegende und wichtigste Teil der linearen Algebra. Matrizen werden häufig in der Programmierung verwendet, beispielsweise bei der 3D-Modellierung oder der Spieleentwicklung. Natürlich ist das Fahrrad seit langem erfunden und die notwendigen Rahmenbedingungen für die Arbeit mit Matrizen sind bereits bereit und können und sollten verwendet werden. Dieser Artikel zielt nicht darauf ab, ein neues Framework zu erfinden, sondern zeigt die Implementierung grundlegender mathematischer Operationen für die Arbeit mit Matrizen in einem funktionalen Stil unter Verwendung der Programmiersprache F #. Während wir das Material untersuchen, wenden wir uns der mathematischen Theorie der Matrizen zu und sehen, wie sie in Code implementiert werden kann.

Erinnern wir uns zunächst daran, was eine Matrix ist. Die Theorie sagt uns Folgendes
Eine rechteckige Zahlentabelle mit m Zeilen und n Spalten wird als Matrix der Größe mxn bezeichnet

Matrizen werden normalerweise mit Großbuchstaben des lateinischen Alphabets bezeichnet und als geschrieben

A=(a11a12...a1na21a22...a2n............am1am2...amn)



Oder kurz

A=(aij)



Um mit Matrizen in F # zu arbeiten, erstellen wir einen Datensatz basierend auf einer zweidimensionalen Tabelle, den wir mit nützlichen Methoden erweitern, um die erforderlichen mathematischen Operationen daran durchzuführen.

type Matrix = { values: int[,] }
    with
        //    
    end

Fügen Sie eine Hilfsmethode hinzu, um die Aufzeichnung mit einem zweidimensionalen Array zu initialisieren

static member ofArray2D (values: int [,]) = 
    { values = values }

Das Eingabeargument für die Funktion ist ein zweidimensionales Array und an seiner Ausgabe ein Datensatz vom Typ Matrix . Unten finden Sie ein Beispiel für die Datensatzinitialisierung.

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

Zwei Matrizen A = (aij) und B = (bij) werden als gleich bezeichnet, wenn sie elementweise zusammenfallen, d.h. aij = bij für alle i = 1,2 ..., m und j = 1,2 ... n

Um diese Regel zu implementieren, werden wir den überschriebenen Operator == verwenden und einige nützliche Funktionen hinzufügen, die wir auch in Zukunft benötigen werden.

static member sizes matrix =
    let rows = matrix.values.[*,0].Length
    let cols = matrix.values.[0,*].Length
    (rows, cols)

static member isEquallySized matrix1 matrix2 =
    let dim1 = Matrix.sizes matrix1
    let dim2 = Matrix.sizes matrix2
    (dim1 = dim2)

static member (==) (matrix1, matrix2) =
    if not (Matrix.isEquallySized matrix1 matrix2) then false
    else
        not (matrix1.values
               |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
               |> Seq.cast<bool>
               |> Seq.contains false)

Schauen wir uns den obigen Code genauer an. Wie Sie sehen können, gibt es drei Funktionen. Die erste Größenfunktion gibt die Dimension der Matrix als Tupel zurück. Da wir nur mit rechteckigen Matrizen arbeiten, um die Anzahl der Zeilen zu ermitteln, nehmen wir einen vollständigen Ausschnitt der ersten Spalte und geben deren Länge zurück.

let rows = matrix.values.[*,0].Length

Das Bestimmen der Anzahl der Spalten funktioniert auf ähnliche Weise: Wir erhalten einen vollständigen Ausschnitt der ersten Zeile und geben deren Länge zurück.

Die folgende Funktion isEquallySized vergleicht die Dimension zweier Matrizen und gibt true zurück , wenn sie gleich sind. Dazu verwendet es die Funktion für vorgefertigte Größen und vergleicht einfach die Ergebnisse.

Der Operator == zum elementweisen Vergleichen zweier Matrizen scheint komplizierter zu sein, aber jetzt werden Sie sehen, dass es auch einfach ist.

Bevor wir zwei Matrizen vergleichen, vergleichen wir ihre Dimension. Wenn sie nicht gleich sind, gibt es keinen weiteren Grund für die Überprüfung, da bereits klar ist, dass die Matrizen nicht gleich sind.

if not (Matrix.isEquallySized matrix1 matrix2) then false

Als nächstes bilden wir basierend auf den ursprünglichen Matrizen Matrix1 und Matrix2 eine neue Matrix, die mit wahr oder falsch gefüllt ist , je nachdem, ob die entsprechenden Zellen beider Matrizen zusammenfallen.

matrix1.values
|> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true

Die Array2D.mapi Funktion iteriert über alle Elemente des matrix1 und leitet drei Parameter
x an den Handler - Zeilenindex
y - Spaltenindex
v -
Zellinhalt Wir der COMPARE Inhalt der Zelle V mit der entsprechenden Zelle matrix2 und wenn sie gleich sind, dann schreibe wahr , ansonsten falsch .

Wenn es mindestens eine Zelle mit dem falschen Element gibt , bedeutet dies, dass die Matrizen nicht gleich sind.

Da Array2D keine Methoden zum Filtern oder Suchen enthält, werden wir dies selbst implementieren. Dazu zerlegen wir die Matrix in eine lineare Liste

|> Seq.cast<bool>

Und finde mindestens eine Nichtübereinstimmung

|> Seq.contains false

Die Funktion Seq.contains gibt true zurück, wenn mindestens ein falscher Wert in der erweiterten Liste gefunden wird . Daher müssen wir das Ergebnis invertieren, damit der Operator == so funktioniert, wie wir es möchten

else
    not (matrix1.values
           |> Array2D.mapi (fun x y v -> if matrix2.values.[x, y] <> v then false else true)
           |> Seq.cast<bool>
           |> Seq.contains false)

Eine Matrix O wird als Null- oder Nullmatrix bezeichnet, wenn alle ihre Elemente gleich Null sind.


static member O rows cols =
    let array2d = Array2D.zeroCreate rows cols
    { values = array2d }

Ein Beispiel für die Verwendung dieser Funktion

let AO = Matrix.O 5 5

Ich glaube, dass es nichts Kompliziertes gibt, das einer Erklärung bedarf, also fahren wir fort.
Eine Matrix, deren Anzahl von Zeilen gleich der Anzahl von Spalten und gleich n ist, wird als quadratische Matrix der Ordnung n bezeichnet

Somit hat die quadratische Matrix die Form.

A=[a11a12...a1na21a22...a2n............an1an2...ann]


Als Teil dieser Regel erstellen wir eine Funktion, die eine rechteckige Matrix in eine quadratische Matrix umwandelt, indem alle Elemente abgeschnitten werden, die nicht in das Quadrat fallen.

static member toSquare matrix =

    //    
    let dim = Matrix.sizes matrix

    //   
    let colCount: int = snd dim
    //   
    let rowCount: int = fst dim

    //    
    let length = System.Math.Min (colCount, rowCount)

    //      
    //     
    let zero = Array2D.zeroCreate length length

    //     
    let square = zero |> Array2D.mapi (fun x y _ -> matrix.values.[x, y])

    //   
    { values = square }

Kommentare im Quellcode erklären, wie die Funktion funktioniert. Fahren wir also fort.
Eine quadratische Matrix wird als dreieckig bezeichnet, wenn alle ihre Elemente unterhalb der Hauptdiagonale gleich Null sind, d. H. Die dreieckige Matrix hat die Form

T=(a11a12...a1n0a22...a2n............00...ann)


Unten finden Sie den Funktionscode, der die ursprüngliche Matrix in eine dreieckige Matrix konvertiert. Aber in unserer Funktion werden wir mit einer rechteckigen Matrix arbeiten, das heißt, sie ist möglicherweise nicht quadratisch. Der Leser kann den Funktionscode leicht so ändern, dass er mit der zuvor untersuchten Funktion eine quadratische Dreiecksmatrix zurückgibt.

static member T matrix =
    let values = matrix.values |> Array2D.mapi (fun x y v -> if y < x then 0 else v)
    { values = values }

Die Funktion Array2D.mapi konvertiert das ursprüngliche zweidimensionale Array mithilfe eines Handlers, der drei Parameter verwendet:

x - Zeilennummer
y - Spaltennummer
v - Zelleninhalt, in ein neues

if y < x then 0 else v

Hier prüfen wir, ob das Element unterhalb der Hauptdiagonale liegt, und wenn ja, füllen Sie Zelle 0. Andernfalls den Anfangswert aus der Eingabematrix.

Das Folgende ist ein Beispiel für die Verwendung dieser Funktion.

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.triangular A
printfn "origin = \n %A" A.values
printfn "triangular = \n %A" R.values

Wir erhalten das folgende Ergebnis

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
triangular = 
 [[1; 2; 3]
 [0; 5; 6]
 [0; 0; 9]
 [0; 0; 0]]

Eine quadratische Matrix wird als Diagonale bezeichnet, wenn alle ihre Elemente außerhalb der Hauptdiagonale gleich Null sind


static member D matrix =
    let diagonal = matrix.values |> Array2D.mapi (fun x y v -> if x <> y then 0 else v)
    { values = diagonal }

Diese Funktion ist der vorherigen sehr ähnlich, nur die Überprüfungsbedingung ist unterschiedlich. Unten finden Sie ein Anwendungsbeispiel

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R = Matrix.D A
printfn "origin = \n %A" A.values
printfn "diagonal = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
diagonal = 
 [[1; 0; 0]
 [0; 5; 0]
 [0; 0; 9]
 [0; 0; 0]]

Die Diagonalmatrix ist eine Einheit und wird mit E bezeichnet, wenn alle auf der Hauptdiagonale befindlichen Elemente gleich Eins sind

E=(10...001...0............00...1)


Die Implementierung einer solchen Matrix auf F # sieht so aus

static member E rows cols =
    let array2d = Array2D.init rows cols (fun x y -> if x = y then 1 else 0)
    { values = array2d }

Matrixoperationen mit F #


Eine Reihe von Aktionen kann sowohl für Matrizen als auch für Zahlen ausgeführt werden, von denen einige Operationen mit Zahlen ähnlich sind und einige spezifisch sind.
Die Summe zweier Matrizen Amn = (aij) und Bmn = (bij) gleicher Größe ist die Matrix gleicher Größe A + B = Cmn = (cij) , deren Elemente gleich der Summe der Elemente der Matrizen A und B sind, die sich an den entsprechenden Stellen befinden

cij=aij+bij,i=1,2,...,m,j=1,2,...,n


Beispiel: Für gegebene Matrizen A und B finden wir die Summe A + B.

A=(231506),B=(331720),A+B=(162226)


Betrachten Sie den Code zum Hinzufügen von zwei Matrizen

static member (+) (matrix1, matrix2) =
    if Matrix.isEquallySized matrix1 matrix2 then
        let array2d = matrix1.values |> Array2D.mapi (fun x y v -> matrix2.values.[x, y] + v)
        { values = array2d }
    else failwith "matrix1 is not equal to matrix2"

Bevor Sie Matrizen hinzufügen, müssen Sie sicherstellen, dass ihre Dimension übereinstimmt. Andernfalls löst die Funktion eine Ausnahme aus. Unten finden Sie ein Beispiel für die Verwendung dieser Funktion

let a = array2D [[2;3]
                 [1;-5]
                 [0;6]]
let A = Matrix.ofArray2D a

let b = array2D [[-3;3]
                 [1;7]
                 [2;0]]
let B = Matrix.ofArray2D b

let R = A+B
printfn "A+B =\n %A" R.values

A+B =
 [[-1; 6]
 [2; 2]
 [2; 6]]

Das Produkt der Matrix A = (aij) mit der Zahl k ist die Matrix kA = (kaij) mit der gleichen Größe wie die Matrix A, die durch Multiplizieren aller Elemente der Matrix A mit der Zahl k erhalten wird

Beispiel: Für eine gegebene Matrix A finden wir die Matrix 3A

A=(230154),3A=(69031512)



static member (*) (value, matrix) = 
    let array2d = matrix.values |> Array2D.mapi (fun _ _ v -> v * value)
    { values = array2d }

Matrix -A = (- 1) * A wird die entgegengesetzte Matrix A genannt . Von dieser Definition gehen wir reibungslos zur nächsten über
Die Differenz der gleich großen Matrizen A und B ist die Summe der Matrix A und der Matrix gegenüber von B.

static member (-) (matrix1: Matrix, matrix2: Matrix) = 
    if Matrix.isEquallySized matrix1 matrix2 then
        matrix1 + (-1)*matrix2
    else failwith "matrix1 is not equal to matrix2"

Zwei Matrizen werden als konsistent bezeichnet, wenn die Anzahl der Spalten der ersten gleich der Anzahl der Zeilen der zweiten ist

A=(2103),B=(05211437)



static member isMatched matrix1 matrix2 = 
    let row1Count = matrix1.values.[0,*].Length
    let col2Count = matrix2.values.[*,0].Length

    row1Count = col2Count

Eine Matrixkonsistenzprüfung ist erforderlich, um sie zu multiplizieren.
Das Produkt AB kohärente Matrix Amn = (aij) und Bnp = (bjk) ist die Matrix Cmn = (CIK) , Element CIK wird als die Summe der Elemente berechnet i -ten Reihe der Matrix A und die entsprechenden Elemente der k - ten Spalte der Matrix B

Berechnen Sie das Produkt der Matrizen

A=(102310),B=(105120)


Entscheidung zur Bestimmung des Matrizenprodukts

AB=(1(1)+05+2(2)10+01+203(1)+15+0(2)30+11+00)=(5021)


Betrachten Sie den Code zum Multiplizieren von zwei Matrizen

static member (*) (matrix1, (matrix2: Matrix)) =
    if Matrix.isMatched matrix1 matrix2 then
        let row1Count = matrix1.values.[*,0].Length
        let col2Count = matrix2.values.[0,*].Length

        let values = Array2D.zeroCreate row1Count col2Count

        for r in 0..row1Count-1 do
            for c in 0..col2Count-1 do
                let row = Array.toList matrix1.values.[r,*]
                let col = Array.toList matrix2.values.[*,c]

                let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col
                values.[r,c] <- cell

        { values = values }

    else failwith "matrix1 is not matched to matrix2"

Schauen wir uns den Code genauer an.
Vor der Multiplikation müssen Sie sicherstellen, dass die Matrizen konsistent sind

if Matrix.isMatched matrix1 matrix2 then

Die resultierende Matrix hat eine Dimension, in der die Anzahl der Zeilen der ersten Matrix und die Anzahl der Spalten der zweiten Matrix entspricht

let row1Count = matrix1.values.[*,0].Length
let col2Count = matrix2.values.[0,*].Length

//        
let values = Array2D.zeroCreate row1Count col2Count

Danach durchlaufen wir alle Zeilen und Spalten der ursprünglichen Matrizen

for r in 0..row1Count-1 do
    for c in 0..col2Count-1 do
        let row = Array.toList matrix1.values.[r,*]
        let col = Array.toList matrix2.values.[*,c]

Wir berechnen den Gesamtwert jeder Zelle

let cell = List.fold2 (fun acc val1 val2 -> acc + (val1 * val2)) 0 row col

Die Funktion List.fold2 empfängt zwei Listen am Eingang (Zeile und Spalte) und übergibt die folgenden Parameter an den Handler

acc - den Akkumulator, der das Ergebnis des vorherigen Berechnungswerts1
enthält - den Inhalt der Zelle aus dem ersten Array. In unserem Fall ist dies die Zeile aus der ersten Matrix
val2 - der Inhalt der Zelle aus dem zweiten Array, dh die Spalten der zweiten Matrix.

Da die Matrizen konsistent sind, sind wir sicher, dass wir nicht über die Arrays hinausgehen werden.

Der Handler fügt dem Akkumulator ein Produkt aus Zellen aus Zeilen und einer Spalte hinzu, und der resultierende Wert wird an die nächste Iteration übergeben. Somit ist das Endergebnis der Funktion List.fold2wird der Endwert der Produkte von zwei Matrizen sein. Es bleibt nur, sie mit der zuvor erstellten leeren Matrix zu füllen

values.[r,c] <- cell

Welches wird als Ergebnis zurückkehren

{ values = values }

Unten finden Sie ein Beispiel für die Verwendung dieser Funktion

let a = array2D [[1;0;2]
                 [3;1;0]]
let A = Matrix.ofArray2D a

let b = array2D [[-1;0]
                 [5;1]
                 [-2;0]]
let B = Matrix.ofArray2D b

let R = A*B

printfn "A*B =\n %A" R.values

A1*B1 =
 [[-5; 0]
 [2; 1]]

Wenn k ∈ N ist, ist die k-te Potenz einer quadratischen Matrix A das Produkt von k Matrizen A.

Ak=AA...A(k)


Betrachten Sie den Code auf F # für das Produkt einer Matrix zu einer Potenz. Die Schwanzrekursion wird hier verwendet, um den Stapel nicht mit großen Kräften zu überlaufen. Die Schwanzrekursion ist eine Rekursion, die der Compiler schließlich in eine Schleife konvertiert. Wenn möglich, wird empfohlen, immer die Schwanzrekursion anstelle der üblichen zu verwenden. Dazu benötigen Sie jedoch jeden Rekursionsrahmen, um den endgültig berechneten Wert zurückzugeben. Dieser Wert wird normalerweise als Akkumulator bezeichnet und an den nächsten Rekursionsrahmen übergeben. Das heißt, im Gegensatz zur regulären Rekursion, bei der der berechnete Wert im Stapel zurückgegeben wird, gibt die Schwanzrekursion den berechneten Wert im Stapel weiter. Jeder neue Rekursionsrahmen führt seine Berechnungen durch und addiert sie zu dem zuvor berechneten Wert, der in der Batterie gespeichert ist. Danach,Da der letzte Frame der Rekursion funktioniert hat, hat der Akkumulator bereits einen berechneten Wert, der einfach als Ergebnis zurückgegeben wird.

Somit kann der Compiler den Code optimieren und in eine reguläre Schleife konvertieren.


//    
// matrix -  
// value -  
static member (^^) (matrix, value) =

    //  ,    
    // m - 
    // p =  
    let inRecPow m p =

        //  
        // acc -  .   Matrix
        // p -     
        //         
        let rec recPow acc p =
            //   
            match p with
            | x when x > 0 ->
                //    
                //      ,      
                let nextAcc = acc*m
                //           
                recPow nextAcc (x-1)
            //    ,    
            | _ -> acc

        //   ,         
        let dim = Matrix.sizes matrix
        let colCount = snd dim
        let rowCount = fst dim

        let u = Matrix.E rowCount colCount
        //           
        recPow u p

    //  ,      
    let powMatrix = inRecPow matrix value
    //   
    { values = powMatrix.values }

Der Code enthält detaillierte Kommentare zur Funktionsweise. Benötigt eine kleine Erklärung, warum wird die Einheitsmatrix verwendet? Es wird für den ersten Rekursionsrahmen benötigt und dient als Basiswert des Akkumulators, in dem das Endergebnis akkumuliert wird.
Unten finden Sie ein Beispiel für die Verwendung unserer Funktion

A=(1021)


A2=AA=(1021)(1021)=(1001)


A3=AA2=(1021)(1001)=(1021)


Wir berechnen das folgende Produkt

f(A)=2A34A2+3E


Wobei E die Identitätsmatrix ist. Da wir der Matrix keine Zahl hinzufügen können, müssen wir 3E hinzufügen .

2(1021)4(1001)+3(1001)=(1043)



//     
static member (+) (matrix, (value: int)) =
    let dim = Matrix.sizes matrix
    let r = fst dim
    let c = snd dim

    //   
    let unit = Matrix.E r c
    //          
    value*unit + matrix

let a = array2D [[1;0]
                 [2;-1]]
let A = Matrix.ofArray2D a

let R = 2*(A^^3) - 4*(A^^2) + 3
printfn "2*A^3 - 4*A^2 + 3 =\n %A" R.values

2*A5^3 - 4*A5^2 + 3 =
 [[1; 0]
 [4; -3]]

Die Matrix A T, deren Spalten aus Zeilen der Matrix A mit den gleichen Nummern und der gleichen Folge von Elementen bestehen, wird als in die Matrix A transponiert bezeichnet

static member transpose matrix =
    let dim = Matrix.sizes matrix
    let rows = fst dim
    let cols = snd dim

    //      
    let tMatrix = Matrix.O cols rows
    //       
    matrix.values |> Array2D.iteri(fun x y v -> tMatrix.values.[y, x] <- v)

    //  
    tMatrix

Anwendungsbeispiel

let a = array2D [[1;2;3]
                 [4;5;6]
                 [7;8;9]
                 [10;11;12]]
let A = Matrix.ofArray2D a
let R6 = Matrix.T A
printfn "origin = \n %A" A.values
printfn "transpose = \n %A" R.values

origin = 
 [[1; 2; 3]
 [4; 5; 6]
 [7; 8; 9]
 [10; 11; 12]]
transpose = 
 [[1; 4; 7; 10]
 [2; 5; 8; 11]
 [3; 6; 9; 12]]

Zusammenfassung


In diesem Artikel haben wir Beispiele für die Implementierung und Verwendung von Matrizen aus der Theorie der linearen Algebra untersucht. Sowie die grundlegenden mathematischen Operationen auf ihnen, unter Verwendung eines funktionalen Ansatzes in F #. Ich hoffe, der Leser kann die Flexibilität schätzen, die funktionale Sprachen bieten.

Den vollständigen Quellcode des Matrixmoduls, dessen Fragmente im Rahmen des Artikels berücksichtigt wurden, finden Sie auf dem Github.

Github Matrix.fs

All Articles