SC-09

Course 9

Nonlinear Equations and ODEs

Solve nonlinear equations $f(x) = 0$ and initial value problems for ordinary differential equations. From classical bisection to modern Runge-Kutta methods.

Learning Objectives

Implement bisection and fixed-point iteration
Apply Newton's method and understand its convergence
Use secant and hybrid methods when derivatives are unavailable
Implement Euler's method for ODE initial value problems
Apply Runge-Kutta methods for higher accuracy
Understand stability and stiffness in ODEs

1. Bisection Method

The simplest root-finding method: repeatedly halve an interval containing a root.

Algorithm Bisection Method

Input: $f$ , interval $[a, b]$ with $f(a)f(b) < 0$ , tolerance $\epsilon$

While $b - a > \epsilon$ :
Compute midpoint $c = (a + b)/2$
If $f(c) = 0$ , return $c$
If $f(a)f(c) < 0$ , set $b = c$
Else set $a = c$
Return $(a + b)/2$

Theorem 9.1: Bisection Convergence

After $n$ iterations, the error satisfies:

|x_n - r| \leq \frac{b - a}{2^{n+1}}

Convergence is linear with rate $1/2$ .

Remark:

Bisection is slow but reliable. It's often used to get a good initial guess for faster methods like Newton's method.

2. Fixed-Point Iteration

Definition 9.1: Fixed-Point Problem

Rewrite $f(x) = 0$ as $x = g(x)$ . A fixed point of $g$ is a value $x^*$ such that $g(x^*) = x^*$ .

Iterate: $x_{n+1} = g(x_n)$

Theorem 9.2: Convergence Criterion

If $g \in C^1$ on an interval containing $x^*$ and $|g'(x^*)| < 1$ , then fixed-point iteration converges locally with rate $|g'(x^*)|$ .

If $|g'(x^*)| > 1$ , the iteration diverges from $x^*$ .

Example: Choosing g(x)

To solve $x^3 - x - 1 = 0$ :

$g_1(x) = x^3 - 1$ → $|g_1'(x^*)| \approx 4.5 > 1$ (diverges)
$g_2(x) = (x + 1)^{1/3}$ → $|g_2'(x^*)| \approx 0.24 < 1$ (converges)

3. Newton's Method

Definition 9.2: Newton's Iteration

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

Geometric interpretation: Follow the tangent line at $(x_n, f(x_n))$ to the x-axis.

Theorem 9.3: Quadratic Convergence

If $f \in C^2$ near simple root $r$ and $x_0$ is close enough to $r$ :

|e_{n+1}| \leq \frac{M}{2m} |e_n|^2

where $M = \max|f''|$ , $m = \min|f'|$ near $r$ .

Example: Newton's Method

Find $\sqrt{2}$ by solving $f(x) = x^2 - 2 = 0$ :

x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right)

$n$	$x_n$	Error
0	1.0	0.414
1	1.5	0.086
2	1.41667	0.0025
3	1.41421	$2 \times 10^{-6}$

Definition 9.3: Secant Method

Replace $f'(x_n)$ with finite difference approximation:

x_{n+1} = x_n - f(x_n) \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}

Convergence order: $\phi = (1 + \sqrt{5})/2 \approx 1.618$ (golden ratio).

4. Euler Method for ODEs

Consider the initial value problem: $y' = f(t, y)$ , $y(t_0) = y_0$ .

Definition 9.4: Forward Euler Method

y_{n+1} = y_n + h f(t_n, y_n)

where $h$ is the step size and $t_{n+1} = t_n + h$ .

Theorem 9.4: Euler Error

Local truncation error: $O(h^2)$

Global error: $O(h)$ (Euler is a first-order method)

Definition 9.5: Backward Euler (Implicit)

y_{n+1} = y_n + h f(t_{n+1}, y_{n+1})

Requires solving for $y_{n+1}$ at each step. More stable for stiff problems.

Example: Euler Method

Solve $y' = -y$ , $y(0) = 1$ with $h = 0.1$ :

y_{n+1} = y_n + 0.1(-y_n) = 0.9 y_n

At $t = 1$ : $y_{10} = 0.9^{10} \approx 0.349$ (exact: $e^{-1} \approx 0.368$ )

5. Runge-Kutta Methods

Runge-Kutta methods achieve higher accuracy by evaluating $f$ at multiple points within each step.

Definition 9.6: Second-Order Runge-Kutta (Midpoint)

k_1 = f(t_n, y_n)

k_2 = f\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_1\right)

y_{n+1} = y_n + h k_2

This is a second-order method with local error $O(h^3)$ .

Definition 9.7: Classical Fourth-Order Runge-Kutta (RK4)

k_1 = f(t_n, y_n)

k_2 = f\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_1\right)

k_3 = f\left(t_n + \frac{h}{2}, y_n + \frac{h}{2}k_2\right)

k_4 = f(t_n + h, y_n + h k_3)

y_{n+1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4)

Theorem 9.5: RK4 Error

RK4 is a fourth-order method: local error $O(h^5)$ , global error $O(h^4)$ .

Multistep Methods

Adams-Bashforth (explicit) and Adams-Moulton (implicit) use previous solution values:

y_{n+1} = y_n + h\sum_{j=0}^{k} b_j f_{n-j}

Stiff Equations

Stiff ODEs have widely varying time scales. Explicit methods require tiny steps. Use implicit methods (backward Euler, BDF, implicit RK) which are A-stable.

Remark:

Modern ODE solvers use adaptive step size control, comparing solutions at different orders to estimate error and adjust $h$ automatically.

Practice Quiz

Nonlinear Equations and ODEs Quiz

Questions

Correct

Accuracy

The bisection method guarantees convergence if:

Easy

Not attempted

Newton's method has convergence order:

Easy

Not attempted

The Euler method for

y' = f(t, y)

has local truncation error:

Easy

Not attempted

Fixed-point iteration

x_{n+1} = g(x_n)

converges if:

Medium

Not attempted

The secant method approximates Newton's method by:

Medium

Not attempted

The classical 4th-order Runge-Kutta method evaluates

f

how many times per step?

Medium

Not attempted

For a multiple root

f(x) = (x - r)^m g(x)

with

m > 1

, standard Newton's method:

Hard

Not attempted

An ODE method is called implicit if:

Hard

Not attempted

The order of the secant method convergence is:

Hard

Not attempted

Stiff ODEs are best solved with:

Hard

Not attempted

Frequently Asked Questions

When should I use Newton's method vs. bisection?

Newton's method: When you have a good initial guess and can compute derivatives. Fast convergence (quadratic) but may diverge with poor starting point.

Bisection: When you need guaranteed convergence or don't have derivatives. Slower (linear) but always works if initial bracket is valid.

How do I choose step size for ODE solvers?

Use adaptive step size control: estimate local error by comparing solutions at different orders, then adjust $h$ to keep error within tolerance. Libraries like MATLAB's ode45 or SciPy's solve_ivp do this automatically.

What is a stiff ODE and how do I recognize one?

A stiff ODE has solution components with vastly different time scales. Signs include:

Explicit methods require extremely small step sizes
Jacobian has eigenvalues with very different magnitudes
The solution appears smooth but explicit methods still struggle

Solution: Use implicit methods like backward Euler or BDF.

How do I solve systems of nonlinear equations?

Generalize Newton's method: for $F(\mathbf{x}) = \mathbf{0}$ :

\mathbf{x}_{n+1} = \mathbf{x}_n - J^{-1}(\mathbf{x}_n) F(\mathbf{x}_n)

where $J$ is the Jacobian matrix. In practice, solve $J \Delta \mathbf{x} = -F$ for the update.

Why is RK4 so popular?

RK4 offers an excellent balance: fourth-order accuracy with only 4 function evaluations per step. It's accurate enough for most non-stiff problems, easy to implement, and has good stability properties. For more demanding problems, use adaptive RK methods like Dormand-Prince (ode45).