🔢Numerical Analysis I Unit 4 – Fixed-Point Iteration for Nonlinear Equations

What's the Big Idea?

• Fixed-point iteration is a numerical method for solving nonlinear equations of the form $f(x) = 0$
• Involves reformulating the equation into the form $x = g(x)$, where $g(x)$ is a function that maps the input value $x$ to itself
• The method starts with an initial guess $x_0$ and iteratively applies the function $g(x)$ to generate a sequence of approximations $x_1, x_2, \ldots$ that converge to the fixed point $x^*$
• The fixed point $x^*$ satisfies the condition $x^* = g(x^*)$, meaning it remains unchanged under the transformation defined by $g(x)$
  • For example, if $g(x) = \cos(x)$, the fixed point would be a value $x^*$ such that $\cos(x^*) = x^*$
• Convergence of the iterative process depends on the properties of the function $g(x)$ and the choice of the initial guess $x_0$
• Fixed-point iteration provides a simple and intuitive approach to solving nonlinear equations numerically
• Can be easily implemented using a loop structure in programming languages

Key Concepts to Grasp

• Nonlinear equations are equations where the highest power of the variable is greater than one or the equation involves transcendental functions (trigonometric, exponential, logarithmic)
• A fixed point of a function $g(x)$ is a value $x^*$ such that $g(x^*) = x^*$
  • Geometrically, a fixed point corresponds to the intersection of the graph of $y = g(x)$ with the line $y = x$
• Reformulating the original equation $f(x) = 0$ into the form $x = g(x)$ is crucial for applying fixed-point iteration
  • The choice of the function $g(x)$ affects the convergence properties of the method
• Convergence of fixed-point iteration depends on the contractivity of the function $g(x)$ in the neighborhood of the fixed point
  • A function is contractive if $|g'(x)| < 1$ in the vicinity of the fixed point
  • Contractivity ensures that the iterates move closer to the fixed point with each iteration
• The error in the approximation at each iteration can be estimated using the formula $|x_{n+1} - x_n|$, which measures the absolute difference between consecutive iterates
• The rate of convergence indicates how quickly the iterates approach the fixed point and is determined by the magnitude of $|g'(x^*)|$
  • Linear convergence occurs when $|g'(x^*)| < 1$, while quadratic convergence is achieved when $g'(x^*) = 0$

The Math Behind It

• Given a nonlinear equation $f(x) = 0$, the goal is to find a value $x^*$ such that $f(x^*) = 0$
• Fixed-point iteration reformulates the equation into the form $x = g(x)$, where $g(x)$ is a carefully chosen function
• The iterative scheme for fixed-point iteration is defined as:
  • $x_{n+1} = g(x_n)$, for $n = 0, 1, 2, \ldots$
  • Starting with an initial guess $x_0$, the method generates a sequence of approximations $x_1, x_2, \ldots$ by repeatedly applying the function $g(x)$
• Convergence of the iterative scheme is guaranteed by the Banach fixed-point theorem (also known as the contraction mapping theorem)
  • The theorem states that if $g(x)$ is a contraction mapping on a complete metric space, then it has a unique fixed point, and the sequence of iterates converges to that fixed point
• A function $g(x)$ is a contraction mapping if there exists a constant $L$ (called the Lipschitz constant) such that $|g(x) - g(y)| \leq L|x - y|$ for all $x$ and $y$ in the domain of $g$, and $0 \leq L < 1$
• The rate of convergence is determined by the magnitude of $|g'(x^*)|$:
  • Linear convergence: $|g'(x^*)| < 1$
  • Quadratic convergence: $g'(x^*) = 0$
• The error in the approximation at each iteration can be estimated using the formula:
  • $|x_{n+1} - x_n| \leq L|x_n - x_{n-1}|$, where $L$ is the Lipschitz constant

How It Actually Works

• Start with the nonlinear equation $f(x) = 0$ that needs to be solved
• Reformulate the equation into the form $x = g(x)$ by isolating $x$ on one side of the equation
  • The choice of $g(x)$ should be such that it is easy to evaluate and has good convergence properties
• Choose an initial guess $x_0$ as the starting point for the iteration
• Iteratively apply the function $g(x)$ to generate a sequence of approximations:
  • $x_1 = g(x_0)$
  • $x_2 = g(x_1)$
  • $x_3 = g(x_2)$
  • $\ldots$
• Continue the iteration until a specified convergence criterion is met, such as:
  • The absolute difference between consecutive iterates $|x_{n+1} - x_n|$ falls below a predefined tolerance $\varepsilon$
  • The maximum number of iterations is reached
• The final iterate $x_n$ is taken as the approximate solution to the nonlinear equation
• Assess the accuracy of the solution by evaluating the residual $|f(x_n)|$, which measures how close $x_n$ is to being a true root of $f(x)$
• If the desired accuracy is not achieved, you may need to:
  • Choose a different initial guess $x_0$
  • Reformulate the equation into a different form $x = g(x)$ with better convergence properties
  • Switch to a different numerical method

When to Use (and When Not to)

• Fixed-point iteration is suitable when:
  • The nonlinear equation can be easily reformulated into the form $x = g(x)$
  • The function $g(x)$ is contractive in the neighborhood of the fixed point, ensuring convergence
  • A good initial guess $x_0$ can be provided, close enough to the actual solution
• Fixed-point iteration is particularly effective for equations involving transcendental functions (trigonometric, exponential, logarithmic) or composite functions
• It can be used as a simple and intuitive method for finding approximate solutions to nonlinear equations
• Fixed-point iteration may not be the best choice when:
  • The equation cannot be easily reformulated into the form $x = g(x)$
  • The function $g(x)$ is not contractive near the fixed point, leading to slow or no convergence
  • The initial guess $x_0$ is far from the actual solution, causing the iteration to diverge or converge slowly
• In cases where fixed-point iteration is not suitable, other numerical methods such as Newton's method, secant method, or bisection method may be more appropriate
• Fixed-point iteration can be sensitive to the choice of the initial guess and the reformulation of the equation, so it may require experimentation to find a suitable setup
• It is important to analyze the convergence properties of the function $g(x)$ before applying fixed-point iteration to ensure its effectiveness

Common Pitfalls and Tricks

• Choosing an inappropriate function $g(x)$ when reformulating the equation can lead to slow convergence or divergence
  • Aim for a function $g(x)$ that is contractive near the fixed point
  • Avoid functions with steep gradients or oscillatory behavior near the fixed point
• Using an initial guess $x_0$ that is too far from the actual solution can result in a large number of iterations or failure to converge
  • If possible, use domain knowledge or graphical analysis to choose a reasonable initial guess
  • If multiple solutions exist, different initial guesses may converge to different solutions
• Insufficient tolerance for the convergence criterion can lead to premature termination of the iteration
  • Set the tolerance based on the desired accuracy of the solution
  • Be cautious of using a very small tolerance, as it may result in unnecessary iterations
• Overreliance on fixed-point iteration without considering other numerical methods
  • Fixed-point iteration may not always be the most efficient or robust method
  • Be aware of alternative methods such as Newton's method, secant method, or bisection method
• Tricks to improve convergence:
  • Experiment with different reformulations of the equation into the form $x = g(x)$
  • Try applying a relaxation parameter $\alpha$ to the iteration scheme: $x_{n+1} = \alpha g(x_n) + (1 - \alpha) x_n$
  • Use a hybrid approach by combining fixed-point iteration with other methods, such as using fixed-point iteration to refine an initial approximation obtained by another method

Real-World Applications

• Solving nonlinear equations arises in various fields, including engineering, physics, economics, and computer science
• Fixed-point iteration can be used to:
  • Find the equilibrium states of dynamical systems, such as the steady-state temperature distribution in a heat transfer problem
  • Determine the operating point of electronic circuits, such as the bias voltages and currents in a transistor amplifier
  • Compute the fixed points of complex mappings in chaos theory and fractal geometry
  • Solve optimization problems by reformulating them as fixed-point problems, such as in game theory and economics
• Specific examples:
  • In control systems, fixed-point iteration can be used to find the steady-state values of system variables, such as the position of a robotic arm or the speed of a motor
  • In computer graphics, fixed-point iteration is employed in algorithms for generating fractal patterns, such as the Mandelbrot set or Julia sets
  • In economics, fixed-point iteration can be applied to find the equilibrium prices in a market or the optimal strategies in game theory
• Understanding fixed-point iteration provides a foundation for tackling real-world problems that involve solving nonlinear equations numerically
• Applying fixed-point iteration to practical problems requires careful formulation of the equations, selection of appropriate initial guesses, and interpretation of the results in the context of the specific application domain

Practice Problems

1. Use fixed-point iteration to find a solution to the equation $x^3 - x - 1 = 0$, starting with an initial guess of $x_0 = 1$. Perform at least three iterations.

2. Consider the equation $e^x - x^2 = 0$. Reformulate the equation into the form $x = g(x)$ in two different ways. Determine which reformulation is more suitable for fixed-point iteration and explain why.

3. Apply fixed-point iteration to solve the equation $\cos(x) = x$, starting with an initial guess of $x_0 = 0.5$. Perform iterations until the absolute difference between consecutive iterates is less than $10^{-4}$.

4. Investigate the convergence of fixed-point iteration for the equation $x = e^{-x}$, starting with different initial guesses: $x_0 = 0$, $x_0 = 1$, and $x_0 = 2$. Observe the behavior of the iterates and explain the results.

5. Use fixed-point iteration to find a solution to the equation $x^3 + 4x^2 - 10 = 0$, starting with an initial guess of $x_0 = 1$. Perform at least three iterations and discuss the convergence of the method.

6. Consider the equation $x = \tan(x)$. Determine if fixed-point iteration is an appropriate method to solve this equation. If not, suggest an alternative numerical method and justify your choice.

7. Implement fixed-point iteration in a programming language of your choice to solve the equation $x^2 - 3x + 2 = 0$, starting with an initial guess of $x_0 = 0$. Perform iterations until the absolute difference between consecutive iterates is less than $10^{-6}$.

8. Analyze the convergence of fixed-point iteration for the equation $x = \sqrt{2x - 1}$, starting with an initial guess of $x_0 = 1$. Determine the fixed point analytically and compare it with the numerical results obtained from fixed-point iteration.