Método de la Secante

Introducción y antecedentes

El método de la secante es un método numérico abierto que sirve para encontrar las raíces de una función de manera iterativa. El método se basa en el concepto de la recta secante que corta a la función de un punto a otro para aproximarse de manera iterativa a una de las raíces de la función dada.

En qué consiste

El método de la secante es una variante del método Newton-Raphson, pero a diferencia de este no necesita la derivada de la función. A través de la recta secante entre dos puntos iniciales [xn, xn-1], se aproxima a la recta tangente de la función en un punto dado y de la misma manera que en Newton-Raphson se busca el punto de la recta (secante) en el que cruza el eje x. Una vez que se tiene el valor en x, se repite el procedimiento ahora usando el valor de x encontrado y xn. El valor de xn se encuentra de la siguiente manera:

funcion

Requisitos previos

  • Una función continua.
  • Dos puntos iniciales.

Diagrama de flujo

secant

Criterio de detención del método

Se puede definir de manera iterativa: cuando la diferencia de valores aproximados de una iteración a otra sea menor a cierto error definido; o absoluto: cuando la función en el punto del valor de x encontrado entra en cierto error definido (en cuanto a su cercanía a cero).

Código fuente (GitHub)

screenshot-from-2017-02-28-18-22-35

Pruebas y resultados con casos de éxito, casos de falla y casos frontera

f(x) = x²-2

screenshot-from-2017-02-28-18-41-11

Esta función tiene dos raíces sqrt(2) y -sqrt(2), cuyas aproximaciones decimales son 1.4142135623 y -1.4142135623 respectivamente. Si utilizamos un valor de x0 y x1 de 1 y 1.5 el método retorna como raíz sqrt(2). Esto se debe a que la primer secante termina apuntando a 1.4. Haciendo prácticamente imposible que la secante pudiera aproximarse a la otra raíz.

screenshot-from-2017-02-28-18-51-08

En está misma función (Y para todas las funciones, en realidad), si se seleccionaran los valores x0 y x1 donde f(x0) y f(x1) son iguales (O lo suficiente para que no se pueda computar una diferencia), el método falla, pues la secante se haría horizontal y no tocaría f(x) = 0.

screenshot-from-2017-02-28-18-55-53


f(x) = e^x -0.5

screenshot-from-2017-02-28-19-19-13

Esta función tiene una única raíz en -0.693147. Si se toman valores iniciales separados el uno por el otro una cantidad adecuada, el método se ejecuta sin problemas.

La otra manera en que el método falle, es dar como parámetros iniciales, valores que al calcular la secante hace un avance mínimo. Causando un overflow. Tiende a ocurrir en casos donde la pendiente es muy vertical, y las primeras dos x son muy cercanas.

screenshot-from-2017-02-28-19-11-19

screenshot-from-2017-02-28-19-11-29

Existe otro caso, basado en los mismo principios (Crear una secante muy vertical), pero que las x no tienen que estar muy juntas. En este caso se da como valores iniciales -20 y 15. Creando una secante vertical, que termina apuntando a -20 de nuevo.

screenshot-from-2017-02-28-19-35-09

Como se menciono en el caso anterior, el método falla si la secante calculada es prácticamente horizontal. En el caso anterior podía ocurrir porque f(x0) y f(x1) eran igual. En este caso, la función no tiene por su naturaleza dos f(x) iguales, pero aún así se puede obtener una secante muy horizontal.

screenshot-from-2017-02-28-19-19-30


Para finalizar con los casos, en cualquier función, si cualquiera de los parámetros iniciales es la raíz, el método da como resultado esa x. Esto debido a que al momento que la secante toca f(x) = 0, es en el punto x proveido.

Conclusiones

El método de la secante es útil por el hecho de que no se necesita saber la derivada de la función, basta con tener la función y recibir dos valores de x. Estos dos valores de x afectan cómo se ejecutará el método y se tienen que introducir de tal manera que la función en xn sea más cercano al cero que xn-1. Por esto mismo el uso del método es limitado y sólo funcionará cuando se conoce previamente la función.

Anuncios

Project Weightless – My entry

Here you can find our project scope/description. Its a document in Google Drive. And the presentation, also in Google Drive.

Well, at the start we had some problems, Raúl and I. Basically, because we didn’t had any class together, we didn’t share any project to work in this class. Finally, we came up with this idea, inspired in the hobbies of Raúl. And then, fortunately, Gabriel became a new member for our team.

Now the problem is that each one of us has his load of projects of other classes, and its a shame we couldn’t integrate another project to this class, to save some time, and make a better final product for both classes.

 

Let’s change it all: Ch 6 SG

In life, you should control the changes made, don’t let life control them. In an affective project, changes are controlled by it, an ineffective one lets changes control it. That it’s why change control is created, to let changes be made, while ensuring that their impact is truly understood.

The procedure to approve changes is rather simple.

  • If the changes are made during the initial development (Requirements definition, architecture construction, etc.), no further procedure is needed. Changes are made freely
    At the end of the initial development, a technical review is made, to approve the work is done.
    Finally, the initial development is presented to the change board, which approves the content of the phase. It ensures all parties are satisfied and considered.
  • Version control is implemented. Is a system that stores changes made (mainly to the source code). It archives all the versions of the code.
  • Systematical Change Proposals are done now. Every change is proposed to a board. The proposal contains the changes to be made and the impact (In cost and benefits). Then, the board notifies the parties affected by the changes, which give their viewpoint. At the end, the final decision of the approval is made by the board. Which notifies to all concerned parties of the resolution

The main benefit of implementing change control, is that is will always do what is meant to be done. To protect the project from unnecessary changes.

The main problem is to incorrectly consider a change (Either by approving it, or not). In the book, a number of question the board should ask is listed. This, to make the decisión with more certainty,

To be successful at staging: Ch 5 SG

The software projects are always divided into stages. The first divisions we can make are the intellectuals. There are 3 intellectual stages, which exist at the same time, because there is no successful project which doesn’t let all the phases to coexist:

  1. Discovery: State the real user requirements. Convert uncertainty into certainty through interviews and building prototypes.
  2. Invention: Creation of architecture and design for the project, and classes and functions. Again, the objective is to gain certainty, even more than in the discovery phase.
  3. Implementation: Convert the potential of the certainty created in the previous phases, and map it to a real project.

And continuing with the division of a project into stages, behold, the Stage Delivery Plan. A plan to develop software, where after 3 phases of requirements definition, n deliveries are made (Once per stage). Each stage delivery is release that is given to the client, to approve or to make changes, so the next delivery approaches to what the client desires. The main benefits of the Staged Delivery Plan are:

  • Functionality (At least, the most important) is implemented very early. So the client can start to see a “product” since the start.
  • Because at the end of each stage there is a delivery, risks of integration and user requirements are reduced. At the final delivery, the integration of all functionality shouldn’t be a problem, and the requirements are mostly all accounted for.
  • The problems are detected early. If since the first stages, the project is in trouble, there is a problem. You don’t need to wait until the project is almost done to find out.
  • Developers don’t lose time making status and progress reports, because there is no accurate report than the working software.
  • Making almost releasable software at the end of each stage, gives more options to choose at the end.
  • There is no problem making large estimations for the whole project, because smaller estimates are done instead, for each stage.

The only considerable downside is that Staged Delivery Plan can cost more, but not that much. Usually people tend to think there are a lot of extra costs, but the truth is that most of those expenses would happen on any method. The only truly extra cost is the expense of releasing software at each stage.

It is expected that all the steps at each stage tend to overlap, and coexist at the same time. It is accepted, but one should try to do at least 80% of the work of the activity, before starting another one. Mainly because the errors can be contained to the step where they were created.

During the first phase, of this plan, requirements and the architecture are constructed. Here, the effort is lower than the implementation phase, where mini cycles of design, construction and testing are made (One per stage). After “50%” off the project development, the effort stays flat. This happens because the last part isn’t just testing, or transitioning to delivery (Like in linear models), but still, the mini cycles are still done at each stage. It’s important to remember that the percentage of schedule assigned to an activity, isn’t equal to the percentage of effort.

Regarding how much code is written, in Stage Delivery Plan, it grows in a S shape. Little code at the start, then increments in the middle stages, and flattens on the final ones, as less creation of code is done and more fixing is made.

Finally, there should be, as always, milestones and deliveries stated formally, so there can be an easy way to track progress. The book’s page has all the details.

 

 

Método de Newton-Raphson

By Arturo Fornés A01227071 and Miguel Montoya A01226045

Introducción y Antecedentes:

El método de Newton-Raphson tiene como propósito encontrar una raíz de una función a través de aproximaciones iterativas a un valor de x. El método se basa en el concepto geométrico de la línea tangente; en cada punto f(a), la línea tangente es dada por la derivada f'(a).

El Método (en qué consiste):

Dado un valor de x0, una aproximación a una raíz será denominado x1, que se encuentra usando la línea tangente formada entre los puntos (x1, 0) y (x0, f(x0)). Formando una función de forma y = mx + b podemos despejar para encontrar x1.

Requisitos Previos:

  • Una función diferenciable y continua.
  • Su derivada.
  • Un valor de x inicial.

Diagrama de Flujo:

newtonrhapson

Criterio de Detención del Método:

Nosotros definimos que el método se detuviera cuando se obtenga un error absoluto (f(x1)) menor al error máximo. El método se puede modificar para que se detenga cuando se obtuviera un error iterativo (p) menor al seleccionado
Otras manera para que el método se detenga es si se consigue un NaN (Not a Number) al momento de evaluar las funciones o de calcular la p.

Código Fuente: (GitHub)

screenshot-from-2017-02-15-21-17-01

Pruebas y Resultados:

 

f2

f(x) = x⁷-3 con derivada f'(x) = 7x⁶

Este método tiene sólo una raíz, por lo que el método siempre encontrará la misma raíz, en x = (3)^(1/7) ≈ 1.1699. Pero esta función no resulta tan simple como parece, es sino por cómo se ve que se puede identificar el problema.

La función tiene una pendiente casi horizontal, muy pequeña, entre x = (-1, 1), que son aproximaciones a los puntos de inflexión. Usar valores menores al punto de inflexión positivo resultará en un disparo en las aproximaciones a valores muy grandes, ya que la línea tangente en esos puntos tendrá una pendiente con muy poca inclinación.

Estos son los valores que retorna el método dado ciertas x0:

x0 = 6, pasando el punto de inflexión.

f2x6

x0 = -0.2, dentro de la zona con la pendiente casi horizontal.

El pase de diapositivas requiere JavaScript.

x0 = 0, cuando la pendiente es 0, no se encuentra la raíz, pues se indetermina.

f2x0.png


 

f1

f(x) = cos(3x) – x³, con derivada f'(x) = -3(sin(3x) + x²)

Esta función tiene 3 raíces, por lo que dada cierta x0, resultará en alguna de estas raíces:

x≈-0.996071
x≈-0.593972
x≈0.485394

Sólo cuando x0 es igual a uno de los puntos de inflexión la función se indetermina igual que en el caso anterior. Resultados según ciertos valores de x0.

x0 = -1.5

f1x-1.png

x0 = -0.2

f1x-2

x0 = 3

f1x-3

x0 = 0, en uno de los puntos de inflexión, la función se indetermina.

f1x-4.png


screenshot-from-2017-02-15-21-40-38

f(x)=ln(x-1) +1

Esta función tiene una raíz x = 1 + 1/e (x = 0.367879).

Esta función se indetermina, cuando se coloca como valor inicial un número menor a 1 (Incluyéndolo). Y de 2 a infinito (Incluyéndolo), pues la pendiente calculada por la derivada es de una magnitud mínima, causando que la siguiente aproximación sea imposible de calcular.

x0 = 1.5, 2 y 1.

El pase de diapositivas requiere JavaScript.

Conclusiones:

Podemos concluir que este método no solo es mucho más sencillo de aplicar que el método de bisección común, pero también tiende a ser más rápido. A pesar de no poder obtener más de una raíz por intento, es muy eficaz de obtener la raíz en funciones donde la diferencia de pendiente no es muy insignificante.

The Mythical Man-Month Ch1

The Tar Pit

This chapter starts with an analogy, comparing the development of a project with a big animal trapped in a tar pit. Why? A animal, as it tries to escape, makes strong and fast moves that will only make him more stuck. Like an animal, a big project, where each problem isn’t solved with delicacy and order, makes things worse. But also, the best could happen, and the project can survive.

A project can produce either a “simple” program (Like the ones produced in garages by two programmers that then became famous) and a more useful but complex and costly program, that evolves from the “simple” one.  There are two types of these programs: The programming product, program that can be run, tested, repaired and extended, implemented in multiple OS and well documented; and a programming system, is a collection of interacting programs, with lots of interfaces, semantic and syntax, with a precise budget of system resources and a bunch of testings with different system components. Both of these types of programs cost at least 3 times more time of development.

There is a final program type, that combines the characteristics of a programming product and system. It costs 9 times as much but it the the truly useful program.

A programmer enjoys his craft, but also a programmer can woe it. I’m assuming every idea regarding this part of the chapter, is kind of subjective, because obviously everyone is different and something someone might enjoy, might be the difficult part for another one.

The reasons a programmer enjoys the craft are:

  • Its always fun to make things
  • Receives pleasure from doing things useful for others
  • Resolving puzzle types problems with lots of moving and interacting parts
  • Joy of learning, because the problems are always new
  • Delight of working the ming, because a programmer works with pure thoughts, it build everything from air

In general, its fun, because it promotes creativity and sensibilities.

The reasons a programmer woes the craft are:

  • The performance must be perfect, if there is an error in the code, that’s it, it won’t work. It must be perfect
  • There is always someone who establishes your objectives, resources and available information
  • There is a great dependence on others’ work
  • It’s not fun to being a bug finder
  • The project might be obsolete (To your own eyes) before completion. All because new ideas might arise, that aren’t implemented. Usually this one might really affect the morale, but the truth is that it might not be as bad, because the obsoleteness of a product mustn’t be measured against non-implemented ideas, but against similar already-released products.

So this is the views of a programmer in programming

Método de bisección

Por Arturo Fornés (A01227071) y Miguel Montoya (A01226045)

Antecedentes:

El método de bisección tiene como propósito encontrar raíces (o más bien, solo una raíz) de un polinomio. Es un método iterativo, es decir, parte del proceso se repetirá un número de veces hasta que se cumpla un requisito que nosotros seleccionamos, este puede ser hasta que se alcance un número de iteraciones o que se alcance un error aceptable.
Este método se basa en el teorema de valor intermedio.

El método:

El algoritmo de bisección consiste en un intervalo cerrado [a,b]. De acuerdo al teorema de valor intermedio, todos los valores de f(a) a f(b) son imagen de un valor del intervalo [a,b]; además si f(a) y f(b) tienen símbolos diferentes, quiere decir que en algún momento, un valor m, dentro de [a,b] tiene f(m) = 0, es decir, m es una raíz del polinomio.
Para llegar a este valor m, se divide el intervalo en 2, y se selecciona la mitad donde la f(a) o f(b), con el punto f(m) tengan todavía signo diferente. Este paso se repite con el nuevo sub-intervalo seleccionado, hasta que el valor de f(m) es 0, o una aproximación muy cercana a la real.

Requisitos previos:

-La función a evaluar deberá ser continua
-Se debe establecer un margen de error
-Se deben proporcionar dos x para generar un intervalo

Diagrama de flujo:

bisection1

Detención del método:

El método se puede detener de dos maneras: O encontró un error o la raíz no traspasa y = 0, por lo tanto retorna un error y finaliza; o pudo encontrar una raíz en el intervalo seleccionado (Incluyendo los casos frontera)

Código del método. Github :

screenshot-from-2017-02-03-12-26-24screenshot-from-2017-02-03-12-27-43

Pruebas y resultados (Casos):

El método obtendrá una raíz de manera correcta cuando se le pida la de una función que en algún momento cruza el eje x de positivo a negativo o al revés. Casos como estos incluyen las siguientes funciones:

f(x) = x, donde la raíz es 0

Se usa la siguiente función:
screenshot-from-2017-02-03-16-55-11
Comenzando con valores de x: -1 y 3, se entra al ciclo y se recorre la aproximación hasta que se encuentra la raiz. Se obtiene el siguiente resultado:
1

f(x) = x⁴+x³, donde las raíces son -1 y 0

Se usa la siguiente función:
screenshot-from-2017-02-03-17-02-53
Comenzando con los valores de x: -1 y 1 o 0 y 1, se obtiene en un paso una de las raíces, pues una frontera del rango dado es ya una de las raíces:
2 2-2

f(x) = x², con raíz en 0

Se usa la siguiente función:
screenshot-from-2017-02-03-17-06-16
Esta función sólo puede obtener la raíz de manera correcta si la raíz está en una frontera, por ejemplo, los siguientes valores de x: 0 y 1. Se obtiene el siguiente resultado:
3
Pero si se tratan de usar los siguientes valores de x: -1 y 1, a pesar de que la raíz esté en x = 0, en medio de los dos valores dados, no se entrará al ciclo pues f(-1) y f(1) son ambos positivos:
3-2
La función no cambia de positivo a negativo, por lo que se tiene un caso de fallo, otro ejemplo de fallo es la siguiente función:

f(x) = x⁴, con raiz en 0.

Se usa la siguiente función:
screenshot-from-2017-02-03-17-12-40
De la misma manera con valores de x: -2 y 2, no se obtiene una solución, porque la función nunca cruza el eje x:
4

Conclusiones:

El método de bisección es sencillo de aplicar, y útil en muchos casos, aunque tienes que sacrificar el poder obtener más de una raíz, con solo una ejecución, y son muchas las situaciones donde la raíz, a pesar de existir, no es encontrada por no cruzar y=0.