8 - בעיות ערכים עצמיים — אלגוריתמים נומריים

הגדרה 1 (ערך עצמי)

עבור מטריצה ריבועית $A$ בגודל $n\times n$ , הסקלר $\lambda$ יקרא ערך עצמי אם קיים וקטור $\underline{v}$ כך שמתקיים:

A\underline{v}=\lambda \underline{v}

הגדרה 2 (וקטור עצמי)

וקטור $\underline{v}$ לו קיימת $\lambda$ המקיים $A\underline{v}=\lambda \underline{v}$ נקרא וקטור עצמי

משפט

|A|=\prod_{k=1}^n \lambda_{k} \qquad \qquad \mathrm{Tr}(A)=\sum_{k=1}^n \lambda_{k}

דוגמה

נמצא את הע"ע של המטריצה $A=\begin{pmatrix}1 & 2 & 4 \\ 2 & 3 & 2 \\ 4 & 2 & 1\end{pmatrix}$ .

|A-\lambda I|=\begin{vmatrix} 1-\lambda & 2 & 4 \\ 2 & 3-\lambda & 2 \\ 4 & 2 & 1-\lambda \end{vmatrix}=-\lambda^3+5\lambda^2+17\lambda-21=0

זה לא ממש משהו שאנחנו יכולים לפתור סתם ככה.
נשים לב כי סכום כל שורה הוא $7$ ולכן $\begin{pmatrix}1 & 2 & 4\\2 & 3 & 2\\4 & 2 & 1\end{pmatrix}\begin{pmatrix}1\\ 1\\ 1\end{pmatrix}=\begin{pmatrix}7\\7\\7\end{pmatrix}=7\begin{pmatrix}1\\1\\1\end{pmatrix}$ .
לכן, $\lambda=7$ הוא ע"ע ואז:

\frac{-\lambda^3+5\lambda^2+17\lambda-21}{\lambda-7}=-(\lambda-1)(\lambda+3)

נמצא את השאר: $\lambda_{2}=1 \land \lambda_{3}=-3$ .

את הו"ע נמצא ע"י מציאת הפתרונות למשוואה ההומוגנית $(A-\lambda_{3}I)\underline{v}=\underline{0}$ .

משפט (פירוק

Schur

)

אם מטריצה ממשית ולכסינה, אזי היא ניתנת לפירוק שור:

A=QTQ^H

כאשר $Q^H=\overline{Q^t}$ ומתקיים:

$T$ משולשת עליונה (ואולי מרוכבת)
$Q$ אורתונורמלית (ואולי מרוכבת)

הערה

גם אם $A$ סימטרית, $T \neq T^H$ בהכרח.

T=T^H \iff \R{\text{ אלכסונית וממשית}} T

באופן כללי, עבור $A$ סימטרית:

A=A^H \iff \R{\text{ ממשית}}A

משפט

אם $A$ מטריצה ריבועית ממשית וסימטרית אזי:

$A$ לכסינה
כל הע"ע שלה ממשיים
כל הו"ע יכולים להיות ממשיים
ו"ע השייכים לע"ע שונים יהיו אורתוגונוליים.

לכן, לכסון של מטריצה סימטרית יראה כך: $A=QDQ^t$ .
הערה: גם אם קיים לכסון אורתוגונלי הוא לא היחיד וקיימים לכסונים נוספים כמו הרגיל.

משפט

אם $A$ מטריצה ריבועית, ממשית, סימטרית וחיובית מוגדרת, אזי כל הע"ע שלה חיוביים.

משפט

אם $A$ מטריצה ריבועית, ממשית, סימטרית וחיובית חצי מוגדרת, אזי כל הע"ע שלה אי שליליים.

ראינו שע"ע וו"ע יכולים להתקבל כפתרון של בעיית אופטימיזציה.
אם $A$ סימטרית אזי:

\underset{\underline{x}|\;\!\left\lVert \underline{x} \right\rVert_{2}=1 }{\max} \underline{x}^tA\underline{x}=\underset{\underline{x}}{\max} \frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}}=\lambda_{1}

כאשר $\lambda_{1}$ הוא הע"ע הגדול ביותר של $A$ .
באותו האופן:

\underset{\underline{x}|\;\!\left\lVert \underline{x} \right\rVert_{2}=1 }{\min} \underline{x}^tA\underline{x}=\underset{\underline{x}}{\min} \frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}}=\lambda_{n}

כאשר $\lambda_{n}$ הוא הע"ע הקטן ביותר של $A$ .

תרגיל

נתונה מטריצה $A$ בגודל $n\times n$ שאיבריה נתונים לפי $a_{ij}=i \cdot j$ .
א. מהי דרגתה של המטריצה?
ב. מצאו את הע"ע שלה.
ג. מצאו לפחות ו"ע אחד של המטריצה.
ד. נתונה המטריצה $D$ אשר איבריה הם $d_{ij}=\displaystyle \sum_{k=1}^n (k-i)(k-j)$ . הוכח שמטריצה זו חיובית מוגדרת.

פתרון א':
נסתכל על דוגמה:

A_{2}=\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix} \qquad \qquad A_{3}=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 9 & 6 \\ 3 & 6 & 9 \end{pmatrix}

$r(A)=1$ כי כל השורות הן כפולה בסקלר של השורה הראשונה.

A_{i}=\begin{pmatrix} i\cdot 1 & i\cdot 2 & \dots & i\cdot n \end{pmatrix}=i\begin{pmatrix} 1 & 2 & \dots & n \end{pmatrix}

פתרון ב':
אנו יודעים כי $0$ מר"ג של $n-1$ מכיוון שהשורות הן כפולה בסקרל אחד של השני.
לפי משפט, $0$ הוא מר"א של לפחות $n-1$ פעמים.

\mathrm{Tr}(A)=\sum_{i=1}^n i^2=\lambda+(n-1)\cdot 0=\lambda

\lambda=\frac{n(n+1)(2n+1)}{6}

הערה: לא צריך לזכור את הנוסחה הזו, הפתרון עם הסכום סבבה. זה לא קומבי פה.

פתרון ג':
ל- $0$ יש $n-1$ ו"ע בת"ל.

\forall j\neq 1 :\;\;\; A(je_{1}-e_{j})=0

כל העמודות הן כפולה בסקלר של העמודה הראשונה.

jA_{1}-A_{j}=0

נקבל את הפתרונות: $\left\{ 2e_{1}-e_{2},3e_{1}-e_{3},\dots,ne_{1}-e_{n} \right\}$

A=\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}\begin{pmatrix} 1 & 2 & \dots & n \end{pmatrix}

A\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}=\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}\begin{pmatrix} 1 & 2 & \dots & n \end{pmatrix}\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}=\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}\sum_{i=1}^n i^2

הערה

אם $A=\underline{v}\underline{v}^t$ אז:

A\underline{v}=\underline{v}\underline{v}^t\underline{v}=(\underline{v}^t\underline{v})\underline{v}

$\underline{v}^t\underline{v}$ הוא סקלר ולכן יהיה הע"ע בעוד ש- $\underline{v}$ הוא ו"ע.

פתרון ד':
נמצא $B$ כך ש- $D=B^tB$ .
אם קיימת כזאת אזי $d_{ij}=\displaystyle \sum_{k=1}^n b_{ki}b_{kj}$ . נקבע $b_{ij}=(i-j)$ ונקבל:

d_{ij}=\sum_{k=1}^n b_{ki}b_{kj}=\sum_{k=1}^n (k-i)(k-j)

ולכן, קיימת $B$ כך ש- $D=B^tB$ .
לכן, $D$ היא מטריצת גרם ולכן, לפי משפט, היא חיובית חצי מוגדרת.

תרגיל

תהא $A$ סימטרית מגודל $n\times n$ .
הוכח כי $\displaystyle \underset{\underline{w}}{\max} \frac{\underline{w}^tA\underline{w}}{\underline{w}^t\underline{w}}=\lambda$ כאשר $\lambda$ הוא הע"ע הגדול ביותר.

הוכחה:
$A$ סימטרית ולכן לכסינה ואורתוגונלית.
לכן, קיים בסיס אורתונורמלי של ו"ע ב- $\mathbb{R}^n$ ובה"כ $\underline{v}_{1}$ הוא הו"ע המתאים ל- $\lambda$ הנתונה.

\frac{\underline{v}_{1}^tA\underline{v}_{1}}{\left\lVert \underline{v}_{1} \right\rVert_{2}^2 }=\underline{v}^t_{1}A\underline{v}_{1}=\underline{v}_{1}^t\lambda \underline{v}_{1}=\lambda \underline{v}_{1}^t\underline{v}_{1}=\lambda

לכן: $\displaystyle \underset{\underline{w}}{\max} \frac{\underline{w}^tA\underline{w}}{\underline{w}^t\underline{w}}\geq \lambda$ .
יהי $0\neq \underline{w} \in \mathbb{R}^n$ . קיימים $\alpha_{1},\alpha_{2},\dots,\alpha_{n}\in \mathbb{R}$ כך ש- $\underline{w}=\alpha_{1}\underline{v}_{1}+\alpha_{2}\underline{v}_{2}+\dots+\alpha_{n}\underline{v}_{n}$ .

\underline{w}^tA\underline{w}=\left( \sum_{k=1}^n \alpha_{k}\underline{v}_{k} \right)^tA\left( \sum_{k=1}^n \alpha_{k}\underline{v}_{k} \right)=\sum_{k,t \in \left\{ 1,\dots,n \right\}} \alpha_{k}\alpha_{t}\underline{v}_{k}^tA\underline{v}_{t}=\sum_{k,t \in \left\{ 1,\dots,n \right\}}\lambda_{t}\alpha_{k}\alpha_{t}\underline{v}_{k}^t\underline{v}_{t}=\lambda_{k}\alpha_{k}^2\cdot 1

\leq \lambda \sum_{k=1}^n \alpha_{k}^2=\lambda \underline{w}^t\underline{w}

\frac{\underline{w}^tA\underline{w}}{\left\lVert \underline{w} \right\rVert_{2}^2 }\leq \lambda

לכן: $\displaystyle \underset{\underline{w}}{\max} \frac{\underline{w}^tA\underline{w}}{\underline{w}^t\underline{w}}= \lambda$
∎

הגדרה 1 (ערך עצמי)

עבור מטריצה ריבועית $A$ בגודל $n\times n$ , הסקלר $\lambda$ יקרא ערך עצמי אם קיים וקטור $\underline{v}$ כך שמתקיים:

A\underline{v}=\lambda \underline{v}

הגדרה 2 (וקטור עצמי)

וקטור $\underline{v}$ לו קיימת $\lambda$ המקיים $A\underline{v}=\lambda \underline{v}$ נקרא וקטור עצמי

משפט

|A|=\prod_{k=1}^n \lambda_{k} \qquad \qquad \mathrm{Tr}(A)=\sum_{k=1}^n \lambda_{k}

דוגמה

נמצא את הע"ע של המטריצה $A=\begin{pmatrix}1 & 2 & 4 \\ 2 & 3 & 2 \\ 4 & 2 & 1\end{pmatrix}$ .

|A-\lambda I|=\begin{vmatrix} 1-\lambda & 2 & 4 \\ 2 & 3-\lambda & 2 \\ 4 & 2 & 1-\lambda \end{vmatrix}=-\lambda^3+5\lambda^2+17\lambda-21=0

\frac{-\lambda^3+5\lambda^2+17\lambda-21}{\lambda-7}=-(\lambda-1)(\lambda+3)

נמצא את השאר: $\lambda_{2}=1 \land \lambda_{3}=-3$ .

את הו"ע נמצא ע"י מציאת הפתרונות למשוואה ההומוגנית $(A-\lambda_{3}I)\underline{v}=\underline{0}$ .

משפט (פירוק

Schur

)

אם מטריצה ממשית ולכסינה, אזי היא ניתנת לפירוק שור:

A=QTQ^H

כאשר $Q^H=\overline{Q^t}$ ומתקיים:

$T$ משולשת עליונה (ואולי מרוכבת)
$Q$ אורתונורמלית (ואולי מרוכבת)

הערה

גם אם $A$ סימטרית, $T \neq T^H$ בהכרח.

T=T^H \iff \R{\text{ אלכסונית וממשית}} T

באופן כללי, עבור $A$ סימטרית:

A=A^H \iff \R{\text{ ממשית}}A

משפט

אם $A$ מטריצה ריבועית ממשית וסימטרית אזי:

$A$ לכסינה
כל הע"ע שלה ממשיים
כל הו"ע יכולים להיות ממשיים
ו"ע השייכים לע"ע שונים יהיו אורתוגונוליים.

משפט

אם $A$ מטריצה ריבועית, ממשית, סימטרית וחיובית מוגדרת, אזי כל הע"ע שלה חיוביים.

משפט

אם $A$ מטריצה ריבועית, ממשית, סימטרית וחיובית חצי מוגדרת, אזי כל הע"ע שלה אי שליליים.

ראינו שע"ע וו"ע יכולים להתקבל כפתרון של בעיית אופטימיזציה.
אם $A$ סימטרית אזי:

\underset{\underline{x}|\;\!\left\lVert \underline{x} \right\rVert_{2}=1 }{\max} \underline{x}^tA\underline{x}=\underset{\underline{x}}{\max} \frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}}=\lambda_{1}

כאשר $\lambda_{1}$ הוא הע"ע הגדול ביותר של $A$ .
באותו האופן:

\underset{\underline{x}|\;\!\left\lVert \underline{x} \right\rVert_{2}=1 }{\min} \underline{x}^tA\underline{x}=\underset{\underline{x}}{\min} \frac{\underline{x}^tA\underline{x}}{\underline{x}^t\underline{x}}=\lambda_{n}

כאשר $\lambda_{n}$ הוא הע"ע הקטן ביותר של $A$ .

תרגיל

פתרון א':
נסתכל על דוגמה:

A_{2}=\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix} \qquad \qquad A_{3}=\begin{pmatrix} 1 & 2 & 3 \\ 2 & 9 & 6 \\ 3 & 6 & 9 \end{pmatrix}

$r(A)=1$ כי כל השורות הן כפולה בסקלר של השורה הראשונה.

A_{i}=\begin{pmatrix} i\cdot 1 & i\cdot 2 & \dots & i\cdot n \end{pmatrix}=i\begin{pmatrix} 1 & 2 & \dots & n \end{pmatrix}

\mathrm{Tr}(A)=\sum_{i=1}^n i^2=\lambda+(n-1)\cdot 0=\lambda

\lambda=\frac{n(n+1)(2n+1)}{6}

הערה: לא צריך לזכור את הנוסחה הזו, הפתרון עם הסכום סבבה. זה לא קומבי פה.

פתרון ג':
ל- $0$ יש $n-1$ ו"ע בת"ל.

\forall j\neq 1 :\;\;\; A(je_{1}-e_{j})=0

כל העמודות הן כפולה בסקלר של העמודה הראשונה.

jA_{1}-A_{j}=0

נקבל את הפתרונות: $\left\{ 2e_{1}-e_{2},3e_{1}-e_{3},\dots,ne_{1}-e_{n} \right\}$

A=\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}\begin{pmatrix} 1 & 2 & \dots & n \end{pmatrix}

A\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}=\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}\begin{pmatrix} 1 & 2 & \dots & n \end{pmatrix}\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}=\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}\sum_{i=1}^n i^2

הערה

אם $A=\underline{v}\underline{v}^t$ אז:

A\underline{v}=\underline{v}\underline{v}^t\underline{v}=(\underline{v}^t\underline{v})\underline{v}

$\underline{v}^t\underline{v}$ הוא סקלר ולכן יהיה הע"ע בעוד ש- $\underline{v}$ הוא ו"ע.

פתרון ד':
נמצא $B$ כך ש- $D=B^tB$ .
אם קיימת כזאת אזי $d_{ij}=\displaystyle \sum_{k=1}^n b_{ki}b_{kj}$ . נקבע $b_{ij}=(i-j)$ ונקבל:

d_{ij}=\sum_{k=1}^n b_{ki}b_{kj}=\sum_{k=1}^n (k-i)(k-j)

ולכן, קיימת $B$ כך ש- $D=B^tB$ .
לכן, $D$ היא מטריצת גרם ולכן, לפי משפט, היא חיובית חצי מוגדרת.

תרגיל

\frac{\underline{v}_{1}^tA\underline{v}_{1}}{\left\lVert \underline{v}_{1} \right\rVert_{2}^2 }=\underline{v}^t_{1}A\underline{v}_{1}=\underline{v}_{1}^t\lambda \underline{v}_{1}=\lambda \underline{v}_{1}^t\underline{v}_{1}=\lambda

\underline{w}^tA\underline{w}=\left( \sum_{k=1}^n \alpha_{k}\underline{v}_{k} \right)^tA\left( \sum_{k=1}^n \alpha_{k}\underline{v}_{k} \right)=\sum_{k,t \in \left\{ 1,\dots,n \right\}} \alpha_{k}\alpha_{t}\underline{v}_{k}^tA\underline{v}_{t}=\sum_{k,t \in \left\{ 1,\dots,n \right\}}\lambda_{t}\alpha_{k}\alpha_{t}\underline{v}_{k}^t\underline{v}_{t}=\lambda_{k}\alpha_{k}^2\cdot 1

\leq \lambda \sum_{k=1}^n \alpha_{k}^2=\lambda \underline{w}^t\underline{w}

\frac{\underline{w}^tA\underline{w}}{\left\lVert \underline{w} \right\rVert_{2}^2 }\leq \lambda

לכן: $\displaystyle \underset{\underline{w}}{\max} \frac{\underline{w}^tA\underline{w}}{\underline{w}^t\underline{w}}= \lambda$
∎