# 4 - ALGEBRA-LINEAR

## 1419 days ago by jmarcellopereira

ALGEBRA LINEAR

Some common Sage rings and fields
ZZ integers, ring

QQ rationals, field

AA, QQbar algebraic number fields, exact

RDF real double field, inexact

CDF complex double field, inexact

RR 53-bit reals, inexact, not same as RDF

RealField(400) 400-bit reals, inexact

CC, ComplexField(400) complexes, too

RIF real interval field

GF(2) mod 2, field, specialized implementations

GF(p) == FiniteField(p) p prime, field

Integers(6) integers mod 6, ring only

CyclotomicField(7) rationals with 7th root of unity √QuadraticField(-5, ’x’) rationals with x= −5

SR ring of symbolic expressions

VETORES

v = vector([1, 0]) u = vector([0, 1]) t = vector([-1,-2]) v;u;t
 (1, 0) (0, 1) (-1, -2) (1, 0) (0, 1) (-1, -2)

Gráfico de vetores 2D

plot(v,color="red", figsize = (4,4),gridlines="minor") + plot(u) + plot(t,color="green")

# campo de vetores resultante var('x,y') plot_vector_field((x,y),(x,0,1),(y,0,1), figsize=(6,5), gridlines="minor")

OPERAÇÕES COM VETORES

Soma e Subtração de Vetores

v = vector([1, 0]); u = vector([0, 1]); t = vector([-1,-2]); Som = v+u+t; Sub = v-u-t v; u; t; Som; Sub
 (1, 0) (0, 1) (-1, -2) (0, -1) (2, 1) (1, 0) (0, 1) (-1, -2) (0, -1) (2, 1)

Viualização Gráfica 2D

plot(v,color="red", figsize = (4,4),gridlines="minor")+plot(u)+plot(t,color="green")+plot(Som,color="black")
plot(v,color="red", figsize = (4,4),gridlines="minor")+plot(u)+plot(t,color="green")+plot(Sub,color="black")

Vetores 3D

w = vector([1, 0, 0]); r = vector([0,1, 0]); s = vector([0,0, 1]); Som = w+r+s; Sub = w-r-s; w;r;s; Som; Sub
 (1, 0, 0) (0, 1, 0) (0, 0, 1) (1, 1, 1) (1, -1, -1) (1, 0, 0) (0, 1, 0) (0, 0, 1) (1, 1, 1) (1, -1, -1)

Visualizção Gráfica 3D

plot(w,color='red', figsize = (5,6), mesh=true, thickness=3) + plot(r, thickness=3)+ plot(s,color='green',thickness=3) + plot(Som,color='green',thickness=3)
plot(w,color='red', figsize = (5,6), mesh=true, thickness=3) + plot(r, thickness=3)+ plot(s,color='green',thickness=3) + plot(Sub,color='green',thickness=3)
# multiplicação por escalar v = vector([1, 0]); 2*v
 (2, 0) (2, 0)
# Multiplicação elemento por elemento entre vetores v = vector([1, 0]) u = vector([0, 1]) # Divisão por escalar v = vector([1, 0]) v/2 v.pairwise_product(u)
 (0, 0) (0, 0)
# Divisão por escalar v = vector([1, 0]) v/2
 (1/2, 0) (1/2, 0)
# Divisão elemento por elemento entre vetores v = vector([1, 0]) u = vector([0, 1])
# Potencia elemento por elemento v = vector([1, 2]) u = vector([3, 4]) v.apply_map(lambda x: x^2)
 (1, 4) (1, 4)
# Potencia elemento por elemento entre vetores
# Transposição v = vector([1, 0]) v.column()
 [1] [0] [1] [0]
# Vetor aletório Va = random_vector(QQ, 3) ; Vab = random_vector(ZZ, 3) Va ; Vab
 (-25, -1/2, 2/5) (1, 1, 1) (-25, -1/2, 2/5) (1, 1, 1)
# Mediana dos elementos de um vetor
# Média dos valores dos elementos de um vetor
# Desvio padrão dos elementos de um vetor
# Valor máximo do vetor v v = vector([1, 0]) max(v)
 1 1
# Valor máximo de um vetor e indice
# valores extremos de um vetor: minimo e máximo
# Testando se o indice 3 corresponde ao elemento de maior valor do vetor v = [1 2 3]. # O valor true no teste de igualdade corresponde a verdadeiro
# Valor mínimo de um vetor min(v)
 0 0
# Valor minimo de um vetor e indice
# Testando se o indice 1 corresponde ao elemento de menor valor do vetor v = [1 2 3]. # O valor true no teste de igualdade corresponde a verdadeiro
# Produto interno: somente vetores coluna. aqui o uso do transpose ou v' nao funciona v = vector([1, 0]) u = vector([0, 1]) v.inner_product(u) ; v.dot_product(u)
 0 0 0 0
# Produto externo ou vetorial vv = vector([1, 0, 0]) uu = vector([0, 1, 0]) vv.cross_product(uu)
 (0, 0, 1) (0, 0, 1)

Multiplicação de Vetores

Multiplicação v(linhas_v,colunas_v) * u(linhas_u,colunas_u) , só é possível se colunas_v = linhas_u ou seja se o número de colunas de v for igual ao númer de linhas de colunas de u resultando em um vetor de m_v linhas e n_u colunas

v = vector([1, 1]) u = vector([-1, -1]) u*v
 -2 -2
 (1, 1) (1, 1)

OPERAÇÕES COM MATRIZES

A = matrix([[0, -1, -1], [1, 1, 1], [2, 4, 1]]) B = matrix([[1.1, 0.0, 1.8], [-1.7, 9.6, 1.0], [7.9, 4.6, -5.5]]) A ; B
 [ 0 -1 -1] [ 1 1 1] [ 2 4 1] [ 1.10000000000000 0.000000000000000 1.80000000000000] [-1.70000000000000 9.60000000000000 1.00000000000000] [ 7.90000000000000 4.60000000000000 -5.50000000000000] [ 0 -1 -1] [ 1 1 1] [ 2 4 1] [ 1.10000000000000 0.000000000000000 1.80000000000000] [-1.70000000000000 9.60000000000000 1.00000000000000] [ 7.90000000000000 4.60000000000000 -5.50000000000000]
type(A) ; type(B)
    

Soma e Subtração de Matrizes

A+B
 [ 1.10000000000000 -1.00000000000000 0.800000000000000] [-0.700000000000000 10.6000000000000 2.00000000000000] [ 9.90000000000000 8.60000000000000 -4.50000000000000] [ 1.10000000000000 -1.00000000000000 0.800000000000000] [-0.700000000000000 10.6000000000000 2.00000000000000] [ 9.90000000000000 8.60000000000000 -4.50000000000000]
A-B
 [ -1.10000000000000 -1.00000000000000 -2.80000000000000] [ 2.70000000000000 -8.60000000000000 0.000000000000000] [ -5.90000000000000 -0.600000000000000 6.50000000000000] [ -1.10000000000000 -1.00000000000000 -2.80000000000000] [ 2.70000000000000 -8.60000000000000 0.000000000000000] [ -5.90000000000000 -0.600000000000000 6.50000000000000]

Matriz aleatória

C = random_matrix(RR,3,3); D = random_matrix(ZZ,3,2) C ; D
 [-0.375982345804659 0.0455742151790328 -0.528963235672596] [-0.592825677959837 -0.697713400309605 -0.160281847680464] [ 0.829988031980482 -0.356950914960860 -0.927039175887283] [ 1 1] [ 0 -1] [-1 0] [-0.375982345804659 0.0455742151790328 -0.528963235672596] [-0.592825677959837 -0.697713400309605 -0.160281847680464] [ 0.829988031980482 -0.356950914960860 -0.927039175887283] [ 1 1] [ 0 -1] [-1 0]
type(C) ; type(D)
    

Determinante

show(A) A.det() ; det(A)
 \newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrr} 0 & -1 & -1 \\ 1 & 1 & 1 \\ 2 & 4 & 1 \end{array}\right) -3 -3 -3 -3

Cofatores

 \newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrr} 0 & -1 & -1 \\ 1 & 1 & 1 \\ 2 & 4 & 1 \end{array}\right) [-3 -3 0] [ 1 2 -1] [ 2 -2 1] [-3 -3 0] [ 1 2 -1] [ 2 -2 1]

Multiplicação de Matrizes

Multiplicação Ma(linhas_Ma,colunas_Ma) * Mb(linhas_Mb,colunas_Mb) , só é possível se colunas_Ma = linhas_Mb ou seja se o número de colunas de Ma for igual ao número de linhas de Mb resultando em uma matriz de Ma_linhas e Mb_colunas

A*B
 [-6.20000000000000 -14.2000000000000 4.50000000000000] [ 7.30000000000000 14.2000000000000 -2.70000000000000] [ 3.30000000000000 43.0000000000000 2.10000000000000] [-6.20000000000000 -14.2000000000000 4.50000000000000] [ 7.30000000000000 14.2000000000000 -2.70000000000000] [ 3.30000000000000 43.0000000000000 2.10000000000000]

Matrizes especiais

# matriz de zeros Mzeros_A = matrix(3, 3, 0) ; Mzeros_B = zero_matrix(3,3) Mzeros_A; Mzeros_B
 [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0]
# matriz de uns Muns = ones_matrix(3,3) Muns
 [1 1 1] [1 1 1] [1 1 1] [1 1 1] [1 1 1] [1 1 1]
# matriz identidade Miden_A = matrix(3, 3, 1) ; Miden_B = identity_matrix(3,3) Miden_A; Miden_B
 [1 0 0] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [0 0 1] [1 0 0] [0 1 0] [0 0 1]
#matriz diagonal com termos definidos Mdiag_A = diagonal_matrix([2, 1.3, 5]); Mdiag_B = matrix(QQ, 3, 3, 8) Mdiag ; Mdiag_B
 Traceback (click to the left of this block for traceback) ... NameError: name 'Mdiag' is not defined Traceback (most recent call last): File "", line 1, in File "_sage_input_52.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("I21hdHJpeiBkaWFnb25hbCBjb20gdGVybW9zIGRlZmluaWRvcwoKTWRpYWdfQSA9IGRpYWdvbmFsX21hdHJpeChbMiwgMS4zLCA1XSk7IE1kaWFnX0IgPSBtYXRyaXgoUVEsIDMsIDMsIDgpCgoKTWRpYWcgOyBNZGlhZ19C"),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in File "/tmp/tmpl7Fh7x/___code___.py", line 7, in exec compile(u'Mdiag ; Mdiag_B File "", line 1, in NameError: name 'Mdiag' is not defined

Gráfico de uma matriz

Ma = random_matrix(RDF,5) Ma
 [ 0.6538050147862324 -0.32541912158611463 -0.1660593296650852 -0.5534591928975958 0.46374193422893706] [ -0.5486518265230627 -0.32236783179125683 -0.07616041392141293 -0.6063505222049581 0.45374756049487064] [ -0.9072735433073706 0.11974129318503413 -0.8206291706670703 0.36194453352152767 0.4782907533200187] [ -0.717323659305259 -0.7003335121018457 -0.4015294035700083 -0.8553520894235311 -0.9668054000538027] [ 0.7638155414235157 0.7760292660431884 -0.8316641722022806 -0.8438537806219206 -0.4119026429871264] [ 0.6538050147862324 -0.32541912158611463 -0.1660593296650852 -0.5534591928975958 0.46374193422893706] [ -0.5486518265230627 -0.32236783179125683 -0.07616041392141293 -0.6063505222049581 0.45374756049487064] [ -0.9072735433073706 0.11974129318503413 -0.8206291706670703 0.36194453352152767 0.4782907533200187] [ -0.717323659305259 -0.7003335121018457 -0.4015294035700083 -0.8553520894235311 -0.9668054000538027] [ 0.7638155414235157 0.7760292660431884 -0.8316641722022806 -0.8438537806219206 -0.4119026429871264]
Ma.plot(cmap='Blues',vmin=min(min(Ma)), vmax=ceil(max(max(Ma))), colorbar=true, figsize=(6,5))
Mb = matrix([[1,2],[3,4]]) Mb
 [1 2] [3 4] [1 2] [3 4]
Mb.apply_map(lambda x: x^2)
 [ 1 4] [ 9 16] [ 1 4] [ 9 16]

MA = matrix(RDF,[[8.0,9.1,1.9],[0.5,5.5,3.6],[8.9,1.0,6.1]]) MB = vector(RDF,[8.1,-3.0,7.5]) MA; MB
 [8.0 9.1 1.9] [0.5 5.5 3.6] [8.9 1.0 6.1] (8.1, -3.0, 7.5) [8.0 9.1 1.9] [0.5 5.5 3.6] [8.9 1.0 6.1] (8.1, -3.0, 7.5)
MA.augment(MB,subdivide=True)
 [ 8.0 9.1 1.9| 8.1] [ 0.5 5.5 3.6|-3.0] [ 8.9 1.0 6.1| 7.5] [ 8.0 9.1 1.9| 8.1] [ 0.5 5.5 3.6|-3.0] [ 8.9 1.0 6.1| 7.5]

simplificando o sistema

MA.augment(MB).rref()
 [ 1.0 0.0 0.0 1.3874910660890618] [ 0.0 1.0 0.0 -0.16950363920127176] [ 0.0 0.0 1.0 -0.7670765326215377] [ 1.0 0.0 0.0 1.3874910660890618] [ 0.0 1.0 0.0 -0.16950363920127176] [ 0.0 0.0 1.0 -0.7670765326215377]
MA.pivots()
 (0, 1, 2) (0, 1, 2)

Sistemas Lineares

Resolvenddo o sistema

MA = matrix(RDF,[[8.0,9.1,1.9],[0.5,5.5,3.6],[8.9,1.0,6.1]]) MB = vector(RDF,[8.1,-3.0,7.5]) MA ; MB
 [8.0 9.1 1.9] [0.5 5.5 3.6] [8.9 1.0 6.1] (8.1, -3.0, 7.5) [8.0 9.1 1.9] [0.5 5.5 3.6] [8.9 1.0 6.1] (8.1, -3.0, 7.5)
X = MA\MB X
 (1.3874910660890618, -0.16950363920127187, -0.7670765326215376) (1.3874910660890618, -0.16950363920127187, -0.7670765326215376)
X = MA.solve_right(MB) X
 (1.3874910660890618, -0.16950363920127187, -0.7670765326215376) (1.3874910660890618, -0.16950363920127187, -0.7670765326215376)

Decomposição LU

Ax = b

A = LU

P*A = L*U

• P is a square permutation matrix, of siz, so is all zeroes, but with exactly a single one in each row and each column.
• L is lower-triangular, square of siz, with every diagonal entry equal to one.
• U is upper-triangular with size, i.e. entries below the “diagonal” are all zero.
P,L,U = MA.LU() P; L; U
 [0.0 0.0 1.0] [1.0 0.0 0.0] [0.0 1.0 0.0] [ 1.0 0.0 0.0] [ 0.898876404494382 1.0 0.0] [0.056179775280898875 0.6637895602137279 1.0] [ 8.9 1.0 6.1] [ 0.0 8.201123595505617 -3.5831460674157296] [ 0.0 0.0 5.635758323057953] [0.0 0.0 1.0] [1.0 0.0 0.0] [0.0 1.0 0.0] [ 1.0 0.0 0.0] [ 0.898876404494382 1.0 0.0] [0.056179775280898875 0.6637895602137279 1.0] [ 8.9 1.0 6.1] [ 0.0 8.201123595505617 -3.5831460674157296] [ 0.0 0.0 5.635758323057953]
# Testando L*U
 [8.9 1.0 6.1] [8.0 9.1 1.9] [0.5 5.5 3.6] [8.9 1.0 6.1] [8.0 9.1 1.9] [0.5 5.5 3.6]

Método de Cholesky

Este método se aplica quando a matriz dos coeficientes A é simétrica (A = A^t) e definida positiva. Nesta situação, a matriz A pode ser fatorada em A=LU=LL^t.

MC = matrix([[4,2,14],[2,17,-5],[14,-5,83]]) MC
 [ 4 2 14] [ 2 17 -5] [14 -5 83] [ 4 2 14] [ 2 17 -5] [14 -5 83]
MC.transpose() == MC
 True True
MC.cholesky()
 [ 2 0 0] [ 1 4 0] [ 7 -3 5] [ 2 0 0] [ 1 4 0] [ 7 -3 5]
%time A = random_matrix(RDF,5000,5000) B = random_vector(RDF,5000)
 CPU time: 8.06 s, Wall time: 17.36 s CPU time: 8.06 s, Wall time: 17.36 s
%time xx =A\B
 Traceback (click to the left of this block for traceback) ... MemoryError Traceback (most recent call last): File "", line 1, in File "_sage_input_73.py", line 12, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("eHggPUFcQg=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")); print "CPU time: %.2f s, Wall time: %.2f s"%(cputime(__SAGE_t__), walltime(__SAGE_w__)) File "", line 1, in File "/tmp/tmpMU53Cz/___code___.py", line 2, in exec compile(u'xx =A * BackslashOperator() * B File "", line 1, in File "/usr/local/sage-6.9/local/lib/python2.7/site-packages/sage/misc/misc.py", line 1621, in __mul__ return self.left._backslash_(right) File "sage/matrix/matrix2.pyx", line 74, in sage.matrix.matrix2.Matrix._backslash_ (/usr/local/sage-6.9/src/build/cythonized/sage/matrix/matrix2.c:4408) File "sage/matrix/matrix_double_dense.pyx", line 1758, in sage.matrix.matrix_double_dense.Matrix_double_dense.solve_right (/usr/local/sage-6.9/src/build/cythonized/sage/matrix/matrix_double_dense.c:12657) File "/usr/local/sage-6.9/local/lib/python2.7/site-packages/scipy/linalg/basic.py", line 94, in solve overwrite_b=overwrite_b) MemoryError
%time x = A.solve_right(B)
 Traceback (click to the left of this block for traceback) ... MemoryError Traceback (most recent call last): File "", line 1, in File "_sage_input_74.py", line 12, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("eCA9IEEuc29sdmVfcmlnaHQoQik="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")); print "CPU time: %.2f s, Wall time: %.2f s"%(cputime(__SAGE_t__), walltime(__SAGE_w__)) File "", line 1, in File "/tmp/tmpz_WRC1/___code___.py", line 2, in exec compile(u'x = A.solve_right(B) File "", line 1, in File "sage/matrix/matrix_double_dense.pyx", line 1758, in sage.matrix.matrix_double_dense.Matrix_double_dense.solve_right (/usr/local/sage-6.9/src/build/cythonized/sage/matrix/matrix_double_dense.c:12657) File "/usr/local/sage-6.9/local/lib/python2.7/site-packages/scipy/linalg/basic.py", line 94, in solve overwrite_b=overwrite_b) MemoryError
xx[99]; x[99]
 Traceback (click to the left of this block for traceback) ... NameError: name 'xx' is not defined Traceback (most recent call last): File "", line 1, in File "_sage_input_75.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("eHhbOTldOyB4Wzk5XQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in File "/tmp/tmphK14EB/___code___.py", line 3, in exec compile(u'xx[_sage_const_99 ]; x[_sage_const_99 ] File "", line 1, in NameError: name 'xx' is not defined

Utilizando o NumPy

%time from numpy import linalg x = linalg.solve(A,B)
 Connection to localhost closed. Connection to localhost closed.
reset()
import numpy as np AA = np.random.rand(5000,5000) BB = np.random.rand(5000,1) Aa = np.matrix(AA) Bb = np.matrix(BB)

%time xy = np.linalg.solve(Aa,Bb)
 CPU time: 0.00 s, Wall time: 0.01 s CPU time: 0.00 s, Wall time: 0.01 s
%time xy = np.linalg.solve(AA,BB)
 CPU time: 0.00 s, Wall time: 0.00 s CPU time: 0.00 s, Wall time: 0.00 s
reset()
A = random_matrix(GF(2), 5000, 5000) b = random_vector(GF(2), 5000)
A[299,300] ; b[299]
 1 0 1 0
%time x = A\b
 CPU time: 2.65 s, Wall time: 5.34 s CPU time: 2.65 s, Wall time: 5.34 s
x[299]
 1 1
%time x = A.solve_left(b)
 CPU time: 0.23 s, Wall time: 0.46 s CPU time: 0.23 s, Wall time: 0.46 s
x[466]
 1 1

Comparação com outros Softwares

 Julia Octave MatLab Julia Python Sage RDF 2.326s* 3.38s A/B : 8.480s* Linalg: 8.523s*

* tempo médio em segundos numa máquina I5 Haswell, 8GB Ram, Linux NETRunner 17, SageMath 7.0

Aritmética em RR(reais) é mais lento do que aritmética com tipos C nativos.

AUTOVETORES E AUTOVALORES

A = matrix([[0, 4], [-1, 0]]) A
 [ 0 4] [-1 0] [ 0 4] [-1 0]
A.eigenvalues ()
 [-2*I, 2*I] [-2*I, 2*I]
A.eigenvectors_left() ; A.eigenvectors_right()
 [(-2*I, [(1, 2*I)], 1), (2*I, [(1, -2*I)], 1)] [(-2*I, [(1, -0.50000000000000000?*I)], 1), (2*I, [(1, 0.50000000000000000?*I)], 1)] [(-2*I, [(1, 2*I)], 1), (2*I, [(1, -2*I)], 1)] [(-2*I, [(1, -0.50000000000000000?*I)], 1), (2*I, [(1, 0.50000000000000000?*I)], 1)]
A.eigenmatrix_left() ; A.eigenmatrix_right()
 ( [-2*I 0] [ 1 2*I] [ 0 2*I], [ 1 -2*I] ) ( [-2*I 0] [ 1 1] [ 0 2*I], [-0.50000000000000000?*I 0.50000000000000000?*I] ) ( [-2*I 0] [ 1 2*I] [ 0 2*I], [ 1 -2*I] ) ( [-2*I 0] [ 1 1] [ 0 2*I], [-0.50000000000000000?*I 0.50000000000000000?*I] )

%%% Fim Algebra linear %%%