Precision of solutions given condition number of matrix (floating point)

Question

I have a question on which I am stuck. If someone could point me in the right direction, I would appreciate it.

I did poorly on my last midterm with a question similar to this one so I'd like to be able to understand the concept in addition to help towards the answer so that I can do better on the final exam.

Thanks in advance.

Answer 1

The standard approach to error analysis of linear systems is to consider that the given system represents any of the systems

(A + ΔA) * (x + Δx) = b + Δb

where ΔA and Δb have entries of relative size μ = 5 * 10^-d, so that

||ΔA|| ∼ μ * ||A|| and ||Δb|| ∼ μ * ||b||.

The idea being that the solution found will represent the exact solution of a perturbed system with perturbations in the bounds given.

---

By standard manipulations of truncated geometric or Neumann series

(A + ΔA) * Δx = Δb - ΔA * x

and ignoring all second order terms,

Δx ≃ A^-1 * Δb - A^-1 * ΔA * x = A^-1 * Δb - A^-1 * ΔA * A^-1 * b

so that

||Δx|| ≃ ||A^-1|| * ||Δb|| + ||A^-1|| * ||ΔA|| * ||x|| ≦ μ * (||A^-1|| * ||b|| + κ * ||x||)

||Δx|| ≦ 2 * μ * κ * ||x||

The relative error of x, ||Δx||/||x||, which will determine the number of valid digits in x, is about or smaller than 2 * μ * κ. Per assignment, this has to be smaller than 5 * 10^-e, or

2 * κ ≦ 10^d-e.

and with the specific formula for κ,

2 * λ * n^α ≦ 10^d-e.