1

I need to solve the following equation using Givens Rotation:

$$ A\cdot x = b $$

Correction: I need to solve:

$$ ||A\cdot x - b || \to \min $$

with $$A = \begin{bmatrix} 1 & 1 \\ -2 & -7 \\ 0 & -5 \\ \end{bmatrix}$$ and $$b= \begin{bmatrix} 1 \\ {-13 \over 2} \\ {-5 \over 2} \end{bmatrix} $$

Using Givens Rotation I get to the equation: $$ Q^T\cdot A\cdot x = Q^T \cdot b $$

$$ \begin{bmatrix} -2.2361 & -6.7082 \\ 0 & 5.4772 \\ 0 & 0 \\ \end{bmatrix} \cdot x = \begin{bmatrix} -6.2610 \\ 3.1038 \\ 0.8165 \\ \end{bmatrix} $$

The numbers are from matlab, but they are the same as the exact results on my paper. But I don't understand the last row. There it says:

$$ 0 \cdot x_1 + 0 \cdot x_2 = 0.8165 $$

What am I missing here?

Ignoring the last row, and using back substitution I get the same results for $x_1$ and $x_2$ as I did with solving $A^TAx = A^Tb$.

Angelo.Hannes
  • 281
  • Since $Ax=b$ cannot hold for any $x$ if $b$ is not in the range of $A$, $Q^TAx=Q^Tb$ cannot hold for any $x$ either. Recall, that you want to solve $|b-Ax|=\min_x$ instead of $Ax=b$. – Algebraic Pavel Jun 05 '14 at 11:05

1 Answers1

1

Minimizing $\|Ax-b\|$ is equivalent to minimizing $\|Q^T(Ax-b)\|$. This norm is minimal if $$ \begin{bmatrix} -2.2361 & -6.7082 \\ 0 & 5.4772 \\ \end{bmatrix} \cdot x = \begin{bmatrix} -6.2610 \\ 3.1038 \\ \end{bmatrix} $$ thus ignoring the third row of your system. Let $\hat x$ be the solution of this system.

Then the third row gives you the residual in the equation: $$ \|A\hat x - b\|= 0.8165. $$ This is the minimal residual you can obtain, any other vector $x$ will yield a larger residual.

daw
  • 49,113
  • 2
  • 38
  • 76