Page 47 - Matrix Analysis & Applied Linear Algebra

1.6 Ill-Conditioned Systems 39

is ill-conditioned by considering the following perturbed system:
v − w − x − y − z =0,
1
− v + w − x − y − z =0,
15
1
− v + x − y − z =0,
15
1
− v + y − z =0,
15
1
− v + z =1.
15
1.6.7. Let f(x) = sin πx on [0, 1]. The object of this problem is to determine
the coefficients α i of the cubic polynomial
3
! i
p(x)= α i x
i=0
that is as close to f(x) as possible in the sense that
" 1
2
r = [f(x) − p(x)] dx
0
# $ 2
" 1 3 " 1 " 1 3
! i ! i
2
= [f(x)] dx − 2 α i x f(x)dx + α i x dx
0 0 0
i=0 i=0
is as small as possible.
(a) In order to minimize r, impose the condition that ∂r/∂α i =0
for each i =0, 1, 2, 3, and show this results in a system of linear
equations whose augmented matrix is [H 4 | b], where H 4 and
b are given by
1
 1 1 1   2 
2 3 4 π
   
 1 1 1 1   1 
2 3 4 5 π
   
and  .
   
H 4 =   b = 
 1 1 1 1   1 4 
3 4 5 6 π π 3 
   −
   
1 1 1 1 1 6
4 5 6 7 π − π 3
Any matrix H n that has the same form as H 4 is called a
Hilbert matrix of order n.
(b) Systems involving Hilbert matrices are badly ill-conditioned,
and the ill-conditioning becomes worse as the size increases. Use
exact arithmetic with Gaussian elimination to reduce H 4 to tri-
angular form. Assuming that the case in which n = 4 is typical,
explain why a general system [H n | b] will be ill-conditioned.
Notice that even complete pivoting is of no help.