lu_factor/lu_factorization.py at master · lucas-rls/lu_factor · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import numpy as np

def clone_matrix(matrix):
    new_matrix = []
    for line in matrix:
        new_line = []
        for elem in line:
            new_line.append(elem)
        new_matrix.append(new_line)
    return new_matrix


def swap_lines(matrix, l1, l2):
    if(l1 != l2):
        aux = matrix[l1]
        matrix[l1] = matrix[l2]
        matrix[l2] = aux
    return matrix

def print_matrix(matrix):
        for line in matrix:
            print("|{}|".format("\t".join(list(map(lambda item: "{:7.2f}".format(item), line)))))
        print('\n\n')

def build_zero_matrix(size):
    z = []
    for i in range(size):
        z.append([0]*size)
    return z

def set_diagonal(m, n = 1):
    for i in range(len(m)):
        m[i][i] = n
    return m

def buld_intentity_matrix(size):
    i = build_zero_matrix(size)
    set_diagonal(i, 1)
    return i

def find_pivo(matrix, col):
    maior = matrix[col][col]
    index = col
    for i in range(col, len(matrix[0])):
        if(abs(matrix[i][col]) > abs(maior)):
            maior = matrix[i][col]
            index = i
    return index, maior

def lu_factor(matrix):
    u = clone_matrix(matrix)
    l = build_zero_matrix(len(matrix))
    for k in range(len(matrix) - 1):
        # pivoteamento #
        print('L:')
        print_matrix(l)
        print('U:')
        print_matrix(u)
        index, maior = find_pivo(u, k)
        print("Swap line {} with line {}".format(k, index))
        u = swap_lines(matrix, k, index)
        l = swap_lines(l, k, index)
        print('L:')
        print_matrix(l)
        print('U:')
        print_matrix(u)
        ##
        print(f"Pivo - {u[k][k]}")
        for j in range(k + 1, len(matrix)):
            l[j][k] = u[j][k]/u[k][k]
            for i in range(k, len(matrix)):
                u[j][i] = u[j][i] - l[j][k]*u[k][i]
        print('L:')
        print_matrix(l)
        print('U:')
        print_matrix(u)
    set_diagonal(l)
    return l, u

if __name__ == "__main__":

    m = [
            [ 1,    0,    0,   0,    1],
            [-1,    1,    0,   0,    1],
            [-1,   -1,    1,   0,    1],
            [-1,   -1,   -1,   1,    1],
            [-1,   -1,   -1,  -1,    1]
        ]

    m = [
            [ 10,   5,   6,   7,   0,   0,   0,   0,   0,   0,   0,  0],
            [ 20,  20,  21,  14,   4,   0,   0,   0,   0,   0,   0,  0],
            [ 90,  65,  82,  64,  10,   3,   0,   0,   0,   0,   0,  0],
            [  0,  90, 101,  12,  49,  14,   7,   0,   0,   0,   0,  0],
            [  0,   0,  90,  29,  46,  48,  20,   7,   0,   0,   0,  0],
            [  0,   0,   0,  90, 101,  92,  83,  20,   4,   0,   0,  0],
            [  0,   0,   0,   0,  90,  65,  80,  84,  15,   5,   0,  0],
            [  0,   0,   0,   0,   0,  90,  92,  82,  53,  11,   2,  0],
            [  0,   0,   0,   0,   0,   0,  90, 101,  79,  47,   5,  9],
            [  0,   0,   0,   0,   0,   0,   0,  90,  47,  19,  28, 20],
            [  0,   0,   0,   0,   0,   0,   0,   0,  90,  20,  35, 86],
            [  0,   0,   0,   0,   0,   0,   0,   0,   0,  90,  92, 30]
        ]


    l, u = lu_factor(m)

    print("L:")
    print_matrix(l)
    print('\n\nU:')
    print_matrix(u)
    print('\n\nmult:')
    print_matrix(np.dot(l, u))