Chapter 1
Floating-Point Arithmetic and Error Analysis
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:
distinguish exact real arithmetic from floating-point arithmetic;
derive the standard model \fl(x)=x(1+\delta), |\delta|\le u;
use the \gamma_n-notation to control accumulated rounding errors;
analyze cancellation and loss of significant digits;
distinguish conditioning from stability;
interpret residuals as backward-error objects;
recognize stable and unstable algebraic reformulations;
solve basic and advanced error-analysis exercises.
The Numerical Representation Problem
Numerical analysis begins with a structural obstruction: the field of real numbers \mathbb R is infinite and uncountable, whereas every digital computer manipulates only finitely many representable numbers. Thus a real number x\in\mathbb R is usually not stored as x itself, but as a nearby machine number \fl(x). The discrepancy between x and \fl(x) is not a programming accident. It is an unavoidable mathematical consequence of finite storage.
A numerical result is meaningful only when we understand both the mathematical sensitivity of the problem and the stability of the algorithm used to solve it. \text{forward error} \approx \text{conditioning} \times \text{backward error}.
Let x be an exact quantity and let \widetilde{x} be an approximation. The absolute error is E_{\mathrm{abs}}(x,\widetilde{x}) = |x-\widetilde{x}|. If x\ne0, the relative error is E_{\mathrm{rel}}(x,\widetilde{x}) = \frac{|x-\widetilde{x}|}{|x|}.
Absolute error measures distance in the original physical scale. Relative error measures error compared with the magnitude of the exact quantity. The second notion is usually more informative when quantities vary over several orders of magnitude.
Let x_1=10^6, \widetilde{x}_1=10^6+1, and let x_2=10^{-6}, \widetilde{x}_2=2\cdot10^{-6}. Then \frac{|x_1-\widetilde{x}_1|}{|x_1|}=10^{-6}, \qquad \frac{|x_2-\widetilde{x}_2|}{|x_2|}=1. The first approximation is relatively accurate; the second has 100\% relative error.
Floating-Point Systems
Let \beta\ge2 be an integer base, let t\ge1 be the number of significant digits, and let L<U be integer exponent bounds. A normalized floating-point system is the set \mathcal F(\beta,t,L,U) = \left\{ \pm \left( d_0+d_1\beta^{-1}+\cdots+d_{t-1}\beta^{-(t-1)} \right)\beta^e \right\}, where d_0\in\{1,\ldots,\beta-1\}, \qquad d_j\in\{0,\ldots,\beta-1\}, \qquad L\le e\le U. The number m=d_0+d_1\beta^{-1}+\cdots+d_{t-1}\beta^{-(t-1)} is the mantissa, and e is the exponent.
A normalized floating-point number therefore has the form x=\pm m\beta^e, \qquad 1\le m<\beta. The exponent controls the scale, whereas the mantissa controls the significant digits.
In a normalized base-\beta system with t significant digits, the spacing between 1 and the next larger normalized floating-point number is \varepsilon_{\mathrm{mach}} = \beta^{1-t}. For rounding to nearest, the unit roundoff is u=\frac12\beta^{1-t}. For chopping, a standard relative-error bound is u_{\mathrm{chop}}=\beta^{1-t}.
Rounding as a Projection onto a Finite Set
Let \mathcal F be a floating-point system. The operation \fl:\mathbb R\to\mathcal F maps a real number to a representable number. For rounding to nearest, \fl(x) is a nearest floating-point number to x. Ties are resolved by a prescribed rule, for example round-to-even.
Let x be a real number lying between two consecutive normalized floating-point numbers a<b. If \fl(x) is obtained by rounding to nearest, then |x-\fl(x)|\le \frac{b-a}{2}.
Since a and b are the two nearest representable endpoints surrounding x, rounding to nearest chooses either a or b. The largest possible distance to the nearest endpoint occurs at the midpoint (a+b)/2, and that distance is (b-a)/2. Hence |x-\fl(x)|\le \frac{b-a}{2}.
□
Let x lie in the normalized range of a base-\beta, t-digit floating-point system. If \fl(x) is obtained by rounding to nearest and no overflow or underflow occurs, then there exists \delta\in\mathbb R such that \fl(x)=x(1+\delta), \qquad |\delta|\le u, where u=\frac12\beta^{1-t}.
It is enough to consider x>0, since the system is symmetric with respect to sign. Suppose \beta^e\le x<\beta^{e+1}. In this binade, adjacent normalized floating-point numbers have spacing \Delta=\beta^{e-(t-1)}. By the local spacing bound, |x-\fl(x)| \le \frac{\Delta}{2} = \frac12\beta^{e-(t-1)}. Since x\ge \beta^e, we obtain \frac{|x-\fl(x)|}{|x|} \le \frac{\frac12\beta^{e-(t-1)}}{\beta^e} = \frac12\beta^{1-t} = u. Define \delta=\frac{\fl(x)-x}{x}. Then \fl(x)=x(1+\delta) and |\delta|\le u.
□
The statement excludes overflow and underflow. Near underflow, the normalized-spacing model changes. Near overflow, the rounded value may not be representable at all.
The Standard Model for Floating-Point Arithmetic
The previous theorem describes the representation of a single real number. Numerical algorithms also perform arithmetic operations. Let \circ\in\{+,-,\times,/\}. The standard model assumes that a floating-point operation is the exact real operation followed by rounding: \fl(x\circ y) = (x\circ y)(1+\delta), \qquad |\delta|\le u, provided the exact result is in the normalized range and no exceptional event occurs.
For an arithmetic operation \circ, the floating-point operation is modeled by x\mathbin{\widehat{\circ}}y = \fl(x\circ y) = (x\circ y)(1+\delta), \qquad |\delta|\le u.
This model is the foundation for most backward error analysis.
Accumulation of Rounding Errors
It is convenient to introduce the notation \gamma_n=\frac{nu}{1-nu}, \qquad nu<1. This quantity appears naturally when bounding products of many terms 1+\delta_j.
Let |\delta_j|\le u for j=1,\ldots,n, and assume nu<1. Then \prod_{j=1}^n(1+\delta_j) = 1+\theta_n, \qquad |\theta_n|\le \gamma_n.
For the upper bound, \prod_{j=1}^n(1+\delta_j)\le (1+u)^n. Using the elementary estimate (1+u)^n\le(1-nu)^{-1} for nu<1, one obtains (1+u)^n \le \frac{1}{1-nu} = 1+\frac{nu}{1-nu} = 1+\gamma_n. Similarly, \prod_{j=1}^n(1+\delta_j) \ge (1-u)^n \ge 1-\frac{nu}{1-nu} = 1-\gamma_n. Therefore the product has the form 1+\theta_n, with |\theta_n|\le \gamma_n.
□
Let s=x_1+x_2+\cdots+x_n and let \widehat{s} be computed by the recursive floating-point summation \widehat{s}_1=x_1, \qquad \widehat{s}_k=\fl(\widehat{s}_{k-1}+x_k), \qquad k=2,\ldots,n. If no overflow or underflow occurs and (n-1)u<1, then \widehat{s} = \sum_{j=1}^n x_j(1+\theta_j), \qquad |\theta_j|\le\gamma_{n-1}. Consequently, |\widehat{s}-s| \le \gamma_{n-1}\sum_{j=1}^n |x_j|.
At each addition there is a local perturbation: \widehat{s}_k = (\widehat{s}_{k-1}+x_k)(1+\delta_k), \qquad |\delta_k|\le u. Expanding recursively gives each original datum multiplied by a product of at most n-1 rounding factors. By the referenced result, every such product is 1+\theta_j, with |\theta_j|\le\gamma_{n-1}. Thus \widehat{s} = \sum_{j=1}^n x_j(1+\theta_j). Subtracting s and taking absolute values gives |\widehat{s}-s| = \left| \sum_{j=1}^n x_j\theta_j \right| \le \gamma_{n-1}\sum_{j=1}^n |x_j|.
□
Cancellation and Loss of Significance
Cancellation occurs when two nearly equal floating-point numbers are subtracted. Although subtraction itself may be exact under certain circumstances, the result can have few significant digits if the inputs already contain errors.
Let \widetilde{x}=x(1+\delta_x), \qquad \widetilde{y}=y(1+\delta_y), with |\delta_x|\le\varepsilon, \qquad |\delta_y|\le\varepsilon. Assume x\ne y. Then the relative error in the difference satisfies \frac{|(\widetilde{x}-\widetilde{y})-(x-y)|}{|x-y|} \le \varepsilon \frac{|x|+|y|}{|x-y|}.
We compute (\widetilde{x}-\widetilde{y})-(x-y) = x\delta_x-y\delta_y. Therefore |(\widetilde{x}-\widetilde{y})-(x-y)| \le |x|\,|\delta_x|+|y|\,|\delta_y| \le \varepsilon(|x|+|y|). Dividing by |x-y| gives the result.
□
The amplification factor \frac{|x|+|y|}{|x-y|} is large when x and y are close.
For large x, the expression \sqrt{x+1}-\sqrt{x} subtracts two nearly equal numbers. Multiplying by the conjugate gives \sqrt{x+1}-\sqrt{x} = \frac{1}{\sqrt{x+1}+\sqrt{x}}. The second expression avoids subtracting nearly equal quantities.
For small x, the expression 1-\cos x is susceptible to cancellation. A stable equivalent form is 1-\cos x = 2\sin^2\left(\frac{x}{2}\right).
Sterbenz Lemma
Let x and y be positive normalized floating-point numbers in a radix-\beta floating-point system with exact subtraction after alignment. If \frac12\le \frac{x}{y}\le2, then x-y is exactly representable as a floating-point number.
Assume without loss of generality that x\ge y>0. The hypothesis gives y\le x\le2y. Thus 0\le x-y\le y. Since x and y lie within at most one binade of each other, their significands can be aligned without losing significant digits beyond the required precision for the exact difference. The subtraction of the aligned integer significands is exact. After normalization, the result is representable. Hence \fl(x-y)=x-y.
□
Sterbenz lemma says that subtraction of two floating-point inputs may be exact. It does not say that the original real data were accurate. If x and y already contain errors, the referenced result shows that those errors may be amplified.
Conditioning of Mathematical Problems
Let a problem be represented by a mapping F:X\to Y. The condition number measures the sensitivity of F(x) to perturbations of x.
Suppose F is Fréchet differentiable at x. The absolute condition number is \kappa_{\mathrm{abs}}(F,x) = \|DF(x)\|, where DF(x) is the Fréchet derivative.
If x\ne0 and F(x)\ne0, the relative condition number is \kappa_{\mathrm{rel}}(F,x) = \frac{\|DF(x)\|\,\|x\|}{\|F(x)\|}.
For a scalar f:\mathbb R\to\mathbb R, this becomes \kappa_f(x) = \left| \frac{x f'(x)}{f(x)} \right|.
Let F:X\to Y be Fréchet differentiable at x. Then, for small h, F(x+h)-F(x)=DF(x)h+o(\|h\|). Consequently, \frac{\|F(x+h)-F(x)\|}{\|F(x)\|} \le \kappa_{\mathrm{rel}}(F,x) \frac{\|h\|}{\|x\|} + o\left(\frac{\|h\|}{\|x\|}\right).
By Fréchet differentiability, F(x+h)-F(x)=DF(x)h+r(h), \qquad \frac{\|r(h)\|}{\|h\|}\to0. Taking norms, \|F(x+h)-F(x)\| \le \|DF(x)\|\,\|h\|+\|r(h)\|. Dividing by \|F(x)\| and rewriting the leading term as \frac{\|DF(x)\|\,\|h\|}{\|F(x)\|} = \frac{\|DF(x)\|\,\|x\|}{\|F(x)\|} \frac{\|h\|}{\|x\|} gives the result.
□
Conditioning of Linear Systems
For a nonsingular matrix A, the solution of Ax=b is x=A^{-1}b. Perturbing b to b+\Delta b changes the solution to x+\Delta x, where A\Delta x=\Delta b, \qquad \Delta x=A^{-1}\Delta b.
Let A be nonsingular. If Ax=b and A(x+\Delta x)=b+\Delta b, then \frac{\|\Delta x\|}{\|x\|} \le \kappa(A) \frac{\|\Delta b\|}{\|b\|}, where \kappa(A)=\|A\|\,\|A^{-1}\|.
Since \Delta x=A^{-1}\Delta b, \|\Delta x\|\le \|A^{-1}\|\,\|\Delta b\|. Also b=Ax, so \|b\|\le \|A\|\,\|x\|. Thus \frac{1}{\|x\|} \le \frac{\|A\|}{\|b\|}. Combining the previous two estimates gives \frac{\|\Delta x\|}{\|x\|} \le \|A^{-1}\|\,\|\Delta b\|\frac{\|A\|}{\|b\|} = \kappa(A)\frac{\|\Delta b\|}{\|b\|}.
□
Forward Error, Backward Error, and Stability
Let x be the exact solution of a problem and let \widetilde{x} be a computed solution. The forward error is \|\widetilde{x}-x\|.
A computed solution \widetilde{x} has small backward error if it is the exact solution of a nearby problem.
For a linear system, if \widetilde{x} is computed, its residual is r=b-A\widetilde{x}. Then A\widetilde{x}=b-r. Thus \widetilde{x} is the exact solution of the perturbed problem A\widetilde{x}=\widetilde{b}, \qquad \widetilde{b}=b-r.
An algorithm is backward stable if the computed solution is the exact solution of a nearby problem, with the perturbation size comparable to unavoidable rounding error.
Conditioning belongs to the problem. Stability belongs to the algorithm. A stable algorithm applied to an ill-conditioned problem may still produce a large forward error. \text{forward error} \lesssim \text{condition number}\times\text{backward error}.
A Model Result: Backward Error for a Dot Product
Let s=x^Ty=\sum_{i=1}^n x_i y_i. A standard floating-point dot product computes products and sums sequentially.
Assume no overflow or underflow and nu<1. The computed dot product satisfies \fl(x^Ty) = \sum_{i=1}^n x_i y_i(1+\theta_i), \qquad |\theta_i|\le \gamma_n. Equivalently, \fl(x^Ty)=(x+\Delta x)^Ty with componentwise perturbations satisfying |\Delta x_i|\le \gamma_n |x_i|.
Each product and addition introduces a factor 1+\delta_j, with |\delta_j|\le u. Expanding the recursive computation gives each term x_i y_i multiplied by a product of at most n such factors. By the referenced result, that product is 1+\theta_i, where |\theta_i|\le\gamma_n. Define \Delta x_i=\theta_i x_i. Then \sum_{i=1}^n x_i y_i(1+\theta_i) = \sum_{i=1}^n (x_i+\Delta x_i)y_i = (x+\Delta x)^Ty, and |\Delta x_i|\le\gamma_n|x_i|.
□
Stable and Unstable Algebraic Forms
Two algebraically identical formulas may have radically different numerical behavior.
The roots of ax^2+bx+c=0 are formally x_{\pm} = \frac{-b\pm\sqrt{b^2-4ac}}{2a}. If b^2\gg4ac, one of the signs may involve severe cancellation. A stable strategy computes one root using the noncancelling sign and obtains the other from x_+x_-=\frac{c}{a}.
For small x, evaluating \log(1+x) directly may lose accuracy if 1+x rounds to a number too close to 1. Specialized functions such as \operatorname{log1p}(x) are designed to compute this quantity accurately.
Algorithms
Caption.
Kahan compensated summation
x_1,\ldots,x_n
s\gets 0
c\gets 0
For k=1,\ldots,n:
y\gets x_k-c
t\gets s+y
c\gets (t-s)-y
s\gets t
Return s
Caption.
Safe hypotenuse computation
x,y\in\mathbb R
v\gets \max(|x|,|y|)
u\gets \min(|x|,|y|)
If v=0:
Return 0
Else:
Return v\sqrt{1+(u/v)^2}
Chapter Summary
Floating-point arithmetic replaces \mathbb R by a finite set \mathcal F.
Correct rounding gives \fl(x)=x(1+\delta),\qquad |\delta|\le u.
Products of rounding factors are controlled by \gamma_n=\frac{nu}{1-nu}.
Cancellation amplifies previous relative errors.
Conditioning measures the sensitivity of the mathematical problem.
Stability measures the behavior of the numerical algorithm.
Backward stability means the computed solution solves a nearby problem exactly.
Exercises
The following problem set is intentionally large. It contains computational, conceptual, proof-oriented, and research-level problems. The problems marked by \star, \star\star, and \star\star\star are progressively more difficult. All exercises are labeled so that the detailed solutions volume can later refer to them unambiguously.
Basic problems
Let x=\pi and \widetilde{x}=3.14. Compute the absolute and relative errors.
In a decimal floating-point system with \beta=10 and t=5, compute \varepsilon_{\mathrm{mach}} and the unit roundoff for rounding to nearest.
In a binary floating-point system with t=24 significant binary digits, compute \varepsilon_{\mathrm{mach}} and the unit roundoff for rounding to nearest.
Prove that if \fl(x)=x(1+\delta) and |\delta|\le u, then |\fl(x)-x|\le u|x|.
Show that 1-\cos x=2\sin^2\left(\frac{x}{2}\right). Explain why the right-hand side is numerically preferable for small x.
Let f(x)=x^p, with p\in\mathbb R. Compute the relative condition number \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|.
Let f(x)=\log x. Compute \kappa_f(x). Explain why the problem is ill-conditioned near x=1.
Let f(x)=e^x. Compute its relative condition number. Explain why the value grows with |x| even though e^x is smooth everywhere.
Let \gamma_n=\frac{nu}{1-nu}. Show that \gamma_n=nu+O(n^2u^2) when nu\ll1.
In a normalized system \mathcal F(\beta,t,L,U), show that adjacent floating-point numbers in the binade [\beta^e,\beta^{e+1}) are separated by \Delta=\beta^{e-(t-1)}.
Explain why chopping gives a relative error bound of order \beta^{1-t}, whereas rounding to nearest gives a bound of order \frac12\beta^{1-t}.
Let Ax=b be nonsingular and let \widetilde{x} be a computed approximation. Prove that x-\widetilde{x}=A^{-1}(b-A\widetilde{x}).
Construct an example where \sum_{j=1}^n |x_j| \gg \left|\sum_{j=1}^n x_j\right|. Explain why summation is then sensitive to rounding errors.
Suppose an algorithm is backward stable for a problem with condition number \kappa. Explain why the expected forward error is proportional to \kappa u.
For the quadratic equation ax^2+bx+c=0, derive a cancellation-free procedure for computing both roots when b>0 and b^2\gg4ac.
Let x=10^{-8}. Compare, at least theoretically, the expressions 1-\cos x \qquad\text{and}\qquad 2\sin^2(x/2). Which one should be used in floating-point arithmetic, and why?
Give precise definitions of forward error and backward error for the scalar problem f(x)=0. Explain the difference between the two notions.
For a computed approximation \widetilde{x} to Ax=b, show that \widetilde{x} is the exact solution of a perturbed right-hand-side problem. Give the perturbation explicitly and relate it to the residual.
Intermediate problems \star
Prove the referenced result using induction instead of the product estimate.
Let s=\sum_{j=1}^n x_j. Use the referenced result to derive a relative error bound for \widehat{s}, assuming s\ne0. Explain why the bound becomes large when |s|\ll\sum_{j=1}^n |x_j|.
In exact real arithmetic, addition is associative. Construct a concrete example in a floating-point system showing that \fl(\fl(a+b)+c) \ne \fl(a+\fl(b+c)), even when no underflow or overflow occurs.
Let x and y be floating-point numbers in a normalized radix-\beta system \mathcal F(\beta,t,L,U). Suppose that \frac{1}{\beta}\le\frac{x}{y}\le \beta. Prove or disprove that x-y is exactly representable in \mathcal F. If the statement is false, identify the classical interval for x/y that guarantees exact subtraction under Sterbenz-type hypotheses.
Let n=2^m, and suppose that s=\sum_{j=1}^n x_j is computed by a balanced binary summation tree rather than by recursive left-to-right summation. Assume the standard floating-point model and no overflow or underflow.
Prove that the computed sum satisfies \widehat{s} = \sum_{j=1}^n x_j(1+\theta_j), \qquad |\theta_j|\le\gamma_m, \qquad m=\log_2 n.
Deduce that |\widehat{s}-s| \le \gamma_{\log_2 n}\sum_{j=1}^n |x_j|.
Compare this estimate with the recursive summation bound.
When a floating-point system includes subnormal numbers, the minimum positive representable number shifts from x_{\min}=\beta^L to x_{\min}^{\mathrm{sub}}=\beta^{L-(t-1)}.
Show that subnormal numbers preserve a uniform absolute-spacing model below the normalized threshold.
Determine the corresponding absolute representation-error bound under rounding to nearest.
Explain why a flush-to-zero policy can destroy small nonzero information.
Suppose a floating-point system does not include subnormal numbers and instead uses a flush-to-zero policy when underflow occurs. Construct two positive floating-point numbers x and y satisfying \frac12\le\frac{x}{y}\le2 such that the exact difference x-y is nonzero but \fl(x-y)=0. Explain why this contradicts the practical conclusion one would expect from Sterbenz lemma.
Consider evaluating e^{-x}=\sum_{k=0}^{\infty}\frac{(-1)^k x^k}{k!}, \qquad x>0, for large x.
Estimate where the terms \frac{x^k}{k!} reach their maximum magnitude.
Explain why enormous alternating terms may cancel to produce a tiny final value.
Give a stable alternative for computing e^{-x}.
Let x and y be positive real numbers. We wish to evaluate f(x,y)=\log x-\log y.
Derive the relative condition number of f with respect to perturbations in (x,y).
Explain why direct evaluation becomes dangerous when x\approx y.
Provide a stable alternative based on \log x-\log y=\log\left(1+\frac{x-y}{y}\right) and the function \operatorname{log1p}.
For small x, explain why direct evaluation of \log(1+x) may lose accuracy. Give a first-order error explanation and state why \operatorname{log1p}(x) is numerically preferable.
Let x_1,\ldots,x_n\in\mathbb R. The variance may be written as \sigma^2 = \frac1n\sum_{j=1}^n x_j^2 - \left(\frac1n\sum_{j=1}^n x_j\right)^2.
Prove the formula.
Show that the formula can suffer catastrophic cancellation when the data are clustered around a large mean.
Derive the two-pass alternative \sigma^2=\frac1n\sum_{j=1}^n (x_j-\bar{x})^2.
The standard formula for computing the hypotenuse is h(x,y)=\sqrt{x^2+y^2}.
Explain how the formula may overflow or underflow even when the final result is representable.
Derive the scaled form h(x,y) = v\sqrt{1+(u/v)^2}, \qquad v=\max(|x|,|y|), \qquad u=\min(|x|,|y|).
Explain why the scaled form is safer.
Let x\in\mathbb R^m and y\in\mathbb R^n. Consider the rank-one outer product S=xy^T, where s_{ij}=x_iy_j. Prove that the computed entries satisfy \widehat{s}_{ij}=s_{ij}(1+\delta_{ij}), \qquad |\delta_{ij}|\le u. Contrast this one-rounding structure with the \gamma_n-behavior of inner products.
Consider x_n=n\left(\exp\left(\frac1n\right)-1\right).
Prove analytically that x_n\to1.
Explain why direct floating-point evaluation eventually loses all meaningful digits as n\to\infty.
Give a stable reformulation using \operatorname{expm1}.
Advanced problems \star\star
The Kahan summation algorithm computes the sum of n numbers by maintaining a compensation term: \begin{aligned} s_1 &= x_1,\qquad c_1=0,\\ y_k &= \fl(x_k-c_{k-1}),\\ t_k &= \fl(s_{k-1}+y_k),\\ c_k &= \fl\!\left(\fl(t_k-s_{k-1})-y_k\right),\\ s_k &= t_k. \end{aligned} Prove, under the standard model, that the final error satisfies the first-order estimate |\widehat{s}_n-s| \le \left(2u+O(nu^2)\right)\sum_{j=1}^n |x_j|. Explain the structural mechanism by which the first-order n-dependence is removed.
Let a,b\in\mathcal F, and assume round-to-nearest arithmetic with no overflow or underflow. The TwoSum algorithm is \begin{aligned} s &= \fl(a+b),\\ z &= \fl(s-a),\\ e &= \fl\big((a-(s-z))+(b-z)\big). \end{aligned} Prove that a+b=s+e exactly in real arithmetic. Explain why this identity is fundamental for compensated summation and double-double arithmetic.
Assume a,b\in\mathcal F, |a|\ge |b|, and round-to-nearest arithmetic. Consider \begin{aligned} s &= \fl(a+b),\\ e &= \fl\big(b-(s-a)\big). \end{aligned}
Prove that a+b=s+e exactly.
Construct a counterexample showing that the conclusion may fail when |a|\ge |b| is removed.
Compare FastTwoSum with TwoSum.
Consider a monic polynomial p(z)=\prod_{j=1}^n(z-\lambda_j) with distinct roots. Let p be perturbed to p(z)+\epsilon q(z), \qquad \deg(q)\le n-1.
Prove that the first-order perturbation of \lambda_k satisfies \Delta\lambda_k = -\epsilon\frac{q(\lambda_k)}{p'(\lambda_k)} + O(\epsilon^2).
Deduce that the absolute sensitivity of \lambda_k is governed by \frac{1}{|p'(\lambda_k)|}.
Explain why Wilkinson’s polynomial p(z)=\prod_{j=1}^{20}(z-j) exhibits extreme ill-conditioning.
Let A\in\mathbb R^{n\times n} be nonsingular, and consider F(A)=A^{-1}. Using the differential identity D(A^{-1})[E]=-A^{-1}EA^{-1}, show that the relative condition number of matrix inversion is bounded by \kappa_{\mathrm{rel}}(F,A)\le \|A\|\,\|A^{-1}\|. Discuss conditions under which equality is attained.
Let Ax=b, \qquad (A+\Delta A)(x+\Delta x)=b+\Delta b. Suppose |\Delta A|\le \omega |A|, \qquad |\Delta b|\le \omega |b| componentwise. Derive the first-order componentwise estimate \frac{\|\Delta x\|_\infty}{\|x\|_\infty} \le \omega \frac{ \left\| |A^{-1}|\,|A|\,|x| + |A^{-1}|\,|b| \right\|_\infty } {\|x\|_\infty} + O(\omega^2). Explain why this may be sharper than a normwise \kappa(A)-based estimate.
Let A\in\mathbb R^{m\times n} and x\in\mathbb R^n. Let \widehat{y}=\fl(Ax) be computed by the standard row dot-product algorithm. Prove that there exists \Delta A such that \widehat{y}=(A+\Delta A)x, \qquad |\Delta A|\le \gamma_n |A| componentwise.
Let x,y\in\mathbb R^n. Compare the componentwise backward stability of:
the inner product s=x^Ty;
the rank-one outer product S=xy^T.
Prove that each entry of the outer product is affected by only one multiplication rounding, whereas the inner product accumulates a \gamma_n-type factor.
Let p(x)=\sum_{k=0}^n a_kx^k be evaluated by Horner’s rule: y_n=a_n, \qquad y_k=\fl(y_{k+1}x+a_k), \qquad k=n-1,\ldots,0. Prove that the computed value \widehat{p}(x)=y_0 satisfies |\widehat{p}(x)-p(x)| \le \gamma_{2n}\sum_{k=0}^n |a_k||x|^k.
A fused multiply-add operation computes \operatorname{fma}(a,b,c)=\fl(ab+c) with only one final rounding. Prove that a dot product accumulated using FMA admits a sharper error bound involving \gamma_n, rather than the \gamma_{2n}-type bound associated with separate multiplication and addition.
Recall \gamma_n=\frac{nu}{1-nu}. Prove:
\gamma_k<\gamma_n for k<n;
\gamma_m+\gamma_n+\gamma_m\gamma_n\le \gamma_{m+n};
if |\theta_m|\le\gamma_m and |\theta_n|\le\gamma_n, then (1+\theta_m)(1+\theta_n)=1+\theta_{m+n}, \qquad |\theta_{m+n}|\le\gamma_{m+n}.
Let F(A)=\det(A) for nonsingular A. Use D(\det)(A)[E] = \det(A)\operatorname{trace}(A^{-1}E) to study the conditioning of determinant evaluation.
Prove the differential identity.
Show that \frac{|\det(A+E)-\det(A)|}{|\det(A)|} \le n\|A^{-1}\|\,\|E\|+O(\|E\|^2).
Rewrite the estimate in terms of \|E\|/\|A\|.
Let x\in[\underline{x},\overline{x}], \qquad y\in[\underline{y},\overline{y}]. Assume directed rounding toward -\infty and +\infty.
Derive interval enclosures for x+y, x-y, xy, and x/y, assuming 0\notin[\underline{y},\overline{y}].
Prove that outward rounding gives an interval containing the exact result.
Give an explicit example of dependency overestimation.
Let U\in\mathbb R^{n\times n} be nonsingular and upper triangular. Let \widehat{x} be computed by back substitution for Ux=b. Prove that there exists an upper triangular perturbation \Delta U such that (U+\Delta U)\widehat{x}=b, \qquad |\Delta U|\le \gamma_n |U| componentwise, up to harmless row-dependent constants.
Let F(x,y)=x-y. Derive its relative condition number with respect to perturbations in (x,y). Explain precisely why subtraction is ill-conditioned when x\approx y.
Let p(x)=a_0+a_1x+\cdots+a_nx^n. Compare the operation count and rounding-error structure of direct monomial evaluation with Horner evaluation. Derive a qualitative reason why Horner’s method is preferred.
Consider the roots \lambda_\pm of ax^2+bx+c=0. Let f(a,b,c)=\lambda_+ be the root function. Compute the gradient \nabla f(a,b,c) wherever the root is simple. Use it to write a relative condition number with respect to perturbations in (a,b,c). Under what conditions on the coefficients does root-finding become intrinsically ill-conditioned?
Let A\in\mathbb R^{n\times n} with \|A\|_2<1. We wish to compute Y=(I-A)^{-1} via the truncated Neumann series Y_k=\sum_{j=0}^{k}A^j.
Derive an upper bound on the relative condition number of this problem with respect to perturbations in A.
Assuming \|\fl(BC)-BC\|_2\le \gamma_n\|B\|_2\|C\|_2, derive an inductive forward-error bound for the computed series \widehat{Y}_k.
Consider x_{k+1}=\frac{13}{3}x_k-\frac{4}{3}x_{k-1}, \qquad x_0=1, \qquad x_1=\frac13.
Show analytically that the exact solution is x_k=(1/3)^k.
Observe that the characteristic polynomial has a second root 4. Explain why floating-point errors generically excite this mode and eventually cause exponential divergence.
Let A=\begin{pmatrix}a&b\\c&d\end{pmatrix}. The standard determinant algorithm computes \det(A)=ad-bc.
Derive a relative error bound for \fl(\fl(ad)-\fl(bc)) using the standard model.
Explain why the computation loses relative accuracy when ad\approx bc.
Explain how a fused multiply-add unit can help in an error-free transformation for ad-bc.
Let F(A)=e^A=\sum_{k=0}^{\infty}\frac{A^k}{k!}. Prove that the Fréchet derivative of F at A in the direction E is DF(A)E=\int_0^1 e^{(1-s)A}E e^{sA}\,ds. Use this identity to obtain a norm bound for \|DF(A)\|.
Consider Rump’s bivariate polynomial f(x,y) = 333.75y^6+x^2(11x^2y^2-y^6-121y^4-2)+5.5y^8+\frac{x}{2y}. Evaluate or analyze this expression for x=771751, \qquad y=424401. Explain why standard floating-point evaluation can give dramatically wrong values, including wrong signs, and identify the cancellation mechanism responsible for the failure.
Research-level problems \star\star\star
Let Ax=b be solved using an LU factorization computed in a low precision with unit roundoff u_\ell. Suppose residuals are computed in a higher precision with unit roundoff u_h\ll u_\ell. The refinement process is r_k=b-Ax_k, \qquad A d_k=r_k, \qquad x_{k+1}=x_k+d_k. Model the low-precision correction solve as applying A^{-1}+\Delta, where \|\Delta\|\le C u_\ell\|A^{-1}\|. Derive the recurrence \|e_{k+1}\| \le C u_\ell\kappa(A)\|e_k\| + O(u_h)\|x\|. Conclude that refinement converges if C u_\ell\kappa(A)<1.
Let H=I-2vv^T, \qquad \|v\|_2=1. Suppose \widehat{y} is computed by applying H to x: y=Hx=x-2v(v^Tx). Assuming the dot product and axpy operations satisfy the usual floating-point error bounds, prove that \widehat{y}=(H+\Delta H)x, \qquad \|\Delta H\|_2\le C_nu. Explain why Householder transformations are preferred over explicitly forming normal equations in least-squares problems.
Let A=[a_1,a_2]\in\mathbb R^{m\times2} have nearly parallel columns. Let \widehat{q}_1,\widehat{q}_2 be produced by classical Gram–Schmidt in floating-point arithmetic. Show that |\widehat{q}_1^T\widehat{q}_2| can be proportional to \kappa(A)u, rather than merely u. Explain the role of cancellation in the orthogonalization step.
Consider the stable method for solving ax^2+bx+c=0 when b>0: x_1=\frac{-b-\sqrt{b^2-4ac}}{2a}, \qquad x_2=\frac{c}{a x_1}. Perform a forward error analysis using the standard model and derive an explicit upper bound for the relative error of \widehat{x}_2. Explain why this calculation remains robust when b^2\gg4ac.
Let z=a+ib and w=c+id. The standard floating-point multiplication evaluates \fl(zw)= \fl(\fl(ac)-\fl(bd)) + i\,\fl(\fl(ad)+\fl(bc)). Prove a normwise error estimate of the form \|\fl(zw)-zw\|_2 \le C\gamma_2\|z\|_2\|w\|_2 for a small absolute constant C. Determine the sharpest constant your proof gives.
Let D_1 and D_2 be positive diagonal matrices.
Show by example that the normwise condition number \kappa(A)=\|A\|\,\|A^{-1}\| is not invariant under diagonal scaling A\mapsto D_1AD_2.
Define the Skeel-type row-scaling condition quantity \kappa_{\mathrm{S}}(A) = \left\| |A^{-1}|\,|A| \right\|_{\infty}. Prove its invariance under positive row scaling A\mapsto DA.
Explain why componentwise conditioning can be more informative for highly scaled matrices.
Let V\in\mathbb R^{n\times n} be a Vandermonde matrix generated by distinct positive real nodes. Use Gautschi-type bounds, or derive suitable lower bounds, to show that Vandermonde matrices in the monomial basis may become exponentially ill-conditioned as n grows. Explain what this reveals about high-degree fitting in the monomial basis.
Let A\in\mathbb R^{n\times n} be symmetric positive definite, and let \widehat{L} be the computed Cholesky factor obtained in floating-point arithmetic. Prove a normwise backward-error statement of the form \widehat{L}\widehat{L}^T=A+\Delta A, \qquad \|\Delta A\|_2\le C_nu\|A\|_2, for a modest dimension-dependent constant C_n. Explain why no pivoting is needed for positive definite matrices.
Strassen’s algorithm computes C=AB for n\times n matrices using fewer scalar multiplications by performing linear combinations of submatrices.
Prove that a Strassen-type algorithm satisfies a normwise error estimate of the form \|\widehat{C}-C\|_F \le c_n u\|A\|_F\|B\|_F, with a growth factor c_n reflecting the recursion and additions.
Explain why this bound is weaker than the componentwise backward-error interpretation available for classical matrix multiplication.
Discuss why a faster asymptotic arithmetic count does not automatically imply superior numerical behavior.
Assume a stochastic rounding model in which \fl(x)=x(1+\delta), \qquad \mathbb E[\delta]=0, \qquad |\delta|\le u.
Derive the expected error of a product of n independent rounding factors.
Compare the expected error growth with the deterministic \gamma_n-bound.
Discuss why stochastic rounding may help in low-precision iterative methods.
Design a compensated dot-product algorithm based on error-free transformations such as TwoSum and TwoProduct. Prove a componentwise backward-error estimate sharper than the standard dot-product \gamma_n estimate, clearly stating every assumption on rounding mode and availability of fused multiply-add.
Construct, or prove the existence of, a family of inputs x_1,\ldots,x_n for which the recursive summation error bound |\widehat{s}-s| \le \gamma_{n-1}\sum_{j=1}^n |x_j| is sharp up to a modest constant factor. Discuss the role of signs and ordering.
This problem previews Chapter 4. Let Gaussian elimination with partial pivoting be applied to Ax=b. Under the standard model, formulate the type of backward-error statement one expects: (A+\Delta A)\widehat{x}=b, \qquad |\Delta A|\le C_nu\,|\widehat{L}|\,|\widehat{U}|. Explain why the growth factor enters the analysis and why pivoting matters.
Parallel summation may evaluate the same mathematical sum in different orders. Explain why this can produce different floating-point results. Propose a reproducible summation strategy and analyze its expected error growth using pairwise or compensated summation ideas.
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 1. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 1.1
Problem formulation.
Let x=\pi and \widetilde{x}=3.14. Compute the absolute and relative errors.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.2
Problem formulation.
In a decimal floating-point system with \beta=10 and t=5, compute \varepsilon_{\mathrm{mach}} and the unit roundoff for rounding to nearest.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
In a normalized base-\beta floating-point system with precision p, adjacent numbers near 1 are separated by \beta^{1-p}. If rounding to nearest is used, the maximum relative rounding error is one half of this spacing: u=\frac12\beta^{1-p}. The machine epsilon often used in software is the distance from 1 to the next larger floating-point number: \varepsilon_{\rm mach}=\beta^{1-p}. Therefore u=\frac{\varepsilon_{\rm mach}}{2}. The standard rounding model is \fl(x)=x(1+\delta), \qquad |\delta|\le u, provided x is in the normalized range and no overflow or underflow occurs.
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 1.3
Problem formulation.
Prove that if \fl(x)=x(1+\delta) and |\delta|\le u, then |\fl(x)-x|\le u|x|.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.4
Problem formulation.
Show that 1-\cos x=2\sin^2\left(\frac{x}{2}\right). Explain why the right-hand side is numerically preferable for small x.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.5
Problem formulation.
Let f(x)=x^p, with p\in\mathbb R. Compute the relative condition number \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.6
Problem formulation.
Let f(x)=\log x. Compute \kappa_f(x). Explain why the problem is ill-conditioned near x=1.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.7
Problem formulation.
Prove the referenced result using induction instead of the product estimate.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.8
Problem formulation.
Let s=\sum_{j=1}^n x_j. Use the referenced result to derive a relative error bound for \widehat{s}, assuming s\ne0.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.9
Problem formulation.
Construct an example where \sum_j |x_j|\gg |\sum_j x_j|. Explain why summation is then sensitive to rounding.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.10
Problem formulation.
Let Ax=b be nonsingular and let \widetilde{x} be a computed approximation. Prove that x-\widetilde{x}=A^{-1}(b-A\widetilde{x}).
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.11
Problem formulation.
Suppose an algorithm is backward stable for a problem with condition number \kappa. Explain why the expected forward error is proportional to \kappa u.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.12
Problem formulation.
For the quadratic equation ax^2+bx+c=0, derive a cancellation-free procedure for computing both roots when b>0 and b^2\gg 4ac.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Cancellation occurs when two nearly equal quantities are subtracted: a-b,\qquad a\approx b. If a and b are already rounded, the relative error in a-b can be much larger than the relative errors in a and b. For the quadratic formula, x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}, cancellation occurs when -b and \sqrt{b^2-4ac} have nearly the same magnitude and opposite signs. A stable form is q=-\frac12\left(b+\operatorname{sign}(b)\sqrt{b^2-4ac}\right), x_1=\frac{q}{a}, \qquad x_2=\frac{c}{q}. The second root is obtained from x_1x_2=c/a, avoiding the dangerous subtraction.
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 1.13
Problem formulation.
The Kahan summation algorithm computes the sum of n numbers x_1, x_2, \ldots, x_n by maintaining a running compensation term c for accumulated rounding errors: \begin{aligned} s_1 &= x_1, \quad c_1 = 0 \\ \text{For } &k = 2, \ldots, n: \\ & y_k = x_k - c_{k-1} \\ & t_k = s_{k-1} + y_k \\ & c_k = (t_k - s_{s-1}) - y_k \\ & s_k = t_k \end{aligned} Prove that under the standard model of floating-point arithmetic, the final error satisfies |\widehat{s}_n - s| \le \left( 2u + O(n u^2) \right) \sum_{j=1}^n |x_j|, thereby showing that the error bound is independent of n to first order.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.14
Problem formulation.
In standard real arithmetic, addition is associative. Prove that in any floating-point system \mathcal{F}(\beta, t, L, U) with t \ge 2, associativity fails. Specifically, construct a concrete counterexample showing that \fl(\fl(a + b) + c) \neq \fl(a + \fl(b + c)), even when no underflow or overflow occurs.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.15
Problem formulation.
Let x and y be floating-point numbers in \mathcal{F}(\beta, t, L, U). Suppose that \frac{1}{\beta} \le \frac{x}{y} \le \beta. Prove or disprove: x - y is exactly representable in \mathcal{F}. If it is false, provide the sharpest lower and upper bounds on x/y for which exact subtraction is guaranteed under radix \beta.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.16
Problem formulation.
When a floating-point system includes subnormal (denormalized) numbers, the minimum positive representable number shifts from x_{\min} = \beta^L to x_{\min}^{\text{sub}} = \beta^{L-(t-1)}.
Prove that if subnormal numbers are used, the absolute representation error model |x - \fl(x)| remains bounded by a constant for all |x| < \beta^L. What is this constant?
Show that without subnormal numbers (flush-to-zero policy), Sterbenz Lemma fails completely.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.17
Problem formulation.
Consider a monic polynomial p(z) = \prod_{j=1}^n (z - \lambda_j) with distinct roots. Let one particular root \lambda_k be perturbed to \lambda_k + \Delta \lambda_k due to a small coefficient perturbation p(z) + \epsilon q(z), where \deg(q) \le n-1.
Prove that the absolute condition number of the root \lambda_k with respect to variations in the polynomial coefficients is given by \kappa_{\text{abs}}(\lambda_k) = \frac{1}{|p'(\lambda_k)|}.
Use this to explain why Wilkinson’s polynomial p(z) = \prod_{j=1}^{20} (z - j) exhibits extreme ill-conditioning near its larger roots.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.18
Problem formulation.
Let A \in \mathbb{R}^{n \times n} be a nonsingular matrix, and consider the matrix inversion problem F(A) = A^{-1}. Show that using any subordinate componentwise matrix norm \|\cdot\|, the relative condition number of matrix inversion is exactly equal to the standard matrix condition number: \kappa_{\text{rel}}(F, A) = \|A\| \cdot \|A^{-1}\| = \kappa(A).
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.19
Problem formulation.
Let Ax = b and (A + \Delta A)(x + \Delta x) = b + \Delta b. Suppose we have a structural componentwise bound |\Delta A| \le \omega |A| and |\Delta b| \le \omega |b|, where the inequalities and absolute values hold element-by-element. Prove that \frac{\|\Delta x\|_\infty}{\|x\|_\infty} \le \omega \frac{\||A^{-1}| \cdot |A| \cdot |x| + |A^{-1}| \cdot |b|\|_\infty}{\|x\|_\infty} + O(\omega^2). Explain why this componentwise condition number can be significantly smaller than \kappa(A) when A is highly scaled or sparse.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.20
Problem formulation.
Consider evaluating f(x) = e^{-x} for large x > 0 using its Taylor series expansion: e^{-x} = \sum_{k=0}^\infty \frac{(-1)^k x^k}{k!}.
Determine the maximum magnitude of an individual term in the summation as a function of x.
Prove that evaluating this series directly in floating-point arithmetic leads to a catastrophic loss of relative precision for large x, and derive an alternative, backward-stable algebraic reformulation to compute e^{-x}.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Cancellation occurs when two nearly equal quantities are subtracted: a-b,\qquad a\approx b. If a and b are already rounded, the relative error in a-b can be much larger than the relative errors in a and b. For the quadratic formula, x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}, cancellation occurs when -b and \sqrt{b^2-4ac} have nearly the same magnitude and opposite signs. A stable form is q=-\frac12\left(b+\operatorname{sign}(b)\sqrt{b^2-4ac}\right), x_1=\frac{q}{a}, \qquad x_2=\frac{c}{q}. The second root is obtained from x_1x_2=c/a, avoiding the dangerous subtraction.
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 1.21
Problem formulation.
Let A \in \mathbb{R}^{m \times n} and x \in \mathbb{R}^n. Let \widehat{y} = \fl(Ax) be the matrix-vector product evaluated via the standard row dot-product algorithm. Prove that \widehat{y} satisfies a componentwise backward error relation of the form: \widehat{y} = (A + \Delta A)x, \quad |\Delta A| \le \gamma_n |A|. Is it possible to satisfy this bound if \Delta A is restricted to be normwise instead of componentwise?
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.22
Problem formulation.
The standard formula for computing the length of the hypotenuse is f(x,y) = \sqrt{x^2 + y^2}.
Identify the range of inputs (x,y) where this formula triggers an unwarranted overflow or underflow even though the final mathematical result f(x,y) is perfectly representable in \mathcal{F}.
Prove that the reformulated algorithm f(x,y) = v \cdot \sqrt{1 + \left(\frac{u}{v}\right)^2}, \quad v = \max(|x|,|y|), \quad u = \min(|x|,|y|), is forward stable and safe from spurious overflow/underflow. Bound its relative error.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.23
Problem formulation.
Let x and y be positive real numbers. We wish to evaluate f(x,y) = \ln(x) - \ln(y).
Derive the relative condition number \kappa_{\text{rel}}(f, (x,y)). When is this problem ill-conditioned?
Show that evaluating \fl(\fl(\ln x) - \fl(\ln y)) exhibits severe forward error when x \approx y, and provide a stable alternative evaluation method using the standard \operatorname{log1p}(z) = \ln(1+z) framework.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.24
Problem formulation.
Let x, y \in \mathbb{R}^n. Compare the componentwise backward stability of:
The inner product s = x^T y.
The rank-one outer product matrix s_{ij} = x_i y_j.
Prove that the outer product is always perfectly backward stable with |\Delta s_{ij}| \le u |s_{ij}|, whereas the inner product requires the cumulative \gamma_n factor. Explain the structural difference.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.25
Problem formulation.
Let p(x) = \sum_{k=0}^n a_k x^k be evaluated using Horner’s rule: y_n = a_n, \quad y_k = \fl(y_{k+1} x + a_k), \quad k = n-1, n-2, \ldots, 0. Prove that the computed value \widehat{p}(x) = y_0 satisfies: |\widehat{p}(x) - p(x)| \le \gamma_{2n} \sum_{k=0}^n |a_k| |x|^k.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.26
Problem formulation.
Let V \in \mathbb{R}^{n \times n} be a Vandermonde matrix defined by distinct real nodes x_1, x_2, \ldots, x_n. Prove that as n \to \infty, the condition number \kappa_2(V) grows at least exponentially with n, regardless of the choice of nodes within a bounded interval [a,b]. What does this imply about fitting high-degree polynomials using a monomial basis?
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.27
Problem formulation.
Recall the definition \gamma_n = \frac{nu}{1-nu}. Prove the following identities and bounds used frequently in multi-term error propagation sequences:
\gamma_k < \gamma_n for k < n.
\gamma_m + \gamma_n + \gamma_m \gamma_n \le \gamma_{m+n}.
(1 + \theta_m)(1 + \theta_n) = 1 + \theta_{m+n}, where |\theta_i| \le \gamma_i.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.28
Problem formulation.
Consider the classic stable method for solving a x^2 + b x + c = 0 when b > 0: x_1 = \frac{-b - \sqrt{b^2 - 4ac}}{2a}, \quad x_2 = \frac{c}{a x_1}. Perform a thorough forward error analysis using the standard model to find an explicit upper bound for the relative error of the computed root \widehat{x}_2. Show that the calculation of x_2 remains robust even if b^2 \gg 4ac.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Cancellation occurs when two nearly equal quantities are subtracted: a-b,\qquad a\approx b. If a and b are already rounded, the relative error in a-b can be much larger than the relative errors in a and b. For the quadratic formula, x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}, cancellation occurs when -b and \sqrt{b^2-4ac} have nearly the same magnitude and opposite signs. A stable form is q=-\frac12\left(b+\operatorname{sign}(b)\sqrt{b^2-4ac}\right), x_1=\frac{q}{a}, \qquad x_2=\frac{c}{q}. The second root is obtained from x_1x_2=c/a, avoiding the dangerous subtraction.
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 1.29
Problem formulation.
Let A = [q_1, q_2] \in \mathbb{R}^{m \times 2} have columns that are nearly parallel. Let \widehat{q}_1, \widehat{q}_2 be the vectors obtained via the Classical Gram-Schmidt (CGS) algorithm in floating-point arithmetic. Show that the loss of orthogonality |\widehat{q}_1^T \widehat{q}_2| can be proportional to \kappa(A) u, rather than u.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.30
Problem formulation.
Let z = a + ib and w = c + id be two complex numbers. The standard floating-point multiplication evaluates: \fl(zw) = \fl(\fl(ac) - \fl(bd)) + i \, \fl(\fl(ad) + \fl(bc)). Prove that the normwise forward error satisfies: \|\fl(zw) - zw\|_2 \le \sqrt{2} \, \gamma_2 \|z\|_2 \|w\|_2.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.31
Problem formulation.
Let D be a diagonal matrix with positive diagonal entries. Prove that the relative condition number \kappa(A) = \|A\| \cdot \|A^{-1}\| satisfies: \kappa(DAD) \neq \kappa(A) \quad \text{in general,} but that the componentwise relative condition number defined via the matrix skeleton \||A^{-1}| \cdot |A|\|_2 is invariant under arbitrary diagonal scaling transformations A \leftarrow D_1 A D_2.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.32
Problem formulation.
Consider the sequence defined by x_0 = 1 and the analytical definition of the exponential limit: x_{n} = n \left( \exp\left(\frac{1}{n}\right) - 1 \right).
Prove analytically that \lim_{n \to \infty} x_n = 1.
Implement or mathematically simulate this iteration in a standard floating-point environment. Show that as n \to \infty, the computed values \widehat{x}_n eventually collapse to 0. Analyze the precise step where cancellation occurs.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Cancellation occurs when two nearly equal quantities are subtracted: a-b,\qquad a\approx b. If a and b are already rounded, the relative error in a-b can be much larger than the relative errors in a and b. For the quadratic formula, x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}, cancellation occurs when -b and \sqrt{b^2-4ac} have nearly the same magnitude and opposite signs. A stable form is q=-\frac12\left(b+\operatorname{sign}(b)\sqrt{b^2-4ac}\right), x_1=\frac{q}{a}, \qquad x_2=\frac{c}{q}. The second root is obtained from x_1x_2=c/a, avoiding the dangerous subtraction.
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 1.33
Problem formulation.
Let n=2^m, and suppose that s=\sum_{j=1}^n x_j is computed by a balanced binary summation tree rather than by recursive left-to-right summation. Assume the standard floating-point model and no overflow or underflow.
Prove that the computed sum \widehat{s} satisfies \widehat{s} = \sum_{j=1}^n x_j(1+\theta_j), \qquad |\theta_j|\le \gamma_m, \qquad m=\log_2 n.
Deduce the absolute error bound |\widehat{s}-s| \le \gamma_{\log_2 n} \sum_{j=1}^n |x_j|.
Compare this estimate with the standard recursive summation bound |\widehat{s}_{\mathrm{rec}}-s| \le \gamma_{n-1}\sum_{j=1}^n |x_j|. Explain why pairwise summation is preferable for large n.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.34
Problem formulation.
Let a,b\in\mathcal F, and assume round-to-nearest arithmetic with no overflow or underflow. The following algorithm is known as TwoSum: \begin{aligned} s &= \fl(a+b),\\ z &= \fl(s-a),\\ e &= \fl\big((a-(s-z))+(b-z)\big). \end{aligned} Prove that a+b=s+e exactly in real arithmetic. In other words, s is the rounded floating-point sum and e is the exact rounding error represented as a floating-point number.
Then explain why this result is fundamental for compensated summation and double-double arithmetic.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.35
Problem formulation.
Assume a,b\in\mathcal F, |a|\ge |b|, and round-to-nearest arithmetic. Consider the algorithm \begin{aligned} s &= \fl(a+b),\\ e &= \fl\big(b-(s-a)\big). \end{aligned}
Prove that, under the stated magnitude condition, a+b=s+e exactly.
Show by constructing a counterexample that the conclusion may fail if the assumption |a|\ge |b| is removed.
Compare FastTwoSum with TwoSum in terms of arithmetic cost and hypotheses.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.36
Problem formulation.
Let x_1,\ldots,x_n\in\mathbb R. The variance may be written as \sigma^2 = \frac1n\sum_{j=1}^n x_j^2 - \left(\frac1n\sum_{j=1}^n x_j\right)^2.
Prove that this formula is mathematically correct.
Show that if the data are clustered around a large mean, then the two terms \frac1n\sum_{j=1}^n x_j^2 \qquad\text{and}\qquad \left(\frac1n\sum_{j=1}^n x_j\right)^2 can be nearly equal, producing catastrophic cancellation.
Derive a backward-stable two-pass alternative based on \sigma^2 = \frac1n\sum_{j=1}^n (x_j-\bar{x})^2, \qquad \bar{x}=\frac1n\sum_{j=1}^n x_j.
Explain why the two-pass method is still not immune to all rounding errors, but is usually much more stable than the one-pass formula.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Cancellation occurs when two nearly equal quantities are subtracted: a-b,\qquad a\approx b. If a and b are already rounded, the relative error in a-b can be much larger than the relative errors in a and b. For the quadratic formula, x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}, cancellation occurs when -b and \sqrt{b^2-4ac} have nearly the same magnitude and opposite signs. A stable form is q=-\frac12\left(b+\operatorname{sign}(b)\sqrt{b^2-4ac}\right), x_1=\frac{q}{a}, \qquad x_2=\frac{c}{q}. The second root is obtained from x_1x_2=c/a, avoiding the dangerous subtraction.
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 1.37
Problem formulation.
A fused multiply–add operation computes \operatorname{fma}(a,b,c)=\fl(ab+c) with only one final rounding, instead of computing \fl(\fl(ab)+c).
Let s=x^Ty=\sum_{j=1}^n x_jy_j.
Prove that the standard dot-product algorithm without FMA admits a backward error bound involving \gamma_{2n}.
Prove that a dot product accumulated using FMA admits a sharper bound of the form \widehat{s} = \sum_{j=1}^n x_jy_j(1+\theta_j), \qquad |\theta_j|\le \gamma_n.
Explain why the improvement is not merely cosmetic when n is large.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.38
Problem formulation.
Let U\in\mathbb R^{n\times n} be nonsingular and upper triangular. Let \widehat{x} be the result of solving Ux=b by floating-point back substitution. Assume the standard model and no overflow or underflow.
Prove that there exists an upper triangular perturbation \Delta U such that (U+\Delta U)\widehat{x}=b and |\Delta U| \le \gamma_n |U| componentwise, up to harmless changes in the constant depending on the precise operation count in each row.
Then explain why triangular solves are backward stable but may still have large forward error if U is ill-conditioned.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.39
Problem formulation.
Let F(A)=\det(A) for nonsingular A\in\mathbb R^{n\times n}. Use the identity D(\det)(A)[E] = \det(A)\operatorname{trace}(A^{-1}E) to study the conditioning of determinant evaluation.
Prove the differential identity above.
For a subordinate matrix norm, show that \frac{|\det(A+E)-\det(A)|}{|\det(A)|} \le n\|A^{-1}\|\|E\|+O(\|E\|^2).
Rewrite this estimate in terms of the relative perturbation \frac{\|E\|}{\|A\|}.
Explain why determinant computation may be extremely ill-conditioned even when the determinant itself is not close to zero in absolute value.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
For a scalar problem y=f(x), perturb x to x+\Delta x. Taylor expansion gives f(x+\Delta x)-f(x)=f'(x)\Delta x+O(\Delta x^2). The relative output perturbation is therefore \frac{|f(x+\Delta x)-f(x)|}{|f(x)|} \approx \left|\frac{x f'(x)}{f(x)}\right| \frac{|\Delta x|}{|x|}. Hence the relative condition number is \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. For a linear system Ax=b, perturbation analysis gives \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \left( \frac{\|\Delta A\|}{\|A\|} + \frac{\|\Delta b\|}{\|b\|} \right), where \kappa(A)=\|A\|\,\|A^{-1}\|.
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 1.40
Problem formulation.
Let x and y be real numbers known only through intervals x\in [\underline{x},\overline{x}], \qquad y\in [\underline{y},\overline{y}]. Assume the floating-point system supports directed rounding toward -\infty and +\infty.
Derive rigorous interval enclosures for x+y, x-y, xy, and x/y, assuming 0\notin[\underline{y},\overline{y}].
Prove that if every lower endpoint is rounded downward and every upper endpoint is rounded upward, then the resulting interval contains the exact real result.
Explain why interval arithmetic gives reliability but may suffer from overestimation due to dependency.
Give an explicit example where the dependency problem causes a much wider interval than necessary.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.41
Problem formulation.
Let Ax=b be solved using an LU factorization computed in a low precision with unit roundoff u_\ell. Suppose residuals are computed in a higher precision with unit roundoff u_h\ll u_\ell. The iterative refinement process is r_k=b-Ax_k, \qquad A d_k=r_k, \qquad x_{k+1}=x_k+d_k, where the correction equation is solved using the low-precision LU factors.
Model the low-precision triangular solves as applying an approximate inverse A^{-1}+\Delta, where \|\Delta\|\le C u_\ell \|A^{-1}\| for a modest constant C.
Derive an error recurrence of the form \|e_{k+1}\| \le C u_\ell \kappa(A)\|e_k\| + O(u_h)\|x\|.
Conclude that refinement converges provided C u_\ell \kappa(A)<1.
Explain why this theorem justifies modern mixed-precision solvers.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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 1.42
Problem formulation.
Let H=I-2vv^T, \qquad \|v\|_2=1, be a Householder reflector. In exact arithmetic, H is orthogonal: H^TH=I.
Suppose \widehat{y} is computed by applying the reflector to a vector x: y=Hx=x-2v(v^Tx). Assume the dot product and axpy operations satisfy the standard floating-point error bounds.
Prove that the computed vector \widehat{y} satisfies \widehat{y} = (H+\Delta H)x, where \|\Delta H\|_2 \le C_n u for a dimension-dependent constant C_n.
Explain why products of Householder reflectors are preferred over explicitly forming normal equations in least-squares problems.
Compare this stability mechanism with the instability of classical Gram–Schmidt for nearly linearly dependent columns.
Method.
Use the floating-point model, conditioning definitions, rounding-error bounds, and stable algebraic reformulations.
Detailed solution and justification.
Use the standard floating-point model \fl(x\circ y)=(x\circ y)(1+\delta), \qquad |\delta|\le u, for \circ\in\{+,-,\times,/\}. If several operations are performed, the product of perturbation factors satisfies \prod_{j=1}^{n}(1+\delta_j)=1+\theta_n, \qquad |\theta_n|\le \gamma_n, where \gamma_n=\frac{nu}{1-nu}. Thus the required error estimate follows by replacing each floating-point operation by an exact operation multiplied by a factor 1+\delta_j, collecting the \theta_n terms, and bounding them by \gamma_n.
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.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.