2NM4 Week 5: Root finding

Overview

Root finding begins by expressing equations as zeros of scalar or vector functions, then distinguishes analytical polynomial methods from iterative searches. The lecture compares bracketed bisection and false position with open secant and Newton-Raphson methods, explaining their convergence, assumptions, and failure modes. It extends Newton-Raphson to nonlinear systems using the Jacobian and shows how initial guesses determine basins of attraction, including fractal boundaries in the complex plane.

Key takeaways

For a continuous scalar function with opposite signs at two endpoints, a bracketed method has a root guarantee; a sign change across a discontinuity, such as 1/x at zero, invalidates that guarantee.
Bisection halves its bracket each iteration and converges linearly, while false position uses a secant crossing and has approximately 1.618 order convergence.
Newton-Raphson derives its update from a first-order Taylor expansion and converges quadratically near a suitable root, but requires a derivative and can diverge when the initial guess is poor or the slope is near zero.
For a system of nonlinear equations, Newton-Raphson replaces the scalar derivative with a Jacobian and solves a linear system for the vector-valued update.
Newton-Raphson finds local roots rather than all roots; in the complex plane, basins of attraction can have fractal boundaries where tiny changes to an initial guess change the converged root.
A polynomial's companion matrix converts root finding into an eigenvalue problem, allowing an eigenvalue solver to find all roots, including complex roots, without choosing an initial guess.

Chapters

0:00 Roots as Zeros of Scalar and Vector Equations

A root is a value of x for which f(x) = 0, extending the familiar solution of a linear equation ax = b.
The input and output can be scalar or vector; a system root makes every component of the output vector zero.
Root finding targets exact solutions, while optimization later addresses inconsistent systems and best-fit solutions.

3:38 Initial Guesses and Closed Versus Open Searches

Iterative solvers start from a guess, unlike many linear-system methods that can use a convenient zero initial vector.
Engineering judgment, simplified models, prior time steps, and knowledge of the physics can supply useful starting values.
Closed methods require a bracket around a root; open methods start from one or more guesses without a guaranteed bracket.

5:51 Graphical Root Counts and Plotting Artifacts

A graph can suggest where real roots lie, but plots are sampled points connected by lines, not exact representations of the function.
For 1/x, a plotting routine can draw a false segment across the vertical asymptote, even though the function has no root.
Functions such as sin(x²) can have infinitely many real roots, with roots becoming increasingly close together.

11:35 Complex Roots and Symmetry in Initial Guesses

The quadratic x² + 4 has two complex roots even though its real-valued graph never crosses zero.
For real-coefficient polynomials, non-real roots occur as conjugate pairs, symmetric about the real axis.
An iterative solver started exactly on the real axis can remain there and miss complex roots; a complex initial guess can reach them.

16:57 Pathological Functions Challenge Smooth-Solver Assumptions

Continuity and differentiability are different: |x| is continuous at zero but has a kink where its derivative is undefined.
The Weierstrass function is continuous and nowhere differentiable, demonstrating that a function can behave very differently from a smooth curve.
Discontinuities and sharp transitions can arise in engineering models with conditional logic or failure thresholds, so solvers cannot assume every function is smooth.

23:04 Polynomial Roots, Abel-Ruffini, and Companion Matrices

Polynomial equations have analytic formulas through degree four, but the Abel-Ruffini theorem rules out a general radical formula for degree five and higher.
A degree-n polynomial has exactly n roots when complex roots and multiplicity are counted, though some may not be real.
A companion matrix converts polynomial root finding into an eigenvalue problem.

26:00 Building Companion Matrices to Find Every Polynomial Root

Normalize the polynomial so its leading coefficient is one, place the negatives of its remaining coefficients across the companion matrix's top row, and place ones on the subdiagonal.
The companion matrix's characteristic polynomial recovers the original polynomial, so its eigenvalues are the polynomial roots.
An eigenvalue solver finds real and complex roots without an initial guess, although its numerical computation is iterative.

35:32 Linear Bases Connect Polynomial and Fourier Representations

Polynomials use powers of x as a linear basis, while Fourier series use sine and cosine terms at multiple frequencies.
Companion-matrix-style root methods can be adapted to some other bases, including Fourier and certain orthogonal polynomial bases.
Fourier representations are useful for periodic signals, but the lecture notes that this connection is clearer after studying Fourier analysis.

40:17 Choosing Polynomial Fits or RBFs for Data

For one-dimensional scalar data, a polynomial fit can be a practical first choice; nonlinear models such as A exp(-B/t) require nonlinear fitting instead.
High-order multivariable polynomials can oscillate badly, even when they pass through all supplied data points.
Radial basis functions, or RBFs, combine the influence of nearby data points and are a useful general tool for multidimensional interpolation.

48:00 RBF Kernels, Smoothing, and the Epsilon Scale

An RBF assigns each data point a radial sphere of influence, shaped by a kernel such as a Gaussian or inverse quadratic.
The parameter epsilon controls the kernel's width; average spacing between data points is a starting heuristic, not a universal rule.
Interpolation forces an RBF through every data point, while curve fitting can smooth noisy measurements and relax that exact-match requirement.

53:00 RBF Smoothness and Ill-Conditioned Data

Gaussian RBFs are infinitely differentiable, which can help gradient-based optimization avoid derivative discontinuities.
RBF systems become ill-conditioned when input points are coincident or nearly colocated, making results sensitive to roundoff error.
A pseudoinverse can handle some singular or rectangular systems, but it does not cure ill-conditioning; cubic splines can be a more stable alternative for one-dimensional data.

59:26 Bracketing Roots with the Intermediate Value Theorem

A continuous function with opposite signs at two endpoints has at least one root between them, by the intermediate value theorem.
Bracketing methods repeatedly query the function and keep the interval containing a sign change.
A sign change alone does not guarantee a root if the function is discontinuous, as with 1/x across its asymptote.

1:05:38 Bisection Narrows a Root Interval by Halves

Bisection evaluates the midpoint of the bracket and keeps the half-interval whose endpoints have opposite signs.
The procedure is a binary search and, for a continuous function with a valid bracket, reliably narrows toward a root.
A maximum-iteration limit protects against nonconvergence or invalid assumptions about continuity.

1:09:01 Bisection Convergence and Practical Stopping Tests

Bisection halves the interval on each iteration, giving linear convergence and requiring many function evaluations for high precision.
Stop when the change in the estimated x value or the bracket width falls below an absolute or relative tolerance.
Avoid testing whether two floating-point values are exactly equal; finite precision makes tolerance-based stopping more reliable.

1:18:22 False Position Uses Endpoint Values to Improve the Guess

False position draws a secant line between the bracket endpoints and uses where that line crosses zero as the next estimate.
The method retains the sign-based bracket update, combining a root guarantee with more information than bisection uses.
Its convergence order is approximately 1.618, the golden ratio, which is superlinear and typically faster than bisection.

1:21:41 False Position Demonstration and Bracketing Tradeoffs

For the example f(x) = cos(x) - x, the false-position illustration reaches the root in about four iterations, compared with about 16 for bisection.
False position works well when a local linear approximation describes the function near the root, but poor brackets or unusual shapes can slow progress.
Bracketing becomes difficult in multiple dimensions because a region needs more than two points to enclose a root.

1:27:30 Open Methods Trade Root Guarantees for Flexibility

Open methods discard the bracket, making them easier to extend to n-dimensional systems.
Without opposite-sign endpoints, open methods cannot guarantee that a root exists or that an iteration will converge.
The secant method keeps two starting estimates and extrapolates from their function values without maintaining a bracket.

1:36:23 The Secant Method Approximates the Derivative

The secant method draws a line through two evaluated points and uses its zero crossing as the next estimate.
It avoids requiring an analytic derivative and has the same approximately 1.618 convergence order as false position.
Unlike false position, secant iterations do not preserve a sign-changing interval, so they can diverge.

1:39:32 Newton-Raphson Uses a Tangent for Quadratic Convergence

Newton-Raphson uses one current estimate, its function value, and its derivative to find where the tangent crosses zero.
The update follows from the first-order Taylor expansion: set f(xₙ) + f′(xₙ)Δx approximately equal to zero, then update x.
Near a suitable root, Newton-Raphson has quadratic convergence, reducing error much faster than linear-convergence methods.

1:42:08 Analytic and Numerical Derivatives in Solver Software

Newton-Raphson requires both the function and its derivative; symbolic software can differentiate coupled models internally.
When an analytic derivative is unavailable, software can approximate it numerically by perturbing the input, which is related to the secant method.
A tangent uses the derivative at one point, while a secant estimates slope from two distinct points.

1:47:04 Newton-Raphson Failure with Complex Roots and Flat Slopes

For f(x) = x² + 2, the roots are complex, so a real initial guess can keep Newton-Raphson on the real axis and prevent it from finding either root.
A zero or near-zero derivative makes the update divide by zero or produce a very large step.
Newton-Raphson can jump away from a root or cycle instead of converging, so quadratic convergence applies only under suitable conditions.

1:51:40 Newton-Raphson Depends on a Good Starting Point

Newton-Raphson can take large, erratic steps before reaching a region where its local Taylor approximation is effective.
Engineering guesses can come from physical intuition, simplified models, or a previous time step in a time-dependent simulation.
A previous time-step solution is often a strong initial guess for the next step, unless the time step is too large or the system changes sharply.

1:55:00 Newton Iterations Can Diverge, Cycle, or Find Another Root

A tangent nearly parallel to the x-axis can send the next estimate far away, and repeated updates can form a cycle.
A starting point may converge to a different root than the one intended, since Newton-Raphson finds local roots rather than all roots.
No general guarantee connects an arbitrary initial guess to a desired root; solver success must be checked rather than assumed.

2:02:37 Multivariable Newton-Raphson and the Jacobian

For a vector function of a vector input, the Jacobian contains every partial derivative of each output component with respect to each input variable.
The Newton step solves a linear system involving the Jacobian and the current function residual to compute a vector increment.
This extends scalar Newton-Raphson to simultaneous nonlinear equations and brings the method back to linear-system solvers.

2:07:02 Initial Guesses Change Multivariable Newton Paths

A sample two-variable nonlinear system converges to the root (1, 1) from several initial guesses, but the number of iterations and residual path vary.
Starting values such as (3, 3), (10, 10), and (-10, -10) produce different iteration paths, including residuals that rise before falling.
A small final residual indicates that the equations are approximately satisfied, but engineering judgment is still needed to assess whether the solution is useful.

2:09:13 Complex Newton Basins Form Fractal Boundaries

Sampling complex initial guesses for a polynomial with three roots colors each point by the root to which Newton-Raphson converges.
The regions that converge to each root are basins of attraction, and their boundaries have a fractal structure.
Near those boundaries, tiny changes in the initial guess can produce a different root, so finite precision can make the outcome unpredictable.

Transcript excerpt

0:01 So moving on, root finders. Everybody know what a root is? The root of an equation. >> Not root. >> Anybody want to jump up? Why? You're already talking. This is your question for today. [laughter] >> What you got? >> What's that? >> You got it. Okay. So the roots of your equations are the zeros of the equation. When it becomes complicated is when you have nonlinear functions, right? So all of our linear functions, ax is equal to b. You move the b over to the other side and you get like just kind of a linear function. The root of that is the solution. The reason why we're calling it a root now and

0:48 moving it over to the other side is that we're going to generalize it to any f ofx. Um this can be a vector. It could be a scalar function with vector inputs i.e. f of x1, x2, x3. It could be a vector function of vector inputs. It could be a vector function of scalar inputs. Right? All that matters is that everything is satisfied down to zero. Right? So this guy is actually a vector equation of vector inputs. Right? X is a vector. The entire thing that zero is also a vector. Okay. B. So, what we're going to do now is we're going to try and attack like kind of the general case of how these things actually work. Um, we can seldom solve for the root

1:35 directly and that's going to be kind of a case that we're going to keep coming back and back to. There are a number of exceptions, linear systems being one of them. It is a special case. People call them like nonlinear systems. It's a bit of a misnomer, right? non the set

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Numerical Methods for Engineering.