Métodos Numéricos Repaso - fing.edu.uy

Métodos NuméricosRepaso

Luis Stábile

Facultad de Ingeniería. UdelaR (IMERL) Repaso 2020 1 / 16

10 de febrero de 2020 - Problema 1

a) Describa el método de interpolación de Lagrange por n + 1 puntos:(xi, f (xi)), i = 0, . . . , n.

b) Se considera la función f (x) = sin(x) + cos(x). Utilice Lagrange parahallar el polinomio que interpola a f por los puntos con abscisas:xi = {0, π2 , π}.

10 de febrero de 2020 - Problema 1 a

Consiste en encontrar un polinomio de grado n (tenemos n + 1 datos) talque Pn(xi) = yi.El planteo de Lagrange es escribir Pn(x) como combinación lineal de unabase de polinomios {lj(x)} a los que llamamos polinomios de Lagrange.

Pn(x) =n∑

yjlj(x)

I Como Pn(xi) = yi tenemos que:

lj(xi)

{1 si i = j0 si i 6= j

Necesitamos:I lj(xi) tenga raices en x0, x1, . . . , xi−1, xi+1, . . . , xnI li(xi) = 1

Tomamos:

lj(x) =(x− x0)(x− x1) . . . (x− xj−1)(x− xj+1) . . . (x− xn)

(xj − x0)(xj − x1) . . . (xj − xj−1)(xj − xj+1) . . . (xj − xn)

Pn(x) =n∑

yjlj(x)

lj(xi)

{1 si i = j0 si i 6= j

Tomamos:

Pn(x) =n∑

yjlj(x)

lj(xi)

{1 si i = j0 si i 6= j

Tomamos:

Pn(x) =n∑

yjlj(x)

lj(xi)

{1 si i = j0 si i 6= j

Tomamos:

10 de febrero de 2020 - Problema 1 b

Tenemos f (x) = sin(x) + cos(x),x0 = 0, x1 = π

2 , x2 = π,y0 = f (0) = 1, y1 = f (π2 ) = 1, y2 = f (π) = −1.

El polinomio interpolante es

P(x) =2∑

yjlj(x)

con lj(x) =

∏2i=0,i6=j(x− xi)∏2i=0,i 6=j(xj − xi)

Tenemos f (x) = sin(x) + cos(x),x0 = 0, x1 = π

2 , x2 = π,y0 = f (0) = 1, y1 = f (π2 ) = 1, y2 = f (π) = −1.

El polinomio interpolante es

P(x) =2∑

yjlj(x)

con lj(x) =

∏2i=0,i6=j(x− xi)∏2i=0,i 6=j(xj − xi)

Operando, tenemos

l0(x) =(x− π/2)(x− π)(0− π/2)(0− π)

=(x− π/2)(x− π)

l1(x) =(x− 0)(x− π)

(π/2− 0)(π/2− π)=

(x)(x− π)−π2/4

l2(x) =(x− 0)(x− π/2)(π − 0)(π − π/2)

=(x)(x− π/2)

Por tanto P(x) = l0(x) + l1(x)− l2(x).Operando y agrupando en potencias de x obtenemos:

P(x) =−4x2 + 2πx + π2

c) Describa el Método de Newton-Raphson (NR) para f : R→ R.

d) Se considera f (x) = x + log(x), la cual tiene una raíz α en el intervalo[1

e , 1]. Analice convergencia, orden y velocidad de convergencia de NRpara estimar α.

10 de febrero de 2020 - Problema 2 c

Dada una función f que es derivable, la idea del método es:Arrancamos en x0 y tomamos la recta tangente en el punto (x0, f (x0)):

y(x) = f (x0) + f ′(x0)(x− x0)

Tomamos x1 igual al corte entre la recta tangente y(x) y la recta y = 0:

y(x1) = f (x0) + f ′(x0)(x1 − x0) = 0

f ′(x0)× x1 = f ′(x0)× x0 − f (x0)

f ′(x0) 6= 0↓

x1 =f ′(x0)× x0 − f (x0)

f ′(x0)

x1 = x0 −f (x0)

f ′(x0)

Dada una función f que es derivable, la idea del método es:Arrancamos en x0 y tomamos la recta tangente en el punto (x0, f (x0)):

y(x) = f (x0) + f ′(x0)(x− x0)

Tomamos x1 igual al corte entre la recta tangente y(x) y la recta y = 0:

y(x1) = f (x0) + f ′(x0)(x1 − x0) = 0

f ′(x0)× x1 = f ′(x0)× x0 − f (x0)

f ′(x0) 6= 0↓

x1 =f ′(x0)× x0 − f (x0)

f ′(x0)

x1 = x0 −f (x0)

f ′(x0)

Repetimos el mismo razonamiento de forma sucesiva:

xk+1 = xk −f (xk)

f ′(xk)

Observaciones:I Necesitamos que f ′(xk) 6= 0 ∀k ∈ N.I El método de Newton Raphson es un caso particular de MIG:

{x0 ∈ Rxn+1 = g(xn) = xn − f (xn)

f ′(xn)

10 de febrero de 2020 - Problema 2 d

La iteración del método de Newton-Raphson puede escribirse como

x(k+1) = x(k) − f (x(k))f ′(x(k))

En términos de Iteración de Punto Fijo el planteo anterior puedeescribirse como:

x(k+1) = g(x(k))

Donde g(x) = x− f (x)f ′(x)

. Puede probarse (ver teórico) que si existe una

constante m tal que |g′| ≤ m < 1 en I = [1/e, 1], entonces g escontractiva y por tanto existe un único punto fijo α ∈ I tal que g(α) = α,o sea f (α) = 0.

x(k+1) = x(k) − f (x(k))f ′(x(k))

x(k+1) = g(x(k))

x(k+1) = x(k) − f (x(k))f ′(x(k))

x(k+1) = g(x(k))

Operando, tenemos g′(x) =−(x + log(x))

(x + 1)2 , de donde

|g′(x)| = x + log(x)(x + 1)2 . Una fracción crece cuando el denominador es

pequeño y/o cuando el numerador es grande.

Sustituyendo el mayor valor posible para el numerador (en x=1) y elmenor valor posible para el denominador (x=1/e), tenemos

0 < |g′(x)| ≤ 1(1 + 1/e)2 < 1. Tomando m =

1(1 + 1/e)2 tenemos que

g es contractiva en I por lo que N-R converge ∀x(0) ∈ I.

(x + 1)2 , de donde

0 < |g′(x)| ≤ 1(1 + 1/e)2 < 1. Tomando m =

(x + 1)2 , de donde

0 < |g′(x)| ≤ 1(1 + 1/e)2 < 1. Tomando m =

Tomando x(0) = 1/2, al ejecutar N-R obtenemos la sucesiónx(0) = 0.5, x(1) = 0.564, x(2) = 0.567 con valoresf (x(0)) = −0.193, f (x(1)) = −0.008, f (x(2)) = 0.000.

Operando obtenemos g′′(x) = 2(x + log(x))− x+1x . Como g′(α) = 0 y

g′′(α) 6= 0, tenemos (ver teórico) que el orden de convergencia es 2 y lavelocidad de convergencia es |g

′′(α)|2 = α+1

Tomando como α = 0.567, tenemos que la velocidad de convergencia esaproximadamente 1.382.

′′(α)|2 = α+1

c) Se considera un sistema lineal con: A =

(2 11 −1

), b =

i) Analice la convergencia de GS a la solución α del sistema.ii) Partiendo de x0 = (0, 0), halle la estimación x2 de GS y el correspondiente

error.

10 de febrero de 2020 - Problema 3 c i

c) Se considera un sistema lineal con: A =

(2 11 −1

), b =

i) Analice la convergencia de GS a la solución α del sistema.

Para G-S tenemos

x(k+1) = Qx(k) + r x(k+1) = (L + D)−1(−U)x(k) + (L + D)−1b

(L + D)−1 =

(1/2 01/2 −1

)⇒ (L + D)−1(−U) =

(0 −1/20 −1/2

)La matriz Q y el vector r quedan Q =

(0 −1/20 −1/2

), r =

(3/23/2

)La matriz Q tiene valores propios λ1 = 0 y λ2 = −1/2, de donde su radioespectral ρ(Q) = 1/2 cumple ρ(Q) < 1, por lo que la iteración converge.

10 de febrero de 2020 - Problema 3 c ii

ii) Partiendo de x0 = (0, 0), halle la estimación x2 de GS y el

La solución exacta es α =

). Partiendo de x(0) = (0, 0) tenemos

x(1) = Qx(0) + r, x(1) =(

3/23/2

Iterando nuevamente, x(2) =(

0 −1/20 −1/2

)(3/23/2

(3/23/2

)Operando, x(2) =

(3/43/4

10 de febrero de 2020 - Problema 3 c ii

Sabemos que el error en el paso k, e(k) cumple e(k) = Qke(0), de donde

e(2) = Q2(

)Operando, tenemos e(2) =

(1/41/4

)Esto coincide con el hecho que α =

)y x(2) =

(3/43/4

), de donde es obvio

que e(2) =(

1/41/4

), una forma directa y más sencilla de calcularlo.

Métodos Numéricos Repaso - fing.edu.uy

Documents

Transcript of Métodos Numéricos Repaso - fing.edu.uy