Iterative Methods Solver
Understanding Iterative Methods
Iterative methods are numerical techniques used to find approximate solutions to equations, especially those that are difficult or impossible to solve analytically. These methods start with an initial guess (or guesses) and then apply a repetitive process (iteration) to generate a sequence of approximations that ideally converge to the true solution.
The process is typically stopped when the difference between successive approximations is smaller than a predefined tolerance or when a maximum number of iterations is reached.
Method of Bisection
The bisection method is a root-finding algorithm that repeatedly divides an interval in half and selects the subinterval in which a root must lie. It's simple and robust, but can be slow to converge.
Conditions: Requires an initial interval \([a, b]\) such that $f(a) \cdot f(b) < 0$. This guarantees at least one root in the interval if $f(x)$ is continuous.
Algorithm:
- Choose an interval \([a_0, b_0]\) such that $f(a_0)f(b_0) < 0$.
- Calculate the midpoint $c_n = \frac{a_n + b_n}{2}$.
- If $f(c_n)$ is close to 0 (or $|b_n - a_n|$ is small), then $c_n$ is the approximate root.
- If $f(a_n)f(c_n) < 0$, set $a_{n+1} = a_n, b_{n+1} = c_n$.
- Else, set $a_{n+1} = c_n, b_{n+1} = b_n$.
- Repeat from step 2.
Solve $f(x) = 0$ using Bisection
Method of Successive Approximations (Fixed-Point Iteration)
This method involves rearranging the equation $f(x) = 0$ into the form $x = g(x)$. An initial guess $x_0$ is made, and successive approximations are generated using the iterative formula $x_{n+1} = g(x_n)$.
Condition for Convergence: The iteration converges to a root if $|g'(x)| < 1$ in an interval around the root that contains $x_0$. The smaller the value of $|g (x)|$, the faster the convergence.
Algorithm:
- Rearrange $f(x) = 0$ into the form $x = g(x)$.
- Choose an initial guess $x_0$.
- Calculate $x_{n+1} = g(x_n)$.
- If $|x_{n+1} - x_n|$ is less than the desired tolerance, then $x_{n+1}$ is the approximate root.
- Otherwise, set $x_n = x_{n+1}$ and repeat from step 3.
Solve $x = g(x)$ using Fixed-Point Iteration
Newton-Raphson Method
The Newton-Raphson method is a powerful and often fast-converging iterative technique for finding roots of a real-valued function $f(x)$. It uses the tangent line to the function at the current approximation to find the next approximation.
Formula: Starting with an initial guess $x_0$, successive approximations are given by:
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
Conditions:
- $f(x)$ must be differentiable.
- $f'(x_n)$ must not be zero at any iteration.
- The initial guess $x_0$ should be sufficiently close to the actual root for convergence.
Solve $f(x) = 0$ using Newton-Raphson
The derivative $f'(x)$ will be calculated automatically.