User
Question 3 [15 points] Define the matrix An ∈ Rn×n by
An =
1 −1 −1 · · · −1
0 1 −1 · · · −1
0 0 1 . . . ...
... ... . . . . . . −1
0 0 · · · 0 1
.
1. Show that the entry of the inverse of An at row i and column j has value:
0, if i > j
1, if i = j
2^(j−I−1), if i < j
2. What is the condition number of An? (The condition number of a matrix A is defined to be
‖A‖∞
∥
∥A−1∥
∥∞.) Is matrix An ill-conditioned?
3. Let −→
b = (−n + 2 −n + 3 · · · −1 0 1)> .
The solution of An−→x = −→
b is −→x = (1 1 · · · 1)> .
Perturb −→
b to ˆb = −→
b + (0 · · · 0 )> .
Let ˆx be the solution to An ˆx = ˆb. What is ˆx? (Hint: ˆx = −→x + A−1
n (ˆb − −→
b ).)
4. Show that the values of −→
b , ˆb, −→x , ˆx satisfy
‖−→x − ˆx‖∞
‖−→x ‖∞
≤ ‖An‖∞
∥
∥A−1
n
∥
∥∞
∥
∥
∥−→
b − ˆb
∥
∥
∥∞∥
∥
∥−→
b
∥
∥
∥∞
