Project: Analyzing Inverse Quadratic Interpolation for Root-Finding

This project delves into the inverse quadratic interpolation method, a numerical algorithm used to find the roots of functions. The research investigates the method's efficiency, applying it to polynomial and transcendental functions. The methodology involves explaining the method in a clear manner, using examples and graphical representations. The project explores the application of the inverse quadratic interpolation formula to approximate the least positive root of given functions. Furthermore, it compares the effectiveness of this method with other root-finding techniques, such as Newton's, Secant's, and Bisection's methods, through detailed examples and iterative processes. The results are presented in tables and graphs to demonstrate the convergence and accuracy of the inverse quadratic interpolation method. The project highlights the importance of root-finding in various fields and discusses the advantages and disadvantages of the chosen method.

Inverse Quadratic
Interpolation
Method

Abstract
The main purpose of this research is to discuss
a root-finding algorithm in a more efficient
way. This research study presents the inverse
quadratic interpolation method for finding the
root(s) of a function. A related question that
the researcher tries to answer is how reliable
this method is in all aspects of root
approximation.

INTRODUCTION
Finding roots is the same as solving equations. Often we
are interested in finding x such that f(x) = 0. If a
function maps real numbers to real numbers (), its roots
are the x -coordinates of the points where its graph meets
the x -axis. In any given polynomial function, the
fundamental theorem of algebra states that there are at
least a number of roots equal to the degree of the
function (though some of the roots may be repeated or
some may result in complex values). It follows that if the
degree of the polynomial function is even, then the
number of its roots is also even. On the other hand, if the
degree of the polynomial function is odd, then the number
of its roots is odd.

As we have learned in high school algebra, finding
solutions (roots) of a function is relatively easy with
polynomials. A root of a linear function f(x) = ax +
b can be found by setting f(x) = 0 and solving for x
using simple algebra. The quadratic formula, as we
always encounter in intermediate algebra, is one
method that can be used to determine the root(s)
of any parabola (the graph of a quadratic function),
allowing even the complex roots (if they exist).
There is also a formula for finding the roots of a
cubic function and even of a quartic function. For
polynomials of higher than fourth degree, where
the roots cannot be solved algebraically, we must
use other methods to find the roots of the function.

There are a lot of methods that are already known today to have an
efficient use in solving for the roots of functions. Some of these are the
bracketing methods like bisection and false position (regula falsi)
methods; the open methods like Newton’s, secant, Muller’s,
interpolation, and inverse interpolation methods; and the combination
of these methods like the Brent’s method.
Bisection method is the simplest of all these root-finding methods but
is quite the slowest-converging method. This is done by first choosing
an interval where the root is suspected to lie and whose function
values at the boundaries result in opposite signs, and then repeatedly
bisecting an interval until the interval gets smaller and smaller
converging to the actual root of a function. The false position method
is faster than the bisection method, and it also requires two starting
points to bracket the root. The open methods, on the other hand, take
a long process and solution and may require three initial
approximation values, but these methods assure that when they
converge, they converge faster than the bracketing methods. While
the Brent’s method , which some consider the fastest and the most
reliable method, takes a very complicated process which may require
the use of a math software application.

The quadratic interpolation method, as the
closest relevant study to this research, is done
by choosing three initial approximate values x0,
x1, and x2, and then determines the next
approximation x3 by the intersection of the x-axis
with the parabola through (x0, f(x0)), (x1, f(x1)),
and (x2, f(x2)). The process is repeated
continuously until the approximate root of the
function becomes closer and closer to the actual
root. Hence, this method is more known as the
Muller’s ethod. Bong-kyu Park (1987), however,
used a different approach in his study wherein he
used only two initial approximate .

values x0 and x1 as the endpoints of the interval and took
another initial approximate value x2 as the midpoint of the
interval. The new approximation x3 is the intersection of the x-
axis with a quadratic curve through (x0, f(x0)), (x2, f(x2)), and
(x1, f(x1)). He proposed the new method and called it the
New-Muller’s method [9] where he believed to improve the rate
of convergence and calculate for reducing the interval. The
inverse quadratic interpolation method, the focus of this
research study, is almost similar to the Muller’s method and
the latter (the New-Muller’s method) only that it uses the
inverse of the function and fits the parabola that will intersect
the x-axis.
Finding the roots of a function is important because it can give
us a clearer visualization of the function. It is also helpful in
determining the exact point where the function turns from
negative into positive. Root-finding methods can also be used
in business and economics to find equilibrium points.

This research aims to discuss the inverse quadratic
interpolation method for finding roots of functions.
Specifically, this research aims to
1. Investigate on the efficiency of the inverse quadratic
interpolation method as an algorithm for finding roots
of a function;
2. Apply the inverse quadratic interpolation formula in
approximating the least positive root of a given
function; and
3. Compare the effectiveness of this method with other
root-finding methods (e.g., Newton, Secant, and
Bisection) using examples.

METHODOLOGY
Discuss a root-finding method in a lighter
manner—the way that readers can easily
understand compared to other existing
materials. The researcher will use polynomial
and transcendental function examples in order
to demonstrate the efficiency of the chosen
method. In presenting and organizing the data
and results, the researcher will use graphs and
tables for convenience of presentation.

RESULTS AND DISCUSSIONS
Like many root-finding methods, the inverse quadratic
interpolation method is a numerical algorithm for solving
nonlinear equation f(x) = 0. In this case, the function f has to be a
function of one real variable. Below is the procedure for applying
this method.
Select three known points on the function to be solved with at
least one point on
o Each side of the x-axis
o Fit a quadratic curve to these three points.
o Find the root (x) of the quadratic curve in the range of interest.
o Find the value of y that corresponds to the value of x.
o Replace the furthest outlying of the three trial points with this new point.

Inverse Quadratic Interpolation
Formula
A case will be considered in this method where there
are three points xn-2, xn-1, and xn as initial values.
The function will be evaluated at each of these points
resulting in yn-2 = f(xn-2), yn-1 = f(xn-1), and yn =
f(xn), respectively. Assuming that f has an inverse
quadratic function g, then xn-2 = g(yn-2), xn-1 =
g(yn-1), and xn = g(yn), and so on. This process is
done by computing a parabola that goes through
these three given points and taking the intersection of
the parabola with the x-axis as the new root estimate.
Fitting the points with a parabola in y, we have:

However, this method has some
disadvantages—it cannot compute complex
roots because it will always cross the x-axis.
Also, if the three initial values (guesses)
chosen are very far from a root, then the
method will not converge. Hence, when this
equation converges at nth iteration, then xn is
the root of the given function. This method is
also one of the fastest methods for computing
a root, and for that reason, it is widely used
today.