• Author / Uploaded
• Rommel Coello

Citation preview

Universidad de Cuenca Facultad de Ingeniería Escuela de Ingeniería Civil Materia: Métodos Numéricos

Elaborado por: Rodrigo Guerrero Coronel

Profesor: Ing. Lenin Campozano MSc.

Fecha: Abril 08/2015 Cuenca – Ecuador

1.- Introducción. El Presente informe pretende dar a conocer el funcionamiento del método de Newton-Horner (utilizado para hallar ceros de funciones polinomiales), para ello será necesario una breve explicación del algoritmo de Horner (división sintética).

Descripción del Informe: Se comienza con una explicación del algoritmo de Horner para posteriormente explicar el método de Newton-Horner, se verán los códigos utilizados y la aplicación de los mismos en 3 ejercicios.

Objetivos: -Aprender el funcionamiento del método Newton-Horner utilizado para hallar ceros de funciones polinomiales. -Poder interpretar los algoritmos que utilizan estos métodos programándolos en MATLAB. -Lograr aplicar correctamente el algoritmo.

2.- Desarrollo. Ceros de Funciones Algoritmo de Horner: >> Es un algoritmo para evaluar de forma eficiente funciones polinómicas de una forma monomial (que dependa de una sola variable). Dado el polinomio: 𝑝(𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + 𝑎3 𝑥 3 + ⋯ + 𝑎𝑛 𝑥 𝑛 , donde 𝑎0, 𝑎1, … 𝑎𝑛 son números reales, queremos evaluar el polinomio a un valor específico de 𝑥 , digamos 𝑥0 . Para llevar a cabo el procedimiento, definimos una nueva secuencia de constantes como se muestra a continuación: 𝑏𝑛 = 𝑎𝑛 𝑏𝑛−1 = 𝑎𝑛−1 + 𝑏𝑛 𝑥0 ⋮ 𝑏0 = 𝑏𝑛 𝑎0 + 𝑏1 𝑥0 Entonces 𝑏0 es el valor de 𝑝(𝑥0 ). Para ver cómo funciona esto, nótese que el polinomio puede escribirse de la forma 𝑝(𝑥) = 𝑎0 + 𝑥(𝑎1 + 𝑥(𝑎2 + ⋯ 𝑥(𝑎𝑛−1 + 𝑎𝑛 𝑥) + ⋯ ))

Después, sustituyendo iterativamente la 𝑏𝑖 en la expresión, 𝑝(𝑥0 ) = 𝑎0 + 𝑥0 (𝑎1 + 𝑥0 (𝑎2 + ⋯ 𝑥0 (𝑎𝑛−1 + 𝑏𝑛 𝑥0 ) + ⋯ )) 𝑝(𝑥0 ) = 𝑎0 + 𝑥0 (𝑎1 + 𝑥0 (𝑎2 + ⋯ 𝑥0 (𝑏𝑛−1 ) + ⋯ )) ⋮ 𝑝(𝑥0 ) = 𝑎0 + 𝑥0 (𝑏1 ) 𝑝(𝑥0 ) = 𝑏0

Este método permite evaluar efectivamente el polinomio 𝑝𝑛 en un punto 𝑧 usando el siguiente algoritmo de división sintética. 𝑏𝑛 = 𝑎𝑛 𝑏𝑘 = 𝑎𝑘 + 𝑧 ∗ 𝑏𝑘+1

De este modo, dividiendo un polinomio 𝑝𝑛 ∈ 𝑃𝑛 para 𝑥 − 𝑧 se deduce de que: 𝑝𝑛 (𝑥) = 𝑏0 + (𝑥 − 𝑧)𝑞𝑛−1 (𝑥; 𝑧), habiendo denotado por 𝑞𝑛−1 el cociente y por 𝑏0 el resto de la división. Si 𝑧 es una raíz de 𝑝𝑛 , entonces tenemos 𝑏0 = 𝑝𝑛 (𝑧) = 0 y por consiguiente

𝑝𝑛 (𝑥) = (𝑥 − 𝑧)𝑞𝑛−1 (𝑥; 𝑧). En este caso la ecuación algebraica 𝑞𝑛−1 (𝑥; 𝑧) = 0 proporciona las 𝑛 − 1 raíces restantes de 𝑝𝑛 (𝑥). Esta observación sugiere adoptar el siguiente criterio de Deflación para calcular todas las raíces de 𝑝𝑛 : Para 𝑚 = 𝑛, 𝑛 − 1, . . . , 1: 1. Hallar una raíz 𝑟𝑚 de pm con un método de aproximación apropiado; 2. Calcular 𝑞𝑚−1 (𝑥; 𝑟𝑚 ) utilizando el algoritmo de división sintética (habiendo definido 𝑧 = 𝑟𝑚 ); 3. Poner 𝑝𝑚−1 = 𝑞𝑚−1 . Eficiencia del algoritmo Horner: La evaluación usando la forma monomial del polinomio de grado-n requiere al menos 𝑛 sumas y (𝑛2 + 𝑛)/2 multiplicaciones, si las potencias se calculan mediante la repetición de multiplicaciones. El algoritmo de Horner sólo requiere n sumas y n multiplicaciones. (Minimizar el número de multiplicaciones es lo más deseable porque necesitan mucha carga computacional y son inestables comparadas con la suma). Se han demostrado que el algoritmo de Horner es óptimo, de modo que cualquier algoritmo que se use para evaluar un polinomio requerirá como mínimo el mismo número de operaciones.

>>Código utilizado en MATLAB para algoritmo de Horner: function [y,b] = horner(coeficientes,z) %Algoritmo de Horner (division sintetica). n = length(coeficientes)-1; %Nos da el nuevo grado del polinomio b = zeros(n+1,1); %Crea una matriz de nx1 donde se guardaran los nuevos coeficientes b(1) = coeficientes(1); for j=2:n+1 b(j) = coeficientes(j)+b(j-1)*z; %Calcula y guarda los coeficiente del nuevo polinomio o del polinomio asociado dependiendo cual sea el caso end y = b(n+1); %Nos devuelve el coeficiente b0 b = b(1:end-1) %Devuelve los coeficientes del polinomio o el polinomio asociado dependiendo cual sea el caso return %La función devuelve el coeficiente b0 y un vector con los nuevos coeficientes

>>Evaluar la función 𝑝(𝑥) = 2𝑥 2 − 5𝑥 + 6 𝑒𝑛 𝑥 = 2 utilizando el algoritmo de Horner.

Método de Newton-Horner: Como su nombre sugiere, el método de Newton-Horner implementa el procedimiento de deflación utilizando el método de Newton para calcular las raíces 𝑟𝑚 . La ventaja reside en el hecho de que la implementación del método de Newton explota convenientemente el algoritmo de Horner. En realidad, si 𝑞𝑛−1 es el polinomio asociado a 𝑝𝑛 , puesto que 𝑝′ 𝑛 (𝑥) = 𝑞𝑛−1 (𝑥; 𝑧) + (𝑥 − 𝑧)𝑞 ′ 𝑛−1 (𝑥; 𝑧), se tiene 𝑝′𝑛 (𝑧) = 𝑞𝑛−1 (𝑧; 𝑧). Gracias a esta identidad, el método de Newton-Horner para la aproximación de una raíz (real o compleja) 𝑟𝑗 de 𝑝𝑛 (𝑗 = 1, . . . , 𝑛) toma la siguiente forma: dada una (0)

estimación inicial 𝑟𝑗

de la raíz, calcular para cada 𝑘 ≥ 0 y hasta la convergencia

Ahora utilizamos la técnica de deflación, explotando el hecho de que 𝑝𝑛 (𝑥) = (𝑥 − 𝑟𝑗 )𝑝𝑛−1 (𝑥). Entonces procedemos a la aproximación de un cero de 𝑝𝑛−1 y así sucesivamente hasta que sean procesadas todas las raíces de 𝑝𝑛 .Nótese que, cuando 𝑟 𝑗 ∈ C , es necesario realizar el cálculo en aritmética compleja tomando (0)

𝑟𝑗

con parte imaginaria no nula. Caso contrario, el método de Newton-Horner (𝑘)

generaría una sucesión 𝑟𝑗

de números reales.

function [n_raices,n_errores,n_iteraciones]= newtonhorner(coeficientes,x0 ,tolerancia,iter_max) %Metodo de Newton-Horner %newtonhorner(Vector con los coeficientes del Polinomio,Valor inicial,Tolerancia,# iteraciones maxima) %Dado un valor inicial el metodo se detiene para cada raiz encontrada %despues de el numero de iteraciones maxima o despues de que el error (diferencia entre dos iteraciones consecutivas) sea %menor que la tolerancia if nargin==2 %Si el numero de argumentos es 2, se da 2 argumentos por defecto para la funcion tolerancia=1.e-04; iter_max = 100; elseif nargin==3 %Si el numero de argumentos es 3, completa 1 argumento por defecto iter_max=100; end %Caso Contrario trabaja con los 4 argumentos de la funcion dados n=length(coeficientes)-1; %Nos da el numero de raices a calcular n_iteraciones=zeros(n,1); %Crea una matriz de 5x1 donde se guardaran el numero de iteraciones de cada raiz calculada n_raices = zeros(n,1); %Crea una matriz de 5x1 donde se guardaran las futuras raices n_errores=zeros(n,1); %Crea una matriz de 5x1 donde se guardaran los errores de cada raiz %Iteraciones de Newton for k=1:n error=tolerancia+1; x=x0; n_iter=0; %Contador de iteaciones encerado while n_iter= tolerancia [pz,b] = horner(coeficientes,x); [dpz ,b] = horner(b,x); xnew=x-(pz/dpz); %Calcula la nueva raiz error=abs(xnew -x); %Calculo del error n_iter=n_iter + 1; x=xnew; end if n_iter>=iter_max fprintf('El metodo no converge para el numero maximo de iteraciones\n'); end %Deflacion [pz,coeficientes] = horner(coeficientes,x); n_raices(k)=x; %Guarda las raices calculadas n_iteraciones(k)=n_iter; %Guarda el numero de iteraciones realizadas al calcular cada raiz n_errores(k)=error; %Guarda los errores end return %La función Devuelve las raíces,los errores y las iteraciones

>>Hallar las raíces del siguiente polinomio 𝑝(𝑥) = 4𝑥 2 − 5𝑥 +1 con un 𝑥0 = 2 utilizando el método de Newton-Horner.

>>Hallar las raíces del siguiente polinomio 𝑝(𝑥) = 6𝑥 6 + 5𝑥 5 −14𝑥 4 + 𝑥 3 + 2𝑥 2 con un 𝑥0 = 2 utilizando el método de Newton-Horner.

Conclusiones: -Una de las ventajas de este método es que puede operar con números imaginarios (complejos). -La pérdida de precisión es bastante evidente para el cálculo de la raíz múltiple, y se hace menos relevante a medida que la multiplicidad crece. -El método de Newton explota al máximo el algoritmo de Horner para el cálculo de raíces de funciones polinomiales.