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

Uncertainty Principle in Kernel-based Interpolation

If one wants to interpolate or reconstruct a function $f:\Omega\to\mathbb{R},\,\Omega\subset\mathbb{R}^d,\, d>1$ on a finite Set $X_n:=\{x_1,\ldots,x_n\}\subset\Omega$ using translates of a ...
Max Stuthmann's user avatar
0 votes
0 answers
20 views

Show that if $A \mathbf{x} = \mathbf{b}$, then $\text{cond}_p(\mathbf{A}) \geq \frac{\|A\|_p\|x\|_p}{\|b\|_p}$

I have this simple little question to show that the above inequality holds with respect to the p-norm (i.e. the norm defined: by $\|x\|_p = \left( \sum_{i=1}^{n} |x_i|^p \right)^{\frac{1}{p}}$). I ...
isobariccc's user avatar
0 votes
1 answer
38 views

Quantity reflecting ratio of largest vector element to smallest vector element

Given a vector $v \in \mathbb{R}^n$, is there a well known quantity equal or relating to $$ \frac{\max_j \vert{v_j}\vert}{\min_j \vert{v_j}\vert}? $$ I have noted that this quantity is coordinate-...
MikeEVMM's user avatar
1 vote
0 answers
45 views

Prove that the condition number of the stiffness matrix in Laplace equation is bounded by $h^{-2}$

I'm a little stuck trying to estimate a condition number in FEM context. I would like to prove the following: Consider the stiffness matrix $K$ for piecewise linear functions on a quasi-uniform mesh ...
Rodrigo Z's user avatar
0 votes
0 answers
24 views

Adding random noise to an ill-posed problem

Suppose I have found a (finite) solution $x$ to an ill-posed problem, e.g. \begin{equation} b = A x \end{equation} where $A$ is a $N\times N$ matrix with a large condition number, $b$ is a vector ...
knuth's user avatar
  • 21
1 vote
0 answers
74 views

Evaluate $f(x)=(1−\cos(x))/x$ for arguments $0<x≪1$

How would one usefully evaluate the function $f(x)=\frac{1-\cos (x)}{x}$ for arguments $0<x \ll 1$ evaluate? Calculate $f\left(10^{-4}\right)$ with an error smaller than $10^{-10}$. Unfortunately, ...
Euler007's user avatar
  • 130
3 votes
1 answer
84 views

Build matrix from existing vectors such that condition number of matrix is minimal

I have a set of $K\gg1$ vectors, each belonging to $\mathbb{R}^N$, where $N\in\mathbb{N}, N> 2$. My goal is to select a subset of $M < K$ vectors from this set of $K$ vectors in order to form a ...
Bulbasaur's user avatar
  • 157
0 votes
0 answers
45 views

Condition number for non-negative least squares

If I want to analyze the stability of a non-negative least squares problem $||Ax-b||_2^2, x\ge0$, how can I measure the stability of the system? If it was a regular least squares problem, then I can ...
MRm's user avatar
  • 101
0 votes
0 answers
41 views

How to compute the condition number for non-linear systems?

I've been studying numerical methods for solving systems of equations, and I came across the concept of the condition number for linear systems. I understand that the condition number is used to ...
amir abbas 's user avatar
0 votes
2 answers
245 views

Prove that condition number of a matrix increases in its dimension

This is my first time asking a question here. Thus, I apologise in advance if it is not articulated correctly or something else turns out to be wrong with it. Before asking the question itself, ...
nura khazhimurat's user avatar
1 vote
1 answer
84 views

Alternate definition of condition number

I am trying to understand if the condition number of a matrix $A$ can be defined as $\left(\frac{\Delta x}{x}\right) / \left(\frac{\Delta b}{b}\right)$ under the following conditions: $$ Ax = b, \...
amir abbas 's user avatar
2 votes
1 answer
100 views

If $L$ is a positive semi-definite matrix and all elements in each row add up to 0, How to prove that the inf-norm of $(I+L)(I+L+L^2)^{-1} \leq 1$?

Assuming that the L is a positive semi-definite matrix and $$ \sum\limits_{j=1}^{N} L_{i,j} = 0. \quad for \; i = 1,...,N.$$ I want to prove that $\|(I+L) (I+L+L^2)^{-1}\|_{\infty} \leq 1$, I have ...
Owen Jun's user avatar
0 votes
1 answer
55 views

Condition number and commutators

Suppose that $A,B$ are two positive $n \times n$ complex matrices. Consider the operator $$ A + i B $$ which is not necessarily normal. However, if $\lbrack A, B \rbrack = 0$ then $A + i B$ is normal....
Frederik Ravn Klausen's user avatar
0 votes
0 answers
18 views

Comparing results of linear systems based on conditions

Say I have two regular matrices $A, A' \in \mathbb{R}^{n \times n}$, two right hand sides $b, b' \in \mathbb{R}^{n}$ and two vectors $c, c' \in \mathbb{R}^{n}$. In my algorithm I want to perform a ...
hfhc2's user avatar
  • 171
0 votes
0 answers
32 views

Compare the condition number for the least square problem matrix

I am working on a problem with the following matrix $$G=\begin{pmatrix}I&A\\ A^T&0 \end{pmatrix}$$ where $A\in\mathbb{R}^{m\times n}$ and $m>n$ with full column rank. Then by rescaling, ...
James Chiu's user avatar
1 vote
0 answers
109 views

Bound on minimum perturbation of eigenvalues, based on condition number

Problem: This problem comes from a past Ph.D. qualifying exam at my institution. Let $\newcommand{\R}{\mathbb{R}} \newcommand{\l}{\lambda} A \in \R^{n \times n}$ be of full rank and diagonalizable as ...
PrincessEev's user avatar
  • 43.4k
0 votes
1 answer
67 views

Derivation of the matrix condition number of linear equations

When I was reading the derivation of the matrix condition number for linear equations on Wikipedia, $||\textbf{b}||$ can be directly replaced by $||\textbf{Ax}||$ as the non-singular square matrix is ...
tyrela's user avatar
  • 61
2 votes
1 answer
156 views

Is there a stable algorithm for every well-conditioned problem?

Reading these notes on condition numbers and stability, the summary states: If the problem is well-conditioned then there is a stable way to solve it. If the problem is ill-conditioned then there is ...
Thanks for flying Vim's user avatar
0 votes
1 answer
75 views

Evaluation of linear system conditioning

I am working in Matlab trying to solve a wider problem, that led to 2 linear systems \begin{equation} A_1 x = b_1^0 \end{equation} \begin{equation} A_2 x = b_2^0 \end{equation} The matrices and ...
Jason Burton's user avatar
2 votes
1 answer
300 views

Condition number change in Cholesky matrix decomposition [closed]

Give a symmetric positive definite matrix $A$ that has a LDLT decomposition $A = L D L^{\top}$, why is the condition number of $A$ not less than that of matrix $D$, i.e., $\mbox{cond} (A) \geqslant \...
Sizhe Ding's user avatar
1 vote
1 answer
57 views

Bound the Condition Number

Let $\mathbf{A} \in \mathbb{C}^{n \times n}$ be a non-zero matrix with Schur decomposition $\mathbf{A}=\mathbf{U}(\boldsymbol{\Lambda}+\mathbf{N}) \mathbf{U}^*$ where $\mathbf{U}$ is unitary, $\mathbf{...
Kai Yue's user avatar
  • 89
0 votes
1 answer
102 views

Conditioning of Triangular Systems

I tried this exercise from the book numerical matrix analysis by llse. C. F. Ipsen of section 3.3 (iii). Let $A \in \mathbb{R}^{n \times n}$ be a matrix upper triangular and nonsingular. I have to ...
Gustavo Andres Pava Parra's user avatar
0 votes
1 answer
103 views

Bound on the condition number of a PSD matrix

Suppose $x_s$ is a $d$ dimensional vector which are features in the regression model. Values in the vector $x_s$ are controlled or uncontrolled. For example, the first element might be chosen by a ...
Amin's user avatar
  • 85
0 votes
1 answer
104 views

Advice regarding solving ill-conditioned systems

I start from a well-conditioned linear system $AX=B$ where $A$, $X$ and $B$ are complex square matrices of the same shape ($M$,$M$) and cond(A)=1 Then I need to ...
Ziofil's user avatar
  • 1,580
1 vote
0 answers
61 views

Find maximum condition number of symmetric five-diagonal matrix

Let $A$ be a five-diagonal matrix: $$ A = \begin{bmatrix} 1 & a & b & & \cdots & & & & \\ a & 1 & a & b& \cdots & & & & \\ b & a &...
Carlos Adir's user avatar
  • 1,292
2 votes
1 answer
309 views

What exactly is a multigrid preconditioner?

Background: In preconditioned Krylov subspace (KSP) methods (e.g. PCG, PGMRES etc.), a matrix $\boldsymbol{M \approx A}$ called preconditioner is required so that a new set of linear systems, e.g. $\...
Freewill's user avatar
1 vote
0 answers
23 views

Bound on elementwise condition number in Higham

In chapter 7 of the book "Accuracy and Stability of Numerical Algorithms" by Higham there is an upper bound for the relative error of solution of linear system in terms of elementwise error. ...
Mrs Robinson's user avatar
1 vote
0 answers
83 views

Comparison at the condition numbers of the matrices

We have the matrix $M_1=\begin{pmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2\end{pmatrix}$ and its condition numbers are $\text{cond}_1=\|M_1\|_1\|M_1^{-1}\|_1=4\cdot 2=8$ and $\...
Mary Star's user avatar
  • 13.9k
1 vote
0 answers
60 views

Minimizing the condition number of matrix-valued function

We have the matrix \begin{equation*}M_a=\begin{pmatrix}a & 1000a \\ 0.5 & 0.5\end{pmatrix}, \qquad a\in \mathbb{R}\setminus\{0\}\end{equation*} I want to calculate the condition number exactly ...
Mary Star's user avatar
  • 13.9k
1 vote
0 answers
149 views

Error bounds for perturbation of linear system input

I'm trying to determine an upper bound for the relative error when solving a linear system with a perturbed input. Particularly, I consider a linear system of the form: \begin{equation}Ax = b\end{...
jackphen's user avatar
  • 117
4 votes
1 answer
356 views

Condition number of random matrix gets worse as dimension grows

I observed experimentally that, when generating (pseudo) random matrices, their condition number increases with the dimension. Why? When using the norm induced by the Euclidean norm for vector spaces, ...
iamanoob's user avatar
  • 251
0 votes
1 answer
109 views

Condition number of subset of columns of a matrix

I have the following question. Let $A \in \mathbb{R}^{n \times m}$, with $n < m$, and let the columns of $A$ have unit $\ell_2$ norm. Say we select a set of indexes $I \subset \{0,1,\dots, m-1\}$ ...
ikiga1's user avatar
  • 3
0 votes
0 answers
103 views

Conceptual meaning of eigenvectors and eigenvalues

Can someone provide an intuitive/conceptual explanation for eigenvalues and eigenvectors? I know the mathematical definition $$Ax= \lambda x$$ which means that if x is an eigenvector, then it is only ...
dumjo's user avatar
  • 1
0 votes
0 answers
66 views

Sensitivity in matrix multiplication $C=AB$ - condition number of $A$

Let both $A,B\in\mathbb{R}^{n \times n}$ and positive definite. I know the condition number for $A$ in $Ax=b$ quantifies the sensitivity in this problem. What I am wondering about is if the condition ...
kampfkoloss's user avatar
1 vote
0 answers
80 views

On the 2-norm convergence rate of steepest descent method

When minimizing $f(x)=\frac{1}{2}x^THx\quad (H>0)$ , the steepest descent method derives the iteration $$x_{k+1}=x_k-\frac{x_k^TH^2 x_k}{x_k^TH^3 x_k}Hx_k$$. The question is to prove the following ...
Oolong Milktea's user avatar
-1 votes
1 answer
30 views

Upper bound on $\lambda_{max}(V_t)/\lambda_{min}(V_t)$, where $V_t = I + \sum_{i=1}^{t-1} x_i x^T_i$

Consider a matrix $V_t = I_{d\times d} + \sum_{i=1}^{t-1} x_i x^T_i$, where $x_i \in \mathbb{R}^d$ and $\|x_i\|_2 \leq 1$. Is it possible to find upper bound (in terms of $d$ and $t$) for the ratio ...
melatonin15's user avatar
0 votes
2 answers
56 views

Proof that $\Delta A := -\sigma_n u_n {v^T}_n$ is the smallest possible perturbation such that $A + \Delta A$ is singular.

I'm studying the peoperties of the SVD decomposition $A = U\Sigma V^T$ and have run into the following statement: $\Delta A := -\sigma_n u_n {v^T}_n $ is the smallest possible perturbation such that $...
Maxime's user avatar
  • 13
0 votes
0 answers
60 views

Best algorithm to calculate the condition number of a matrix

The condition number of a matrix $A$ is $\kappa(A)=\|A\|\|A^{-1}\|$. What is the best algorithm to calculate it?
user avatar
0 votes
1 answer
224 views

Is there any similar concept to condition number for singular matrices?

according to Wikipedia conditioning is the rate at which a function changes in response to small changes in its inputs, and the condition number associated with the linear equation $Ax = b$ gives a ...
user avatar
1 vote
2 answers
167 views

Estimate the condition number in the second norm of the matrix An

Let $A_{n}$ be a matrix of size $n$ for $n \geq 1$, and a structure: $$ A_{n}=\left[\begin{array}{cccccccc} \sqrt{21} & 1 & 0 & 0 & \ldots & 0 & 0 & 0 \\ 0 & \sqrt{21} &...
Tariro Manyika's user avatar
4 votes
1 answer
195 views

Prove that $\kappa (A) = \sup\Big\{ \frac{||Ax||}{||Ay||},\ ||x|| = ||y||\Big\}$.

I am trying to prove this for my numerical analysis class. This is from chapter 4.4 of Kincaid and Cheney's book. So far I haven´t got any good idea. I have tried $$ \|A\| \|A^{-1}\| = \sup \|A\frac{u}...
jushou1302's user avatar
1 vote
1 answer
57 views

Finding "more dependent" columns of an ill-conditioned square matrix

I need a way to determine which columns of an ill-conditioned square matrix, $A$, are "less independent", and therefore could be said to be more responsible for low eigenvalues. Eigen/SVD ...
Gillespie's user avatar
  • 121
6 votes
2 answers
302 views

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 ...
gct's user avatar
  • 593
5 votes
2 answers
164 views

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||...
user1049882's user avatar
-1 votes
1 answer
83 views

Prove that the condition number $c(A^k) \leq c(A)^k$ for every positive integer $k$ and invertible matrix A. [closed]

I'm not sure where to start here other than $c(A) = \| A \| \|A^{-1} \|$. How does this compare to $c(A^k)$?
gus f's user avatar
  • 366
3 votes
1 answer
195 views

Condition number of block matrix

Given a block matrix: $$A= \begin{bmatrix} D & E^T \\ E & 0 \end{bmatrix} , $$ where $D$ is a diagonal, positive entry matrix and $E$ is an incidence matrix of a graph, how is the condition ...
SilvioM's user avatar
  • 1,248
0 votes
0 answers
183 views

Condition number for the sum of two numbers

The condition number for the sum of two numbers $a$ and $b$ is $K=\frac{|a|+|b|}{|a+b|}$. But if I have $a=10$ and $b=-10$, I know that their difference is exactly $0$, so I have in practice no error, ...
bobinthebox's user avatar
0 votes
1 answer
37 views

Cond(PA)=Cond(A)

I want to proof the following equation. A is a nxn regular matrix and P a permutation Matrix $$cond_2(PA)=cond_2(A)$$ So the spectral norm of $||P||=1$ so $cond(PA)=||PA|| \cdot ||(PA)^{-1}||$ I tried ...
Walter Frosch's user avatar
0 votes
1 answer
3k views

condition number and singular values

Let $m \geq n$ and $A \in \mathbb{R}^{m\times n}$. Let $\sigma_1,\dots, \sigma_n \geq 0$ be the singular values of $A$. We know that if $r$ is the rank of $A$, then $\sigma_1,\dots, \sigma_r$ are ...
yf297's user avatar
  • 69
1 vote
1 answer
206 views

How to prove the condition number $\kappa(P) = n$?

I recently have been considering the Sylvester matrix equation given by $AX-XB = C$, where the rank of $C$ is lower than $X$, and $A$ is a diagonal matrix, and $B$ is defined as follow \begin{equation}...
xiuhua's user avatar
  • 441

1
2 3 4 5 6