Chapter 2
Nonlinear Equations
Rendered from the uploaded full LaTeX source with KaTeX. No PDF, no PDF.js, no image extraction, and no raw LaTeX displayed.
After completing this chapter, the reader should be able to:
formulate scalar and vector nonlinear root-finding problems;
distinguish bracketing, open, hybrid, interval, and quasi-Newton methods;
prove convergence of bisection, fixed-point iteration, Newton’s method, and the secant method;
derive local error equations and convergence orders;
analyze multiple roots and multiplicity-corrected iterations;
derive and compare cubic and quartic methods such as Chebyshev, Halley, super-Halley, Householder, Ostrowski, King, Jarratt, and Traub methods;
understand certified methods such as interval Newton and Krawczyk operators;
apply Newton–Kantorovich and Smale-type criteria;
understand nonlinear systems, Broyden updates, Newton–Krylov methods, and Anderson acceleration;
solve basic, advanced, and research-level exercises on nonlinear equations.
The Root-Finding Problem
The scalar nonlinear equation problem is to find \xi\in\mathbb R such that f(\xi)=0. The vector version is to find x^\ast\in\mathbb R^n such that F(x^\ast)=0, \qquad F:\mathbb R^n\to\mathbb R^n. Nonlinear equations arise in implicit time discretizations, nonlinear boundary-value problems, chemical equilibrium, nonlinear eigenvalue problems, bifurcation analysis, optimization, power-flow systems, mechanics, population models, and discretized nonlinear PDEs.
A linear equation has one global algebraic structure. A nonlinear equation may have no root, one root, many roots, multiple roots, singular roots, or roots with complicated basins of attraction. Therefore a serious root solver must address existence, localization, convergence, conditioning, certification, and stopping criteria.
Let f be sufficiently differentiable near \xi. The point \xi is a root of multiplicity m\ge1 if f(\xi)=f'(\xi)=\cdots=f^{(m-1)}(\xi)=0, \qquad f^{(m)}(\xi)\ne0. Equivalently, locally, f(x)=(x-\xi)^m g(x), \qquad g(\xi)\ne0. A root of multiplicity 1 is called simple.
Error, Residual, and Conditioning of a Root
Let \xi be a root of f. The error of an approximation x is e=x-\xi, whereas the residual is r=f(x). A small residual does not automatically imply a small error. The connection depends on the conditioning of the root.
Let f\in C^1 near a simple root \xi, so that f(\xi)=0, \qquad f'(\xi)\ne0. Let f be perturbed to f_\varepsilon(x)=f(x)+\varepsilon g(x), where g is continuous near \xi. If \xi_\varepsilon denotes a nearby root of f_\varepsilon, then \xi_\varepsilon = \xi - \varepsilon\frac{g(\xi)}{f'(\xi)} + O(\varepsilon^2). Thus the absolute sensitivity of the root is governed by \frac{1}{|f'(\xi)|}.
Assume \xi_\varepsilon=\xi+\varepsilon \eta+O(\varepsilon^2). The equation f_\varepsilon(\xi_\varepsilon)=0 gives f(\xi+\varepsilon\eta+O(\varepsilon^2)) + \varepsilon g(\xi+\varepsilon\eta+O(\varepsilon^2))=0. Taylor expansion and f(\xi)=0 yield \varepsilon \eta f'(\xi)+\varepsilon g(\xi)+O(\varepsilon^2)=0. Dividing by \varepsilon and taking the limit gives \eta=-\frac{g(\xi)}{f'(\xi)}. Therefore \xi_\varepsilon = \xi - \varepsilon\frac{g(\xi)}{f'(\xi)} + O(\varepsilon^2).
□
If f'(\xi) is small, then |f(x)| may be small while |x-\xi| is not. A robust root-finder should monitor both residual and step size, and should be aware of the local conditioning of the root.
Order of Convergence
Let x_k\to \xi, and set e_k=x_k-\xi. The sequence has order p>1 if there exists C>0 such that \lim_{k\to\infty} \frac{|e_{k+1}|}{|e_k|^p} = C. The constant C is the asymptotic error constant.
Linear convergence corresponds to |e_{k+1}|\approx q|e_k|, \qquad 0<q<1. Quadratic convergence corresponds to p=2, cubic to p=3, and quartic to p=4.
Bracketing Methods
Bracketing methods preserve an interval known to contain a root. They are slow but reliable.
Let f\in C[a,b]. If f(a)f(b)<0, then there exists at least one \xi\in(a,b) such that f(\xi)=0.
By the intermediate value theorem, the continuous image f([a,b]) contains every value between f(a) and f(b). Since f(a) and f(b) have opposite signs, zero lies between them.
□
Bisection
Caption.
Bisection method
f\in C[a,b], f(a)f(b)<0, tolerance \tau>0
While (b-a)/2>\tau:
m\gets(a+b)/2
If f(m)=0:
Return m
b\gets m
Else:
a\gets m
Return (a+b)/2
Let f\in C[a,b], f(a)f(b)<0, and let x_n be the midpoint after n bisection steps. Then b_n-a_n=\frac{b-a}{2^n}, \qquad |x_n-\xi|\le \frac{b-a}{2^{n+1}} for any root \xi\in[a_n,b_n].
At each step the interval is replaced by one of its halves. Thus b_n-a_n=\frac{b-a}{2^n}. Since x_n is the midpoint and \xi\in[a_n,b_n], |x_n-\xi|\le \frac{b_n-a_n}{2} = \frac{b-a}{2^{n+1}}.
□
Regula Falsi, Illinois, Pegasus, and Ridder Methods
The false-position method replaces the midpoint by the zero of the secant line: c=\frac{a f(b)-b f(a)}{f(b)-f(a)}. It preserves bracketing, but one endpoint may remain fixed for many iterations.
The Illinois method modifies the retained endpoint value by a factor 1/2 when the same endpoint survives repeatedly. Pegasus-type methods use a smoother damping factor. Ridder’s method uses an exponential interpolation idea and often converges faster than regula falsi while preserving a bracket.
Bisection is slow but guaranteed. False-position variants and Ridder-type methods try to preserve the guarantee while exploiting function values more intelligently.
Fixed-Point Iteration
A root problem may be rewritten as x=g(x). The fixed-point iteration is x_{k+1}=g(x_k).
A point \xi is a fixed point of g if g(\xi)=\xi.
Let g:[a,b]\to[a,b] satisfy |g(x)-g(y)|\le L|x-y|, \qquad 0\le L<1. Then g has a unique fixed point \xi\in[a,b]. Moreover, for every x_0\in[a,b], the sequence x_{k+1}=g(x_k) converges to \xi, and |x_k-\xi| \le \frac{L^k}{1-L}|x_1-x_0|.
For m>n, |x_m-x_n| \le \sum_{j=n}^{m-1}|x_{j+1}-x_j|. Since g is a contraction, |x_{j+1}-x_j| = |g(x_j)-g(x_{j-1})| \le L|x_j-x_{j-1}|. Induction yields |x_{j+1}-x_j|\le L^j|x_1-x_0|. Thus |x_m-x_n| \le \frac{L^n}{1-L}|x_1-x_0|. Hence \{x_k\} is Cauchy and converges to some \xi\in[a,b]. By continuity, \xi=\lim_{k\to\infty}x_{k+1} = \lim_{k\to\infty}g(x_k) = g(\xi). Uniqueness follows from |\xi-\eta|=|g(\xi)-g(\eta)|\le L|\xi-\eta|. Since L<1, \xi=\eta. Letting m\to\infty gives the error bound.
□
Aitken Acceleration and Steffensen’s Method
Suppose a scalar sequence x_k converges linearly: x_k=\xi+cq^k+o(q^k), \qquad |q|<1. Aitken’s \Delta^2 process defines \widehat{x}_k = x_k - \frac{(x_{k+1}-x_k)^2} {x_{k+2}-2x_{k+1}+x_k}.
If x_k=\xi+cq^k+dq^{2k}+o(q^{2k}), \qquad 0<|q|<1, then Aitken’s transform satisfies \widehat{x}_k-\xi=O(q^{2k}). Thus the leading linear error term is eliminated.
Write \Delta x_k=x_{k+1}-x_k = c(q-1)q^k+d(q^2-1)q^{2k}+o(q^{2k}), and \Delta^2 x_k=x_{k+2}-2x_{k+1}+x_k = c(q-1)^2q^k+d(q^2-1)^2q^{2k}+o(q^{2k}). Substituting into \widehat{x}_k=x_k-\frac{(\Delta x_k)^2}{\Delta^2x_k} shows that the term cq^k cancels, leaving an O(q^{2k}) error.
□
Steffensen’s method applies Aitken acceleration to fixed-point iteration without explicit derivatives: x_{k+1} = x_k - \frac{(g(x_k)-x_k)^2} {g(g(x_k))-2g(x_k)+x_k}. For sufficiently smooth g, it is often quadratically convergent near a simple fixed point.
Newton’s Method
Newton’s method replaces f near x_k by its tangent line: f(x_k)+f'(x_k)(x-x_k)=0. Therefore x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}.
Caption.
Newton’s method
f, f', starting value x_0, tolerance \tau>0
For k=0,1,2,\ldots:
If |f'(x_k)| is too small:
stop or switch to a safeguarded method
x_{k+1}\gets x_k-f(x_k)/f'(x_k)
If |x_{k+1}-x_k|\le\tau(1+|x_{k+1}|) and |f(x_{k+1})|\le\tau:
Return x_{k+1}
Let f\in C^2 near a simple root \xi, with f(\xi)=0, \qquad f'(\xi)\ne0. If x_0 is sufficiently close to \xi, then Newton’s method converges to \xi. Moreover, with e_k=x_k-\xi, e_{k+1} = \frac{f''(\xi)}{2f'(\xi)}e_k^2 + O(e_k^3).
Taylor expansion gives f(x_k) = f'(\xi)e_k+\frac12 f''(\xi)e_k^2+O(e_k^3), and f'(x_k) = f'(\xi)+f''(\xi)e_k+O(e_k^2). Since f'(\xi)\ne0, \frac{1}{f'(x_k)} = \frac{1}{f'(\xi)} \left[ 1-\frac{f''(\xi)}{f'(\xi)}e_k+O(e_k^2) \right]. Multiplying, \frac{f(x_k)}{f'(x_k)} = e_k-\frac{f''(\xi)}{2f'(\xi)}e_k^2+O(e_k^3). Thus e_{k+1}=e_k-\frac{f(x_k)}{f'(x_k)} = \frac{f''(\xi)}{2f'(\xi)}e_k^2+O(e_k^3).
□
Multiple Roots and Multiplicity Correction
Suppose f(x)=(x-\xi)^m g(x), \qquad m\ge2, \qquad g(\xi)\ne0. Then standard Newton iteration satisfies e_{k+1} = \left(1-\frac1m\right)e_k + O(e_k^2).
Since f'(x) = (x-\xi)^{m-1}\left[m g(x)+(x-\xi)g'(x)\right], we obtain \frac{f(x)}{f'(x)} = \frac{(x-\xi)g(x)} {m g(x)+(x-\xi)g'(x)} = \frac{x-\xi}{m}+O((x-\xi)^2). Therefore e_{k+1} = e_k-\frac{f(x_k)}{f'(x_k)} = \left(1-\frac1m\right)e_k+O(e_k^2).
□
If m is known, the modified Newton method x_{k+1}=x_k-m\frac{f(x_k)}{f'(x_k)} recovers quadratic convergence.
Semilocal Newton Theory
Let f\in C^2(I), where I\subset\mathbb R is an interval containing x_0. Assume f'(x_0)\ne0. Define \eta=\left|\frac{f(x_0)}{f'(x_0)}\right|, \qquad B=\left|\frac{1}{f'(x_0)}\right|. Suppose |f''(x)|\le M, \qquad x\in I. If h=BM\eta\le\frac12 and [x_0-r,x_0+r]\subset I, \qquad r=\frac{1-\sqrt{1-2h}}{BM}, then Newton’s method starting at x_0 converges to a root \xi\in[x_0-r,x_0+r].
The proof uses the quadratic majorant \phi(t)=\eta-t+\frac{BM}{2}t^2. The condition h\le1/2 ensures that \phi has the nonnegative zero r=\frac{1-\sqrt{1-2h}}{BM}. Using |f''|\le M, one shows that the Newton corrections for f are bounded by those of the majorant equation. This implies that the Newton sequence stays inside [x_0-r,x_0+r], and that the total correction length is finite. Hence x_k converges. Continuity gives f(\xi)=0.
□
Damped, Safeguarded, and Trust-Region Newton Methods
A damped Newton step has the form x_{k+1}=x_k+\lambda_k p_k, \qquad p_k=-\frac{f(x_k)}{f'(x_k)}, \qquad 0<\lambda_k\le1. For systems, J_F(x_k)p_k=-F(x_k). A line search chooses \lambda_k so that a merit function decreases, for example \phi(x)=\frac12\|F(x)\|^2. Trust-region methods restrict the step to \|p_k\|\le \Delta_k, and adjust the radius \Delta_k according to the agreement between predicted and actual decrease.
Caption.
Damped Newton method with residual line search
f, f', initial value x_0, \sigma\in(0,1), \rho\in(0,1)
For k=0,1,2,\ldots:
p_k\gets -f(x_k)/f'(x_k)
\lambda\gets1
While |f(x_k+\lambda p_k)|>(1-\sigma\lambda)|f(x_k)|:
\lambda\gets \rho\lambda
x_{k+1}\gets x_k+\lambda p_k
The Secant Method
The secant method replaces f'(x_k) by the divided difference \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}. Thus x_{k+1} = x_k - f(x_k)\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}.
Caption.
Secant method
f, initial values x_0,x_1, tolerance \tau>0
For k=1,2,\ldots:
d_k\gets f(x_k)-f(x_{k-1})
If d_k=0:
stop or restart
x_{k+1}\gets x_k-f(x_k)(x_k-x_{k-1})/d_k
If |x_{k+1}-x_k|\le \tau(1+|x_{k+1}|):
Return x_{k+1}
Let f\in C^2 near a simple root \xi, with f'(\xi)\ne0. If the secant iterates converge to \xi, then the order of convergence is p=\frac{1+\sqrt5}{2}.
Let e_k=x_k-\xi. A divided-difference expansion gives e_{k+1} = C e_k e_{k-1} + o(e_k e_{k-1}), \qquad C=\frac{f''(\xi)}{2f'(\xi)}. Assuming |e_{k+1}|\approx A|e_k|^p, we also have |e_k|\approx A|e_{k-1}|^p. The product relation gives |e_{k+1}| \approx |C|\,|e_k|\,|e_{k-1}| \approx |C|\,|e_k|^{1+1/p}. Hence p=1+\frac1p, and therefore p^2=p+1, \qquad p=\frac{1+\sqrt5}{2}.
□
Muller, Inverse Quadratic Interpolation, and Brent-Type Methods
Muller’s method fits a quadratic interpolant to (x_{k-2},f(x_{k-2})),\quad (x_{k-1},f(x_{k-1})),\quad (x_k,f(x_k)), and uses a root of the quadratic as the next iterate. It can produce complex iterates even for real functions.
Inverse quadratic interpolation instead interpolates the inverse function x=x(f) using three function values and evaluates at f=0. Brent’s method combines bisection, the secant method, and inverse quadratic interpolation while preserving a bracket.
Use a fast interpolation step when it is safe. If the interpolation step looks unreliable, return immediately to bisection. This is the philosophy behind robust production root solvers.
Cubic One-Step Methods
High-order one-step methods use higher derivative information to cancel additional terms in the local error expansion.
Chebyshev’s Method
Chebyshev’s method is x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} - \frac{f''(x_k)}{2f'(x_k)} \left(\frac{f(x_k)}{f'(x_k)}\right)^2.
Let f\in C^3 near a simple root \xi, with f'(\xi)\ne0. Then Chebyshev’s method converges cubically for x_0 sufficiently close to \xi: e_{k+1} = C_C e_k^3+O(e_k^4), where C_C = \frac{f'''(\xi)}{3f'(\xi)} - \frac{[f''(\xi)]^2}{2[f'(\xi)]^2}.
Set e=x-\xi, and write f(x)=a_1e+a_2e^2+a_3e^3+O(e^4), where a_1=f'(\xi), \qquad a_2=\frac{f''(\xi)}{2}, \qquad a_3=\frac{f'''(\xi)}{6}. Then f'(x)=a_1+2a_2e+3a_3e^2+O(e^3), and f''(x)=2a_2+6a_3e+O(e^2). A quotient expansion gives \frac{f(x)}{f'(x)} = e-\frac{a_2}{a_1}e^2+ \left(2\frac{a_2^2}{a_1^2}-2\frac{a_3}{a_1}\right)e^3+O(e^4). Also \frac{f''(x)}{2f'(x)} = \frac{a_2}{a_1} + \left(3\frac{a_3}{a_1}-2\frac{a_2^2}{a_1^2}\right)e + O(e^2). Substituting these expansions into Chebyshev’s update cancels the terms of order e and e^2. The remaining leading term is e_{+} = \left( 2\frac{a_3}{a_1} - 2\frac{a_2^2}{a_1^2} \right)e^3 +O(e^4). Since a_2=f''(\xi)/2 and a_3=f'''(\xi)/6, this gives C_C = \frac{f'''(\xi)}{3f'(\xi)} - \frac{[f''(\xi)]^2}{2[f'(\xi)]^2}.
□
Halley’s Method
Halley’s method is x_{k+1} = x_k - \frac{2f(x_k)f'(x_k)} {2[f'(x_k)]^2-f(x_k)f''(x_k)}.
Let f\in C^3 near a simple root \xi, with f'(\xi)\ne0. Then Halley’s method converges cubically: e_{k+1} = C_H e_k^3+O(e_k^4), where C_H = \frac{[f''(\xi)]^2}{4[f'(\xi)]^2} - \frac{f'''(\xi)}{6f'(\xi)}.
Use f(x)=a_1e+a_2e^2+a_3e^3+O(e^4), f'(x)=a_1+2a_2e+3a_3e^2+O(e^3), \qquad f''(x)=2a_2+6a_3e+O(e^2). Substitute these expansions into H(x)=x-\frac{2ff'}{2(f')^2-ff''}. Expanding the rational expression in powers of e gives cancellation of the linear and quadratic terms and e_{+} = \left( \frac{a_2^2}{a_1^2} - \frac{a_3}{a_1} \right)e^3 + O(e^4). Using a_2=f''(\xi)/2 and a_3=f'''(\xi)/6, the stated constant follows.
□
Super-Halley and Schröder-Type Cubic Methods
Let L_f(x) = \frac{f(x)f''(x)}{[f'(x)]^2}. Many cubic methods can be written in the form x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}\,\Phi(L_f(x_k)), where \Phi(0)=1 and \Phi'(0)=1/2. Examples include:
\Phi_{\mathrm{Halley}}(t)=\frac{1}{1-t/2}, \Phi_{\mathrm{Cheb}}(t)=1+\frac{t}{2}, and super-Halley-type variants using \Phi_{\mathrm{sH}}(t)=1+\frac{t}{2(1-t)}. These methods differ in error constants and stability behavior away from the root.
Quartic and Multipoint Methods
Derivative information is expensive. Multipoint methods obtain high order using several function evaluations per iteration.
Ostrowski’s Fourth-Order Method
Ostrowski’s method uses one derivative and two function evaluations: y_k=x_k-\frac{f(x_k)}{f'(x_k)}, x_{k+1} = y_k - \frac{f(y_k)}{f'(x_k)} \frac{f(x_k)}{f(x_k)-2f(y_k)}.
Let f\in C^4 near a simple root \xi, f'(\xi)\ne0. If x_0 is sufficiently close to \xi, then Ostrowski’s method converges with order four: e_{k+1}=C_Oe_k^4+O(e_k^5).
Let f(x)=a_1e+a_2e^2+a_3e^3+a_4e^4+O(e^5), \qquad a_1\ne0. The Newton predictor satisfies y_k-\xi = \frac{a_2}{a_1}e_k^2 + O(e_k^3). Therefore f(y_k)=a_1(y_k-\xi)+O((y_k-\xi)^2)=O(e_k^2). Substituting the Taylor expansions of f(x_k), f'(x_k), and f(y_k) into the Ostrowski correction shows that all terms of orders e_k^2 and e_k^3 cancel. Hence e_{k+1}=C_Oe_k^4+O(e_k^5). The constant is an explicit polynomial in a_2/a_1, a_3/a_1, and a_4/a_1.
□
King’s Fourth-Order Family
King’s family modifies the Newton correction by a weight depending on t_k=\frac{f(y_k)}{f(x_k)}. A typical representative is y_k=x_k-\frac{f(x_k)}{f'(x_k)}, x_{k+1} = y_k - \frac{f(y_k)}{f'(x_k)} \frac{1+\beta t_k}{1+(\beta-2)t_k}, where \beta is a parameter. Under suitable smoothness assumptions, this family has fourth-order convergence for simple roots.
Jarratt-Type Fourth-Order Methods
Jarratt-type methods use two derivative evaluations, commonly at x_k and an intermediate point. One representative form is y_k=x_k-\frac{2}{3}\frac{f(x_k)}{f'(x_k)}, x_{k+1} = x_k - \frac{1}{2} \left[ 3-\frac{f'(y_k)}{f'(x_k)} \right]^{-1} \left[ 3+\frac{f'(y_k)}{f'(x_k)} \right] \frac{f(x_k)}{f'(x_k)}. Its local order is four.
Traub-Type Multipoint Methods
Traub-type methods combine Newton-like predictors with correction steps using interpolation or divided differences. Their purpose is to maximize convergence order per function evaluation. Kung–Traub optimality theory predicts that a method using d function evaluations without memory can achieve order at most 2^{d-1}.
If a method has order p and requires d function or derivative evaluations per iteration, its efficiency index is E=p^{1/d}. A fourth-order method using three evaluations has index 4^{1/3}, which may be better or worse than Newton’s 2^{1/2} depending on cost and stability.
Methods with Memory
A method with memory uses information from previous iterations to improve parameters or weights. Such methods can have an order higher than the Kung–Traub bound for memoryless methods with the same number of fresh evaluations. Secant-type and inverse-interpolation methods are early examples. Modern adaptive King-type and Traub-type families often tune parameters dynamically.
Systems of Nonlinear Equations
Let F:\mathbb R^n\to\mathbb R^n. Newton’s method solves J_F(x_k)s_k=-F(x_k), and updates x_{k+1}=x_k+s_k.
Caption.
Newton’s method for systems
F, Jacobian J_F, initial vector x_0
For k=0,1,2,\ldots:
Solve J_F(x_k)s_k=-F(x_k)
x_{k+1}\gets x_k+s_k
If \|F(x_{k+1})\| and \|s_k\| are sufficiently small:
Return x_{k+1}
Let F\in C^2 in a neighborhood of x^\ast\in\mathbb R^n, with F(x^\ast)=0, \qquad J_F(x^\ast)\ \text{nonsingular}. Then Newton’s method converges quadratically for all initial guesses sufficiently close to x^\ast.
Let e_k=x_k-x^\ast. Taylor’s theorem gives F(x_k)=J_F(x^\ast)e_k+O(\|e_k\|^2), and J_F(x_k)=J_F(x^\ast)+O(\|e_k\|). Since J_F(x^\ast) is nonsingular, J_F(x_k) remains nonsingular near x^\ast. Hence e_{k+1} = e_k-J_F(x_k)^{-1}F(x_k). Using the Taylor expansions and continuity of matrix inversion gives \|e_{k+1}\|\le C\|e_k\|^2.
□
Quasi-Newton, Broyden, and Rank-One Updates
Broyden’s method builds an approximation B_k\approx J_F(x_k) satisfying the secant condition B_{k+1}s_k=y_k, \qquad s_k=x_{k+1}-x_k, \qquad y_k=F(x_{k+1})-F(x_k). The good Broyden update is B_{k+1} = B_k + \frac{(y_k-B_k s_k)s_k^T}{s_k^T s_k}.
Caption.
Broyden’s method
F, x_0, nonsingular approximation B_0
For k=0,1,2,\ldots:
Solve B_k s_k=-F(x_k)
x_{k+1}\gets x_k+s_k
y_k\gets F(x_{k+1})-F(x_k)
B_{k+1}\gets B_k+\dfrac{(y_k-B_k s_k)s_k^T}{s_k^T s_k}
The matrix B_{k+1} = B_k + \frac{(y_k-B_k s_k)s_k^T}{s_k^T s_k} satisfies B_{k+1}s_k=y_k.
Multiply by s_k: B_{k+1}s_k = B_k s_k + \frac{(y_k-B_k s_k)s_k^Ts_k}{s_k^Ts_k} = B_k s_k+y_k-B_k s_k = y_k.
□
Newton–Krylov and Inexact Newton Methods
For large systems, one avoids forming or factoring the Jacobian. Newton–Krylov methods solve J_F(x_k)s_k=-F(x_k) approximately using Krylov methods such as GMRES. An inexact Newton step satisfies \|J_F(x_k)s_k+F(x_k)\| \le \eta_k\|F(x_k)\|. For superlinear convergence, one typically requires \eta_k\to0. Jacobian-vector products may be approximated by finite differences: J_F(x)v \approx \frac{F(x+\sigma v)-F(x)}{\sigma}.
Anderson Acceleration
For a fixed-point map x=g(x), Anderson acceleration forms a new iterate using a least-squares combination of recent residuals r_k=g(x_k)-x_k. It often dramatically accelerates convergence, especially for nonlinear PDE fixed point iterations. However, unlike pure contractions, it may lose monotonicity and may need damping or safeguarding.
Interval Newton and Certified Roots
For an interval X, define N(X) = m-\frac{f(m)}{f'(X)}, \qquad m=\operatorname{mid}(X), where f'(X) is an interval enclosure of derivative values over X.
Let f\in C^1(X). If N(X)\cap X=\varnothing, then X contains no root of f. If N(X)\subset X, and 0\notin f'(X), then X contains a unique root of f.
If \xi\in X is a root, then by the mean value theorem 0=f(\xi)=f(m)+f'(\eta)(\xi-m) for some \eta between m and \xi. Hence \xi=m-\frac{f(m)}{f'(\eta)}\in N(X). Thus any root in X must lie in N(X)\cap X, proving exclusion. The inclusion case follows from the interval contraction principle and the assumption 0\notin f'(X), which prevents multiple crossings.
□
The Krawczyk Operator
For systems F:\mathbb R^n\to\mathbb R^n, the Krawczyk operator is K(x_0,X) = x_0-CF(x_0)+(I-CJ_F(X))(X-x_0), where C is an approximate inverse of J_F(x_0).
If K(x_0,X)\subset \operatorname{int}(X), then X contains a unique zero of F.
The operator is derived by applying a Newton-like fixed-point map T(x)=x-CF(x) over the interval box X. The inclusion K(x_0,X)\subset \operatorname{int}(X) implies that T maps X strictly into itself with a verified contraction structure controlled by I-CJ_F(X). A fixed-point theorem then gives existence, and the interval contraction gives uniqueness.
□
Smale’s Alpha Theory
For analytic scalar f, define \beta(f,x)=\left|\frac{f(x)}{f'(x)}\right|, \gamma(f,x) = \sup_{k\ge2} \left| \frac{f^{(k)}(x)}{k!f'(x)} \right|^{1/(k-1)}, and \alpha(f,x)=\beta(f,x)\gamma(f,x).
There exists a universal constant \alpha_0>0 such that if \alpha(f,x_0)\le\alpha_0, then Newton’s method starting at x_0 converges quadratically to a root near x_0.
The full theory extends to polynomial systems and is fundamental in certified numerical algebraic geometry.
Stopping Criteria
Common stopping tests are |x_{k+1}-x_k|\le \tau(1+|x_{k+1}|), |f(x_k)|\le\tau, and, for systems, \|s_k\|\le\tau(1+\|x_k\|), \qquad \|F(x_k)\|\le\tau. A reliable implementation checks both step size and residual, monitors derivative or Jacobian conditioning, and detects stagnation.
Algorithms Summary
| Method | Guarantee | Local speed | Main weakness |
|---|---|---|---|
| Bisection | yes | linear | slow |
| Regula falsi | yes | often superlinear | stagnation possible |
| Ridder | yes | fast linear/superlinear | bracket required |
| Fixed point | if contraction | linear | depends on g |
| Aitken/Steffensen | local | often quadratic | denominator instability |
| Newton | local | quadratic | derivative, divergence risk |
| Secant | local | order \varphi | no bracket |
| Chebyshev | local | cubic | needs f'' |
| Halley | local | cubic | rational denominator |
| Ostrowski/King | local | quartic | more evaluations |
| Brent | yes | fast in practice | complex logic |
| Interval Newton | certified | fast when narrow | interval overhead |
| Broyden | local | often superlinear | approximate Jacobian |
| Newton–Krylov | local/globalized | fast large-scale | linear solver tolerance |
Exercises
The following problems are divided into basic, intermediate, advanced, and research-level exercises. Problems marked by \star, \star\star, and \star\star\star are progressively harder. Detailed hints and solutions will be placed in the separate solutions volume.
Basic problems
Let f\in C[a,b], f(a)f(b)<0. How many bisection steps are sufficient to guarantee an absolute error below \varepsilon?
Apply three steps of bisection to f(x)=x^3-2 on [1,2].
Show that solving x=\cos x is equivalent to finding a zero of f(x)=x-\cos x.
Let g(x)=\cos x on [0,1]. Find a Lipschitz constant L<1 for g.
Derive Newton’s method from the tangent line approximation.
Apply Newton’s method to f(x)=x^2-a, a>0, and derive x_{k+1}=\frac12\left(x_k+\frac{a}{x_k}\right).
Derive the secant method by replacing f'(x_k) with a divided difference.
Let f(x)=\varepsilon x, where 0<\varepsilon\ll1. Explain why a small residual does not necessarily imply a small error.
Show that \xi=1 is a root of multiplicity 3 of f(x)=(x-1)^3(x+2).
Derive the regula falsi formula c=\frac{a f(b)-b f(a)}{f(b)-f(a)}.
Explain why a robust stopping criterion should check both |x_{k+1}-x_k| and |f(x_k)|.
Give an example where Newton’s method fails because f'(x_k)=0.
Compute the efficiency index of Newton, Halley, and a fourth-order method requiring three evaluations.
Explain why |g'(\xi)|<1 suggests local convergence of x_{k+1}=g(x_k).
Intermediate problems \star
Prove the referenced result.
Fill in all details in the proof of the referenced result.
If g is a contraction with constant L<1, prove |x_k-\xi| \le \frac{L}{1-L}|x_k-x_{k-1}|.
Prove the referenced result.
Derive Steffensen’s method by applying Aitken acceleration to x_{k+1}=g(x_k).
For f(x)=x^2-a, compute the constant \frac{f''(\xi)}{2f'(\xi)} in the Newton error formula.
Prove the referenced result.
Show that if the multiplicity m is known, then x_{k+1}=x_k-m\frac{f(x_k)}{f'(x_k)} is locally quadratically convergent.
Prove that the secant method satisfies e_{k+1}=C e_ke_{k-1}+o(e_ke_{k-1}) for a simple root.
Use the product error model to derive the golden-ratio order of convergence of the secant method.
Let \phi(x)=\frac12 f(x)^2. Show that the Newton direction is a descent direction for \phi whenever f'(x)\ne0.
Prove the exclusion part of the referenced result.
Prove the referenced result.
Derive Ridder’s method from exponential interpolation over a sign-changing bracket.
Explain why a Brent-type method must reject some interpolation steps and return to bisection.
Advanced problems \star\star
Complete the majorant argument in the referenced result.
Prove the referenced result and verify the stated error constant.
Prove the referenced result and verify the stated error constant.
Show that super-Halley-type methods of the form x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}\Phi(L_f(x_k)) are cubic when \Phi(0)=1 and \Phi'(0)=1/2.
Derive the third-order Householder method and compare it with Halley’s method.
Carry out the full Taylor expansion proving the referenced result.
Prove that King’s family has fourth-order convergence for a suitable range of the parameter \beta.
Verify fourth-order convergence of the Jarratt-type method stated in this chapter.
State the Kung–Traub conjecture and verify the optimal order 2^{d-1} for d=2,3,4.
Compare Newton, Halley, Chebyshev, Ostrowski, and King methods using their efficiency indices and derivative requirements.
Derive Muller’s method from quadratic interpolation and explain why complex iterates may arise.
Derive inverse quadratic interpolation and explain its role in Brent’s method.
For p(z)=z^3-1, derive the Newton iteration map and describe the basins of attraction of the three roots.
Compute \alpha(f,x) for f(x)=x^2-a, a>0.
Prove the referenced result.
Show that the good Broyden update solves a minimum-change Frobenius norm problem subject to the secant equation.
For \|J_F(x_k)s_k+F(x_k)\|\le\eta_k\|F(x_k)\|, explain why \eta_k\to0 is required for superlinear convergence.
Show how roots of a monic polynomial can be represented as eigenvalues of a companion matrix. Discuss conditioning.
If \xi is a known root of f, analyze the numerical risks of replacing f(x) by f(x)/(x-\xi) when \xi is approximate.
Construct a rational weight function \Phi(t) satisfying \Phi(0)=1,\qquad \Phi'(0)=1/2, and derive the resulting cubic method.
Research-level problems \star\star\star
State and prove the Newton–Kantorovich theorem in Banach spaces using a Lipschitz condition on the Fréchet derivative.
Define \alpha(F,x), \beta(F,x), and \gamma(F,x) for analytic systems. State a certified approximate-zero theorem and apply it to a two-variable polynomial system.
Develop interval Newton for F:\mathbb R^n\to\mathbb R^n and prove an inclusion theorem using interval Jacobians.
Prove the referenced result.
Derive forcing conditions for Newton–Krylov methods that guarantee superlinear convergence.
Analyze Anderson acceleration applied to a contractive fixed-point map. Explain why it can accelerate convergence but may lose monotonicity.
For p(z)=z^d-1, analyze the Newton map as a rational dynamical system and explain why basin boundaries are generally fractal.
Let H(x,t)=(1-t)G(x)+tF(x). Derive the Davidenko differential equation for solution paths and explain predictor–corrector continuation.
For a system F(x)=0 with a singular Jacobian at the root, discuss deflation techniques that restore nonsingularity. Give an algebraic example.
Let F=\nabla\phi. Compare Newton’s method for F(x)=0 with Newton’s method for minimizing \phi. Analyze line search and trust regions.
Compare interval Newton methods, Sturm sequences, and Descartes subdivision methods for isolating real polynomial roots.
Construct a method with memory whose convergence order exceeds the Kung–Traub bound for the same number of fresh evaluations. Explain why memory changes the optimality comparison.
Compare the complex basins of Newton, Chebyshev, Halley, and Ostrowski methods for p(z)=z^3-1. Discuss speed versus basin stability.
Design a verified algorithm that combines subdivision, interval Newton, and deflation to isolate all real roots of a polynomial on a finite interval.
Recall that Steffensen’s method updates the iteration via x_{k+1} = x_k - \frac{f(x_k)^2}{f(x_k + f(x_k)) - f(x_k)}. Prove that if \xi is a simple root of f(x) = 0 and f \in C^2, this method converges quadratically without requiring any evaluation of the derivative f'(x_k). Contrast its operational cost with Newton’s method.
Let g \in C^p([a,b]) with g(\xi) = \xi. Suppose that g'(\xi) = g''(\xi) = \dots = g^{(p-1)}(\xi) = 0, but g^{(p)}(\xi) \neq 0. Prove that the sequence x_{k+1} = g(x_k) converges to \xi with order p, and show that the asymptotic error constant is given by C = \frac{g^{(p)}(\xi)}{p!}. FIZMAKOEND|exercise FIZMAKOBEGIN|exercise||: Secant Method on Linear Systems Consider the multi-dimensional secant method applied to a linear system of equations $Ax = b$, where $A \in \mathbb{R}^{n \times n}$ is non-singular. Under what conditions on the choice of initial points $x_0, x_1, \dots, x_n$ will the sequential multi-dimensional secant iteration converge to the exact solution in exactly $n$ steps? FIZMAKOEND|exercise FIZMAKOBEGIN|exercise||: Sensitivity of Multiple Roots Let $\xi$ be a root of $f(x) = 0$ with multiplicity $m > 1$. Suppose $f$ is perturbed to $\tilde{f}(x) = f(x) + \epsilon g(x)$, where $g(\xi) \neq 0$ and $\epsilon > 0$ is a small parameter. Prove that the perturbed root $\tilde{\xi}$ satisfies the asymptotic expansion \[ |\tilde{\xi} - \xi| = \left( \frac{m! \, |g(\xi)|}{|f^{(m)}(\xi)|} \right)^{1/m} \epsilon^{1/m} + O(\epsilon^{2/m}). Explain how this quantifies the severe ill-conditioning of multiple roots.
Suppose an iteration produces an error sequence satisfying e_{k+1} = e_k(1 - c e_k^p) for c > 0 and p \ge 1, indicating sublinear or logarithmic convergence. Apply Aitken’s \Delta^2 process to this sequence and determine whether it structurally upgrades the convergence to a superlinear rate.
Let g: \mathbb{R} \to \mathbb{R} be globally differentiable with |g'(x)| \le L < 1 for all x \in \mathbb{R}. Prove that g possesses a unique fixed point \xi \in \mathbb{R}. Construct a counterexample showing that if the condition is weakened to |g'(x)| < 1 for all x, a fixed point might not exist.
Consider a two-step predictor-corrector method: y_k = x_k - \frac{f(x_k)}{f'(x_k)}, \quad x_{k+1} = y_k - \frac{f(y_k)}{f'(x_k)}. Prove that this method achieves third-order convergence while evaluating only one derivative per iteration. Compute its efficiency index.
In a hybrid root-finding routine, an interpolation step x_{k+1}^{\text{interp}} is accepted only if it falls within the interval [x_k, x_{k-1}]. Prove that if the base method is the secant method, this safeguard preserves the asymptotic convergence order \phi = (1+\sqrt{5})/2 near a simple root.
Let g(x) = \xi + c|x - \xi|^\alpha \sin(1/(x-\xi)) for x \neq \xi, and g(\xi) = \xi, where \alpha > 1. Analyze the local convergence behavior of the fixed-point iteration x_{k+1} = g(x_k). Is the condition g'(\xi) = 0 necessary to achieve a superlinear convergence order?
Let f \in C^2(\mathbb{R}) be a strictly convex function (f''(x) > 0 for all x) with a unique zero \xi. Prove that for any initial guess x_0 > \xi, the sequence of Newton iterates \{x_k\} decreases monotonically and converges quadratically to \xi. What happens if x_0 < \xi?
Halley’s method is typically cubic for simple roots. Apply Halley’s method to a function f(x) with a root \xi of multiplicity m > 1. Show that the iteration reduces to a first-order convergent process, and determine its exact asymptotic error constant as a function of m.
Extend the scalar super-Halley method to systems of nonlinear equations F(x) = 0, where F: \mathbb{R}^n \to \mathbb{R}^n. Using the notation J_F(x) for the Jacobian and H_F(x) for the Hessian tensor, explicitly write out the multi-dimensional super-Halley iteration step and prove its cubic convergence local properties.
Consider the Potra–Pták iteration defined by: y_k = x_k - \frac{f(x_k)}{f'(x_k)}, \quad x_{k+1} = x_k - \frac{f(x_k) + f(y_k)}{f'(x_k)}. Prove that this method is third-order convergent. Compare its computational requirements and efficiency index with the standard Chebyshev and Halley cubic methods.
Design a three-step derivative-free or single-derivative multi-point framework that achieves eighth-order convergence using exactly four function evaluations per step. Verify that this satisfies the upper bound of the Kung–Traub conjecture.
Formulate the secant method for an operator F: X \to Y acting between two Banach spaces X and Y. Since direct division is impossible, define the appropriate divided difference operator [x_k, x_{k-1}; F] and prove the local convergence theorem under an explicit Lipschitz condition on the divided difference.
Let x_{k+1} be computed via Inverse Quadratic Interpolation (IQI) using three prior points x_k, x_{k-1}, x_{k-2}. Prove that the error sequence satisfies e_{k+1} \approx C e_k e_{k-1} e_{k-2}. Show that the characteristic equation governing the convergence order \alpha is \alpha^3 - \alpha^2 - \alpha - 1 = 0, and find its unique real root.
Let f(x) be an analytic function on \mathbb{C}. Define \beta(f,x) = |f(x)/f'(x)| and \gamma(f,x) = \sup_{n \ge 2} |f^{(n)}(x)/(n! f'(x))|^{1/(n-1)}. Prove that if \alpha(f,x) = \beta(f,x)\gamma(f,x) < 3 - 2\sqrt{2}, then Newton’s method is guaranteed to converge to a unique zero within a defined neighborhood of x.
Let F: \mathbb{R}^n \to \mathbb{R}^n be continuously differentiable, and let \phi(x) = \frac{1}{2}\|F(x)\|_2^2. Consider the damped Newton update x_{k+1} = x_k + \alpha_k s_k, where J_F(x_k)s_k = -F(x_k). Prove that if \alpha_k is selected via the Armijo backtracking rule, the iteration cannot get trapped in local maxima or saddles of \phi, and will converge to a stationary point of \phi.
Prove that the good Broyden method for solving F(x) = 0 satisfies a superlinear convergence criterion \lim_{k \to \infty} \frac{\|x_{k+1} - \xi\|}{\|x_k - \xi\|} = 0, provided the initial guess x_0 and initial Jacobian approximation B_0 are sufficiently close to \xi and J_F(\xi), respectively.
Let p(x) = x^n + a_{n-1}x^{n-1} + \dots + a_0 be a polynomial. Let C(p) be its companion matrix. Show that the condition number of an eigenvalue \lambda of C(p) is directly proportional to 1/|p'(\lambda)|. Discuss why balancing the companion matrix via diagonal similarity transformations affects the conditioning of the root-finding process.
Prove that any multi-point root-finding method that utilizes exactly two evaluations of the function f (and no derivatives) per iteration cannot have an order of convergence greater than 2. Construct a specific method that explicitly achieves this maximum optimal barrier.
The Jarratt method utilizes the following structure: y_k = x_k - \frac{2}{3}\frac{f(x_k)}{f'(x_k)}, \quad x_{k+1} = x_k - \left[ 1 - \frac{3}{2}\frac{f'(y_k) - f'(x_k)}{3f'(y_k) - f'(x_k)} \right] \frac{f(x_k)}{f'(x_k)}. Perform a meticulous Taylor expansion around the simple root \xi to prove that the method achieves fourth-order convergence.
Analyze King’s family of multi-point methods. Show that by inserting a rational weight function of the form \Phi(t) = \frac{1 + \beta t}{1 + (\beta - 2)t} where t = f(y_k)/f(x_k), the error term corresponding to e_k^3 vanishes identically for any value of the parameter \beta \in \mathbb{R}.
Suppose the Jacobian operator J_F(x) satisfies a Hölder continuity condition \|J_F(x) - J_F(y)\| \le H \|x - y\|^\alpha for \alpha \in (0,1]. Generalize the scalar majorant framework of the Newton–Kantorovich theorem to establish the existence of a root and derive the modified convergence rate.
Consider a random polynomial P_n(x) = \sum_{i=0}^n c_i x^i, where the coefficients c_i are independent and identically distributed standard normal random variables. Prove that the expected number of real roots scales as \frac{2}{\pi} \ln(n) + O(1) as n \to \infty. Discuss how this alters the initialization strategy for global solvers.
When evaluating a polynomial after tracking a root \xi_1, we can form P_{n-1}(x) = \frac{P_n(x)}{x - \xi_1}. Show that if \xi_1 contains a rounding error \delta, evaluating P_{n-1}(x) near subsequent roots that are smaller in magnitude than \xi_1 is forward stable, whereas evaluating it near roots larger than \xi_1 causes catastrophic error propagation.
In infinite-dimensional spaces, Newton’s method can fail if the inverse Jacobian loses derivatives (i.e., the mapping J_F(x)^{-1} is unbounded). Outline the Nash–Moser modification, which introduces smoothing operators S_\theta into the Newton step: x_{k+1} = x_k - S_{\theta_k} J_F(x_k)^{-1} F(x_k). Prove that under appropriate assumptions, this method achieves superlinear convergence despite the loss of derivatives.
Let p(z) be a polynomial of degree d \ge 3 on the complex plane \mathbb{C}. Let N_p(z) = z - p(z)/p'(z) be its Newton rational map. Prove that the boundary of the basin of attraction of any root \xi_k is exactly equal to the Julia set of N_p. Conclude that if the Julia set is connected, all roots share the exact same boundary.
Anderson acceleration updates a fixed point iteration x_{k+1} = g(x_k) by tracking a history of m past iterates and minimizing the residual \sum \alpha_i (g(x_i) - x_i). Formalize this as a multi-term linear recurrence. Prove that if g is a linear operator with spectrum \sigma(g), Anderson acceleration restricts the effective spectrum to a subset of a low-degree Krylov subspace.
The Krawczyk operator for interval root-finding is defined as K(X) = x - Y F(x) + (I - Y J_F(X))(X - x), where x \in X and Y is an approximate inverse Jacobian matrix. Prove that if K(X) \subseteq \operatorname{int}(X), then X contains a unique exact solution to F(x) = 0, and the interval iteration X_{k+1} = K(X_k) \cap X_k converges quadratically in width.
Consider a homotopy continuation path defined by H(x,t) = 0. Suppose that at some point (x^*, t^*), the partial Jacobian J_x H(x^*, t^*) develops a nullspace of dimension 1. Classify this singularity as either a turning point or a bifurcation point. Derive an explicit numerical algorithm to compute the tangent vectors of branching paths and pass through the singularity without failure.
Construct an advanced multi-point method with memory by replacing a fixed parameter \beta with a dynamic self-correcting parameter calculated using secant-like divided differences from the preceding iteration. Prove that this self-correcting memory structure increases the convergence order from 4 to 2 + \sqrt{5} \approx 4.236 without requiring any additional function evaluations.
Let \xi \in \mathbb{R}^n be an isolated root of F(x) = 0 such that \operatorname{rank}(J_F(\xi)) = n-1. Let v be a basis vector for the nullspace of J_F(\xi). Construct an augmented system G(x, u) = \begin{pmatrix} F(x) \\ J_F(x)u \\ v^T u - 1 \end{pmatrix} = 0. Prove that (\xi, v) is a simple root of the deflated augmented system G = 0, thereby restoring the quadratic convergence rate of Newton’s method.
Using Smale’s \alpha-theory, show that the number of Newton iterations required to obtain a certified approximate zero of an analytic function f to an accuracy of \epsilon is bounded by O\left(\log \log \left(\frac{1}{\epsilon}\right)\right), provided the initial point satisfies \alpha(f, x_0) < \alpha_0. Use this to derive a global polynomial-time bound for isolating roots of polynomials.
Formulate the Full Approximation Scheme (FAS) multigrid method for solving a non-linear elliptic partial differential equation discretized as A(u) = f. Show how the fine-grid nonlinear residual is transferred to the coarse grid, and prove that FAS reduces to standard linear multigrid when the operator A is linear.
Let F: \mathbb{R}^n \to \mathbb{R}^n be continuously differentiable. The trust-region method steps are computed by minimizing a local quadratic model subject to \|s\|_2 \le \Delta_k. Prove that if the steps satisfy a Cauchy decrease condition, the sequence of gradients or residuals satisfies \lim_{k \to \infty} \inf \|J_F(x_k)^T F(x_k)\|_2 = 0, guaranteeing global convergence to a stationary point.
Prove the general theorem of Traub regarding multi-point iterations: an iterative method without memory that uses d evaluations of the function or its derivatives cannot exceed an order of convergence of 2^{d-1}. Show that this upper bound is attained if and only if the multi-point rational interpolation matches all local Hermite data exactly.
Exercise solutions
The solutions below are converted from the uploaded LaTeX solution file. Open an accordion to view the full solution.
This chapter gives detailed worked solutions for the exercises in Chapter 2. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 2.1
Problem formulation.
Let f\in C[a,b], f(a)f(b)<0. How many bisection steps are sufficient to guarantee an absolute error below \varepsilon?
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Because f(a)f(b)<0, the intermediate value theorem gives at least one root in [a,b]. Bisection replaces the interval by the half that still contains a sign change: c_k=\frac{a_k+b_k}{2}. After one step the interval length is (b-a)/2. After k steps, b_k-a_k=\frac{b_0-a_0}{2^k}. Since the midpoint is used as the approximation, |x_\ast-c_k|\le \frac{b_k-a_k}{2} = \frac{b_0-a_0}{2^{k+1}}. To guarantee |x_\ast-c_k|\le\varepsilon, it is enough to choose k\ge \left\lceil \log_2\left(\frac{b_0-a_0}{2\varepsilon}\right) \right\rceil.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.2
Problem formulation.
Apply three steps of bisection to f(x)=x^3-2 on [1,2].
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Because f(a)f(b)<0, the intermediate value theorem gives at least one root in [a,b]. Bisection replaces the interval by the half that still contains a sign change: c_k=\frac{a_k+b_k}{2}. After one step the interval length is (b-a)/2. After k steps, b_k-a_k=\frac{b_0-a_0}{2^k}. Since the midpoint is used as the approximation, |x_\ast-c_k|\le \frac{b_k-a_k}{2} = \frac{b_0-a_0}{2^{k+1}}. To guarantee |x_\ast-c_k|\le\varepsilon, it is enough to choose k\ge \left\lceil \log_2\left(\frac{b_0-a_0}{2\varepsilon}\right) \right\rceil.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.3
Problem formulation.
Show that solving x=\cos x is equivalent to finding a zero of f(x)=x-\cos x.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
A fixed point satisfies x_\ast=g(x_\ast). The iteration is x_{k+1}=g(x_k). If g maps an interval into itself and |g'(x)|\le L<1 on that interval, then |x_{k+1}-x_\ast| = |g(x_k)-g(x_\ast)| \le L|x_k-x_\ast|. Therefore |x_k-x_\ast|\le L^k|x_0-x_\ast|, and the iteration converges linearly.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.4
Problem formulation.
Let g(x)=\cos x on [0,1]. Find a Lipschitz constant L<1 for g.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.5
Problem formulation.
Derive Newton’s method from the tangent line approximation.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.6
Problem formulation.
Apply Newton’s method to f(x)=x^2-a, a>0, and derive x_{k+1}=\frac12\left(x_k+\frac{a}{x_k}\right).
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.7
Problem formulation.
Derive the secant method by replacing f'(x_k) with a divided difference.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The secant method replaces the derivative in Newton’s method by a first divided difference: f'(x_k)\approx \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}. Substitution into Newton’s formula gives x_{k+1} = x_k - f(x_k) \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}. For a simple root and smooth f, the secant method has order p=\frac{1+\sqrt5}{2}, which is superlinear but lower than Newton’s quadratic order.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.8
Problem formulation.
Let f(x)=\varepsilon x, where 0<\varepsilon\ll1. Explain why a small residual does not necessarily imply a small error.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.9
Problem formulation.
Show that \xi=1 is a root of multiplicity 3 of f(x)=(x-1)^3(x+2).
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.10
Problem formulation.
Derive the regula falsi formula c=\frac{a f(b)-b f(a)}{f(b)-f(a)}.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.11
Problem formulation.
Explain why a robust stopping criterion should check both |x_{k+1}-x_k| and |f(x_k)|.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.12
Problem formulation.
Give an example where Newton’s method fails because f'(x_k)=0.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.13
Problem formulation.
Compute the efficiency index of Newton, Halley, and a fourth-order method requiring three evaluations.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.14
Problem formulation.
Explain why |g'(\xi)|<1 suggests local convergence of x_{k+1}=g(x_k).
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
A fixed point satisfies x_\ast=g(x_\ast). The iteration is x_{k+1}=g(x_k). If g maps an interval into itself and |g'(x)|\le L<1 on that interval, then |x_{k+1}-x_\ast| = |g(x_k)-g(x_\ast)| \le L|x_k-x_\ast|. Therefore |x_k-x_\ast|\le L^k|x_0-x_\ast|, and the iteration converges linearly.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.15
Problem formulation.
Prove the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Because f(a)f(b)<0, the intermediate value theorem gives at least one root in [a,b]. Bisection replaces the interval by the half that still contains a sign change: c_k=\frac{a_k+b_k}{2}. After one step the interval length is (b-a)/2. After k steps, b_k-a_k=\frac{b_0-a_0}{2^k}. Since the midpoint is used as the approximation, |x_\ast-c_k|\le \frac{b_k-a_k}{2} = \frac{b_0-a_0}{2^{k+1}}. To guarantee |x_\ast-c_k|\le\varepsilon, it is enough to choose k\ge \left\lceil \log_2\left(\frac{b_0-a_0}{2\varepsilon}\right) \right\rceil.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.16
Problem formulation.
Fill in all details in the proof of the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
A fixed point satisfies x_\ast=g(x_\ast). The iteration is x_{k+1}=g(x_k). If g maps an interval into itself and |g'(x)|\le L<1 on that interval, then |x_{k+1}-x_\ast| = |g(x_k)-g(x_\ast)| \le L|x_k-x_\ast|. Therefore |x_k-x_\ast|\le L^k|x_0-x_\ast|, and the iteration converges linearly.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.17
Problem formulation.
If g is a contraction with constant L<1, prove |x_k-\xi| \le \frac{L}{1-L}|x_k-x_{k-1}|.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
A fixed point satisfies x_\ast=g(x_\ast). The iteration is x_{k+1}=g(x_k). If g maps an interval into itself and |g'(x)|\le L<1 on that interval, then |x_{k+1}-x_\ast| = |g(x_k)-g(x_\ast)| \le L|x_k-x_\ast|. Therefore |x_k-x_\ast|\le L^k|x_0-x_\ast|, and the iteration converges linearly.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.18
Problem formulation.
Prove the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.19
Problem formulation.
Derive Steffensen’s method by applying Aitken acceleration to x_{k+1}=g(x_k).
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.20
Problem formulation.
For f(x)=x^2-a, compute the constant \frac{f''(\xi)}{2f'(\xi)} in the Newton error formula.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.21
Problem formulation.
Prove the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.22
Problem formulation.
Show that if the multiplicity m is known, then x_{k+1}=x_k-m\frac{f(x_k)}{f'(x_k)} is locally quadratically convergent.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.23
Problem formulation.
Prove that the secant method satisfies e_{k+1}=C e_ke_{k-1}+o(e_ke_{k-1}) for a simple root.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The secant method replaces the derivative in Newton’s method by a first divided difference: f'(x_k)\approx \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}. Substitution into Newton’s formula gives x_{k+1} = x_k - f(x_k) \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}. For a simple root and smooth f, the secant method has order p=\frac{1+\sqrt5}{2}, which is superlinear but lower than Newton’s quadratic order.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.24
Problem formulation.
Use the product error model to derive the golden-ratio order of convergence of the secant method.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The secant method replaces the derivative in Newton’s method by a first divided difference: f'(x_k)\approx \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}. Substitution into Newton’s formula gives x_{k+1} = x_k - f(x_k) \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}. For a simple root and smooth f, the secant method has order p=\frac{1+\sqrt5}{2}, which is superlinear but lower than Newton’s quadratic order.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.25
Problem formulation.
Let \phi(x)=\frac12 f(x)^2. Show that the Newton direction is a descent direction for \phi whenever f'(x)\ne0.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.26
Problem formulation.
Prove the exclusion part of the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.27
Problem formulation.
Prove the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 2.28
Problem formulation.
Derive Ridder’s method from exponential interpolation over a sign-changing bracket.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.29
Problem formulation.
Explain why a Brent-type method must reject some interpolation steps and return to bisection.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Because f(a)f(b)<0, the intermediate value theorem gives at least one root in [a,b]. Bisection replaces the interval by the half that still contains a sign change: c_k=\frac{a_k+b_k}{2}. After one step the interval length is (b-a)/2. After k steps, b_k-a_k=\frac{b_0-a_0}{2^k}. Since the midpoint is used as the approximation, |x_\ast-c_k|\le \frac{b_k-a_k}{2} = \frac{b_0-a_0}{2^{k+1}}. To guarantee |x_\ast-c_k|\le\varepsilon, it is enough to choose k\ge \left\lceil \log_2\left(\frac{b_0-a_0}{2\varepsilon}\right) \right\rceil.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.30
Problem formulation.
Complete the majorant argument in the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.31
Problem formulation.
Prove the referenced result and verify the stated error constant.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.32
Problem formulation.
Prove the referenced result and verify the stated error constant.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.33
Problem formulation.
Show that super-Halley-type methods of the form x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}\Phi(L_f(x_k)) are cubic when \Phi(0)=1 and \Phi'(0)=1/2.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.34
Problem formulation.
Derive the third-order Householder method and compare it with Halley’s method.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.35
Problem formulation.
Carry out the full Taylor expansion proving the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.36
Problem formulation.
Prove that King’s family has fourth-order convergence for a suitable range of the parameter \beta.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.37
Problem formulation.
Verify fourth-order convergence of the Jarratt-type method stated in this chapter.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.38
Problem formulation.
State the Kung–Traub conjecture and verify the optimal order 2^{d-1} for d=2,3,4.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.39
Problem formulation.
Compare Newton, Halley, Chebyshev, Ostrowski, and King methods using their efficiency indices and derivative requirements.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.40
Problem formulation.
Derive Muller’s method from quadratic interpolation and explain why complex iterates may arise.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.41
Problem formulation.
Derive inverse quadratic interpolation and explain its role in Brent’s method.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.42
Problem formulation.
For p(z)=z^3-1, derive the Newton iteration map and describe the basins of attraction of the three roots.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.43
Problem formulation.
Compute \alpha(f,x) for f(x)=x^2-a, a>0.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.44
Problem formulation.
Prove the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The secant method replaces the derivative in Newton’s method by a first divided difference: f'(x_k)\approx \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}. Substitution into Newton’s formula gives x_{k+1} = x_k - f(x_k) \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}. For a simple root and smooth f, the secant method has order p=\frac{1+\sqrt5}{2}, which is superlinear but lower than Newton’s quadratic order.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 2.45
Problem formulation.
Show that the good Broyden update solves a minimum-change Frobenius norm problem subject to the secant equation.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The secant method replaces the derivative in Newton’s method by a first divided difference: f'(x_k)\approx \frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}. Substitution into Newton’s formula gives x_{k+1} = x_k - f(x_k) \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}. For a simple root and smooth f, the secant method has order p=\frac{1+\sqrt5}{2}, which is superlinear but lower than Newton’s quadratic order.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.46
Problem formulation.
For \|J_F(x_k)s_k+F(x_k)\|\le\eta_k\|F(x_k)\|, explain why \eta_k\to0 is required for superlinear convergence.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.47
Problem formulation.
Show how roots of a monic polynomial can be represented as eigenvalues of a companion matrix. Discuss conditioning.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 2.48
Problem formulation.
If \xi is a known root of f, analyze the numerical risks of replacing f(x) by f(x)/(x-\xi) when \xi is approximate.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.49
Problem formulation.
Construct a rational weight function \Phi(t) satisfying \Phi(0)=1,\qquad \Phi'(0)=1/2, and derive the resulting cubic method.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.50
Problem formulation.
State and prove the Newton–Kantorovich theorem in Banach spaces using a Lipschitz condition on the Fréchet derivative.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 2.51
Problem formulation.
Define \alpha(F,x), \beta(F,x), and \gamma(F,x) for analytic systems. State a certified approximate-zero theorem and apply it to a two-variable polynomial system.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.52
Problem formulation.
Develop interval Newton for F:\mathbb R^n\to\mathbb R^n and prove an inclusion theorem using interval Jacobians.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.53
Problem formulation.
Prove the referenced result.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.54
Problem formulation.
Derive forcing conditions for Newton–Krylov methods that guarantee superlinear convergence.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.55
Problem formulation.
Analyze Anderson acceleration applied to a contractive fixed-point map. Explain why it can accelerate convergence but may lose monotonicity.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
A fixed point satisfies x_\ast=g(x_\ast). The iteration is x_{k+1}=g(x_k). If g maps an interval into itself and |g'(x)|\le L<1 on that interval, then |x_{k+1}-x_\ast| = |g(x_k)-g(x_\ast)| \le L|x_k-x_\ast|. Therefore |x_k-x_\ast|\le L^k|x_0-x_\ast|, and the iteration converges linearly.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.56
Problem formulation.
For p(z)=z^d-1, analyze the Newton map as a rational dynamical system and explain why basin boundaries are generally fractal.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.57
Problem formulation.
Let H(x,t)=(1-t)G(x)+tF(x). Derive the Davidenko differential equation for solution paths and explain predictor–corrector continuation.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.58
Problem formulation.
For a system F(x)=0 with a singular Jacobian at the root, discuss deflation techniques that restore nonsingularity. Give an algebraic example.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 2.59
Problem formulation.
Let F=\nabla\phi. Compare Newton’s method for F(x)=0 with Newton’s method for minimizing \phi. Analyze line search and trust regions.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.60
Problem formulation.
Compare interval Newton methods, Sturm sequences, and Descartes subdivision methods for isolating real polynomial roots.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 2.61
Problem formulation.
Construct a method with memory whose convergence order exceeds the Kung–Traub bound for the same number of fresh evaluations. Explain why memory changes the optimality comparison.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
The solution follows from local linearization. For a scalar equation use f(x_k+s)\approx f(x_k)+f'(x_k)s, and for a nonlinear system use F(x_k+s)\approx F(x_k)+J_F(x_k)s. The correction is chosen so that the linear model vanishes. For systems this gives J_F(x_k)s_k=-F(x_k), \qquad x_{k+1}=x_k+s_k. Convergence, order, and stopping criteria are then obtained from Taylor expansion, residual estimates, and the conditioning relation |x_k-x_\ast|\approx \frac{|f(x_k)|}{|f'(x_\ast)|} near a simple root.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 2.62
Problem formulation.
Compare the complex basins of Newton, Chebyshev, Halley, and Ostrowski methods for p(z)=z^3-1. Discuss speed versus basin stability.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Always test the result on the scalar model equation or Fourier mode and verify the amplification factor satisfies the stated stability bound.
Exercise 2.63
Problem formulation.
Design a verified algorithm that combines subdivision, interval Newton, and deflation to isolate all real roots of a polynomial on a finite interval.
Method.
Use Taylor expansion, fixed-point theory, bracketing, Newton/secant formulas, or nonlinear-system linearization as appropriate.
Detailed solution and justification.
Taylor expansion around x_k gives f(x_k+s)=f(x_k)+f'(x_k)s+\frac12f''(\xi_k)s^2. Newton’s method sets the linear part equal to zero: f(x_k)+f'(x_k)s_k=0. Thus s_k=-\frac{f(x_k)}{f'(x_k)}, and x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}. If x_\ast is a simple root and e_k=x_k-x_\ast, then e_{k+1} = \frac{f''(x_\ast)}{2f'(x_\ast)}e_k^2+O(e_k^3), so the convergence is quadratic.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.