# Workbook 2 — Naive root finding > [!abstract] The problem > In class we sampled a scalar function $f$ on $[a,b]$ uniformly as $y_i = f(a+i\,\Delta x)$, $i=0,1,\dots,n$, with $\Delta x=(b-a)/n$. Using a **logic-flow diagram or pseudocode**, outline how to identify, from the sampled data alone, possible **roots** of $f$ — and what the **secant line** gives as an approximate root. --- ## 0. What are we actually being asked to do? This is not a "solve for the roots" problem — it is a "**describe the procedure**" problem. The computer does not have the formula for $f$; it has a table of dots $(x_i, y_i)$. From that table we must (a) **decide** that a root sits between two neighboring samples, and (b) **estimate** where it is. The deliverable is the *logic* — pseudocode or a flow diagram — not a finished program. > [!tip] The one idea to hold onto > A continuous curve cannot get from below the axis to above it without crossing zero. So a **sign change** between two consecutive samples guarantees (by the Intermediate Value Theorem) that a root lives in that little interval — even though we never see the curve between the dots. --- ## 1. Detecting a bracket: the sign-change test The nodes are $x_i = a + i\,\Delta x$ with spacing $\Delta x=(b-a)/n$: there are $n$ equal subintervals and $n+1$ nodes $x_0,\dots,x_n$. Between neighbors $x_i$ and $x_{i+1}$, if the samples sit on opposite sides of the axis, continuity forces a crossing: $y_i\,y_{i+1} < 0 \quad\Longrightarrow\quad \exists\, r\in(x_i,x_{i+1}) \text{ with } f(r)=0.$ The product is negative exactly when the two values have opposite signs — a one-line test. This is the [Intermediate Value Theorem](https://en.wikipedia.org/wiki/Intermediate_value_theorem) doing the work. ## 2. Estimating the root: the secant line We only have two points, so model the curve between them by the straight line through $(x_i,y_i)$ and $(x_{i+1},y_{i+1})$ — the [secant](https://en.wikipedia.org/wiki/Secant_line) — and take *its* root. From point–slope form with slope $m=\dfrac{y_{i+1}-y_i}{x_{i+1}-x_i}$, set $y=0$ and solve for $x$: $\boxed{\,x_c = x_i - y_i\,\frac{x_{i+1}-x_i}{y_{i+1}-y_i}.\,}$ This is [linear interpolation](https://en.wikipedia.org/wiki/Linear_interpolation): $x_c$ is where the connect-the-dots line crosses the axis. It is the *exact* root when $f$ is linear on the bracket, and a good estimate when $\Delta x$ is small. ## 3. The algorithm (pseudocode) ```text Require: samples (x_0,y_0),...,(x_n,y_n) with y_i = f(x_i) for i = 0, 1, ..., n-1: if y_i * y_{i+1} < 0: # sign change -> a root is bracketed x_c <- x_i - y_i * (x_{i+1}-x_i)/(y_{i+1}-y_i) # secant-line root estimate report / plot (x_c, f(x_c)) else if y_i == 0: # a sample landed exactly on a root report (x_i, 0) ``` As a **logic-flow diagram**: *start loop* → *is $y_i\,y_{i+1}<0$?* → **yes**: compute $x_c$, plot → **no**: skip → *next $i$* → *end*. > [!example]- Reference implementation (four languages) > All four scan consecutive samples of a precomputed `y` and mark the secant roots. > ```matlab > for i = 1:length(x)-1 > if y(i)*y(i+1) < 0 > xc = x(i) - y(i)*(x(i+1)-x(i))/(y(i+1)-y(i)); > plot(xc, f(xc), '*m', 'MarkerSize', 12, 'LineWidth', 2) > end > end > ``` > ```python > for i in range(len(x)-1): > if y[i]*y[i+1] < 0: > xc = x[i] - y[i]*(x[i+1]-x[i])/(y[i+1]-y[i]) > ax.plot(xc, f(xc), 'm*', ms=12) > ``` > ```r > for (i in 1:(length(x)-1)) { > if (y[i]*y[i+1] < 0) { > xc <- x[i] - y[i]*(x[i+1]-x[i])/(y[i+1]-y[i]) > points(xc, f(xc), pch=8, col="magenta", cex=2, lwd=2) > } > } > ``` > ```wolfram > Do[If[y[[i]] y[[i+1]] < 0, > xc = x[[i]] - y[[i]] (x[[i+1]]-x[[i]])/(y[[i+1]]-y[[i]]); > AppendTo[roots, {xc, f[xc]}]], {i, 1, Length[x]-1}] > ``` ## 4. What it catches — and what it misses - **Catches:** any **simple** (odd-multiplicity) crossing — one per bracket where the sign flips. - **Misses:** an **even-multiplicity** root (the curve touches the axis and turns back — no sign change), and **two roots inside one subinterval** (the endpoints can share a sign). - **Finer sampling** (larger $n$, smaller $\Delta x$) resolves more brackets and sharpens each secant estimate, but never fixes the even-multiplicity blind spot — that needs a better local model (a parabola; see Day 3). --- # Sanity checks and context ## 5. A worked spot-check Take $f(x)=x^2-2$ on $[0,2]$ with $n=4$, so $\Delta x=0.5$ and nodes $0,0.5,1,1.5,2$: | $x_i$ | 0 | 0.5 | 1 | 1.5 | 2 | |---|---|---|---|---|---| | $y_i=f(x_i)$ | $-2$ | $-1.75$ | $-1$ | $0.25$ | $2$ | The only sign change is between $x=1$ ($y=-1$) and $x=1.5$ ($y=0.25$). The secant estimate is $x_c = 1 - (-1)\cdot\frac{1.5-1}{0.25-(-1)} = 1 + \frac{0.5}{1.25} = 1.4,$ against the true root $\sqrt{2}\approx 1.4142$ — off by about $0.014$ on a coarse 4-interval grid. ## 6. Where this is going This naive finder is the engine for the term's root/critical-point work: run it on $f$ for roots, on $f'$ for critical points, on $f''$ for inflections. Its one weakness — even-multiplicity roots — is exactly what motivates **Day 3**, where a local **quadratic (Taylor) model** replaces the secant line and can find a root even where there is no sign change. ## 7. Common pitfalls > [!warning] Watch out for these > - **Loop bound.** Stop at $i=n-1$: the body reads index $i+1$, so going to $i=n$ runs off the end. > - **Node vs. interval count.** $n$ subintervals means $n+1$ nodes, and $\Delta x=(b-a)/n$. (In code that stores $N$ points you'd write $\Delta x=(b-a)/(N-1)$.) > - **Divide-by-zero.** If $y_{i+1}=y_i$ the secant is horizontal — but a genuine sign change makes $y_{i+1}-y_i\neq 0$, so inside the `if` you are safe. > - **Plotting height.** Use $f(x_c)$ for the marker's height, not the secant's value (which is $0$). ## 8. Checkpoint questions 1. Why does the *product* $y_i y_{i+1}$ (rather than the sum) detect opposite signs? 2. Sketch a function and a sampling for which the method reports **no** root even though two roots lie in $[a,b]$. What went wrong? 3. Show that if $f$ is linear on $[x_i,x_{i+1}]$, the secant estimate $x_c$ is the *exact* root. 4. You want critical points instead of roots. What do you feed the same algorithm, and why?