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.
Questions tagged [condition-number]
273 questions
12
votes
3 answers
What is the practical impact of a matrix's condition number?
Let's say I am trying to solve a square linear system
$Ax = b$
for whatever reason. A perturbation $\delta b$ in $b$ will lead to a perturbation $\delta x$ in $x$, whose relative norm is bounded by the condition number of A $\kappa (A)$ according…
Bleevoe
- 123
- 1
- 4
10
votes
3 answers
Relating condition number of hessian to the rate of convergence
While minimizing a Lipschitz continuous strongly convex functions, the rate of convergence of the gradient descent method depends on the condition number of the hessian of the function, where a high condition number leads to slow convergence. Can…
user2684957
- 367
- 3
- 11
9
votes
1 answer
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)}$$
Where $\sigma_1 (A)$ is the operator norm of…
Erika
- 259
- 1
- 2
- 8
8
votes
1 answer
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{pmatrix}
$$
I'm wondering if elimination of some variables…
uranix
- 7,323
- 1
- 17
- 51
6
votes
3 answers
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, true?
Is this still true for rectangular…
2012User
- 371
- 4
- 13
6
votes
1 answer
What is a big condition number for a matrix?
The condition number of a matrix is a measure of how close a matrix is to being singular.
But, what is considered a big condition number?
Victor
- 453
- 1
- 5
- 13
6
votes
2 answers
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/notes/numericalStability.pdf on page 24.
Now, when…
makansij
- 1,503
- 1
- 17
- 41
6
votes
1 answer
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],\; i = 0,\dots, n,$ which are not uniformly…
Vlad
- 6,622
- 3
- 32
- 68
5
votes
2 answers
Prove $k(AB) \leq k(A)k(B)$ where $k(\cdot)$ denotes the condition number
Given a $n \times n$ matrix $A$ and $B$, we need to prove
$k(AB) \leq k(A)k(B)$ where $k(\cdot)$ denotes the condition number of a matrix.
Is there any thing wrong in the below proof?
$$k(AB)
= \|AB\| \cdot \|(AB)^{-1}\|
\leq \|A\| \cdot…
Learner
- 2,616
- 1
- 25
- 37
5
votes
2 answers
Relative Condition Number of Atan(x) vs Atan2(y,x)
I'm trying to think through the sensitivity of atan2 to errors in its inputs and I've run into a disconnect that I don't quite understand.
I know that you can compute the relative condition number of a differential function $f$ as:
$$\kappa(\vec{x})…
gct
- 563
- 1
- 3
- 10
5
votes
2 answers
Eigenvalue and spectral condition
Let $A=\begin{pmatrix} 1& 1 \\ a^2 &1 \end{pmatrix} \text{ with } a\in (0,\frac{1}{2}]$. Show $$cond_2(A)=||A||_2 \cdot ||A^{-1}||_2\leq 4(1-a^2)^{-1}$$ by first showing $||A||^2_2\leq||A||_1||A||_{\infty}$.
$||A||^2_2$ is the maximal eigenvalue…
user1049882
- 105
- 7
5
votes
1 answer
Is the set of matrices with constrained condition numbers a convex set?
Let $\mathbb{S}_{\tau}^{+,p}$ indicates the $p\times p$ real symmetric positive-semidefinite matrix, whose condition number, defined as the ratio of maximum eigenvalue and minimum eigenvalue, is less or equal to $\tau$. Is $\mathbb{S}_{\tau}^{+,p}$…
Tan
- 601
- 2
- 13
5
votes
1 answer
Matrices and influence of small error on their inverse matrices.
Find (nontrivial) matrix $A\in M_n$ such, that only small error in its element has small influence on inverse matrix, it means that this matrix will be different from $A^{-1}$ only little bit. Then find (nontrivial) matrix $B\in M_n$ such, that only…
Waney
- 614
- 5
- 11
5
votes
1 answer
Condition number of $2 \times 2$ block matrix in terms of the singular values of the off-diagonal blocks
If $A$ is $m \times n$ matrix such that $ m \geq n $ and $B$ is the block matrix
$$ B = \begin{bmatrix}I & A \\ A^T & 0 \end{bmatrix} $$
then what is the condition number of $B$ in terms of singular values of $A$?
abhiganit
- 51
- 1
4
votes
1 answer
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 m$ rectangular matrices? Let's consider $3$…
2012User
- 371
- 4
- 13