Inicio / Directorio / Informática y Telecomunicaciones /

Métodos Numéricos para la Búsqueda de Raíces: Bisección, Falsa Posición, Punto Fijo, Newton, Secantes y Muller

Informática y Telecomunicaciones7,06 KB

Métodos Numéricos para la Búsqueda de Raíces

Método de Bisección

Intervalo inicial: f(a) · f(b) < 0

  1. Calcular el punto medio: xm = (a + b) / 2
  2. Determinar el nuevo intervalo: f(a) · f(xm) < 0 o f(xm) · f(b) < 0
  3. Repetir el proceso hasta que se cumpla la condición de parada.

Convergencia: 1/2 (lineal)

  • Puede ser difícil encontrar un intervalo inicial adecuado.
  • Si ocurre un error de redondeo, el intervalo resultante puede no contener la raíz.

Método de Falsa Posición

  1. Trazar la recta que une los puntos (a, f(a)) y (b, f(b)). Su intersección con el eje x es xs.
  2. Calcular: xs = a − [(b − a) · f(a)] / [f(b) − f(a)]
  3. Determinar el nuevo intervalo: f(a) · f(xs) < 0 o f(xs) · f(b) < 0
  4. Repetir el proceso hasta que se cumpla la condición de parada.

Método de Punto Fijo

Se define la función de iteración g(x) = x + c(x) · f(x), donde g(x*) = x*.

Teoremas de Existencia y Unicidad

  • Si g es continua en I y g(I) ⊂ I, entonces g tiene al menos un punto fijo en I.
  • Si g está definida en I = [a, b] y, para todo x ∈ I, se cumple |g'(x)| ≤ L < 1, entonces existe exactamente un x* en I tal que x* = g(x*).
  • Si g es continua en I, g(I) ⊂ I y |g(x) − g(y)| ≤ γ · |x − y| para x ≠ y con γ < 1, entonces existe x* ∈ I tal que g(x*) = x*, y el proceso iterativo xk+1 = g(xk) converge a x* si x0 ∈ I.

Estimaciones de Error

  • Error a priori: |x* − xk| ≤ (Lk · |x1 − x0|) / (1 − L)
  • Error a posteriori: |x* − xk| ≤ (L · |xk − xk−1|) / (1 − L)

Convergencia: lineal.

Iteración Lineal

Se busca la intersección de y = g(x) con y = x. Con g(x) = x + f(x) (es decir, c(x) = 1).

  • Puede producir convergencia o divergencia.
  • Tipos de comportamiento: oscilante (en forma de cuadrado) y monótono (en forma de escalera).

Método de Newton

Convergencia cuadrática, si x0 está suficientemente cerca de x* y si f'(x*) ≠ 0:

|xk+1 − x*| ≤ (L / 2m) · |xk − x*|2 ≤ 2 · (1/4)2k · τ, donde τ ≤ m / L, y m y L son constantes.

Búsqueda de un Intervalo de Convergencia

  1. Tomar un intervalo cualquiera y aplicar la fórmula de Newton.
  2. Si el resultado está dentro del intervalo inicial, la función converge en él.
  3. Si el resultado cae fuera del intervalo, redefinir el intervalo usando ese punto y repetir el proceso.
  4. Continuar hasta encontrar el intervalo donde la función converge.

Fórmula: xk+1 = xk − f(xk) / f'(xk)

Error: f(x) − Taylorm(x) = (x − x0)m+1 · (f(m+1)(ξ)) / (m+1)!, donde f es una función continua y Taylorm(x) es la aproximación de f alrededor del punto x0.

El método de Newton puede entrar en un bucle infinito o divergir, dependiendo del punto inicial.

Métodos de Múltiples Pasos

Utilizan valores de f y, en algunos casos, de sus derivadas.

Método de las Secantes

xk+1 = xk − (xk−1 − xk) · f(xk) / [f(xk) − f(xk−1)]

  1. Tomar dos puntos de la curva: (x0, f(x0)) y (x1, f(x1)).
  2. Determinar la recta que pasa por ambos puntos y calcular su intersección con el eje x (y = 0). Luego se utilizan (x1, f(x1)) y (x2, f(x2)) y se repite el proceso.
  • No es necesario que la raíz esté encerrada en un intervalo con cambio de signo.
  • Pueden ocurrir overflow, underflow y cancelación subtractiva.
  • Corrección: xk+1 = xk − (xk−1 − xk) · [f(xk) / f(xk−1)] / [1 − f(xk) / f(xk−1)], si |f(xk)| < |f(xk−1)|; en caso contrario, se intercambia xk por xk+1.

Es más rápido que los métodos lineal y de bisección, pero más lento que el método de Newton.

Interpolación Polinomial

Polinomio de Lagrange (polinomio interpolador)

Es un polinomio de grado n que pasa por todos los puntos (xi, yi) de una curva.

pn(x) = [(x − x1)(x − x2) … (x − xn)] / [(x0 − x1)(x0 − x2) … (x0 − xn)] · y0 + [(x − x0)(x − x2) … (x − xn)] / [(x1 − x0)(x1 − x2) … (x1 − xn)] · y1 + …

Diferencias Divididas de Newton

Otra forma de obtener el polinomio interpolador:

pn(x) = f(x0) + (x − x0) · f(x0, x1) + … + (x − x0)…(x − xn−1) · f(x0, …, xn)

  • f(x0, x1) = [f(x0) − f(x1)] / (x0 − x1)
  • f[x2, x1, x0] = (f[x1, x0] − f[x2, x1]) / (x0 − x2)

Método de Muller

Se obtiene el polinomio interpolador de Newton para tres puntos iniciales:

p(x) = f[x2, x1, x0] · (x − x2)2 + (f[x2, x1] + (x2 − x1) · f[x2, x1, x0]) · (x − x2) + f(x2)

x3 = x2 + [−b + signo(b) · √(b2 − 4ac)] / (2a)

El siguiente iterando será la raíz de este polinomio que esté más próxima a x2.

Descargar

PDF Word HTML