עד כה עסקנו בפתרון יעיל(L U LU LU A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b A ∈ R m × n A \in\mathbb{R}^{m \times n} A ∈ R m × n m ≥ n m\geq n m ≥ n A A A
קיומו של פתרון יחיד
אין פתרון
מה קורה כאשר אין פתרון? על פי מה שידענו עד כה עלינו להרים ידים. לא עוד! אלגוריתם הריבועים הפחותים מציע חלופה: נחפש את הוקטור x ‾ ∗ \underline{x}^* x ∗
min x ‾ p ( x ‾ ) = min x ‾ ∥ A x ‾ − b ‾ ∥ 2 2 = min ∥ r ⃗ ∥ 2 2 \underset{\underline{x}}{\min}p(\underline{x})=\underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=\min\left\lVert \vec{r} \right\rVert _{2}^2 x min p ( x ) = x min ∥ A x − b ∥ 2 2 = min ∥ r ∥ 2 2 הפונקציה המובאת למינימום היא "פרבולה רב מימדית":
p ( x ‾ ) = ∥ A x ‾ − b ‾ ∥ 2 2 = ( A x ‾ − b ‾ ) t ( A x ‾ − b ‾ ) = ( A x ‾ ) t A x ‾ − ( A x ‾ ) t b ‾ − b ‾ t A x ‾ + b t b x ‾ t A t A x ‾ − 2 x ‾ t A t b ‾ + b ‾ t b ‾ = x ‾ t K x ‾ − 2 x ‾ t f ‾ + c \begin{align*}
p(\underline{x})&=\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=(A\underline{x}-\underline{b})^t(A\underline{x}-\underline{b}) \\
&=(A\underline{x})^tA\underline{x}-(A\underline{x})^t\underline{b}-\underline{b}^tA\underline{x}+b^tb \\
&\underline{x}^tA^tA\underline{x}-2\underline{x}^tA^t\underline{b}+\underline{b}^t\underline{b}=\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c
\end{align*} p ( x ) = ∥ A x − b ∥ 2 2 = ( A x − b ) t ( A x − b ) = ( A x ) t A x − ( A x ) t b − b t A x + b t b x t A t A x − 2 x t A t b + b t b = x t K x − 2 x t f + c
בבעיה הריבועית שהתקבלה, אם המטריצה K K K K ≻ 0 K \succ 0 K ≻ 0 p ( x ‾ ) p(\underline{x}) p ( x )
x ‾ ∗ = K − 1 f ‾ \underline{x}^*=K^{-1}\underline{f} x ∗ = K − 1 f
אם K K K
פתרון הריבועים הפחותים
p ( x ‾ ) = ∥ A x ‾ − b ‾ ∥ 2 2 = x ‾ t A t A x ‾ − 2 x ‾ t A t b ‾ + b ‾ t b ‾ = x ‾ t K x ‾ − 2 x ‾ t f ‾ + c p(\underline{x})=\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2 =\underline{x}^tA^tA\underline{x}-2\underline{x}^tA^t\underline{b}+\underline{b}^t\underline{b}=\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c p ( x ) = ∥ A x − b ∥ 2 2 = x t A t A x − 2 x t A t b + b t b = x t K x − 2 x t f + c הפתרון האופטימלי צריך לקיים:
K x ‾ = f ‾ ⟺ A t A x ‾ = A t b ‾ K\underline{x} =\underline{f} \iff A^tA\underline{x}=A^t\underline{b} K x = f ⟺ A t A x = A t b x ‾ ∗ = ( A t A ) − 1 A t b ‾ = A † b ‾ \underline{x}^*=(A^tA)^{-1}A^t\underline{b}=A^{\dagger}\underline{b} x ∗ = ( A t A ) − 1 A t b = A † b
הפסודו-היפוך מתלכד עם היפוך רגיל כאשר המטריצה ריבועית.
נוכל לטעון ש-K = A t A K=A^tA K = A t A A A A K = A t A K=A^tA K = A t A
בבעיה הריבועית שהתקבלה, אם המטריצה K K K x ‾ ∗ \underline{x}^* x ∗
K x ‾ ∗ = f ‾ K\underline{x}^*=\underline{f} K x ∗ = f מהווה נקודת מינימום גלובלית ל-p ( x ‾ ) p(\underline{x}) p ( x )
בואו נעניק לנוסחת הפתרון משמעות נוספת:
K x ‾ ∗ = f ‾ ⇓ A t A x ‾ ∗ = A t b ‾ ⇓ A t ( A x ‾ ∗ − b ‾ ) = 0 ⇓ A t r ‾ ∗ = 0 } A ⊥ r ‾ ∗ \left.\begin{matrix}
K\underline{x}^*=\underline{f} \\
\Downarrow \\
A^tA\underline{x}^*=A^t\underline{b} \\
\Downarrow \\
A^t(A\underline{x}^*-\underline{b})=0 \\
\Downarrow \\
A^t\underline{r}^*=0
\end{matrix}\right\} {\LARGE A \perp \underline{r}^*} K x ∗ = f ⇓ A t A x ∗ = A t b ⇓ A t ( A x ∗ − b ) = 0 ⇓ A t r ∗ = 0 ⎭ ⎬ ⎫ A ⊥ r ∗ פירוש הדבר הוא שוקטור השארית r ‾ ∗ = A x ‾ ∗ − b ‾ \underline{r}^*=A\underline{x}^*-\underline{b} r ∗ = A x ∗ − b A A A A t A x ‾ = A t b ‾ A^tA\underline{x}=A^t\underline{b} A t A x = A t b המשוואה הנורמלית .
במונחים של נגזרות
הריבועים הפחותים זו בעצם פונקציה ונוכל לגזור אותה:
∇ x ‾ p ( x ‾ ) = 2 A t ( A x ‾ − b ‾ ) \nabla_{\underline{x}}p(\underline{x})=2A^t(A\underline{x}-\underline{b}) ∇ x p ( x ) = 2 A t ( A x − b ) לכן, מציאת המינימום כרוכה באיפוס הגרדיאנט ומכאן מגיעים למשוואה הנורמלית
2 A t ( A x ‾ − b ‾ ) = 0 ⟹ A t A x ‾ = A t b ‾ 2A^t(A\underline{x}-\underline{b})=0 \implies A^tA\underline{x}=A^t\underline{b} 2 A t ( A x − b ) = 0 ⟹ A t A x = A t b באופן דומה, אם K ≻ 0 K \succ 0 K ≻ 0
∇ x ‾ ( x ‾ t K x ‾ − 2 x ‾ t f ‾ + c ) = 2 ( K x ‾ − f ‾ ) \nabla_{\underline{x}}(\underline{x}^tK\underline{x}-2\underline{x}^t\underline{f}+c)=2(K\underline{x}-\underline{f}) ∇ x ( x t K x − 2 x t f + c ) = 2 ( K x − f )
מצאו פתרון ל:
min x ‾ ∥ ( 1 − 1 1 1 1 0 ) ( x 1 x 2 ) − ( 2 1 1 ) ∥ 2 2 \underset{\underline{x}}{\min}\left\lVert \begin{pmatrix}
1 & -1 \\
1 & 1 \\
1 & 0
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}-\begin{pmatrix}
2 \\
1 \\
1
\end{pmatrix} \right\rVert_{2}^2 x min 1 1 1 − 1 1 0 ( x 1 x 2 ) − 2 1 1 2 2 צריך לפתור את המשוואה הנורמלית:
A t A x ‾ = A t b ‾ A^tA\underline{x}=A^t\underline{b} A t A x = A t b A t A = ( 1 1 1 − 1 1 0 ) ( 1 − 1 1 1 1 0 ) = ( 3 0 0 2 ) A t b ‾ = ( 1 1 1 − 1 1 0 ) ( 2 1 1 ) = ( 4 − 1 ) A^tA=\begin{pmatrix}
1 & 1 & 1 \\
-1 & 1 & 0
\end{pmatrix}\begin{pmatrix}
1 & -1 \\
1 & 1 \\
1 & 0
\end{pmatrix}=\begin{pmatrix}
3 & 0 \\
0 & 2
\end{pmatrix} \qquad \qquad A^t\underline{b}=\begin{pmatrix}
1 & 1 & 1 \\
-1 & 1 & 0
\end{pmatrix}\begin{pmatrix}
2 \\
1 \\
1
\end{pmatrix}=\begin{pmatrix}
4 \\
-1
\end{pmatrix} A t A = ( 1 − 1 1 1 1 0 ) 1 1 1 − 1 1 0 = ( 3 0 0 2 ) A t b = ( 1 − 1 1 1 1 0 ) 2 1 1 = ( 4 − 1 ) ואז נקבל:
( 3 0 0 2 ) ( x 1 x 2 ) = ( 4 − 1 ) \begin{pmatrix}
3 & 0 \\
0 & 2
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}=\begin{pmatrix}
4 \\
-1
\end{pmatrix} ( 3 0 0 2 ) ( x 1 x 2 ) = ( 4 − 1 ) ( 3 2 4 0 2 − 1 ) R 1 = R 1 − R 2 → ( 3 0 4 0 2 − 1 ) ⟹ ( x 1 x 2 ) = ( 4 3 − 1 2 ) \left(\begin{array}{cc|c}
3 & 2 & 4 \\
0 & 2 & -1
\end{array}\right)\overrightarrow{R_{1}=R_{1}-R_{2}}\left(\begin{array}{cc|c}
3 & 0 & 4 \\
0 & 2 & -1
\end{array}\right)\implies \begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}=\begin{pmatrix}
\frac{4}{3} \\
-\frac{1}{2}
\end{pmatrix} ( 3 0 2 2 4 − 1 ) R 1 = R 1 − R 2 ( 3 0 0 2 4 − 1 ) ⟹ ( x 1 x 2 ) = ( 3 4 − 2 1 ) עמודות המטריצה בת"ל ולכן אמור להיות לנו פתרון אחד - שזה בדיוק מה שיצא לנו :)
A ( 4 3 − 1 2 ) = ( 11 6 5 6 4 3 ) A\begin{pmatrix}
\frac{4}{3} \\
-\frac{1}{2}
\end{pmatrix}=\begin{pmatrix}
\frac{11}{6} \\
\frac{5}{6} \\
\frac{4}{3}
\end{pmatrix} A ( 3 4 − 2 1 ) = 6 11 6 5 3 4 ∥ ( 11 6 5 6 4 3 ) − ( 2 1 1 ) ∥ 2 2 = ∥ ( − 1 6 − 1 6 1 3 ) ∥ 2 2 = 1 6 \left\lVert \begin{pmatrix}
\frac{11}{6} \\
\frac{5}{6} \\
\frac{4}{3}
\end{pmatrix}-\begin{pmatrix}
2 \\
1 \\
1
\end{pmatrix} \right\rVert_{2}^2=\left\lVert \begin{pmatrix}
-\frac{1}{6} \\
-\frac{1}{6} \\
\frac{1}{3}
\end{pmatrix} \right\rVert_{2}^2=\frac{1}{6} 6 11 6 5 3 4 − 2 1 1 2 2 = − 6 1 − 6 1 3 1 2 2 = 6 1
מצאו פתרון:
min x ‾ ∥ ( 5 − 8 1 1 1 3 ) ( x 1 x 2 ) − ( 1 2 4 ) ∥ 2 2 \underset{\underline{x}}{\min}\left\lVert \begin{pmatrix}
5 & -8 \\
1 & 1 \\
1 & 3
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}-\begin{pmatrix}
1 \\
2 \\
4
\end{pmatrix} \right\rVert _{2}^2 x min 5 1 1 − 8 1 3 ( x 1 x 2 ) − 1 2 4 2 2 A t A = ( 27 − 36 − 36 74 ) A t b ‾ = ( 11 6 ) A^tA=\begin{pmatrix}
27 & -36 \\
-36 & 74
\end{pmatrix} \qquad \qquad A^t\underline{b}=\begin{pmatrix}
11 \\
6
\end{pmatrix} A t A = ( 27 − 36 − 36 74 ) A t b = ( 11 6 ) המטריצה A t A A^tA A t A A A A
( 27 − 36 − 36 74 ) ( x 1 x 2 ) = ( 11 6 ) \begin{pmatrix}
27 & -36 \\
-36 & 74
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}=\begin{pmatrix}
11 \\
6
\end{pmatrix} ( 27 − 36 − 36 74 ) ( x 1 x 2 ) = ( 11 6 ) ( 1 − 12 11 3 0 26 62 3 ) ⟹ ( x 1 x 2 ) = ( 1.467 0.795 ) \left(\begin{array}{cc|c}
1 & -12 & \frac{11}{3} \\
0 & 26 & \frac{62}{3}
\end{array}\right)\implies \begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}=\begin{pmatrix}
1.467 \\
0.795
\end{pmatrix} ( 1 0 − 12 26 3 11 3 62 ) ⟹ ( x 1 x 2 ) = ( 1.467 0.795 ) דרך נוספת לפתרון
בהינתן נקודה b ‾ ∈ R m \underline{b} \in \mathbb{R}^m b ∈ R m V ⊆ R m V \subseteq \mathbb{R}^m V ⊆ R m v ‾ ∗ ∈ V \underline{v}^* \in V v ∗ ∈ V b ‾ \underline{b} b V V V { v ‾ 1 , v ‾ 2 , … , v ‾ n } \left\{ \underline{v}_{1},\underline{v}_{2},\dots,\underline{v}_{n} \right\} { v 1 , v 2 , … , v n } v ‾ ∈ V \underline{v}\in V v ∈ V
v ‾ = x 1 v ‾ 1 + x 2 v ‾ 2 + ⋯ + x n v ‾ n = ( ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ v ‾ 1 v ‾ 2 … v ‾ n ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ) ( x 1 x 2 ⋮ x n ) = A x ‾ \underline{v}=x_{1}\underline{v}_{1}+x_{2}\underline{v}_{2}+\dots+x_{n}\underline{v}_{n}=\begin{pmatrix}
\vert & \vert & & \vert \\
\vert & \vert & & \vert \\
\vert & \vert & & \vert \\
\underline{v}_{1} & \underline{v}_{2} & \dots & \underline{v}_{n} \\
\vert & \vert & & \vert \\
\vert & \vert & & \vert \\
\vert & \vert & & \vert
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2} \\
\vdots \\
x_{n}
\end{pmatrix}=A\underline{x} v = x 1 v 1 + x 2 v 2 + ⋯ + x n v n = ∣ ∣ ∣ v 1 ∣ ∣ ∣ ∣ ∣ ∣ v 2 ∣ ∣ ∣ … ∣ ∣ ∣ v n ∣ ∣ ∣ x 1 x 2 ⋮ x n = A x כל בעיית ריבועים פחותים ניתנת לפרשות כפעולת הטלה של הוקטור b ‾ \underline{b} b A A A
v ‾ ∗ = a r g min v ‾ ∈ V ∥ v ‾ − b ‾ ∥ 2 2 \underline{v}^*=arg \underset{\underline{v} \in V}{\min}\left\lVert \underline{v}-\underline{b} \right\rVert _{2}^2 v ∗ = a r g v ∈ V min ∥ v − b ∥ 2 2 x ‾ ∗ = a r g min x ‾ ∥ A x ‾ − b ‾ ∥ 2 2 ⟹ v ‾ ∗ = A x ‾ ∗ \underline{x}^*=arg \underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2 \implies \underline{v}^*=A\underline{x}^* x ∗ = a r g x min ∥ A x − b ∥ 2 2 ⟹ v ∗ = A x ∗
אם c o l A = c o l B colA=colB co l A = co lB
∥ A x ‾ − b ‾ ∥ 2 2 ⟵ x ‾ ∗ \left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2 \longleftarrow \underline{x}^* ∥ A x − b ∥ 2 2 ⟵ x ∗ ∥ B x ‾ − b ‾ ∥ 2 2 ⟵ y ‾ ∗ \left\lVert B\underline{x}-\underline{b} \right\rVert _{2}^2 \longleftarrow \underline{y}^* ∥ B x − b ∥ 2 2 ⟵ y ∗ זה לא בהכרח יהיה אותו הפתרון אבל תמיד יתקיים A x ‾ ∗ = B y ‾ ∗ A\underline{x}^*=B\underline{y}^* A x ∗ = B y ∗
מצאו את הנקודה הקרובה ביותר ל-b ‾ \underline{b} b { ( 3 2 1 ) , ( − 2 1 3 ) } \left\{ \begin{pmatrix}3\\2\\1\end{pmatrix},\begin{pmatrix}-2\\1\\3\end{pmatrix} \right\} ⎩ ⎨ ⎧ 3 2 1 , − 2 1 3 ⎭ ⎬ ⎫ b ‾ = ( − 1 − 2 4 ) \underline{b}=\begin{pmatrix}-1\\-2\\4\end{pmatrix} b = − 1 − 2 4
נתרגם את בעיה זו לריבועים פחותים.
∥ ( 3 − 2 2 1 1 3 ) ( x 1 x 2 ) − ( − 1 − 2 4 ) ∥ 2 2 \left\lVert \begin{pmatrix}
3 & -2 \\
2 & 1 \\
1 & 3
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}-\begin{pmatrix}
-1 \\
-2 \\
4
\end{pmatrix} \right\rVert_{2}^2 3 2 1 − 2 1 3 ( x 1 x 2 ) − − 1 − 2 4 2 2 מחפשים את A x ‾ A\underline{x} A x ולא את x ‾ \underline{x} x
A t A = ( 14 − 1 − 1 14 ) A t b ‾ = ( − 3 12 ) A^tA=\begin{pmatrix}
14 & -1 \\
-1 & 14
\end{pmatrix} \qquad \qquad A^t\underline{b}=\begin{pmatrix}
-3 \\
12
\end{pmatrix} A t A = ( 14 − 1 − 1 14 ) A t b = ( − 3 12 ) ( 14 − 1 − 3 − 1 14 12 ) ⟹ ( x 1 x 2 ) = ( − 2 13 11 13 ) \left(\begin{array}{cc|c}
14 & -1 & -3 \\
-1 & 14 & 12
\end{array}\right)\implies \begin{pmatrix}
x_{1} \\
x_{2}
\end{pmatrix}=\begin{pmatrix}
-\frac{2}{13} \\
\frac{11}{13}
\end{pmatrix} ( 14 − 1 − 1 14 − 3 12 ) ⟹ ( x 1 x 2 ) = ( − 13 2 13 11 ) זה x ‾ \underline{x} x A x ‾ A\underline{x} A x
v ‾ ∗ = A x ‾ = ( 3 − 2 2 1 1 3 ) ( − 2 13 11 13 ) = ( − 28 13 7 13 31 13 ) \underline{v}^*=A\underline{x}=\begin{pmatrix}
3 & -2 \\
2 & 1 \\
1 & 3
\end{pmatrix}\begin{pmatrix}
-\frac{2}{13} \\
\frac{11}{13}
\end{pmatrix}=\begin{pmatrix}
-\frac{28}{13} \\
\frac{7}{13} \\
\frac{31}{13}
\end{pmatrix} v ∗ = A x = 3 2 1 − 2 1 3 ( − 13 2 13 11 ) = − 13 28 13 7 13 31 וזה בדיוק מה שרצינו.
תרגול מבחינות
תרגיל (מועד א' אביב תשנ"ו(בקורס שהיה הגרסה הקודמת של הקורס הזה))
נתונה בעיית הריבועים הפחותים הבאה:
min x ‾ ∥ A x ‾ − b ‾ ∥ 2 2 = min x ‾ ∥ ( 1 1 0 1 0 1 0 1 1 1 1 1 0 0 1 ) ( x 1 x 2 x 3 ) − ( 2 1 1 2 0 ) ∥ 2 2 \underset{\underline{x}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=\underset{\underline{x}}{\min}\left\lVert \begin{pmatrix}
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix}\begin{pmatrix}
x_{1} \\
x_{2} \\
x_{3}
\end{pmatrix}-\begin{pmatrix}
2 \\
1 \\
1 \\
2 \\
0
\end{pmatrix} \right\rVert _{2}^2 x min ∥ A x − b ∥ 2 2 = x min 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 x 1 x 2 x 3 − 2 1 1 2 0 2 2 א. האם לבעיה זו פתרון יחיד?L S LS L S A A A m × n m \times n m × n m < n m<n m < n
פתרון א': יחיד .
פתרון ב':
A t A = ( 3 2 2 2 3 2 2 2 4 ) A t b ‾ = ( 5 5 4 ) A^tA=\begin{pmatrix}
3 & 2 & 2 \\
2 & 3 & 2 \\
2 & 2 & 4
\end{pmatrix} \qquad \qquad A^t\underline{b}=\begin{pmatrix}
5 \\
5 \\
4
\end{pmatrix} A t A = 3 2 2 2 3 2 2 2 4 A t b = 5 5 4 כעת נפתור את המשוואה הנורמלית:
( 3 2 2 5 2 3 2 5 2 2 4 4 ) ⟹ ( x 1 x 2 x 3 ) = ( 1 1 0 ) \left(\begin{array}{ccc|c}
3 & 2 & 2 & 5 \\
2 & 3 & 2 & 5 \\
2 & 2 & 4 & 4
\end{array}\right) \implies \begin{pmatrix}
x_{1} \\
x_{2} \\
x_{3}
\end{pmatrix}=\begin{pmatrix}
1 \\
1 \\
0
\end{pmatrix} 3 2 2 2 3 2 2 2 4 5 5 4 ⟹ x 1 x 2 x 3 = 1 1 0 וזהו הפתרון היחיד.
פתרון ג': A x ‾ = b ‾ A\underline{x}=\underline{b} A x = b
∥ A x ‾ − b ‾ ∥ 2 2 = 0 \left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2=0 ∥ A x − b ∥ 2 2 = 0 פתרון ד':
n ≤ r ( A ) ≤ m n\leq r(A)\leq m n ≤ r ( A ) ≤ m ולכן זה לא יתכן.
נתונה בעיית ריבועים פחותים עם מטריצה A ∈ R m × n A \in \mathbb{R}^{m\times n} A ∈ R m × n
min x ‾ ∈ R n ∥ A x ‾ − b ‾ ∥ 2 2 \underset{\underline{x} \in \mathbb{R}^{n}}{\min}\left\lVert A\underline{x}-\underline{b} \right\rVert _{2}^2 x ∈ R n min ∥ A x − b ∥ 2 2 בחרו את הטענה הנכונה:m ≥ n m\geq n m ≥ n m ≤ n m\leq n m ≤ n A A t = I AA^t=I A A t = I A A t = I AA^t=I A A t = I ∞ \infty ∞
א - לאו דווקא נכון.∞ \infty ∞ A = ( 1 0 0 0 1 0 ) A=\begin{pmatrix}1 & 0 & 0\\0 & 1 & 0\end{pmatrix} A = ( 1 0 0 1 0 0 )
תרגיל (מועד א' חורף 2022)
עבור בעיית ריבועים פחותים נתון שהמטריצה A A A m m m n n n n > m n>m n > m ∞ \infty ∞ x 1 , x 2 x_{1},x_{2} x 1 , x 2 x 3 = 2 3 x 2 + 1 3 x 1 x_{3}=\frac{2}{3}x_{2}+\frac{1}{3}x_{1} x 3 = 3 2 x 2 + 3 1 x 1 ∞ \infty ∞ x 1 , x 2 x_{1},x_{2} x 1 , x 2 x 3 = 2 3 x 2 + 1 3 x 1 x_{3}=\frac{2}{3}x_{2}+\frac{1}{3}x_{1} x 3 = 3 2 x 2 + 3 1 x 1 ∞ \infty ∞ x 1 , x 2 x_{1},x_{2} x 1 , x 2 x 3 = 2 3 x 2 − 1 3 x 1 x_{3}=\frac{2}{3}x_{2}-\frac{1}{3}x_{1} x 3 = 3 2 x 2 − 3 1 x 1 ∞ \infty ∞ x 1 , x 2 x_{1},x_{2} x 1 , x 2 x 3 = x 2 + x 1 2 x_{3}=\frac{x_{2}+x_{1}}{2} x 3 = 2 x 2 + x 1
א - לא נכון כי r ( A ) < n r(A)<n r ( A ) < n
יהיו x 1 , x 2 x_{1},x_{2} x 1 , x 2
A t A ( 2 3 x 2 + 1 3 x 1 ) = 2 3 A t A x 2 + 1 3 A t A x 1 = 2 3 A t b + 1 3 A t b = A t b A^tA\left( \frac{2}{3}x_{2}+\frac{1}{3}x_{1} \right)=\frac{2}{3}A^tAx_{2}+\frac{1}{3}A^tAx_{1}=\frac{2}{3}A^tb+\frac{1}{3}A^tb=A^tb A t A ( 3 2 x 2 + 3 1 x 1 ) = 3 2 A t A x 2 + 3 1 A t A x 1 = 3 2 A t b + 3 1 A t b = A t b ולכן הוקטור הנ"ל הוא גם כן פתרון ולכן התשובה הנכונה היא ב ב ב
צירוף קמור של פתרונות למערכת משוואת הוא תמיד פתרון.
α 1 x 1 + α 2 x 2 + ⋯ + α n x n \alpha_{1}x_{1}+\alpha_{2}x_{2}+\dots+\alpha_{n}x_{n} α 1 x 1 + α 2 x 2 + ⋯ + α n x n ∑ α i = 1 \sum \alpha_{i}=1 ∑ α i = 1 ג ו-ה לא נכונים כי הם אומרים שצירוף קמור הוא אינו פתרון1 3 A t b = A t b \frac{1}{3}A^tb=A^tb 3 1 A t b = A t b A t b = 0 ⟺ A^tb=0 \iff A t b = 0 ⟺
תרגיל (מועד ב' חורף 2022)
נתונה לנו המטריצה A A A
A = ( 1 1 − 1 1 1 − 1 1 1 − 1 1 − 1 3 1 − 1 3 1 − 1 3 ) A=\begin{pmatrix}
1 & 1 & -1 \\
1 & 1 & -1 \\
1 & 1 & -1 \\
1 & -1 & 3 \\
1 & -1 & 3 \\
1 & -1 & 3
\end{pmatrix} A = 1 1 1 1 1 1 1 1 1 − 1 − 1 − 1 − 1 − 1 − 1 3 3 3 ברצונינו לתכנן בעיית L S LS L S 10 10 10 b ‾ \underline{b} b b ‾ \underline{b} b b ‾ = ( 1 1 1 − 1 − 1 − 1 ) \underline{b}=\begin{pmatrix}1\\ 1\\1\\-1\\-1\\-1\end{pmatrix} b = 1 1 1 − 1 − 1 − 1 b ‾ \underline{b} b b ‾ = ( − 1 − 1 − 1 − 2 − 2 − 2 ) \underline{b}=\begin{pmatrix}-1\\-1\\-1\\-2\\-2\\-2\end{pmatrix} b = − 1 − 1 − 1 − 2 − 2 − 2 b ‾ \underline{b} b b ‾ = ( − 1 − 1 − 1 1 1 1 ) \underline{b}=\begin{pmatrix}-1\\-1\\-1\\1\\1\\1\end{pmatrix} b = − 1 − 1 − 1 1 1 1 b ‾ \underline{b} b b ‾ = ( − 2 − 2 − 2 1 1 1 ) \underline{b}=\begin{pmatrix}-2\\-2\\-2\\1\\1\\1\end{pmatrix} b = − 2 − 2 − 2 1 1 1
נשים לב כי עמודות A A A ד היא התשובה הנכונה.