[comp-systems]

Otros algoritmos interesantes, alguien que se atreva a iniciar a codificarlos

Metodo Gasuss-Jordan
Un codigo en C
http://www.taringa.net/posts/ciencia-educacion/16722669/Programa-en-C-Metodo-de-Gauss-Jordan.html

Determinante

[compsystems]

Listo Newton_Raphson, hay que pulir ciertos detalles de presentación, pero funciona, por favor lo prueban, lo optimizan y me comentan sobre su funcionamiento, el código esta echo de tal manera que muestra los pasos de la ejecución para hacerlo mas didáctico, estas sentencias se pueden eliminar.

He visto muchos códigos de Newton_Raphson en la red pero todos cometen un grave error, no chequean si la derivada retorna cero, creando una indeterminación, por ende el programa termina abruptamente, ademas mi codigo si no converge llama nuevamente a la función principal

Código: [Seleccionar]

// versión 1.0.0 ultima edicion 28/Oct/2014
// By  ingmarov and  JAIMEZA aka (compsystems) www.jaimeza.org 
// Para ejecutar este codigo use PSEINT http://pseint.sourceforge.net

// http://es.wikipedia.org/wiki/M%C3%A9todo_de_Newton
// [youtube]opLpVhq4Vjo[/youtube]
// ejempo  1*x^3-6*x^2+11*x-6*x^0 polinomio de grado 3, tiene 4 coeficientes visto en forma vectorial o de arreglo como [ 1, -6, 11, -6 ]
// raices {1,2,3}

// funcion auxiliar
funcion valor_retorno = evalPolinomio( copia_Pol, orden_Pol, val_x )  // Esta función como su nombre lo indica evalúa un polinomio de orden n en el valor x
Definir valor_retorno, acumSum, polEval como real;
Definir k Como Enteros;

acumSum = 0; // valor inicial de la expresion a evaluar
Escribir " ";
Para k = 0 Hasta orden_Pol Con Paso 1 Hacer // segun el ejemplo si 1*x^3+6*x^2+11*x+6*x^0 entonces inicia ciclo entre 0 y 3
polEval = (copia_Pol[k+1]* (val_x)^(orden_Pol-k) );
//Imprimir polEval;
acumSum = acumSum + polEval;
//Imprimir "para k =" k, " Acumulado = ", acumSum;
// Ejemplo
// para k = 0 extrae el coeficente de la posicion 1 y lo multiplica por el valor de x^(3-0) => 1*x^3 y le suma el valor acumulado anterior
// para k = 1 extrae el coeficente de la posicion 2 y lo multiplica por el valor de x^(3-1) => x^2 y le suma el valor acumulado anterior
// para k = 2 extrae el coeficente de la posicion 3 y lo multiplica por el valor de x^(3-2) => x^1 y le suma el valor acumulado anterior
// para k = 3 extrae el coeficente de la posicion 4 y lo multiplica por el valor de x^(3-3) => x^0 y le suma el valor acumulado anterior
FinPara

valor_retorno = acumSum; // valor_retorno es la variable que contiene el valor de retorno cuando se invoca desde otra funcion o proceso
FinFuncion


// funcion auxiliar
funcion Newton_Raphson()

Dimension Pol[10]; // Se crean un arreglo para almacenar los coeficientes del polinomio (maximo 10 coeficientes)
Dimension derPol[9]; // Se crean un arreglo uno para almacenar los coeficientes de la derivada. (maximo 9 coeficientes)
Definir Pol, derPol Como Entero; // tipo de coeficientes enteros para el polinomio y derivada

Definir n Como Entero; // variable para el grado del poninomio
Definir i, ci Como Entero; // variables contadores

Escribir "Bienvenido!, esta aplicación le ayudará a localizar la raices de un polinomio p(x) usando el algoritmo de Newton-Raphson";
Escribir Sin Saltar "Escriba el grado del polinomio n= ";
Leer n;

Escribir "Escriba los coeficientes del polinomio ordenado de forma canónica descendente";
// Ciclo Para: sirve para leer los coeficientes del polinoio y hallar su derivada.
Para ci = 1 Hasta n+1 Hacer // un polinomio de grado n, tiene n+1 coeficientes
Escribir Sin Saltar "ingrese coeficiente ", ci, " = ";
Leer Pol[ci]; // asignar por lectura de teclado cada coeficiente del polinomio
Si ci < n+1 Entonces // la derivada del x^0 es cero por eso no se incluye
derPol[ci] = Pol[ci]*( (n-ci)+1); // asigna el valor de la derivada en la formacion o arreglo delPol
FinSi
FinPara

Para ci = 1 Hasta n+1 Hacer // Esto no es necesario pero lo que hace es escibir el polinomio.
Si ci < n Entonces
Escribir Sinsaltar Pol[ci],"*x^", n-(ci-1), "+";
Sino
Si ci=n Entonces // para x^1
Escribir Sinsaltar Pol[ci],"*x+"; // extrae el valor del coeficiente de x^1
Sino
Escribir Pol[ci]; // para x^0
FinSi
FinSi
FinPara

Escribir "Derivada"; // Este escribe el polinomio correspondiente a la derivada.

Para ci = 1 Hasta n Hacer
Si ci < n-1 Entonces
Escribir Sinsaltar derPol[ci],"*x^", n-ci, "+";
Sino
Si ci=n-1 Entonces
Escribir Sinsaltar derPol[ci],"*x+";
Sino
Escribir derPol[ci];
FinSi
FinSi
FinPara

// Esta es la iteración propia del algoritmo de Newton_Raphson
Definir x0, x1, iter, flag_salida, p_x0, dp_x0 como real;
Definir test1, test2 como logico;


Definir EPS Como Real; // criterio de exactitud
//Escribir "criterio de convergencia EPS= " sin saltar;
//leer EPS; // margen de error;

Definir EPS1 Como Real; // criterio de exactitud
Escribir "criterio de exactitud, tolerancia EPS1= " sin saltar;
leer EPS1; // margen de error;

Definir max_iter Como Entero;
Escribir Sin Saltar "Ingrese el numero de iteraciones maximo permitido";
Leer max_iter;

Escribir "El polinomio tiene ", n , " raices";

Escribir "Ingrese el valor inicial, absisa cercana a la raíz x0 = " sin saltar;
Leer x0; // Este es el primer valor almacenado para comenzar la iteración


flag_salida = 0;
iter = 1; // iteracion inicial
p_x0 = evalPolinomio( Pol, n, x0 ); // Se evalúa al polinomio en el valor x0
Escribir "Pol(", x0, ")= ", p_x0; // imprime el valor resultante

test1 = abs(p_x0)>EPS1; // el valor de x0 no cumple el criterio de exactitud
escribir "abs(p_x0)>=EPS1: ", abs(p_x0), ">", EPS1, ": ", test1;
test2 = iter <= max_iter;
escribir "iter <= max_iter: ", iter "<=" max_iter, ": ", test2;

Mientras test2 y test1 Hacer
escribir " "
escribir "ITER #", iter;
escribir "x0=", x0;
test2 = iter <= max_iter;
escribir "iter <= max_iter: ", iter "<=" max_iter, ": ", test2;

p_x0 = evalPolinomio( Pol, n, x0 ); // Se evalúa al polinomio en el valor x0
Escribir "Pol(", x0, ")= ", p_x0; // imprime el valor resultante
test1 = abs(p_x0)>EPS1; // el valor de x0 no cumple el criterio de exactitud
escribir "abs(p_x0)=",abs(p_x0);
escribir "abs(p_x0)>=EPS1: ", abs(p_x0), ">", EPS1, ": ", test1;




dp_x0 = evalPolinomio( derPol, n-1, x0 ); // Se evalúa la derivada en el valor x0
Si dp_x0 == 0 Entonces
Escribir "la derivada evaluada en xo es cero, por lo tanto x1 se vuelve indefinido";
Escribir "Escoja otro valor inicial de xo";
iter = max_iter+1; // salida forzosa del loop
flag_salida = 1;
Sino
Escribir "DerPol(", x0, ")= ", dp_x0;
x1 = x0 - (p_x0/dp_x0); // Esta es la definición del algoritmo de Newton-Raphson
//EPS = abs((x1-x0)/x1);

iter = iter+1; // Esto incrementa el número de iteraciones hechas
escribir "x1=", x1;
x0 = x1; // actualiza valor inicial

    FinSi

FinMientras

si flag_salida == 0 Entonces

Si iter >= max_iter Entonces
Escribir "El algoritmo no converge";
Escribir "Escoja otro valor inicial de xo, o aumente el numero de iteraciones";
Esperar Tecla;
Newton_Raphson();
Sino
Escribir "";
Escribir "Nos alegramos por que encontramos la raíz";
Escribir "La raíz aproximada es: ", x0;
Escribir "Con una toleracia de ", EPS1;
Escribir "Número de iteraciones = ", iter;
FinSi
finsi

FinFuncion
// funcion principal
Proceso Principal//()
Newton_Raphson();
FinProceso

También pienso agregarle al código anterior, que se repita n veces según el numero de raíces y multiplicidades y soporte de raíces complejas (QUIEN ME AYUDA)

gracias

Jaime
 

[ingmarov]

Hola amigos comparto lo que tengo del programa de raices de un polinomio:

No le he puesto comentarios, lo he hecho en python 3.2 y aún no he agregado la parte de Newton-Raphson. He dejado momentaneamente de avanzar con él, pero localiza bien las raices del polinomio y de su derivada. (después agregaré comentarios al código)
Hae falta afinar algunas cosas
Aqui el código.

Código: [Seleccionar]

#! /usr/bin/python3.2
def lecoef(n):
i=0
a=[1.1]
print("introdusca los coeficientes del polinomio ordenado")
a[0]=float(input("coeficiente 1: "))
while i<n:
a=a+[float(input("coeficiente: "))]
i+=1
return a
def evaluadora(c,m,v):
        acum,i=0,0
        while i<m+1:
                acum+=c[i]*v**(m-i)
                i+=1
        return acum
def exploradora(poly,n):
        val1,val2,i,cont,c=20000.1,100000.1,0,0,[]
        val2=evaluadora(poly,n,-20.00001)
        falla="no tiene raices"
        while i!=400:
                val1=evaluadora(poly,n,-20.05+i/10)
                val2=evaluadora(poly,n,-19.945+i/10)
                if val1*val2<0 and i!=0:
                        c=c+[[-20.001+i/10,-19.85+i/10]]
                        cont+=1
                #print('para x= ', -20.05+i/10," y=", val1, "i=", i)
                i=i+1
                if cont==n:
                        i=400
        if cont!=0:
                return c
        else:
                return falla
def derivadora(pol,n):
        b,i=[1.1],1
        b[0]=n*pol[0]
        while i<n:
              b=b+[(n-i)*pol[i]]
              i+=1
        return b
parada,n="hola",1.1
while parada != "q":
    print("Bienvenido(a), este programa calcula las raices de un polinomio")
    llave=1
    while llave==1:
        n=float(input("Introdusca el grado del polinomio: "))
        if n==int(n):
            llave=2
        else :
            print("el grado debe ser un número entero")
    n=int(n)
    print("grado= ",n)
    a=lecoef(n)
    b=derivadora(a,n)
    c=exploradora(a,n)
    cd=exploradora(b,n-1)
    print("ubicación de las raices del polinomio",c)
    print("ubicación de las raices de la derivada",cd)
    parada=input("Ingrese \"q\" para salir u otro caracter para continuar: ")


Como dije aún no lo termino, pero publico esto para que sepan que estoy avanzando.

Saludos

[luis]

me parece que no es buena idea el que poco código haga muchas cosas. voy a señalar dos casos que veo en el último código que manda ingmarov. sin ánimo de indicar qué hacer, pero creyendo que lo que sugiero es mejor.

un caso típico de recarga es cuando pone

Código: [Seleccionar]

i += 1
aunque es algo diferente, se puede ver como una abreviatura de

Código: [Seleccionar]

i = i + 1
aparecen dos preguntas: si es diferente y no conozco la diferencia, ¿cuál es la ventaja de incorporar una sintaxis diferente? y si la sé, ¿es tan importante esa diferencia en el problema concreto que estoy resolviendo? y aviso desde ya que entiendo inadecuadas las dos respuestas siguientes para su uso:

*. lo hago por que se puede. pues no es adecuada... también podría escribir

Código: [Seleccionar]

i = i + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 , y claramente eso no es razonable
*. lo hago porque es más eficiente. pues tampoco, porque la eficiencia que se gana es demasiado poca para justificar el agregado de esa construcción, especialmente cuando el objetivo del ejercicio es describir con claridad el algoritmo y no escribir de forma complicada para ganar muy poca cosa en términos de eficiencia absoluta (y nada, en términos de costos)

un caso que mezcla más cosas, y es a mi gusto menos deseable aún, es

Código: [Seleccionar]

a=a+[float(input("coeficiente: "))]

(o más engorroso aún ...

Código: [Seleccionar]

a += [float(input("coeficiente: "))])

la expresión

Código: [Seleccionar]

[float(input("coeficiente: "))] denota una lista de un solo elemento; un real que ha sido leído de pantalla. es conveniente separar la obtención de los datos de su uso. creo que un mejor código sería

Código: [Seleccionar]

r = float(input("coeficiente: "))
a = a + [r]

igualmente, prefiero siempre escribir

Código: [Seleccionar]

r = leerFloat("coeficiente: ")

con algo como

Código: [Seleccionar]

def leerFloat(s):
   return float (input (s))

de forma que si quiero trabajar el tema del ingreso de datos con errores lo puedo separar de la parte más matemática del problema.

finalmente, usaría las operaciones propias que tiene python para el manejo de listas. en este caso, mi fragmento diría

Código: [Seleccionar]

r = leerFloat("coeficiente: "))
a.append (r)

salduos

luis

[ingmarov]

Gracias luis por revisar y por las sugerencias. La razón por la que no he terminado el programa es porque reconozco que necesito aprender un poco más sobre python, para poder optimizar el programa y por eso me tardaré un poco más, además hay otros detalles que debo ajustar.

Spoiler

me parece que no es buena idea el que poco código haga muchas cosas. voy a señalar dos casos que veo en el último código que manda ingmarov. sin ánimo de indicar qué hacer, pero creyendo que lo que sugiero es mejor.

un caso típico de recarga es cuando pone

Código: [Seleccionar]

i += 1
aunque es algo diferente, se puede ver como una abreviatura de

Código: [Seleccionar]

i = i + 1
aparecen dos preguntas: si es diferente y no conozco la diferencia, ¿cuál es la ventaja de incorporar una sintaxis diferente? y si la sé, ¿es tan importante esa diferencia en el problema concreto que estoy resolviendo? y aviso desde ya que entiendo inadecuadas las dos respuestas siguientes para su uso:

*. lo hago por que se puede. pues no es adecuada... también podría escribir

Código: [Seleccionar]

i = i + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 , y claramente eso no es razonable
*. lo hago porque es más eficiente. pues tampoco, porque la eficiencia que se gana es demasiado poca para justificar el agregado de esa construcción, especialmente cuando el objetivo del ejercicio es describir con claridad el algoritmo y no escribir de forma complicada para ganar muy poca cosa en términos de eficiencia absoluta (y nada, en términos de costos)

un caso que mezcla más cosas, y es a mi gusto menos deseable aún, es

Código: [Seleccionar]

a=a+[float(input("coeficiente: "))]

(o más engorroso aún ...

Código: [Seleccionar]

a += [float(input("coeficiente: "))])

la expresión

Código: [Seleccionar]

[float(input("coeficiente: "))] denota una lista de un solo elemento; un real que ha sido leído de pantalla. es conveniente separar la obtención de los datos de su uso. creo que un mejor código sería

Código: [Seleccionar]

r = float(input("coeficiente: "))
a = a + [r]

igualmente, prefiero siempre escribir

Código: [Seleccionar]

r = leerFloat("coeficiente: ")

con algo como

Código: [Seleccionar]

def leerFloat(s):
   return float (input (s))

de forma que si quiero trabajar el tema del ingreso de datos con errores lo puedo separar de la parte más matemática del problema.

finalmente, usaría las operaciones propias que tiene python para el manejo de listas. en este caso, mi fragmento diría

Código: [Seleccionar]

r = leerFloat("coeficiente: "))
a.append (r)

salduos

luis

[cerrar]

Saludos

[ingmarov]

Hola compsystems!

Si la derivada se hace cero, entonces prueba encontrar los ceros de la derivada y evalúa la función en los ceros de sus derivadas n-ésimas. si el polinomio se hace cero en esos valores almacénalo para escribirlo como una raiz del polinomio.
Todavía el programa no da la raiz exacta, y debes introducir muchos datos. Intenta definir la tolerancia y el numero de iteraciones dentro del programa.

Spoiler

Listo Newton_Raphson, hay que pulir ciertos detalles de presentación, pero funciona, por favor lo prueban, lo optimizan y me comentan sobre su funcionamiento, el código esta echo de tal manera que muestra los pasos de la ejecución para hacerlo mas didáctico, estas sentencias se pueden eliminar.

He visto muchos códigos de Newton_Raphson en la red pero todos cometen un grave error, no chequean si la derivada retorna cero, creando una indeterminación, por ende el programa termina abruptamente, ademas mi codigo si no converge llama nuevamente a la función principal

Código: [Seleccionar]

// versión 1.0.0 ultima edicion 28/Oct/2014
// By  ingmarov and  JAIMEZA aka (compsystems) www.jaimeza.org 
// Para ejecutar este codigo use PSEINT http://pseint.sourceforge.net

// http://es.wikipedia.org/wiki/M%C3%A9todo_de_Newton
// [youtube]opLpVhq4Vjo[/youtube]
// ejempo  1*x^3-6*x^2+11*x-6*x^0 polinomio de grado 3, tiene 4 coeficientes visto en forma vectorial o de arreglo como [ 1, -6, 11, -6 ]
// raices {1,2,3}

// funcion auxiliar
funcion valor_retorno = evalPolinomio( copia_Pol, orden_Pol, val_x )  // Esta función como su nombre lo indica evalúa un polinomio de orden n en el valor x
Definir valor_retorno, acumSum, polEval como real;
Definir k Como Enteros;

acumSum = 0; // valor inicial de la expresion a evaluar
Escribir " ";
Para k = 0 Hasta orden_Pol Con Paso 1 Hacer // segun el ejemplo si 1*x^3+6*x^2+11*x+6*x^0 entonces inicia ciclo entre 0 y 3
polEval = (copia_Pol[k+1]* (val_x)^(orden_Pol-k) );
//Imprimir polEval;
acumSum = acumSum + polEval;
//Imprimir "para k =" k, " Acumulado = ", acumSum;
// Ejemplo
// para k = 0 extrae el coeficente de la posicion 1 y lo multiplica por el valor de x^(3-0) => 1*x^3 y le suma el valor acumulado anterior
// para k = 1 extrae el coeficente de la posicion 2 y lo multiplica por el valor de x^(3-1) => x^2 y le suma el valor acumulado anterior
// para k = 2 extrae el coeficente de la posicion 3 y lo multiplica por el valor de x^(3-2) => x^1 y le suma el valor acumulado anterior
// para k = 3 extrae el coeficente de la posicion 4 y lo multiplica por el valor de x^(3-3) => x^0 y le suma el valor acumulado anterior
FinPara

valor_retorno = acumSum; // valor_retorno es la variable que contiene el valor de retorno cuando se invoca desde otra funcion o proceso
FinFuncion


// funcion auxiliar
funcion Newton_Raphson()

Dimension Pol[10]; // Se crean un arreglo para almacenar los coeficientes del polinomio (maximo 10 coeficientes)
Dimension derPol[9]; // Se crean un arreglo uno para almacenar los coeficientes de la derivada. (maximo 9 coeficientes)
Definir Pol, derPol Como Entero; // tipo de coeficientes enteros para el polinomio y derivada

Definir n Como Entero; // variable para el grado del poninomio
Definir i, ci Como Entero; // variables contadores

Escribir "Bienvenido!, esta aplicación le ayudará a localizar la raices de un polinomio p(x) usando el algoritmo de Newton-Raphson";
Escribir Sin Saltar "Escriba el grado del polinomio n= ";
Leer n;

Escribir "Escriba los coeficientes del polinomio ordenado de forma canónica descendente";
// Ciclo Para: sirve para leer los coeficientes del polinoio y hallar su derivada.
Para ci = 1 Hasta n+1 Hacer // un polinomio de grado n, tiene n+1 coeficientes
Escribir Sin Saltar "ingrese coeficiente ", ci, " = ";
Leer Pol[ci]; // asignar por lectura de teclado cada coeficiente del polinomio
Si ci < n+1 Entonces // la derivada del x^0 es cero por eso no se incluye
derPol[ci] = Pol[ci]*( (n-ci)+1); // asigna el valor de la derivada en la formacion o arreglo delPol
FinSi
FinPara

Para ci = 1 Hasta n+1 Hacer // Esto no es necesario pero lo que hace es escibir el polinomio.
Si ci < n Entonces
Escribir Sinsaltar Pol[ci],"*x^", n-(ci-1), "+";
Sino
Si ci=n Entonces // para x^1
Escribir Sinsaltar Pol[ci],"*x+"; // extrae el valor del coeficiente de x^1
Sino
Escribir Pol[ci]; // para x^0
FinSi
FinSi
FinPara

Escribir "Derivada"; // Este escribe el polinomio correspondiente a la derivada.

Para ci = 1 Hasta n Hacer
Si ci < n-1 Entonces
Escribir Sinsaltar derPol[ci],"*x^", n-ci, "+";
Sino
Si ci=n-1 Entonces
Escribir Sinsaltar derPol[ci],"*x+";
Sino
Escribir derPol[ci];
FinSi
FinSi
FinPara

// Esta es la iteración propia del algoritmo de Newton_Raphson
Definir x0, x1, iter, flag_salida, p_x0, dp_x0 como real;
Definir test1, test2 como logico;


Definir EPS Como Real; // criterio de exactitud
//Escribir "criterio de convergencia EPS= " sin saltar;
//leer EPS; // margen de error;

Definir EPS1 Como Real; // criterio de exactitud
Escribir "criterio de exactitud, tolerancia EPS1= " sin saltar;
leer EPS1; // margen de error;

Definir max_iter Como Entero;
Escribir Sin Saltar "Ingrese el numero de iteraciones maximo permitido";
Leer max_iter;

Escribir "El polinomio tiene ", n , " raices";

Escribir "Ingrese el valor inicial, absisa cercana a la raíz x0 = " sin saltar;
Leer x0; // Este es el primer valor almacenado para comenzar la iteración


flag_salida = 0;
iter = 1; // iteracion inicial
p_x0 = evalPolinomio( Pol, n, x0 ); // Se evalúa al polinomio en el valor x0
Escribir "Pol(", x0, ")= ", p_x0; // imprime el valor resultante

test1 = abs(p_x0)>EPS1; // el valor de x0 no cumple el criterio de exactitud
escribir "abs(p_x0)>=EPS1: ", abs(p_x0), ">", EPS1, ": ", test1;
test2 = iter <= max_iter;
escribir "iter <= max_iter: ", iter "<=" max_iter, ": ", test2;

Mientras test2 y test1 Hacer
escribir " "
escribir "ITER #", iter;
escribir "x0=", x0;
test2 = iter <= max_iter;
escribir "iter <= max_iter: ", iter "<=" max_iter, ": ", test2;

p_x0 = evalPolinomio( Pol, n, x0 ); // Se evalúa al polinomio en el valor x0
Escribir "Pol(", x0, ")= ", p_x0; // imprime el valor resultante
test1 = abs(p_x0)>EPS1; // el valor de x0 no cumple el criterio de exactitud
escribir "abs(p_x0)=",abs(p_x0);
escribir "abs(p_x0)>=EPS1: ", abs(p_x0), ">", EPS1, ": ", test1;




dp_x0 = evalPolinomio( derPol, n-1, x0 ); // Se evalúa la derivada en el valor x0
Si dp_x0 == 0 Entonces
Escribir "la derivada evaluada en xo es cero, por lo tanto x1 se vuelve indefinido";
Escribir "Escoja otro valor inicial de xo";
iter = max_iter+1; // salida forzosa del loop
flag_salida = 1;
Sino
Escribir "DerPol(", x0, ")= ", dp_x0;
x1 = x0 - (p_x0/dp_x0); // Esta es la definición del algoritmo de Newton-Raphson
//EPS = abs((x1-x0)/x1);

iter = iter+1; // Esto incrementa el número de iteraciones hechas
escribir "x1=", x1;
x0 = x1; // actualiza valor inicial

    FinSi

FinMientras

si flag_salida == 0 Entonces

Si iter >= max_iter Entonces
Escribir "El algoritmo no converge";
Escribir "Escoja otro valor inicial de xo, o aumente el numero de iteraciones";
Esperar Tecla;
Newton_Raphson();
Sino
Escribir "";
Escribir "Nos alegramos por que encontramos la raíz";
Escribir "La raíz aproximada es: ", x0;
Escribir "Con una toleracia de ", EPS1;
Escribir "Número de iteraciones = ", iter;
FinSi
finsi

FinFuncion
// funcion principal
Proceso Principal//()
Newton_Raphson();
FinProceso

También pienso agregarle al código anterior, que se repita n veces según el numero de raíces y multiplicidades y soporte de raíces complejas (QUIEN ME AYUDA)

gracias

Jaime
 

[cerrar]

Mira en este hilo, allí utilicé Newton Raphson para calcular una raiz de un polinomio, quizás te sirva.[/s] Ignóralo

Ya he revisado

Funciona muy bien, le he puesto un número máximo de iteraciones=40 y una tolerancia de 0.0000001 como valores fijos.

El criterio para parar las iteraciones es cuando x1=x0, eso nos quitará de encima a la tolerancia. Bueno con esto tenemos el problema con la derivada=0, como ya he mencionado en ese caso debemos evaluar la función en los ceros de la derivada.

Aprendo mucho al ver la forma en que escribes los programas, muy ordenado, fácil de leer. Intentaré hacerlo de esa forma.

Hasta luego.

[luis]

sigo revisando...

pensando en mejorar el python, reescribo el primer programa

Código: [Seleccionar]

def lecoef(n):
i=0
a=[1.1]
print("introdusca los coeficientes del polinomio ordenado")
a[0]=float(input("coeficiente 1: "))
while i<n:
a=a+[float(input("coeficiente: "))]
i+=1
return a

escribes

Código: [Seleccionar]

a=[1.1] para tener un elemento en la lista de forma de poder realizar la asignación

Código: [Seleccionar]

a[0]=.... comienzo eliminando eso, y agregando la función append que ya comentara.

Código: [Seleccionar]

def lecoef(n):
i=0
a=[]
print("introdusca los coeficientes del polinomio ordenado")
while i<n:
                r = leerFloat ("coeficiente: ")
                a.append (r)
i+=1
return a

ahora, la única función que realiza la variable i es la de asegurarse que se lean n coeficientes. eso lo solucionamos empleando un for. ojalá pudieramos eliminar esa variable, pero no se cómo se podría hacer de forma sencilla.

última cosa... puse el print al principio; me parece mejor separar lo más posible la interacción entrada/salida con el aspecto más de programación del asunto.

Código: [Seleccionar]

def lecoef(n):
print("introdusca los coeficientes del polinomio ordenado")
a=[]
        for i in range (1+n):
                r = leerFloat ("coeficiente: ")
                a.append (r)
return a

saludos

luis

[ingmarov]

Nuevamente gracias luis, ya había pesado en utilizar la función range()

Pero hay muchos detalles que afinar.

Una aclaración es que el código que he compartido solo encuentra números entre los cuales el polinomio tiene un cero o raiz, lo hace revisando cuándo la función cambia de signo. En el algoritmo de Newton-Raphson utilizaré uno de estos números como valor inicial de la iteración.

Lo anterior tiene un problema, ya que no todos los polinomios cambian de signo en una raiz o cero. Por ejemplo:

\( \boxed{(x+1)^2=x^2+2x+1} \)   ó   \( \boxed{(x+3)^{\color{red}4}=x^4+12x^3+54x^2+108x+81} \) Corregido

Además la derivada de estos polinomios tiene raiz o cero en el mismo punto, lo cual es un problema para el algoritmo de Newton-Raphson.

Ya sé como solucionarlo, pero quiero aprender un poco más sobre python, para luego continuar con el programa.

Saludos

[luis]

hola

hoy quería comentar acerca de la función evaluadora.

lo primero tiene que ver con la forma en que evaluas el polinomio. resulta que en cada iteración calculas el mismo exponente. la idea es que la lista \( c_0, c_1, \dots, c_m \) codifica el polinomio \( c_0 + c_1 x + \dots + c_m x^m \). una forma más eficiente de realizar la evaluación consiste en sacar factor común: \( c_0 + x (c_1 + \dots + x c_m) \). puedes buscar en la wikipedia acerca de esto; se le llama algoritmo de Horner. de esa forma el exponente se calcula una única vez, de a pedacitos. adicionalmente, se evidencia la naturaleza recursiva del cómputo de los polinomios.

Código: [Seleccionar]

def evaluadora(c,m,v):
   out = c[0]
   if m > 0:
      out = out + v * evaluadora (c[1:], m-1, v)
   return out

dos cosas acerca de python. uno: la lista

Código: [Seleccionar]

c[1:] es como

Código: [Seleccionar]

c, salvo que comienza en el primer elemento. dos: siempre podemos volver más compacto un código, y no por eso mejorarlo (al menos desde el punto de vista de la claridad). por ejemplo...

Código: [Seleccionar]

def evaluadora(c,m,v):
   return c[0] + (0 if m>0 else (v * evaluadora (c[1:], m-1, v)))

otra forma, a mi juicio menos natural, habría sido implementar Horner iterativamente.

Código: [Seleccionar]

def evaluadora(c,m,v):
   acum, i = c[m], m-1
   while i >= 0:
      acum = c[i] + v * acum
      i = i - 1
   return acum

(ojo... como siempre, no revisé que funcionara... escribo los programas sin ejecutar)

saludos

luis

[ingmarov]

Spoiler

hola

hoy quería comentar acerca de la función evaluadora.

lo primero tiene que ver con la forma en que evaluas el polinomio. resulta que en cada iteración calculas el mismo exponente. la idea es que la lista \( c_0, c_1, \dots, c_m \) codifica el polinomio \( c_0 + c_1 x + \dots + c_m x^m \). una forma más eficiente de realizar la evaluación consiste en sacar factor común: \( c_0 + x (c_1 + \dots + x c_m) \). puedes buscar en la wikipedia acerca de esto; se le llama algoritmo de Horner. de esa forma el exponente se calcula una única vez, de a pedacitos. adicionalmente, se evidencia la naturaleza recursiva del cómputo de los polinomios.

Código: [Seleccionar]

def evaluadora(c,m,v):
   out = c[0]
   if m > 0:
      out = out + v * evaluadora (c[1:], m-1, v)
   return out

dos cosas acerca de python. uno: la lista

Código: [Seleccionar]

c[1:] es como

Código: [Seleccionar]

c, salvo que comienza en el primer elemento. dos: siempre podemos volver más compacto un código, y no por eso mejorarlo (al menos desde el punto de vista de la claridad). por ejemplo...

Código: [Seleccionar]

def evaluadora(c,m,v):
   return c[0] + (0 if m>0 else (v * evaluadora (c[1:], m-1, v)))

otra forma, a mi juicio menos natural, habría sido implementar Horner iterativamente.

Código: [Seleccionar]

def evaluadora(c,m,v):
   acum, i = c[m], m-1
   while i >= 0:
      acum = c[i] + v * acum
      i = i - 1
   return acum

(ojo... como siempre, no revisé que funcionara... escribo los programas sin ejecutar)

saludos

luis

[cerrar]

Hola luis

Comparto las modificaciones a las funciones que has comentado

Código: [Seleccionar]

def lecoef(n):
    a=[]
    print("introdusca los coeficientes del polinomio ordenado")
    for i in range(n+1):
                r=float(input("coeficiente: "))
                a.append(r)
    return a
def evaluadora(c,m,v):#algoritmo de horner, teorema del residuo
        acum=0
        for i in range(m+1):
            acum=acum*v+c[i]
        return acum

Todo funcionaba como lo había escrito, y todo funciona como está ahora. Me gusta más como está ahora.
La idea ahora es construir una matriz de derivadas del polinomio, para conocer el orden de las raíces y poder aplicar Newton-Raphson a las derivadas. Publicaré cuando haya cambiado algo importante.

Saludos