Método de Jacobi & Método de Gauss-Seidel

Introducción y antecedentes

Ambos son métodos semejantes, usados para calcular la solución a un sistema de ecuaciones lineales (De forma Ax = b).

Requisitos de los métodos

Para ambos:

  • El sistema de ecuaciones se tiene que poder representar en una matriz cuadrada
  • La diagonal no debe tener elementos nulos
  • La matriz tiene que ser dominante (Los elementos en la diagonal tienen que tener el coeficiente de mayor magnitud de la ecuación)

Diferencias

En Jacobi, para cada iteración, se usan los valores previamente estimados de las variables (O si es la primer iteración, los valores de las variables definidas por el usuario o las default). En cambio en Gauss-Seidel, el método va reemplazando las variables calculadas en la iteración anterior, por las de la iteración actual inmediatamente. Así el método reduce el número de iteraciones totales.

Diagramas de flujo

Se realizaron los diagramas de flujo para resolver un sistema de 3 ecuaciones y 3 incógnitas

Jacobi

Jacobi

Gauss-Seidel

Gauss-Seidel

¿Es un método iterativo?

Sí. Al final de cada iteración, el método ya tiene una aproximación a la solución. Durante la siguiente iteración, se utilizan los resultados previos obtenidos para calcular las nuevas soluciones.

Código

Jacobi: GitHub

Gauss-Seidel: GitHub

Criterio de convergencia del método

Para garantizar la convergencia de ambos métodos, Jacobi y– Gauss-Seidel, se tiene que cumplir con alguna de las siguientes condiciones:

  • Ser diagonal dominante.
  • Ser simétrica y definida positva.

En los siguientes ejemplos nos aseguraremos de cumplir con la propiedad de la diagonal dominante, esto se refiere a que el elemento de la diagonal de cada fila debe ser el elemento de mayor magnitud en esa fila.

Relajación (qué es y para qué sirve?)

Relajación es un método iterativo para resolver sistemas de ecuaciones. Consiste en actualizar los elementos del vector solución, uno a uno, asumiendo que los valores previos están correctos.

Pruebas y resultados

3 incógnitas

3x-2y+z=4

x+5y+2z=6

-2x+3y+6z=1

La solución del sistema es x = 1.6857143, y = 0.7142857, z = 0.3714286.

Usando scilab se encontró la solución:

01-scilab

El sistema cumple con la propiedad de la diagonal dominante, por lo que ambos métodos deberían encontrar la solución.

gs-01-gs.png
Usando Gauss-Seidel
gs-01-j
Usando Jacobi

Ambos métodos encontraron la solución con un error absoluto de 10^-6.


4 incógnitas

8x-3y+z-w=20

-x+20y-3z+8w=3

x+y+3z-w=3

6x-4y+11z+15w=9

La solución del sistema es x = 2.621404, y = 0.3945017, z = – 0.1140893, w = – 0.3263623.

Usando scilab se encontró la solución:

gs-02-matriz

Dado que el sistema cumple con la propiedad de la diagonal dominante, ambos métodos deberían encontrar la solución.

gs-02-gs.png
Usando Gauss-Seidel
gs-02-j
Usando Jacobi

Ambos métodos encontraron la solución con un error absoluto de 10^-6.

Casos de falla

Ambos métodos fallan cuando no se cumple con alguna de las condiciones mencionadas en la sección Criterio de convergencia del método, ambos métodos divergen, por ejemplo, si no se cumple con la propiedad de la diagonal dominante.

Conclusiones

Es clara la superioridad del método de Gauss-Seidel sobre Jacobi. Pues en menos iteraciones, se obtienen las soluciones al sistema. Solamente es necesario aplicar los cambios por cada variable del sistema, más que por cada iteración,

Anuncios

Requirements: Ch. 8 SG

The first “real” ideas of the project are reflected in UI prototypes and user manuals. But before doing that, something essential for the whole project needs to be gathered: The Requirements. How? Doing interviews to users and comparing products (Just remember that the difficult part is not to record what the user wants, but making him understand what he wants). And then? Write them, specify them, analyze, compare, build storyboards and prototypes. After all of that you have your requirements.

Overview of the process

  1. Identify end users that can define the product: They should be interested in the product in a way that you can deposit your complete trust in their criteria.
  2. Interview those end users: Here you will obtain the basic set of requirements.
  3. Build simple interactive UI: Really, as simple as possible. But make different alternatives. In paper storyboards are an easy way to present the requirements in a way everyone can understand.
  4. Show the UI to the end users and receive feedback. Work on the feedback on show it again. Do this until the end user is satisfied.
  5. Develop a style guide: The standards of the product look and feel.
  6. Extend the prototype to include every functionality: Now that you have every requirement defined and how each one must look, you can introduce everything. Still, it’s a throwaway, but lets try to work on a single one.
  7. Treat that prototype as the base line: Because you know what to reach, you can start giving formal estimates to the boss.
  8. Write the end user documentation: What will the user see, the basic “how does it work” and how to interact with it.
  9. Write the non end user documentation: The things that the user doesn’t care about, but someone else might. Like another team that might make an upgrade, and maybe needs to understand how the algorithms work, how the software interacts with the hardware, etc.

And that’s it.

Planning in advance: Ch. 7 SG

Even thought someone might say that its impossible to plan before knowing which are the requirements, but… THAT ISN’T TRUE! There are several thing to do. More specifically, 7 things.

Project Vision

For a team to share a vision and final objectives (Objectives aren’t requirements), the team functioned effectively. This will make improvements in very aspect of the team; from organizational and administrative improvements, such as decision making; to motivation and influence on the team.

The vision must be specific and motivational, but the most important characteristic is that it must be achievable. Finally, everyone must commit to the vision.

Executive Sponsorship

This refers to designate the support that the team or person that has heavy decision impact on the project. This person or team will approve every feature, user interface, release…  And it’s important that if this entity is a team, each member must represent a different interest.
Because no one likes to have the same boss multiple times… Imagine the same reproach by each boss when you get something wrong.

Project Scope Targets

Features, schedule and budget are things that can and should be declared before any real requirements definition. Well… an exact definition of theses 3 things can’t really be done, but  a real tentative target must be defined. A recommended technique to define this sort of things is to define an upper and lower limit for everything, this provides a margin to deal with the uncertainty.

Publicizing Plans and Projects

Big mistake: TO KEEP THE PLANNING SECRET. People need and should know what are they going to face in the future. If the manager doesn’t inform the programmers or the testers, considerations might not be taken to make a plan that can adapt to them. So, because there isn’t a plan that they approve, or at least that they can prepare for, people run out of control. What should always be public? You ask:

  • List of tasks completed
  • Defect statistics
  • Top 10 risk list
  • Percent of schedule used
  • Percent of resources used
  • Status reports given to upper management

Risk Management

Every project must commit to risk management. What does this mean? Well, to provide the all the necessary means to predict, act and resolve risks. What should be provided? An approach, resources and funds, and make the assessment of risk impact the project (I mean, if you know something is coming, let’s act on it). And which are the approaches available? Here, have a list:

  • Risk officer: Spotter of emerging risks. A “pessimistic” person that will try to find every possible problem during development.
  • To 10 risk list: A list, with possible risks and how is currently being fought.
  • Risk tracing: A system that prioritizes risks, if they are open or closed to process, and who is working on them.

Remember that each entry of the top 10 risk list needs to have a reason to be there. Answer why is that a risk and needs management, how is it going to be resolved, what steps are needed to solve it, who will do each step, when can a step be started, how much is going to cost. The answers need to be recorded.

Oh, and there can be a channel, available to everyone to report risks. The managers and officers can’t see everything.

Personnel Strategies

Basic knowledge to staff buildup: Senior staff at the requirements stage, add more staff to the development stage. And just because you need staff, you shouldn’t hire available people, you need to hire good and skilled people, even if that means to wait a little bit.

The team roles (For you to remember) are:

  • Project manager
  • Product manager
  • Architect
  • UI designer
  • End-user liaison (interact with users)
  • Developers
  • QA/Testers
  • Tool smith (develop utilities for the development)
  • Build coordinator (running daily builds)
  • Risk officer
  • End-user documentation specialist
  • Optional: Tiger teams (2 people temporary teams to solve problems fast)

Oh, and a last thing

Time accounting

Just… keep track on how is the personnel spending their time. OK? Good. This will help when making estimates, and presenting those estimates to the upper management.

And that’s it…

It’s a lot to take in. But when you do all of this, you have finally a SOFTWARE DEVELOPMENT PLAN.

Bye!

 

 

 

Eliminación de Gauss y Gauss-Jordan

Arturo Fornés – A01227071
Miguel Montoya – A01226045


Introducción y antecedentes

Gauss y Gauss-Jordan son ambos algoritmos del Álgebra Lineal que sirven para encontrar la solución a un sistema lineal (sistema de ecuaciones). Un sistema lineal puede tener una solución única, una infinidad de soluciones o ninguna solución. La solución única de un sistema de ecuaciones se encuentra despejando las incógnitas y encontrando su valor; se tiene una infinidad de soluciones cuando al despejar alguna de las ecuaciones quedan en 0=0; no se tiene solución cuando alguna de las ecuaciones resulta en 0=a, a != 0.

Requisitos de los métodos

  • Una matriz de dimensión n x n.
  • Un sistema de ecuaciones con una solución única.

Diferencias entre uno y otro método

Usando el método de Gauss se obtiene una matriz triangular superior; la última incógnita tiene una solución y se sustituye en la penúltima y se sigue este procedimiento para las siguientes filas en este orden.

Usando Gauss-Jordan se obtiene una matriz en forma escalonada reducida, es decir donde el pivote de cada fila es 1 y todo elemento que no sea el pivote es 0, se forma una diagonal de 1’s. Al llegar a la forma escalonada reducida de la matriz, ya se tiene la solución en el vector con el cual se expandió la matriz de coeficientes para formar el sistema lineal.

Diagramas de flujo

Gauss

Gauss

Gauss-Jordan

Gauss-Jordan

¿Es un método iterativo?

Ninguno de los dos métodos, Gauss ni Gauss-Jordan, es iterativo, hay iteraciones dentro de ellos pero no se aproxima de manera iterativa al resultado. Un método iterativo es definido por realizar una aproximación a la solución en cada una de sus iteraciones; Gauss y Gauss-Jordan calculan una solución una única vez, en ambos casos un vector solución.

Archivo de script en Scilab

Gauss: GitHub.

Screenshot from 2017-03-11 13-27-05

Gauss-Jordan: GitHub.

Screenshot from 2017-03-09 07-40-50

Pivoteo, y escalamiento.

El pivote en una matriz es definido como el primer elemento que sea diferente de 0 en una fila. La forma escalonada se obtiene al seguir un patrón de escalones entre los pivotes, donde el pivote de una fila se encuentre a la derecha del pivote de la fila anterior.

Pruebas y resultados con sistemas de más de 3 incógnitas

Caso 1:

3x + 3y + 12z +21w = 18
2x + 4y + 10z +14w = 16
-2x + -8z -18w = 10
3x + 11z +28w = 11

Gauss

Screenshot from 2017-03-11 13-24-48

Gauss-Jordan

Screenshot from 2017-03-11 13-25-15.png

Ambos métodos obtienen los resultados de manera exitosa

Caso 2:

2x +3y -2z = 7
x -2y +w +4v = -2
10y +4z +5v = 43
7w +7v = 0
3x +5y -5z +11w +v = -2

Gauss

Screenshot from 2017-03-11 14-11-47.png

Gauss-Jordan

Screenshot from 2017-03-11 14-12-18

Ambos métodos resuelven el sistema de 5 variables correctamente

Casos de falla

Ambos métodos, Gauss y Gauss-Jordan, fallarán para sistemas que no tengan una solución única o en los que el pivote de una fila se encuentre a la izquierda del pivote anterior. Lo último se puede evitar reacomodando manualmente las filas (intercambiándolas entre sí).

Conclusiones

El método de Gauss requiere menos pivoteo, pero al mismo tiempo necesita realizar el proceso de sustitución. mientras tanto, Gauss-Jordan elimina por completo la sustitución, obteniendo un valor para cada variable de manera independiente, aunque necesita de mayor pivoteo.

Método de Cramer

Arturo Fornés – A01227071

Miguel Montoya – A01226045


Introducción y antecedentes

La regla de Cramer es un método númerico para obtener las soluciones a un sistema de ecuaciones dado. Es costoso en recursos, sobretodo en matrices grandes.

La regla es: xj = det(Aj)/det(A)

Donde cada Aj es la matriz A donde la columna j es reemplazada por el vector solución

Requisitos del método

  • Para el funcionamiento la matriz tiene que ser cuadrada.
  • El vector solución no deberá ser 0, pues causaría que det(Aj) fuera 0, y por lo tanto la solución. Cuando puede no ser el caso.

Qué es un determinante

Es un termino complejo de definir. El determinante de una matriz es un número, si es 0 es que es un sistema singular, y si es cercano a 0 es que es un sistema mal condicionado. Un sistema singular en un sistema de ecuaciones ocurre cuando varias de las ecuaciones tienen la misma pendiente.

Diagrama de flujo

Cramer

Control de iteraciones del método

Archivo de script en Scilab (GitHub)

Screenshot from 2017-03-08 21-15-05

Pruebas con 2 y 3 incógnitas

2 incógnitas

[  1   1] = [ 2]
[-1   1]    [ 3]

Screenshot from 2017-03-09 20-22-39

El método funciona de manera exitosa

3 incógnitas

[  1   2    3]    [ -5]
[  3   1  -3] = [  4]
[-3   4   7]    [ -7]

Screenshot from 2017-03-09 20-25-06

El método funciona de manera exitosa

Conclusiones

Es un método mucho más fácil de implementar que el método de eliminación  Gaussiana y sustitución. El problema comienza al momento de tener que calcular determinantes de matrices muy grandes. Aunque nunca hay que olvidar que esto permite evitar el pivoteo de Gauss.

Comparación métodos

Arturo Fornés – A01227071
Miguel Montoya – A01226045


Tipo

  • Bisección: Cerrado
  • Newton-Raphson: Abierto
  • Secante: Abierto
  • Bairstow: Abierto

Requisitos para buen funcionamiento

  • Bisección: Función continua.
  • Newton-Raphson: Función diferenciable y continua.
  • Secante: Función continua.
  • Bairstow: Función polinómica.

Riesgos

 

  • Bisección: Que no exista un cambio de signo al cruzar la raíz.
  • Newton-Raphson: Que una aproximación resulte cercana a un punto de inflexión (Que no sea la raíz).
  • Secante: Si la pendiente es muy grande o muy pequeña el método falla.
  • Bairstow: A pesar de ser el método más confiable, polinomios de muy alto grado, o si son de grado impar con multiplicidad total a una raíz pueden hacer que el método falle, o que el resultado no sea tan exacto.

 

Convergencia

 

  • Bisección: Lineal.
  • Newton-Raphson: Tiene una convergencia cuadrática.
  • Secante: Superlineal, por ser la razón dorada. Es casi cuadrática.
  • Bairstow: Al utilizar Newton-Raphson para calcular las raíces, también es cuadrática.

 

Ventajas y desventajas

 

  • Bisección: Tienes que introducir dos datos iniciales, y no encontrará raíces en casos que no se cambia de signo, como x².
  • Newton-Raphson: Es muy fácil de implementar, y la velocidad de convergencia es alta, siempre y cuando haya una pendiente significante.
  • Secante: No es necesario saber la derivada de la función, pero es muy fácil que los dos primeros números introducidos puedan hacer que la pendiente de la secante sea muy pronunciada o muy horizontal.
  • Bairstow: Puede encontrar todas las raíces de una función, pero solamente si es de un polinomio (No funciona con funciones trigonométricas o exponenciales).

 

Tolerancia al error

 

  • Bisección: Muy poca. El hecho de que la raíz tenga que cambiar de signo al cruzarla y que tenga que estar en el rango introducido, hace que falle muy seguido.
  • Newton-Raphson: Tiene una mayor tolerancia al error que bisección, pero no descarta que el método falle si la función tiene varios puntos de inflexión que no sean raíces.
  • Secante: Tiene una buena tolerancia, pero en los casos donde el método falla puede considerarse como situaciones ridículas (Como elegir como valores iniciales 1 y -1 en la función x²)
  • Bairstow: Tiene una muy buena tolerancia al error, de hecho, tiene a no indeterminarse, y en casos de polinomios de muy alto grado, da resultados aceptables.

 

Tipo de raíces que encuentra

 

  • Bisección: Reales
  • Newton-Raphson: Reales
  • Secante: Reales
  • Bairstow: Reales y complejas

 

Cuántas raíces encuentra el método

 

  • Bisección: Una sola raíz
  • Newton-Raphson: Una sola raíz
  • Secante: Una sola raíz
  • Bairstow: Dos raíces, o todas dependiendo de la implementación

 

Schedule – Ch2 MMM.

Which is the main reason for a project to fail? Lack of time in the calendar. And why is there little time? Fail to estimate, confuse progress and effort, bad monitoring, and bad manpower management.

But, don’t let this bad things get to you… Lets be optimists.

In fact. that its exactly what we must stop doing (We shouldn’t stop being optimists, the problem is that in the programming area, we kinda abuse of it). We are always stuck saying “This time will work!” and “I assure you, it’s the last bug”. And why all of this optimism? Because programming involves creating what, in our minds, it’s already completed; So we tend to think everything will be fine.

So lets stop being optimists, shall we?

Let’s talk about the fallacious idea of a man-month. Bad project managers tend to think that the more people working on a project, the less month will be needed to complete it. But that is only true is there is a lack of manpower, when the programmers aren’t enough to do some progress at all. After that point of equilibrium, more manpower only involves more costs, because the tasks need a minimum time to be completed (A baby will be born in 9 months, no matter how many mothers he has). Even if some independence between some task was found, the time to “train” the new programmers, it it doesn’t increases even more the time needed, at least it doesn’t affect the schedule whatsoever. The only way that increasing the manpower with no limits could be a good idea, is when every single task has nothing to do with the rest of them.

And now that we have the manpower thing sorted up, you should know that what most affects a schedule is the debugging and testing. Because we are optimists, this phase is usually badly estimated. 1/6 of the schedule should be for coding, and 1/2 to all the tests and debugging. And why this bad estimates (Apart of positivism), the managers will select a schedule that will me the owner happy, instead of defending the procedure.