Condition number of a matrix

[kalleC]

Homework Statement

For a system of equations Ax = b
Let dA be a random perturbation of the matrix A

The error in

Which dA fullfills the equality

norm(A^-1 (da) x) = norm(A^-1) norm(dA) norm(x)

(The SVD of A is known)
(b is a known vector)

Homework Equations

The Attempt at a Solution

I managed to solve a somewhat similar question asking for what b and db fullfills the upper bound for K = norm(A)*norm(b)/norm(x) <= cond(A)

when b = A*V(:,1) and db = U(:,5) <-- clearly rows and columns values corresponding to the smallest singular value of A

However for this particular question I am clueless as to how to form dA to maximise the condition number so it reaches cond(A) = norm(A)*norm(A^-1)

 

[mighty2000]

which simplifies to sqrt(cond(A)) = norm(A)*norm(x)/norm(b)

Hi there,

Thank you for your question. To answer this, we need to understand the concept of condition number and how it is affected by perturbations in the matrix A.

The condition number of a matrix A is a measure of how sensitive the solution x is to small changes in the entries of A. A higher condition number means that small changes in A can result in large changes in the solution x, making the system of equations more difficult to solve.

In this case, we are looking for a perturbation dA that maximizes the condition number, which means that it will have the greatest effect on the solution x. To do this, we can use the singular value decomposition (SVD) of A.

The SVD of A is given by A = UΣV^T, where U and V are orthogonal matrices and Σ is a diagonal matrix with the singular values of A on the diagonal. The condition number of A is then given by the ratio of the largest and smallest singular values of A, i.e. cond(A) = σ1/σn.

To maximize the condition number, we want to find a perturbation dA that affects the smallest singular value of A (σn) the most. This can be achieved by setting dA = U(:,n)V^T(:,n), where U(:,n) and V^T(:,n) are the columns of U and rows of V^T corresponding to the smallest singular value σn.

Substituting this dA into the original equation, we get:

norm(A^-1 (dA) x) = norm(A^-1) norm(dA) norm(x)

norm(A^-1 U(:,n)V^T(:,n) x) = norm(A^-1) norm(U(:,n)V^T(:,n)) norm(x)

Since U and V are orthogonal matrices, their norm is equal to 1. Also, norm(A^-1) = 1/σ1, so the equation becomes:

norm(A^-1 U(:,n)V^T(:,n) x) = 1/σ1 * norm(U(:,n)V^T(:,n)) * norm(x)

= 1/σ1 * norm(U(:,n)) * norm(V^T(:,n)) * norm(x)

= 1/σ1 * 1 * 1 * norm(x) =