You will implement **two classic numerical methods** for finding roots of equations of the form:

$$
f(x) = 0
$$

Because many equations cannot be solved analytically, **numerical root-finding methods** are widely used in scientific computing and engineering to approximate solutions.

## Methods to Implement

### **Bisection Method**

* Requires an interval ($$[a, b]$$) where the function changes sign.
* Repeatedly halves the interval to narrow down the root.
* Guaranteed to converge, but relatively slow compared to other methods.

### **Newton-Raphson Method**

* Uses the derivative of the function.
* Starts from an initial guess and iteratively refines the solution.
* Converges faster, but may fail if the derivative is zero or the initial guess is poor.

import unittest
import importlib
import math
import user_code


class TestRootFindingMethods(unittest.TestCase):

    def setUp(self):
        importlib.reload(user_code)
        self.f = lambda x: x**2 - 2
        self.df = lambda x: 2 * x
        self.true_root = math.sqrt(2)

    def test_bisection_finds_root(self):
        root, iterations = user_code.bisection_method(self.f, 1, 2, tol=1e-8)

        _dynamic_test(
            self,
            abs(root - self.true_root) <= 1e-8,
            "Bisection method approximates the root within tolerance",
            f"Bisection root {root} is not within tolerance of √2",
        )

    def test_newton_finds_root(self):
        root, iterations = user_code.newton_raphson(self.f, self.df, 1.5, tol=1e-8)

        _dynamic_test(
            self,
            abs(root - self.true_root) <= 1e-8,
            "Newton–Raphson method approximates the root within tolerance",
            f"Newton–Raphson root {root} is not within tolerance of √2",
        )

    def test_return_types(self):
        root_b, it_b = user_code.bisection_method(self.f, 1, 2)
        root_n, it_n = user_code.newton_raphson(self.f, self.df, 1.5)

        _dynamic_test(
            self,
            isinstance(root_b, float) and isinstance(it_b, int),
            "Bisection returns (float root, int iterations)",
            f"Bisection returned invalid types: {type(root_b)}, {type(it_b)}",
        )

        _dynamic_test(
            self,
            isinstance(root_n, float) and isinstance(it_n, int),
            "Newton–Raphson returns (float root, int iterations)",
            f"Newton–Raphson returned invalid types: {type(root_n)}, {type(it_n)}",
        )

    def test_iteration_limit_respected(self):
        _, it_b = user_code.bisection_method(self.f, 1, 2, tol=1e-20, max_iter=5)
        _, it_n = user_code.newton_raphson(self.f, self.df, 1.5, tol=1e-20, max_iter=5)

        _dynamic_test(
            self,
            it_b <= 5,
            "Bisection respects max_iter limit",
            f"Bisection exceeded max_iter (used {it_b})",
        )

        _dynamic_test(
            self,
            it_n <= 5,
            "Newton–Raphson respects max_iter limit",
            f"Newton–Raphson exceeded max_iter (used {it_n})",
        )

    def test_newton_converges_faster(self):
        _, it_b = user_code.bisection_method(self.f, 1, 2, tol=1e-8)
        _, it_n = user_code.newton_raphson(self.f, self.df, 1.5, tol=1e-8)

        _dynamic_test(
            self,
            it_n < it_b,
            "Newton–Raphson converges faster than Bisection",
            f"Newton–Raphson used {it_n} iterations, Bisection used {it_b}",
        )


def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)


if __name__ == "__main__":
    unittest.main()


test_main.py

Master the essential numerical methods for approximating mathematical problems on computers. This course blends mathematical intuition, algorithmic reasoning, and hands-on Python implementation to equip you with the tools for scientific computing.

Explore the motivations, limitations, and core concepts underlying numerical computation, including error sources and convergence.

Delve into the implementation and analysis of foundational numerical algorithms for differentiation, integration, and root-finding.

Master numerical approaches for solving ordinary differential equations and analyzing dynamic system stability.

Challenge: Implement and Compare Root-Finding Methods

Methods to Implement

Bisection Method

Newton-Raphson Method

解答