Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NO-LINEAL EN UNA VARIABLE 57
para xca f(x)=(x -ath(x) con lim h(x) c O X--+ Cl
Si m - 1 la raiz se dice simple V
~_JEqI~l1i3J~L~90na la m_ultiplicidad de una ra iz de una ecuacion f(x) = 0 can las
derivadas de la funci6nl
_tiene su dos rimeras deriYa~ntinuas enLin
cUOaIaiz simple de la ecuaci6n
Demostraci6n~ Supongamos que a es una raiz simple de la ecuacion f(x) = O Entonces de
acuerdo can la definicion 23 f(a) = 0 y
para x ca f(x) =(x -a)h(x) can limh(x) c O x--+a
Derivando a ambos lados de la expresion anterior can respecto a x obtenemos
f ( x) = h( x) + ( x - a )h ( x)
Como lim f (x) = lim h(x) c 0 X4 a X4cr
Y f es continua en a (par hipotesis) entonces lim f(x) = f(a ) c 0 X- gtCl I I l ) ~ I I Ln -
Reclprocamente supongamos que f( a) = 0 y f(a) c O Hacienda un desarrollo en serie de
Taylor para f alrededor de a obtenemos
f(x) = f(a) + f(a )(x _ a) + f (~ ) (x - a )2 ___ 2 o
= (x-a)lf(a)+f(~)(xa ) l para algun ~ entre x y a
Llamando a
h(x) = f (a ) + f (~ ) (xI )
tenemosque para xca f(x)=(x- a )h(x) con limh(x)=f(a ) c O V X--+Cl
En general se tiene el siguiente teorema cuya demostraci6n es completamente analoga a la del teorema 22 anterior
Capitulo 2 SOLUCION NUMERICA DE58 METODOS NUMERICOS
Teorema 23~2ongamos que la funci6n f tiene sus primeras m + 1 derivadas continuas~~ yuJltQtervalo ab que conJ~ne a un numercY~1 ~ntonces s una rafz de multiplicidad m_de
laecuacj6n f(x)=O siys610si O=f(a)=f(a)=f(a)= =f(m-11(a) y f (m1(a)otO V - Jo
Volviendo aJ metodo de Newton-Raphsonla- hip_6tQ$~e1 para aplicar este metodo es
que ~9a sus primeras dosJIerl ladas ~QntiIlua en un intervalo lab] con f( x)ot-0 para--
todo x E[ab] y exista ~ ~ [a b tal que f(a) = O
De acuerdo con la hip6tesis general y el teorema 22 ~a)ot 0 entonces la raiz _~
simple es decir de multiplicidad 1 shy
L_a_sect siguientes graficas muestran diversas posibilidades de multiplicidad para una raiz a de
una ecuaci6n f( x) =0
Presentacion usando polinomiOi d
y = f(x) general y sea a una aproximaci6n de II y = f(x)
1 Consideremos el polinomio dez~~ xx
FIGURA 213a FIGURA213b FIGURA 213c (Raiz simple) (Raiz multiple par) (Raiz multiple irnpar)
Hay varias formas de presentar el metodo de Newton-Raphson dos de elias son
Presentacion grcifica Supongamos que f satisface la hip6tesis general y escojamos
Xo E[ab] cercano ala raiz a
L~ primera aproximaci6n x en el metodo de Newton-Raphson es el punto en el cual la obtenemos
recta L tangente a la grafica de f en el punto (xo f( xo)) corta al eje x (ver la FIGURA 214)
y despejando a De acuerdo con esto se liene que
( ) f(xo) - 0f Xo = -------Xo - x
yentonces
En general para cad a n ~ 1 x = X 1 - f( Xn-Oscisa del punto de intersecci6n de la n n- f(xn_) r - -_
recta tangent~ltJa grafica de fen el punta xn-1 f(Xn_)) ~on el eje x
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NO-LINEAL EN UNA VARIABLE 59
y
Xo
FIGURA 214
Presentaci6n usando polinomios de Taylor Supongamos que f satisface la hip6tesis
general y sea a una aproximaci6n de a tal que Ia - a I es pequeno
Consideremos el polinomio de Taylor de primer grado para f alrededor de a ~ bull
f(X)=f(O)+f(O)(X _O)+f()(X-2~)2 x y 0con entre
En particular para x = a tenemos
O=f(a)= f(a)+ f (a)(a-a)+ f (~)(a-2~ r ~ a y aentre
(a-amiddotrSuponiendo que el termino f( ~) 2 es despreciable (recuerde que f es acotada)
obtenemos
o f( a bull ) + f bull (a )( a - a bull )
y despejando a lIegamos a
f(a) y a - -(- ) es por 10 general una mejor aproximaci6n de a que a
f a
EI metodo de Newton-Raphson para encontrar una raiz a de una ecuaci6n f(x) = 0
consiste en generar una sucesi6n xn n definida mediante la f6rmula de iteraci6n
60 METODOS NUMERIC OS
y escogiendo Xo cercano a a
De acuerdo con la f6rmula anterior se ve claramente que el metodo de Newton-Raphson es un caso especial del metodo de iteraci6n de Punto Fijo cuando se toma como funci6n de iteraci6n la funci6n
g(x) = x _ f(x) f( x)
La escogencia del punto inicial Xo es muy importante para la convergencia del metodo de
4x - 7Newton-Raphson Como ejemplo consideremos la funci6n f x () = -- que tiene un cero
x - 2 7
en a = - = 175 Como 4
4(x-2)-(4X-7) - 1 2 f(x) = (X_2)2 = (X_2)2 fll(x) = (X_2)3
entonces es continuamente diferenciable dos veces en todo intervalo que no contenga a X = 2
La sucesi6n generada por el metodo de Newton-Raphson para la funci6n dada es
4x _ 7 n 1 shy
xn- 1rn = xn_ - - 2 xn- 1 2-1
La grafica de f(x) = 4x - 7 es como se muestra en la FIGURA 215 x - 2
Se puede ver que si en la f6rmula para xn (en el metodo de Newton-Raphson) usamos
Xo =15 obtenemos x = 20 Y el metodo no puede continuarse
Si Xo E(152) el metodo converge Que pasa si Xo middotE(015)
En las TABLAS 28 Y 29 se muestran los resultados obtenidos al aplicar el metodo de 4x - 7
Newton-Raphson a la funci6n f(x) = -- tomando como puntos iniciales Xo =165 Y x-2
Xo = 185 respectivamente y usando como criterio de aproximaci6n If(xn) 1lt 5 x 10-5 0
I xn - Ilt 5 x 10 - 5 xn-1
)
Capitulo 2 SOLUCION NUMERICA DE
y
n
Capitulo 2 SOLUCICN NUMERICA DE UNA ECUACICN NO-LINEAL EN UNA VARIABLE 61
y
4 -------------shy
x
FIGURA 215
n Xn f( Xn) I Xn - Xn- 1 I
0 165 114 1 179 -761 I 14 2 17564 -105 j 336x10-1
3 1750163 -260 x1 0-3 6237 x 10-3
4 175 0 163 x 10-4
TABLA 28 Instrucci6n en DERIVE
NEWTON( f( x) x Xo N) aproXima las primeras N iteracion~s en Ie metodo de Newtonshy
Raphson aplicado a la funci6n f(x) tomando como aproximacion inicial xo Para el ejemplo
aproXime la expresi6n NEWTON( 4x shy 7 x 165 4) 0 x-2
n
0 185 -266 1 179 -761 60 x 10-2
2 17564 -105 336 x 10-1
3 1750163 -260 x10-r 6237 x 10--3
4 175 0 163 x 10-4
TABLA 29
Para la misma funci6n f si usamos el metodo de Newton-Raphson con Xo = to se obtienen
hasta la quinta iteraci6n los resultados que se muestran en la TABLA 210 siguiente +
Capitulo 2 SOLUCION NUMERICA DE UNA62 METODOS NUMERICOS
I n
0 I
xn
10 I
f( xn )
30 I I xn - xn-1I I
1 2
40 220
45 405
30 180
3 16420 4000609 16200 4
5 1076168 x 107
4632550 x 1014 4000000
4000000 10760038 x 107
46325498 x1014
TABLA 210
EI siguiente teorema da condiciones suficientes no necesarias para la convergencia del metodo de Newton-Raphson aunque no da de manera explicita un intervalo donde se pueda escoger el punto inicial xo
Teorema 24 Sea f una funci6n continuamente diferenciable dos veces en un intervalo [ab]
que contiene un numero a Si f( a) = 0 y f ( a ) Q (a es rafz simple de la ecuaci6n
f( x) = 0 ) entonces existe 0gt 0 tal que la sucesi6n xnn c~
converge a a para cualquier Xo E [a - 0 a + 0]
Demostraci6n Haciendo
g(x) = x- f(x) f(x)
se demostrara que existe un 0 gt 0 tal que la funci6n 9 satisface las hip6tesis del teorema 21
(de Punto Fijo) en el intervalo [a - oa + 0]
En efecto
Como f (a)O y f es continua en [ab] existe 01gt 0 tal que f (x)O para todo
x E[a - o a + o d~[a b] Entonces 9 es continua en [a - 01 a +01] shy
Ahora
g(x) = 1- f (x)f (x- f(x)f (x) = [f (xW - [f ( x)t + f(x)f(x)
[f (x)t [f(x)t f(x)f ( x)
para xE[a - 01a + o1]
[f ( x)t
y como f es continuamente diferenciable dos veces en
[a -01a +01] porotrolado f(a)=O y f(a)tOas
f(a)f(a)
g(a) = [f(a)]2
Ahora como g es continua en [a - o1a + Sd y
tal que ~ g (x)IK lt 1 paratoda xe[a- tia+o]
Fijados K Y 8 falta demostrar que ~[a -oa +
Si x E [a - 8 a + 8] el teorema del valor meltfjO
ta ll que
f(a) (recuerde que g(a) = a - f(a) = a
Asf que Ig(x) - ex I~ 0 10 que signib
Luego g[a - 8 a + 0] -+ [a - Ba
consecuencia la sucesi6n Xnn
Nota Los crfterlol Newton-Rlphlon
de la sucesi6n n
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 63
y como f es continuamente diferenciable dos veces en [ab] entonces g es continua en
[a-8 1a+8 1 ] porotrolado f(a)= O y f (a) O asfque
g(a ) = f(a )f(~ ) = deg [f (a)]
Ahora como g es continua en [a - 81a + 8] Y g(a) = 0 entonces existe 8 con 0 lt8 lt 81
talgue Igl(x)J ~ K lt 1 paratoda x E[a-8a+8] (este 8 depende del Kescogido)
Fijados K Y 8 falta demostrar que 9([a - 8 a + 8]) ~ (a - 8 a + 8]
Si x E[a - 8a + 8] el teorema del valor medio aplicado a 9 implica que existe un ~ entre x y a
tal que
I g( x) - a I = I g(x) - g(a ) I = I g(~ ) II x - a I ~ KI x - a I lt I x - a I~ 8
(recuerde que g(a ) = a - ~~) = a )
Aslque I g(x)-a l~8 loquesignificaque g(x)E [a - 8a+8] paratodo x E[a - 8a + 8]
Luego g(a -oa+8]~(a-o a+o] satisface todas las hip6tesis del teorema 21 y en
consecuencia la sucesi6n xn n definida por
converge aacualquiera sea Xo E[a-oa+o] V
Nota Los criterios de aproximaclon que generalmente se utilizan ~n el metodo de Newton-Raphson son dado E gt 0 se toma como aproximaci6n de la ra iz a al termino xN
de la sucesi6n generada mediante la f6rmula de iteracion de Newton donde N es el menor
entero no-negativ~ tal que I f( xn) I lt E 0 Ixn - xn-1 Ilt E
Observe que si el metodo de Newton-Raphson converge como
entonces entre mas grande sea I f ( x) J en la vecindad de la raiz a mas rapida sera la
convergencia
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCION NUMERICA DE58 METODOS NUMERICOS
Teorema 23~2ongamos que la funci6n f tiene sus primeras m + 1 derivadas continuas~~ yuJltQtervalo ab que conJ~ne a un numercY~1 ~ntonces s una rafz de multiplicidad m_de
laecuacj6n f(x)=O siys610si O=f(a)=f(a)=f(a)= =f(m-11(a) y f (m1(a)otO V - Jo
Volviendo aJ metodo de Newton-Raphsonla- hip_6tQ$~e1 para aplicar este metodo es
que ~9a sus primeras dosJIerl ladas ~QntiIlua en un intervalo lab] con f( x)ot-0 para--
todo x E[ab] y exista ~ ~ [a b tal que f(a) = O
De acuerdo con la hip6tesis general y el teorema 22 ~a)ot 0 entonces la raiz _~
simple es decir de multiplicidad 1 shy
L_a_sect siguientes graficas muestran diversas posibilidades de multiplicidad para una raiz a de
una ecuaci6n f( x) =0
Presentacion usando polinomiOi d
y = f(x) general y sea a una aproximaci6n de II y = f(x)
1 Consideremos el polinomio dez~~ xx
FIGURA 213a FIGURA213b FIGURA 213c (Raiz simple) (Raiz multiple par) (Raiz multiple irnpar)
Hay varias formas de presentar el metodo de Newton-Raphson dos de elias son
Presentacion grcifica Supongamos que f satisface la hip6tesis general y escojamos
Xo E[ab] cercano ala raiz a
L~ primera aproximaci6n x en el metodo de Newton-Raphson es el punto en el cual la obtenemos
recta L tangente a la grafica de f en el punto (xo f( xo)) corta al eje x (ver la FIGURA 214)
y despejando a De acuerdo con esto se liene que
( ) f(xo) - 0f Xo = -------Xo - x
yentonces
En general para cad a n ~ 1 x = X 1 - f( Xn-Oscisa del punto de intersecci6n de la n n- f(xn_) r - -_
recta tangent~ltJa grafica de fen el punta xn-1 f(Xn_)) ~on el eje x
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NO-LINEAL EN UNA VARIABLE 59
y
Xo
FIGURA 214
Presentaci6n usando polinomios de Taylor Supongamos que f satisface la hip6tesis
general y sea a una aproximaci6n de a tal que Ia - a I es pequeno
Consideremos el polinomio de Taylor de primer grado para f alrededor de a ~ bull
f(X)=f(O)+f(O)(X _O)+f()(X-2~)2 x y 0con entre
En particular para x = a tenemos
O=f(a)= f(a)+ f (a)(a-a)+ f (~)(a-2~ r ~ a y aentre
(a-amiddotrSuponiendo que el termino f( ~) 2 es despreciable (recuerde que f es acotada)
obtenemos
o f( a bull ) + f bull (a )( a - a bull )
y despejando a lIegamos a
f(a) y a - -(- ) es por 10 general una mejor aproximaci6n de a que a
f a
EI metodo de Newton-Raphson para encontrar una raiz a de una ecuaci6n f(x) = 0
consiste en generar una sucesi6n xn n definida mediante la f6rmula de iteraci6n
60 METODOS NUMERIC OS
y escogiendo Xo cercano a a
De acuerdo con la f6rmula anterior se ve claramente que el metodo de Newton-Raphson es un caso especial del metodo de iteraci6n de Punto Fijo cuando se toma como funci6n de iteraci6n la funci6n
g(x) = x _ f(x) f( x)
La escogencia del punto inicial Xo es muy importante para la convergencia del metodo de
4x - 7Newton-Raphson Como ejemplo consideremos la funci6n f x () = -- que tiene un cero
x - 2 7
en a = - = 175 Como 4
4(x-2)-(4X-7) - 1 2 f(x) = (X_2)2 = (X_2)2 fll(x) = (X_2)3
entonces es continuamente diferenciable dos veces en todo intervalo que no contenga a X = 2
La sucesi6n generada por el metodo de Newton-Raphson para la funci6n dada es
4x _ 7 n 1 shy
xn- 1rn = xn_ - - 2 xn- 1 2-1
La grafica de f(x) = 4x - 7 es como se muestra en la FIGURA 215 x - 2
Se puede ver que si en la f6rmula para xn (en el metodo de Newton-Raphson) usamos
Xo =15 obtenemos x = 20 Y el metodo no puede continuarse
Si Xo E(152) el metodo converge Que pasa si Xo middotE(015)
En las TABLAS 28 Y 29 se muestran los resultados obtenidos al aplicar el metodo de 4x - 7
Newton-Raphson a la funci6n f(x) = -- tomando como puntos iniciales Xo =165 Y x-2
Xo = 185 respectivamente y usando como criterio de aproximaci6n If(xn) 1lt 5 x 10-5 0
I xn - Ilt 5 x 10 - 5 xn-1
)
Capitulo 2 SOLUCION NUMERICA DE
y
n
Capitulo 2 SOLUCICN NUMERICA DE UNA ECUACICN NO-LINEAL EN UNA VARIABLE 61
y
4 -------------shy
x
FIGURA 215
n Xn f( Xn) I Xn - Xn- 1 I
0 165 114 1 179 -761 I 14 2 17564 -105 j 336x10-1
3 1750163 -260 x1 0-3 6237 x 10-3
4 175 0 163 x 10-4
TABLA 28 Instrucci6n en DERIVE
NEWTON( f( x) x Xo N) aproXima las primeras N iteracion~s en Ie metodo de Newtonshy
Raphson aplicado a la funci6n f(x) tomando como aproximacion inicial xo Para el ejemplo
aproXime la expresi6n NEWTON( 4x shy 7 x 165 4) 0 x-2
n
0 185 -266 1 179 -761 60 x 10-2
2 17564 -105 336 x 10-1
3 1750163 -260 x10-r 6237 x 10--3
4 175 0 163 x 10-4
TABLA 29
Para la misma funci6n f si usamos el metodo de Newton-Raphson con Xo = to se obtienen
hasta la quinta iteraci6n los resultados que se muestran en la TABLA 210 siguiente +
Capitulo 2 SOLUCION NUMERICA DE UNA62 METODOS NUMERICOS
I n
0 I
xn
10 I
f( xn )
30 I I xn - xn-1I I
1 2
40 220
45 405
30 180
3 16420 4000609 16200 4
5 1076168 x 107
4632550 x 1014 4000000
4000000 10760038 x 107
46325498 x1014
TABLA 210
EI siguiente teorema da condiciones suficientes no necesarias para la convergencia del metodo de Newton-Raphson aunque no da de manera explicita un intervalo donde se pueda escoger el punto inicial xo
Teorema 24 Sea f una funci6n continuamente diferenciable dos veces en un intervalo [ab]
que contiene un numero a Si f( a) = 0 y f ( a ) Q (a es rafz simple de la ecuaci6n
f( x) = 0 ) entonces existe 0gt 0 tal que la sucesi6n xnn c~
converge a a para cualquier Xo E [a - 0 a + 0]
Demostraci6n Haciendo
g(x) = x- f(x) f(x)
se demostrara que existe un 0 gt 0 tal que la funci6n 9 satisface las hip6tesis del teorema 21
(de Punto Fijo) en el intervalo [a - oa + 0]
En efecto
Como f (a)O y f es continua en [ab] existe 01gt 0 tal que f (x)O para todo
x E[a - o a + o d~[a b] Entonces 9 es continua en [a - 01 a +01] shy
Ahora
g(x) = 1- f (x)f (x- f(x)f (x) = [f (xW - [f ( x)t + f(x)f(x)
[f (x)t [f(x)t f(x)f ( x)
para xE[a - 01a + o1]
[f ( x)t
y como f es continuamente diferenciable dos veces en
[a -01a +01] porotrolado f(a)=O y f(a)tOas
f(a)f(a)
g(a) = [f(a)]2
Ahora como g es continua en [a - o1a + Sd y
tal que ~ g (x)IK lt 1 paratoda xe[a- tia+o]
Fijados K Y 8 falta demostrar que ~[a -oa +
Si x E [a - 8 a + 8] el teorema del valor meltfjO
ta ll que
f(a) (recuerde que g(a) = a - f(a) = a
Asf que Ig(x) - ex I~ 0 10 que signib
Luego g[a - 8 a + 0] -+ [a - Ba
consecuencia la sucesi6n Xnn
Nota Los crfterlol Newton-Rlphlon
de la sucesi6n n
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 63
y como f es continuamente diferenciable dos veces en [ab] entonces g es continua en
[a-8 1a+8 1 ] porotrolado f(a)= O y f (a) O asfque
g(a ) = f(a )f(~ ) = deg [f (a)]
Ahora como g es continua en [a - 81a + 8] Y g(a) = 0 entonces existe 8 con 0 lt8 lt 81
talgue Igl(x)J ~ K lt 1 paratoda x E[a-8a+8] (este 8 depende del Kescogido)
Fijados K Y 8 falta demostrar que 9([a - 8 a + 8]) ~ (a - 8 a + 8]
Si x E[a - 8a + 8] el teorema del valor medio aplicado a 9 implica que existe un ~ entre x y a
tal que
I g( x) - a I = I g(x) - g(a ) I = I g(~ ) II x - a I ~ KI x - a I lt I x - a I~ 8
(recuerde que g(a ) = a - ~~) = a )
Aslque I g(x)-a l~8 loquesignificaque g(x)E [a - 8a+8] paratodo x E[a - 8a + 8]
Luego g(a -oa+8]~(a-o a+o] satisface todas las hip6tesis del teorema 21 y en
consecuencia la sucesi6n xn n definida por
converge aacualquiera sea Xo E[a-oa+o] V
Nota Los criterios de aproximaclon que generalmente se utilizan ~n el metodo de Newton-Raphson son dado E gt 0 se toma como aproximaci6n de la ra iz a al termino xN
de la sucesi6n generada mediante la f6rmula de iteracion de Newton donde N es el menor
entero no-negativ~ tal que I f( xn) I lt E 0 Ixn - xn-1 Ilt E
Observe que si el metodo de Newton-Raphson converge como
entonces entre mas grande sea I f ( x) J en la vecindad de la raiz a mas rapida sera la
convergencia
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NO-LINEAL EN UNA VARIABLE 59
y
Xo
FIGURA 214
Presentaci6n usando polinomios de Taylor Supongamos que f satisface la hip6tesis
general y sea a una aproximaci6n de a tal que Ia - a I es pequeno
Consideremos el polinomio de Taylor de primer grado para f alrededor de a ~ bull
f(X)=f(O)+f(O)(X _O)+f()(X-2~)2 x y 0con entre
En particular para x = a tenemos
O=f(a)= f(a)+ f (a)(a-a)+ f (~)(a-2~ r ~ a y aentre
(a-amiddotrSuponiendo que el termino f( ~) 2 es despreciable (recuerde que f es acotada)
obtenemos
o f( a bull ) + f bull (a )( a - a bull )
y despejando a lIegamos a
f(a) y a - -(- ) es por 10 general una mejor aproximaci6n de a que a
f a
EI metodo de Newton-Raphson para encontrar una raiz a de una ecuaci6n f(x) = 0
consiste en generar una sucesi6n xn n definida mediante la f6rmula de iteraci6n
60 METODOS NUMERIC OS
y escogiendo Xo cercano a a
De acuerdo con la f6rmula anterior se ve claramente que el metodo de Newton-Raphson es un caso especial del metodo de iteraci6n de Punto Fijo cuando se toma como funci6n de iteraci6n la funci6n
g(x) = x _ f(x) f( x)
La escogencia del punto inicial Xo es muy importante para la convergencia del metodo de
4x - 7Newton-Raphson Como ejemplo consideremos la funci6n f x () = -- que tiene un cero
x - 2 7
en a = - = 175 Como 4
4(x-2)-(4X-7) - 1 2 f(x) = (X_2)2 = (X_2)2 fll(x) = (X_2)3
entonces es continuamente diferenciable dos veces en todo intervalo que no contenga a X = 2
La sucesi6n generada por el metodo de Newton-Raphson para la funci6n dada es
4x _ 7 n 1 shy
xn- 1rn = xn_ - - 2 xn- 1 2-1
La grafica de f(x) = 4x - 7 es como se muestra en la FIGURA 215 x - 2
Se puede ver que si en la f6rmula para xn (en el metodo de Newton-Raphson) usamos
Xo =15 obtenemos x = 20 Y el metodo no puede continuarse
Si Xo E(152) el metodo converge Que pasa si Xo middotE(015)
En las TABLAS 28 Y 29 se muestran los resultados obtenidos al aplicar el metodo de 4x - 7
Newton-Raphson a la funci6n f(x) = -- tomando como puntos iniciales Xo =165 Y x-2
Xo = 185 respectivamente y usando como criterio de aproximaci6n If(xn) 1lt 5 x 10-5 0
I xn - Ilt 5 x 10 - 5 xn-1
)
Capitulo 2 SOLUCION NUMERICA DE
y
n
Capitulo 2 SOLUCICN NUMERICA DE UNA ECUACICN NO-LINEAL EN UNA VARIABLE 61
y
4 -------------shy
x
FIGURA 215
n Xn f( Xn) I Xn - Xn- 1 I
0 165 114 1 179 -761 I 14 2 17564 -105 j 336x10-1
3 1750163 -260 x1 0-3 6237 x 10-3
4 175 0 163 x 10-4
TABLA 28 Instrucci6n en DERIVE
NEWTON( f( x) x Xo N) aproXima las primeras N iteracion~s en Ie metodo de Newtonshy
Raphson aplicado a la funci6n f(x) tomando como aproximacion inicial xo Para el ejemplo
aproXime la expresi6n NEWTON( 4x shy 7 x 165 4) 0 x-2
n
0 185 -266 1 179 -761 60 x 10-2
2 17564 -105 336 x 10-1
3 1750163 -260 x10-r 6237 x 10--3
4 175 0 163 x 10-4
TABLA 29
Para la misma funci6n f si usamos el metodo de Newton-Raphson con Xo = to se obtienen
hasta la quinta iteraci6n los resultados que se muestran en la TABLA 210 siguiente +
Capitulo 2 SOLUCION NUMERICA DE UNA62 METODOS NUMERICOS
I n
0 I
xn
10 I
f( xn )
30 I I xn - xn-1I I
1 2
40 220
45 405
30 180
3 16420 4000609 16200 4
5 1076168 x 107
4632550 x 1014 4000000
4000000 10760038 x 107
46325498 x1014
TABLA 210
EI siguiente teorema da condiciones suficientes no necesarias para la convergencia del metodo de Newton-Raphson aunque no da de manera explicita un intervalo donde se pueda escoger el punto inicial xo
Teorema 24 Sea f una funci6n continuamente diferenciable dos veces en un intervalo [ab]
que contiene un numero a Si f( a) = 0 y f ( a ) Q (a es rafz simple de la ecuaci6n
f( x) = 0 ) entonces existe 0gt 0 tal que la sucesi6n xnn c~
converge a a para cualquier Xo E [a - 0 a + 0]
Demostraci6n Haciendo
g(x) = x- f(x) f(x)
se demostrara que existe un 0 gt 0 tal que la funci6n 9 satisface las hip6tesis del teorema 21
(de Punto Fijo) en el intervalo [a - oa + 0]
En efecto
Como f (a)O y f es continua en [ab] existe 01gt 0 tal que f (x)O para todo
x E[a - o a + o d~[a b] Entonces 9 es continua en [a - 01 a +01] shy
Ahora
g(x) = 1- f (x)f (x- f(x)f (x) = [f (xW - [f ( x)t + f(x)f(x)
[f (x)t [f(x)t f(x)f ( x)
para xE[a - 01a + o1]
[f ( x)t
y como f es continuamente diferenciable dos veces en
[a -01a +01] porotrolado f(a)=O y f(a)tOas
f(a)f(a)
g(a) = [f(a)]2
Ahora como g es continua en [a - o1a + Sd y
tal que ~ g (x)IK lt 1 paratoda xe[a- tia+o]
Fijados K Y 8 falta demostrar que ~[a -oa +
Si x E [a - 8 a + 8] el teorema del valor meltfjO
ta ll que
f(a) (recuerde que g(a) = a - f(a) = a
Asf que Ig(x) - ex I~ 0 10 que signib
Luego g[a - 8 a + 0] -+ [a - Ba
consecuencia la sucesi6n Xnn
Nota Los crfterlol Newton-Rlphlon
de la sucesi6n n
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 63
y como f es continuamente diferenciable dos veces en [ab] entonces g es continua en
[a-8 1a+8 1 ] porotrolado f(a)= O y f (a) O asfque
g(a ) = f(a )f(~ ) = deg [f (a)]
Ahora como g es continua en [a - 81a + 8] Y g(a) = 0 entonces existe 8 con 0 lt8 lt 81
talgue Igl(x)J ~ K lt 1 paratoda x E[a-8a+8] (este 8 depende del Kescogido)
Fijados K Y 8 falta demostrar que 9([a - 8 a + 8]) ~ (a - 8 a + 8]
Si x E[a - 8a + 8] el teorema del valor medio aplicado a 9 implica que existe un ~ entre x y a
tal que
I g( x) - a I = I g(x) - g(a ) I = I g(~ ) II x - a I ~ KI x - a I lt I x - a I~ 8
(recuerde que g(a ) = a - ~~) = a )
Aslque I g(x)-a l~8 loquesignificaque g(x)E [a - 8a+8] paratodo x E[a - 8a + 8]
Luego g(a -oa+8]~(a-o a+o] satisface todas las hip6tesis del teorema 21 y en
consecuencia la sucesi6n xn n definida por
converge aacualquiera sea Xo E[a-oa+o] V
Nota Los criterios de aproximaclon que generalmente se utilizan ~n el metodo de Newton-Raphson son dado E gt 0 se toma como aproximaci6n de la ra iz a al termino xN
de la sucesi6n generada mediante la f6rmula de iteracion de Newton donde N es el menor
entero no-negativ~ tal que I f( xn) I lt E 0 Ixn - xn-1 Ilt E
Observe que si el metodo de Newton-Raphson converge como
entonces entre mas grande sea I f ( x) J en la vecindad de la raiz a mas rapida sera la
convergencia
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
60 METODOS NUMERIC OS
y escogiendo Xo cercano a a
De acuerdo con la f6rmula anterior se ve claramente que el metodo de Newton-Raphson es un caso especial del metodo de iteraci6n de Punto Fijo cuando se toma como funci6n de iteraci6n la funci6n
g(x) = x _ f(x) f( x)
La escogencia del punto inicial Xo es muy importante para la convergencia del metodo de
4x - 7Newton-Raphson Como ejemplo consideremos la funci6n f x () = -- que tiene un cero
x - 2 7
en a = - = 175 Como 4
4(x-2)-(4X-7) - 1 2 f(x) = (X_2)2 = (X_2)2 fll(x) = (X_2)3
entonces es continuamente diferenciable dos veces en todo intervalo que no contenga a X = 2
La sucesi6n generada por el metodo de Newton-Raphson para la funci6n dada es
4x _ 7 n 1 shy
xn- 1rn = xn_ - - 2 xn- 1 2-1
La grafica de f(x) = 4x - 7 es como se muestra en la FIGURA 215 x - 2
Se puede ver que si en la f6rmula para xn (en el metodo de Newton-Raphson) usamos
Xo =15 obtenemos x = 20 Y el metodo no puede continuarse
Si Xo E(152) el metodo converge Que pasa si Xo middotE(015)
En las TABLAS 28 Y 29 se muestran los resultados obtenidos al aplicar el metodo de 4x - 7
Newton-Raphson a la funci6n f(x) = -- tomando como puntos iniciales Xo =165 Y x-2
Xo = 185 respectivamente y usando como criterio de aproximaci6n If(xn) 1lt 5 x 10-5 0
I xn - Ilt 5 x 10 - 5 xn-1
)
Capitulo 2 SOLUCION NUMERICA DE
y
n
Capitulo 2 SOLUCICN NUMERICA DE UNA ECUACICN NO-LINEAL EN UNA VARIABLE 61
y
4 -------------shy
x
FIGURA 215
n Xn f( Xn) I Xn - Xn- 1 I
0 165 114 1 179 -761 I 14 2 17564 -105 j 336x10-1
3 1750163 -260 x1 0-3 6237 x 10-3
4 175 0 163 x 10-4
TABLA 28 Instrucci6n en DERIVE
NEWTON( f( x) x Xo N) aproXima las primeras N iteracion~s en Ie metodo de Newtonshy
Raphson aplicado a la funci6n f(x) tomando como aproximacion inicial xo Para el ejemplo
aproXime la expresi6n NEWTON( 4x shy 7 x 165 4) 0 x-2
n
0 185 -266 1 179 -761 60 x 10-2
2 17564 -105 336 x 10-1
3 1750163 -260 x10-r 6237 x 10--3
4 175 0 163 x 10-4
TABLA 29
Para la misma funci6n f si usamos el metodo de Newton-Raphson con Xo = to se obtienen
hasta la quinta iteraci6n los resultados que se muestran en la TABLA 210 siguiente +
Capitulo 2 SOLUCION NUMERICA DE UNA62 METODOS NUMERICOS
I n
0 I
xn
10 I
f( xn )
30 I I xn - xn-1I I
1 2
40 220
45 405
30 180
3 16420 4000609 16200 4
5 1076168 x 107
4632550 x 1014 4000000
4000000 10760038 x 107
46325498 x1014
TABLA 210
EI siguiente teorema da condiciones suficientes no necesarias para la convergencia del metodo de Newton-Raphson aunque no da de manera explicita un intervalo donde se pueda escoger el punto inicial xo
Teorema 24 Sea f una funci6n continuamente diferenciable dos veces en un intervalo [ab]
que contiene un numero a Si f( a) = 0 y f ( a ) Q (a es rafz simple de la ecuaci6n
f( x) = 0 ) entonces existe 0gt 0 tal que la sucesi6n xnn c~
converge a a para cualquier Xo E [a - 0 a + 0]
Demostraci6n Haciendo
g(x) = x- f(x) f(x)
se demostrara que existe un 0 gt 0 tal que la funci6n 9 satisface las hip6tesis del teorema 21
(de Punto Fijo) en el intervalo [a - oa + 0]
En efecto
Como f (a)O y f es continua en [ab] existe 01gt 0 tal que f (x)O para todo
x E[a - o a + o d~[a b] Entonces 9 es continua en [a - 01 a +01] shy
Ahora
g(x) = 1- f (x)f (x- f(x)f (x) = [f (xW - [f ( x)t + f(x)f(x)
[f (x)t [f(x)t f(x)f ( x)
para xE[a - 01a + o1]
[f ( x)t
y como f es continuamente diferenciable dos veces en
[a -01a +01] porotrolado f(a)=O y f(a)tOas
f(a)f(a)
g(a) = [f(a)]2
Ahora como g es continua en [a - o1a + Sd y
tal que ~ g (x)IK lt 1 paratoda xe[a- tia+o]
Fijados K Y 8 falta demostrar que ~[a -oa +
Si x E [a - 8 a + 8] el teorema del valor meltfjO
ta ll que
f(a) (recuerde que g(a) = a - f(a) = a
Asf que Ig(x) - ex I~ 0 10 que signib
Luego g[a - 8 a + 0] -+ [a - Ba
consecuencia la sucesi6n Xnn
Nota Los crfterlol Newton-Rlphlon
de la sucesi6n n
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 63
y como f es continuamente diferenciable dos veces en [ab] entonces g es continua en
[a-8 1a+8 1 ] porotrolado f(a)= O y f (a) O asfque
g(a ) = f(a )f(~ ) = deg [f (a)]
Ahora como g es continua en [a - 81a + 8] Y g(a) = 0 entonces existe 8 con 0 lt8 lt 81
talgue Igl(x)J ~ K lt 1 paratoda x E[a-8a+8] (este 8 depende del Kescogido)
Fijados K Y 8 falta demostrar que 9([a - 8 a + 8]) ~ (a - 8 a + 8]
Si x E[a - 8a + 8] el teorema del valor medio aplicado a 9 implica que existe un ~ entre x y a
tal que
I g( x) - a I = I g(x) - g(a ) I = I g(~ ) II x - a I ~ KI x - a I lt I x - a I~ 8
(recuerde que g(a ) = a - ~~) = a )
Aslque I g(x)-a l~8 loquesignificaque g(x)E [a - 8a+8] paratodo x E[a - 8a + 8]
Luego g(a -oa+8]~(a-o a+o] satisface todas las hip6tesis del teorema 21 y en
consecuencia la sucesi6n xn n definida por
converge aacualquiera sea Xo E[a-oa+o] V
Nota Los criterios de aproximaclon que generalmente se utilizan ~n el metodo de Newton-Raphson son dado E gt 0 se toma como aproximaci6n de la ra iz a al termino xN
de la sucesi6n generada mediante la f6rmula de iteracion de Newton donde N es el menor
entero no-negativ~ tal que I f( xn) I lt E 0 Ixn - xn-1 Ilt E
Observe que si el metodo de Newton-Raphson converge como
entonces entre mas grande sea I f ( x) J en la vecindad de la raiz a mas rapida sera la
convergencia
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCICN NUMERICA DE UNA ECUACICN NO-LINEAL EN UNA VARIABLE 61
y
4 -------------shy
x
FIGURA 215
n Xn f( Xn) I Xn - Xn- 1 I
0 165 114 1 179 -761 I 14 2 17564 -105 j 336x10-1
3 1750163 -260 x1 0-3 6237 x 10-3
4 175 0 163 x 10-4
TABLA 28 Instrucci6n en DERIVE
NEWTON( f( x) x Xo N) aproXima las primeras N iteracion~s en Ie metodo de Newtonshy
Raphson aplicado a la funci6n f(x) tomando como aproximacion inicial xo Para el ejemplo
aproXime la expresi6n NEWTON( 4x shy 7 x 165 4) 0 x-2
n
0 185 -266 1 179 -761 60 x 10-2
2 17564 -105 336 x 10-1
3 1750163 -260 x10-r 6237 x 10--3
4 175 0 163 x 10-4
TABLA 29
Para la misma funci6n f si usamos el metodo de Newton-Raphson con Xo = to se obtienen
hasta la quinta iteraci6n los resultados que se muestran en la TABLA 210 siguiente +
Capitulo 2 SOLUCION NUMERICA DE UNA62 METODOS NUMERICOS
I n
0 I
xn
10 I
f( xn )
30 I I xn - xn-1I I
1 2
40 220
45 405
30 180
3 16420 4000609 16200 4
5 1076168 x 107
4632550 x 1014 4000000
4000000 10760038 x 107
46325498 x1014
TABLA 210
EI siguiente teorema da condiciones suficientes no necesarias para la convergencia del metodo de Newton-Raphson aunque no da de manera explicita un intervalo donde se pueda escoger el punto inicial xo
Teorema 24 Sea f una funci6n continuamente diferenciable dos veces en un intervalo [ab]
que contiene un numero a Si f( a) = 0 y f ( a ) Q (a es rafz simple de la ecuaci6n
f( x) = 0 ) entonces existe 0gt 0 tal que la sucesi6n xnn c~
converge a a para cualquier Xo E [a - 0 a + 0]
Demostraci6n Haciendo
g(x) = x- f(x) f(x)
se demostrara que existe un 0 gt 0 tal que la funci6n 9 satisface las hip6tesis del teorema 21
(de Punto Fijo) en el intervalo [a - oa + 0]
En efecto
Como f (a)O y f es continua en [ab] existe 01gt 0 tal que f (x)O para todo
x E[a - o a + o d~[a b] Entonces 9 es continua en [a - 01 a +01] shy
Ahora
g(x) = 1- f (x)f (x- f(x)f (x) = [f (xW - [f ( x)t + f(x)f(x)
[f (x)t [f(x)t f(x)f ( x)
para xE[a - 01a + o1]
[f ( x)t
y como f es continuamente diferenciable dos veces en
[a -01a +01] porotrolado f(a)=O y f(a)tOas
f(a)f(a)
g(a) = [f(a)]2
Ahora como g es continua en [a - o1a + Sd y
tal que ~ g (x)IK lt 1 paratoda xe[a- tia+o]
Fijados K Y 8 falta demostrar que ~[a -oa +
Si x E [a - 8 a + 8] el teorema del valor meltfjO
ta ll que
f(a) (recuerde que g(a) = a - f(a) = a
Asf que Ig(x) - ex I~ 0 10 que signib
Luego g[a - 8 a + 0] -+ [a - Ba
consecuencia la sucesi6n Xnn
Nota Los crfterlol Newton-Rlphlon
de la sucesi6n n
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 63
y como f es continuamente diferenciable dos veces en [ab] entonces g es continua en
[a-8 1a+8 1 ] porotrolado f(a)= O y f (a) O asfque
g(a ) = f(a )f(~ ) = deg [f (a)]
Ahora como g es continua en [a - 81a + 8] Y g(a) = 0 entonces existe 8 con 0 lt8 lt 81
talgue Igl(x)J ~ K lt 1 paratoda x E[a-8a+8] (este 8 depende del Kescogido)
Fijados K Y 8 falta demostrar que 9([a - 8 a + 8]) ~ (a - 8 a + 8]
Si x E[a - 8a + 8] el teorema del valor medio aplicado a 9 implica que existe un ~ entre x y a
tal que
I g( x) - a I = I g(x) - g(a ) I = I g(~ ) II x - a I ~ KI x - a I lt I x - a I~ 8
(recuerde que g(a ) = a - ~~) = a )
Aslque I g(x)-a l~8 loquesignificaque g(x)E [a - 8a+8] paratodo x E[a - 8a + 8]
Luego g(a -oa+8]~(a-o a+o] satisface todas las hip6tesis del teorema 21 y en
consecuencia la sucesi6n xn n definida por
converge aacualquiera sea Xo E[a-oa+o] V
Nota Los criterios de aproximaclon que generalmente se utilizan ~n el metodo de Newton-Raphson son dado E gt 0 se toma como aproximaci6n de la ra iz a al termino xN
de la sucesi6n generada mediante la f6rmula de iteracion de Newton donde N es el menor
entero no-negativ~ tal que I f( xn) I lt E 0 Ixn - xn-1 Ilt E
Observe que si el metodo de Newton-Raphson converge como
entonces entre mas grande sea I f ( x) J en la vecindad de la raiz a mas rapida sera la
convergencia
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCION NUMERICA DE UNA62 METODOS NUMERICOS
I n
0 I
xn
10 I
f( xn )
30 I I xn - xn-1I I
1 2
40 220
45 405
30 180
3 16420 4000609 16200 4
5 1076168 x 107
4632550 x 1014 4000000
4000000 10760038 x 107
46325498 x1014
TABLA 210
EI siguiente teorema da condiciones suficientes no necesarias para la convergencia del metodo de Newton-Raphson aunque no da de manera explicita un intervalo donde se pueda escoger el punto inicial xo
Teorema 24 Sea f una funci6n continuamente diferenciable dos veces en un intervalo [ab]
que contiene un numero a Si f( a) = 0 y f ( a ) Q (a es rafz simple de la ecuaci6n
f( x) = 0 ) entonces existe 0gt 0 tal que la sucesi6n xnn c~
converge a a para cualquier Xo E [a - 0 a + 0]
Demostraci6n Haciendo
g(x) = x- f(x) f(x)
se demostrara que existe un 0 gt 0 tal que la funci6n 9 satisface las hip6tesis del teorema 21
(de Punto Fijo) en el intervalo [a - oa + 0]
En efecto
Como f (a)O y f es continua en [ab] existe 01gt 0 tal que f (x)O para todo
x E[a - o a + o d~[a b] Entonces 9 es continua en [a - 01 a +01] shy
Ahora
g(x) = 1- f (x)f (x- f(x)f (x) = [f (xW - [f ( x)t + f(x)f(x)
[f (x)t [f(x)t f(x)f ( x)
para xE[a - 01a + o1]
[f ( x)t
y como f es continuamente diferenciable dos veces en
[a -01a +01] porotrolado f(a)=O y f(a)tOas
f(a)f(a)
g(a) = [f(a)]2
Ahora como g es continua en [a - o1a + Sd y
tal que ~ g (x)IK lt 1 paratoda xe[a- tia+o]
Fijados K Y 8 falta demostrar que ~[a -oa +
Si x E [a - 8 a + 8] el teorema del valor meltfjO
ta ll que
f(a) (recuerde que g(a) = a - f(a) = a
Asf que Ig(x) - ex I~ 0 10 que signib
Luego g[a - 8 a + 0] -+ [a - Ba
consecuencia la sucesi6n Xnn
Nota Los crfterlol Newton-Rlphlon
de la sucesi6n n
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 63
y como f es continuamente diferenciable dos veces en [ab] entonces g es continua en
[a-8 1a+8 1 ] porotrolado f(a)= O y f (a) O asfque
g(a ) = f(a )f(~ ) = deg [f (a)]
Ahora como g es continua en [a - 81a + 8] Y g(a) = 0 entonces existe 8 con 0 lt8 lt 81
talgue Igl(x)J ~ K lt 1 paratoda x E[a-8a+8] (este 8 depende del Kescogido)
Fijados K Y 8 falta demostrar que 9([a - 8 a + 8]) ~ (a - 8 a + 8]
Si x E[a - 8a + 8] el teorema del valor medio aplicado a 9 implica que existe un ~ entre x y a
tal que
I g( x) - a I = I g(x) - g(a ) I = I g(~ ) II x - a I ~ KI x - a I lt I x - a I~ 8
(recuerde que g(a ) = a - ~~) = a )
Aslque I g(x)-a l~8 loquesignificaque g(x)E [a - 8a+8] paratodo x E[a - 8a + 8]
Luego g(a -oa+8]~(a-o a+o] satisface todas las hip6tesis del teorema 21 y en
consecuencia la sucesi6n xn n definida por
converge aacualquiera sea Xo E[a-oa+o] V
Nota Los criterios de aproximaclon que generalmente se utilizan ~n el metodo de Newton-Raphson son dado E gt 0 se toma como aproximaci6n de la ra iz a al termino xN
de la sucesi6n generada mediante la f6rmula de iteracion de Newton donde N es el menor
entero no-negativ~ tal que I f( xn) I lt E 0 Ixn - xn-1 Ilt E
Observe que si el metodo de Newton-Raphson converge como
entonces entre mas grande sea I f ( x) J en la vecindad de la raiz a mas rapida sera la
convergencia
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 63
y como f es continuamente diferenciable dos veces en [ab] entonces g es continua en
[a-8 1a+8 1 ] porotrolado f(a)= O y f (a) O asfque
g(a ) = f(a )f(~ ) = deg [f (a)]
Ahora como g es continua en [a - 81a + 8] Y g(a) = 0 entonces existe 8 con 0 lt8 lt 81
talgue Igl(x)J ~ K lt 1 paratoda x E[a-8a+8] (este 8 depende del Kescogido)
Fijados K Y 8 falta demostrar que 9([a - 8 a + 8]) ~ (a - 8 a + 8]
Si x E[a - 8a + 8] el teorema del valor medio aplicado a 9 implica que existe un ~ entre x y a
tal que
I g( x) - a I = I g(x) - g(a ) I = I g(~ ) II x - a I ~ KI x - a I lt I x - a I~ 8
(recuerde que g(a ) = a - ~~) = a )
Aslque I g(x)-a l~8 loquesignificaque g(x)E [a - 8a+8] paratodo x E[a - 8a + 8]
Luego g(a -oa+8]~(a-o a+o] satisface todas las hip6tesis del teorema 21 y en
consecuencia la sucesi6n xn n definida por
converge aacualquiera sea Xo E[a-oa+o] V
Nota Los criterios de aproximaclon que generalmente se utilizan ~n el metodo de Newton-Raphson son dado E gt 0 se toma como aproximaci6n de la ra iz a al termino xN
de la sucesi6n generada mediante la f6rmula de iteracion de Newton donde N es el menor
entero no-negativ~ tal que I f( xn) I lt E 0 Ixn - xn-1 Ilt E
Observe que si el metodo de Newton-Raphson converge como
entonces entre mas grande sea I f ( x) J en la vecindad de la raiz a mas rapida sera la
convergencia
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOlUCI6N NUMERICA DE UNA EClJ64 M~TODOSNUM~R~OS
Algoritmo 23 (Newton-Raphson) Para encontrar una aproximaci6n a de una raiz a de
una ecuaci6n f( x) = 0 conocida una aproximacion inicial Xo
Entrada f( x) f ( x) una aproximaci6n inicial Xo una tolerancia Tal y un numero maximo
de iteraciones N
Salida Una raiz aproximada a a un mensaje
Paso 1 Tomar n = 1
Paso 2 Mientras que n 0 N seguir los pasos 3-8
Paso 4 Si d = 0 entonces salida No se puede continuar el metodo Terminar
ePaso 5 Tomar c = Xo - - (calcula xn )
d
Paso 6 Si If( c) 1lt Tol 0 Ic - Xo I= I ~ 1lt Tol entonces salida Una raiz
aproximada es a =C n Terminar
Paso 7 Tomar n =n + 1
Paso 8 Tomar Xo = c (redefine Xo )
Paso 9 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 26 Can respecto a las raices al a2 Y a 3 de la ecuaci6n 3x2 - eX = 0 vemos
que la funci6n f( x) = 3x2 - eX satisface la hip6tesis general del metoda de Newton-Raphson
en los intervalos [-5--] [910] Y [3738] Si aplicamos el metoda de Newton-Raphson
can aproximaciones iniciales apropiadas y criterio de aproximaci6n
r
se obtienen los resultados que se muestran en las T ABLAS 211 212 Y 213 siguientes
2 Para este ejemplo aproXime la expresi6n NEWTON( 3x
De acuerdo con la TABLA 211 se tiene que U 1
n
De acuerdo con la TABLA 212 se tiene que Q2
n
Ejercicio 25 Use el metodo de ecuaci6n x - tanx = 0 usando como anterior +
223 EI metodo de encontrar raices reale d ecuaci6n polin6mica con cOlriCI~
Si a
n xn f(xn) Ixn - xn_1 I 0 - 5 143 1 -4602195 426 x10-3 397805 x 10-2
2 - 4589635 418 x10-6 1256 x 10-3
TABLA 211
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 65
Para este ejemplo aproXime la expresion NEWTON( 3x2 - exp( x) x - 052 )
De acuerdo con la TABLA 211 se tiene que a 1 -4589635 = x2
n xn f( xn) Ixn - xn_1 I 0 10 281 x10-1
1 9141552 426 x 10-3 858448 x 10-2
2 9100176 418 x10-6 41376 x 10-3
TABLA212
De acuerdo con la TABLA 212 se tiene que a2 9100176 = x2
n xn f( xn) Ixn - xn-1 I 0 37 622 x10- 1
1 3734125 - 203 x 1 0-2 34125 x 10-2
2 3733080 -200 x10-5 1045 x 10-3
TABLA 213
Los resultados de la TABLA 213 indican que a3 Z 3733080 = bullx2
Ejercicio 25 Use el metodo de Newton-Raphson para encontrar la menor raiz positiva de la ecuacion x - tanx = 0 usando como criterio de aproximaci6n el mismo dado en ejemplo 26 anterior bull
223 EI metodo de Newton-Raphson combinado con el algoritmo de Horner para encontrar raices reales de ecuaciones polinomicas con coeficientes reales Dada una ecuaci6n polin6mica con coeficientes reales
Si a es una raiz real de la ecuaci6n p( x) = 0 el metodo de Newton-Raphson para aproximar
la rafz a consiste en generar la sucesion xn n mediante la formula de iteracion
p( xn- 1)
xn =xn_1 - ( ) n=12 p xn _1
con Xo escogido cercano a a
Como se ve en la f6rmula anterior el calculo de cada iteracion requiere la evaluaci6n del polinomio p y su derivada p en un numero Existe un algoritmo amado algoritmo de Horner muy facil de implementar en el computador el cual permite calcular de manera eficiente el valor del polinomio y el de su derivada en un nUmero
EI algoritmo de Horner se basa en escribir el polinomio p(x) en la forma encajada 0 anidada siguiente
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCI6N NUMERICA Of66 ME-TODOS NUMERICOS
Si queremos evaluar p(z) y p(z) para algun numero real z basta tener en cuenta que
Si hacemos
bn =an Y
= ak + zbk+1 para k = n -1n - 2 10 bk
entonces bo = p(z)
Los numeros auxiliares bn bn_ b son los coeficientes del polinomio cociente q(x) que
resulta de la division de p(x) par x - z Y bo es el residuo es decir
p( x) = ( x - z )q( x) + b0
En efecto
Como p(x) =(x - z)q(x) + bo entonces para x =z se obtiene
p(z) = (z - z)q(z) + bo = bo
Ahora bien como
p( x) = (x - z )q( x) + bo
entonces derivando a ambos lad os de esta ultima ecuaci6n con respecto a x obtenemos
p(x) = q( x) + (x - z)q( x)
yentonces
p(z) = q(z) + (z - z)q(z) = q(z)
y como q(x) es un polinomio del cual
b b _ b ) podemos aplicar el algoritmo de n n de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un
Y su derivada en un numero real z
Entrada EI grado n del polinomio los
real z
Salida bo = p(z) Y c = p(z
Paso 1 Tomar bn = an (cacula el~-
Paso 3 Tomar bo =ao +zb
Paso 4 Salida p(z) =bo Y
Observe en el algoritmo
reducido q(x) si Jlnl~rJlmDl
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NO-LINEAL EN UNA VARIABLE 67
y como q(x) es un polinomio del cual conocemos sus coeficientes (los numeros
bn bn_1 b1 ) podemos aplicar el algoritmo de Horner al polinomio q(x) para hallar q(z) y
de esta manera obtener p(z)
Algoritmo 24 (Horner) Para evaluar un polinomio con coeficientes reales
Y su derivada en un numero real z
Entrada EI grado n del polinomio los coeficientes aOa1 an del polinomio p(x) el numero
real z
Salida bo =p(z) y c =p(z)
Paso 1 Tomar b = an (calcula el coeficiente b de q( x) )n n
c =an
Paso 2 Para j = n -1n - 2bull 1 tomar
bj = aj + zbj+1 (calcula los coeficientes bn_1bn_2 b1 de q(x))
c = bj+ zc (almacenaenca q(z) = p(z))
Paso 3 Tomar bo = ao + zb1 (almacena en bo a pz))
Paso 4 Salida p(z)=bo y pmiddot(z) = c Terminar
Observe en el algoritmo anterior que como b b _1 b son los coeficientes del polinomio n n 1
reducido q( x) si aplicamos el algoritmo de Horner a este polinomio q(x) es decir hacemos
cn = bn y
para j=n - 1n - 2 1 hacemos cj = bj + zc j+1
obtenemos que c1 = b1 + zC 2 = q(z) = P(z) Por tanto al terminar la aplicacion del
algoritmo de Horner en c queda almacenado q(z) es decir c = q(z) = P(z)
Es importante observar que el algoritmo de Horner solo usa n multiplicaciones y n sumas
para calcular p(z) 10 que hace muy eficiente dicho calculo Intente calcular p(z) de
cualquier otra forma y compare el numero de operaciones
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
68 M~TODOSNUM~~COS
Para implementar el algoritmo de Horner manualmente usamos el esquema de division sintetica
an a _ an-2 a1 a ~ n 1 o zbn_zbn 1 zb2 zb1
b _ b _ bo=P(Z)bn n 1 n 2 b1II
an
Ejemplo 27 Consideremos la ecuaci6n x 3 - x - 1 = O Como p( x) = x 3
- x -1 es continua en
el intervalo [12] p(1) = - 1lt 0 Y p(2)=5 gt 0 entonces la ecuacion p(x) = o tiene por 10
men os una rafz en el intervalo [12] Por otro lado como p(x) = 3x2 - 1gt 0 para todo
x E [12] entonces la ecuaci6n p( x) = 0 tiene una (mica raiz simple a 1 E [12] Es claro
entonces que se puede aplicar el metodo de Newton-Raphson para calcular esta raiz a 1middot Si
hacemos los calculos usando el metodo de Newton-Raphson combinado con el algoritmo de Horner tomando como aproximaci6n inicial Xo = 2 Y criterio de aproximaci6n
3I xn - xn_11 lt 5 x 10-3
0 Ip(xn) 1 lt 5 x 10- obtenemos
Debemos calcular p(20) y p(20) Si usamos el algoritmo de Horner y aritmetica con
redondeo a cinco (5) dlgitos para los caculos se obtienen los resultados que aparecen en el siguiente esquema de divisi6n sintetica
20 -1 -1 62 4
2 3 15 =p(2) I 2 8
4 1 11 =P(2) I
Entonces
3x1= 20- 50 =15455 Y I x1- xo l= 4545 gt 5 x 10 shy110
3 Para calcular P(X1) = p(15455) Y verificar si se satisface la condicion I p(x1) lt 5 x 10-
usaremos el algoritmo de Horner Vea el siguiente esquema de division sintetica
Capitulo 2 SOLUCI6N NUM~RICA DE
-10 2388615455
15455 13886
15455
3091
3 Observe que p(x1)1 = 11461gt 5 x 10- asl ~ut resultados que aparecen en el esquema anleriOl
Si seguimos calculando como se indic6 en
3p(x )=1536 gt 5 x 10- P(X2) = 2
3Ip(X3 ) I = 0046 lt 005 =5 x 10-
Luego al 13258 = X3 Puesto que
podrlamos intentar aproximar las
verificar facilmente que las ralces
Recordemos que
donde q(x)
los coeficientes del polinomio
Total que
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCI6N NUMERICA DE UNA ECUACI6N NOmiddotLlNEAL EN UNA VARIABLE 69
115455 o -1 -1 15455 23886 21461
15455 13886 1 1461=p(15455)
15455 47771
3091 61657=p(15455)
3Observe que Ip( Xl) I= 11461 gt 5 x 10- asf que debemos calcular x2 De acuerdo con los
resultados que aparecen en el esquema anterior
X =X - P(Xl) =15455 - 11461 = 13596 Y Ix2-xI=1859gt5x10-3 2 1 p(xl ) 61657
Si seguimos calculando como se indic6 en los dos casos anteriores obtenemos
P(X2) = 1536 gt 5 x 10-3 p(x2) = 45455 X3 = 13258
3Ip(x3)1 = 0046 lt 005 = 5 x 10-
3Luego Ul 13258 = x3 Puesto que la ecuaci6n dada x - X-1 = 0 tiene tres raices como
podrfamos intentar aproximar las otras dos raices u 2 Y U3 de esta ecuaci6n (Se puede
verificar facilmente que las raices u 2 Y u 3 son complejas no-reales)
Recordemos que
p(x) = (x - 13258)q(x) + p(13258)
3donde q(x) es el polinomio cociente en la division de p(x) = x - x -1 por x - 13258 Y que
los coeficientes del polinomio q( x) se pueden obtener usando el algoritmo de Horner Pues
bien el siguiente esquema muestra cuales son los coeficientes del polinomio q(x)
0 -1 -1 13258 I
13258 17577 10046
13258 07577 I 00046 =p(13258) I IIII lt 1 middot
b2 b1
De acuerdo con el anterior esquema de division sintetica el polinomio q(x) es
q(x) = x 2 + 13258x + 7577
Total que
p(x) = (x - 13258)( x2 + 13258x + 7577) + 00046
(recuerde que estamos haciendo redondeo a cinco dfgitos)
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCION NUMERICA DE UNA 70 METODOS NUMERIC OS
Si despreciamos el residuo en la division anterior es decir despreciamos p(13258) = 0046
entonces 2p( x) (x -13258)(x + 13258x + 7577)
2y entonces podrlamos usar el polinomio reducido q( x) = x + 13258x + 7577 (cociente de la
3divis ion del polinomio x - x - 1 por el pol inomio x - 13258) para aproximar las otras dos 3ralces de la ecuacion orig inal p( x) = x - x - 1= 0 Si resolvemos la ecuac ion q( x) == 0
obtenemos a 23 ~ - 6629 plusmn 56415i bull
Instrucci6n en DERIVE
QUOTIENT( p( x) x - a ) Simplifica 0 aproXima el polinomio cociente q( x) que resulta de la
division del polinomio p( x) pQr x - a Para el ejemplo aproXime la expresion
QUOTIENT( x3 - x -1 x - 13258) 0
EI proceso ilustrado en el ejemplo anterior para aproximar las ralces a 2 y a 3 se conoce
como Deflaci6n
En general la Deflacion aplicada al problema dehallar raices reales de ecuaciones polinomicas consiste en 10 sigu iente
Supongamos que en la N-esima iteraci6n en la aplicacion del metodo de Newton-Raphson obtuvimos un cero aproximado del polinomio p(x) entonces xN
ya que p(xN ) 0 (porque p(x) es continua y si a con a un cero de p(x) entonces xN
p( xN ) p(a) = 0 )
Lo anterior significa que (x - xN ) es un factor aproximado de p(x)
Tomando a~ == Y qn_(x) como el polinomio reducido q(x) de grado n -1 se tiene que xN
d con n cerosSi p(x) es un polinomlo de gra 0 n reiteradamente permitira eventual mente ~btener n
factor cuadratico aproximado q2 (X) es declr
p(x)e(x -a)(x-a) (x
AI polinomio cuadratico q2(X) Ie podremos ealcular
EI procedimiento descrito antes para obtener
La posible deficiencia en la precisi~n de la~ cuando obtenemos los cer~s aproxlmados e Raphson aplicado al polinomio redueido q(x
ado a queDeflaci6n cualquier cero aproxlm k
someterse a un refinamiento aplicando el
p(x) tomando a a~ como aproximaci6n
Un algoritmo para el metodo de
Algoritmo 25 (Newton-Raphon
aproximado a del polinomio p(x)
Entrada EI grado n y 105 una toleraneia ToiXo
Salida Un cero aproximado jI
Paso 1 Tomar i1
Paso 2 Mientras Que
y podemos encontrar una aproximacion a de un segundo cero de p(x) aplicando el metodo
de Newton-Raphson al polinomio qn- ( x) con 10 cual
p(x) (x - a )( x - a )qn- 2(x)
siendo qn-2(x) un pol inomio de grado n - 2
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
Capitulo 2 SOLUCION NUMERICA DE UNA ECUACION NOmiddotLlNEAL EN UNA VARIABLE 71
Si p(X) es un polinomio de grado n con n ceros reales este procedimiento aplicado reiteradamente permitira eventualmente obtener n - 2 ceros aproximados de p(x) y un
factor cuadratico aproximado q2(X) es decir
AI polinomio cuadratico q2(X) Ie podremos calcular sus ceros usando la formula cuadratica
EI procedimiento descrito antes para obtener 00middot0~_2 se conoce como Deflaci6n
La posible deficiencia en la precision de las raices obtenidas por Deflacion se debe a que cuando obtenemos los ceros aproximados de p(x) estamos usando el metodo de Newtonshy
Raphson aplicado al pOlinomio reducido qk(X) Para mejorar la precision en el metodo de
Defiacion cualquier cero aproximado o~ que se encuentre para un polinomio reducido debe
someterse a un refinamiento aplicando el metodo de Newton-Raphson al polinomio original
p(x) tomando a o~ como aproximacion inicial
Un algoritmo para el metodo de Newton-Raphson combinado con Horner es el iguiente
Algoritmo 25 (Newton-Raphson combinado con Horner) Para encontrar un cero
aproximado 0 del polinomio
Entrada EI grado n y los coeficientes aOa1 an del polinomio p(x) una aproximacion inicial
Xo una tolerancia Tol y un numero maximo de iteraciones N
Salida Un cero aproximado 0 del polinomio p(x) 0 un mensaje
Paso 1 Tomar i = 1
Paso 2 Mientras que i ~ N seguir los pasos 3-10
Paso 3 Tomar bn = an y c = an
Paso 4 Para j = n -1n - 2 1 tomar
Paso 5 Tomar bo = ao + xOb1 (calcula p(xo))
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217
72 METODOS NUMERICOS
Paso 6 Si c = 0 entonces salida No se puede continuar el metodo porque se
anul6 p( xo) Terminar
bPaso 7 Tome Xl = Xo - ~ (calcula Xi en el metodo de Newton-Raphson)
c
Paso 8 Si I bo 1lt Tol 0 I Xl - Xo I = I b 1lt Tol entonces salida Una raiz
aproximada de p( x) = 0 es a = Xl Terminar
Paso 9 Tomar i = i + 1
Paso 10 Tomar Xo = Xlmiddot
Paso 11 Salida Se alcanz6 el numero maximo de iteraciones N pero no la tolerancia Terminar
Ejemplo 28 Encontrar todas las ra ices reales de la ecuaci6n pol in6mica
X4 _ 2x3 - 4X2 + 4x + 4 =0 usando el metodo de Newton-Raphson y Deflaci6n
Empezamos graficando el polinomio p(x) = X4 - 2x3 - 4X2 + 4x + 4 para ubicar las raices
reales (ver la FIGURA 216 siguiente)
Y Y=P(x)
3 4 x2
FIGURA 216
De acuerdo con la grafica del polinomio p(x) = X4 -2x raices a l a2a3 y a 4 de la ecuaci6n
a E[-2-1] a2 E[- 1O] a 3 E [12] a 4 E[23J
Se ve ciaramente que p( x) satisface la hip6tesis
intervalos apropiados para cada una de las ralces
Usando el metoda de Newton-Raphson para 5Ip(xn) 1lt 5 x 10 - 0 Ixn - xn_l I 5 x 10 5 58
Yel correspondiente polinomio reducldo de
Usando Deflaci6n encontramos
al 1414157 =X5 tomando como
correspondiente de grado 2 es
Finalmente encontramos aDn)xin
cuadratica q2(x) ~ 0 con 10 que
Ejemplo 29 X4 +5X3 _9x2 _85x-136 0
La grllfica del polinomio r( 217