Introdunction to Linear Algebra-第10章-Applications
[TOC]
《Introdunction to Linear Algebra》的第10章： Applications.
10.1 Graphs and Networks
略过.
10.2 Matrices in Engineering
有弹簧力学系统来举例动力学方程的线性代数表达:
代号表述:
$u(u_1,u_2, u_3)$ = movements of the masses (down is positive)
$y(y_1,y_2, y_3,y_4)$ or $(y_1,y_2,y_3) =$ tensions in the springs
延伸:
$u$ Movements of $n$ masses $(u_1,…, u_n)$
$e$ Elongations of $m$ springs $(e_1,···,e_m)$
$y$ Internal forces in $m$ springs $(y_1,· · ·,y_m)$
$f$ External forces on $n$ masses $(f_i, …,f_n )$
A great framework for applied mathematics connects $u$ to $e$ to $y$ to $f$. Then $A^T C Au = f$:
- 对于左侧的双固定场景 fixed-fixed boundary:
some properties of $K=A^TCA$
$ K $ is tridiagonal, because mass $3$ is not connected to mass $1$.
$ K $ is symmetric, because $ C $ is symmetric and $ A^{\mathrm{T}} $ comes with $ A $.
$ K $ is positive definite, because $ c_{i}>0 $ and $ A $ has independent columns.
$ K^{-1} $ is a full matrix (not sparse) with all positive entries.
Fixed End and Free End 的场景
$$
\text{ FIXED FREE} \quad
A_{1}^{\mathrm{T}} C_{1} A_{1}=\left[\begin{array}{ccc}c_{1}+c_{2} & -c_{2} & 0 \\ -c_{2} & c_{2}+c_{3} & -c_{3} \\ 0 & -c_{3} & c_{3}\end{array}\right]
$$
- Two Free Ends: K is Singular 两端自由
$$
\begin{array}{l}
\text{ FREE-FREE } \\
\boldsymbol{e} = A \boldsymbol{u}
\end{array}
\left[\begin{array}{l}
e_{1} \\
e_{2}
\end{array}\right]=\left[\begin{array}{l}
u_{2}-u_{1} \\
u_{3}-u_{2}
\end{array}\right]=\left[\begin{array}{rrr}
-1 & 1 & 0 \\
0 & -1 & 1
\end{array}\right]\left[\begin{array}{l}
u_{1} \\
u_{2} \\
u_{3}
\end{array}\right]
$$
$$
A \boldsymbol{u}=\left[\begin{array}{rrr}
-1 & 1 & 0 \\
0 & -1 & 1
\end{array}\right]\left[\begin{array}{l}
1 \\
1 \\
1
\end{array}\right]=\left[\begin{array}{l}
0 \\
0
\end{array}\right]=\text { no stretching }
$$
$$
\left[\begin{array}{rr}
-1 & 0 \\
1 & -1 \\
0 & 1
\end{array}\right]\left[\begin{array}{ll}
c_{2} & \\
& c_{3}
\end{array}\right]\left[\begin{array}{rrr}
-1 & 1 & 0 \\
0 & -1 & 1
\end{array}\right]=\left[\begin{array}{ccc}
c_{2} & -c_{2} & 0 \\
-c_{2} & c_{2}+c_{3} & -c_{3} \\
0 & -c_{3} & c_{3}
\end{array}\right]
$$
- Circle of Springs 环形连接
归纳应用思路:
This is a fundamental example in computational science and engineering.
- Model the problem by a differential equation
- Discretize the differential equation to a difference equation
- Understand and solve the difference equation (and boundary conditions!)
- Interpret the solution; visualize it; redesign if needed.
其中对于第二步有: forward or backward or centered differences 三种离散化的选择:
$$
\frac{d \boldsymbol{u}}{d \boldsymbol{x}} \approx \frac{u(x+\Delta x)-u(x)}{\Delta x} \text { or } \frac{u(x)-u(x-\Delta x)}{\Delta x} \text { or } \frac{u(x+\Delta x)-u(x-\Delta x)}{2 \Delta x}
$$
Between $x = 0$ and $x = 1$, we divide the interval into $n + 1$ equal pieces. The pieces have width $\Delta x = 1/(n + 1)$. The values of $u$ at then breakpoints $\Delta x, 2\Delta x, …$ will be the unknowns $u_1$ to $u_n$ in our matrix equation $Ku = f$.
$$
\text { Solution to compute: } \boldsymbol{u}=\left(u_{1}, u_{2}, \ldots, u_{n}\right) \approx(u(\Delta x), u(2 \Delta x), \ldots, u(n \Delta x))
$$
一般使用 forward and backward differences.
10.3 Markov Matrices, Population, and Economics
Markov Matrices
定义:
- Every entry of $A$ is positive: $a_{ij} > 0$.
- Every column of $A$ adds to 1.
guarantee a stable steady state.
If $ A $ is a positive Markov matrix (entries $ a_{i j}>0 $, each column adds to $1$ ), then $ \lambda_{1}=1 $ is larger than any other eigenvalue. The eigenvector $ \boldsymbol{x}_{1} $ is the steady state:
$$
\boldsymbol{u}_{k}=\boldsymbol{x}_{1}+c_{2}\left(\lambda_{2}\right)^{k} \boldsymbol{x}_{2}+\cdots+c_{n}\left(\lambda_{n}\right)^{k} \boldsymbol{x}_{n} \quad \text{ always approaches } \quad \boldsymbol{u}_{\infty} = \boldsymbol{x}_{1}
$$.
Perron-Frobenius Theorem
Perron-Frobenius for $A>0 $
All numbers in $ A \boldsymbol{x}=\lambda_{\max } \boldsymbol{x} $ are strictly positive.
Linear Algebra in Economics: The Consumption Matrix
Consumption matrix: We have $n$ industries like chemicals, food, and oil. To produce a unit of chemicals may require .2 units of chemicals, .3 units of food, and .4 units of oil.化成矩阵形式 $A$ 如下:
$$
\left[\begin{array}{c}
\text { chemical output } \\
\text { food output } \\
\text { oil output }
\end{array}\right]=\left[\begin{array}{ccc}
.2 & .3 & .4 \\
.4 & .4 & .1 \\
.5 & .1 & .3
\end{array}\right]\left[\begin{array}{c}
\text { chemical input } \\
\text { food input } \\
\text { oil input }
\end{array}\right]
$$
问题是 Can this economy meet demands $y_1 , y_2, y_3$ for chemicals,food, and oil? 用数学描述为:
$$
\textbf { Problem } \text { Find a vector } \boldsymbol{p} \text { such that } \boldsymbol{p}-A \boldsymbol{p}=\boldsymbol{y} \quad \text { or } \quad \boldsymbol{p}=(I-A)^{-1} \boldsymbol{y} \text {. }
$$
when is $(I-A)^{-1}$ a nonnegative matrix?
If $ \lambda_{1}>1 $ then $ (I-A)^{-1} $ has negative entries
If $ \lambda_{1}=1 $ then $ (I-A)^{-1} $ fails to exist
If $ \lambda_{1}<1 $ then $ (I-A)^{-1} $ is nonnegative as desired.
The nice formula for $(I-A)^{-1}$ is the geometric series of matrices:
$$
(I-A)^{-1}=I+A+A^{2}+A^{3}+\cdots
$$
类比于 $\frac{1}{1-x}=1+x+x^2+…$.
答案: it converges if all eigenvalues of $A$ have $|\lambda| < 1$.
10.4 Linear Programming
省略基础的线性规划问题介绍.
The Dual Problem
对于线性规划:$A \boldsymbol{x} = \boldsymbol{b}, \boldsymbol{x} \geq 0, \min : \boldsymbol{c} \boldsymbol{x}$,其对偶问题:$A^T \boldsymbol{y} \leq \boldsymbol{c}, \max : b \boldsymbol{y}$
$$
\text { If } A \boldsymbol{x} = \boldsymbol{b}, \boldsymbol{x} \geq 0, A^{\mathrm{T}} \boldsymbol{y} \leq \boldsymbol{c} \text { then } \boldsymbol{b}^{\mathrm{T}} \boldsymbol{y}=(A \boldsymbol{x})^{\mathrm{T}} \boldsymbol{y} = \boldsymbol{x}^{\mathrm{T}}\left(A^{\mathrm{T}} \boldsymbol{y}\right) \leq \boldsymbol{x}^{\mathrm{T}} \boldsymbol{c}
$$
If either problem has a best vector ($\boldsymbol{x}^{*}$ or $\boldsymbol{y}^{*}$) then so does the other. Minimum cost $ \boldsymbol{c} \cdot \boldsymbol{x}^{*} $ **equals** maximum income $ \boldsymbol{b} \cdot \boldsymbol{y}^{*} $.
Simplex method 单纯形法
参考链接:https://www.hrwhisper.me/introduction-to-simplex-algorithm/
https://blog.csdn.net/jmh1996/article/details/84929974
Interior Point Methods
后面详细学习.
10.5 Fourier Series: Linear Algebra for Functions
本节的研究对象从有限维转变成无限维.
在无限维内积空间(Hilbert spaces)里,我们只研究长度有限的向量以及函数:
$$
\begin{aligned}
& |\boldsymbol{v}|^{2}=\boldsymbol{v} \cdot \boldsymbol{v}=v_{1}^{2}+v_{2}^{2}+v_{3}^{2}+\cdots \quad &\text{ must add to a finite number.} \\
& |f|^{2}=(f, f)=\int_{0}^{2 \pi}|f(x)|^{2} d x \quad & \text{ must be a finite integral.}
\end{aligned}
$$
两个 Hilbert spaces 内的向量的内积仍旧是长度有限的:
Schwarz inequality: $|v· w| \leq ||v|| : ||w||$.
对于两个 Hilbert spaces 内的函数的内积则用积分表达:
DEFINITION The inner product of $ f(x) $ and $ g(x) $, and the length squared of $ f(x) $, are
$$
(f, g)=\int_{0}^{2 \pi} f(x) g(x) d x \text{ and } |f|^{2}=\int_{0}^{2 \pi}(f(x))^{2} d x
$$
Fourier Series
The Fourier series of a function $f ( x)$ is its expansion into sines and cosines:
$$
f(x)=a_{0}+a_{1} \cos x+b_{1} \sin x+a_{2} \cos 2 x+b_{2} \sin 2 x+\cdots
$$
里面的 sines 与 cosines 有如下特点:
任意两个项目的内积都是0,也就是互相 orthogonal,他们是 Hilbert spaces 函数的基.
任意 Hilbert spaces 里的函数的长度均可以表达成如下:
$$
\begin{aligned}
(f, f) &=\int_{0}^{2 \pi}\left(a_{0}+a_{1} \cos x+b_{1} \sin x+a_{2} \cos 2 x+\cdots\right)^{2} d x \\
&=\int_{0}^{2 \pi}\left(a_{0}^{2}+a_{1}^{2} \cos ^{2} x+b_{1}^{2} \sin ^{2} x+a_{2}^{2} \cos ^{2} 2 x+\cdots\right) d x \\
|f|^{2} &=2 \pi a_{0}^{2}+\pi\left(a_{1}^{2}+b_{1}^{2}+a_{2}^{2}+\cdots\right)
\end{aligned}
$$
$$
\text { The derivatives of } r(x)=\frac{x^{\mathrm{T}} S x}{x^{\mathrm{T}} x} \text { are zero when } \quad S x=r(x) x
$$
$$
\text { Function length }=\text { vector length } \quad|F|^{2}=(F, F)=A_{0}^{2}+A_{1}^{2}+B_{1}^{2}+A_{2}^{2}+\cdots
$$
如何计算 Fourier Series 里的各项系数?
$$ \boldsymbol{a}_{\boldsymbol{k}}=\frac{1}{\pi} \int_{0}^{2 \pi} f(x) \cos k x d x \quad \text { and similarly } \quad \boldsymbol{b}_{k}=\frac{1}{\pi} \int_{0}^{2 \pi} f(x) \sin k x d x $$ Infinite-dimensional Hilbert space is very much like then-dimensional space $R^n$. $$ \text { Finite orthogonal series } \quad \boldsymbol{b}=c_{1} \boldsymbol{v}_{1}+c_{2} \boldsymbol{v}_{2}+\cdots+c_{n} \boldsymbol{v}_{n} $$ 对应地: $$ \text { Coefficient } c_{1} \quad \boldsymbol{v}_{1}^{\mathrm{T}} \boldsymbol{b}=c_{1} \boldsymbol{v}_{1}^{\mathrm{T}} \boldsymbol{v}_{1}+0+\cdots+0 . \quad \text { Therefore } c_{1}=\boldsymbol{v}_{1}^{\mathrm{T}} \boldsymbol{b} / \boldsymbol{v}_{1}^{\mathrm{T}} \boldsymbol{v}_{1} $$Introdunction to Linear Algebra-第10章-Applications
https://www.chuxin911.com/Introdunction_to_Linear_Algebra_Chapter10_20220220/