Non-Linear Equations

⚡ Key Takeaways

Non-linear equations are equations in which the unknown appears in a form other than first-degree (e.g., squared, inside a sine, multiplied by itself), so the graph is not a straight line and the superposition principle fails. Key result in words: most non-linear equations cannot be solved in closed form, so we rely on existence theorems and iterative numerical methods (bisection, Newton–Raphson, fixed-point iteration) to locate roots. Where it applies: physics, engineering, economics, biology — anywhere rates depend non-trivially on the quantity itself. Who/when: roots of polynomials studied since Babylon (~1800 BCE); Newton's method (1669), Abel–Ruffini impossibility (1824).

💡 The Core Insight

Linearity grants superposition (solutions add) and scaling (solutions multiply by constants), which together give complete, formula-based solvability. Non-linearity destroys both. The compensating strategy is to abandon the search for one magic formula and instead (1) prove a root exists via continuity or contraction arguments, then (2) converge to it through repeated approximation. Every numerical root-finder is, at heart, a way of replacing the hard non-linear problem with a sequence of easy ones.

DefinitionNon-Linear Equation

A non-linear equation in the real variable $x$ is an equation of the form

1

\quad f(x) = 0

Derivation hint: any equation $g(x)=h(x)$ is rewritten as $f(x)=g(x)-h(x)=0$ ; "non-linear" means $f$ is not of the form $f(x)=ax+b$ . A root (or zero) of $f$ is a value $x^*$ satisfying $f(x^*)=0$ . The defining property of non-linearity is the failure of the superposition operator condition:

2

\quad f(\alpha x + \beta y) \ne \alpha\, f(x) + \beta\, f(y) \quad \text{for some } \alpha,\beta,x,y

Derivation hint: a function is linear (affine, $b=0$ ) iff it satisfies additivity $f(x+y)=f(x)+f(y)$ and homogeneity $f(\alpha x)=\alpha f(x)$ ; negating either gives non-linearity. Here $f:\mathbb{R}\to\mathbb{R}$ (or $\mathbb{R}^n\to\mathbb{R}^n$ for systems); $x^*$ is the root; $\alpha,\beta\in\mathbb{R}$ are scalars.

TheoremIntermediate Value Theorem (Existence of a Root)

If $f$ is continuous on the closed interval $[a,b]$ and $f(a)\,f(b)<0$ , then there exists at least one $x^*\in(a,b)$ with $f(x^*)=0$ .

4

\quad f \in C[a,b],\ \ f(a)f(b)<0 \ \Longrightarrow\ \exists\, x^*\in(a,b): f(x^*)=0

Derivation hint: connectedness of $[a,b]$ and continuity of $f$ force the image $f([a,b])$ to be an interval containing both a positive and a negative value, hence $0$ .

TheoremBanach Fixed-Point Theorem (Convergence of Iteration)

Let $g:[a,b]\to[a,b]$ be a contraction, i.e. $|g(x)-g(y)|\le L|x-y|$ with Lipschitz constant $0\le L<1$ . Then $g$ has a unique fixed point $x^*=g(x^*)$ , and the iteration $x_{n+1}=g(x_n)$ converges to it from any starting point.

5

\quad |x_n - x^*| \le \frac{L^n}{1-L}\,|x_1 - x_0|

Derivation hint: telescoping the contraction inequality gives a geometric bound on $|x_{n+1}-x_n|$ ; summing the geometric tail yields the error estimate.

ProofNewton–Raphson Iteration and its Quadratic Convergence

We derive the workhorse method for solving $f(x)=0$ and prove its convergence rate.

Step 1 — Linearize. Suppose $x_n$ approximates a root. Taylor-expand $f$ about $x_n$ :

6

\quad f(x) = f(x_n) + f'(x_n)(x-x_n) + \tfrac{1}{2}f''(\xi)(x-x_n)^2

Derivation hint: Taylor's theorem with Lagrange remainder, $\xi$ between $x$ and $x_n$ .

Step 2 — Solve the linear model. Drop the quadratic term and set $f(x)=0$ , solving for the new estimate $x_{n+1}$ :

7

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

Derivation hint: set the tangent line $f(x_n)+f'(x_n)(x-x_n)=0$ and solve for $x$ ; geometrically $x_{n+1}$ is where the tangent at $x_n$ crosses the axis.

Step 3 — Track the error. Let $e_n = x_n - x^*$ . Substituting $x=x^*$ into [6] (where $f(x^*)=0$ ) and rearranging using [7]:

8

\quad e_{n+1} = -\frac{f''(\xi)}{2f'(x_n)}\,e_n^2

Derivation hint: write $e_{n+1}=x_{n+1}-x^*$ , substitute [7], expand $f(x_n)$ and $f'(x_n)$ via Taylor about $x^*$ , and collect the leading term.

Step 4 — Conclude. As $x_n\to x^*$ , the prefactor tends to the constant $C=|f''(x^*)/2f'(x^*)|$ , giving

9

\quad |e_{n+1}| \approx C\,|e_n|^2

Derivation hint: take the limit $\xi,x_n\to x^*$ in [8]; $|e_{n+1}|/|e_n|^2 \to C$ defines quadratic convergence — the number of correct digits roughly doubles each step. This requires $f'(x^*)\ne 0$ (a simple root). At a multiple root, $f'(x^*)=0$ degrades convergence to linear. $\blacksquare$

∎

mathematician · Évariste Galois | 1811–1832

A French prodigy who, before dying in a duel at twenty, founded group theory to answer the ancient question: which equations are solvable by radicals? Galois showed that the solvability of a polynomial equation is governed by the structure of a finite group of permutations of its roots — its Galois group. The general quintic is unsolvable precisely because the symmetric group $S_5$ is not solvable. His midnight-before-the-duel manuscript, dismissed by Cauchy and Poisson during his life, became one of mathematics' foundational texts. Galois converted the brute computational question "find the roots" into the structural question "what symmetry do the roots possess" — the paradigmatic non-linear insight.

🧠 Intuition

Think of $f(x)=0$ as asking "where does the curve $y=f(x)$ touch the ground?" For a line, there is at most one crossing and you can compute it by eye. A non-linear curve wiggles: it may swoop down and back up (two crossings), graze the axis tangentially (a double root), or never reach it. Because the curve bends, knowing its value and slope here tells you only locally where it is heading — hence the iterative philosophy: take a step, look again, correct. Newton's method is literally "slide down the tangent line to where it hits the axis, and repeat"; if the curve is gently bending and you start near the root, each slide overshoots by an amount proportional to the square of your remaining error, which is why it converges with breathtaking speed.

Figure

Newton's method: the tangent at

x_n

crosses the axis at

x_{n+1}

, closing in on the root

x^*

.

ExampleNewton's Method for a Square Root

Given: Compute $\sqrt{2}$ by solving $f(x)=x^2-2=0$ , starting at $x_0=1.5$ .

Setup: $f'(x)=2x$ , so the iteration [7] becomes

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

Steps:

$x_0=1.5$
$x_1=\tfrac12(1.5+2/1.5)=\tfrac12(1.5+1.3333)=1.41\overline{6}$
$x_2=\tfrac12(1.41667+2/1.41667)=1.4142157$
$x_3=1.41421356237$ (matches $\sqrt2$ to 11 digits)

Notice the digit-doubling: after step 1 we have ~3 correct digits, after step 2 ~6, after step 3 ~11 — the hallmark of quadratic convergence.

Answer: $\boxed{\sqrt{2}\approx 1.41421356}$ (dimensionless).

ExampleBisection for a Transcendental Root

Given: Find the root of $f(x)=\cos x - x = 0$ (the Dottie number), known to lie in $[0,1]$ , to within $\pm 0.05$ .

Setup: $f(0)=\cos 0 - 0 = 1 >0$ , $f(1)=\cos 1 - 1 \approx 0.5403-1=-0.4597<0$ . A sign change confirms a root by [4]. Bisection halves the interval each step.

Steps:

$n$	$a$	$b$	$m=(a+b)/2$	$f(m)$	keep
0	0.000	1.000	0.500	$+0.378$	$[0.5,1]$
1	0.500	1.000	0.750	$-0.018$	$[0.5,0.75]$
2	0.500	0.750	0.625	$+0.186$	$[0.625,0.75]$
3	0.625	0.750	0.6875	$+0.085$	$[0.6875,0.75]$
4	0.6875	0.750	0.71875	$+0.034$	$[0.71875,0.75]$

Interval width is now $0.031 < 0.05$ .

Answer: $\boxed{x^*\approx 0.739}$ (the true Dottie number is $0.739085\ldots$ , dimensionless).

⚠️ Common mistake

A sign change is sufficient but not necessary for a root. The IVT [4] guarantees a root when $f(a)f(b)<0$ , but a function can have a root (even infinitely many) without any sign change on the bracket — e.g. a tangential double root where $f$ touches the axis without crossing. Conversely, bisection cannot find double roots because they produce no sign change. Likewise, "Newton's method always converges" is false: with a poor starting point it can diverge, oscillate in a cycle, or rocket off to a different root. Convergence is only guaranteed for a sufficiently close start near a simple root.

Counterexample

Consider $f(x)=x^2$ . Its only root $x^*=0$ is a double root: $f(0)=f'(0)=0$ . Bracketing fails — $f$ is non-negative everywhere, so no $[a,b]$ gives $f(a)f(b)<0$ , and bisection never starts. Newton's method does converge but only linearly: from $x_n$ ,

x_{n+1}=x_n-\frac{x_n^2}{2x_n}=\tfrac12 x_n,

so the error merely halves each step ( $e_{n+1}=\tfrac12 e_n$ ) instead of squaring. This single example demolishes both "every root has a sign change" and "Newton is always quadratic."

connection

Non-linear equations sit at the crossroads of pure and applied mathematics. Solving $f(x)=0$ where $f$ is a polynomial is the domain of Polynomial Equations and ultimately Galois Theory, which explains why no radical formula exists past degree four. The iterative methods generalize directly to systems via the multivariate Newton's Method using the Jacobian matrix, linking the topic to Linear Algebra. Existence arguments rest on Continuity and the Intermediate Value Theorem, while contraction-based convergence is pure Fixed-Point Theory. When the unknown is a function rather than a number, the subject becomes Non-Linear Differential Equations, whose qualitative behavior (limit cycles, chaos) is studied in Dynamical Systems.

🔬 Where this appears

⏳ History

- c. 1800 BCE — Babylonian tablets (e.g., YBC 7289) solve quadratics and approximate

\sqrt{2}

to remarkable precision via an iterative averaging method essentially identical to Newton's.

- c. 250 CE — Diophantus of Alexandria studies non-linear (Diophantine) equations seeking integer solutions.

- 820 CE — Al-Khwārizmī's al-Jabr systematizes the solution of quadratic equations, founding algebra.

- 1535 — Tartaglia and (controversially) Cardano publish the solution of the general cubic by radicals.

- 1540s — Ferrari solves the quartic, completing the radical-solvability of degrees ≤ 4.

- 1669 — Isaac Newton describes his iterative method (refined by Joseph Raphson in 1690) for approximating roots.

- 1799–1824 — Paolo Ruffini and Niels Henrik Abel prove the general quintic has no solution by radicals (the Abel–Ruffini theorem).

- 1830s — Évariste Galois develops group theory, giving the definitive criterion for solvability by radicals.

- 1922 — Stefan Banach proves his fixed-point theorem, providing the rigorous convergence foundation for iteration.

open-problem

Even with modern computers, finding all roots of a non-linear system in $\mathbb{R}^n$ remains genuinely hard: there is no general algorithm guaranteed to locate every solution, and the basins of attraction of Newton's method form intricate fractal boundaries (famously visualized as Newton fractals), so a tiny change in the starting guess can jump to a different root. Determining the number of real roots of a sparse polynomial system is connected to deep questions in real algebraic geometry and the Smale problems — Stephen Smale's list of unsolved problems for the 21st century asks for a polynomial-time algorithm to find an approximate zero of a polynomial system (the "Smale's 17th problem," with major progress by Beltrán–Pardo and Lairez but the deterministic version still open). For chaotic non-linear dynamics, even the existence of long-term predictable solutions can be provably impossible.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also