MATH 472 COMPUTING PROJECT # 2

MATH 472 COMPUTING PROJECT # 2

The n n Hilbert matrix Hn de?ned by
H
n
ij =
1
i + j 1
; i; j = 1; : : : ; n: (1)
The Hilbert matrix Hn arises when approximating a function by a polynomial of
degree less than or equal to n using the Least-Squares method. They are extremely
ill-conditioned even for small n. In fact the following asymptotic estimate is known
?1(H
n
) = O((1 + p
2)4n
=
p
n): (2)
(1) Obviously Hn
is symmetric. Using the fact that
Hn
ij =
R 1
0
x
i+j2 dx; i; j = 1; : : : ; n; show that Hn
is positive de?nite.
(2) The inverse of Hn
is explicitly known:
(H
n
)
1
ij = (1)i+j
(i + j 1)?
n + i 1
n j
??n + j 1
n i
??i + j 2
i 1
?2
: (3)
Write a program to compute ?1(H8
) using formulas (1) and (3). Compare it
to the estimate provided by (2).
The task here is to compute the inverse of H8 using two methods: Choleski and QR.
The purpose is to 1) getting familiarity with the implementation of these methods
and 2) to gauge the e?ect of roundo? errors on the accuracy of the answers and 3)
to compare the two methods and to see which one is less/more sensitive to roundo?
errors. Indeed, Hilbert matrices are very ill-conditioned so we expect large errors.
(1) Write a program to compute the Choleski factorization LLT of H8
. You may
use the program I gave in class. Then write a program to do Forward and
Back substitution. You should implement these yourself and not use a software
package. So include a copy of your codes with your project. With these codes
compute the inverse by solving 8 linear systems H8xi = ei
; i = 1; : : : ; 8, xi
being the ith column of the inverse.
The output should be (i) (H8
)
1 using formula (3), (ii) the computed approximate inverse H8
approxinv and (iii) k(H8
)
1 H8
approxinvk1. It is recommended that you use double precision in all your calculations since it is
possible for single precision to be overwhelmed by the ill-conditioning.
(2) Repeat the above but using the QR factorization of H8
. For the factorization
you can use Matlab or other software. For the solution phase use the Back
substitution code use in the Choleski method.
To summarize, you should submit the following
(1) The proof of positive de?niteness of Hn
.
2 MATH 472 COMPUTING PROJECT # 2
(3) The codes for the Choleski factorization, the Forward and Back substitution
(4) (H8
)
1 using formula (3)
(5) The computed approximate inverse H8
approxinv using Choleski
(6) k(H8
)
1 H8
approxinvk1 using Choleski
(7) The computed approximate inverse H8
approxinv using QR.
(8) k(H8
)
1 H8
approxinvk1