SME
Numerical Methods for Engineers · Problem type
Condition number of a matrix
Use this for “Find the condition number of A = [[1, 1], [1, 1.01]] in the row-sum norm. Is A ill-conditioned?”
Diagram
D = a₁₁a₂₂ − a₁₂a₂₁
D = 1 × 1.01 − 1 × 1 = 1.01 − 1
D = 0.01
Down the main diagonal, take away the other diagonal
This is an example. Type your own values to start a new problem.
A
=
a₁₁
a₂₁
a₁₂
a₂₂
D
Determinant of A
worked out (not typed)
‖A‖∞
Row-sum norm of A
worked out (not typed)
‖A⁻¹‖∞
Row-sum norm of A⁻¹
worked out (not typed)
κ∞
Condition number
worked out (not typed)
log₁₀ κ
Digits lost
worked out (not typed)
Formulas
D
=
a₁₁
×
a₂₂
−
a₁₂
×
a₂₁
0.01 = 1 × 1.01 − 1 × 1
‖A‖∞
=
max(|
a₁₁
|
+
|
a₁₂
|,
|
a₂₁
|
+
|
a₂₂
|)
2.01 = max(|1| + |1|, |1| + |1.01|)
‖
A
-1
‖∞
=
max(|
a₂₂
|
+
|
a₁₂
|,
|
a₂₁
|
+
|
a₁₁
|)
÷
|
D
|
201 = max(|1.01| + |1|, |1| + |1|) ÷ |0.01|
κ∞
=
‖A‖∞
×
‖
A
-1
‖∞
404.01 = 2.01 × 201
log₁₀ κ = log₁₀(κ∞)
2.6064 = log₁₀(404.01)
Assumptions
•
The row-sum norm ‖A‖∞ is the largest sum of |entries| across a row.
•
κ∞ = ‖A‖∞‖A⁻¹‖∞ is at least 1; a large κ means a small change in b or A moves x a lot.
•
About log₁₀ κ of the 16 digits a computer carries can be lost in solving Ax = b.
Step-by-step
WE KNOW
a₁₁ = 1, a₁₂ = 1, a₂₁ = 1, a₂₂ = 1.01
FIND
determinant of A (D), row-sum norm of A (‖A‖∞), row-sum norm of A⁻¹ (‖A⁻¹‖∞), condition number (κ∞), digits lost (log₁₀ κ)
Step 1 · Find determinant of A (D)
Use D = a₁₁ × a₂₂ − a₁₂ × a₂₁
Down the main diagonal, take away the other diagonal.
D
=
1
×
1.01
−
1
×
1
D
=
0.01
Step 2 · Find row-sum norm of A (‖A‖∞)
Use ‖A‖∞ = max(|a₁₁| + |a₁₂|, |a₂₁| + |a₂₂|)
Add the sizes of the entries across each row; the norm is the larger sum.
‖A‖∞ = max(1 + 1, 1 + 1.01)
‖A‖∞ = 2.01
Step 3 · Find row-sum norm of A⁻¹ (‖A⁻¹‖∞)
Use ‖A⁻¹‖∞ = max(|a₂₂| + |a₁₂|, |a₂₁| + |a₁₁|) ÷ |D|
A
-1
=
(
1
D
)[[
a₂₂
,
−
a₁₂
],
[−
a₂₁
,
a₁₁
]]:
swap
the
diagonal,
change
the
other
signs,
divide
by
D
.
Then
take
its
larger
row
sum.
‖
A
-1
‖∞
=
max(1.01 + 1, 1 + 1)
0.01
‖
A
-1
‖∞
=
201
Step 4 · Find condition number (κ∞)
Use κ∞ = ‖A‖∞ × ‖A⁻¹‖∞
The
condition
number
multiplies
the
two
norms:
how
much
A
can
stretch,
times
how
much
A
-1
can.
κ∞ = 2.01 × 201
κ∞ = 404.01
Step 5 · Find digits lost (log₁₀ κ)
Use log₁₀ κ = log₁₀(κ∞)
Each factor of 10 in κ can cost one significant digit of x.
log₁₀ κ = log₁₀(404.01)
log₁₀ κ = 2.6064
Check
Put the numbers back in. Both sides should match.
0.01 = 1 × 1.01 − 1 × 1 ✓
2.01 = max(1 + 1, 1 + 1.01) ✓
201
=
max(1.01 + 1, 1 + 1)
0.01
✓
404.01 = 2.01 × 201 ✓
2.6064 = log₁₀(404.01) ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.