26.3: Proceso de ortogonalización de Gram-Schmidt

Última actualización
Guardar como PDF

Page ID: 115372

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

import math
import copy
from urllib.request import urlretrieve
urlretrieve('https://raw.githubusercontent.com/colbrydi/jupytercheck/master/answercheck.py', 
            'answercheck.py');

def transpose(A):
    '''Calculate the transpose of matrix A represented as list of lists'''
    n = len(A)
    m = len(A[0])
    AT = list()
    for j in range(0,m):    
        temp = list()
        for i in range(0,n):
            temp.append(A[i][j])
        AT.append(temp)
    return AT

Hacer esto

Implementar el proceso de ortogonalización de Gram-Schmidt a partir del libro de texto Hefron (página 282). Esta función toma como entrada una\(m \times n\) Matrix\(A\) con columnas linealmente independientes y devuelve una\(m \times n\) Matrix\(G\) con vectores de columna ortogonales. El algoritmo básico funciona de la siguiente manera:

AT = transponer (A) (este proceso trabaja con las columnas de la matriz por lo que es más fácil trabajar con la transpuesta. Piense en una lista de lista, es fácil obtener una fila (una lista)).
Haga una nueva lista vacía del mismo tamaño que AT y llámela GT (G transpose)
Índice de bucle i sobre todas las filas en AT (es decir, columnas de A)
- GT [i] = AT [i]
- Índice de bucle j de 0 a i
  - GT [i] -= proj (GT [i], GT [j])
G = transponer (GT)

Utilice la siguiente definición de función como plantilla:

def GramSchmidt(A):
    return G

Aquí, vamos a probar tu función usando los vectores:

A4 = [[1,4,8],[2,0,1],[0,5,5],[3,8,6]]
print(transpose(A4))
G4 = GramSchmidt(A4)
print(transpose(G4))

from answercheck import checkanswer

checkanswer.matrix(G4,'a472a81eef411c0df03ae9a072dfa040');

A2 = [[-4,-6],[3,5]]
print(transpose(A2))
G2 = GramSchmidt(A2)
print(transpose(G2))

from answercheck import checkanswer

checkanswer.matrix(G2,'23b9860b72dbe5b84d7c598c08af9688');

Pregunta

¿Cuál es la complejidad Big-O del proceso Gram-Schmidt?