UNIT 3 - ITERATIVE PROCESS

3.1 Definition of Iterative Process

An iterative process is a method of solving a problem through repeated application of a procedure. It involves a cycle of steps where each repetition builds upon the results of the previous one, gradually approaching the desired solution.

Key Aspects of an Iterative Process:

1. Repetition: A set of instructions or a process is applied multiple times.

2. Feedback: Each iteration uses the output of the previous iteration as its input, forming a feedback loop that informs the next step.

3. Convergence (Goal): The objective is to move toward a solution, a fixed point, or an optimal state. While the process may not reach an exact solution in a finite number of steps, it aims to get arbitrarily close.

4. Stopping Condition: Defines when the process should stop, which may be:

   • Reaching a desired level of accuracy or tolerance.

   • Performing a maximum number of iterations.

   • The change between successive iterations becomes smaller than a predefined threshold.

Key Characteristics of Iterative Processes:

• Approximation: Iterative processes often produce approximate solutions rather than exact ones.

• Convergence: A well-designed iterative process should converge to a solution.

• Computational Cost: The complexity of steps involved and the number of iterations required determine the computational cost.

3.2 The Bisection Method

The Bisection Method is a simple and robust numerical technique for finding the roots of a continuous function. It is a bracketing method, meaning it relies on an interval known to contain a root.

The method is based on the Intermediate Value Theorem, which states that if a continuous function f(x)f(x) takes on values of opposite signs at the endpoints of an interval [a,b][a, b], then it must have at least one root within that interval.

The Bisection Method repeatedly halves the interval [a,b][a, b] and keeps the subinterval where the sign change occurs, effectively squeezing in on the root.

Steps of the Bisection Method:

1. Initial Interval: Start with an interval [a,b][a, b] such that f(a)f(a) and f(b)f(b) have opposite signs (i.e., f(a)⋅f(b)<0f(a) \cdot f(b) < 0).

2. Midpoint Calculation: Compute the midpoint: c=a+b2c = \frac{a + b}{2}.

3. Subinterval Selection:

   • If f(c)=0f(c) = 0, then cc is the root, and the process stops.

   • If f(a)⋅f(c)<0f(a) \cdot f(c) < 0, then the root lies in [a,c][a, c], so set b=cb = c.

   • If f(b)⋅f(c)<0f(b) \cdot f(c) < 0, then the root lies in [c,b][c, b], so set a=ca = c.

4. Repeat: Go back to Step 2 and continue iterating.

5. Stopping Criterion: The process continues until a desired level of accuracy is reached, based on criteria such as:

   • The interval width ∣b−a∣|b - a| is smaller than a specified tolerance ε\varepsilon.

   • The absolute value ∣f(c)∣|f(c)| is smaller than a tolerance ε\varepsilon.

   • A maximum number of iterations is reached.

Advantages of the Bisection Method:

• Simplicity: Easy to understand and implement.

• Guaranteed Convergence: If the initial interval contains a root and the function is continuous, the method will converge.

• Robustness: Not very sensitive to the shape of the function.

Disadvantages of the Bisection Method:

• Slow Convergence: Convergence is linear, which can be slow compared to other methods.

• Requires an Interval: Needs an initial interval that brackets the root.

• Finds Only One Root: Cannot determine multiple roots in an interval.

3.3 The Order of Convergence of an Iterative Method

The order of convergence describes how quickly a sequence of approximations approaches the true solution.

Formal Definition:

Let {xn}\{x_n\} be a sequence that converges to a limit xx. If there exist constants C>0C > 0 and α>0\alpha > 0 such that: lim⁡n→∞∣xn+1−x∣∣xn−x∣α=C\lim_{n \to \infty} \frac{|x_{n+1} - x|}{|x_n - x|^\alpha} = C then the sequence {xn}\{x_n\} is said to converge to xx with order α\alpha. The constant CC is called the asymptotic error constant.

Interpretation:

• α=1\alpha = 1: Linear convergence (steady progress, but slow). The error decreases linearly with each iteration. It's like taking steps of roughly the same size each time. You make steady progress, but it might take many steps to reach the destination.

• α=2\alpha = 2: Quadratic convergence (error decreases much faster). The error decreases quadratically with each iteration. It's like doubling the length of your steps with each iteration. You cover ground much more quickly and reach the destination in fewer steps.

• α=3\alpha = 3: Cubic convergence (even faster convergence).

Importance of Order of Convergence:

• Efficiency: Higher-order convergence means faster, requiring fewer iterations to reach the solution.

• Computational Cost: Methods with higher-order convergence can significantly reduce the computational cost, especially for problems requiring high accuracy.

Determining the Order of Convergence:

• Theoretical Analysis: Analyzing the algorithm mathematically can often reveal its order of convergence. This might involve using Taylor series expansions or other techniques.

• Numerical Experiments: Running the algorithm for different initial guesses and observing how the error decreases with each iteration can provide an empirical estimate of the order of convergence.

Key Points

• The order of convergence is a crucial factor in assessing the efficiency of iterative methods.

• Higher-order convergence generally leads to faster convergence.

• The specific order of convergence can vary depending on the algorithm and the problem being solved.

3.4 Numerical Stability of Iterative Methods

Numerical stability a crucial property of iterative methods in numerical analysis. Describes how sensitive computed results are to small errors or perturbations. A numerically stable method will produce results that are only slightly affected by small errors, while an unstable method can amplify these errors, leading to wildly inaccurate results.

An iterative method is considered numerically stable if small changes or errors introduced during the computation (e.g., rounding errors due to finite precision arithmetic) do not lead to large deviations in the computed solution.

Types of Instability:

1. Rounding Error Propagation: Due to the finite precision of computers, each arithmetic operation introduces a tiny rounding error. In an unstable method, these small errors can accumulate and grow exponentially, eventually corrupting the entire solution.

2. Sensitivity to Initial Conditions: Some iterative methods are very sensitive to the initial guess or starting point. A small change in the initial guess can lead to drastically different results, even if the method itself is otherwise stable.

3. Growth of Errors: : Instability can manifest as the uncontrolled growth of errors during the iteration process. Even if the initial error is small, it can become large after a few iterations.

Factors Affecting Numerical Stability:

• Algorithm Choice: Some algorithms are inherently more stable than others.

• Problem Conditioning: Ill-conditioned problems can make even stable algorithms behave poorly.

• Floating-Point Precision: Higher precision can improve stability by reducing rounding errors.

Analyzing Numerical Stability:

1. Error Analysis: Mathematical techniques can be used to analyze how errors propagate through the iterative process. This often involves studying the growth of errors over multiple iterations.

2. Numerical Experiments: Running the algorithm with different initial guesses and observing how the results change can provide insights into stability. Introducing small perturbations into the input data and seeing how the solution is affected is also a common technique.

3. Stability Theory: Mathematical theory from numerical analysis provides tools for studying the stability of iterative methods. This often involves concepts like eigenvalues, norms, and matrix analysis.

Importance of Numerical Stability:

Numerical stability is a critical property of iterative methods. It describes how robust the method is to small errors during the computation. Stable methods are essential for obtaining reliable and accurate results in numerical computations. Understanding and analyzing numerical stability is a key part of numerical analysis.

• Reliability: Numerical stability is essential for the reliability of numerical computations. Unstable methods can produce garbage results, even if the algorithm is mathematically correct.

• Accuracy: Stability is closely related to accuracy. Unstable methods can amplify errors, making it impossible to obtain accurate solutions.

END OF UNIT 3