[SOLVED] Ma128a 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.
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,
(f − f1) (f − f2) (f − f0) (f − f2) (f − f0) (f − f1)
x (f ) = x0+ x1+ 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):
f1 f2 f0 f2 f0 f1
x3 = x0+ x1+ x2
(f0 − f1) (f0 − f2) (f1 − f0) (f1 − f2) (f2 − f0) (f2 − f1)
Modified zero-in for root-finding in a sketch
For given initial interval [a, b] with
f (a) · f (b) < 0.
We would like to find a root of the equation f (x) = 0, for x ∈ R

Modified zero-in for root-finding in a sketch
For given initial interval [a, b] with
f (a) · f (b) < 0.
We would like to find a root of the equation f (x) = 0, for x ∈ R
1. set x0, x1, x2 b
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
Algorithm Sketch

More details!
1. function calls: when the function f (·) is called.
1.1 There are three function calls in IQI formula
f0 = f(x0), f1 = f(x1), f2 = f(x2)
f1 f2 f0 f2 f0 f1
x3 = x0 + x1 + x2 (f0 − f1) (f0 − f2) (f1 − f0) (f1 − f2) (f2 − f0) (f2 − f1)
1.2 There are eighteen function calls in IQI formula
x3 = f(x1)f(x2) f(x0)f(x2) f(x0)f(x1)
x0 + x1 + x2
(f(x0)− f(x1)) (f(x0)− f(x2)) (f(x1)− f(x0)) (f(x1)− f(x2)) (f(x2)− f(x0)) (f(x2)− f(x1))
Faster with 1.1, needs further improvement for full extra credit

More details!
1. function calls: when the function f (·) is called.
1.1 There are three function calls in IQI formula
f0 = f(x0), f1 = f(x1), f2 = f(x2)
f1 f2 f0 f2 f0 f1
x
1.2 There are eighteen function calls in IQI formula
f(x1)f(x2) f(x0)f(x2) f(x0)f(x1)
x
Faster with 1.1, needs further improvement for full extra credit
2. IQI with safety bracket:
▶ sort x0, x1 = a, b; x2 ∈ (a, b) with f (a) · f (b) < 0
▶ let x3 = IQI(x0, x1, x2) ∈ (a, b)
▶ if f (x0) · f (x2) < 0, continue IQI with x0, x2, x3:
x0new
▶ if f (x2) · f (x1) < 0, continue IQI with x1, x2, x3:
x0new
Programming project submission details (I)
You should turn in a .m file modifiedzeroinxxx.m which contains a matlab function of the form
function [root,info] = modifiedzeroinxxx(func,Int,params)
▶ xxx is your student id
▶ func is a function handle
▶ Int contains the initial interval [Int.a,Int.b]
▶ params is an object that contains at least two fields params.root tol and params.func tol.
Your algorithm should terminate once the interval containing the root is at most params.root tol in length, or the function value at the current iterate is at most params.func tol in absolute value.
Programming project submission details (II)
On output, root is the computed root, and info should have at least one field info.flag, which is 0 for a successful execution, and 1 otherwise.
Your program will be tested against a few functions of our choice.
1. (100 points) Your root finder finds all roots within 40 function calls.
2. (60-80 points) Your root finder finds all roots.
3. (extra credit: 5 points) Your root finder finds all roots in less than 30 function calls.
4. (0 points) Your program does not run.
We will choose params.root tol = params.func tol = 10−7. Your program will receive 0 points if it is found to be highly similar to the matlab built-in function fzero. While we allow group discussions, you must do all your programming work by yourself.
Test functions (easy)
▶ f (x) = x e−x − 2x + 1 on interval [0,3], with root x = 0.671553094250269
▶ f (x) = x cos(x) − 2×2 + 3x − 1 on interval [1,3], with root x = 1.256623322505569
▶ f (x) = x3 − 7×2 + 14x − 6 on interval [0,1], with root
x = 0.585786437626905
√
▶ f (x) = x − cos(x) on interval [0,1], with root x = 0.641714370872883
▶ f (x) = 2x cos(2x) − (x + 1)2 on interval [−4,−2], with root x = −2.191308011797247
Test functions (hard)
▶ f (x) = x4 − 2×3 − 4×2 + 4x + 4 on interval [0,2], with root x = 1.414213562373094
▶ f (x) = sign(x) ∗ |x|1/3 on interval [−1,8], with root x = 0
▶ f (x) = (x − 3)5 on interval [2.4,3.4], with root x = 3