0
$\begingroup$

I am trying to solve a linear system $Ax = b$ where

$$ A =\begin{bmatrix} 2& 9& 2& 1& 4& 1& 0& 0& 0 \\ 9& 65& 9& 1& 4& 1& 0& 0& 0 \\ 2& 9& 2& 1& 4& 1& 0& 0& 0 \\ 1& 1& 1& 2& 5& 2& 1& 8& 1 \\ 4& 4& 4& 5& 17& 5& 1& 8& 1 \\ 1& 1& 1& 2& 5& 2& 1& 8& 1 \\ 0& 0& 0& 1& 1& 1& 1& 8& 1 \\ 0& 0& 0& 8& 8& 8& 8& 64& 8 \\ 0& 0& 0& 1& 1& 1& 1& 8& 1 \end{bmatrix} $$ and A is ill-conditioned and singular. I have decided to solve the system in a least-squared sense by QR factorization of $A$ into the product of the orthogonal matrix $Q$ and the upper triangular matrix $R$, using the Householder method. However during the process of QR factorization I noticed that some diagonal elements of $R$, shown below

$$ \begin{bmatrix} -1.03440804e+01& -6.17744617e+01& -1.03440804e+01& -3.57692501e+00& -1.25675744e+01& -3.57692501e+00& -5.80041893e-01& -4.64033515e+00& -5.80041893e-01\\ 0.00000000e+00& -2.42675892e+01& -1.56036495e-16& 4.69608314e+00& 1.50964785e+01& 4.69608314e+00& 1.22928468e+00& 9.83427745e+00& 1.22928468e+00\\ 0.00000000e+00& 0.00000000e+00& -2.05323646e-15& -2.64610272e-01& -2.64610272e-01& -2.64610272e-01& -2.64610272e-01& -2.11688218e+00& -2.64610272e-01\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& -8.19038412e+00& -8.19038412e+00& -8.19038412e+00& -8.19038412e+00& -6.55230729e+01& -8.19038412e+00\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& -2.04418448e-15& -4.82955896e-15& -4.80506304e-15& -3.84405043e-14& -4.80506304e-15\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 2.48208983e-15& 2.53068420e-15& 2.02454736e-14& 2.53068420e-15\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& -1.09555726e-17& -8.76445805e-17& -1.09555726e-17\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 4.96874996e-32& 6.21093745e-33\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00 \end{bmatrix} $$

are so small, e.g. $βˆ’2.05323646π‘’βˆ’15$, that they seem to have been zero-ed out during the process.

Therefore I was wondering what this says about the suitability of the QR factorization for solving such a linear systems. Would GMRES for example be a better method?

Update

As @copperhat pointed out the original matrix has repeated columns, so here is another matrix

$$ A = \begin{bmatrix} 53 & 83 & 101 & 119 & 133 & 161 & 0 & 0 & 0 \\ 83& 130& 158& 187& 209& 253& 0& 0& 0 \\ 101& 158& 194& 221& 247& 299& 0& 0& 0 \\ 119& 187& 221& 1130& 1222& 1464& 1189& 1247& 1363 \\ 133& 209& 247& 1222& 1322& 1584& 1271& 1333& 1457 \\ 161& 253& 299& 1464& 1584& 1898& 1517& 1591& 1739 \\ 0& 0& 0& 1189& 1271& 1517& 1681& 1763& 1927 \\ 0& 0& 0& 1247& 1333& 1591& 1763& 1849& 2021 \\ 0& 0& 0& 1363& 1457& 1739& 1927& 2021& 2209 \end{bmatrix} $$

with non-repeating columns AFAICS, but whose facrorization produces an $R$ matrix

$$ \begin{bmatrix} -2.78693380e+02& -4.37505907e+02& -5.21540914e+02& -2.06983388e+03& -2.24480036e+03& -2.69183646e+03& -1.99061420e+03& -2.08771733e+03& -2.28192360e+03\\ 0.00000000e+00& 7.62349509e-01& -6.86114558e+00& 8.40100714e+02& 8.99300515e+02& 1.07385052e+03& 1.15108324e+03& 1.20723365e+03& 1.31953445e+03\\ 0.00000000e+00& 0.00000000e+00& -7.22714360e-13& -4.79826007e+01& -5.12917456e+01& -6.12191802e+01& -6.78374700e+01& -7.11466148e+01& -7.77649046e+01\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 2.20128739e+03& 2.35310031e+03& 2.80853908e+03& 3.11216493e+03& 3.26397785e+03& 3.56760370e+03\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 3.48673102e-13& 6.79970467e-13& 1.88237140e-13& 3.01758615e-13& 6.42902231e-14\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 2.35448168e-13& -6.69362848e-15& -1.54702891e-14& -4.32877439e-14\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& -1.64085428e-13& 1.81948529e-14& -3.15564299e-14\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& -2.14238677e-13& 7.10530473e-15\\ 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& 0.00000000e+00& -1.66984181e-13 \end{bmatrix} $$

with elements in the upper triangular part of the matrix zero-ed out.

$\endgroup$
6
  • $\begingroup$ GMRES uses QR, so I am not sure how that would improve things. Without more knowledge, you won't do much better than QR. $\endgroup$
    – copper.hat
    Commented Jun 16 at 20:00
  • $\begingroup$ @Moo I used numpy, but you can see that the result of the website you linked is not upper triangular i.e. many elements in the upper triangular part of $R$ are zero-ed out. $\endgroup$
    – Olumide
    Commented Jun 16 at 23:13
  • $\begingroup$ What are you expecting exactly, there 3 rows that are repeated, so there is really no surprise with fp arithmetic? $\endgroup$
    – copper.hat
    Commented Jun 17 at 0:16
  • $\begingroup$ @copper.hat Thanks for the observation. I have provided an alternative matrix the factorization of which produces a similar problem. $\endgroup$
    – Olumide
    Commented Jun 17 at 0:46
  • 1
    $\begingroup$ You could take the SVD decomposition, keep the non-too small singular values (and associated singular vectors), then "reconstruct" your matrix from that. $\endgroup$
    – Jean Marie
    Commented Jun 17 at 1:02

0

Reset to default

You must log in to answer this question.