Apuntes Metodos Numericos

ECUACIONES NO LINEALES

Algoritmos para resolver una ecuaci´n no lineal f (x) = 0, f : [a, b] −→ R, con
o
f (a)f (b) < 0.
M´todo de Newton-Bisecci´n
e
o

1. Tomar x0 ∈ [a, b]; k = 0; ε > 0;
2.
• Si f (a)f (x0 ) < 0 ⇒ a0 = a, b0 = x0 .
• Si no ⇒ a0 = x0 , b0 = b.
3.
• Si |f (xk )| > εM |f (xk )| ⇒ y k+1 = xk −

f ( xk )
.
f (xk )

– Si y k+1 ∈ [ak , bk ] ⇒ xk+1 = y k+1 .
ak +bk
– Si no ⇒ xk+1 =
.
2
a k + bk
• Si no ⇒ xk+1 =
.
2
4.
• Si f (ak )f (xk+1 ) < 0 ⇒ ak+1 = ak , bk+1 = xk+1 .
• Si no ⇒ ak+1 = xk+1 , bk+1 = bk .
5.
• Si |xk+1 − xk | < ε max{1, |xk+1 |} y |f (xk+1 )| < ε ⇒ STOP.
• Si |f (xk+1 )| < εf ⇒ STOP.
• Si no ⇒ volver al paso 2.
NOTAS:
• ε es la precisi´n que se desea en la soluci´n.
o
o
• εf es la precisi´n con la que se eval´a lafunci´n f . Si no se conoce, se debe elegir
o
u
o
3/4
un n´mero mayor que la precisi´n de la m´quina. En algunos casos εf = εM puede
u
o
a
ser un n´mero razonable.
u
o
a
• εM es la precisi´n de la m´quina.
1

M´todo de Secante-Bisecci´n
e
o

1. Tomar x0 = a; x1 = b; a1 = a; b1 = b; ε > 0;
2. Calcular
x2 = x1 −

f (x1 )
.
f (x1 ) − f (x0 )
x 1 − x0

3. k = 2.
• Si f (x2)f (a1 ) < 0 ⇒ a2 = a1 , b2 = x2 , x1 = x0 .
• Si no ⇒ a2 = x2 , b2 = b1 .
4. mk =

f (xk ) − f (xk−1 )
.
xk − xk − 1
f (xk )
.
mk
= y k+1 .

• Si |mk | > εM |f (xk )| ⇒ y k+1 = xk −
– Si y k+1 ∈ [ak , bk ] ⇒ xk+1
ak + bk
– Si no ⇒ xk+1 =
.
2
a k + bk
.
• Si no ⇒ xk+1 =
2
5.

• Si f (ak )f (xk+1 ) < 0 ⇒ ak+1 = ak , bk+1 = xk+1 .
• Si no ⇒ ak+1 = xk+1 , bk+1 = bk .
6.
• Si|xk+1 − xk | < ε max{1, |xk+1 |} y |f (xk+1 )| < ε ⇒ STOP.
• Si |f (xk+1 )| < εf ⇒ STOP.
• Si no ⇒ volver al paso 4.
NOTAS:
• ε es la precisi´n que se desea en la soluci´n.
o
o
• εf es la precisi´n con la que se eval´a la funci´n f . Si no se conoce, se debe elegir
o
u
o
3/4
un n´mero mayor que la precisi´n de la m´quina. En algunos casos εf = εM puede
u
o
a
ser un n´merorazonable.
u
• εM es la precisi´n de la m´quina.
o
a

2

SISTEMAS DE ECUACIONES NO
LINEALES
Algoritmos para resolver el sistema de ecuaciones no lineales f (x) = 0, dada una
funci´n f : D(f ) ⊂ Rn −→ Rn , D(f ) siendo alg´n subconjunto abierto de Rn .
o
u

M´todo de Newton
e

1. Tomar un punto inicial x0 ∈ Rn ; β ∈ (0, 1/2]; ε > 0; εf > 0; k = 0. Ir al paso 2.
2. Ak = Df (xk ).
−3/4• Mientras cond(Ak ) > εM

⇒ Ak = Ak + λk I , con λk =

√

εM Df (xk ) .

Ir al paso 3.
3. Ak dk = −f (xk ). Ir al paso 4.
4. Tomar

mk = min{j ∈ Z+ : f (xk + β j dk ) < f (xk ) },
ρk = β mk y xk+1 = xk + ρk dk .

Ir al paso 5.
5.
• Si xk+1 − xk < ε max{1, xk+1 } y f (xk+1 ) < ε ⇒ STOP.
• Si f (xk+1 ) < εf ⇒ STOP.
• Si no ⇒ Incrementar el contador de iteraciones k → k + 1.Volver a 2.
NOTAS:
o
o
• ε es la precisi´n que se desea en la soluci´n.
• εf es la precisi´n con la que se eval´a la funci´n f . Si no se conoce, se debe elegir
o
u
o
3/4
un n´mero mayor que la precisi´n de la m´quina. En algunos casos εf = εM puede
u
o
a
ser un n´mero razonable.
u
o
• En el paso 2 es aconsejable utilizar la funci´n rcond de Matlab para obtener una
estimaci´nnum´rica del inverso del n´mero de condici´n (seg´n la norma 1) de la
o
e
u
o
u
matriz Ak . De esta forma, la condici´n del paso 2 podr´ escribirse en la forma
o
ıa
3/4
rcond(Ak ) ≤ εM . An´logamente es aconsejable utilizar norm(A, 1) para obtener
a
la norma 1 de A como alternativa a la norma 2, que requiere un mayor coste computacional.
3

M´todo de Broyden
e

1. Tomar un puntoinicial x0 ∈ Rn ; β ∈ (0, 1/2]; ε > 0; εf > 0; B0 Df (x0 ); k = 0;
IND = 1; max > 0.
√
−3/4
2. Mientras cond(Bk ) > εM ⇒ Bk = Bk + λk I , con λk = εM Bk .
3. Bk dk = −f (xk ).
4. mk = min{j ∈ Z+ : f (xk + β j dk ) < f (xk ) }.
• Si mk > max y IND = 1 ⇒ STOP. No hay convergencia.
• Si mk > max y IND = 0 ⇒ Bk

Df (xk ); IND = 1. Volver a 2.

• Si no ⇒ IN D = 0, ρk = β mk ; xk+1 = xk + ρk dk...