[75.12] Análisis Numérico I

María Inés Parnisari

26 de abril de 2017

Índice

1. Errores 2

2. Sistemas de ecuaciones lineales 4

3. Ecuaciones de una variable 10

4. Sistemas de ecuaciones no lineales 13

5. Interpolación 14

6. Ajuste de funciones y mejor aproximación 18

7. Diferenciación numérica 18

8. Integración numérica 19

9. Ecuaciones diferenciales ordinarias 22

1

Figura 1:Precisión yexactitud.

Algunas de�niciones preliminares:

Análisis numérico: diseño de algoritmos para resolver problemas de matemática continua.

Error: incertidumbre tanto de los datos de ingreso como de los resultados obtenidos en unprocedimiento. Está asociado a la aproximación.

Exactitud: error absoluto o relativo de un valor. No está limitada por la precisión.

Precisión: exactitud con que se llevan a cabo operaciones aritméticas. No siempre mejora unaaproximación.

Orden de convergencia de un algoritmo: la velocidad con la cual una sucesión convergea su límite. Este concepto es, desde el punto de vista práctico, muy importante si necesitamostrabajar con secuencias de sucesivas aproximaciones de un método iterativo.

Supongamos que la secuencia {xk} converge al número ξ. Decimos que la sucesión converge conorden q a ξ si

lımk→∞

|xk+1 − xi||xk − xi|q

= λ con λ > 0

El número q es llamado orden de convergencia. En particular, convergencia de orden 1 es lla-mada convergencia lineal, la de orden 2 convergencia cuadrática y la convergencia de orden 3convergencia cúbica.

1 Errores

1.1 Fuentes de error

1.1.1 Error inherente

Error inherente: error de los datos de entrada que puede provenir de la precisión en la medición de los datos,la representación numérica, etc. Dado un valor exacto m y una aproximación m, de�nimos:

Error absoluto: |ea| = |m− m|

Error relativo: |er| = |ea||m| = |m−m|

|m| (mejor aproximación que el error absoluto)

Número de condición / factor de ampli�cación: sea la función y = f(x). El error relativo de y es

ery u∂f(x)

∂x· x

f(x)︸ ︷︷ ︸CP

· erx . Al coe�ciente que multiplica el error relativo de x lo llamamos número de condición.

Si la función es dos o más variables, tendremos CPi = ∂f(x)∂xi· xif(x) . Es decir:

CP =∑i

∣∣∣∣∂f(x)

∂xi

∣∣∣∣ · |xi||f(x)|

Ejemplo: sea el algoritmo z = a2 + b2. Su número de condición está dado por

CP =

[∂z

∂a

a

z

]+

[∂z

∂b

b

z

]=

[2a · a

a2 + b2

]+

[2b · b

a2 + b2

]=

2a2

a2 + b2+

2b2

a2 + b2= 2

1.1.2 Error de redondeo

Error de redondeo / corte: error debido a la representación numérica utilizada.

El error de redondeo surge por la notación de punto �otante:

N ∼= d, d1d2...dt × βp con

t cantidad de dígitos

β base

p exponente

Corte: forma de redondear que consiste en �borrar� dígitos.

2

Redondeo: forma de redondear que consiste en modi�car el último dígito según el siguiente criterio:

dk =

{dk si 0 ≤ dk+1 ≤ 4

dk + 1 si 5 ≤ dk+1 ≤ 9

La cota para el error de redondeo es:

Para números de la formad, d1d2...dk

Para números de la forma0, d1d2...dk

Corte 10−t 101−t

Redondeo 12 · 10−t 1

2 · 101−t

Término de estabilidad: nos da una idea de la in�uencia del error de redondeo.

El error relativo por el error de redondeo es er =∑ki=1 |T (x)|µi = Teµ

1.1.3 Otras fuentes de error

Error de truncamiento / discretización: error que aparece al transformar un procedimiento in�nito en uno�nito.

Error del modelo matemático: se debe a las simpli�caciones e hipótesis introducidas para de�nir el modelomatemático que representa el modelo físico.

Error humano: error producido por la intervención humana y/o por programas de computación mal hechos.

1.1.4 Error total

erT = CP · r + Te · µ

1.2 Algoritmos

Factores de ampli�cación de errores de entrada: y = x1(op)x2 =⇒ ry = f1x1 + f2x2

op + − × ÷f1

x1

yx1

y 1 1

f2x2

y −x2

y 1 -1

Algoritmo bien condicionado: un problema matemático está bien condicionado cuando al introducir peque-ñas variaciones en los datos de entrada se producen pequeñas variaciones en los resultados.

CP � 1 =⇒problema mal condicionado CP 6� 1 problema bien condicionado

Si f representa al algoritmo �real� y f∗ al algoritmo �computacional�, y x a la variable �real� y x∗ a la variable�computacional� entonces el error en los resultados se de�ne como:

|f(x)− f ∗ (x∗)| ≤ |f(x)− f(x∗)|+ |f(x∗)− f ∗ (x)|+ |f ∗ (x)− f ∗ (x∗)|

Algoritmo estable: tiene la propiedad de que la propagación de los errores de redondeo es lineal o cuasi-lineal.

En ≈ c · n · E0

Te � 1 =⇒algoritmo inestable Te 6� 1 =⇒algoritmo estable

Para obtener algoritmos estables se recomienda:

1. Evitar la resta de números con errores

2. Minimizar el tamaño de los números intermedios relativos al resultado �nal

3. valornuevo = valorviejo + correccion

4. Usar transformaciones bien condicionadas

Resumiendo:

1 + TeCP� 1 =⇒mal algoritmo 1 + Te

CP6� 1 =⇒buen algoritmo

3

1.3 Grá�ca de proceso y perturbaciones experimentales

Una forma de obtener los coe�cientes Te y CP es la grá�ca de proceso: undiagrama de �ujo que representa la propagación de los errores relativos y deredondeo.

La grá�ca de proceso no siempre es útil y práctica. También podemos estimarel CP y el Te mediante perturbaciones experimentales:

Si suponemos Te ≈ 0 =⇒CP = err

Si suponemos r ≈ 0 =⇒ Te =yµ−yξyξ(µ−ξ)

1.3.1 Estimación del Cp

Consiste en suponer que no existen errores de redondeo y perturbar los valores de entrada. La idea es: se tomanlos datos de entrada y se aplica el algoritmo a analizar, obteniendo el resultado �exacto� x. Luego se �perturban�los datos de entrada introduciéndoles un error ±k y se vuelven a calcular los resultados, obteniéndose x1 y x2.Entonces se calculan los Cp:

Cp1 =∣∣∣x−x1

x · 1+k

∣∣∣Cp2 =

∣∣∣x−x2

x · 1−k

∣∣∣Y �nalmente tenemos que CP = max{Cp1 , Cp2}. Como hemos supuesto que los errores de redondeo son despre-ciables, los Cp deberían ser similares, con lo cual tendremos una estimación de la condición del problema.

1.3.2 Estimación del Te

Consiste en suponer que no existen errores inherentes.

Ejemplo: aproximamos la función f(x) = sin(x) con su serie de MacLaurin g(x) = x− x3

6 + x5

120 −x7

5040 + x9

362880 .Calculemos el valor de f(π4 ) con tres precisiones utilizando g(x):

u = 15→ µu = 10−14 → yu = 0, 70710678293687

t = 8→ µt = 10−7 → yt = 0, 7071068

s = 4→ µs = 10−3 → ys = 0, 706

Tomando como valor �exacto� a yu tenemos que:

Tes = yu−ysyu(µs−µu) = 1, 565

Tet = yu−ytyu(µt−µu) = 0, 241

En este caso concluimos que calcular f(y) con más precisión mejora el resultado �nal, pero esto no siempre escierto.

2 Sistemas de ecuaciones lineales

Sea el sistema de ecuaciones dado pora11x1 + ...+ a1nxn = b1...

an1x1 + ...+ annxn = bn

=⇒ Ax = B =⇒

a11 · · · a1n

.... . .

...an1 · · · ann

x1

...xn

=

b1...bn

Si A es una matriz cuadrada tal que det(A) 6= 0, podemos resolver el sistema mediante x = A−1B. Sin embargo,los coe�cientes de la matriz A puede provenir de mediciones imprecisas, lo que haría que calcular A−1 resulteen más errores. Por este motivo surgen alternativas a esta forma de resolución del sistema.

4

Norma in�nito de una matriz A: es la máxima suma absoluta de las �las de una matriz.

‖A‖∞ = max1≤i≤m

n∑j=1

|aij |

Número de condición de una matriz A: se de�ne como κ(A) = ‖A‖∞∥∥A−1

∥∥∞. Puede estimarse mediante

‖x−x‖∞‖x‖∞

· 10t ≤ κ(A). El error relativo de x al resolver Ax = B depende de κ(A).

Matriz bien condicionada: si κ(A) es chico entonces la matriz A es bien condicionada, y no hay alta propa-gación de errores de redondeo al resolver Ax = B. Caso contrario, A es mal condicionada. Generalmente, lasmatrices mal condicionadas mezclan coe�cientes chicos con coe�cientes grandes, o satisfacen det(A) ≈ 0. Si Aes tal que 6 ∃A−1 entonces κ(A) =∞.

2.1 Sustitución directa e inversa

Dada una matriz A que es triangular superior o triangular inferior, existen dos métodos para resolver el sistemaAx = B.

Si A es triangular inferior, la sustitución directa consiste en:

xi =bi −

∑i−1j=1 lijxj

lii

Si A es triangular superior, la sustitución inversa consiste en:

xi =bi −

∑nj=i+1 uijxj

uii

2.2 Métodos directos

Cuando queremos resolver el sistema Ax = B y la matriz A tiene en su mayoría coe�cientes no nulos (matrizdensa) podemos aplicar un método directo para resolverlo. Estos métodos consisten en transformar la matrizoriginal A en una matriz triangular y luego aplicar sustitución directa o inversa.

Ventajas Desventajas- sólo hay errores de redondeo - no resuelven bien matrices mal condicionadas

- el número de operaciones es �nito - se vuelven inestables con matrices grandes

2.2.1 Método de eliminación de Gauss

Consiste en transformar la matriz A de Ax = B en una matriz triangular superior mediante operaciones entre�las y luego aplicar sustitución inversa.

Eliminación con pivoteo parcial: es necesario intercambiar de lugar �las. Es del orden O(cn3).

Eliminación con pivoteo total: es necesario intercambiar de lugar �las y columnas.

Convergencia: cuando A es diagonal dominante, es decir |aii| >∑nj=1,j 6=i |aij |

Ventajas Desventajas- fácil de programar - si cambia el vector B es necesario retriangular A.

- O(n3)

2.2.2 Factorización LU; métodos de Doolittle y Crout

La factorización LU consiste en transformar la matriz A en A = L︸︷︷︸4

U︸︷︷︸5

. Entonces el sistema Ax = B se

convierte en:1 0 · · · 0

m2,1 1. . .

......

. . . 0mn,1 · · · mn,n−1 1

a〈1〉11 · · · a

〈1〉1n

0...

.... . .

0 · · · 0 a〈n〉nn

x1

...xn

=

b1...bn

7→ {Ux = y (I)

Ly = B (II)

5

dondemi,j =a〈i〉ji

a〈i〉ii

son los coe�cientes de la triangulación de Gauss. El sistema (I) se resuelve aplicando sustitución

inversa y para (II) sustitución directa.

Teorema: si se puede efectuar la eliminación de Gauss en el sistema lineal Ax = B sin intercambios de �las,entonces A se puede factorizar en el producto LU . Dos ejemplos de estos tipos de matrices son: estrictamentediagonal dominantes, de�nidas positivas.

Ventajas Desventajas- si cambia el vector B no hay que refactorizar A - determinar L y U requiere O(n3) pasos

- resolver Ax = B requiere O(n2) pasos- no sirve para todas las A

Método de Doolittle: consiste en factorizar A asumiendo que lii = 1.

A = LU =

1 0 · · · 0

l21 1. . .

......

. . .. . . 0

ln1 · · · ln,n−1 1

u11 · · · u1n

0. . .

......

. . .

0 · · · 0 unn

La fórmula general es:

lji = 1uii

[aji −

∑i−1k=1 ljkuki

]uii = aii −

∑i−1k=1 likuki

uij = aij −∑i−1k=1 likukj

Método de Crout: consiste en factorizar A asumiendo que uii = 1.

2.2.3 Método de Cholesky

Si A es una matriz simétrica y de�nida positiva, entonces planteamos que A = S︸︷︷︸4

ST︸︷︷︸5

. La fórmula es:

sii =√aii −

∑i−1k=1 s

2ik

sji = 1sii

[aji −

∑i−1k=1 sjksik

]para i 6= j

Ventajas Desventajas- menor cantidad de cálculos que Crout y Doolittle - O(n3)

2.3 Métodos iterativos estacionarios

Supongamos el sistema Ax = B. Tenemos que:

B −Ax = 0

B −Ax+ Px = Px

B + (−A+ P )x = Px

x = (I − P−1A)x+ P−1B

x〈i+1〉 = (I − P−1A)︸ ︷︷ ︸T

x〈i〉 + P−1B︸ ︷︷ ︸C

Los métodos iterativos:

Son muy útiles para resolver sistemas con matrices ralas (con muchos coe�cientes nulos). También sonútiles para resolver sistemas con matrices mal condicionadas (pero si κ(A) � 10t, siendo t la precisiónutilizada para realizar los cálculos, entonces debe aumentarse t para obtener una solución aceptable). Ypor último, son útiles cuando A es grande.

6

Para que el método converja a la única solución con cualquier x〈0〉, T debe ser tal que ρ(T ) < 1, o lo quees lo mismo ‖T‖ < 1 para cualquier norma natural. Idealmente, debería ser ‖T‖ � 1.

Nunca dan una solución exacta, incluso si usamos una precisión in�nita.

Re�namiento iterativo: es una técnica que, dada una solución obtenida por el método de Gauss, factorizaciónLU o Cholesky, mejora el resultado.

Ax = B =⇒ Ax0 = B =⇒ B−Ax0 = r0 =⇒ Ax−Ax0 = r0 =⇒ A(x− x0)︸ ︷︷ ︸d0

= r0 =⇒ Ad0 = r0 =⇒ d0+x0 = x1 =⇒ . . .

Cuando la matriz A es muy mal condicionada, la primera solución obtenida mediante un método directo puedeno estar muy cerca de la solución correcta. Entonces podemos usar el re�namiento iterativo:

x = x〈1〉 +

n→∞∑i=1

d〈i〉

Un criterio de corte aceptado para parar las iteraciones es:∣∣x〈n+1〉 − x〈n〉∣∣∣∣x〈n+1〉

∣∣ ≤ TOL

Y además, puesto que|x〈n+1〉−x〈n〉||x〈n+1〉| ≤ κ(A) ‖R‖‖B‖ , si A es mal condicionada la tolerancia debe ser más chica.

Los siguientes métodos se llaman métodos iterativos estacionarios porque las matrices T y C no se modi-�can.

2.3.1 Método de Jacobi

Dado el sistema inicial Ax = B, el método de Jacobi consiste en despejar de cada ecuación las incógnitas:a11x1 + ...+ a1nxn = b1...

an1x1 + ...+ annxn = bn

=⇒

x1 = b1−a12x2−...−a1nxn

a11...

xn = bn−an1x1−...−ann−1xn−1

ann

=⇒ x〈i+1〉i =

bi −∑nk 6=ik=1

aikx〈i〉k

aii

En forma matricial esto es

x〈i+1〉 = Tx〈i〉 + C =

0 −a12a11

· · · −a1,na11. . .

......

. . .

− an,1an,n

· · · −an,n−1

an,n0

x〈i〉 +

b1a11...bnan,n

siendo:

P = D

T = −D−1(L+ U)

C = D−1B

Convergencia: cuando A es estrictamente diagonal dominante, es decir |aii| >∑nj=1,j 6=i |aij |

2.3.2 Método de Gauss-Seidel

El método de Gauss-Seidel es similar al método de Jacobi pero más rápido, con la diferencia de que en elcálculo de xi (i > 0) se aprovecha lo calculado en el paso anterior:

x〈i+1〉i =

bi −∑i−1k=1 aikx

〈i+1〉k −

∑nk=1 aikx

〈i〉k

aii

En forma matricial esto es x〈i+1〉 = Tx〈i〉 + C siendo:

7

P = D + L

T = I − (D + L)−1A

C = (D + L)−1B

Convergencia: cuando A es estrictamente diagonal dominante, es decir |aii| >∑nj=1,j 6=i |aij |, o bien cuando A

es simétrica y de�nida positiva.

2.3.3 Métodos de las sobrerelajaciones (SOR)

El método de las sobrerelajaciones es una variante del método de Gauss-Seidel, pero que converge másrápido.

x〈i+1〉 = (1− ω)x〈i〉 + ω

(bi −

∑i−1k=1 aikx

〈i+1〉k −

∑nk=1 aikx

〈i〉k

aii

)︸ ︷︷ ︸

xGAUSS−SEIDEL

En forma matricial esto es x〈i+1〉 = (1− ω)x〈i〉 + ωD−1(B − Lx〈i+1〉 − Ux〈i〉) siendo:

P = 1ωD + L

0 < ω < 2 (notar que si ω = 1 estamos en el método de Gauss-Seidel)

Convergencia: cuando A es simétrica (A = AT ) y de�nida positiva (xTAx > 0 ∀x 6= 0).

Ventajas Desventajas- obtener ω no es fácil

Teorema: si A es una matriz tribanda, es decir:

A =

a11 a12 0

a21. . .

. . .

. . .. . . an−1,n

0 an,n−1 ann

entonces:

ωoptimo =2

1 +√

1− ρ(Tj)2

donde ρ(Tj) es el mayor autovalor de la matriz T obtenida mediante el método de Jacobi.

2.4 Métodos iterativos no estacionarios

En estos métodos se aplica x〈i+1〉 = Tx〈i〉 + C, y las matrices T y C varían en cada iteración.

2.4.1 Método de los residuos mínimos

El método de los residuos mínimos consiste en buscar que R〈i+1〉 sea mínimo en cada iteración. Su fórmulaes:

x〈i+1〉 = x〈i〉 + αiR〈i〉

Siendo:

R〈i+1〉 = R〈i〉 − αiAR〈i〉

αi =[AR〈i〉]

TR〈i〉

[AR〈i〉]AR〈i〉

8

R〈0〉 = B −Ax〈0〉

Las iteraciones �nalizan cuando R〈i+1〉 < TOL.

Convergencia: cuando A es simétrica y de�nida positiva.

Ventajas Desventajas- fácil de programar - convergencia similar a Jacobi

2.4.2 Método del descenso más rápido

El método del descenso más rápido determina un mínimo local para una función de varias variables de laforma g : <n → <. Intuitivamente puede describirse así:

1. Evalúe g en una aproximación inicial x〈0〉.

2. Determine una dirección desde x〈0〉 que origine una disminución en el valor de g.

3. Desplace una cantidad apropiada hacia esta dirección y llame al nuevo vector x〈1〉.

4. Repita los pasos 1 a 3 reemplazando x〈0〉con x〈1〉.

La fórmula general es:

x〈i+1〉 = x〈i〉 + αiR〈i〉

siendo:

R〈0〉 = B −Ax〈0〉

αi = R〈i〉TR〈i〉

R〈i〉TAR〈i〉

R〈i+1〉 = R〈i〉 − αiAR〈i〉

Convergencia: cuando A es simétrica y de�nida positiva.

Ventajas Desventajas

- converge independientemente del x〈0〉 - convergencia lineal- fácil de programar - puede converger en algo que no es el mínimo de g

- mejor velocidad que MRM - no usa bien las direcciones más empinadas- menos cantidad de operaciones

2.4.3 Método de los gradientes conjugados

El método del gradiente conjugado es muy útil como método iterativo de aproximación para resolversistemas de gran tamaño con entradas no nulas. Supondremos que A es simétrica y de�nida positiva.

El cálculo multivariable nos dice que la dirección de máximo descenso en el valor de g(x) es la dirección dadapor −∇g(x); es decir, en la dirección del residual r = b−Ax.

x〈i+1〉 = x〈i〉 + αid〈i〉

con:

d〈0〉 = R〈0〉 = b−Ax〈0〉

αi = R〈i〉TR〈i〉

d〈i〉TAd〈i〉

R〈i+1〉 = R〈i〉 − αiAd〈i〉

β〈i+1〉 = R〈i+1〉T R〈i+1〉

R〈i〉T R〈i〉

d〈i+1〉 = R〈i+1〉 + β〈i+1〉 · d〈i〉

9

Convergencia: cuando A es simétrica y de�nida positiva.

Ventajas Desventajas- convergencia muy rápida para matrices grandes - suele ser inestable

- Si A ∈ Rn×n, n iteraciones alcanzan- Si A ∈ Rn×n tiene k autovalores repetidos, n− k iteraciones alcanzan

Si la matriz A es mal condicionada, este método es altamente susceptible a los errores de redondeo. Es poresto que existe el método de gradientes conjugados precondicionado. Un ejemplo de su uso es, en vezde resolver Ax = B, podemos resolver ATAx = ATB. Notar que en este caso A = ATA es simétrica y de�nidapositiva.

3 Ecuaciones de una variable

Sea el problema f(x) = 0. Resolver esta ecuación equivale a encontrar las raíces de la función f . Sin embargo,no siempre es posible despejar x e igualar a 0. Una forma de obtener la solución sería gra�cando la función yviendo donde ésta corta al eje X. Pero esto es poco práctico en casos complejos.

Si tenemos como datos a f(x), una tolerancia máxima y un intervalo inicial [a, b], podemos utilizar losmétodosde arranque (bisección y Regula Falsi) para achicar este intervalo, y luego utilizar otros métodos para aproximarla solución.

Teorema del valor intermedio: sea f una función continua en un intervalo [a, b] y supongamos que f(a) < f(b).Entonces para cada u tal que f(a) < u < f(b), existe al menos un c dentro de (a, b) tal que f(c) = u.

3.1 Método de la bisección

Figura 2: Bisección aplicadaen el rango [a1, b1].

Método de la bisección: se basa en el teorema del valor intermedio y en labúsqueda binaria. Si f es una función continua de�nida en [a, b] con f(a) yf(b) con signos diferentes, entonces existe p ∈ [a, b] tal que f(p) = 0. El métodorequiere dividir varias veces a la mitad el intervalo [a, b] y, en cada paso, localizara la mitad que contenga a p. Conviene elegir el intervalo inicial lo más pequeñoposible.Ejemplo: supongamos el intervalo inicial [a1, b1]. Luego p1 = a1+b1

2 . Si f(p1) = 0hemos llegado a la solución. Si f(a1) y f(p1) tienen el mismo signo, el nuevointervalo será [p1, b1]. Si f(a1) y f(p1) tienen distinto signo, el nuevo intervaloes [a1, p1].

Teorema: sea f ∈ C[a, b] y f(a) · f(b) < 0. El método de la bisección genera unasucesión p1, ..., pn que aproxima a un cero de f tal que:

|pn − p| ≤b− a

2n=⇒ n ≥ ln(b− a)− ln(TOL)

ln(2)

En este caso, tenemos que la condición de corte es:

TOL ≤ |b0 − a0|2n+1

Es importante destacar que para elegir el intervalo donde se encuentra la raíz debe veri�carse que f(a) ·f(b) < 0.Sin embargo, si esto no se cumple no implica que la raíz no exista (pues puede ser una raíz doble).

Ventajas Desventajas- fácil de entender - convergencia lenta- converge siempre - podemos rechazar una buena aproximación intermedia

3.2 Método del de punto �jo o de las aproximaciones sucesivas

10

Figura 3: Método del punto �-jo.

Un punto �jo de una función g es un número p que satisface g(p) = p.

Teorema de su�ciencia para la existencia y unicidad del punto �jo:

1. Si g ∈ C[a, b] y g(x) ∈ [a, b] para toda x ∈ [a, b] entonces g tiene un punto�jo en [a, b].

2. Si g′(x) existe en (a, b) y existe una constante 0 < k < 1 con |g′(x)| ≤ kpara toda x ∈ (a, b) entonces el punto �jo en [a, b] es único.

Método de iteración de punto �jo: supongamos que deseamos resolverf(x) = 0. Para hallar el x tal que g(x) = x escogemos una aproximación inicialx0 y generamos la sucesión x1, ..., xn haciendo

xi+1 = g (xi) para i ≥ 0

Si la secuencia converge en x y g es continua, entonces obtenemos una solución con x = g(x). El error está dadopor:

|xn − x| ≤ kn|b− a|

Ventajas Desventajas- si k ≈ 0 converge rápidamente - convergencia lineal

- si k ≈ 1 converge lentamente

3.3 Método de Newton-Raphson

Figura 4: Una iteracióndel método de Newton-Raphson.

El método de Newton-Raphson es una de las técnicas más poderosas que exis-ten para resolver un problema del tipo f(x) = 0. Este método comienza con unaaproximación inicial x0 y genera la sucesión x1, ..., xn de�nida por:

x〈i+1〉 = x〈i〉 − f(x〈i〉)

f ′(x〈i〉)

El método obtiene las aproximaciones utilizando tangentes sucesivas. Comenzandocon x0, la aproximación x1 es la intersección entre la línea tangente a la grá�ca def en (x0, f(x0)) y el eje X. La aproximación x2 es la intersección entre la tangentea la grá�ca de f en (x1, f(x1)) y el eje X, y así sucesivamente.

Es importante notar que no es posible continuar con este método si f ′(xn−1) = 0para alguna n. Además, f ′′(x) debe estar acotada.

La deducción de este método proviene del desarrollo por Taylor:

f(x) = f(x) + (x− x)f ′(x) + · · · = 0

(x− x)f ′(x) = −f(x)

x = x− f(x)

f ′(x)

Teorema de convergencia: sea f ∈ C2[a, b]. Si x ∈ [a, b] es tal que f(x) = 0 y f ′(x) 6= 0, entonces existe δ > 0 talque el método de Newton genera una sucesión x1, ..., xn que converge a p para cualquier aproximación inicialx0 ∈ [x− δ, x+ δ].

Ventajas Desventajas- muy poderoso - necesitamos conocer la derivada de f

- convergencia cuadrática para raíces simples - necesita una buena aproximación inicial- convergencia lineal para raíces dobles

3.4 Método de la secante

11

Figura 5: Método de la se-cante.

Si queremos evitarnos el problema de evaluar la derivada en el método de New-

ton, podemos aproximarla mediante la de�nición: f ′(xi) ≈ f(xi)−f(xi−1)xi−xi−1

. Entoncestenemos:

xi+1 = xi −f(xi)(xi − xi−1)

f(xi)− f(xi−1)

La técnica que se utiliza en esta fórmula se llama método de la secante. Co-menzando con las dos aproximaciones iniciales x0 y x1, la aproximación x2 es laintersección entre la línea que une (x0, f(x0)) y (x1, f(x1)) con el eje X.

Ventajas Desventajas- es más rápido que el método

del punto �jo- es más lento que el método de

Newton- fácil de usar

- no necesitamos conocer f ′

3.5 Método de la posición falsa / Regla falsa

Figura 6: Método de la regula Falsi.

El método de la posición falsa combina el método de bisección y el método de la secante, pero ofrece unaprueba para asegurarnos que la raíz queda entre dos iteraciones sucesivas.

Primero elegimos p0 y p1 tales que f(p0) · f(p1) < 0. p2 será la intersección en X de la recta secante. Luegocalculamos f(p1) · f(p2), si es mayor a 0 la raíz está entre p0 y p1, sino está entre p1 y p2. Su fórmula general es:

pn = an −f(an)(bn − an)

f(bn)− f(an)ó pn = bn −

f(bn)(bn − an)

f(bn)− f(an)

Ventajas Desventajas- converge siempre - requiere más cálculos que el método de la secante

- más rápido que el método de la bisección - converge lentamente- puede fallar si el denominador se anula

3.6 Método 42 de Aitken

Diferencias progresivas: dada la sucesión p0, ..., pn la diferencia progresiva4pn está dada por4pn = pn+1−pncon n ≥ 0.

Supongamos que p0, ..., pn es una sucesión linealmente convergente con un límite p. El método 42 de Aitkense basa en la suposición de que la sucesión p0, ..., pn de�nida por

pn = pn −(pn+1 − pn)2

pn+2 − 2pn+1 + pn= pn −

(4pn)2

42pn

converge más rápidamente a p que la sucesión original.

Ventajas Desventajas- convergencia acelerada - poco práctico para programar

- no evaluamos la derivada

12

3.7 Método de Ste�ensen

Existe una mejora para el método de Aitken, que se basa en aplicar este método para una sucesión dada poraproximaciones sucesivas, y se conoce como método de Ste�ensen.

La sucesión que genera está dada por:

p〈0〉0 p

〈1〉0 p

〈2〉0 · · ·

p〈0〉1 p

〈1〉1 p

〈2〉1 · · ·

p〈0〉2

Ventajas Desventajas- Convergencia cuadrática

Algoritmo 1 Método de Ste�ensen

función steffensen(p0,TOL,itermax,g(p)):

iter = 1

while (iter < itermax):

p1 = g(p0)

p2 = g(p1)

p = p0 - (p1 - p0)^2/(p2 - 2p1 + p0)

if (|p - p0| < TOL):

return p

else:

iter = iter + 1

p0 = p

return 'El método fracasó después de'+itermax+'iteraciones.'

4 Sistemas de ecuaciones no lineales

Un sistema de ecuaciones no lineales tiene la formaf1(x1, . . . , xn) = 0

f2(x1, . . . , xn) = 0...

fn(x1, . . . , xn) = 0

=⇒ F(x1, . . . , xn) = (f1, . . . , fn)T = 0

4.1 Adaptación del método de Jacobi

Ejemplo: supongamos el sistema dado por

{f(x1, x2) = x2

1 + x22 − 1 = 0

g(x1, x2) = x21 − 2x1 − x2 + 1 = 0

Podemos resolverlo mediante una adaptación del método de Jacobi a sistemas de ecuaciones mediante:

x〈i+1〉1 = ±

√1−

(x〈i〉2

)2

x〈i+1〉2 =

(x〈i〉1

)2

− 2x〈i〉1 + 1

4.2 Adaptación del método de Gauss-Seidel

Ejemplo: supongamos el sistema dado por

{f(x1, x2) = x2

1 + x22 − 1 = 0

g(x1, x2) = x21 − 2x1 − x2 + 1 = 0

13

Podemos resolverlo mediante una adaptación del método de Gauss-Seidel a sistemas de ecuaciones mediante:

x〈i+1〉1 = ±

√1−

(x〈i〉2

)2

x〈i+1〉2 =

(x〈i+1〉1

)2

− 2x〈i+1〉1 + 1

4.3 Método de Newton

El método de Newton para sistemas no lineales consiste en

x〈i+1〉 = x〈i〉 − J(x〈i〉)−1

· F(x〈i〉)

siendo J(x) la matriz jacobiana de F (x).

Ventajas Desventajas- convergencia cuadrática - debe conocerse un valor inicial bueno

- necesita calcular e invertir J(x) en cada paso- O(n3) pasos

4.4 Método de Broyden

El método de Broyden es una variante del método de Newton. En este método se reemplaza la matrizjacobiana con una matriz de aproximación que se actualiza en cada iteración.

Supongamos que se da una aproximación inicial x〈0〉 a la solución p de F (x) = 0. Calculamos x〈1〉 como enel método de Newton, y para calcular x〈2〉 nos apartamos de Newton y examinamos el método de la secantepara una ecuación no lineal: reemplazamos la matriz J(x〈1〉) por una matriz A que tiene la propiedad de queA1

(x〈1〉 − x〈0〉

)= F

(x〈1〉

)− F

(x〈0〉

), es decir que x〈2〉 = x〈1〉 −A−1

1 F(x〈1〉

). En general, calculamos:

x〈i+1〉 = x〈i〉 −A−1i F

(x〈i〉)

siendo

Ai = Ai−1 +F(x〈i〉)− F

(x〈i+1〉)−Ai−1

(x〈i〉 − x〈i+1〉)∥∥x〈i〉 − x〈i+1〉

∥∥2

2

Ventajas Desventajas- no hay que invertir matrices - hay que invertir una matriz al comienzo

- no hay que calcular el jacobiano - convergencia superlineal- O(n2) pasos - debe conocerse un valor inicial bueno

5 Interpolación

En ingeniería y algunas ciencias es frecuente disponer de un cierto número de puntos obtenidos por muestreo oa partir de un experimento y pretender construir una función que los ajuste. Se denomina interpolación a laobtención de nuevos puntos partiendo del conocimiento de un conjunto discreto de puntos.

Polinomios: funciones de la forma Pn(x) = a0 + a1x1 + a2x

2 + · · ·+ anxn. Dado que las derivadas e integrales

de los polinomios son fáciles de calcular, éstos se usan para aproximar funciones continuas.

Para curvas que no pueden de�nirse mediante polinomios contamos con curvas paramétricas llamadas curvasde Bezier.

Supongamos que tenemos los puntos y0 = f(x0), y1 = f(x1),...,yn = f(xn) y queremos obtener un polinomio degrado n que pase lo más cerca posible de y0, ..., yn. Lo que podemos hacer es plantear el sistema de ecuaciones:

a0 + a1x0 + ...+ anx

n0 = y0

...

a0 + a1xn + ...+ anxnn = yn

=⇒

1 x0 · · · xn01 x1 · · · xn1...

.... . .

...1 xn · · · xnn

a0

...an

=

y0

...yn

14

La matriz de este sistema se llama matriz de Vandermonde. Esta matriz es mal condicionada. Por lo tanto,este generalmente no es un buen método.

Fenómeno de Runge: se da cuando aparecen oscilaciones no deseadas en los extremos del intervalo a interpolar.

Figura 7: Fenómeno de Runge.

5.1 Interpolación y polinomio de Lagrange

Teorema: si x0, . . . , xn son n + 1 números distintos y si f es una función cuyos valores están dados en esosnúmeros, entonces existe un único polinomio P (x) de grado a lo sumo n que satisface f(xk) = P (xk) conk = 0, 1, ..., n.

Este polinomio está dado por:

Ln;i =

n∏j=0,j 6=i

(x− xj)(xi − xj)

Pn(x) =

n∑i=0

[f(xi) · Ln;i]

Ventajas Desventajas- la distribución de puntos no incide - O(n2) operaciones para evaluar Pn(x)

- es sencillo - agregar (xn+1, yn+1) requiere recular todo- es inestable

5.2 Método de Newton

El método de las diferencias divididas de Newton consiste en de�nir

f(xi) = yi

f(xi, xi+1) = f(xi+1)−f(xi)xi+1−xi

f(xi, xi+1, xi+2) = f(xi+1,xi+2)−f(xi,xi+1)xi+2−xi

...

f(xk, . . . , xn) = f(xk+1,...,xn)−f(xk,...,xn−1)xn−xk

El método de las diferencias divididas �progresivas� de Newton de grado 3 consiste en:

P (x) = f(x0) + f(x0, x1)(x− x0) + f(x0, x1, x2)(x− x0)(x− x1) + f(x0, x1, x2, x3)(x− x0)(x− x1)(x− x2)

donde x0 > x1 > x2 > x3.

El método de las diferencias divididas �regresivas� de Newton de grado 3 consiste en:

P (x) = f(x3) + f(x2, x3)(x− x3) + f(x1, x2, x3)(x− x3)(x− x2) + f(x0, x1, x2, x3)(x− x3)(x− x2)(x− x1)

donde x0 < x1 < x2 < x3.

Ventajas Desventajas- agregar un punto inicial o �nal es muy sencillo - O(n2) operaciones para obtener f(xk, . . . , xn)

- O(n) operaciones para evaluar Pn(x) - agregar un punto intermedio requiere recalcular todo- se exigen datos xi ordenados

15

5.3 Interpolación baricéntrica de Lagrange

Sea el polinomio genérico L(x) =∏ni=0(x− xi)

Sean los pesos baricéntricos

wi =1∏n

k=0,k 6=i xi − xkpara todo i = 0...n

Entonces podemos de�nir al polinomio interpolante como:

Pn(x) = L(x) ·n∑i=0

[f(xi)

wix− xi

]Este es el llamado método mejorado de Lagrange.

Ventajas Desventajas- O(n) operaciones para evaluar Pn(x)

- O(n) operaciones para agregar un par de datos- wi no depende de f(xn+1)

- no es necesario ordenar los datos

El método baricéntrico de Lagrange consiste en:

Pn(x) =

∑ni=0 f(xi)

wix−xi∑n

i=0wix−xi

Ventajas Desventajas- O(n) operaciones para agregar un par de datos - es inestable

- es más estable que Lagrange original

5.4 Interpolación de Hermite

La interpolación de Hermite se utiliza cuando conocemos el valor de la función en el punto y la derivada.

Teorema: sea f ∈ C1[a, b] y sean x0, . . . , xn ∈ [a, b] distintos, el polinomio único que concuerda con f(xi) yf ′(xi) para i = 0 . . . n es el polinomio de Hermite de grado, a lo sumo, 2n+ 1, que está dado por

H2n+1(x) =

n∑i=0

f(xi)Hn;i(x) +

n∑i=0

f ′(xi)Hn;i(x)

donde

Hn;i(x) =[1− 2(x− xi)L′n;i(xi)

][Ln;i(x)]

2

Hn;i(x) = (x− xi) [Ln;i(x)]2

Este polinomio también se puede calcular mediante el método de diferencias divididas Newton. De�nimos unasucesión {z0, . . . , z2n+1} dada por z2i = z2i+1 = xi, con i = 0 . . . n. Entonces:

H2n+1(x) = f(z0) +

2n+1∑k=1

f(z0, . . . , zk) ·k−1∏j=0

(x− zj)

Y podemos formar la tabla correspondiente:

zi f(zi) f(zi, zi+1) f(zi, zi+1, zi+2) f(zi, zi+1, zi+2, zi+3)z0 = x0 f(z0) = f(x0) f(z0, z1) = f ′(x0)z1 = x0 f(z1) = f(x0) f(z1, z2) f(z0, z1, z2) f(z0, z1, z2, z3)z2 = x1 f(z2) = f(x1) f(z2, z3) = f ′(x1) f(z1, z2, z3)z3 = x1 f(z3) = f(x1) f(z3, z4)

Ventajas Desventajas- procedimiento tedioso incluso

para valores chicos de n

16

5.5 Interpolación por �splines�

Figura 8: Spline.

La interpolación por �splines� consiste en interpolar datos mediante segmentosde curvas. En este caso los segmentos serán polinomios de tercer grado, denominadostrazadores cúbicos. Sean los n + 1 puntos, de�nimos las n curvas interpolantescomo:

Si(x) = ai + bi(x− xi) + ci(x− xi)2 + di(x− xi)3 con i = 0..n− 1

Este polinomio debe cumplir las siguientes condiciones:

1. Si(xi) = f(xi) para i = 0, . . . , n (la curva pasa por los puntos)

2. Si+1(xi+1) = Si(xi+1) para i = 0, . . . , n− 2 (Si es continua)

3. S′i+1(xi+1) = S′i(xi+1) para i = 0, . . . , n− 2 (S′i es continua)

4. S′′i+1(xi+1) = S′′i (xi+1) para i = 0, . . . , n− 2 (S′′i es continua)

5. Alguna de las siguientes condiciones de borde:

a) Frontera libre / natural: S′′0 (x0) = S′′n−1(xn) = S′′n(xn) = 0

b) Frontera sujeta:

{S′0(x0) = f ′(x0) = α

S′n−1(xn) = S′n(xn) = f ′(xn) = β

Para hallar los coe�cientes ai, bi, ci y di con spline de frontera libre debe plantearse:1

ai = f(xi)

hi = xi+1 − xi

1 0 0 · · · 0

h0 2(h0 + h1) h1

.

.

.

0 h1 2(h1 + h2) h2

.

.

.

... 0

hn−2 2(hn−2 + hn−1) hn−1

0 · · · 0 0 1

c0c1...

cn

=

0

3[fN (x1, x2)− fN (x0, x1)]

.

.

.

3[fN (xn−1, xn)− fN (xn−2, xn−1)]0

bi = fN (xi, xi+1)− hi3 (2ci + ci+1)

di = ci+1−ci3hi

Para hallar los coe�cientes ai, bi, ci y di con spline de frontera sujeta debe plantearse:

ai = f(xi)

hi = xi+1 − xi

2h0 h0 0 · · · 0

h0 2(h0 + h1) h1

.

.

.

0 h1 2(h1 + h2) h2

.

.

.

... 0

hn−2 2(hn−2 + hn−1) hn−1

0 · · · 0 hn−1 2hn−1

c0c1...

cn

=

3fN (x0, x1)− 3f ′(a)

3fN (x1, x2) = 3fN (x0, x1)

.

.

.

3fN (xn−1, xn)− 3fN (xn−2, xn−1)3f ′(b)− 3fN (xn−1, xn)

bi = fN (xi, xi+1)− hi3 (2ci + ci+1)

di = ci+1−ci3hi

La interpolación con spline de frontera sujeta es más precisa que la natural, pero requiere los valores de laderivada en los extremos, o al menos buenas aproximaciones.

Puede demostrarse que las matrices asociadas a los dos sistemas mencionados son estrictamente diagonal do-minantes, de�nidas positivas, tribandas y simétricas, y que la solución de los dos es única.

1fN denota la diferencia dividida de Newton

17

6 Ajuste de funciones y mejor aproximación

6.1 Mejor aproximación

Figura 9: Ajuste.

Si la cantidad de puntos xi dados es muy grande, interpolar mediante polinomioscrea curvas de alto grado que se vuelven muy inestables en los extremos. Esto sepuede resolver, en parte, mediante interpolaciones fragmentadas o segmentos de curvas(polinomios de Hermite o splines). Sin embargo, una de las condiciones fundamentalespara estos métodos es que los puntos xi sean distintos.

Cuando para un mismo xi tenemos varios valores de f(xi) podemos construir unacurva que ajuste lo mejor posible los datos disponibles, sin que la curva pase por lospuntos dados.

La aproximación la hacemos con una función g(x) =∑mi=0 ciφi(x), donde m < n.

6.2 Método de los cuadrados mínimos

El problema general de aproximar un conjunto de datos distintos (x1, y1), . . . , (xm, ym) con un polinomioPn(x) = a0 + a1x + a2x

2 + · · · + anxn de grado n < m − 1 puede resolverse mediante el método de los

cuadrados mínimos. Este método consiste en resolver las n+ 1 ecuaciones normales para las n+ 1 incógnitasaj .

n∑k=0

ak

m∑i=1

xj+ki =

m∑i=1

yixji para cada j = 0, . . . , n

En forma matricial esto es∑mi=1 x

0i

∑mi=1 x

1i · · ·

∑mi=1 x

ni∑m

i=1 x1i

∑mi=1 x

2i

......

. . .∑mi=1 x

ni · · ·

∑mi=1 x

2ni

a0

a1

...an

=

∑mi=1 yix

0i∑m

i=1 yix1i

...∑mi=1 yix

ni

Nótese que el coe�ciente A11 nos dice la cantidad de puntos que intervienen en el ajuste, y que la matriz essimétrica y de�nida positiva, y es similar a una matriz de Vandermonde. De ahí que cualquier ajuste de curvashecho con polinomios es un problema mal condicionado, y por ello no se recomienda trabajar con polinomiosde grado mayor a 4 o 5.

Puede demostrarse que las ecuaciones normales tienen una solución única, a condición de que las xi seandistintas.

Si sospechamos que los datos (xi, yi) tienen una relación exponencial, podemos proponer la función de ajustey = aebx.

7 Diferenciación numérica

Dado que no siempre las soluciones analíticas al problema de diferenciar son aplicables a los problemas, y nosiempre existe tal solución numérica, existen métodos numéricos que aproximan las soluciones con distinto gradode exactitud.

Sin embargo, debe notarse que la diferenciación numérica es inestable y depende mucho de la precisión utilizada.

7.1 Aproximación por diferencias

Se pueden clasi�car según 3 tipos:

1. Diferencias progresivas: f ′(x) ≈ f(x+h)−f(x)h . Su orden de convergencia es O(h).

2. Diferencias regresivas: f ′(x) ≈ f(x)−f(x−h)h . Su orden de convergencia es O(h).

18

3. Diferencias centradas: f ′(x) ≈ f(x+h)−f(x−h)2h . Su orden de convergencia es O(h2). Es el que mejor

aproxima de los tres.

Tener en cuenta que achicar el paso h en los tres algoritmos anteriores no siempre es una manera de obteneruna aproximación mejor, ya que empieza a incidir el error de redondeo, dado que el numerador se vuelve cadavez más chico. Además, no es posible calcular un valor óptimo para h.

7.2 Método de los tres y cinco puntos

El algoritmo del método de los tres puntos es:

f ′(x) ≈ −3f(x) + 4f(x+ h)− f(x+ 2h)

2h

Su orden de convergencia es O(h2).

El algoritmo llamado método de los cinco puntos es:

f ′(x) =f(x− 2h)− 8f(x− h) + 8f(x+ h)− f(x+ 2h)

12h+h4

30f (5)(ξ)

Su orden de convergencia es O(h4), es decir, proporcional a la derivada quinta, lo que lo hace muy preciso.

7.3 Extrapolación de Richardson

Elmétodo de extrapolación de Richardson es aplicable solo si E(h) = k1h1 +k2h21 +k3h

31 + · · · , y se puede

generalizar de la siguiente manera:

Nj(h) = Nj−1

(h

q

)+Nj−1

(hq

)−Nj−1(h)

qj−1 − 1

siendo N1 el resultado de aproximar la derivada con alguno de los métodos mencionados anteriormente (porejemplo, diferencias progresivas).

Ejemplo: aproximar f ′(1) siendo f(x) = sin(π3x)con extrapolación de Richardson, con q = 2.

hi N1 = f(1+h)−f(1)h N2 = N1(h2 ) +

N1(h2 )−N1(h)

21−1 N3 = N2

(h2

)− N2(h2 )−N2(h)

22−1 N4

0,2 N1(0, 2) = 0, 42520,1 N1(0, 1) = 0, 4752 N2(0, 2) = 0, 52520,05 N1(0, 05) = 0, 4996 N2(0, 1) = 0, 5240 N3(0, 2) = 0, 52360,025 N1(0, 025) = 0, 5117 N2(0, 05) = 0, 5238 N3(0, 1) = 0, 5237 N4(0, 2) = 0, 5237

La extrapolación puede aplicarse si el error de truncamiento es∑n−1j=1 kjh

αj +O(hαm).

8 Integración numérica

Cuando necesitamos obtener el valor de una integral de�nida, pueden ocurrir dos cosas: que la función no tengauna antiderivada explícita, o que ésta no sea fácil de obtener. Entonces podemos obtener una aproximaciónutilizando una cuadratura.

Cuadratura numérica:∫ baf(x) dx ≈

∑ni=1 cif(xi), donde ci son los �coe�cientes de peso� y los f(xi) son los

�puntos de cuadratura�.

Los siguientes métodos aproximan la función f(x) con un polinomio interpolante, cuyas antiderivadas son fácilesde calcular.

19

8.1 Fórmulas cerradas de Newton-Cotes

Fórmula cerrada de Newton-Cotes: la fórmula cerrada de n+ 1 puntos de Newton-Cotes utiliza los nodosequidistantes xi = x0 + ih, para i = 0..n, donde x0 = a, xn = b y h = b−a

n . Se llama �cerrada� porque se incluyenlos extremos del intervalo como nodos.

Regla del rectángulo:∫ b

a

f(x) dx ≈ (b− a) · f(a)︸ ︷︷ ︸por defecto

o

∫ b

a

f(x) dx ≈ (b− a) · f(b)︸ ︷︷ ︸por exceso

Su orden de convergencia es O(h). Esta regla da un resultado exacto para funciones del tipo f(x) = c.

Regla del trapecio (n=1): se obtiene al integrar en [a, b] el primer polinomio de Lagrange. Se aproximael área bajo una función f de valores positivos con un trapecio.∫ x1

x0

f(x) dx =h

2· [f(x0) + f(x1)]− h3

12f ′′(ξ)

siendo h = b− a. Su convergencia es O(h2). Esta regla da un resultado exacto para polinomios de grado1 o menos.

Regla de Simpson (n=2): se obtiene al integrar el segundo polinomio de Lagrange.∫ x2

x0

f(x) dx =h

3

[f(a) + 4f

(a+ b

2

)+ f(b)

]− h5

90f (4)(ξ)

siendo h = b−a2 . Su convergencia es O(h4). Esta regla proporciona resultados exactos al aplicarla a poli-

nomios de grado 3 o menos.

Regla de tres octavos de Simpson (n=3):∫ x3

x0

f(x) dx =3h

8[f(x0) + 3f(x1) + 3f(x2) + f(x3)]− 3h5

80f (4)(ξ)

siendo h = b−a3 .

8.2 Fórmulas abiertas de Newton-Cotes

Fórmula abierta de Newton-Cotes: la fórmula abierta de n + 1 puntos de Newton-Cotes utiliza los nodosequidistantes xi = x0 + ih, para i = 0..n, donde x0 = a + h, xn = b − h y h = b−a

n+2 . Se llama �abierta� porqueno se incluyen los extremos del intervalo como nodos.

Regla del punto medio (n=0):∫ x1

x0

f(x) dx = 2hf(x0) +h3

3f ′′(ξ)

= (x1 − x0) · f(x0 + x1

2

)

8.3 Métodos compuestos

En general, las fórmulas de Newton-Cotes no son adecuadas para utilizarse en intervalos de integración grandes.Para estos casos se utilizan los siguientes métodos, que tienen la ventaja de que son estables respecto del errorde redondeo. Todos estos algoritmos son O(h4), pero tienen una desventaja: el tiempo de procesamiento. Estoquiere decir que reducir el paso h mejora la precisión, pero llegará un punto en que la representación numéricanos impedirá a�nar el paso. Además, cada vez que querramos a�nar el paso, deberemos calcular todo otra vez.

20

Regla compuesta del rectángulo:∫ b

a

f(x) dx ≈ h

[n−1∑i=1

f(xj) + f(b)

]

siendo h = b−an y xj = a+ jh.

Regla compuesta del trapecio: sea f ∈ C2[a, b]. Entonces la fórmula compuesta del trapecio para nsubintervalos puede escribirse como

∫ b

a

f(x) dx =h

2

f(a) + 2

n−1∑j=1

f(xj) + f(b)

− b− a12

h2f ′′(µ)

siendo h = b−an y xj = a+ jh para cada j = 0..n.

Regla compuesta de Simpson: sea f ∈ C4[a, b] y n par. Entonces la fórmula compuesta de Simpsonpara n subintervalos puede escribirse como

∫ b

a

f(x) dx =h

3

f(a) + 2

n2−1∑j=1

f(x2j) + 4

n2∑j=1

f(x2j−1) + f(b)

− b− a180

h4f (4)(µ)

siendo h = b−an y xj = a+ jh para cada j = 0..n.

Regla compuesta del punto medio: sea f ∈ C2[a, b] y n par. Entonces la fórmula compuesta del puntomedio para n+ 2 subintervalos puede escribirse como

∫ b

a

f(x) dx = 2h

n2∑j=0

f(x2j) +b− a

6h2f ′′(µ)

siendo h = b−an+2 y xj = a+ (j + 1)h para cada j = −1..(n+ 1).

8.4 Método de Romberg

El método de integración de Romberg utiliza la regla compuesta del trapecio para obtener aproximacionespreliminares y luego se aplica el proceso de extrapolación de Richardson para mejorar las aproximaciones. Si severi�ca que f ∈ C2(k+1)[a, b], la fórmula está dada por

Rk,j = Rk,j−1 +Rk,j−1 −Rk−1,j−1

4j−1 − 1

donde k = 2, 3, . . . , n y j = 2, . . . , k. Su convergencia es O(h2jk ). Los resultados generados con éstas fórmulas se

incluyen en la siguiente tabla.

R1,1

R2,1 R2,2

......

. . .

Rn,1 Rn,2 · · · Rn,n

El �mejor� valor es Rn,n. Otra ventaja de este método es que permite agregar una nueva �la a la tabla con sólohacer una aplicación más de la regla compuesta del trapecio (y luego promediar los demás valores).

8.5 Cuadratura de Gauss

En todas las fórmulas de Newton-Cotes se emplean valores de la función en puntos equidistantes. Esta prácticaes útil cuando utilizamos dichos métodos en reglas compuestas, pero esta restricción puede afectar la exactitudde la aproximación.

El método de cuadratura de Gauss selecciona los puntos de la evaluación de manera óptima y no en unaforma igualmente espaciada. Recordando la fórmula de una cuadratura

∑ni=1 cif(xi), los valores xi son las raíces

del polinomio de Legendre, y las constantes ci se obtienen operando con los xi. Estos valores están tabulados:

21

n xi ci

1 x0 = 0 c0 = 22 x0 = 0, 57735 c0 = 1

x1 = −0, 57735 c1 = 13 x0 = 0, 77459 c0 = 0, 55555

x1 = 0 c1 = 0, 88888x2 = −0, 77459 c2 = 0, 55555

......

...

La fórmula para este método es∫ b

a

f(x) dx =

∫ 1

−1

f

((b− a)t+ (b+ a)

2

)b− a

2dt

Este método arroja resultados exactos cuando g ≤ 2n− 1, donde g es el grado del polinomio a integrar, y n esla cantidad de puntos de Gauss. Además, el error cometido es proporcional a la derivada de orden 2n.

Ventajas Desventajas- pocas evaluaciones del polinomio

- fácil de programar- sólo desconocemos el error de redondeo

8.6 Integrales múltiples

Dada la integral∫∫Af(x, y) dxdy, dondeA es una región rectangular del plano tal queA = {(x, y) : a ≤ x ≤ b ∧ c ≤ y ≤ d},

podemos obtener una aproximación utilizando una adaptación de los métodos anteriormente estudiados.

Método del trapecio∫ d

c

∫ b

a

f(x, y) dxdy ≈ (b− a)(d− c)4

[f(a, c) + f(a, d) + f(b, c) + f(b, d)]

Método de Simpson

∫ d

c

∫ b

a

f(x, y) dxdy ≈(b− a)(d− c)

36{f(x0, y0) + f(x0, y2) + f(x2, y0) + f(x2, y2)

+4 [f(x0, y1) + f(x1, y0) + f(x1, y2) + f(x2, y1) + 4f(x1, y1)]}

donde x0 = a, x1 = a+b2 , x2 = b, y0 = c, y1 = c+d

2 , y2 = d.

Método de cuadratura de Gauss

∫ d

c

∫ b

a

f(x, y) dxdy ≈ (b− a)(d− c)4

n∑i=1

m∑j=1

cicjf(xi, yj)

con xi = b−a2 ti + b+a

2 , yj = d−c2 tj + d+c

2 , siendo ti, tj las raíces de los polinomios de Legendre y ci, cj loscoe�cientes de peso.

9 Ecuaciones diferenciales ordinarias

Estudiaremos cómo aproximar la solución y(t) a un problema de la forma{dydt = f(t, y) para a ≤ t ≤ by(a) = α

Condición de Lipschitz: una función f(t, y) satisface la condición de Lipschitz en la variable y en un conjuntoD ⊂ R2 si existe una constante L > 0 tal que

|f(t, y1)− f(t, y2)||y1 − y2|

≤ L para todo (t, y1), (t, y2) ∈ D

22

Teorema: si f(t, y) está de�nida en un conjunto convexo D ⊂ R2 y existe una constante L > 0 tal que∣∣∣∂f(t,y)∂y

∣∣∣ ≤ L para toda (t, y) ∈ D, entonces f satisface la condición de Lipschitz.

Teorema (de su�ciencia): supongamos que D = {(t, y)|a ≤ t ≤ b;−∞ < y <∞} y que f(t, y) es continua en D.Si f satisface la condición de Lipschitz, entonces el problema de valor inicial y′(t) = f(t, y), a ≤ t ≤ b, y(a) = αtiene solución única.

Problema bien planteado: el problema de valor inicial dydt = f(t, y), a ≤ t ≤ b, y(a) = α es bien planteado si:

1. El problema tiene solución única y(t),

2. Si perturbamos el problema, la solución también se perturbará, pero poco.

Los siguientes métodos no nos proporcionan la función y(t), sino que nos da aproximaciones a y(ti) para puntosa ≤ ti ≤ b igualmente espaciados. Si queremos valores intermedios deberemos interpolarlos, generalmenteutilizando el método de Hermite.

9.1 Métodos de un paso

En los métodos de un paso la aproximación del punto de red ti+1 contiene información proveniente de unosolo de los puntos anteriores de red ti.

9.1.1 Método de Euler

El método de Euler es un caso particular del método de Taylor para n = 1. Este método no es lo su�cientementeexacto para utilizarlo en la vida real, pero resulta simple para analizarlo. Sin embargo, son métodos estables.

Método de Euler explícito: siendo el paso h = b−aN , donde N es la cantidad de intervalos, la expresión

de este método es:

wi = y(ti)

wi+1 = wi + h · f(ti, wi) parai = 0, 1, . . . , N − 1

El error local es O(h). Converge siempre.

Método de Euler implícito: siendo el paso h = b−aN , donde N es la cantidad de intervalos, la expresión

de este método es:

wi = y(ti)

wi+1 = wi + h · f(ti+1, wi+1) para i = 0, 1, . . . , N − 1

El error local es O(h). El método de Euler implícito suele dar mejores resultados que el explícito (aunqueesto no siempre es así). La desventaja del método implícito es que no siempre es posible implementarlo.

Método predictor-corrector de Euler: este método consiste en obtener una primera aproximacióncon el método explícito, y con ésta obtener una nueva aproximación con el método implícito, que�corrige� la anterior.

w∗i+1 = wi + h · f(ti, wi)

wi+1 = wi + h · f(ti, w∗i+1)

El error local de este método es O(h).

9.1.2 Métodos de Taylor de orden superior

El método de Taylor de orden n tiene la siguiente expresión:

w0 = α

wi = y(ti)

wi+1 = wi + h · f(ti, wi) +h2

2f ′(ti, wi) + · · ·+ hn

n!f (n−1)(ti, wi) para i = 0, . . . , n− 1

Puede demostrarse que si f ∈ Cn+1[a, b], entonces el error de truncamiento es O(hn). Este método rara vez seemplea en la práctica, pues tiene la desventaja de requerir el cálculo y evaluación de las derivadas de f(t, y).

23

9.1.3 Métodos de Runge-Kutta

Teorema: sea f(t, y) ∈ Cn+1 en D = {(t, y)|a ≤ t ≤ b, c ≤ y ≤ d} y sea (t0, y0) ∈ D. Entonces, para toda(t, y) ∈ D, existe ξ ∈ [t0, t] y µ ∈ [y0, y] con f(t, y) = Pn(t, y) +Rn(t, y) tal que Pn(t, y) es el n-ésimo polinomiode Taylor en dos variables para la función f alrededor de (t0, y0), y Rn(t, y) es el término residual asociado aPn(t, y).

Los métodos de Runge-Kutta se basan en aproximar el polinomio de Taylor para una variable mediantepolinomios de Taylor de dos variables. Existen varios métodos de Runge Kutta, que se clasi�can según su ordende convergencia. Los más sencillos son los de orden 2:

Método del punto medio:

w0 = α

wi+1 = wi + h · f(ti +

h

2, wi +

h

2· f(ti, wi)

)para cada i = 0, 1, . . . , N − 1

Método modi�cado de Euler:

w0 = α

wi+1 = wi +h

2[f(ti, wi) + f (ti+1, wi + h · f(ti, wi))] para cada i = 0, 1, . . . , N − 1

Método de Crank-Nicolson (implícito):

w0 = α

wi+1 = wi +h

2[f(ti, wi) + f(ti+1, wi+1)] para i = 0, 1, . . . , N − 1

Método de Heun:

w0 = α

wi+1 = wi +h

4

[f(ti, wi) + 3f

(ti +

2

3h,wi +

2

3h · f(ti, wi)

)]para i = 0, 1, . . . , N − 1

Para obtener métodos con mayor orden de convergencia se aplica el teorema antes mencionado, y con él seobtiene el método de Runge-Kutta de orden 4, que es muy preciso siempre y cuando la función y(t) tengaal menos cinco derivadas continuas:

w0 = α

k1 = h · f(ti, wi)

k2 = h · f(ti +

h

2, wi +

1

2· k1

)k3 = h · f

(ti +

h

2, wi +

1

2· k2

)k4 = h · f(ti+1, wi + k3)

wi+1 = wi +1

6(k1 + 2k2 + 2k3 + k4) para cada i = 0, 1, . . . , N − 1

9.2 Métodos multipasos

Los métodos multipasos son aquellos que emplean la aproximación en más de uno de los puntos de redprecedentes para determinar la aproximación en el siguiente punto. Se pueden deducir de las series de Taylor odel polinomio interpolante de Lagrange.

Para obtener wi, wi−1, wi−2, . . . debemos utilizar un método de paso simple del mismo orden que el método depaso múltiple.

24

9.2.1 Métodos explícitos de Adams-Bashforth

Dado un orden de convergencia p, los métodos explícitos de Adams-Bashforth usan los puntos wi, wi−1,. . ., wi+1−p para obtener el wi+1. El paso no puede ser arbitrario.

Método de Adams-Bashforth de orden 2 (2 pasos):

w0 = α

w1 = α1

wi+1 = wi +h

2[3f(ti, wi)− f(ti−1, wi−1)] para i = 1, 2, . . . , N − 1

Método de Adams-Bashforth de orden 4 (4 pasos):

w0 = α

w1 = α1

w2 = α2

w3 = α3

wi+1 = wi +h

24[55f(ti, wi)− 59f(ti−1, wi−1) + 37f(ti−2, wi−2)− 9f(ti−3, wi−3)] para i = 3, 4, . . . , N − 1

9.2.2 Métodos implícitos de Adams-Moulton

Dado un orden de convergencia p, los métodos implícitos de Adams-Moulton usan los puntos wi+1, wi,wi−1, . . ., wi+2−p para obtener el wi+1. El tamaño del paso puede ser arbitrario.

Método de Adams-Moulton de orden 2 (1 paso):

w0 = α

w1 = α1

wi+1 = wi +h

2[f(ti+1, wi+1)− f(ti, wi)] para i = 1, 2, . . . , N − 1

Este método es equivalente al método de Crank-Nicolson.

Método de Adams-Moulton de orden 4 (3 pasos):

w0 = α

w1 = α1

w2 = α2

wi+1 = wi +h

24[9f(ti+1, wi+1) + 19f(ti, wi)− 5f(ti−1, wi−1) + f(ti−2, wi−2)] para i = 2, 3, . . . , N − 1

Como no siempre es posible transformar la expresión de Adams-Moulton a una de forma explícita, existen losmétodos predictores-correctores de Adams, que combinan un método de Adams-Bashforth y un métodode Adams-Moulton, ambos del mismo orden de convergencia.

Adams-Bashforth Adams-Moulton

- más sencillos de programar - más estables- menos errores de redondeo

- más precisos

9.3 EDOs con condiciones de contorno

Trataremos de resolver ecuaciones del tipo dnydtn = f

(t, y, y′, . . . , y(n−1)

)en el intervalo [a, b] y con las condiciones

iniciales y(a) = α, y′(a) = β, . . ., y(n−1)(a) = γ.

25

9.3.1 Método del disparo lineal

Teorema: sea el problema y′′ = f(x, y, y′) con a ≤ x ≤ b y las condiciones y(a) = α, y(b) = β. Si f , f ′y,f ′y′ son continuas en D = {(x, y, y′) : a ≤ x ≤ b,−∞ < y <∞,−∞ < y′ <∞} y si f ′y(x, y, y′) > 0 para toda

(x, y, y′) ∈ D y si existe una constante M tal que∣∣f ′y′(x, y, y′)∣∣ ≤ M para toda (x, y, y′) ∈ D, entonces el

problema con valor en la frontera tiene una solución única.

Corolario: sea el problema y′′ = p(x)y′ + q(x)y + r(x) con a ≤ x ≤ b y las condiciones iniciales y(a) = α,y(b) = β. Si se satisface que

p(x), q(x), r(x) son continuas en [a, b]

q(x) > 0 en [a, b]

entonces el problema tiene una solución única.

El método del disparo lineal tiene problemas de estabilidad. Se basa en la sustitución del problema de valor enla frontera por 2 problemas de valor inicial:

(I) y′′ = p(x) · y′ + q(x) · y + r(x) con y(a) = α, y′(a) = 0

(II) y′′ = p(x) · y′ + q(x) · y con y(a) = 0, y′(a) = 1

Si llamamos y1(x) a la solución de (I) e y2(x) a la solución de (II), la solución �nal es:

y(x) = y1(x) + β−y1(b)y2(b) · y2(x)

9.3.2 Métodos de diferencias �nitas para problemas lineales

El método de diferencias �nitas es un método para resolver resoluciones de ecuaciones diferenciales deorden mayor o igual a dos. Consiste en reemplazar las derivadas por diferencias �nitas mediante un cocientede diferencias. La aplicación de diferencias �nitas generan un sistema de ecuaciones lineales del tipo Ax = B.Primero seleccionamos un entero N > 0 y dividimos el intervalo [a, b] en N + 1 subintervalos iguales cuyosextremos son los puntos de malla xi = a + ih para i = 0, 1, . . . , N + 1, donde h = b−a

N+1 . Al escoger h de estemodo (no muy chico), se facilita la aplicación de un algoritmo matricial.

La fórmula de las diferencias centradas para y′′(xi) es

y′′(xi) =1

h2[y(xi+1)− 2y(xi) + y(xi−1)]− h2

12y(4)(ξi)

El método de diferencias �nitas con error de truncamiento de orden O(h²) consiste en resolver el siguientesistema de ecuaciones:

2 + h2q(x1) −1 + h2 p(x1) 0 · · · 0

−1− h2 p(x2) 2 + h2q(x2)

.

.

.

0... 0

.

.

.

...

... −1 + h

2 p(xN−1)0 · · · 0 −1− h

2 p(xN ) 2 + h2q(xN )

w1

.

.

.

wN

=

−h2r(x1) +(1 + h

2 p(x1))w0

−h2r(x2)

.

.

.

−h2r(xN−1)−h2r(xN ) +

(1 + h

2 p(xN ))wN+1

9.3.3 Método de los elementos �nitos

Elmétodo de los elementos �nitos es un método para aproximar soluciones de ecuaciones diferenciales muyutilizado en análisis estructural.

26