|
|
这里有一个资源: Numerical Analysis 2021
讲义 和一些题目:sheet 1
尝试做了一些, 还差第8,9,11,12题没有做, 等到有空闲时间再研究一下(欢迎跟帖 )
紫色是抄录的题干.
- Construct the Lagrange interpolating polynomial for the data
\[3·\frac{(x-1)(x-3)}{(0-1)(0-3)}+2·\frac{(x-0)(x-3)}{(1-0)(1-3)}+6·\frac{(x-0)(x-1)}{(3-0)(3-1)}=x^2-2x+3\]
- If $p_n∈\Pi_n$ interpolates $f$ at $x_0, x_1,…, x_n$, prove that $p_n+q$ is the Lagrange interpolating polynomial to $f+q$ at $x_0, x_1,…, x_n$ whenever $q∈\Pi_n$.
Since $p_n∈\Pi_n$ interpolates $f$ at $x_0, x_1,…, x_n$, we have $p_n(x_i)=f(x_i)$ for $i=0,1,…,n$, so $p_n(x_i)+q(x_i)=f(x_i)+q(x_i)$.
Since $p_n,q∈\Pi_n$, we have $p_n+q∈\Pi_n$. By uniqueness of interpolating polynomial, we conclude that $p_n+q$ is the interpolating polynomial to $f+q$ at $x_0, x_1,…, x_n$.
- Consider interpolating $1/x$ by $p_n∈\Pi_n$ (i.e. at $n+1$ points) on $[1,2]$. If $e(x)$ is the error, show that ${|e(x)|}≤1$ for $x∈[1,2]$ with arbitrarily distributed points, but ${|e(x)|}≤1/2^{(n+1)/2}$ for all $x∈[1,2]$ if $n+1$ is even and half of the interpolation points are in $\left[1, \frac32\right]$ and half in $\left(\frac32, 2\right]$. In this latter situation, how many points would be needed to guarantee ${|e(x)|}≤10^{-3}$ ?
$\left|f^{(n+1)}(ξ)\right|=(n+1)!/ξ^{n+2}<(n+1)!$ for $ξ∈[1,2]$. So ${|e(x)|}<{|π(x)|}(n+1)!/(n+1)!≤1$ since ${|π(x)|}≤1$.
Let $x_0,⋯,x_{(n-1)/2}$ be in $\left[1, \frac32\right]$ and $x_{(n+1)/2},⋯,x_n$ in $\left(\frac32, 2\right]$. For $x∈\left[1, \frac32\right]$ we have ${|x-x_0|},⋯,{|x-x_{(n-1)/2}|}<\frac12$ and ${|x-x_{(n+1)/2}|},⋯,{|x-x_n|}< 1$, so ${|π(x)|}< 1/2^{(n+1)/2}$; for $x∈\left[\frac32,2\right]$ we have ${|x-x_0|},⋯,{|x-x_{(n-1)/2}|}< 1$ and ${|x-x_{(n+1)/2}|},⋯,{|x-x_n|}<\frac12$, so ${|π(x)|}< 1/2^{(n+1)/2}$. In both cases ${|e(x)|}<{|π(x)|}≤1/2^{(n+1)/2}$.
How many points needed? Let $2^{(n+1)/2}>10^3$ we have $n+1>6\log_210≈19.9$, so $n≥19$.
- Show that $\sum_{k=0}^n q\left(x_k\right) L_{n, k}(x)=q(x)$ whenever $q∈\Pi_n$. Also, show that $\sum_{k=0}^n x_k^l L_{n, k}(x)=x^l$ for nonnegative integers $l≤n$.
Since $q∈\Pi_n$ and the value of $q$ at $x_k$ is $q(x_k)$, by uniqueness of interpolating polynomial, $\sum_{k=0}^n q\left(x_k\right) L_{n, k}(x)=q(x)$.
Let $q\left(x\right)=x^l\,(l≤n)$ we get $\sum_{k=0}^n x_k^l L_{n, k}(x)=x^l$.
-
By performing Gauss Elimination (without pivoting), solve
\[\begin{bmatrix}
2&1&1&0\\
4 & 3 & 3 & 1 \\
8 & 7 & 9 & 5 \\
6 & 7 & 9 & 8
\end{bmatrix}\begin{bmatrix}
a \\
b \\
c \\
d
\end{bmatrix}=\begin{bmatrix}
3 \\
8 \\
24 \\
25
\end{bmatrix}
\]
From your calculations, write down an LU factorisation of the matrix $A$ above, and verify that $L U=A$. Then by successive back and forwards substitutions (and without further factorisation) solve $A x=b_2$ where $b_2=[4\;7\;9\;2]^{\sf T}$.
|
R2 = R2 − 2R1
\begin{bmatrix}2&1&1&0\\
0&1&1&1\\
8&7&9&5\\
6&7&9&8\end{bmatrix}
|
R3 = R3 − 4R1
\begin{bmatrix}2&1&1&0\\
0&1&1&1\\
0&3&5&5\\
6&7&9&8\end{bmatrix}
|
R4 = R4 − 3R1
\begin{bmatrix}2&1&1&0\\
0&1&1&1\\
0&3&5&5\\
0&4&6&8\end{bmatrix}
|
|
R3 = R3 − 3R2
\begin{bmatrix}2&1&1&0\\
0&1&1&1\\
0&0&2&2\\
0&4&6&8\end{bmatrix}
|
R4 = R4 − 4R2
\begin{bmatrix}2&1&1&0\\
0&1&1&1\\
0&0&2&2\\
0&0&2&4\end{bmatrix}
|
R4 = R4 − R3
\[U=\begin{bmatrix}2&1&1&0\\
0&1&1&1\\
0&0&2&2\\
0&0&0&2\end{bmatrix}\]
|
\[L=\begin{bmatrix}
1&0&0&0\\
2&1&0&0\\
4&3&1&0\\
3&4&1&1
\end{bmatrix}\]
Solving $Ly=b$ (forward substitution)
\begin{array}l
y_1=4\\
y_2=7-2y_1=-1\\
y_3=9-4y_1-3y_2=-4\\
y_4=2-3y_1-4y_2-y_3=-2
\end{array}
Solving $Ux=y$ (back substitution)
\begin{array}l
x_4=y_4/2=-1\\
x_3=(y_3-2x_4)/2=-1\\
x_2=y_2-x_3-x_4=1\\
x_1=(y_1-x_2-x_3)/2=2
\end{array}
- What is the determinant of the matrix $A$ in the question above?
(The determinant of a triangular matrix is the product of diagonal elements) $\det(L)=1,\det(U)=8⇒\det(A)=\det(LU)=\det(L)\det(U)=8$.
-
Suppose $A$ is a real $n×n$ matrix with $n≥2$ and that the permutation matrix
\[P=\begin{bmatrix}
0 & \cdots & 0 & 1 \\
0 & \cdots & 1 & 0 \\
\vdots & \cdots & \vdots & \vdots \\
1 & \cdots & 0 & 0
\end{bmatrix}\]
Show that premultiplication of $A$ by $P$ reverses the order of the rows of $A$.
If $A=LU$ is an LU factorisation of $A$ (without pivoting), what is the structure of $PLP$ ? Hence describe how to calculate a factorisation $A=\hat{U} \hat{L}$ where $\hat{U}$ is unit upper triangular and $\hat{L}$ is lower triangular.
All entries in row $i$ of $P$ are zero, except $P_{i,n-i+1}=1$.
$$(PA)_{ij}=P_{i,n-i+1}A_{n-i+1,j}=A_{n-i+1,j}$$
So $PA$ has the same rows of $A$ with reversed order.
$L$ is lower triangular. We reverse order of rows and columns of $L$ to get $PLP$, so $PLP$ is upper triangular.
$PAP=L_1U_1$ is an LU factorisation of $PAP$ then $\hat{U}=PL_1P,\hat{L}=PU_1P$.
-
Suppose that $A$ is a square nonsingular matrix. Prove that the factors $Q$ and $R$ featuring in the QR factorisation of $A$ are unique if the diagonal entries of $R$ are all positive. How many possibilities are there if this restriction is removed?
-
By considering the QR factorisation in which the diagonal entries of $R$ are all positive as in the question above (or otherwise), prove that any orthogonal matrix may be expressed as the product of Householder matrices.
-
1) Prove that the product of two lower triangular matrices is lower triangular.
2) Prove that the inverse of a non-singular lower triangular matrix is lower triangular.
3) Deduce similar results for upper triangular matrices.
1) Let $A,B$ be $n×n$ lower triangular matrices. For any $1≤j< i≤n$, if $k≤i$ we have $k< j$, so $B_{kj}=0$; if $k>i$ we have $A_{ik}=0$.
\[(AB)_{ij}=\sum_{k=1}^iA_{ik}B_{kj}+\sum_{k=i+1}^nA_{ik}B_{kj}=0+0=0\]
Therefore $AB$ is lower triangular.
2) To compute $A^{-1}$, using elementary row operation sequence, transform the augmented matrix $(A¦I)$ to $(I¦A^{-1})$.
If $A$ is lower triangular, the sequence of elementary row operations include
i) multiplying a row by a factor
ii) subtracting a multiple of row $i$ from row $j$ ($j< i$).
Starting from $I$, the right portion is lower triangular after each operation, so $A^{-1}$ is lower triangular.
3) The transpose of an upper triangular matrix is a lower triangular matrix and use the identities $(AB)^{\sf T}=B^{\sf T}A^{\sf T},(A^{-1})^{\sf T}=(A^{\sf T})^{-1}$.
-
(matlab) Using a loop and tic and toc compare the time it takes to do (pivoted) LU and QR factorisations. For example, for random matrices of dimension $2^5$ to $2^{10}$
for k=5:10, A=randn(2^k); tic, [L,U,P]=lu(A); toc,...
tic, [Q,R]=qr(A); toc, end
should give some timings. What do you think the computational work is for QR factorisation given that LU is to leading order $\frac{2}{3} n^3$? Note qr uses Householder matrices as described in lectures to compute the QR factorisation.
-
Given an LU factorisation of a matrix $A$, how might one calculate a column of the inverse of $A$? Estimate the computational work in calculating $A^{-1}$ and hence in solving $A x=b$ via explicit computation of $A^{-1}$ and multiplication by $b$.
Are you now convinced that this is not the way to solve linear systems of equations in practice?!
An even worse technique would be to apply GE separately for each column: what would the computational cost be then?
|
|
