Math128A Numerical Analysis - Final Project: Modified zero-in for root-finding
Final Project: Modified zero-in for root-finding
We would like to find a root of the equation f(x)=0, for x∈R
given an initial interval [a, b] with
f (a) · f (b) < 0.
with a combination of two methods
▶ bisection method, for its reliability
▶ inverse quadratic interpolation (IQI) method, for its higher order of convergence.
1/5
inverse quadratic interpolation (IQI) method
Given three pairs of points (x0, f0) , (x1, f1) , (x2, f2), IQI defines a quadratic polynomial in f that goes through these points,
x(f)= (f −f1)(f −f2) x0+(f −f0)(f −f2) x1+(f −f0)(f −f1) x2 (f0 −f1) (f0 −f2) (f1 −f0) (f1 −f2) (f2 −f0) (f2 −f1)
def
This leads to an estimate for the root x3 = x (0):
x3 = f1 f2 x0+ f0 f2 x1+ f0 f1 x2
(f0 −f1) (f0 −f2) (f1 −f0) (f1 −f2) (f2 −f0) (f2 −f1)
2/5
Modified zero-in for root-finding in a sketch For given initial interval [a, b] with
f (a) · f (b) < 0. Wewouldliketofindarootoftheequation f(x)=0, for x∈R
3/5
Modified zero-in for root-finding in a sketch For given initial interval [a, b] with
f (a) · f (b) < 0. Wewouldliketofindarootoftheequation f(x)=0, for x∈R
def a+b 1.setx0,x1,x2=a,b,c= 2
2. let x3 = IQI(x0, x1, x2) ▶ if x3 ̸∈ [a, b]
▶ do bisection steps on [a, b]
▶ set new interval [anew, bnew] ⊂ [a, b] with
f (anew) · f (bnew) < 0, repeat step (1)
▶ else if |f (x3)| has not decreased by a factor of 2 within 4 consecutive IQI iterations,
▶ do bisection steps on [a, b]
▶ set new interval [anew, bnew] ⊂ [a, b] with
f (anew) · f (bnew) < 0, repeat step (1)
▶ repeat IQI in step (2)
3. stop when iteration converged
3/5
More details!
1. function calls: when the function f (·) is called. ▶ There are three function calls in IQI formula
f0 = f(x0), f1 = f(x1), f2 = f(x2)
x3 =
f1 f2
(f0 −f1) (f0 −f2)
x0+
f0 f2
(f1 −f0) (f1 −f2)
x1+
f0 f1
(f2 −f0) (f2 −f1)
x2
▶ There are eighteen function calls in IQI formula
f(x1)f(x2) f(x0)f(x2) f(x0)f(x1)
x3 = x0+ (f(x0) − f(x1)) (f(x0) − f(x2))
(f(x1) − f(x0)) (f(x1) − f(x2))
x1+ x2 (f(x2) − f(x0)) (f(x2) − f(x1))
2. IQI with safety bracket:
▶ letx0, x1 =a, b; x2 ∈(a,b)withf(a)·f(b)<0
▶ letx3 =IQI(x0, x1, x2)∈(a,b)
▶ iff(x0)·f(x2)<0,continueIQIwithx0,x2,x3.
▶ iff(x2)·f(x1)<0,continueIQIwithx1,x2,x3.
4/5
Test functions
-
▶ f(x)=xe−x −2x+1oninterval[0,3],withroot x = 0.671553094250269
-
▶ f(x)=xcos(x)−2x2+3x−1oninterval[1,3],withroot x = 1.256623322505569
-
▶ f(x)=x3−7x2+14x−6oninterval[0,1],withroot x = 0.585786437626905
-
▶ f(x)=√x−cos(x)oninterval[0,1],withroot x = 0.641714370872883
-
▶ f(x)=2xcos(2x)−(x+1)2 oninterval[−2,−4],withroot x = −2.191308011797247
5/5
