let $Ax = b$ be a linear n by n system
if we multiply this system by a non-singular diagonal $D$ I can say that the new system still has the same solution as the previous one , right ?
I ran some tests on matlab and noticed that the condition number stays all the time the same but our teacher claims that by this method we can make the condition number smaller of the system and he didn't explain why
can someone please clarify or give me an example where it is true ? thanks !
On
we have $Ax=b$ we change this to $$ DAx = b. $$ This will be solvable if $A$ and $D$ are invertible since $$ (DA)^{-1} = A^{-1}D^{-1} $$ In terms of condition numbers, suppose $D=A^{-1}$ then the new system is $$ x=b $$ which is nicely conditioned. So, yes, the condition number can change.
On
Regarding the solution space question, multiplying both sides of this equation by a non-singular diagonal matrix corresponds to multiplying each equation in a system of linear equations by some non-zero integer. Looking at it that way, it is clear that the solution space stays the same. As an example, the system
$$x+y=7$$ $$x+2y=10$$
has the same solutions as
$$2x+2y=14$$ $$3x+6y=30$$
Original linear system $$ \mathbf{A}x = b $$ with the matrix $\mathbf{A}\in\mathbb{C}^{n\times n}$, and the data vector $b\in\mathbb{C}^{n}$ is not in the null space $\mathcal{N}\left(\mathbf{A}\right)$. The least squares solution defined as $$ x_{LS} =\left\{ x \in \mathbb{C}^{n} \colon \lVert \mathbf{A}x - b \rVert_{2}^{2} \text{ is minimized} \right\} $$
Introduce a set of weighting factors $w_{k}$ in the form of an invertible diagonal matrix $\mathbf{D}\in\mathbb{C}^{n\times n}$. $$ \mathbf{D} = \left[ \begin{array}{ccccc} \sqrt{w_{1}} \\ & \sqrt{w_{2}} \\ & & \ddots &\\ & & & \sqrt{w_{n}} \end{array} \right] $$ The weighted linear system is expressed as $$ \mathbf{D}\, \mathbf{A}x = \mathbf{D} \, b $$ The least squares solution is defined as $$ \tilde{x}_{LS} =\left\{ \tilde{x} \in \mathbb{C}^{n} \colon \lVert \mathbf{D}\, \mathbf{A}\,x - \mathbf{D} \, b \rVert_{2}^{2} \text{ is minimized} \right\} $$
Establish the normal equations: $$ \left( \mathbf{D} \, \mathbf{A}\right)^{T} \, \mathbf{D} \, \mathbf{A} \, x = \left( \mathbf{D} \, \mathbf{A}\right)^{T} \, \mathbf{D} \, b \qquad \Rightarrow \qquad \mathbf{A}^{T} \, \mathbf{W} \, \mathbf{A} \, x = \mathbf{A}^{T} \, \mathbf{W} \,b $$ Notice $$ \text{rank } \mathbf{A} = \text{rank } \left( \mathbf{D} \, \mathbf{A} \right) $$ The weighting does not affect the existence or uniqueness of solutions. The solution is $$ \tilde{x}_{LS} = \left( \mathbf{A}^{T} \, \mathbf{W} \, \mathbf{A} \right)^{-1} \mathbf{A}^{T} \, \mathbf{W} \, b. $$
Example
From Data Reduction and Error Analysis for the Physical Sciences, 1e, by Philip Bevington, table 6.1: $$ \begin{align} \mathbf{A} x &= b \\ \left[ \begin{array}{cc} 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & 4 \\ 1 & 5 \\ 1 & 6 \\ 1 & 7 \\ 1 & 8 \\ 1 & 9 \\ \end{array} \right] % \left[ \begin{array}{cc} a_{0} \\ a_{1} \end{array} \right] % &= % \frac{1}{10} \left[ \begin{array}{cc} 156 \\ 175 \\ 366 \\ 438 \\ 582 \\ 616 \\ 642 \\ 704 \\ 988 \end{array} \right] % \end{align} $$ The least squares solution is $$ \left[ \begin{array}{cc} a_{0} \\ a_{1} \end{array} \right]_{LS} = \frac{1}{360} \left[ \begin{array}{cc} 1733 \\ 3387 \end{array} \right] \approx \left[ \begin{array}{cc} 4.81389 \\ 9.40833 \end{array} \right] $$ Introduce the weighting factors $$ \mathbf{W} = \left[ \begin{array}{ccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \sqrt{2} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \sqrt{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \sqrt{5} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \sqrt{6} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \sqrt{7} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \sqrt{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ \end{array} \right] $$ and the least squares solution becomes $$ \left[ \begin{array}{cc} \tilde{a}_{0} \\ \tilde{a}_{1} \end{array} \right]_{LS} \approx \left[ \begin{array}{c} 4.27364 \\ 9.49364 \end{array} \right] $$