Estructuras de datos (Prof. Edgardo A. Franco)

1

Practica 03: Eliminación Gaussiana

M. en C. Edgardo Adrián Franco Martínez http://www.eafranco.comedfrancom@ipn.mx@edfrancom edgardoadrianfrancom

Contenido• Introducción

• Ecuaciones lineales

• Sistemas lineales

• Matriz aumentada

• Eliminación Gaussiana

• Requerimientos de la Practica 01

• Observaciones

• Envío de la practica

• Formato del reporte

• Fechas de entrega2

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Introducción• El estudio de los sistemas de ecuaciones lineales y

sus soluciones es uno de los temas más importantesdel algebra lineal, por otro lado el uso de lacomputadora para la solución de este tipo desistemas hace ver la importancia de la computadorapara la solución de problemas matemáticos,demostrando que provee una gran capacidad deprocesamiento que le permiten apoyar ensimulaciones y soluciones a problemas mucho muycomplejos.

3

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Ecuaciones Lineales• Una ecuación lineal de n variables 𝑥1, 𝑥2, 𝑥3, … , 𝑥𝑛

se define como una ecuación que se puedeexpresar de la forma:

𝑎1𝑥1 + 𝑎2𝑥2 + 𝑎3𝑥3 + …+ 𝑎𝑛𝑥𝑛 = 𝑏

• Donde en 𝑎1, 𝑎2, 𝑎3, … , 𝑎𝑛 y 𝑏 son constantesreales. Las variables en una ecuación lineal algunasveces se denominan incógnitas.

4

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Sistemas Lineales• Un conjunto finito de ecuaciones lineales en las

variables 𝑥1, 𝑥2, … , 𝑥𝑛 se denomina sistema deecuaciones lineales o sistema lineal. Una sucesión de

números 𝑠1, 𝑠2, … , 𝑠𝑛 se denomina solución del sistema si

𝑥1 = 𝑠1 ,𝑥2 = 𝑠2, … ,𝑥𝑛 = 𝑠𝑛 es la solución de todas ycada una de las ecuaciones del sistema.

5

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Se dice que un sistema de ecuaciones que no tiene solucioneses inconsistente, si existe por lo menos una solución delsistema, éste se denomina consistente.

No existe solución Una solución Infinidad de soluciones

6

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Un sistema arbitrario de m ecuaciones lineales con nincógnitas se puede escribir como:

𝑎11𝑥1 + 𝑎12𝑥2 + 𝑎13𝑥3 + …+ 𝑎1𝑛𝑥𝑛 = 𝑏1𝑎21𝑥1 + 𝑎22𝑥2 + 𝑎23𝑥3 + …+ 𝑎2𝑛𝑥𝑛 = 𝑏2

𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + 𝑎𝑚3𝑥3 +⋯+ 𝑎𝑚𝑛𝑥𝑛 = 𝑏𝑚

• Donde en x1, x2, x3, … , x𝑛 son las incógnitas y las letrasa y 𝑏 con subíndices denotan constantes.

⋮ ⋮ ⋮ ⋮ ⋮

7

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• Si mentalmente se ubica a los signos +, las letras 𝑥 y lossignos =, entonces un sistema de 𝑚 ecuaciones linealespuede abreviarse al escribir solo el arreglo rectangular denúmeros:

𝑎11 𝑎12 … 𝑎1𝑛 𝑏1𝑎21 𝑎22 … 𝑎2𝑛 𝑏2...

.

.

.

.

.

.

.

.

.

.

.

.𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑛 𝑏𝑚

• Este arreglo se denomina matriz aumentada del sistema.

8

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Matrices aumentadas

Eliminación Gaussiana• El método básico para resolver un sistema de ecuaciones

lineales es sustituir el sistema dado por un nuevo sistemaque tenga el mismo conjunto solución, pero que sea másfácil de resolver. Este nuevo sistema suele obtener en unaserie de pasos mediante la aplicación de los tres tipos deoperaciones siguientes para eliminar incógnitas de manerasistemática.

1. Multiplicar una ecuación por una constante diferente de cero2. Intercambiar dos ecuaciones3. Sumar un múltiplo de una ecuación a otra ecuación

9

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

• La eliminación gaussiana se basa en la idea de reducir lamatriz aumentada a una forma suficientemente simple, i.e.con base en operaciones efectuadas en los renglones de lamatriz aumentada se deberá de llevar la matriz aumentada auna forma escalonada reducida.

10

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Algoritmo de eliminación Gaussiana

11

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Requerimientos de la practica• Construir un programa en C capaz de dar

solución a sistemas de ecuaciones lineales, conbase en el método de eliminación gaussiana.

12

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Observaciones• Siempre se ingresarán sistemas de ecuaciones lineales, los

cuales tienen una solución.

• El método de reducción Gaussiana deberá ser explicado ydetallado en el reporte.

• Se deberá de reflejar directamente cada uno de los pasos delmétodo en el programa implementado.

• El programa deberá ser modular, buscando tenerprocedimientos simples como:

void Intercambia(double * matriz, int fila1, int fila2);

void Multiplica(double * matriz, int fila, double constante);

void Suma(double * matriz, int fila1, double constante, int fila2);

13

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Formato del reportes de practica• Portada• Introducción• Planteamiento del problema• Diseño y funcionamiento de la solución (Descripción de la abstracción del

problema y su solución modular, apoyándose de diagramas de flujo y/o pseudocódigoen un lenguaje claro).

• Implementación de la solución (Según la solución diseñada como seimplemento en el lenguaje de programación, explicaciones de los módulosimplementados)

• Funcionamiento (Verificación de la solución, pruebas, resumen de resultados desalida y Pantallazos)

• Errores detectados (Si existe algún error detectado, el cuál no fue posible resolvero se desconoce el motivo y solo ocurre con ciertas condiciones es necesario describirlo)

• Posibles mejoras (Describir posibles disminuciones de código en laimplementación o otras posibles soluciones)

• Conclusiones (Por cada integrante del equipo)

• Anexo (Códigos fuente *con colores e instrucciones de compilación)

• Bibliografía (En formato IEEE)14

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Envío a través de la pagina Web del curso

• En un solo archivo (ZIP, RAR, TAR, JAR o GZIP)• Reporte (DOC, DOCX o PDF)

• Códigos fuente (.C, .H, etc.)

• Código documentado: Titulo, descripción, fecha, versión, autor.

• (Funciones y Algoritmos: ¿Qué hace?, ¿Cómo lo hace?, ¿Qué recibe?, ¿Qué devuelve?, ¿Causa de errores?).

• NO enviar ejecutables o archivos innecesarios, las instrucciones decompilación van en el anexo del reporte. (Yo compilare los fuente).

15

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez

Fechasde entrega1. Mostrar el funcionamiento de la practica en la sesión de

laboratorio del miércoles 29 de Mayo de 2019.

2. Enviar vía Web en un archivo comprimido (ZIP, RAR oTAR), reporte y códigos de C antes del día Lunes 03 dejunio de 2019 (23:59:59 hora limite).

Grupo Contraseña

1CM12 algoritmia1cm12

16

Alg

ori

tmia

y p

rogr

amac

ión

est

ruct

ura

da

Pra

ctic

a 0

3:

Elim

inac

ión

Gau

ssia

na

Pro

f. Ed

gard

o A

dri

án F

ran

co M

artí

nez