5 - Conditioning and Stability

Big-Oh Notation for Small Variables

Example

• Consider $f(n) = 4n^4 + 3n^3 - n^2 + 9n$
  • When $n \gg 1$:
  • $f(n) = O(n^4)$
• What if $0 < n \ll 1$?
  • In this case: $n > n^2 > n^3 > n^4$
  • So $f(n) = O(n)$

General Rules

• When $n \gg 1$:
  $\boxed{O(n^p) = c_p n^p + c_{p-1} n^{p-1} + \ldots + c_0}$
• When $0 < h \ll 1$:
  $\boxed{O(h^p) = c_p h^p + c_{p+1} h^{p+1} + c_{p+2} h^{p+2} + \ldots}$
• Convention: $h$ is used for small values

Causes of Inaccurate Solutions

There are two main causes:

• Bad algorithms
• The problems themselves (Nature, give up!)

Conditioning

อันนี้มาดูของ Problem themselves ก่อน

Definitions

• Well-conditioned (insensitive) problem:
  • A small change in the input data causes a reasonably small change in the solution
• Ill-conditioned (sensitive) problem:
  • A small change in the input data causes a much larger change in the solution relatively

Examples of Ill- and Well-conditioned Problems

Example 1: Computing $\cos x$ (Ill-conditioned case)

The problem: Compute $\cos x$

• Input: $x = 10^{20}\pi$

• Exact answer: $\cos(10^{20}\pi) = 1$

• What if input changes to $(10^{20} + 1)\pi$?

• Solution becomes: $\cos((10^{20} + 1)\pi) = \cos(10^{20}\pi + \pi) = -1$

• Relative change of input:
  $\frac{|(10^{20}\pi + \pi) - 10^{20}\pi|}{|10^{20}\pi|} = \frac{\pi}{10^{20}\pi} = \frac{1}{10^{20}}$

• Relative change of solution:
  $\frac{|-1 - 1|}{|1|} = 2$

• Conclusion: Ill-conditioned because small relative change to the data leads to large relative change to the solution

เปลี่ยน input จาก $10^{20}\pi$ → $(10^{20}+1)\pi$ ซึ่งเป็นแค่การเปลี่ยนไป $1/10^{20}$ ของค่าเดิม
แต่ผลลัพธ์กระโดดจาก $1$ → $-1$ เลย → Ill-conditioned

Example 2: Computing $\cos x$ (Well-conditioned case)

• Input: $x = 0.1$
• $\cos(0.1)$ is well-conditioned
• Any small changes to the input yields small change in output

Analysis:

• $\cos(0.1) = 0.1 - \frac{(0.1)^2}{2!} + \frac{(0.1)^4}{4!} - \ldots$
• $\cos(0.1 + \epsilon) = (0.1 + \epsilon) - \frac{(0.1 + \epsilon)^2}{2!} + \frac{(0.1 + \epsilon)^4}{4!} - \ldots$
• $\cos(0.1 + \epsilon) - \cos(0.1) = O(\epsilon)$

จะเห็นได้ว่าจาก Example 1 & 2 จะโชว์ว่าเป็น Ill-condition นั้นง่ายกว่ามาก เพราะว่าจะโชว์ว่าเป็น Ill- ก็โชว์แค่ one particular example

แต่จะโชว์ Well- ต้องโชว์ any small changes input causes small change to the solution which is harder

Example 3: Finding Roots of Quadratic Equations

The problem: Find the roots of $ax^2 + bx + c = 0$

Case 1: Ill-conditioned

• Roots of $x^2 - 2x + 1 = 0$ (i.e., $a = 1$, $b = -2$, $c = 1$)

• Exact root(s):
  $x^2 - 2x + 1 = 0$
  $(x - 1)^2 = 0$
  $x = 1$

• Suppose we perturb $c$ to $1 - \delta$ where $\delta > 0$ is very small:
  $x^2 - 2x + (1 - \delta) = 0$

• Roots of perturbed equation:
  $\frac{2 \pm \sqrt{(-2)^2 - 4(1 - \delta)}}{2} = \frac{2 \pm \sqrt{4 - 4 + 4\delta}}{2} = \frac{2 \pm \sqrt{4\delta}}{2} = 1 \pm \sqrt{\delta}$

• Relative change of input:
  $\frac{|(1 - \delta) - 1|}{|1|} = \delta$

• Relative change of solution:
  $\frac{|(1 \pm \sqrt{\delta}) - 1|}{|1|} = \sqrt{\delta}$

• Conclusion: Ill-conditioned because if $\delta = 10^{-16} \Rightarrow \sqrt{\delta} = 10^{-8}$

• Large change in solution compared to change in input

จาก $x^2 - 2x + 1 = 0$ ได้ root = 1
ถ้าเปลี่ยน $c$ จาก $1$ → $1-\delta$ นิดเดียว แต่คำตอบ root กระโดดเป็น $1 \pm \sqrt{\delta}$
เช่น $\delta = 10^{-16}$ คำตอบเปลี่ยนระดับ $10^{-8}$ เลย → Ill-conditioned

Case 2: Well-conditioned

• Finding the roots of $x^2 - 3x + 1 = 0$ is well-conditioned

Example 4: Solving Linear Systems $Ax = b$

Case 1: Well-conditioned

• Solving $\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} x = \begin{bmatrix} 3 \\ 4 \end{bmatrix}$ is well-conditioned
• Small changes to the matrix and/or right-hand side vector result in small changes of the solution

Case 2: Ill-conditioned

• Consider solving $\begin{bmatrix} 1 & 2 \\ 3 & 6 + \delta \end{bmatrix} x = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ where $\delta > 0$ is very small
• This is ill-conditioned

Numerical Example:

• Solution of $\begin{bmatrix} 1 & 2 \\ 3 & 6 + 10^{-8} \end{bmatrix} x = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ is $x \approx \begin{bmatrix} 2 \times 10^8 \\ -1 \times 10^8 \end{bmatrix}$
• Solution of $\begin{bmatrix} 1 & 2 \\ 3 & 6 + 10^{-9} \end{bmatrix} \hat{x} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ is $\hat{x} \approx \begin{bmatrix} 2 \times 10^9 \\ -1 \times 10^9 \end{bmatrix}$

ดูสิเปลี่ยน Input ไปนิดเดียว คือ คำตอบเพิ่มขึ้น 10 เท่า กูงงเลยล่ะ

Analysis:

• Relative change in input:
  $\frac{\left\|\begin{bmatrix} 1 & 2 \\ 3 & 6 + 10^{-9} \end{bmatrix} - \begin{bmatrix} 1 & 2 \\ 3 & 6 + 10^{-8} \end{bmatrix}\right\|_1}{\left\|\begin{bmatrix} 1 & 2 \\ 3 & 6 + 10^{-8} \end{bmatrix}\right\|_1} \approx 1.12 \times 10^{-9}$
• Relative change in solution:
  $\frac{\|\hat{x} - x\|_1}{\|x\|_1} \approx 9$

Condition Number

อันนี้ก็มาดูบ้างว่าแล้วถ้าเป็น Well condition, อันไหนดีกว่าล่ะ มันก็มี well มาก well น้อยถูก้ปะ
เพราะในทางคณิตศาสตร์ “well-conditioned” ไม่ได้มีแค่ขาวหรือดำ แต่มีระดับความ “well” อยู่ → ซึ่งวัดได้ด้วย Condition Number

Definition

• Define the condition number of a problem as the ratio of the relative change in the solution to the relative change in the input
• For example, if the problem is to compute $\cos x$, $x$ is the true input, and $\hat{x}$ is the perturbed input, then:

${\text{Condition number} = \frac{|(\cos \hat{x} - \cos x) / \cos x|}{|(\hat{x} - x)/x|}}$

Small condition number = well condition

• But the above definition is very difficult to compute for complex problems therefore
  • ถ้าเอาความหมายแบบด้านบนคือมันทำได้ยาก คนก็เลยบอก relax หน่อยละกัน
• A rough estimate or an upper bound of condition numbers over some domain of inputs are usually used instead

Conditioning of a Linear System

Problem Statement

• How sensitive is a solution $x$ to $Ax = b$ if $A$ and $b$ are perturbed?

Setup

• Suppose the true problem (with true inputs) is:
  $Ax = b$
• Perturb $A$ to $A + E$ and $b$ to $b + e$, where $E$ and $e$ are "small"
• The perturbed problem is therefore:
  $(A + E)\hat{x} = b + e$

Small Perturbation Analysis

• We consider small perturbation. That is: (LHS, and RHS เลยนะข้าง่างอะ)
  $\frac{\|(A + E) - A\|}{\|A\|} = \frac{\|E\|}{\|A\|} \leq \delta$
  $\frac{\|(b + e) - b\|}{\|b\|} = \frac{\|e\|}{\|b\|} \leq \delta$

• where $\delta > 0$ is small (say, $0 < \delta \ll 1$)

• Above are the same as: (คืออันเดียวกันข้างบน แค่ย้ายไปอีกฝั่ง)
  $\boxed{\|E\| \leq \delta \|A\|} \quad (1)$
  $\boxed{\|e\| \leq \delta \|b\|} \quad (2)$

• Assume $p$-norm is used for vectors and matrices

Derivation

Starting from the perturbed equation:
$(A + E)\hat{x} = b + e$
$A\hat{x} + E\hat{x} = b + e$
$A\hat{x} = b + e - E\hat{x}$
$\hat{x} = A^{-1}b + A^{-1}e - A^{-1}E\hat{x}$

But $A^{-1}b = x$. So:
$\hat{x} = x + A^{-1}e - A^{-1}E\hat{x}$
$\hat{x} - x = A^{-1}e - A^{-1}E\hat{x}$
$\|\hat{x} - x\| = \|A^{-1}e - A^{-1}E\hat{x}\|$

Using triangular inequality:
$\|\hat{x} - x\| \leq \|A^{-1}e\| + \|-A^{-1}E\hat{x}\|$
$= \|A^{-1}e\| + \|A^{-1}E\hat{x}\|$
$\leq \|A^{-1}\| \cdot \|e\| + \|A^{-1}\| \cdot \|E\| \cdot \|\hat{x}\|$

(using subordination and submultiplicativity ก็คือใช้ 3 - Norms)

Continuing the Analysis

From (1) and (2):
$\|\hat{x} - x\| \leq \|A^{-1}\| \cdot \delta \|b\| + \|A^{-1}\| \cdot \delta \|A\| \cdot \|\hat{x}\|$

Note that:
$\|\hat{x}\| = \|x + (\hat{x} - x)\| \leq \|x\| + \|\hat{x} - x\|$

From above:
$\|\hat{x} - x\| \leq \delta \|A^{-1}\| \cdot \|b\| + \delta \|A^{-1}\| \cdot \|A\| (\|\hat{x} - x\| + \|x\|)$

Let $\kappa(A)$ denote $\|A^{-1}\| \cdot \|A\|$.

Rewrite as:
$\|\hat{x} - x\| \leq \delta \|A^{-1}\| \cdot \|b\| + \delta\kappa(A) (\|\hat{x} - x\| + \|x\|)$
$\|\hat{x} - x\| \leq \delta \|A^{-1}\| \cdot \|b\| + \delta\kappa(A) \|\hat{x} - x\| + \delta\kappa(A) \|x\|$

Then:
$\|\hat{x} - x\| - \delta\kappa(A) \|\hat{x} - x\| \leq \delta \|A^{-1}\| \|b\| + \delta\kappa(A) \|x\|$
$(1 - \delta\kappa(A)) \|\hat{x} - x\| \leq \delta \|A^{-1}\| \|b\| + \delta\kappa(A) \|x\|$

Final Result

But $b = Ax$. So:
$\|b\| = \|Ax\| \leq \|A\| \cdot \|x\|$

From the previous slide:
$(1 - \delta\kappa(A)) \|\hat{x} - x\| \leq \delta \|A^{-1}\| \cdot \|A\| \cdot \|x\| + \delta\kappa(A) \|x\|$
$= \delta\kappa(A) \|x\| + \delta\kappa(A) \|x\|$
$= 2\delta\kappa(A) \|x\|$

Therefore:
$(1 - \delta\kappa(A)) \frac{\|\hat{x} - x\|}{\|x\|} \leq 2\delta\kappa(A)$

$\boxed{\frac{\|\hat{x} - x\|}{\|x\|} \leq \frac{2\delta\kappa(A)}{1 - \delta\kappa(A)}}$

• ผลลัพธ์สุดท้าย บอกเราว่า relative error ของคำตอบ (solution) ถูกควบคุมโดย $\delta$ (ขนาดของ input error) และ $\kappa(A)$ (condition number)
• ใจความสำคัญ
  • ถ้า $\kappa(A)$ เล็ก → well-conditioned
  • ถ้า $\kappa(A)$ ใหญ่ → ill-conditioned

Conclusion

• When $\delta$ is small, the right-hand side is an increasing function with respect to $\delta\kappa(A)$
• The relative change of the solution of a linear system depends on $\kappa(A)$ (and the relative change of the inputs $\delta$)
• The larger $\kappa(A)$ is, the larger the relative change of the solution

Matrix Condition Number

Definition

• The condition number of a nonsingular square matrix $A$ is defined to be:
  $\boxed{\text{cond}(A) = \|A\| \cdot \|A^{-1}\|}$

• If $A$ is singular, say that $\text{cond}(A) = \infty$

• Sometimes written as $\kappa(A)$

• The larger $\text{cond}(A)$ is, the more ill-conditioned the linear system is

Example 1

Compute the condition numbers in 1-norm and $\infty$-norm of:
$A = \begin{bmatrix} 2 & 0 \\ -1 & 1 \end{bmatrix}$

Solution:

• อันนี้เป็น 2x2 หา Inverse ก็ง่าย ๆ เลยอะ ใช้สูตรได้เลยจาก 05 Inverse Matrix หรือถ้ามันอย่างกว่านั้นก็ใช้ GEPP เด้อ
  $A^{-1} = \frac{1}{2} \cdot \begin{bmatrix} 1 & 0 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 1/2 & 0 \\ 1/2 & 1 \end{bmatrix}$

So:

• $\text{cond}_1(A) = \|A\|_1 \cdot \|A^{-1}\|_1 = 3(1) = 3$
  • ก็คืออิงจากการหา $\|A\|_1$ ได้จาก 3 - Norms เลยนะ
• $\text{cond}_\infty(A) = \|A\|_\infty \cdot \|A^{-1}\|_\infty = 2(3/2) = 3$

Exercise 2

Compute the condition numbers in 1-norm and $\infty$-norm of:
$A = \begin{bmatrix} 2 & -1 & 1 \\ 1 & 0 & 1 \\ 3 & -1 & 4 \end{bmatrix}$
Solution:

• เช่นเคยมันก็มีสูตรการหา $A^{-1 }$ อะนะ แต่ว่าเราจะใช้ GEPP ก็ได้ too!
  $A^{-1} = \begin{bmatrix} .5 & 1.5 & -.5 \\ -.5 & 2.5 & -.5 \\ -.5 & -.5 & .5 \end{bmatrix}$
  So:
• $\text{cond}_1(A) = \|A\|_1 \cdot \|A^{-1}\|_1 = 6(4.5) = 27$
• $\text{cond}_\infty(A) = \|A\|_\infty \cdot \|A^{-1}\|_\infty = 8(3.5) = 28$

แค่นี้เราก็ได้คำตอบแล้วว่า Exercise 2 เป็น more ill condition กว่า Example 1 55555 เพราะว่าตัวเลข Matrix Condition Number เยอะกว่านั่นเอง!

Condition Numbers in MATLAB

>> cond(A, p); % p can be 1, 2, Inf, or 'fro'
>> cond(A); % This gives the condition number in 2-norm.

Properties of Matrix Condition Number

Property 1: Lower Bound

Claim: $\text{cond}_p(A) \geq 1$

Proof:
$\text{cond}_p(A) = \|A\|_p \|A^{-1}\|_p \geq \|AA^{-1}\|_p = \|I\|_p$

But:
$\|I\|_p = \max_{x \neq 0} \frac{\|Ix\|_p}{\|x\|_p} = \max_{x \neq 0} \frac{\|x\|_p}{\|x\|_p} = 1$

Therefore: $\boxed{\text{cond}_p(A) \geq \|I\|_p = 1}$

บอกเราว่าไม่มีระบบไหน “ดีกว่า identity” ได้ ค่าต่ำสุดคือ 1 เท่านั้น

Property 2: Identity Matrix

Claim: $\text{cond}_p(I) = 1$

Proof:

• Recall $I^{-1} = I$
• So: $\text{cond}_p(I) = \|I\|_p \|I^{-1}\|_p = \|I\|_p^2 = 1$
• ($\|I\|_p = 1$ from the previous proof)

Note: Not true for Frobenius norm. E.g.: