Consider the problem 0 an-1 bn-1 Cn-1 where n is much greater than one. The matrix is tridiagonal, only the elements indicated by ak, bk and ck are non-zero. In compact form the problem is where B is known and X must be found. The matrix A is also diagonally dominant, lak! > 0, Icel > 0 and bk > Iakl + Ick! > 0, and it has the property that if di = bi then dk = bk-Akck-l/dk-i > 0 for k 2,3, . . . , n. These conditions imply that A-1 exists and also that none of the elements of A-1 is zero (you are not required to prove either of these two statements) 1. Assuming we have A, how many operations does it take to compute X? (Only count multiplications and divisions as operations.) 2. Show that there is a (unique) LU factorisation di 00...0 l2 d2 0 1 u2 0 0 u-1 n- 00 ln dn by explicitly calculating the Lk, dk and uk in terms of the ak, bk and ck. How many operations does it take to compute this factorisation? 3. Write the factorisation as A = LU and (1) as LUX 3. Show that it is possible to find X in O(n) operations, by solving the problem in two stages. 4. Use the previous results to show that it is possible to compute A-1 using O(n2) operations, but that it is still always more efficient to use the LU algorithm, described in (2) and (3), to solve problem (1) rather than matrix inversion. Consider the problem 0 an-1 bn-1 Cn-1 where n is much greater than one. The matrix is tridiagonal, only the elements indicated by ak, bk and ck are non-zero. In compact form the problem is where B is known and X must be found. The matrix A is also diagonally dominant, lak! > 0, Icel > 0 and bk > Iakl + Ick! > 0, and it has the property that if di = bi then dk = bk-Akck-l/dk-i > 0 for k 2,3, . . . , n. These conditions imply that A-1 exists and also that none of the elements of A-1 is zero (you are not required to prove either of these two statements) 1. Assuming we have A, how many operations does it take to compute X? (Only count multiplications and divisions as operations.) 2. Show that there is a (unique) LU factorisation di 00...0 l2 d2 0 1 u2 0 0 u-1 n- 00 ln dn by explicitly calculating the Lk, dk and uk in terms of the ak, bk and ck. How many operations does it take to compute this factorisation? 3. Write the factorisation as A = LU and (1) as LUX 3. Show that it is possible to find X in O(n) operations, by solving the problem in two stages. 4. Use the previous results to show that it is possible to compute A-1 using O(n2) operations, but that it is still always more efficient to use the LU algorithm, described in (2) and (3), to solve problem (1) rather than matrix inversion
