Lineaire Algebra – Symmetrische matrices en kwadratische vormen – Voorwaardelijke optimalisatie

We zoeken naar maximale en minimale waarden van een kwadratische vorm \(Q(\mathbf{x})\) op \(\mathbb{R}^n\) onder bepaalde voorwaarden. Zo'n voorwaarde is bijvoorbeeld dat \(\mathbf{x}\in\mathbb{R}^n\) een eenheidsvector is, dat wil zeggen:

\[||\mathbf{x}||=1\quad\Longleftrightarrow\quad||\mathbf{x}||^2=1\quad\Longleftrightarrow\quad\mathbf{x}^T\mathbf{x}= \quad\Longleftrightarrow\quad x_1^2+\cdots+x_n^2=1.\]

Voorbeeld: Stel dat \(Q:\mathbb{R}^3\to\mathbb{R}\) met \(Q(\mathbf{x})=7x_1^2+4x_2^2+2x_3^2\). Wat is dan het maximum en het minimum van \(Q(\mathbf{x})\) onder de voorwaarde dat \(\mathbf{x}^T\mathbf{a}=1\) oftewel \(x_1^2+x_2^2+x_3^2=1\). Merk op dat

\[Q(\mathbf{x})=7x_1^2+4x_2^2+2x_3^2\leq 7x_1^2+7x_2^2+7x_3^2=7(x_1^2+x_2^2+x_3^2)=7\]

en

\[Q(\mathbf{x})=7x_1^2+4x_2^2+2x_3^2\geq 2x_1^2+2x_2^2+7x_3^2=2(x_1^2+x_2^2+x_3^2)=2.\]

Verder geldt: \(\mathbf{x}=\begin{pmatrix}1\\0\\0\end{pmatrix}\;\Longrightarrow\;Q(\mathbf{x})=7\) en \(\mathbf{x}=\begin{pmatrix}0\\0\\1\end{pmatrix}\;\Longrightarrow\;Q(\mathbf{x})=2\).

Hieruit volgt dat het maximum van \(Q(\mathbf{x})\) onder de voorwaarde \(\mathbf{x}^T\mathbf{x}=1\) gelijk is aan \(7\) en het minimum gelijk aan \(2\). Dit is respectievelijk de grootste en de kleinste eigenwaarde van de matrix \(D=\text{diag}(7,4,2)\) van de kwadratische vorm \(Q\). Dit geldt algemeen:

Stelling: Als \(A\) een symmetrische matrix is en \(M=\max\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}\) en \(m=\min\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}\), dan geldt: \(M\) is gelijk aan de grootste eigenwaarde van \(A\) en \(m\) is gelijk aan de kleinste eigenwaarde van \(A\). Verder geldt: \(\mathbf{x}^TA\mathbf{x}=M\) als \(\mathbf{x}\) een eigenvector (met \(||\mathbf{x}||=1\) is van \(A\) behorende bij de eigenwaarde \(M\) en \(\mathbf{x}^TA\mathbf{x}=m\) als \(\mathbf{x}\) een eigenvector (met \(||\mathbf{x}||=1\) is van \(A\) behorende bij de eigenwaarde \(m\).

Bewijs: De matrix \(A\) is symmetrisch en dus orthogonaal diagonaliseerbaar. Dat wil zeggen: \(A=PDP^T\) voor zekere orthogonale matrix \(P\) en diagonaalmatrix \(D\). Stel nu \(\mathbf{x}=P\mathbf{y}\), dan volgt: \(\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}\). Verder geldt: \(||\mathbf{x}||=||P\mathbf{y}||=||\mathbf{y}||\). Dus: \(||\mathbf{x}||=1\;\Longleftrightarrow\;||\mathbf{y}||=1\).

Stel nu \(P=\Bigg(\mathbf{u}_1\;\ldots\;\mathbf{u}_n\Bigg)\) en \(D=\text{diag}(\lambda_1,\ldots,\lambda_n)\) met \(\lambda_1\geq\ldots\geq\lambda_n\). Dan geldt dat \(\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}=\lambda_1y_1^2+\cdots+\lambda_ny_n^2\) en dus:

\[M=\max\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}=\max\{\mathbf{y}^TD\mathbf{y}\,:\,||\mathbf{y}||=1\}=\lambda_1\]

en

\[m=\min\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}=\min\{\mathbf{y}^TD\mathbf{y}\,:\,||\mathbf{y}||=1\}=\lambda_n.\]

Verder geldt: \(M=\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}\) als \(\mathbf{y}=\begin{pmatrix}1\\0\\\vdots\\0\end{pmatrix}\) en dus als \(\mathbf{x}=P\mathbf{y}=\mathbf{u}_1\) en \(m=\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}\) als \(\mathbf{y}=\begin{pmatrix}0\\\vdots\\0\\1\end{pmatrix}\) en dus als \(\mathbf{x}=P\mathbf{y}=\mathbf{u}_n\).

Voorbeeld: Bepaal het maximum \(M\) en het minimum \(m\) van de kwadratische vorm \(Q(\mathbf{x})=x_1^2+5x_2^2+5x_3^2-8x_1x_2+8x_1x_3\) onder de voorwaarde dat \(\mathbf{x}^T\mathbf{x}=1\) en bepaal een eenheidsvector \(\mathbf{x}\) zodat \(Q(\mathbf{x})=M\) en een eenheidsvector \(\mathbf{x}\) zodat \(Q(\mathbf{x})=m\).

Merk op dat \(Q(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\) met \(A=\begin{pmatrix}1&-4&4\\-4&5&0\\4&0&5\end{pmatrix}\). Dan volgt:

\begin{align*} |A-\lambda I|&=\begin{vmatrix}1-\lambda&-4&4\\-4&5-\lambda&0\\4&0&5-\lambda\end{vmatrix}=\begin{vmatrix}1-\lambda&-4&4\\ 0&5-\lambda&5-\lambda\\4&0&5-\lambda\end{vmatrix}=\begin{vmatrix}1-\lambda&-4&8\\0&5-\lambda&0\\4&0&5-\lambda\end{vmatrix}\\[2.5mm] &=(5-\lambda)\begin{vmatrix}1-\lambda&8\\4&5-\lambda\end{vmatrix}=(5-\lambda)(\lambda^2-6\lambda-27)=(5-\lambda)(\lambda-9)(\lambda+3). \end{align*}

Hieruit volgt dat \(M=9\) en \(m=-3\). Verder volgt:

\[M=9:\quad\begin{pmatrix}-8&-4&4\\-4&-4&0\\4&0&-4\end{pmatrix}\sim\begin{pmatrix}1&0&-1\\0&1&1\\0&0&0\end{pmatrix} \quad\Longrightarrow\quad\mathbf{x}=\pm\frac{1}{\sqrt{3}}\begin{pmatrix}1\\-1\\1\end{pmatrix}\]

en

\[m=-3:\quad\begin{pmatrix}4&-4&4\\-4&8&0\\4&0&8\end{pmatrix}\sim\begin{pmatrix}1&0&2\\0&1&1\\0&0&0\end{pmatrix} \quad\Longrightarrow\quad\mathbf{x}=\pm\frac{1}{\sqrt{6}}\begin{pmatrix}2\\1\\-1\end{pmatrix}.\]

We kunnen nog wat extra voorwaarden opleggen:

Stelling: Als \(A\) een symmetrische matrix is met \(A=PDP^T\), waarbij \(P=\Bigg(\mathbf{u}_1\;\ldots\;\mathbf{u}_n\Bigg)\) en \(D=\text{diag}(\lambda_1,\ldots,\lambda_n\) met \(\lambda_1\geq\cdots\geq\lambda_n\), dan geldt voor iedere \(k\in\{1,2,\ldots,n-1\}\): het maximum van de kwadratische vorm \(\mathbf{x}^TA\mathbf{x}\) onder de voorwaarden

\[\mathbf{x}^T\mathbf{x}=1,\quad\mathbf{x}^T\mathbf{u}_1=0,\;\ldots,\quad\mathbf{x}^T\mathbf{u}_k=0\]

is gelijk aan de eigenwaarde \(\lambda_{k+1}\) en \(\mathbf{x}^TA\mathbf{x}=\lambda_{k+1}\) als \(\mathbf{x}=\mathbf{u}_{k+1}\).

Voorbeeld: Bepaal het maximum van de kwadratische vorm \(Q(\mathbf{x})=x_1^2+5x_2^2+5x_3^2-8x_1x_2+8x_1x_3\) onder de voorwaarden dat \(\mathbf{x}^T\mathbf{x}=1\) en \(\mathbf{x}^T\mathbf{u}_1=0\) met \(\mathbf{u}_1=\dfrac{1}{\sqrt{3}}\begin{pmatrix}1\\-1\\1\end{pmatrix}\) en bepaal een eenheidsvector \(\mathbf{x}\) waarvoor dat maximum wordt aangenomen.

We hebben gezien dat \(Q(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\) met \(A=\begin{pmatrix}1&-4&4\\-4&5&0\\4&0&5\end{pmatrix}\) en dat de eigenwaarden zijn: \(\lambda_1=9\), \(\lambda_2=5\) en \(\lambda_3=-3\). Het maximum onder de voorwaarden is gelijk aan \(5\). Verder volgt:

\[\lambda_2=5:\quad\begin{pmatrix}-4&-4&4\\-4&0&0\\4&0&0\end{pmatrix}\sim\begin{pmatrix}1&0&0\\0&1&-1\\0&0&0\end{pmatrix} \quad\Longrightarrow\quad\mathbf{x}=\pm\frac{1}{\sqrt{2}}\begin{pmatrix}0\\1\\1\end{pmatrix}.\]

---

Laatst gewijzigd op 2 mei 2021