Skip to main content
20 votes
Accepted

Relating condition number of hessian to the rate of convergence

The classic zig-zag picture is misleading since it suggests that the slow convergence is due to overshooting. But for ill-conditioned problems, convergence is still slow even on a purely quadratic ...
Nick Alger's user avatar
14 votes
Accepted

Why is the condition number of a matrix given by these eigenvalues?

In the book, the condition number refers to the matrix $A \in \mathbb{R}^{n \times n}$, not the function as you stated in the question. The condition number of a matrix $A$ is defined as $$ \kappa(A)...
durdi's user avatar
  • 763
12 votes

What is a big condition number for a matrix?

You can view a solver as a black box which maps the input (in your case, the right-hand side vector) into the output (in your case the solution). The condition number connects the relative error of ...
Carl Christian's user avatar
10 votes

Condition number of a product of two matrices

I'd like to clarify this slightly: the reasoning in user103402's answer isn't quite clear in the case where the matrices are not square, and it can make you think that something false is true as shown ...
Danica's user avatar
  • 644
9 votes

Condition number for polynomial interpolation matrix

Surely you cannot obtain any useful upper bound from $h$. If you translate all data points $x_i$ by the same amount $t$, then $h$ remains unchanged but the matrix becomes closer and closer to singular ...
8 votes
Accepted

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

Given a matrix norm induced by a vector norm of your choice, the distance of an invertible matrix $A$ to its nearest singular matrix, i.e. $\min\{\|A-B\|:\ B \text{ is singular}\}$, is known to be $\|...
user1551's user avatar
  • 141k
8 votes

Why is the condition number of a matrix given by these eigenvalues?

The book is wrong. The matrix must be normal. Existence of an eigenvalue decomposition is not enough (counter to what they claim on that page). For example, the matrix $$\begin{bmatrix} 1 & 99 \...
Nick Alger's user avatar
6 votes
Accepted

Matrix condition number and loss of accuracy

It is a rule of thumb, but there are some estimates backing that rule. Given a matrix $A∈ℝ^{n×n}$ and a vector $b∈ℝ^n$ the linear equation system ought to be solved is $$Ax=b.$$ Now we have ...
P. Siehr's user avatar
  • 3,672
6 votes
Accepted

Condition number of random matrix gets worse as dimension grows

This is correct, and is a (very famous) result of Alan Edelman's from his PhD thesis: Edelman, Alan, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9, No. 4, 543-560 (...
Igor Rivin's user avatar
  • 26.1k
5 votes
Accepted

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

Note that if $\kappa$ is the condition number (with respect to the Euclidean norm), then $$ \kappa(A) = \frac{\sigma_1(A)}{\sigma_n(A)} $$ Where $\sigma_1$ and $\sigma_n$ denote the highest and lowest ...
Ben Grossmann's user avatar
5 votes

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

The fundamental problem is that the domain is not clearly stated. We have two functions which are relevant in this context. Let $\mathcal F$ denote our set of floating point numbers. Then the relevant ...
Carl Christian's user avatar
5 votes
Accepted

Is Schur complement better conditioned than the original matrix?

Lemma. If $P$ and $Q$ are two $n\times n$ Hermitian matrices and $\operatorname{nullity}(Q)=k>0$, the minimum eigenvalue of $P+Q$ is bounded above by the $k$-th largest eigenvalue of $P$. Proof of ...
user1551's user avatar
  • 141k
5 votes

Why is the condition number of a matrix given by these eigenvalues?

$$\operatorname{cond}(A)=\dfrac{\max_{|w|=1}|Aw|}{\min_{|w|=1}|Aw|}$$using SVD we have$$A=UDV$$where $U$ and $V$ are unitary and $D$ is diagonal whose main diagonal entries are eigenvalues of $A$. ...
Mostafa Ayaz's user avatar
  • 32.5k
5 votes
Accepted

find bound on condition number of matrix given matrix norm

$100=\big\Vert A \big\Vert_2 = \sigma_1$ $101^2 = \big\Vert A \big\Vert_F^2 = \sigma_1^2 + \sigma_2^2 + ....+ \sigma_{201}^2 + \sigma_{202}^2$ $k(A) =\frac{\sigma_1}{\sigma_{n}} =\frac{\sigma_1}{\...
user8675309's user avatar
  • 10.3k
5 votes

Relative Condition Number of Atan(x) vs Atan2(y,x)

$$\operatorname{atan2}(y, x) = \arctan(\frac{y}{x}) + (\textit{quadrant fixup if } x < 0)$$ You're dividing by x. This is an ill-conditioned operation if x is near 0. To formalize things a bit, ...
Dan's user avatar
  • 15.7k
4 votes

Why does finer mesh mean worse condition number?

It is not universally true that the condition number becomes worse with a finer mesh, for example take $10u = f$. There's no good reason to solve this via FEM, but you can do it, and the condition ...
user14717's user avatar
  • 4,902
4 votes
Accepted

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

Assuming you're using the spectral norm, the condition number of $A$ is $1$. But there is no matrix with condition number less than $1$, because $$1 = \|I\| = \|M M^{-1}\| \le \|M \| \|M^{-1}\|$$ for ...
Robert Israel's user avatar
4 votes
Accepted

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

Since norms are submultiplicative only, you get the inequality $$ \kappa(A^2) \le \kappa(A)^2. $$ If $A=A^{-1}$ then $A^2=I$, but $\kappa(A)$ can be larger than one.
4 votes
Accepted

Prove that $cond(A)\ge \frac{||A||}{||A-B||}$ for any induced matrix norm

Let $z\in \ker B$ be a unit vector. It is easy to see that $$ \|Az\|=\|Az-Bz\|\le \|A-B\|. $$ On the other hand, we have $$ 1 = \|z\|=\|A^{-1}Az\|\le \|A^{-1}\|\|Az\|. $$ Therefore, we have $$ \|A^{-1}...
Myunghyun Song's user avatar
4 votes
Accepted

$\infty$-norm of a vector

It is the subordinate matrix infinity norm defined as: $$\|A\|_{\infty} =\max_{1 \leq i \leq m}\sum_{j=1}^{n}|a_{ij}|,$$ for the matrix $$A=\left( \begin{array}{ccc} a_{11}&\cdots&...
cqfd's user avatar
  • 12.3k
4 votes
Accepted

Condition number and $LU$ decomposition

Hint: Let’s drop the permutation matrix (assume $A=LU$) and note that the partial pivoting implies that the absolute values of the elements under the unit diagonal of $L$ are bounded from above by $1$...
Algebraic Pavel's user avatar
4 votes
Accepted

Why subtracting 1 is considered ill-conditioned?

When you subtract two nearly equal floating point numbers you lose precision. In your example suppose we are working with seven place base $10$ numbers and let $x=10^{-4}$. Then $t_1=1+x=1.000100$ ...
Ross Millikan's user avatar
4 votes

Is the set of matrices with constrained condition numbers a convex set?

$\def\R{\mathbb{R}}\def\T{^{\mathrm{T}}}\DeclareMathOperator{\cond}{cond}\def\paren#1{\left(#1\right)}$Denote by $S_n$ the set of all $n × n$ symmetric positive-definite matrices over $\R$. Note that ...
Ѕᴀᴀᴅ's user avatar
  • 34.4k
4 votes

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

For any $x,y$ with $\|x\|=\|y\|$ we have, with $z=Ay$, $$ \frac{\|Ax\|}{\|Ay\|}=\frac{\|Ax\|}{\|x\|}\,\frac{\|y\|}{\|Ay\|} =\frac{\|Ax\|}{\|x\|}\,\frac{\|A^{-1}z\|}{\|z\|}\leq\|A\|\,\|A^{-1}\|. $$ ...
Martin Argerami's user avatar
3 votes
Accepted

Sensitivity of the least squares method and matrix condition number

Your line of reasoning amounts to saying "because $x = A^{-1}y$, there is no condition number" to the system of equations. That's false. You can write the system in two ways. Either as $Ax = y$, or ...
Ben Grossmann's user avatar
3 votes

Relating condition number of hessian to the rate of convergence

The steepest descent method "zigzags" as it approaches a minimum. See this figure from Wikipedia. This phenomenon becomes much worse for a badly conditioned problem. The reason that the method ...
Brian Borchers's user avatar
3 votes
Accepted

multiplying a linear system by an invertible diagonal matrix

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)...
dantopa's user avatar
  • 10.4k
3 votes
Accepted

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

No, take for example $T(\epsilon) = \begin{bmatrix} 1 & 0 \\ 0 & \epsilon\end{bmatrix}$. Then $T^{+}(\epsilon) = \begin{bmatrix} 1 & 0 \\ 0 & \eta\end{bmatrix}$, where $\eta = 0$ for $\...
Pawel Kowal's user avatar
  • 2,252
3 votes

Condition number of a diagonal matrix

I mistakenly thought $\|\cdot\|$ was the $\ell^2$-norm. See below the line for the general situation. Hint: $$\|Ax\|^2=\left\|\begin{bmatrix}\lambda_1 x_1 \\ \vdots \\ \lambda_n x_n\end{bmatrix}\...
angryavian's user avatar
  • 90.8k

Only top scored, non community-wiki answers of a minimum length are eligible