Fundamentals

0.1 Evaluating a Polynomial

1) Polynomial

Polynomial: A function of the form

$$P(x)=c_0+c_1x+c_2x^2+\cdots+c_dx^d,$$

where $c_0,\ldots,c_d$ are coefficients and $d$ is the degree.

Degree: The largest exponent of $x$ whose coefficient is nonzero.

Polynomial Evaluation: The process of computing $P(x)$ for a given value of $x$.

2) Horner’s Method

Horner’s Method: An efficient method for evaluating a polynomial by rewriting it in nested form.

$$P(x) = c_0+x\left( c_1+x\left( c_2+\cdots+x(c_{d-1}+xc_d) \right) \right).$$

For a polynomial of degree $d$, Horner’s method requires:

• $d$ multiplications
• $d$ additions
• $O(d)$ time
• $O(1)$ additional space

Horner’s method avoids computing powers of $x$ separately.

3) Nested Multiplication

Nested Multiplication: A generalized form of Horner’s method using different base points.

$$P(x) = c_0+(x-r_0)\left( c_1+(x-r_1)\left( c_2+\cdots+(x-r_{d-1})c_d \right) \right).$$

Base Points: The values $r_0,r_1,\ldots,r_{d-1}$ used in the nested representation.

Nested multiplication is used in polynomial interpolation.

0.2 Binary Numbers

1) Positional Number System

Positional Number System: A representation in which the value of each digit depends on its position.

For a base-$b$ number,

$$(d_nd_{n-1}\cdots d_0.d_{-1}d_{-2}\cdots)_b = \sum_i d_i b^i.$$

2) Binary Number

Binary Number: A base-$2$ number whose digits are $0$ or $1$.

$$(\cdots b_2b_1b_0.b_{-1}b_{-2}\cdots)_2 = \sum_i b_i2^i.$$

Bit: A single binary digit whose value is either $0$ or $1$.

For example,

$$(10101)_2 = 2^4+2^2+2^0 = 21.$$

For a binary fraction,

$$(0.1011)_2 = 2^{-1}+2^{-3}+2^{-4} = \frac{11}{16}.$$

3) Decimal Integer to Binary

Repeated-Division Method: A method for converting a decimal integer to binary by repeatedly dividing by $2$.

1. Divide the integer by $2$.
2. Record the remainder.
3. Repeat with the quotient.
4. Read the remainders in reverse order.

$$(53)_{10}=(110101)_2.$$

4) Decimal Fraction to Binary

Repeated-Multiplication Method: A method for converting a decimal fraction to binary by repeatedly multiplying by $2$.

1. Multiply the fractional part by $2$.
2. Record the integer part.
3. Repeat with the new fractional part.
4. Read the recorded bits in order.

A finite decimal fraction may have an infinite binary representation.

$$(0.7)_{10} = (0.101100110011\ldots)_2.$$

5) Hexadecimal Number

Hexadecimal Number: A base-$16$ number using the digits $0$ through $9$ and $A$ through $F$.

Each hexadecimal digit corresponds to four binary bits.

$$(F)_{16}=(1111)_2=(15)_{10}.$$

Hexadecimal notation is a compact representation of binary data.

0.3 Floating-Point Representation

1) Floating-Point Number

Floating-Point Number: A finite approximation of a real number represented using a sign, significand, and exponent.

A normalized binary floating-point number has the form

$$(-1)^s(1.b_1b_2\cdots b_N)_2\,2^p,$$

where:

• $s$ is the sign bit.
• $1.b_1b_2\cdots b_N$ is the significand.
• $p$ is the exponent.

Significand: The part containing the significant digits of a floating-point number.

Normalized Number: A nonzero floating-point number whose significand has an implicit leading $1$.

2) IEEE 754 Formats

IEEE 754: The standard representation and arithmetic rules for binary floating-point numbers.

Format	Total Bits	Sign	Exponent	Fraction
Single precision	32	1	8	23
Double precision	64	1	11	52

For IEEE 754 double precision,

$$\text{value} = (-1)^s \left( 1+\sum_{i=1}^{52}b_i2^{-i} \right) 2^{E-1023},$$

for $1\leq E\leq2046$.

Exponent Bias: A fixed value added to the actual exponent before storage.

For double precision,

$$E=p+1023.$$

3) Floating-Point Approximation

Floating-Point Approximation: The representable floating-point number stored in place of an exact real number.

The notation

$$\operatorname{fl}(x)$$

denotes the floating-point approximation of $x$.

Many real numbers cannot be represented exactly with a finite number of binary digits.

For example,

$$\operatorname{fl}(0.1)\neq0.1$$

in exact real arithmetic.

4) Machine Epsilon

Machine Epsilon: The distance between $1$ and the next representable floating-point number greater than $1$.

For IEEE 754 double precision,

$$\epsilon_{\mathrm{mach}} = 2^{-52} \approx 2.220446049250313\times10^{-16}.$$

Machine epsilon measures floating-point spacing near $1$.

It is not the smallest positive representable number.

5) Rounding

Chopping: Removing all digits beyond the available precision.

Rounding to Nearest: Selecting the representable number closest to the exact value.

Round to Nearest, Ties to Even: If two representable values are equally close, select the one whose final stored bit is even.

For rounding to nearest,

$$\operatorname{fl}(x)=x(1+\delta), \qquad |\delta| \leq \frac{1}{2}\epsilon_{\mathrm{mach}}.$$

The value $\delta$ represents the relative rounding error.

6) Absolute Error

Absolute Error: The magnitude of the difference between an approximation $\hat{x}$ and the exact value $x$.

$$E_{\mathrm{abs}} = |\hat{x}-x|.$$

Absolute error measures the numerical distance between the two values.

7) Relative Error

Relative Error: The absolute error divided by the magnitude of the exact value.

$$E_{\mathrm{rel}} = \frac{|\hat{x}-x|}{|x|}, \qquad x\neq0.$$

Relative error measures the error in proportion to the size of the exact value.

8) Special Floating-Point Values

Exponent	Fraction	Value
$1$ to $2046$	Any	Normalized number
$0$	Zero	Signed zero
$0$	Nonzero	Subnormal number
$2047$	Zero	Positive or negative infinity
$2047$	Nonzero	NaN

Signed Zero: A representation of zero with either a positive or negative sign.

Infinity: A special value representing a result beyond the finite floating-point range.

NaN: “Not a Number,” representing an undefined or invalid numerical result.

9) Subnormal Number

Subnormal Number: A very small floating-point number represented without an implicit leading $1$.

For double precision,

$$\text{value} = (-1)^s (0.b_1b_2\cdots b_{52})_2 2^{-1022}.$$

The smallest positive subnormal double is

$$2^{-1074}.$$

Subnormal numbers allow gradual underflow near zero.

10) Overflow and Underflow

Overflow: A nonzero result is too large to be represented as a finite floating-point number.

Overflow usually produces positive or negative infinity.

Underflow: A nonzero result is smaller in magnitude than the normal floating-point range.

Underflow may produce a subnormal number or zero.

11) Floating-Point Addition

Floating-point addition generally performs four steps:

1. Align the exponents.
2. Add the significands.
3. Normalize the result.
4. Round the result.

When two operands differ greatly in magnitude, the smaller operand may have no effect on the result.

For double precision,

$$1+2^{-53}=1$$

under round to nearest, ties to even.

12) Floating-Point Arithmetic

Floating-Point Arithmetic: Arithmetic performed on finite approximations rather than exact real numbers.

Floating-point arithmetic is generally not associative.

$$(a+b)+c \neq a+(b+c).$$

Rounding errors make the order of operations important.

Floating-point values should usually be compared using absolute and relative tolerances.

$$|a-b| \leq \text{atol} + \text{rtol}\max(|a|,|b|).$$

0.4 Loss of Significance

1) Significant Digits

Significant Digits: Digits that contribute meaningful precision to a numerical value.

A numerical calculation loses accuracy when significant digits are removed or corrupted by rounding.

2) Cancellation

Cancellation: The loss of leading significant digits when subtracting numbers with similar magnitudes.

Cancellation is not always harmful, but it becomes dangerous when the operands already contain approximation errors.

3) Catastrophic Cancellation

Catastrophic Cancellation: A severe loss of relative accuracy caused by subtracting nearly equal approximate values.

If

$$x\approx y,$$

then the subtraction

$$x-y$$

may eliminate most significant digits.

The relative error of the result can be much larger than the relative errors of $x$ and $y$.

4) Numerically Stable Reformulation

Numerically Stable Reformulation: An algebraically equivalent expression designed to reduce rounding error or cancellation.

For $x\approx a^2$,

$$\sqrt{x}-a$$

is numerically unstable.

Using the conjugate,

$$\sqrt{x}-a = \frac{x-a^2}{\sqrt{x}+a}.$$

The second expression avoids subtracting nearly equal values.

Similarly,

$$\frac{1-\cos x}{\sin^2x}$$

is unstable near $x=0$.

Because

$$\sin^2x=(1-\cos x)(1+\cos x),$$

it can be rewritten as

$$\frac{1}{1+\cos x}.$$

5) Stable Quadratic Formula

For

$$ax^2+bx+c=0,$$

the ordinary quadratic formula is

$$x = \frac{-b\pm\sqrt{b^2-4ac}}{2a}.$$

One root may suffer from catastrophic cancellation when

$$b^2\gg4|ac|.$$

A numerically stable method defines

$$q = -\frac{1}{2} \left( b+\operatorname{sign}(b)\sqrt{b^2-4ac} \right).$$

The roots are then computed by

$$x_1=\frac{q}{a}, \qquad x_2=\frac{c}{q}.$$

This method avoids subtracting nearly equal quantities.

6) Numerical Stability

Numerical Stability: A property of an algorithm that prevents small rounding errors from growing excessively during computation.

A mathematically correct formula is not necessarily a numerically stable algorithm.

0.5 Review of Calculus

1) Limit

Limit: The value approached by a function as its input approaches a specified point.

$$\lim_{x\to a}f(x)=L.$$

Limits describe the local behavior of functions and form the basis of continuity and differentiation.

2) Continuity

Continuous Function: A function $f$ is continuous at $a$ if

$$\lim_{x\to a}f(x)=f(a).$$

A function is continuous on an interval if it is continuous at every point in that interval.

3) Intermediate Value Theorem

Intermediate Value Theorem: If $f$ is continuous on $[a,b]$, then $f$ takes every value between $f(a)$ and $f(b)$.

If

$$f(a)f(b)<0,$$

then there exists at least one $c\in(a,b)$ such that

$$f(c)=0.$$

This theorem is the foundation of bracketing root-finding methods such as the bisection method.

4) Derivative

Derivative: The instantaneous rate of change of a function.

$$f'(x) = \lim_{h\to0} \frac{f(x+h)-f(x)}{h}.$$

The derivative is also the slope of the tangent line to the graph of $f$.

5) Rolle’s Theorem

Rolle’s Theorem: If $f$ is continuous on $[a,b]$, differentiable on $(a,b)$, and

$$f(a)=f(b),$$

then there exists at least one $c\in(a,b)$ such that

$$f'(c)=0.$$

Rolle’s theorem is a special case of the Mean Value Theorem.

6) Mean Value Theorem

Mean Value Theorem: If $f$ is continuous on $[a,b]$ and differentiable on $(a,b)$, then there exists at least one $c\in(a,b)$ such that

$$f'(c) = \frac{f(b)-f(a)}{b-a}.$$

The theorem connects the average rate of change over an interval with an instantaneous rate of change.

7) Taylor Polynomial

Taylor Polynomial: A polynomial approximation constructed from the derivatives of a function at a point.

The degree-$k$ Taylor polynomial of $f$ centered at $x_0$ is

$$P_k(x) = \sum_{j=0}^{k} \frac{f^{(j)}(x_0)}{j!} (x-x_0)^j.$$

Expanded,

$$P_k(x) = f(x_0) + f'(x_0)(x-x_0) + \cdots + \frac{f^{(k)}(x_0)}{k!}(x-x_0)^k.$$

Taylor polynomials are used to derive and analyze numerical methods.

8) Taylor’s Theorem

Taylor’s Theorem: If $f$ has sufficiently many continuous derivatives, then

$$f(x)=P_k(x)+R_k(x),$$

where $P_k(x)$ is the Taylor polynomial and $R_k(x)$ is the remainder.

The Lagrange form of the remainder is

$$R_k(x) = \frac{f^{(k+1)}(c)}{(k+1)!} (x-x_0)^{k+1}$$

for some $c$ between $x_0$ and $x$.

9) Error Bound

Taylor Error Bound: If

$$|f^{(k+1)}(t)|\leq M$$

between $x_0$ and $x$, then

$$|R_k(x)| \leq \frac{M}{(k+1)!} |x-x_0|^{k+1}.$$

The remainder provides a bound on the approximation error.

10) Mean Value Theorem for Integrals

Mean Value Theorem for Integrals: If $f$ is continuous on $[a,b]$, then there exists some $c\in[a,b]$ such that

$$\int_a^b f(x)\,dx = f(c)(b-a).$$

Therefore,

$$f(c) = \frac{1}{b-a} \int_a^b f(x)\,dx.$$

The value $f(c)$ equals the average value of $f$ over the interval.

Essential Concepts

1. Horner’s Method: Evaluates a degree-$d$ polynomial using $d$ additions and $d$ multiplications.
2. Binary Representation: Represents numbers as sums of powers of $2$.
3. Floating-Point Number: Stores an approximation using a sign, significand, and exponent.
4. Machine Epsilon: Measures floating-point spacing near $1$.
5. Rounding Error: The error introduced when an exact value is replaced by a representable value.
6. Absolute Error: Measures the numerical difference from the exact value.
7. Relative Error: Measures the error relative to the size of the exact value.
8. Overflow: Occurs when a result exceeds the largest finite representable value.
9. Underflow: Occurs when a result is too small for the normal floating-point range.
10. Catastrophic Cancellation: Causes severe accuracy loss when nearly equal values are subtracted.
11. Numerical Stability: Describes whether an algorithm controls the growth of rounding errors.
12. Intermediate Value Theorem: Guarantees a root when a continuous function changes sign.
13. Mean Value Theorem: Relates average and instantaneous rates of change.
14. Taylor Polynomial: Approximates a smooth function near a chosen point.
15. Taylor Remainder: Measures and bounds the error of a Taylor approximation.