Derive: Change, Slopes and Approximation

Expand the function on both sides of $x$: $$f(x+h)=f+h{f}^{\prime }+\frac{h^2}{2}{f}^{\prime \prime }+\frac{h^3}{6}{f}^{\prime \prime \prime }+O(h^4),$$ $$f(x-h)=f-h{f}^{\prime }+\frac{h^2}{2}{f}^{\prime \prime }-\frac{h^3}{6}{f}^{\prime \prime \prime }+O(h^4).$$ For the forward difference, subtract $f(x)$ and divide by $h$: $$\frac{f(x+h)-f(x)}{h}=f^{\prime }+\frac{h}{2}{f}^{\prime \prime }+\frac{h^2}{6}{f}^{\prime \prime \prime }+O(h^3).$$ The first term after $f^{\prime }$ is $\frac{h}{2}{f}^{\prime \prime }$, so the error is proportional to $h$ and its constant is half the second derivative. For the central difference, subtract the second expansion from the first. The values $f$ and the second-derivative terms cancel, leaving $$f(x+h)-f(x-h)=2h{f}^{\prime }+\frac{h^3}{3}{f}^{\prime \prime \prime }+O(h^5),$$ and dividing by $2h$ gives $$\frac{f(x+h)-f(x-h)}{2h}=f^{\prime }+\frac{h^2}{6}{f}^{\prime \prime \prime }+O(h^4).$$ The first error term is now $\frac{h^2}{6}{f}^{\prime \prime \prime }$, so the error is proportional to $h^2$. The cancellation of the $h^2$ term is the whole gain: the central quotient spends one extra evaluation and removes the leading error.

Now test the predictions. At $x=1.5$ the derivatives are $f^{\prime \prime }=12x^2=27$ and $f^{\prime \prime \prime }=24x=36$. At $h=0.01$ the forward error predicted is $\frac{0.01}{2}\cdot 27=0.135$, and the observed forward estimate is $13.635601$ against the exact $13.5$, an error of $0.135601$. The extra $0.000601$ is the next term, $\frac{h^2}{6}{f}^{\prime \prime \prime }=\frac{0.0001}{6}\cdot 36=0.0006$, plus a smaller term. The central error predicted is $\frac{0.0001}{6}\cdot 36=0.0006$, and the observed central estimate is $13.5006$, an error of exactly $0.0006$. At $h=0.005$ the forward error is about $0.067650125$ and the central error is $0.00015$. Halving the step halved the forward error and quartered the central error, as the two formulas say. The same Taylor expansion that bounds a function's remainder in section 10.3 therefore prices the check in section 10.6: each extra power of $h$ in the error costs one more derivative in the bound.

The derivative of $x^2$ is $2x$, so the update is $$x_{k+1}=x_k-\alpha \cdot 2x_k=(1-2\alpha )x_k.$$ Unrolling from $x_0=1$ gives $$x_k=(1-2\alpha {)}^k.$$ This is the run from section 10.1 with ratio $r=1-2\alpha$. It tends to zero exactly when $|r|<1$, which is $$-1<1-2\alpha <1.$$ Subtract 1 from all three parts: $-2<-2\alpha <0$. Divide by $-2$ and flip the inequalities: $1>\alpha >0$. So the safe range is the open interval $0<\alpha <1$. At $\alpha =0.5$ the ratio is 0 and the run reaches the minimum in one step. At $\alpha =0.25$ the ratio is $0.5$ and the distance halves at every step. At $\alpha =0.75$ the ratio is $-0.5$: the run alternates sign while shrinking. Those three values all converge.

Now the counterexamples. At $\alpha =1$ the ratio is $-1$, so the run is $1,-1,1,-1,\dots$ forever. The size never changes, the loss stays at 1, and no step descends. At $\alpha =1.1$ the ratio is $-1.2$, so the run is $1,-1.2,1.44,-1.728,2.0736,-2.48832,2.985984,\dots$. The size grows by a factor $1.2$ at every step and the loss grows with it, so the algorithm climbs. The claim that subtracting a multiple of the gradient reduces the loss is therefore false unless the multiple is small, and this example says what small means: $\alpha$ must be below 1 for this quadratic, and the boundary is set by the second derivative, which is 2. The chapter's instruction to step a little is a condition on the product of the step size and the curvature, not a promise that any step works.

Start with the binomial expansion, $$(ax+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(ax{)}^k{b}^{n-k}.$$ The term $k=0$ is the constant $b^n$ and differentiates to zero. For $k\ge 1$, $$\frac{d}{dx}\left(\genfrac{}{}{0ex}{}{n}{k}\right)(ax{)}^k{b}^{n-k}=k(\genfrac{}{}{0ex}{}{n}{k})a^k{b}^{n-k}{x}^{k-1}.$$ Use $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ and put $j=k-1$: $$\frac{d}{dx}(ax+b{)}^n=na\sum _{j=0}^{n-1}(\genfrac{}{}{0ex}{}{n-1}{j})(ax{)}^j{b}^{n-1-j}=na(ax+b{)}^{n-1}.$$ The sum in the middle is the binomial expansion of $(ax+b{)}^{n-1}$, so the two ends agree. This proves the rule for every positive whole number $n$.

The chain rule gives the same result in one line. Set $u=ax+b$ and $y=u^n$. The outer rate is $dy/du=n{u}^{n-1}$ and the inner rate is $du/dx=a$. Their product is $$\frac{dy}{dx}=n{u}^{n-1}\cdot a=na(ax+b{)}^{n-1}.$$ The rule has two factors whatever the size of $n$, which is why a deep composition of powers stays a product of local rates rather than a sum.

Now the number. For $(3x-1{)}^5$ take $a=3$, $b=-1$ and $n=5$. At $x=2$ the inner value is $3\cdot 2-1=5$. The chain rule gives $$5\cdot 3\cdot 5^4=15\cdot 625=9375.$$ The expansion agrees. The polynomial is $243x^5-405x^4+270x^3-90x^2+15x-1$, whose derivative is $1215x^4-1620x^3+810x^2-180x+15$. At $x=2$ that is $19440-12960+3240-360+15=9375$. A nudge of $0.001$ in $x$ raises the inner value by $0.003$, and the outer rate at 5 is $5\cdot 5^4=3125$, so the linear prediction is a rise of about $9.375$ and a rate of $9375$. The actual finite-difference quotient at that step is about $9386.3$, higher because the function bends upward, and it falls toward $9375$ as the step shrinks. The check agrees with the formula to within the truncation error of the nudge, which is the same trade section 10.6 describes.