Skip to main content
Contents Dark Mode Prev Up Next \(\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\dimens}{\operatorname{dim}}
\DeclareMathOperator{\row}{\operatorname{row}}
\DeclareMathOperator{\col}{\operatorname{col}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\nulls}{\operatorname{null}}
\newcommand{\minor}{\operatorname{minor}}
\newcommand{\spans}{\operatorname{span}}
\newcommand{\nullity}{\operatorname{nullity}}
\newcommand{\kers}{\operatorname{ker}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\Tr}{\operatorname{Tr}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 7.4 Applications and computation recap
This section checks whether you can read the computations behind the polynomial synthesis. The goal is interpretation, not writing long programs.
Computation question. When code builds a feature matrix and checks a residual, which approximation problem is it solving?
The main code pattern is the same as in Unit 4. A design matrix stores feature columns. A coefficient vector stores the weights on those features. The product \(A\mathbf c\) stores fitted values. The residual
\begin{equation*}
\mathbf r=\mathbf y-A\mathbf c
\end{equation*}
stores errors at sampled points. The check
\begin{equation*}
A^T\mathbf r\approx\mathbf0
\end{equation*}
checks residual orthogonality.
Table 7.4.1. Reading short computations
np.column_stack([1, x])What are the feature columns?
design matrix for an affine fit
np.linalg.lstsq(A, y, rcond=None)[0]What coefficients are being fitted?
least-squares coefficient vector
A @ cWhat does each row of
\(A\) represent?
y - A @ cWhat was observed or sampled?
A.T @ rWhich feature columns should be orthogonal to
\(r\text{?}\)
residual-orthogonality check
np.column_stack([1, x, x**2])Which polynomial subspace is used?
np.meshgridWhat sample grid is being built?
two-variable sampled points
h @ H @ hWhat vector and Hessian are used?
Activity 7.4.1 . Checkpoint: feature matrix for an affine fit.
import numpy as np
xs = np.array([-1.0, -0.5, 0.0, 0.5, 1.0])
A = np.column_stack([np.ones_like(xs), xs])
A.shape, A
How many rows does
\(A\) have?
How many columns does
\(A\) have?
What does the first column represent?
What does the second column represent?
What polynomial subspace is represented by the columns?
Solution .
The matrix \(A\) has five rows, one for each sample point. It has two columns. The first column is the sampled constant feature \(1\text{.}\) The second column is the sampled \(x\) -feature. Together the columns represent the approximation subspace
\begin{equation*}
\mathcal P_{\le1}=\operatorname{span}\{1,x\}.
\end{equation*}
A coefficient vector
\begin{equation*}
\mathbf c=
\begin{bmatrix}
c_0\\
c_1
\end{bmatrix}
\end{equation*}
produces fitted values for
\begin{equation*}
q(x)=c_0+c_1x.
\end{equation*}
Activity 7.4.2 . Checkpoint: sampled least squares and residual orthogonality.
y = 1 + 2*xs + xs**2 + xs**3
c = np.linalg.lstsq(A, y, rcond=None)[0]
r = y - A @ c
c, A.T @ r
Suppose the output is approximately
(array([1.5 , 2.85]), array([0., 0.]))
What line does the coefficient vector represent?
What does
\(A\mathbf c\) store?
What does
\(\mathbf r\) store?
Does
A.T @ r being close to zero mean
\(\mathbf r=\mathbf0\text{?}\)
Solution .
The coefficient vector
\begin{equation*}
\mathbf c\approx
\begin{bmatrix}
1.5\\
2.85
\end{bmatrix}
=
\begin{bmatrix}
\frac32\\
\frac{57}{20}
\end{bmatrix}
\end{equation*}
represents the sampled least-squares line
\begin{equation*}
q_{\mathrm{sample}}(x)=\frac32+\frac{57}{20}x.
\end{equation*}
The vector \(A\mathbf c\) stores the fitted values
\begin{equation*}
q_{\mathrm{sample}}(x_i)
\end{equation*}
at the sampled points. The residual vector
\begin{equation*}
\mathbf r=\mathbf y-A\mathbf c
\end{equation*}
stores the sampled errors
\begin{equation*}
r_i=p(x_i)-q_{\mathrm{sample}}(x_i).
\end{equation*}
The computation A.T @ r checks whether the residual is orthogonal to the sampled constant feature and the sampled \(x\) -feature:
\begin{equation*}
\sum_i r_i=0,
\qquad
\sum_i x_ir_i=0.
\end{equation*}
It does not mean \(\mathbf r=\mathbf0\text{.}\) It means the residual is orthogonal to the approximation subspace.
Activity 7.4.3 . Checkpoint: three coefficient vectors.
c_taylor = np.array([1.0, 2.0])
c_continuous = np.array([4/3, 13/5])
c_sampled = np.array([3/2, 57/20])
c_taylor, c_continuous, c_sampled
Which vector represents the Taylor line at
\(0\text{?}\)
Which vector represents the continuous
\(L^2[-1,1]\) -least-squares line?
Which vector represents the sampled least-squares line from the five sample points?
Which approximation is local?
Which approximations depend on an interval or sampled points?
Solution .
The vector
\begin{equation*}
\begin{bmatrix}
1\\
2
\end{bmatrix}
\end{equation*}
represents the Taylor line
\begin{equation*}
T(x)=1+2x.
\end{equation*}
The vector
\begin{equation*}
\begin{bmatrix}
4/3\\
13/5
\end{bmatrix}
\end{equation*}
represents the continuous least-squares line
\begin{equation*}
q_{L^2}(x)=\frac43+\frac{13}{5}x.
\end{equation*}
The vector
\begin{equation*}
\begin{bmatrix}
3/2\\
57/20
\end{bmatrix}
\end{equation*}
represents the sampled least-squares line
\begin{equation*}
q_{\mathrm{sample}}(x)=\frac32+\frac{57}{20}x.
\end{equation*}
The Taylor line is local because it uses value and derivative data at one point. The continuous least-squares line depends on the interval \([-1,1]\text{.}\) The sampled least-squares line depends on the chosen sample points.
Activity 7.4.4 . Checkpoint: shrinking interval coefficients.
ts = np.array([1.0, 0.5, 0.25, 0.125])
x2_const = ts**2 / 3
x3_slope = 3*ts**2 / 5
x2_const, x3_slope
What polynomial does
x2_const come from?
What polynomial does
x3_slope come from?
What happens to both arrays as
\(t\to0\text{?}\)
How does this connect to Taylor approximation?
Solution .
The array x2_const contains the constants in the \(L^2[-t,t]\) -projection
\begin{equation*}
P_t(x^2)=\frac{t^2}{3}
\end{equation*}
onto \(\operatorname{span}\{1,x\}\text{.}\) The array x3_slope contains the slopes in the projection
\begin{equation*}
P_t(x^3)=\frac{3t^2}{5}x.
\end{equation*}
Both arrays tend to zero as \(t\to0\text{.}\) This matches the Taylor linear approximations of \(x^2\) and \(x^3\) at \(0\text{,}\) both of which are zero. The code is reading the limiting local least-squares idea from the previous section.
Activity 7.4.5 . Checkpoint: quadratic feature matrix.
A2 = np.column_stack([np.ones_like(xs), xs, xs**2])
c2 = np.linalg.lstsq(A2, y, rcond=None)[0]
fit2 = A2 @ c2
r2 = y - fit2
A2.shape, c2, A2.T @ r2
What polynomial subspace is represented by the columns of
\(A2\text{?}\)
What does
\(fit2\) store?
What does
A2.T @ r2 check?
Why are there three entries in
A2.T @ r2?
Solution .
The columns of \(A2\) represent
\begin{equation*}
\operatorname{span}\{1,x,x^2\}=\mathcal P_{\le2}
\end{equation*}
sampled at the points in xs. The vector \(c2\) stores the coefficients of the sampled least-squares quadratic
\begin{equation*}
c_0+c_1x+c_2x^2.
\end{equation*}
The vector fit2 stores the fitted values at the sample points. The vector r2 stores sampled residuals. The computation A2.T @ r2 checks that the residual is orthogonal to each sampled feature column:
\begin{equation*}
\sum_i r_i=0,
\qquad
\sum_i x_ir_i=0,
\qquad
\sum_i x_i^2r_i=0.
\end{equation*}
There are three entries because the approximation subspace has three feature columns.
Activity 7.4.6 . Checkpoint: sampled best-fit plane in code.
grid = np.linspace(-1, 1, 5)
X, Y = np.meshgrid(grid, grid)
xx = X.ravel()
yy = Y.ravel()
z = 1 + 2*xx - yy + xx**2 + xx*yy + 2*yy**2 + xx**3
A = np.column_stack([np.ones_like(xx), xx, yy])
c = np.linalg.lstsq(A, z, rcond=None)[0]
r = z - A @ c
c, A.T @ r
Suppose the output is approximately
(array([ 2.5 , 2.85, -1. ]), array([0., 0., 0.]))
How many sampled points are used?
What do the three columns of
\(A\) represent?
What plane does the coefficient vector represent?
What does
\(A^T\mathbf r\approx\mathbf0\) check?
How is this the two-variable version of sampled line fitting?
Solution .
The grid has \(5\cdot5=25\) sampled points. The three columns of \(A\) are the sampled constant feature, the sampled \(x\) -feature, and the sampled \(y\) -feature. The coefficient vector represents the sampled best-fit plane
\begin{equation*}
q_{\mathrm{sample}}(x,y)=\frac52+\frac{57}{20}x-y.
\end{equation*}
The check \(A^T\mathbf r\approx\mathbf0\) means
\begin{equation*}
\sum_i r_i=0,
\qquad
\sum_i x_ir_i=0,
\qquad
\sum_i y_ir_i=0.
\end{equation*}
This is the same residual-orthogonality condition as sampled line fitting, but now the approximation subspace is
\begin{equation*}
\operatorname{span}\{1,x,y\}.
\end{equation*}
Activity 7.4.7 . Checkpoint: Hessian quadratic form in code.
H = np.array([
[2.0, 1.0],
[1.0, 4.0],
])
h = np.array([1.0, -1.0])
0.5 * h @ H @ h
Exam skill. Given a short Unit 7 code snippet, identify the vector space, the approximation subspace, the feature columns, the coefficient vector, the fitted values, the residual, and the residual-orthogonality check.
Tags. [U7-LO3, U7-LO4, U7-LO5, U7-LO6, U7-LO7 | C+M+T | Core]
Linked notebook. Run
Lab U7: Polynomial Approximation . Use it to compare Taylor, continuous least-squares, and sampled least-squares approximations, and to practice reading feature matrices, least-squares coefficients, fitted values, and residual checks.
For a quick reference on arrays, sample grids, design matrices, matrix products, transposes, least squares, and numerical checks, see the programming appendix sections
B.2 ,
B.4 ,
B.8 ,
B.9 , and
B.10 .
