Questions tagged [condition-number]

The condition number of a matrix is the ratio of the largest to the smallest singular value in the singular value decomposition of a matrix.

Filter by
Sorted by
Tagged with
7
votes
1answer
264 views

Is Schur complement better conditioned than the original matrix?

Consider the following linear system (in block form) with s.p.d. matrix: $$ \begin{pmatrix} A & B\\ B^\top & C \end{pmatrix} \begin{pmatrix} x\\y \end{pmatrix} = \begin{pmatrix} f\\g \end{...
4
votes
2answers
2k views

Relating condition number of hessian to the rate of convergence

While minimizing a lipschitz continuous strongly convex functions, the rate of convergence of gradient descent method depends on the condition number of the hessian of the function where high ...
4
votes
2answers
943 views

If $\kappa (A) > \kappa (B)$, show $\kappa (B^{-1}A) < \kappa (A)$

Let $A$ and $B$ be a toeplitz and symmetric positive definite $NxN$ matrices. If $\kappa (A) > \kappa (B)$, how to show that: $$\kappa (B^{-1}A) < \kappa (A)$$ where $\kappa $(X) is ...
4
votes
1answer
95 views

Is there any inequality between 2-norm condition number and Frobenius norm condition number for rectangular matrix?

What I have found in [1] Condition number inequality between Frobenius norm and 2-norm for square matrix, Consider a full rank matrix $X \in \mathbb{C}^{n \times m}$, $m=n$, then we can have, $$n - ...
4
votes
0answers
200 views

Minimizing the condition number of a block matrix

Let $$A = \left[ \begin{array}{ccc} & B_{(n(m+1)-m) \times (n(m+1))} & \\ \hline Z_{m \times (nm)} & | & S_{m \times n} \end{array} \right]$$ be a block ...
4
votes
0answers
135 views

Condition number of $A^{-1} B$ where $A$ and $B$ are banded Toeplitz matrices.

I'm looking at a filtering problem with feedback, which can be represented by the equation $A\underline{y} = B\underline{x}$, where $A$ and $B$ are lower triangular banded Toeplitz matrices and $\...
3
votes
3answers
4k views

Condition number of a product of two matrices

Given two square matrices $A$ and $B$, is the following inequality $$\operatorname{cond}(AB) \leq \operatorname{cond}(A)\operatorname{cond}(B),$$ where $\operatorname {cond}$ is the condition number, ...
3
votes
1answer
1k views

Condition number of a block matrix

Let $\mbox{cond} (M) := \frac{\sigma_1 (M)}{\sigma_n (M)}$ be the condition number of matrix $M$. Is $$\mbox{cond} ([A,B]) \leq \mbox{cond}(A) + \mbox{cond}(B)$$ true? And is this true for $n \times ...
3
votes
1answer
182 views

Why does finer mesh mean worse condition number?

Suppose I am working on the finite element approximation of a problem. My understanding is that the condition number of the resulting algebraic system becomes worse when the mesh becomes finer. What ...
3
votes
1answer
1k views

Condition number for polynomial interpolation matrix

We want to interpolate a function $\,f:\mathbb{R}\to\mathbb{R}$ on the interval $[0,1]$ with, say, monomials. Assume we have set $\left\{x_i\right\}_{i=0}^{n}$ of $n+1$ points $x_i\in\left[0,1\right],\...
3
votes
2answers
1k views

Condition number problem

I am given the function $$f(x) = \frac{1}{1+2x} - \frac{1-x}{1+x}$$ and I am asked the following: Explain why for $x \approx 0$ there is a numerical problem. Is the problem in the neighbourhood $x \...
3
votes
1answer
131 views

Condition number of $AA^T$ when $A$ is polynomial Vandermonde

Suppose I'm doing polynomial regression of degree $m$ $$p(x, \mathbf{w}) = w_0 + w_1x + \dotsb + w_mx^m$$ given training data $(x_1, t_1), \dotsc, (x_N, t_N)$. Suppose I'm using the loss function $...
3
votes
0answers
187 views

Matrix Solvers for High Condition Numbers

Suppose I wish to solve the following square system of equations: $$A x = b$$ Suppose that $A$ is modestly large and sparse (problem size $\sim 10^{3-4}$). Suppose that $A$ is banded primarily ...
3
votes
0answers
25 views

preconditioners for matrices arising out of PDEs

Suppose I have the heat the following one dimensional PDE for the heat equation: $$ \frac{\partial u}{\partial t } = \alpha \frac{\partial^2 u}{\partial t^2 } $$ which I discretized in the spatial ...
2
votes
1answer
6k views

Condition number of a rectangular matrix

From what I understand, the condition number of a rectangular matrix $A$ is its largest singular value divided by its smallest nonzero singular value $$\kappa(A) := \frac{\sigma_1 (A)}{\sigma_n (A)}$...
2
votes
3answers
534 views

How to measure how far a matrix is from being singular?

What would be the best mathematical tool/concept to measure how far a matrix is from being singular? Could it be the condition number?
2
votes
2answers
166 views

Different condition numbers of $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$

Let $a,b,c \in \mathbb{R}$ and $A := \begin{pmatrix} a & b \\ b & c \end{pmatrix}$ and $\det(A) \neq 0$. Find the condition number with respect to the 1-, 2- and $\infty$-norm and discuss ...
2
votes
1answer
159 views

Condition number of matrix is $1$ iff $A^TA=\alpha I$

I am trying to prove the following: The condition number $\kappa_p(A)=1$ for $A$ an matrix iff $A^TA=\alpha I$ for some scalar number $\alpha\neq 0$. I read somewhere on the internet that I ...
2
votes
3answers
51 views

What's the different between necessary, sufficient, necessary and sufficient condition?

1)The range of values of "$a$", such that $|x-2|< a$ is a necessary condition for $x^2-3x-10<0$ 2)The range of values of "$a$", such that $|x-2| < a$ is a sufficient condition for $...
2
votes
1answer
135 views

Infinite norm of a vector

While reading the book Numerical Linear Algebra by Trefethen and Bau, I came across the following example. The authors indicate that $\|J\|_{\infty} = 2$, however if I recall the definition of $\|\...
2
votes
2answers
346 views

How is $f(x)=x+1$ not backwards stable if I consider the error propagated in the addition?

Many sources claim that $f(x)=x+1$ is not backwards stable. That is, it does not give an exact solution to a slightly perturbed (or "nearby") problem. e.g. https://www.cs.usask.ca/~spiteri/CMPT898/...
2
votes
1answer
59 views

Solution to a modified linear system using two methods

I am trying to obtain the solution to a modified linear system. I am comparing two methods to solve this modified linear system, and I'm noticing some issues with one of the methods. A linear system ...
2
votes
2answers
136 views

Condition numbers: Find vector pair for which the equality holds

I have that $Ax = b$. I would like to find a vector pair $(b, \delta b)$ for which the following equality holds: $$\frac{||\delta x||_2}{||x||_2} = \kappa_2(A) \frac{||\delta b||_2}{||b||_2},$$ ...
2
votes
1answer
37 views

Discretising the Fourier Integral gives a high condition number

I have the following integral equation $$ \int_0^1 e^{-2\pi i s t} f(t)\, \text{d} t = g(s), \hspace{3em} -1/2 \leq s \leq 1/2$$ where $f$ is to be found, and $g$ is known. I believe this problem is ...
2
votes
0answers
59 views

Solving numerically a strongly stiff nonlinear ODE system with ill-conditioned Jacobian

Using Matlab, I am trying to solve numerically the following nonlinear system of ODEs: $$\begin{aligned} \dot B &= -\alpha B -\nu BV \\ \dot X &= A-\mu_1 X -c E(B)VX \\ \dot Y &= ...
2
votes
0answers
33 views

Show that $ \kappa_2(A) \leq [\kappa_1(A) \kappa_{\infty} (A)]^{1/2}$

Suppose for a matrix $ A \in \mathbb{R}^n$, we have $ \ ||A||_2 \leq ||A^TA||^{1/2}$, where $||.||$ is a norm on $\mathbb{R}^n$ associated to matrix norm on $\mathbb{R}^{n \times n}$ and $||.||_2$ is ...
2
votes
0answers
99 views

Find the relative condition number of $f(x,y) := y e^{4x^2}$ with respect to the 1-norm.

Let $f: \mathbb{R} \to \mathbb{R}$ (I guess it's supposed to be $\mathbb{R}^2 \to \mathbb{R}$) be defined by $f(x,y) := y e^{4x^2}$ Find the relative condition number of with respect to the 1-norm. ...
2
votes
1answer
147 views

Suppose ||.|| is an induced matrix norm, A is non-singular, and B is singular. Prove $\frac{1}{\kappa(A)}\leq\frac{||A-B||}{||A||}$.

$\|\cdot\|$ is the induced norm for $n\times n$ matrices in $\mathbb{C}$, with respect to some vector norm ($\mathbb{C}^n\to\mathbb{R}$). $A$ and $B$ are $n\times n$ matrices where $A$ is non-singular ...
2
votes
1answer
45 views

Measure for how singular a square matrix is in the range [0,1]

I am interested in estimating how close a square matrix is to being singular such that I can compute a value $s \in [0,1]$ where $s=1$ would mean the matrix is singular, and $s=0$ means it is as far ...
2
votes
2answers
78 views

How to choose two diagonal matrices minimizing the condition number

I have a matrix $A \in R^{n×n}$. I would like to choose two diagonal matrices $D_1,D_2 \in R^{n×n}$ such that $\text{cond}(D_1AD_2)$ should be minimal. How to provide such diagonal matrices?
2
votes
0answers
228 views

Relative condition number, Ill conditioned, Well conditioned

I'm currently learning about relative condition number (K), and how they are considered as well conditioned or ill conditioned. From my understanding, a large K value represents ill-conditioned, ...
2
votes
1answer
251 views

Find the condition number of $A$

Find the condition number of $$A = \begin{bmatrix} 0 & 0 & -10^4 & 0 \\ 0 & 0 & 0 & -10 \\ 0 & 10^{-3} & 0 & 0 \\ 10^{-2}& 0& 0& 0 \\ \end{...
2
votes
1answer
494 views

Condition number of the product of two s.p.d. matrices

The condition number for an invertible matrix $A$ is defined as follows $$\mathcal{k}(A) := \|A^{-1}\| \|A\|$$ where $\|\cdot\|$ is the Euclidean norm. If $A$ is symmetric, then $$\mathcal{k}(A)= \...
1
vote
3answers
121 views

multiplying a linear system by an invertible diagonal matrix

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 ...
1
vote
1answer
83 views

Does it hold that $\kappa(A^2) = \kappa(A)^2$?

Let $A \in \mathbb{R}^{n \times n}$ be invertible and $b\in \mathbb{R}^n$. Let $x \in \mathbb{R}^n$ be the solution of $Ax=b$. Let $\kappa(A)$ denote the condition number of matrix $A$. Does the ...
1
vote
1answer
64 views

$\text{cond}(A)\gt \text{cond}(A+B)$ for $AA^T=I$

Let $A$ a matrix such that $AA^T=I$. Is there a matrix $B$ such that $$\text{cond}(A)\gt \text{cond}(A+B)$$ If so give numerical exmples for this, otherwise prove that there isn't. The condition ...
1
vote
1answer
70 views

Is $A \mapsto A^+$ well-conditioned?

Let $A$ have reduced SVD $A = \tilde{U} \tilde{\Sigma} \tilde {V}^*$, and define the Moore-Penrose pseudoinverse of $A$ as $A^+ = \tilde{V} \tilde{\Sigma} \tilde{U}^*$. In the $l^2$ norm $\| \cdot \|$,...
1
vote
1answer
860 views

Matrix condition number and loss of accuracy

There are quite a few sources online that say something along the lines of : "As a rule of thumb, if the condition number $\kappa(A)=10^k$ then you may lose up to $k$ digits of accuracy on top of ...
1
vote
1answer
45 views

Computing the condition number of a matrix

Given$$A=\begin{bmatrix}23.89&-36.48&1.432&21.65\\-36.48&54.58&-5.193&-34.45\\1.432&-5.193&-1.0717&1.937\\21.65&-34.45&1.937&20.50\end{bmatrix}.$$ I am ...
1
vote
1answer
339 views

Finding the relative condition number given a function.

I'm teaching myself how to find the relative condition numbers and I am struggling with connecting it to something basic like scalar multiplication. For example, the first problem of my text book ...
1
vote
1answer
86 views

Compute the condition number of a $3 \times 3$ matrix.

Compute the condition number of the matrix $B$ : $$ B=\begin{bmatrix}3&7&1\\5&8&0\\6&3&2\end{bmatrix} $$ in terms of $\|\cdot\|_{1}$ and $\|\cdot\|_{\infty}$. Important: Our ...
1
vote
3answers
1k views

Sensitivity of the least squares method and matrix condition number

It is my understanding that if we have a simple linear system such as $$Ax = y$$ The condition number of $A$ provides an indication of how sensitive the solution $x$ will be in relation to changes ...
1
vote
1answer
81 views

Create a matrix with a given sparsity pattern and whose condition number is low

In Matlab, I need to create a symmetric matrix with a given sparsity pattern and whose condition number is low ($\leq 10$). The matrix is sparse (more than half of its entries are zero). From what I ...
1
vote
1answer
101 views

Condition number of a polynomial root problem

I dont't understand how the condition number is defined for a problem such as: $x^2-2xp+1=0,\ p\geq1$ Here there are two roots $x_-=p-\sqrt{p^2-1}$ and $x_+=p+\sqrt{p^2-1}$ I understand that the ...
1
vote
1answer
1k views

Condition number of a diagonal matrix

Let $\|\cdot\|$ be any norm on $\mathbb{C}^n$. Let $A\in \mathbb{C}^{n\times n}$ We define the matrix norm by $||A||=\max_{||x||=1}||Ax||$. If $A=diag(\lambda_1,...,\lambda_n)$ and it is invertible, ...
1
vote
1answer
397 views

Condition number of matrix multiplied with permutation matrix

Given a $n \times n$ matrix $A$ with condition number $1$, prove or disprove $\mbox{cond} (A) = \mbox{cond} (PA)$, where $P$ is is any permutation matrix. My attempt: $cond(A) = ||A||*||A^{-1}||$ ...
1
vote
1answer
44 views

Is the condition number of a 2x2 block symmetric matrix greater than the condition number of its upper left hand block?

Is there any known relation between cond(M) and cond(Q) when $$M=\begin{bmatrix}Q&A^T\\A&0\end{bmatrix}$$ and Q is symmetric positive definite and A is rectangular full row rank? From the ...
1
vote
0answers
32 views

Prove the inequality for Condition number of matrix

Let $ A \in \mathbb{R}^{n \times n}$ be a non-singular matrix. Let $\hat A=A+\delta A, \ \hat x=x+\delta x, \ \text{and} \ \hat b=b+\delta b$ with $Ax=b$ and $\hat A \hat x=\hat b \ $. Here $||.||$...
1
vote
1answer
124 views

Is division ill-conditioned when divisor is close to zero?

My intuition is that division of real numbers is ill-conditioned when divisor is close to zero. Is this intuition correct?
1
vote
0answers
24 views

what is the significance of $\kappa$ in the proof of inconditional stability of the Crank-Nicolson scheme

When using a centered difference approximation $$ \frac{\partial}{\partial t}u(t,x) = \frac{u(t + \Delta t/2,x) - u(t - \Delta t/2, x)}{\Delta t} + O((\Delta t)^2) $$ It is an approximation of the ...