5.1.2. Key Concepts

✅ Types of Equations:

1. Algebraic Equations

   • Equations formed using algebraic operations (addition, subtraction, multiplication, division, and exponentiation with rational numbers).
   • Example: 𝑥³ − 4𝑥 + 1 = 0

2. Transcendental Equations

   • Equations involving transcendental functions like sin(x), log(x), or e^x.
   • Example: 𝑒ˣ = 3𝑥, 𝑥sin(𝑥) = 1

This section describes two fundamental types of equations encountered in numerical methods.

• Algebraic Equations are comprised entirely of algebraic expressions, meaning they can be manipulated using basic arithmetic operations. These equations can typically be solved by rearranging them to isolate the variable. A common example is the cubic equation 𝑥³ − 4𝑥 + 1 = 0.

• Transcendental Equations involve non-algebraic functions such as exponential, logarithmic, or trigonometric functions. These equations are often more complex and may not be solvable by standard algebraic methods. The equations 𝑒ˣ = 3𝑥 and 𝑥sin(𝑥) = 1 illustrate this type. Here, numerical methods become essential for finding approximate solutions.

Think of algebraic equations as straightforward puzzles with standard shapes, like square or cubic blocks that fit neatly together. You can solve them with clear techniques. In contrast, transcendental equations are like jigsaw puzzles with irregularly shaped pieces - they require more creativity and specialized tools to find a solution.

🔧 Numerical Methods for Solving Equations

1. Bisection Method

   • Principle: Repeatedly bisect the interval [𝑎, 𝑏] where the function changes sign, and narrow down the root.
   • Condition: Function 𝑓(𝑥) must be continuous in [𝑎, 𝑏] and 𝑓(𝑎)𝑓(𝑏) < 0.
   • Formula: $x_{mid} = \frac{a + b}{2}$
   • Steps: a. Compute 𝑓(𝑎) and 𝑓(𝑏) b. Check if root lies between 𝑎 and 𝑥_{mid} or 𝑥_{mid} and 𝑏 c. Repeat until desired accuracy
   • Pros: Simple and reliable
   • Cons: Slow convergence

2. Regula Falsi Method (False Position Method)

   • Principle: Uses linear interpolation between two points to estimate the root.
   • Formula: $x = a \frac{f(b)}{f(b) - f(a)} - b \frac{f(a)}{f(b) - f(a)}$
   • Improvement over Bisection: Approximates root more intelligently using the function values.
   • Steps: a. Select 𝑎 and 𝑏 such that 𝑓(𝑎)𝑓(𝑏) < 0 b. Calculate new root using the formula c. Replace the interval based on the sign of 𝑓(𝑥)

3. Newton-Raphson Method

   • Principle: Uses tangents to approximate root.
   • Formula: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
   • Steps: a. Choose an initial guess 𝑥₀ b. Evaluate 𝑓(𝑥₀) and 𝑓'(𝑥₀) c. Update 𝑥 iteratively
   • Pros: Fast convergence
   • Cons: Requires derivative; fails if 𝑓′(𝑥) is zero or very small

4. Secant Method

   • Principle: Similar to Newton-Raphson but doesn't require derivative.
   • Formula: $x_{n+1} = x_n - \frac{f(x_n)(x_n - x_{n-1})}{f(x_n) - f(x_{n-1})}$
   • Pros: Doesn’t require 𝑓′(𝑥)
   • Cons: Requires two initial guesses

5. Fixed Point Iteration Method

   • Form: Rearrange the equation into $x = g(x)$
   • Formula: $x_{n+1} = g(x_n)$
   • Condition: |g'(x)| < 1 for convergence
   • Pros: Easy implementation
   • Cons: May diverge if not properly chosen

This portion discusses several numerical methods used to find roots of equations, especially when exact algebraic solutions are not available.

1. Bisection Method: This method repeatedly bisects (divides in half) the interval containing the root, checking which side contains the root based on the sign of the function. It is reliable but can converge slowly.

2. Regula Falsi Method: Also known as the false position method, this improves on the bisection method by calculating the root based on linear interpolation. It can be faster than the bisection method but still depends on the endpoints.

3. Newton-Raphson Method: This is a more advanced technique that uses the tangent of the function at a given point to approximate the root. It converges quickly but requires the derivative of the function. If the derivative is zero or near zero, the method can fail.

4. Secant Method: Like the Newton-Raphson method, but doesn't require calculating the derivative. Instead, it uses two previous points to compute the slope, making it a bit more approachable but still requires two initial guesses.

5. Fixed Point Iteration Method: This involves rearranging the equation into a specific form and iteratively calculating the next value until convergence is achieved. It can be simple to implement but might diverge if the conditions aren’t right.

Imagine trying to find the right path through a dark forest where you know there’s a clear path (the root) but cannot see it directly.

• The Bisection Method is like systematically splitting the forest in half and checking which half has the path.
• The Regula Falsi Method is like pulling a rope through the trees towards a light source, adapting as you go.
• The Newton-Raphson Method is using a high-tech flashlight that shows you where to go based on the steepness of the path in front of you.
• The Secant Method uses two less sophisticated flashlights, each at a distance to show you where to navigate next.
• The Fixed Point Iteration Method is similar to setting a GPS to guide you based on where you think you’ll end up next.

📝 Comparison of Methods

This section summarizes how the different numerical methods compare based on four criteria:

• Initial Guess: Different methods may require different numbers of initial guesses. For instance, Bisection and Regula Falsi require two guesses (endpoints), while methods like Newton-Raphson and Fixed Point require only one.

• Derivative Required: Some methods, like Newton-Raphson and, to some degree, Secant, require the derivative of the function while others do not. This can complicate or simplify the method’s implementation.

• Speed: Different methods have different rates of convergence. Newton-Raphson is usually the fastest, while Bisection converges the slowest but is more reliable in yielding results.

• Reliability: This refers to how likely the method is to converge to the correct solution under various conditions. Bisection is always reliable, while others like Newton-Raphson may fail under certain conditions.

Think of each method like different types of cars you might drive.

• The Bisection Method is like a sturdy, reliable SUV—it may not be the fastest, but it will get you there without fail and can handle rough terrain.
• The Regula Falsi Method is akin to a smart sedan that automatically adjusts its path to avoid traffic jams, offering a blend of speed and consistency.
• The Newton-Raphson Method is like a sports car, fast and exhilarating, but requires skill (a good driver) and can crash if not handled carefully.
• The Secant Method is similar to a hybrid; it can move quickly but needs a skilled driver to handle corners well.
• Lastly, the Fixed Point Iteration is like a GPS system that sometimes needs recalibration. It may lead you astray if not properly set up.

✅ Stopping Criteria

Iteration is stopped when any of the following are satisfied:

• |f(xₙ)| < 𝜀 (function value is close to 0)
• |xₙ - xₙ₋₁| < 𝜀 (change in root is small)
• Fixed number of iterations reached

Stopping criteria are essential conditions that determine when to stop the iterative processes of numerical methods used for finding roots. These criteria are important because they guide the method to ensure results are achieved efficiently and accurately.

1. Function Value Close to Zero (|f(xₙ)| < 𝜀): This condition means that the calculated value of the function at the estimated root is very small, indicating that the root is likely found. Here, 𝜀 is a small threshold value (like 0.001), signifying precision.

2. Small Change in Estimates (|xₙ - xₙ₋₁| < 𝜀): This checks that the difference between successive root estimates is minimal, suggesting convergence to a stable solution.

3. Fixed Number of Iterations: Sometimes, methods are stopped after a predetermined number of iterations to prevent excessive computation, especially if the previous two conditions have not been met.

Imagine you're baking a cake. Instead of continuously checking if it's baked ('is it done yet?'), you have clear signals:

1. You check the cake's center—if a toothpick comes out clean (similar to |f(xₙ)| < 𝜀), you know it's likely ready.
2. You keep an eye on how much it rises compared to previous checks—and if it hasn't changed much (like |xₙ - xₙ₋₁| < 𝜀), you know it's not making more progress.
3. However, if you set a timer (fixed number of iterations), you’ll take it out even if you're not sure, avoiding disasters from overbaking!

--