Informática
Pseudocódigo del método de bisección
Pseudocódigo del método de Bisección
1.- Dada la función escójanse dos valores iniciales para xi y xs de tal manera que sustituyéndolos en la f(x) se encuentre un cambio de signo para determinar entre que intervalos se encuentra la raíz, si esto se cumple ahí que multiplicar f(xi)*f(xs) y el resultado debe ser menor a cero.
2.- La primera aproximación se encuentra de la siguiente manera:
xr =xi + xs
2
3.- Ahora ahí que determinar en que sub-intervalo esta la raíz para eso se hace lo siguiente
a) si f(xi)*f(xs)<0
entonces la raíz esta en el primer sub-intervalo y xs = xr
b) si f(xi)*f(xs)>0
entonces la raíz se encuentra en el segundo sub-intervalo y xi=xr
c) si f(xi)*f(xs)=0 ó f(xs)*f(xr)=0
entonces xr es la raíz
4.- Después se calcula el error aproximado ( ea%=100(xr(valor actual)-xr(valor anterior)))
xr(valor actual)
Se vuelve a calcular la siguiente aproximación
(regresar al paso 2 y seguir hasta aquí nuevamente)
y se deja de realizar hasta que el ea% sea igual a 0.01, o se encuentre la raíz.
INTRODUCCIÓN(Falsa Posición).
MÉTODO DE LA BISECCIÓN
El método de bisección se basa en el siguiente teorema de Cálculo:
Teorema del Valor Intermedio
Sea
continua en un intervalo
y supongamos que
. Entonces para cada
tal que
, existe un
tal que
. La misma conclusión se obtiene para el caso que
.
Básicamente el Teorema del Valor Intermedio nos dice que toda función continua en un intervalo cerrado, una vez que alcanzó ciertos valores en los extremos del intervalo, entonces debe alcanzar todos los valores intermedios.
En particular, si
y
tienen signos opuestos, entonces un valor intermedio es precisamente
, y por lo tanto, el Teorema del Valor Intermedio nos asegura que debe existir
tal que
, es decir, debe haber por lo menos una raíz de
en el intervalo
.
El método de bisección sigue los siguientes pasos:
Sea
continua,
i) Encontrar valores iniciales
,
tales que
y
tienen signos opuestos, es decir,
| |
ii) La primera aproximación a la raíz se toma igual al punto medio entre
y
:
| |
iii) Evaluar
. Forzosamente debemos caer en uno de los siguientes casos:
|
En este caso, tenemos que
y
tienen signos opuestos, y por lo tanto la raíz se encuentra en el intervalo
.
|
En este caso, tenemos que
y
tienen el mismo signo, y de aquí que
y
tienen signos opuestos. Por lo tanto, la raíz se encuentra en el intervalo
.
|
En este caso se tiene que
y por lo tanto ya localizamos la raíz.
El proceso se vuelve a repetir con el nuevo intervalo, hasta que:
| |
es decir,
| |
Ejemplo 1
Aproximar la raíz de
hasta que
.
Solución
Sabemos por lo visto en el ejemplo 1 de la sección anterior, que la única raíz de
se localiza en el intervalo
. Así que este intervalo es nuestro punto de partida; sin embargo, para poder aplicar el método de bisección debemos checar que
y
tengan signos opuestos.
En efecto, tenemos que
| |
mientras que
| |
Cabe mencionar que la función
sí es continua en el intervalo
. Así pues, tenemos todos los requisitos satisfechos para poder aplicar el método de bisección. Comenzamos:
i) Calculamos el punto medio (que es de hecho nuestra primera aproximación a la raíz):
| |
ii) Evaluamos
iii) Para identificar mejor en que nuevo intervalo se encuentra la raíz, hacemos la siguiente tabla:
Por lo tanto, vemos que la raíz se encuentra en el intervalo
.
En este punto, vemos que todavía no podemos calcular ningún error aproximado, puesto que solamente tenemos la primera aproximación. Así, repetimos el proceso con el nuevo intervalo
.
Calculamos el punto medio (que es nuestra segunda aproximación a la raíz):
| |
Aquí podemos calcular el primer error aproximado, puesto que contamos ya con la aproximación actual y la aproximación previa:
| |
Puesto que no se ha logrado el objetivo, continuamos con el proceso.
Evaluamos
, y hacemos la tabla:
Así, vemos que la raíz se encuentra en el intervalo
.
Calculamos el punto medio,
| |
Y calculamos el nuevo error aproximado:
| |
El proceso debe seguirse hasta cumplir el objetivo.
Resumimos los resultados que se obtienen en la siguiente tabla:
Aprox. a la raíz | Error aprox. |
1.25 |
|
1.375 | 9.09% |
1.3125 | 4.76% |
1.28125 | 2.43% |
1.296875 | 1.20% |
1.3046875 | 0.59% |
Así, obtenemos como aproximación a la raíz | |
Option Explicit
Dim sig As String
Dim b As String
Dim a As Double
Dim aux As Double
Dim xi As Double
Dim xs As Double
Dim xr As Double
Dim fxi As Double
Dim fxs As Double
Dim fxr As Double
Dim ff As Double
Dim ea As Double
Dim correcto As Integer
Private Sub cmdcalcular_Click()
fxi = (Exp(-xi)) - xi
fxs = (Exp(-xs)) - xs
xr = (xi + xs) / 2
fxr = (Exp(-xr)) - xr
ff = fxi * fxr
Label2.Caption = Label2.Caption & vbCrLf & Format(xi, "0.#####")
Label4.Caption = Label4.Caption & vbCrLf & Format(xs, "0.#####")
If (ff > 0) Then
sig = "+"
xi = xr
ElseIf (ff < 0) Then
sig = "-"
xs = xr
End If
If (correcto > 0) Then
ea = Abs(((xr - a) / xr) * 100)
End If
Label1.Caption = Label1.Caption & vbCrLf & correcto
Label3.Caption = Label3.Caption & vbCrLf & Format(fxi, "0.#####")
Label5.Caption = Label5.Caption & vbCrLf & Format(fxs, "0.#####")
Label6.Caption = Label6.Caption & vbCrLf & Format(xr, "0.#####")
Label7.Caption = Label7.Caption & vbCrLf & Format(fxr, "0.#####")
Label8.Caption = Label8.Caption & vbCrLf & sig
Label9.Caption = Label9.Caption & vbCrLf & Format(ea, "0.####")
a = xr
If (ea < 0.01) And (correcto > 0) Then
frmbiseccion.Visible = False
cmdcalcular.Enabled = False
frmprincipal.Visible = False
MsgBox "Raiz Encontrada en Xr=" & xr, vbExclamation, "JORGE ARAIZA 8/OCT/2001 "
frmbiseccion.Visible = True
End If
correcto = correcto + 1
End Sub
Private Sub cmdsalir_Click()
Unload Me
frmprincipal.Visible = True
End Sub
Private Sub Command1_Click()
Label1.Caption = " I"
Label2.Caption = " xi"
Label3.Caption = " f(xi)"
Label4.Caption = " xs"
Label5.Caption = " f(xs)"
Label6.Caption = " xr"
Label7.Caption = " f(xr)"
Label8.Caption = " f(xi) f(xr)"
Label9.Caption = " Ea %"
correcto = 0
cmdcalcular.Enabled = True
xi = 0
xs = 1
End Sub
Private Sub Form_Load()
xi = 0
xs = 1
ea = 0
correcto = 0
frmprincipal.Visible = False
End Sub
ALGORITMO DE FALSA POSICIÓN.
1.- Proponer 2 valores para Xi y Xs respectivamente, tales que fxi*fxs sea menor a cero.
2.- Definir el error permitido e=0.01% .
3.- Con los valores de fxi y fxs ahí que calcular el valor de Xr.
Xr = Xs - F(Xs)*(Xi-Xs)
F(Xi)-F(Xs)
4.- Calcular el valor de F(Xr).
5.- Calcular el [ea]%, si el ea es menor a e entonces el valor de Xr es donde se encuentra la raíz y ahí termina sino paso 6
([ea]=(Xractual-Xranterior) *100).
Xractual
6.- si F(Xi)*F(Xr) es mayor a 0
a). Entonces Xi=Xr.
b) si F(Xi)*F(Xr) es menor a 0 entonces Xs = Xr.
Regresar al paso 3 hasta que ea<0.01.
DIAGRAMA DE FLUJO.
INTRODUCCIÓN(Falsa Posición).
Método de la falsa posición
El método de la falsa posición pretende conjugar la seguridad del método de la bisección con la rapidez del método de la secante. Este método, como en el método de la bisección, parte de dos puntos que rodean a la raíz f(x) = 0, es decir, dos puntos x0 y x1tales que f(x0)f(x1) < 0. La siguiente aproximación, x2, se calcula como la intersección con el eje X de la recta que une ambos puntos (empleando la ecuación del método de la secante). La asignación del nuevo intervalo de búsqueda se realiza como en el método de la bisección: entre ambos intervalos, [x0,x2] y [x2,x1], se toma aquel que cumpla f(x)f(x2) < 0. En la figura(1) se representa geométricamente este método.
Figura(1): Representación geométrica del método de la falsa posición. |
[scale=0.9]eps/falpos |
La elección guiada del intervalo representa una ventaja respecto al método de la secante ya que inhibe la posibilidad de una divergencia del método. Por otra parte y respecto al método de la bisección, mejora notablemente la elección del intervalo (ya que no se limita a partir el intervalo por la mitad).
Figura(2): Modificación del método de la falsa posición propuesta por Hamming. La aproximación a la raíz se toma a partir del punto de intersección con el eje X de la recta que une los puntos ( x0,f(x0)/2) y (x1,f(x1)) si la función es convexa en el intervalo (figura a) o bien a partir de la recta que une los puntos (x0,f(x0)) y (x1, f(x1)/2) si la función es cóncava en el intervalo (figura b). |
[scale=0.9]eps/hamming |
Sin embargo, el método de la falsa posición tiene una convergencia muy lenta hacia la solución. Efectivamente, una vez iniciado el proceso iterativo, uno de los extremos del intervalo tiende a no modificarse (ver figura (1)). Para obviar este problema, se ha propuesto una modificación del método, denominada método de Hamming. Según este método, la aproximación a una raíz se encuentra a partir de la determinación del punto de intersección con el eje X de la recta que une los puntos ( x0,f(x0)/2) y (x1,f(x1)) si la función es convexa en el intervalo o bien a partir de la recta que une los puntos (x0,f(x0)) y (x1, f(x1)/2) si la función es cóncava en el intervalo. En la figura (2) se representa gráficamente el método de Hamming.
Como hemos comentado, el método de Hamming requiere determinar la concavidad o convexidad de la función en el intervalo de iteración. Un método relativamente sencillo para determinar la curvatura de la función consiste en evaluar la función en el punto medio del intervalo, f(xm) (en donde xm se calcula como en el método de la bisección) y comparar este valor con la media de los valores de la función en los extremos del intervalo,
. Tenemos entonces que:
CODIGO DEL PROGRAMA DE FALSA POSICION.
Dim sig As String
Dim xi As Double
Dim xs As Double
Dim fxi As Double
Dim fxs As Double
Dim xr As Double
Dim fxr As Double
Dim ea As Double
Dim i As Double
Dim ff As Double
Dim a As Double
Private Sub cmdcalcular_Click()
fxi = Exp(-xi) - xi
fxs = Exp(-xs) - xs
xr = xs - ((fxs * (xi - xs)) / (fxi - fxs))
fxr = Exp(-xr) - xr
ff = fxi * fxr
Label5.Caption = Label5.Caption & Format(xs, "00.######") & vbCrLf
Label3.Caption = Label3.Caption & Format(xi, "00.######") & vbCrLf
If (ff > 0) Then
xi = xr
sig = "+"
End If
If (ff < 0) Then
xs = xr
sig = "-"
End If
If (i = 0) Then
a = xr
End If
If (i > 0) Then
ea = Abs(((a - xr) / xr) * 100)
a = xr
End If
If (ea < 0.01) And (i > 0) Then
frmprincipal.Visible = False
frmfalsa.Visible = False
MsgBox "Raiz Encontrada en Xr= " & xr, vbCritical, "JORGE ARAIZA"
frmfalsa.Visible = True
cmdcalcular.Enabled = False
End If
i = i + 1
Label2.Caption = Label2.Caption & i & vbCrLf
Label4.Caption = Label4.Caption & Format(fxi, "00.######") & vbCrLf
Label6.Caption = Label6.Caption & Format(fxs, "00.######") & vbCrLf
Label7.Caption = Label7.Caption & Format(xr, "00.######") & vbCrLf
Label8.Caption = Label8.Caption & Format(fxr, "00.######") & vbCrLf
Label9.Caption = Label9.Caption & sig & vbCrLf
Label10.Caption = Label10.Caption & Format(ea, "00.######") & vbCrLf
End Sub
Private Sub CMDLIMPIAR_Click()
Label2.Caption = ""
Label3.Caption = ""
Label4.Caption = ""
Label5.Caption = ""
Label6.Caption = ""
Label7.Caption = ""
Label8.Caption = ""
Label9.Caption = ""
Label10.Caption = ""
xi = 0
xs = 1
ea = 0
i = 0
cmdcalcular.Enabled = True
End Sub
Private Sub cmdsalir_Click()
Unload Me
frmprincipal.Visible = True
End Sub
Private Sub Form_Load()
i = 0
ea = 0
Label2.Caption = ""
Label3.Caption = ""
Label4.Caption = ""
Label5.Caption = ""
Label6.Caption = ""
Label7.Caption = ""
Label8.Caption = ""
Label9.Caption = ""
Label10.Caption = ""
xi = 0
xs = 1
End Sub
PSEUDOCODIGO DEL METODO DE NEWTON-RAPHSON.
1.- Dada la función f(x), ahí que calcula un valor para Xi (X inicial) .
2.- Definir el margen de error (e=0.01).
3.- Derivar la función dada y utilizar la siguiente formula.
Xi+1=Xi - f(Xi)
f1(Xi)
3.- Ahora se conoce el valor de Xi+1.
4.- Se calcula el error aproximado( ea%=100(xi+1(valor actual)-xi+1(valor anterior)))
xi+1(valor actual)
si este es menor al error definido, Xi es el valor de la raíz, y ahí termina la búsqueda.
5.- El valor de Xi = Xi+1.
INTRODUCCIÓN.
Método de Newton-Raphson.
Está basado en el uso de una línea tangente como aproximación de f(x), cerca de los puntos donde el valor de la función es cero.
1.- Escoger un número inicial (x0)
2.- Calcular la siguiente aproximación de x1 utilizando la fórmula:
3.- Si | xn-xn+1 | < ð entonces xn+1 es una raíz
De otra forma pasar al punto 2
Codigo del programa de newton raphson.
Dim xi As Double
Dim fxi As Double
Dim a As Double
Dim iteracion As Double
Dim ea As Double
Private Sub cmdcalcular_Click()
fxi = xi - (((Exp(-xi)) - xi) / ((-Exp(-xi) - 1)))
lbli.Caption = lbli.Caption & iteracion & vbCrLf
lblxi.Caption = lblxi.Caption & Format(fxi, "0.########") & vbCrLf
If (iteracion > 1) Then
ea = Abs(((fxi - a) / fxi) * 100)
End If
lbleaa.Caption = lbleaa.Caption & Format(ea, "0.########") & vbCrLf
xi = fxi
a = fxi
If (ea < 0.01) And (iteracion > 1) Then
frmNewton.Visible = False
cmdcalcular.Enabled = False
frmprincipal.Visible = False
MsgBox "Xr= " & fxi, vbCritical, "Raiz Encontrada"
frmNewton.Visible = True
End If
iteracion = iteracion + 1
End Sub
Private Sub CMDLIMPIAR_Click()
a = 0
iteracion = 1
xi = 0
lbli.Caption = ""
lblxi.Caption = ""
lbleaa.Caption = ""
cmdcalcular.Enabled = True
ea = 0
End Sub
Private Sub cmdsalir_Click()
Unload Me
frmprincipal.Visible = True
End Sub
Private Sub Form_Load()
a = 0
iteracion = 1
xi = 0
End Sub
INTRODUCCION.
Método de la Secante
Es similar al método de Newton, pero la derivada se reemplaza por una diferencia dividida. El método requiere de dos puntos para empezar a iterar. Las iteraciones en este caso son
Se puede demostrar que el orden de convergencia para este método es aproximadamente 1.6
Pseudocodigo de la Secante.
1.- Requiere dos valores para xi-1 y xi.
2.- Al darle estos valores se utiliza la sig. formula:
xi+1=xi-f (xi) (xi-1-xi)
f (xi-1)-f (xi)
3.- Se calcula el error aproximado y si este es menor a 0.01 entonces ahi finaliza el programa, sino se repite hasta que se cumpla lo anterior.
4.- Si el error fue mayor a 0.01, entonces xi-1=xi; xi=xi+1, y se debe volver al paso 2
DIAGRAMA DE FLUJO DEL METODO DE LA SECANTE.
Descargar
Enviado por: | Jorge Araiza |
Idioma: | castellano |
País: | México |