Programa de Python para calcular una ecuación polinomial

El siguiente artículo contiene programas para calcular una ecuación polinomial dado que los coeficientes del polinomio se almacenan en una Lista.

Ejemplos:

# Evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3
Input: poly[] = {2, -6, 2, -1}, x = 3
Output: 5

# Evaluate value of 2x3 + 3x + 1 for x = 2
Input: poly[] = {2, 0, 3, 1}, x = 2
Output: 23

# Evaluate value of 2x + 5 for x = 5
Input: poly[] = {2, 5}, x = 5
Output: 15

La ecuación será del tipo:

Se nos proporcionará el valor de la variable y tenemos que calcular el valor del polinomio en ese punto. Para ello tenemos dos enfoques.

Acercarse

• Método ingenuo: usar for loop para calcular el valor.
• Método optimizado: uso del método de Horner para calcular el valor.

Método ingenuo:

En este enfoque, se seguirá la siguiente metodología. Este es el enfoque más ingenuo para hacer tales preguntas.

• El primer coeficiente c _n se multiplicará por x ⁿ
• Entonces el coeficiente c _n-1 se multiplicará por x ^n-1
• Los resultados producidos en los dos pasos anteriores se sumarán
• Esto continuará hasta que todos los coeficientes estén cubiertos.

Ejemplo:

# 2x3 - 6x2 + 2x - 1 for x = 3
poly = [2, -6, 2, -1]
x = 3
n = len(poly)
 
# Declaring the result
result = 0
 
# Running a for loop to traverse through the list
for i in range(n):
 
    # Declaring the variable Sum
    Sum = poly[i]
 
    # Running a for loop to multiply x (n-i-1)
    # times to the current coefficient
    for j in range(n - i - 1):
        Sum = Sum * x
 
    # Adding the sum to the result
    result = result + Sum
 
# Printing the result
print(result)

Producción:

5

Complejidad temporal: O(n ² )

Método optimizado:

El método de Horner se puede utilizar para evaluar polinomios en tiempo O(n). Para comprender el método, consideremos el ejemplo de 2x ³ – 6x ² + 2x – 1. El polinomio se puede evaluar como ((2x – 6)x + 2)x – 1. La idea es inicializar el resultado como el coeficiente de x _n que es 2 en este caso, multiplique repetidamente el resultado con x y agregue el siguiente coeficiente al resultado. Finalmente, devuelva el resultado. 

# + poly[1]x(n-2) + .. + poly[n-1]
def horner(poly, n, x):
 
    # Initialize result
    result = poly[0]
 
    # Evaluate value of polynomial
    # using Horner's method
    for i in range(1, n):
 
        result = result*x + poly[i]
 
    return result
 
# Driver program to
# test above function.
 
 
# Let us evaluate value of
# 2x3 - 6x2 + 2x - 1 for x = 3
poly = [2, -6, 2, -1]
x = 3
n = len(poly)
 
print("Value of polynomial is:", horner(poly, n, x))

Producción:

Value of polynomial is: 5

Complejidad de tiempo: O(n)