Rayleigh quotient
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\newcommand{\trans}{^\top} \newcommand{\adj}{^{\rm adj}} \newcommand{\cof}{^{\rm cof}} \newcommand{\inp}[2]{\left\langle#1,#2\right\rangle} \newcommand{\dunion}{\mathbin{\dot\cup}} \newcommand{\bzero}{\mathbf{0}} \newcommand{\bone}{\mathbf{1}} \newcommand{\ba}{\mathbf{a}} \newcommand{\bb}{\mathbf{b}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bd}{\mathbf{d}} \newcommand{\be}{\mathbf{e}} \newcommand{\bh}{\mathbf{h}} \newcommand{\bp}{\mathbf{p}} \newcommand{\bq}{\mathbf{q}} \newcommand{\br}{\mathbf{r}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\bu}{\mathbf{u}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bw}{\mathbf{w}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\nul}{\operatorname{null}} \newcommand{\rank}{\operatorname{rank}} %\newcommand{\ker}{\operatorname{ker}} \newcommand{\range}{\operatorname{range}} \newcommand{\Col}{\operatorname{Col}} \newcommand{\Row}{\operatorname{Row}} \newcommand{\spec}{\operatorname{spec}} \newcommand{\vspan}{\operatorname{span}} \newcommand{\Vol}{\operatorname{Vol}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\idmap}{\operatorname{id}} \newcommand{\am}{\operatorname{am}} \newcommand{\gm}{\operatorname{gm}} \newcommand{\mult}{\operatorname{mult}} \newcommand{\iner}{\operatorname{iner}}$
from lingeo import random_int_list
Let $A$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$.
According to the spectral theorem, there is an orthonormal basis $\beta = \{\bv_1, \ldots, \bv_n\}$ corresponding to $\lambda_1,\ldots,\lambda_n$.
Let $\bv$ be a vector in $\mathbb{R}^n$.
Then we have the following properties:
With these property in mind, one may solve the optimization problem:
minimize $\bx\trans A\bx$,
subject to $\|\bx\| = 1$.
The minimum value is $\lambda_1$ and is achieved by $\bx = \bv_1$ (or other vector in the same eigenspace).
Similarly, if the problem is asking for an maximum value,
then the maximum value is $\lambda_n$ and is achieved by $\bx = \bv_n$.
Let $A$ be an $n\times n$ real symmetric matrix.
The Rayleigh quotient of $A$ is a function of the form
Let $A$ be an $n\times n$ real symmetric matrix. Then
$$ \begin{aligned} \lambda_1 &= \min_{ \substack{\bx\in\mathbb{R}^n \\ \bx\neq\bzero} } R_A(\bx) = \min_{ \substack{\bx\in\mathbb{R}^n \\ \|\bx\| = 1} } \bx\trans A\bx, \\ \lambda_n &= \max_{ \substack{\bx\in\mathbb{R}^n \\ \bx\neq\bzero} } R_A(\bx) = \max_{ \substack{\bx\in\mathbb{R}^n \\ \|\bx\| = 1} } \bx\trans A\bx. \end{aligned} $$The minimum is achieved by an eigenvector of $\lambda_1$, while the maximum is achieved by an eigenvector of $\lambda_n$.
Moreover, if one already know $\lambda_1$ and $\bv_1$, then
$$ \lambda_2 = \min_{ \substack{\bx\in\mathbb{R}^n \\ \bx\neq\bzero,\ \bx\perp\bv_1} } R_A(\bx) = \min_{ \substack{\bx\in\mathbb{R}^n \\ \|\bx\| = 1,\ \bx\perp\bv_1} } \bx\trans A\bx. $$The vector $\bv_{n-1}$ can be done in a similar way if $\lambda_n$ and $\bv_n$ is known.
執行以下程式碼。
Run the code below.### code
set_random_seed(0)
print_ans = False
n = 3
eigs = random_int_list(n)
A = diagonal_matrix(eigs)
pretty_print(LatexExpr("A ="), A)
if print_ans:
xAx = " + ".join("x_%s^2 (%s)"%(i+1, eigs[i]) for i in range(n))
print("xT A x =", xAx)
print("max value:", max(eigs))
print("achieved by:", identity_matrix(n)[max(list(range(n)), key=lambda k: eigs[k])])
print("min value:", min(eigs))
print("achieved by:", identity_matrix(n)[min(list(range(n)), key=lambda k: eigs[k])])
令
$$ \bx = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}. $$計算 $\bx\trans A\bx$。
Let $$ \bx = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}. $$ Find $\bx\trans A\bx$.求 $\bx\trans A\bx$ 在 $\|\bx\| = 1$ 限制下的最大值。
達成這個最大值的 $\bx$ 為何?
求 $\bx\trans A\bx$ 在 $\|\bx\| = 1$ 限制下的最小值。
達成這個最小值的 $\bx$ 為何?
令 $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ 為一 $n\times n$ 實對稱矩陣,且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。
Let $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$.證明對所有 $i = 1,\ldots,n$ 都有 $\lambda_1 \leq a_{ii} \leq \lambda_n$。
提示:找一個適合的向量 $\bx$ 來套用 $\lambda_1 \leq R_A(\bx) \leq \lambda_n$。
Show that $\lambda_1 \leq a_{ii} \leq \lambda_n$ for each $i = 1,\ldots,n$. Hint: Find an appropriate vector $\bx$ for the inequality $\lambda_1 \leq R_A(\bx) \leq \lambda_n$.令
$$ A = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}. $$說明 $A$ 的最大特徵值 $\lambda_3 \geq 2$。
Let $$ A = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}. $$ Show that the maximum eigenvalue of $A$ has $\lambda_3 \geq 2$.令 $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ 為一 $n\times n$ 實對稱矩陣,且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。
Let $A = \begin{bmatrix} a_{ii} \end{bmatrix}$ be an $n\times n$ real symmetric matrix with eigenvalues $\lambda_1 \leq \cdots \leq \lambda_n$.證明 $\lambda_1 \leq \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} \leq \lambda_n$。
Show that $\lambda_1 \leq \frac{1}{n} \sum_{i=1}^n\sum_{j=1}^n a_{ij} \leq \lambda_n$.令
$$ A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}. $$說明 $A$ 的最大特徵值 $\lambda_3 \geq \frac{4}{3}$。
Let $$ A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}. $$ Show that the maximum eigenvalue of $A$ has $\lambda_3 \geq \frac{4}{3}$.令 $A$ 為一 $n\times n$ 實對稱矩陣,且其特徵值為 $\lambda_1 \leq \cdots \leq \lambda_n$。
令 $B$ 為 $A$ 刪掉第一行第一列的矩陣,而其特徵值為 $\mu_1 \leq \cdots \leq \mu_{n-1}$。
證明 $\lambda_1 \leq \mu_1$ 且 $\mu_{n-1} \leq \lambda_n$。
令
$$ A = \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}. $$解以下極值問題:
maximize $\bx\trans A \bx$,
subject to $\|\bx\| = 1$.
已知
$$ A_n = \begin{bmatrix} 0 & 1 & ~ & 0 \\ 1 & 0 & \ddots & ~ \\ ~ & \ddots & \ddots & 1 \\ 0 & ~ & 1 & 0 \end{bmatrix} $$的所有特徵值為 $\{2\cos(\frac{2k\pi}{n+1}): k = 1,\ldots, n\}$。
求在 $x_1^2 + \cdots + x_n^2 = 1$ 的限制下,
$x_1x_2 + x_2x_3 + \cdots + x_{n-1}x_n$ 的最大值為何。
令
$$ L = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}. $$解以下極值問題:
minimize $\bx\trans L \bx$,
subject to $\|\bx\| = 1$ and $\bx = \bone$.
這裡 $\bone$ 為全一向量。
Let $$ L = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}. $$ Solve the optimization problem: minimize $\bx\trans L \bx$, subject to $\|\bx\| = 1$ and $\bx = \bone$.查找各種資源,並描述柯朗–費雪定理(Courant–Fischer Theorem)。
Use any resource you prefer, state the Courant–Fischer Theorem.