What if, instead of blindly halving the search space with each iteration, we use the available information specific to the function to help speed up the search?

Linear interpolation converges slightly faster than the bisection method. By approximating the curve with a secant, it allows the use of the overall gradient within each interval to find the next point.  Let me explain that to you in detail, Mathematicians use linear polynomials to fit curves with linear interpolation and construct new data points within the range of a discrete set of known data points.

In order to estimate the value of a function between two known values, the linear interpolation formula is used. Additionally, linear polynomials can be used to fit curves using the linear interpolation formula. Interpolation that generates new values based on existing values is known as linear interpolation. In linear interpolation, two adjacent points on a graph or plane are connected geometrically by a straight line. It is possible to consider all points other than the original two as interpolated.

Explanation

Similar to the method of bisection, it follows an iterative approach with the interval [l,u]. After determining the existence of a root, the algorithm for linear interpolation is as follows:

  1. Select values for the upper and lower bounds, \(l = 2.5, u = 4.5 \).

  2. Calculate the midpoint \(p=u-f(u)\cdot\frac{(l-u)}{f(l)-f(u)} \).

  3. If \(f(p) = 0 \), then the root is found, $latex  x=p $. Stop.

  4. Else \(f(p) \neq 0 \)
    a. If \(f(p) \cdot f(l) > 0 , l = p , u = u \)
    b. If \(f(p) \cdot f(u) > 0 , l = l , u = p \)

  5. Repeat steps 2 to 4 until a pre-specified tolerance is satisfied or the maximum number of iterations is reached.

Worked Example

Figure 4.1: Graph of Graph of \(y=sin(x)+3/(4x) \)

Above, we have the same graph as utilized in the previous topic, The Bisection Method.

Figure 4.2

Similarly, we use the same lower bound of \(l=2.5 \) and upper bound of \(u=4.5 \).

Figure 4.3: Drawing the secant

In Figure 4.3, a secant connecting points \((l, f(l)) \) and \((u, f(u)) \) is drawn. To derive the formula for finding the x-intercept, p, we first need to find the equation of the secant in its inverse form (\(x=y/m + p \)).

In general, these are the two formulae for calculating the equation of a straight line:

  1. \(m = \frac{y_1-y_2}{x_1-x_2} \)
  2. \(x= \frac{y}{m} + p \)

By substituting \(y \) for \(f(x) \), we get the following derivation for \(p \):

\(p=x-\frac{y}{m}\\=x-y\cdot\frac{1}{m}\\=x-y\cdot\frac{x_1-x_2}{y_1-y_2}\\=x-f(x)\cdot\frac{x_1-x_2}{f(x_1)-f(x_2)}\\=u-f(u)\cdot\frac{l-u}{f(l)-f(u)} \)

Figure 4.4

From Figure 4.3, it is evident that \(f(p)<0 \), hence the \(u=p=3.551 \) for the next iteration.

Iterationlup
12.54.53.55125307
22.53.5512533.37006416
32.53.3700643.36626412

Compared to the Bisection Method (covered in the previous topic), the linear interpolation part ofBrent’s Method converges much faster with just 3 iterations required to reach an accuracy of 2 decimal places in this case.

The linear interpolation part of Brent’s Method is implemented in kotlin below:

				
					import kotlin.math.sin as sin

fun testFunction(x: Double):Double{
    return sin(x)+3/(4*x)
}

fun linearInterpolation(myFunction: (x: Double) -&gt; Double, lowerBound: Double, upperBound: Double, maxMargin: Double, maxIterations: Int): Double{
    var lower: Double = lowerBound
    var upper: Double = upperBound
    if (myFunction(lower)*myFunction(upper)&gt;0.0){
        return 0.0  // lower and upper bounds have the same sign, root does not exist within that interval
    }
    var mid: Double=(lower+upper)/2
    var iterations: Int = 0
    while (upper-lower&gt;=maxMargin &amp;&amp; iterations0){
            upper = mid
        }
        else{
            lower = mid
        }
        iterations+=1
    }
    return mid
}

linearInterpolation(::testFunction, 2.5, 4.5, 0.00001, 10)
				
			

Output: