Linear Approximation using Taylor Expansion

We assume that we are starting with an approximation \( x_n \) close to the true root. To improve this approximation, we use the Taylor series expansion of \( f(x) \) around \( x_n \):

\[ f(x) \approx f(x_n) + f'(x_n)(x - x_n) \]

This is the first-order Taylor approximation of \( f(x) \), and it essentially represents the equation of the tangent line to the curve \( f(x) \) at the point \( x = x_n \).

Setting the Function to Zero

Since we want to find the root of \( f(x) \), we are looking for the value \( x = x_{n+1} \) where the function equals zero. In other words, we want to find \( x_{n+1} \) such that:

\[ f(x_{n+1}) = 0 \]

Using the linear approximation from above, set the approximation to zero:

\[ 0 = f(x_n) + f'(x_n)(x_{n+1} - x_n) \]

Solving for \( x_{n+1} \)

Now solve for \( x_{n+1} \), the next approximation of the root:

\[ f'(x_n)(x_{n+1} - x_n) = -f(x_n) \]

Rearrange to isolate \( x_{n+1} \):

\[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \]

Algorithm: Newton-Raphson Method

1. Initial Guess: Choose an initial guess \( x_0 \) for the root.
2. Iteration:
   • Compute the function value \( f(x_n) \).
   • Compute the derivative \( f'(x_n) \).
   • Update the estimate for the root using the Newton-Raphson formula: \[ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \]
3. Convergence Check: Continue iterating until the absolute difference \[ |x_{n+1} - x_n| \] is smaller than a predefined tolerance \( \epsilon \), or until \[ |f(x_{n+1})| \] is smaller than a tolerance.
4. Return the Approximate Root: Once convergence criteria are met, return \( x_{n+1} \) as the approximate root.

The Intermediate Value Theorem

The Intermediate Value Theorem states that if \( f(x) \) is continuous on the interval \( [a,b] \) and \( f(a) \cdot f(b) < 0 \) (i.e., the function changes sign between \( a \) and \( b \)), then there exists at least one \( c \in (a,b) \) such that:

\[ f(c) = 0 \]

This means that there is a root of the function in the interval \( [a,b] \).

The Bisection Method

a. Initial Interval \( [a_0, b_0] \):

Start with an interval \( [a_0, b_0] \) such that:

\[ f(a_0) \cdot f(b_0) < 0 \]

This condition guarantees that there is at least one root in this interval.

b. Midpoint Calculation:

The next step is to narrow down the interval by calculating the midpoint of the current interval \( [a_n, b_n] \). The midpoint \( c_n \) of the interval is given by:

\[ c_n = \frac{a_n + b_n}{2} \]

This midpoint divides the interval into two sub-intervals: \( [a_n, c_n] \) and \( [c_n, b_n] \).

c. Check the Sign of \( f(c_n) \):

Now, evaluate the function at the midpoint \( c_n \):

• If \( f(c_n) = 0 \), then \( c_n \) is the root, and we are done.
• If \( f(a_n) \cdot f(c_n) < 0 \), then the root lies in the interval \( [a_n, c_n] \), and we set \( b_{n+1} = c_n \) (i.e., discard the right half of the interval).
• If \( f(c_n) \cdot f(b_n) < 0 \), then the root lies in the interval \( [c_n, b_n] \), and we set \( a_{n+1} = c_n \) (i.e., discard the left half of the interval).

d. Repeat the Process:

This process is repeated iteratively, reducing the size of the interval with each step. After \( n \) iterations, the interval containing the root will be \( [a_n, b_n] \), and the root will be approximated as the midpoint \( c_n \).

e. Stopping Criterion:

The process is stopped when the interval \( [a_n, b_n] \) becomes sufficiently small, that is, when the length of the interval \( |b_n - a_n| \) is smaller than a predefined tolerance \( \epsilon \):

\[ |b_n - a_n| < \epsilon \]

At this point, the root can be approximated by the midpoint:

\[ \text{Root} \approx c_n = \frac{a_n + b_n}{2} \]

Algorithm

1. Choose an initial interval \( [a_0, b_0] \) such that \( f(a_0) \cdot f(b_0) < 0 \).
2. Compute the midpoint \( c_n = \frac{a_n + b_n}{2} \).
3. If \( f(c_n) = 0 \), then \( c_n \) is the root.
4. Otherwise:
   • If \( f(a_n) \cdot f(c_n) < 0 \), set \( b_{n+1} = c_n \) (root is in \( [a_n, c_n] \)).
   • If \( f(c_n) \cdot f(b_n) < 0 \), set \( a_{n+1} = c_n \) (root is in \( [c_n, b_n] \)).
5. Repeat until the interval \( [a_n, b_n] \) is smaller than the tolerance \( \epsilon \).
6. Approximate the root as \( \frac{a_n + b_n}{2} \).

Mathematical Formulation

At the \( n \)-th iteration, the midpoint \( c_n \) is given by:

\[ c_n = \frac{a_n + b_n}{2} \]

The next interval is determined by:

• If \( f(a_n) \cdot f(c_n) < 0 \), set \( b_{n+1} = c_n \) (root is in \( [a_n, c_n] \)).
• If \( f(c_n) \cdot f(b_n) < 0 \), set \( a_{n+1} = c_n \) (root is in \( [c_n, b_n] \)).

This process continues iteratively until the interval is small enough to contain the root within the desired tolerance.