Numerical Analysis

\(k\)-digit decimal machine numbers are of the form \[ \pm 0.d_1 d_2 \dots d_{k} \times 10 ^{n}, \quad d_1 \in \{ 1, \dots , 9\}, d_{i} \in \{ 0, \dots , 9 \}, \forall i = 2, \dots , k. \]

The (\(k\)-digit) floating-point form of a positive real number \(y = 0.d_1 d_2 \dots d_{k} d_{k+1} \times 10 ^{n} \), denoted by \(fl(y)\), is obtained by terminating the mantissa of \(y\) at \(k\) decimal digits using one of these two methods:

1. Chopping: Chop off the digits \(d_{k+1} \dots \). \(fl(y) = y = 0.d_1 d_2 \dots d_{k} \times 10 ^{n}\).
2. Rounding: Add \(5 \times 10 ^{n-(k+1)}\) to \(y\) (i.e., 5 to \(d_{k+1}\)) and then chops the result to obtain a \(k\)-digit decimal machine. Note that the exponent might change.

Suppose \(p ^{*}\) is an approximation to \(p\). The absolute error is \(|p - p ^{*}|\) and the relative error is \(\frac{|p - p ^{*}|}{|p|}\) (provided that \(p \neq 0\)).

Suppose \(\{\beta_n\}_{n=1}^{\infty}\) is a sequence that converges to zero, and \(\{\alpha_n\}_{n=1}^{\infty}\) converges to a number \(\alpha\). If a positive constant \(K\) exists for large \(n\) such that \(|\alpha_n - \alpha| \leq K|\beta_n|\), we say that \(\{\alpha_n\}_{n=1}^{\infty}\) converges to \(\alpha\) with an order of convergence \(O(\beta_n)\), written as \(\alpha_n = \alpha + O(\beta_n)\).

Suppose \(\{\beta_n\}_{n=1}^{\infty}\) is a sequence that converges to zero, and \(\{\alpha_n\}_{n=1}^{\infty}\) converges to a number \(\alpha\). If a positive constant \(K\) exists for large \(n\) such that \(|\alpha_n - \alpha| \leq K|\beta_n|\), we say that \(\{\alpha_n\}_{n=1}^{\infty}\) converges to \(\alpha\) with an order of convergence \(O(\beta_n)\), written as \(\alpha_n = \alpha + O(\beta_n)\).

Suppose a sequence \(x_{n}\) converges to \(l\). Then it is said to have order of convergence \(q \geq 1\) and rate of convergence \(\mu\) if \[ \lim_{n \to \infty} \frac{|x_{n+1} - l|}{|x_{n} - l| ^{q}} = \mu \] for some positive constant \(\mu\) if \(q > 1\) and \(\mu \in (0, 1)\) if \(q = 1\).

Suppose \(f\) is defined and continuous on \([a, b]\) with \(f(a)\) and \(f(b)\) of opposite signs, and (for simplicity) the zero of \(f\) is unique in this interval. To find the zero \(p\) of \(f\) in \([a, b]\), the Bisection method generates a sequence \(p_{n}\) as follows:

1. Initialize \(a_1 = a\) and \(b_1 = b\).
2. For all \(i \geq 1\): Let \[ p_i = a_i + \frac{{b_i - a_i}}{2} = \frac{{a_i + b_i}}{2}. \]
   • (*) If \(f(p_i) = 0\), then \(p = p_i\), and we are done.
   • If \(f(p_i) \cdot f(a_i) < 0\), then \(p \in (p_i, b_i)\), set \(a_{i+1} = p_i\) and \(b_{i+1} = b_i\).
   • If \(f(p_i) \cdot f(a_i) > 0\), then \(p \in (a_i, p_i)\), set \(a_{i+1} = a_i\) and \(b_{i+1} = p_i\).

Given a function \(g(p)\) on \([a, b]\), a \(p\) satisfying \(g(p) = p\) is called a fixed point of \(g\).

Given an initial approximation \(p_0\), the Newton’s generates a sequence \[ p_{n} = p_{n-1} - \frac{f(p_{n-1})}{f'(p_{n-1})}. \]

Given two approximations \(p_0\) and \(p_1\), the Secant Method generates a sequence \[ p_{n} = p_{n-1} - f(p_{n-1})\frac{(p_{n-1} - p_{n-2})}{f(p_{n-1}) - f(p_{n-2})}. \] Geometrically, \(p_n\) is the \(x\)-intercept of the line joining \((p_{n-1}, f(p_{n-1}))\) and \((p_{n-2}, f(p_{n-2}))\).

Given a function \(f\) on the interval \([p_0, p_1]\) where \(f(p_0) \cdot f(p_1) < 0\), the Method of Falsi Position generates a sequence as follows:

• Let \(a = p_0, b = p_1\)
• For any \(n > 1\), compute \(p_{n} = p_{n-1} - \frac{f(b)(b - a)}{f(b) - f(a)}\).
  • If \(f(p_{n}) \cdot f(b) < 0\), then \(p_{n}\) and \(b\) bracket the zero. Update \(a = b\) and \(b = p_{n}\).
  • If \(f(p_{n}) \cdot f(b) > 0\), then \(p_{n}\) and \(a\) bracket the zero. Update \(b = p_{n}\).

In this case, the zero always lies between \(a\) and \(b\) in each step.

Suppose \(x_0, x_1, \ldots, x_n\) are \(n+1\) distinct numbers, and \(f\) is a function whose values are given at these numbers. Then there exists a unique polynomial \(P_{n}(x)\) of degree at most \(n\) with \[f(x_k) = P_{n}(x_k), \text{ for each } k = 0, 1, \ldots, n.\] \(P_{n}(x)\) is given by the Lagrange polynomial for \(f\), defined as: \[P_{n}(x) = f(x_0)L_{n,0}(x) + \ldots + f(x_n)L_{n,n}(x) = \sum_{k=0}^{n} f(x_k)L_{n,k}(x),\] where \(L_{n,k}(x)\) is defined as \[ L_{n,k}(x) = \frac{(x - x_0)\ldots(x - x_{k-1})(x - x_{k+1})\ldots(x - x_n)}{(x_k - x_0)\ldots(x_k - x_{k-1})(x_k - x_{k+1})\ldots(x_k - x_n)} = \prod_{i=0, i \neq k}^{n} \frac{x-x_{i}}{x_{k}-x_{i}}. \]

Let \(f\) be a function and \(x_0, x_1, \dots , x_{n}\) be distinct numbers. The divided differences of \(f\) are recursively defined as follows:

• The zeroth divided difference of \(f\) at each \(x_{i}\) is \(f[x_{i}] = f(x_{i})\).
• For \(1 \leq k \leq n\), the \(k\)-th divided difference w.r.t. \(x_{i}, x_{i+1}, \dots , x_{i+k}\) for \(0 \leq i \leq n-k\) is \[ f[x_{i}, \dots , x_{i+k}] = \frac{f[x_{i+1}, \dots , x_{i+k}] - f[x_{i}, \dots , x_{i+k-1}]}{x_{i+k} - x_{i}}. \]

The \(n\)-th order Newton’s Divided Difference interpolating polynomial of \(f\) is defined as \[ P_{n}(x) = f[x_0] + \sum_{k=1}^{n} f[x_0, x_1, \dots , x_{k}] (x-x_0) \cdots (x- x_{k-1}). \]

Suppose \(f(t) \in C ^2[a, b]\). Given the initial value problem, and a step size \(h = (b-a) / N\), the Euler’s method constructs \(w_{i} \approx y(t_{i}), t_{i} = a + i h\) for \(i = 0, 1, \dots , N-1\) as follows:

This equation is called the difference equation associated with Euler’s method.

1. At the \(k\)-th step, provided \(a_{kk} \neq 0\), we eliminate the coefficient of \(x_{k}\) in rows after the \(k\)-th row: \[ E_{j} \gets E_{j} - \frac{a_{i,k}}{a_{k,k}} E_{i}, \forall j = k + 1, k + 2, \dots , n. \]
2. Use backward substitution to solve the \(i\)-th equation for \(x_{k}\), for \(k = n, n-1, n-2, \dots \). This requires that \(a_{nn} \neq 0\) (at ).

(P.S.: the coefficients / equations always refer to the updated ones.)

At the \(k\)-th step, select the element with the largest absolute value in the \(k\)-th column below the \(k\)-th row as the pivot: \[ E_{k} \leftrightarrow E_{p}, p = \argmax _{k \leq i \leq n} |a_{i,k} ^{(k-1)}|. \]

Compute the scale factor (only once at the start) \(s_{i} = \max_{1 \leq j \leq n} |a_{ij}|\) for each row. Assume \(s_{i} \neq 0\) for all rows. Then, at the \(k\)-th step, select the element with the largest scaled absolute value in the \(k\)-th column below the \(k\)-th row as the pivot: \[ E_{k} \leftrightarrow E_{p}, p = \argmax_{k \leq i \leq n} \frac{|a_{i,k} ^{(k-1)}|}{s_{i}}. \] P.S.: Though scale factors have been computed, they have to be interchanged with the row.

\(\mat{A} = \mat{L} \mat{U}\), where \(\mat{L}\) is lower triangular and \(\mat{U}\) is upper triangular, is called the LU factorization.

Let \(\pi_{1}, \dots \pi_{n}\) be a permutation of the numbers \(1, \dots , n\). Then the corresonding permutation matrix is obtained by rearranging the rows of identity matrix according to \(\pi\), i.e., \(\mat{P} = [\vec{e}_{\pi_{1}} \dots \vec{e}_{\pi_{n}}] ^{T}\). \(\mat{P} \mat{A}\) has the effect of rearranging the rows of \(\mat{A}\) according to \(\pi\).

A square matrix \(\mat{A}\) is convergent if \(\lim_{k \to \infty} (\mat{A} ^{k})_{i,j} = 0\) for all \(i, j\).

A square matrix \(\mat{A}\) is strictly diagonally dominant if \[|a_{ii} > \sum_{j \neq i} |a_{i,j}|.\]