Pemrograman fungsional sebagai contoh bekerja dengan matriks dari teori aljabar linier

pengantar

Dasar bekerja dengan matriks (dalam artikel ini kami hanya akan mempertimbangkan matriks dua dimensi) adalah teori matematika yang kuat dari bidang aljabar linier. Satu definisi atau tindakan mengikuti dari yang lain, satu fungsi memanggil yang lain. Oleh karena itu, untuk implementasi fungsional dari operasi matematika pada matriks, bahasa fungsional sangat cocok. Pada artikel ini, kita akan melihat contoh spesifik dalam F # dan memberikan komentar terperinci tentang cara kerjanya. Karena F # adalah bagian dari keluarga .NET, fungsionalitas yang dihasilkan dapat digunakan tanpa masalah dalam bahasa imperatif lain, misalnya C #.

Definisi dan implementasi matriks dalam F #

Matriks adalah bagian dasar dan terpenting dari aljabar linier. Matriks sering digunakan dalam pemrograman, misalnya, dalam pemodelan 3D atau pengembangan game. Tentu saja, sepeda telah lama ditemukan dan kerangka kerja yang diperlukan untuk bekerja dengan matriks sudah siap, dan mereka dapat dan harus digunakan. Artikel ini tidak bertujuan menciptakan kerangka kerja baru, tetapi menunjukkan implementasi operasi matematika dasar untuk bekerja dengan matriks dalam gaya fungsional menggunakan bahasa pemrograman F #. Ketika kita memeriksa materi, kita akan beralih ke teori matematika dari matriks dan melihat bagaimana hal itu dapat diimplementasikan dalam kode.

Pertama, mari kita ingat apa itu matriks? Teori memberi tahu kita hal berikut

Tabel bujursangkar angka yang berisi m baris dan kolom n disebut matriks ukuran mxn

Matriks biasanya dilambangkan dengan huruf besar alfabet Latin dan ditulis sebagai

$$

$$A=\begin{pmatrix}a11&a12&...&a1n\\a21&a22&...&a2n\\...&...&...&...\\am1&am2&...&amn\end{pmatrix}$$

Atau sebentar lagi

$$

$$A=(aij)$$

Untuk bekerja dengan matriks dalam F # kami akan membuat catatan berdasarkan tabel dua dimensi, yang akan kami kembangkan lebih lanjut dengan metode yang berguna untuk melakukan operasi matematika yang diperlukan di dalamnya.

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

Tambahkan metode pembantu untuk menginisialisasi rekaman dengan array dua dimensi

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

Argumen input ke fungsi akan menjadi array dua dimensi, dan pada outputnya, catatan dari tipe Matrix . Di bawah ini adalah contoh inisialisasi rekaman.

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

Dua matriks A = (aij) dan B = (bij) disebut sama jika mereka bertepatan elemen, yaitu aij = bij untuk semua i = 1,2 ..., m dan j = 1,2 ... n

Untuk menerapkan aturan ini, kami akan menggunakan operator yang diganti == dan menambahkan beberapa fungsi yang berguna, yang juga akan kami butuhkan di masa mendatang.

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)

Mari kita lihat lebih dekat kode di atas. Seperti yang Anda lihat, ada tiga fungsi. Fungsi ukuran pertama mengembalikan dimensi matriks sebagai tupel. Karena kami hanya bekerja dengan matriks persegi panjang, untuk mendapatkan jumlah baris, kami mengambil sepotong penuh kolom pertama dan mengembalikan panjangnya.

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

Menentukan jumlah kolom berfungsi dengan cara yang sama - kita mendapatkan potongan penuh dari baris pertama dan mengembalikan panjangnya.

Fungsi isEquallySized berikut membandingkan dimensi dua matriks dan mengembalikan true jika keduanya sama. Untuk melakukan ini, ia menggunakan fungsi ukuran yang sudah jadi dan hanya membandingkan hasilnya.

Operator == untuk elemen membandingkan dua matriks tampaknya lebih rumit, tetapi sekarang Anda akan melihat bahwa itu juga sederhana.

Sebelum membandingkan dua matriks, kami membandingkan dimensi mereka. Jika mereka tidak sama, maka tidak ada gunanya memeriksa, karena sudah jelas bahwa matriks tidak akan sama.

if not (Matrix.isEquallySized matrix1 matrix2) then false

Selanjutnya, berdasarkan pada matriks asli matriks1 dan matriks2 , kami membentuk matriks baru yang diisi dengan benar atau salah , tergantung pada apakah sel-sel yang sesuai dari kedua matriks tersebut bertepatan.

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

Fungsi Array2D.mapi iterates atas semua elemen matrix1 dan melewati tiga parameter
x ke indeks baris -handler
y - kolom indeks
v -
konten sel Kami membandingkan konten sel v dengan matriks2 sel yang sesuai dan jika mereka sama, maka tulis benar , kalau tidak salah .

Jika setidaknya ada satu sel dengan elemen salah , maka ini berarti bahwa matriks tidak sama satu sama lain.

Karena Array2D tidak mengandung metode untuk memfilter atau mencari, kami akan mengimplementasikannya sendiri. Untuk melakukan ini, kami menguraikan matriks menjadi daftar linier

|> Seq.cast<bool>

Dan temukan setidaknya satu ketidakcocokan

|> Seq.contains false

Fungsi Seq.contains akan mengembalikan true jika setidaknya satu nilai salah ditemukan dalam daftar yang diperluas . Oleh karena itu, kita perlu membalikkan hasilnya sehingga operator == bekerja seperti yang kita inginkan

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)

Matriks O disebut matriks nol atau nol jika semua elemennya sama dengan nol.

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

Contoh menggunakan fungsi ini

let AO = Matrix.O 5 5

Saya percaya bahwa tidak ada yang rumit yang memerlukan penjelasan, jadi kami melanjutkan.

Matriks yang jumlah barisnya sama dengan jumlah kolom dan sama dengan n disebut matriks kuadrat n

Dengan demikian, matriks kuadrat memiliki bentuk.

$$

$$A=\begin{bmatrix}a11&a12&...&a1n\\a21&a22&...&a2n\\...&...&...&...\\an1&an2&...&ann\end{bmatrix}$$

Sebagai bagian dari aturan ini, kita akan membuat fungsi yang mengubah matriks persegi panjang menjadi matriks persegi dengan memotong semua elemen yang tidak jatuh ke dalam persegi.

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 }

Komentar dalam kode sumber menjelaskan bagaimana fungsi ini bekerja, jadi mari kita lanjutkan.

Matriks kuadrat disebut segitiga jika semua elemennya di bawah diagonal utama sama dengan nol, yaitu matriks segitiga memiliki bentuk

$$

$$T=\begin{pmatrix}a11&a12&...&a1n\\0&a22&...&a2n\\...&...&...&...\\0&0&...&ann\end{pmatrix}$$

Di bawah ini adalah kode fungsi yang mengubah matriks asli menjadi segitiga. Tetapi dalam fungsi kami, kami akan bekerja dengan matriks persegi panjang, yaitu, mungkin tidak persegi. Pembaca dapat dengan mudah memodifikasi kode fungsi sehingga mengembalikan matriks segitiga triangular menggunakan fungsi yang telah kita periksa sebelumnya.

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

Fungsi Array2D.mapi mengubah array dua dimensi asli menjadi yang baru menggunakan handler yang mengambil tiga parameter

x - nomor baris
y - jumlah kolom
v - isi sel

if y < x then 0 else v

Di sini kita memeriksa apakah elemen di bawah diagonal utama dan jika demikian, maka isi sel 0. Jika tidak, nilai awal dari matriks input.

Berikut ini adalah contoh penggunaan fungsi ini.

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

Kami mendapatkan hasil sebagai berikut

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]]

Matriks kuadrat disebut diagonal jika semua elemennya terletak di luar diagonal utama sama dengan nol

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

Fungsi ini sangat mirip dengan yang sebelumnya, hanya kondisi verifikasi yang berbeda. Di bawah ini adalah contoh penggunaan

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]]

Matriks diagonal adalah satuan dan dilambangkan dengan E jika semua elemennya yang terletak di diagonal utama sama dengan satu

$$

$$E=\begin{pmatrix}1&0&...&0\\0&1&...&0\\...&...&...&...\\0&0&...&1\end{pmatrix}$$

Implementasi dari matriks seperti pada F # terlihat seperti ini

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

Operasi Matriks dengan F #

Sejumlah tindakan dapat dilakukan pada matriks, serta pada angka, beberapa di antaranya mirip dengan operasi pada angka, dan beberapa spesifik.

Jumlah dua matriks Amn = (aij) dan Bmn = (bij) dengan ukuran yang sama adalah matriks dengan ukuran yang sama A + B = Cmn = (cij) , unsur-unsurnya sama dengan jumlah unsur-unsur dari matriks A dan B yang terletak di tempat yang sesuai

$$

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

Contoh, untuk matriks yang diberikan A dan B, kami menemukan jumlah A + B

$$

$$A=\begin{pmatrix}2&3\\1&-5\\0&6\end{pmatrix}, B=\begin{pmatrix}-3&3\\1&7\\2&0\end{pmatrix}, A+B=\begin{pmatrix}-1&6\\2&2\\2&6\end{pmatrix}$$

Pertimbangkan kode untuk menambahkan dua matriks

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"

Sebelum menambahkan matriks, Anda perlu memastikan bahwa dimensinya bertepatan, jika tidak fungsi tersebut akan melempar pengecualian. Di bawah ini adalah contoh penggunaan fungsi ini

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]]

Produk dari matriks A = (aij) dengan angka k adalah matriks kA = (kaij) dengan ukuran yang sama dengan matriks A yang diperoleh dengan mengalikan semua elemen dari matriks A dengan jumlah k

Contoh, untuk matriks A yang diberikan kita menemukan matriks 3A

$$

$$A=\begin{pmatrix}2&3&0\\1&5&4\end{pmatrix}, 3A=\begin{pmatrix}6&9&0\\3&15&12\end{pmatrix}$$

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

Matriks A = (- 1) * A akan disebut berlawanan matriks A . Dari definisi ini, kami melanjutkan dengan lancar ke yang berikutnya

Perbedaan dari matriks A dan B dengan ukuran yang sama adalah jumlah dari matriks A dan matriks yang berlawanan dengan B

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

Dua matriks disebut konsisten jika jumlah kolom yang pertama sama dengan jumlah baris yang kedua

$$

$$A=\begin{pmatrix}2&1\\0&3\end{pmatrix}, B=\begin{pmatrix}0&5&2&1\\1&4&3&7\end{pmatrix}$$

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

    row1Count = col2Count

Diperlukan pemeriksaan konsistensi matriks untuk memperbanyaknya.

Matriks koheren produk AB Amn = (aij) dan Bnp = (bjk) adalah matriks Cmn = (cik) , elemen cik dihitung sebagai jumlah dari elemen-elemen pada baris ke- i dari matriks A dan elemen-elemen yang sesuai dari kolom ke- k dari matriks B

Hitung produk dari matriks

$$

$$A=\begin{pmatrix}1&0&2\\3&1&0\end{pmatrix}, B=\begin{pmatrix}-1&0\\5&1\\-2&0\end{pmatrix}$$

Keputusan untuk menentukan produk dari matriks

$$

$$AB=\begin{pmatrix}1(-1)+0*5+2(-2)&1*0+0*1+2*0\\3(-1)+1*5+0(-2)&3*0+1*1+0*0\end{pmatrix}= \begin{pmatrix}-5&0\\2&1\end{pmatrix}$$

Pertimbangkan kode untuk mengalikan dua matriks

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"

Mari kita lihat kodenya lebih detail.
Sebelum penggandaan, Anda perlu memastikan bahwa matriks konsisten

if Matrix.isMatched matrix1 matrix2 then

Matriks yang dihasilkan akan memiliki dimensi di mana jumlah baris sama dengan matriks pertama dan jumlah kolom sama dengan matriks kedua

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

//        
let values = Array2D.zeroCreate row1Count col2Count

Setelah itu, kita mengulangi semua baris dan semua kolom dari matriks asli

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]

Kami menghitung nilai total setiap sel

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

Fungsi List.fold2 menerima dua daftar di input (baris dan kolom) dan meneruskan parameter berikut ke penangan

acc - akumulator yang berisi hasil dari kalkulasi
val1 sebelumnya - isi sel dari array pertama. Dalam kasus kami, ini adalah baris dari
val2 matriks pertama - isi sel dari array kedua, yaitu kolom dari matriks kedua.Karena

matriks konsisten, kami yakin bahwa kami tidak akan melampaui array.

Pawang menambahkan ke akumulator produk sel dari baris dan kolom, dan nilai yang dihasilkan akan diteruskan ke iterasi berikutnya. Jadi, hasil akhir dari fungsi List.fold2akan menjadi nilai akhir dari produk dua matriks. Tetap hanya untuk mengisinya dengan matriks kosong yang dibuat sebelumnya

values.[r,c] <- cell

Yang akan kembali sebagai hasilnya

{ values = values }

Di bawah ini adalah contoh penggunaan fungsi ini

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]]

Jika k ∈ N, maka kekuatan k dari matriks kuadrat A adalah produk dari matriks k A

$$

$$A^k=A*A*...A (k- )$$

Pertimbangkan kode pada F # untuk produk dari sebuah matriks hingga daya. Rekursi ekor akan digunakan di sini agar tidak meluap tumpukan dengan kekuatan besar. Ekor rekursi adalah rekursi yang akhirnya diubah oleh kompiler menjadi loop. Jika memungkinkan, Anda disarankan untuk selalu menggunakan rekursi ekor bukan yang biasa, tetapi untuk ini Anda membutuhkan setiap kerangka rekursi untuk mengembalikan nilai akhir yang dihitung. Nilai ini biasanya disebut akumulator dan diteruskan ke kerangka rekursi berikutnya. Yaitu, tidak seperti rekursi biasa, yang mengembalikan nilai yang dihitung ke atas tumpukan, rekursi ekor melewati nilai yang dihitung di atas tumpukan. Setiap frame rekursi baru melakukan perhitungannya sendiri dan menambahkannya ke nilai yang dihitung sebelumnya, yang disimpan dalam baterai. Setelah itu,Ketika kerangka terakhir dari rekursi bekerja, akumulator sudah memiliki nilai yang dihitung, yang hanya mengembalikan sebagai hasilnya.

Dengan demikian, kompiler dapat mengoptimalkan kode dan mengubahnya menjadi loop reguler.

//    
// 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 }

Kode berisi komentar terperinci tentang cara kerjanya. Membutuhkan sedikit penjelasan, mengapa matriks unit digunakan? Dibutuhkan untuk kerangka rekursi pertama dan berfungsi sebagai nilai dasar akumulator, di mana hasil akhir akan diakumulasikan.
Di bawah ini adalah contoh penggunaan fungsi kami

$$

$$A=\begin{pmatrix}1&0\\2&-1\end{pmatrix}$$

$$

$$A^2=AA=\begin{pmatrix}1&0\\2&-1\end{pmatrix}\begin{pmatrix}1&0\\2&-1\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}$$

$$

$$A^3=AA^2=\begin{pmatrix}1&0\\2&-1\end{pmatrix}\begin{pmatrix}1&0\\0&1\end{pmatrix}=\begin{pmatrix}1&0\\2&-1\end{pmatrix}$$

Kami menghitung produk berikut

$$

$$f(A)=2A^3-4A^2+3E$$

Di mana E adalah matriks identitas. Karena kita tidak dapat menambahkan angka ke matriks, kita harus menambahkan 3E .

$$

$$2\begin{pmatrix}1&0\\2&-1\end{pmatrix}- 4\begin{pmatrix}1&0\\0&1\end{pmatrix}+ 3\begin{pmatrix}1&0\\0&1\end{pmatrix}= \begin{pmatrix}1&0\\4&-3\end{pmatrix}$$

//     
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]]

Matriks A ^T yang kolomnya terdiri dari baris-baris matriks A dengan angka yang sama dan urutan elemen yang sama disebut ditransposisikan ke matriks A

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

Contoh penggunaan

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]]

Ringkasan

Pada artikel ini, kami memeriksa contoh implementasi dan penggunaan matriks dari teori aljabar linier. Serta operasi matematika dasar pada mereka, menggunakan pendekatan fungsional di F #. Saya harap pembaca dapat menghargai fleksibilitas yang diberikan oleh bahasa fungsional.

Kode sumber lengkap dari modul matriks, yang bagian-bagiannya dipertimbangkan dalam kerangka artikel, dapat Anda temukan di github.

Github Matrix.fs