--- # System prepended metadata title: Hybrid Root-Finding Algorithm tags: [Bisection, Numerical Analysis, Algorithm, Python, Root-finding, Newton's method] --- # Problem Pure root-finding methods often face a trade-off between robustness and efficiency. Bracketing methods such as the bisection method are guaranteed to converge but are slow, while open methods such as Newton’s method may converge rapidly but can fail without a good initial guess. Design and implement a hybrid root-finding algorithm that combines a bracketing method with a faster local method. Demonstrate the performance of your method on several nonlinear equations and compare it with standard methods in terms of convergence speed and robustness. # Solution First, we observe the limitations and constraints of Newton's method: 1. **Closeness Requirement:** Newton's method is derived from a first-order Taylor expansion, which is only accurate near the exact solution. Consequently, the method requires an initial guess that is sufficiently close to the root to guarantee convergence. 2. **Avoidance of Zero Slopes:** The derivative should ideally be bounded away from zero to prevent explosively large step sizes. A straightforward approach to overcome these limitations is to utilize the bisection method to narrow down the initial interval until the search space is close enough for Newton's method to converge safely. Furthermore, if a predicted Newton step fails or behaves badly during any iteration, the algorithm then switches to the bisection method to generate the next point. This safeguard guarantees at least a global linear rate of convergence. ## Explanation Therefore, we introduce two primary conditions to detect when Newton's method behaves erratically. **1. Out-of-Bounds Check (`out`)** We must verify whether the Newton iterate $$x_{new} = x - \frac{f(x)}{f'(x)}$$ lies within the current bracketing interval [a,b]. Instead of explicitly computing $x_{new}$ and checking the compound inequality $a\leq x_{new} \leq b$, we use an equivalent condition: $$(x_{new}-a)(x_{new}-b)>0$$ which holds if and only if $x_{new}$ lies outside the interval. Substituting the expression for $x_{new}$, we obtain: $$(x - \frac{f(x)}{f'(x)} - a)(x - \frac{f(x)}{f'(x)} -b)>0$$ Multiplying both sides by $[f'(x)]^2$ (which preserves the inequality), we arrive at the form used in the implementation: $$((x-b)f'(x) - f(x))((x-a)f'(x) - f(x))>0$$ This condition guarantees that any accepted Newton step remains inside the bracketing interval. If violated, the algorithm falls back to bisection to preserve the bracketing property. **2. Slow Convergence Check (`slow`)** Even when the Newton iterate remains inside the interval, it may still be ineffective if the step size is too large relative to recent progress. To address this, we impose the condition: $$\left| \frac{f(x)}{f'(x)} \right| \leq \frac{|\Delta x_{\text{old}}|}{2}$$ If this condition is violated, i.e., $$\left| \frac{f(x)}{f'(x)} \right| > \frac{|\Delta x_{\text{old}}|}{2}$$ the algorithm switches to bisection. To avoid division, this is equivalently written as: $$\vert 2f(x) \vert > \vert \Delta x_{old}\ f'(x) \vert$$ It is important to emphasize that this condition does not directly measure the true error $\vert x−x^* \vert$. Instead, it acts as a heuristic that ensures the Newton step is sufficiently small compared to the previous step, thereby avoiding overly aggressive or unproductive updates. **Why use $\Delta x$** Using the previous step size $\Delta x_{old}$ instead of the current interval width provides a form of memory in the iteration. This helps prevent undesirable behaviors such as: * oscillations between two points, and * repeated large steps that undo previous progress. In particular, if the method attempts to revisit a previous region or take a step comparable to earlier ones, the condition will likely be violated, triggering a fallback to bisection. **Remark** These safeguards do not guarantee optimal progress at every step, but they ensure that: * the iterates remain within the bracketing interval, and * the step size decreases in a controlled manner. Together, they provide a balance between the global reliability of bisection and the fast local convergence of Newton’s method. ## Algorithm: The algorithm is designed as follows: ![Screenshot 2026-05-03 at 3.12.08 PM](https://hackmd.io/_uploads/BkKar_VC-x.png) # Experiments [Implement (Python code)](https://colab.research.google.com/drive/1zhYLgUgOBQ-lAdxE4tov7KxiL1_VnEQy?usp=sharing) We then tested the algorithms across five distinct equations, including nonlinear functions. 1. P2: $f(x) = \tan(x) - x$ 2. P5: $f(x) = \cos(x) - x$ 6. P6: $f(x) = e^x \sin(x)$ 4. P4: $f(x) = x^3 - 2x + 2$ 7. P7: $f(x) = (x-e)^5$ For each experiment, we provide the same initial bracket and initial point across all four methods: bisection, hybrid, Newton, and secant. The initial bracket for the secant method is identical to that of the bisection and hybrid methods, and the initial point for Newton's method is always chosen as the right endpoint of the initial bracket. > The convergence history for each method was recorded by plotting the absolute residual $|f(x_k)|$ against the iteration number $k$. ### f(x) = tan(x)-x ![convergence_2](https://hackmd.io/_uploads/H1qGbi7aWg.png) ### f(x) = cos(x) - x ![convergence_5](https://hackmd.io/_uploads/SJiZMsQabl.png) ### f(x) = e^x sin(x) ![convergence_6](https://hackmd.io/_uploads/rknxCi7Tbe.png) In the previous experiments, the hybrid algorithm only executed Newton steps. The difference arises not only from the initial point, but also from the safeguard conditions (`out` and `slow`) that may override Newton steps. The hybrid method initializes at the midpoint of the bracket, whereas Newton's method begins at the right endpoint. These general examples show that the hybrid algorithm can converge as quickly as Newton's method. ### f(x) = x^3 -2x + 2 ![convergence_4](https://hackmd.io/_uploads/Skwj_sVpZl.png) ![convergence_hybrid_4](https://hackmd.io/_uploads/SytqujN6bx.png) For $f(x) = x^3 - 2x + 2$, starting with the initial guess $x_0 = 0$, we compute the iterations as follows: $$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 0 - \frac{0^3 - 2(0) + 2}{3(0)^2 - 2} = -\frac{2}{-2} = 1$$ $$x_2 = x_1 - \frac{f(x_1)}{f'(x_1)} = 1 - \frac{1^3 - 2(1) + 2}{3(1)^2 - 2} = 1 - \frac{1}{1} = 0$$ Since $x_2 = 0 = x_0$, the iteration becomes trapped in an infinite cycle between $0 \to 1 \to 0 \to 1 \to \cdots$, and will never converge to the true root at $x \approx -1.769$. Conversely, the hybrid algorithm avoids this infinite loop because it detects the lack of sufficient convergence progress. Upon detecting this cycle, it safely falls back to a bisection step, effectively breaking the loop and ensuring global convergence. ### f(x) = (x-e)^5 ![convergence_7](https://hackmd.io/_uploads/Byir3iVaWg.png) ![convergence_hybrid_7](https://hackmd.io/_uploads/S1kD3sEp-x.png) [Desmos visualization](https://www.desmos.com/calculator/wshs6rcgsj) | k | x - e | fv | df | dx_old | Newton_step | 2\|fv\| | \|dxold·df\| | slow | |:---:|---:|---:|---:|---:|---:|---:|---:|:---| | 1 | 2.537e-02 | 3.2103e-08 | 5.0606e-06 | 1.5000e+00 | 6.3436e-03 | 6.4205e-08 | 7.5909e-06 | F | | 2 | 2.029e-02 | 1.0519e-08 | 2.0728e-06 | 6.3436e-03 | 5.0749e-03 | 2.1039e-08 | 3.1092e-06 | F | | 3 | -3.489e-01 | 3.4470e-09 | 8.4903e-07 | 5.0749e-03 | 4.0599e-03 | 6.8940e-09 | 5.3859e-09 | T ← BIS | | 4 | -1.643e-01 | -5.1769e-03 | 7.4170e-02 | 3.6929e-01 | 6.9798e-02 | 1.0354e-02 | 3.7641e-04 | T ← BIS | | 5 | -1.314e-01 | -1.1989e-04 | 3.6476e-03 | 1.8465e-01 | 3.2869e-02 | 2.3979e-04 | 1.3470e-03 | F | | 6 | -1.051e-01 | -3.9286e-05 | 1.4940e-03 | -3.2869e-02 | 2.6295e-02 | 7.8573e-05 | 2.7587e-04 | F | | 7 | -4.244e-02 | -1.2873e-05 | 6.1196e-04 | -2.6295e-02 | 2.1036e-02 | 2.5747e-05 | 2.0115e-05 | T ← BIS | | 8 | -3.395e-02 | -1.3770e-07 | 1.6222e-05 | 6.2740e-02 | 8.4882e-03 | 2.7539e-07 | 4.2656e-07 | F | | 9 | -2.716e-02 | -4.5120e-08 | 6.6445e-06 | -8.4882e-03 | 6.7905e-03 | 9.0240e-08 | 4.1688e-07 | F | | 10 | -3.431e-03 | -1.4785e-08 | 2.7216e-06 | -6.7905e-03 | 5.4324e-03 | 2.9570e-08 | 2.3101e-08 | T ← BIS | By observing the last three columns of the table, we can see that the slow condition is triggered cyclically. This explains why the plot above switches back and forth between the bisection and Newton methods. # Analysis Here we will show that this hybrid algorithm has global convergence and eventually iterates using newton method for simple roots. ## 1. Setup and Notation | Symbol | Meaning | |--------|---------| | $f \in C^2([a_0, b_0])$ | twice continuously differentiable objective | | $r \in (a_0, b_0)$ | unique simple root, $f(r) = 0$ | | $m = \min_{[a_0,b_0]} \lvert f'(x)\rvert > 0$ | minimum derivative magnitude | | $M = \max_{[a_0,b_0]} \lvert f''(x)\rvert < \infty$ | maximum second-derivative magnitude | | $[a_k, b_k]$ | bracket after $k$ iterations, $f(a_k)f(b_k) \le 0$ | | $L_k = b_k - a_k$ | bracket length at step $k$ | | $x_k$ | current iterate | | $e_k = x_k - r$ | signed error | | $B_k$ | number of bisection steps taken in the first $k$ iterations | | $K = M/(2m)$ | Newton convergence constant | ## 2. Lemmas ### Lemma 1 — Bracket Preservation **Statement.** For all $k \ge 0$: 1. $f(a_k)\,f(b_k) \le 0$, so $r \in [a_k, b_k]$. 2. $\lvert e_k\rvert \le L_k$. **Proof.** By induction. *Base case* ($k=0$): given by hypothesis. Inductive step: suppose the bracket $[a_k, b_k]$ satisfies (1). The algorithm evaluates $f(x_{k+1})$ for the chosen point $x_{k+1} \in [a_k, b_k]$ (containment is guaranteed by `out` for Newton steps, and is obvious for bisection). It then sets $$[a_{k+1}, b_{k+1}] = \begin{cases} [a_k, x_{k+1}] & \text{if } f(x_{k+1})\,f(b_k) \le 0, \\ [x_{k+1}, b_k] & \text{otherwise.} \end{cases}$$ Either way, the new bracket retains a sign change, so (1) holds. Part (2) follows because $r \in [a_k, b_k]$ implies $\lvert x_k - r\rvert \le b_k - a_k = L_k$. $$\tag*{$\square$}$$ --- ### Lemma 2 — Newton's Quadratic Error Bound **Statement.** If iteration $k+1$ is a Newton step, then there exists $\xi_k$ strictly between $x_k$ and $r$ such that $$e_{k+1} = \frac{f''(\xi_k)}{2\,f'(x_k)}\,e_k^2, \qquad \lvert e_{k+1}\rvert \le K\lvert e_k\rvert^2.$$ > This is the reason that $f\in C^2$ **Proof.** Apply Taylor's theorem with Lagrange remainder to $f(r)$ expanded around $x_k$: $$0 = f(r) = f(x_k) + f'(x_k)(r - x_k) + \frac{f''(\xi_k)}{2}(r - x_k)^2.$$ Rearranging (and recalling $r - x_k = -e_k$): $$f(x_k) = f'(x_k)\,e_k - \frac{f''(\xi_k)}{2}\,e_k^2.$$ Dividing through by $f'(x_k) \ne 0$: $$\frac{f(x_k)}{f'(x_k)} = e_k - \frac{f''(\xi_k)}{2\,f'(x_k)}\,e_k^2.$$ The Newton step gives $x_{k+1} = x_k - f(x_k)/f'(x_k)$, so $$e_{k+1} = x_{k+1} - r = (x_k - r) - \frac{f(x_k)}{f'(x_k)} = e_k - \Bigl(e_k - \frac{f''(\xi_k)}{2\,f'(x_k)}e_k^2\Bigr) = \frac{f''(\xi_k)}{2\,f'(x_k)}\,e_k^2.$$ Taking absolute values: $$\lvert e_{k+1}\rvert \le \frac{M}{2m}\,\lvert e_k\rvert^2 = K\lvert e_k\rvert^2.$$ $$\tag*{$\square$}$$ ## 3. Main theorem ### Part (a). Global Convergence Guarantee **Statement.** For all $k \ge 0$, $\lim_{k \to \infty} x_k = r$ and the limit error $\lim_{k \to \infty} \lvert e_k\rvert = 0$. **Proof.** Observe that each Bisection step halves the interval length: $L_{k+1} = L_k / 2$ and every Newton step strictly replaces one endpoint, ensuring $L_{k+1} < L_k$. We consider two cases based on the number of times the Bisection step is triggered during the iterations. Case 1: *The algorithm keeps executing Bisection steps.* Since Bisection occurs infinitely often ($B_k \to \infty$), the interval length approaches zero: $$L_k \le \frac{L_0}{2^{B_k}} \to 0$$ By Lemma 1(2), $\lvert e_k\rvert \le L_k$, thus $\lvert e_k\rvert \to 0$, meaning the algorithm converges to the root $r$. Case 2: *The algorithm executes only finitely many Bisection steps.* This means there exists an integer $N$ such that for all $k \ge N$, the algorithm only executes Newton steps. If only Newton steps are taken, the `slow` test evaluated in the code must be False for all $k \ge N$. The condition for the slow test is $\lvert 2 f(x_k)\rvert > \lvert \Delta x_{\text{old}} \cdot f'(x_k)\rvert$. Since the test fails, we must have: $$\lvert 2 f(x_k)\rvert \le \lvert \Delta x_{\text{old}} \cdot f'(x_k)\rvert \implies \left\lvert \frac{f(x_k)}{f'(x_k)} \right\rvert \le \frac{1}{2} \lvert \Delta x_{\text{old}}\rvert$$ For a Newton step, the current displacement is $\lvert \Delta x_k\rvert = \left\lvert \frac{f(x_k)}{f'(x_k)} \right\rvert$, so: $$\lvert \Delta x_k\rvert \le \frac{1}{2} \lvert \Delta x_{k-1}\rvert$$ This implies that from step $N$ onwards, the step size is at least halved each time. The sequence of displacements forms a geometric progression, meaning the sequence of iterates $\{x_k\}$ is a Cauchy sequence, and thus it must converge. Furthermore, since the step size $\Delta x_k = f(x_k)/f'(x_k) \to 0$ and $\lvert f'(x_k)\rvert$ is bounded by $m > 0$, we deduce $f(x_k) \to 0$. Therefore, the limit point must be $r$, which proves $\lvert e_k\rvert \to 0$. $$\tag*{$\square$}$$ --- ### Part (b). Asymptotic Quadratic Convergence **Statement.** There exists a finite threshold index $k^*$ such that for all $k \ge k^*$, the algorithm executes only Newton steps, achieving quadratic convergence: $\lvert e_{k+1}\rvert \le K\lvert e_k\rvert^2$. **Proof.** From Part (a), we know the algorithm has global convergence, meaning $L_k \to 0$ and $\lvert e_k\rvert \to 0$. Therefore, there must exist some $k_0$ such that for $k \ge k_0$, the current interval length satisfies: $$L_k < \frac{1}{4K}$$ Since both the root $r$ and the current point $x_k$ are contained within the interval, this guarantees $\lvert e_k\rvert \le L_k < \frac{1}{4K}$. Inductive Hypothesis: Assume the transition from $x_{k-1}$ to $x_k$ was a Newton step, and the previous error was inside the safe region ($\lvert e_{k-1}\rvert < \frac{1}{4K}$).Because this step was a Newton step, we can legitimately apply Lemma 2 to the current error: $$\lvert e_k\rvert \le K\lvert e_{k-1}\rvert^2 \qquad \text{(Eq. 1)}$$ Inductive Step: We now stand at $x_k$ and must prove that the slow test for the next transition (from $x_k$ to $x_{k+1}$) will evaluate to False. Let $A = \lvert \Delta x_{\text{new}}\rvert$ be the anticipated Newton step size. Let $B = \frac{1}{2}\lvert \Delta x_{\text{old}}\rvert$ be half of the previous step size. The slow test is avoided if we can prove $A \le B$. **Step 1: Find the upper bound for $A$.** Using the Taylor expansion from Lemma 2, we can bound $A$ using $e_k$: $$A = \left\lvert \frac{f(x_k)}{f'(x_k)} \right\rvert = \left\lvert e_k - \frac{f''(\xi_k)}{2f'(x_k)} e_k^2 \right\rvert \le \lvert e_k\rvert + K\lvert e_k\rvert^2$$ **Step 2: Find the lower bound for $B$.** Since the previous step ($k-1$) was also a Newton step, we expand it similarly: $$\lvert \Delta x_{\text{old}}\rvert = \left\lvert \frac{f(x_{k-1})}{f'(x_{k-1})} \right\rvert = \left\lvert e_{k-1} - \frac{f''(\xi_{k-1})}{2f'(x_{k-1})} e_{k-1}^2 \right\rvert \ge \lvert e_{k-1}\rvert - K\lvert e_{k-1}\rvert^2$$ Thus, $B \ge \frac{1}{2} \left( \lvert e_{k-1}\rvert - K\lvert e_{k-1}\rvert^2 \right)$. **Step 3: Prove $A \le B$ holds.** Substitute the valid bound (Eq. 1) $\lvert e_k\rvert \le K\lvert e_{k-1}\rvert^2$ into the upper bound of $A$: $$A \le \left( K\lvert e_{k-1}\rvert^2 \right) + K\left( K\lvert e_{k-1}\rvert^2 \right)^2 = K\lvert e_{k-1}\rvert^2 + K^3\lvert e_{k-1}\rvert^4$$ To guarantee $A \le B$, we must show: $$K\lvert e_{k-1}\rvert^2 + K^3\lvert e_{k-1}\rvert^4 \le \frac{1}{2} \lvert e_{k-1}\rvert - \frac{1}{2} K\lvert e_{k-1}\rvert^2$$ Assuming we have not yet hit the exact root ($e_{k-1} \neq 0$), divide by $\lvert e_{k-1}\rvert$ and rearrange: $$\frac{3}{2}K\lvert e_{k-1}\rvert + K^3\lvert e_{k-1}\rvert^3 \le \frac{1}{2}$$ Recall our safe region definition: $\lvert e_{k-1}\rvert < \frac{1}{4K}$, which implies $K\lvert e_{k-1}\rvert < \frac{1}{4}$. Substituting this supremum into the Left Hand Side (LHS) yields: $$\text{LHS} < \frac{3}{2}\left(\frac{1}{4}\right) + \left(\frac{1}{4}\right)^3 = \frac{3}{8} + \frac{1}{64} = \frac{25}{64} \approx 0.3906$$ Since $0.3906 \le 0.5$ strictly holds, the condition $A \le B$ is satisfied. Therefore, the `slow` test fails, and the algorithm will choose the Newton method for step $k+1$. By mathematical induction, once the algorithm executes a single Newton step inside the region $\lvert e\rvert < 1/(4K)$, all future iterations will be pure Newton steps, confirming asymptotic quadratic convergence. $$\tag*{$\square$}$$ ## 4. Quantitative Summary | Phase | Condition | Method | Error bound | |-------|-----------|--------|-------------| | **Global** | any $k$ | bisection fallback | $\lvert e_k\rvert \le L_0/2^{B_k}$ | | **Asymptotic** | $\lvert e_k\rvert < 1/(4K)$ | pure Newton | $\lvert e_{k+1}\rvert \le K\lvert e_k\rvert^2$ | > Note that in worst-case scenarios ---- such as when $f \notin C^2$ or the function has multiple roots ---- the algorithm will still converge to the root $r$, as guaranteed by Part (a). However, the convergence may only be linear. Similar algorithm: [Brent's method, Dekker's method](https://en.wikipedia.org/wiki/Brent%27s_method)