Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/August 2007

Problem 1 A set of functions is a Chebyshev system if (i) The set is linearly independent. (ii) If is a linear combination of which is not identically zero, has at most distinct zeros in . Problem 1a Show that is a Chebyshev system if and only if for any distinct points the matrix with is non-singular. Solution 1a Forward Direction We want to prove the following statement: If is a Chebyshev system, then for any distinct points the matrix with is non-singular. Writing out the matrix yields: Since the set is linearly independent, there does not exist any non-zero sets of constants of such that for any . Hence, the columns of the matrix are linearly independent which implies that is non-singular. Reverse Direction Proof of (i) Assume is non-singular. This implies the columns of are linearly independent. Since is non-singular for any choice of , is a linearly independent set and we have shown . Proof of (ii) By hypothesis, is a linear combination of i.e. for not all zero. Assume for the sake of contradiction that has zeros at This implies the following equations: Rewriting the equations in matrix form yields Since are not all zero, this implies that the columns of , , are linearly dependent, a contradiction. Hence, has at most zeros, and we have shown . Problem 1b Let be such that for all . Let . Show that is a Chebyshev system. For this, you may use results from polynomial interpolation without proof. Solution 1b We have to prove: (i) is a linearly independent set (ii)any linear combination of this set has at most zeros. Proof of (i) If we evaluate at distinct points, , we have the following Van Der Monde matrix whose determinant is non-zero. Hence, are linearly independent. Assume for the sake of contradiction that is a linear combination of , that is . Hence, is a polynomial of degree . Taking derivatives of yields which contradicts the hypothesis. Therefore is a linearly independent set. Proof of (ii) Let . Suppose has (or more) zeros in . By Rolle's Theorem, the (n+1)st derivative of f vanishes on the given interval, a contradiction. (i) and (ii) show that is a Chebyshev system. Problem 2 Let be a sequence of integration rules. Problem 2a Suppose and for some constant . Show that for all Solution 2a By the Weierstrass Approximation Theorem, given , there exists a polynomial such that Let Adding and subtracting and , yields, By the triangle inequality and equation (2) and (3), By equation (1), when , Hence for arbitrary small as , i.e. Problem 2b Show that if all then (1) implies (2). Solution 2b For , equation (1) yields, Letting in equation (0) yields, Combining the two above results yields, Since is finite, there exists some number such that . Since , i.e. equation (2). Problem 3 Consider the real system of linear equations where is non singular and satisfies for all real , where the Euclidean inner product is used here. Problem 3a Show that for all real where is the symmetric part of . Solution 3a Substituting for in and expanding the inner product we have, From properties of inner products we have, Hence, Problem 3b Prove that where is the minimum eigenvalue of . Solution 3b First Inequality Since is symmetric, it has a eigenvalue decomposition where is orthogonal and is a diagonal matrix containing all the eigenvalues. Substitution yields, Let This implies the following three relationships: Substituting, Expanding the numerator we have, Expanding the denominator yield Substituting, Second Inequality From part(a) for all real . Therefore is positive definite which implies all its eigenvalues are positive. In particular, Problem 3c Now consider the iteration for computing a series of approximate solutions to (1), where and is chosen to minimize as a function of . Prove that Solution 3c First, we want to write as a function of i.e. Changing the indices of equation from to ,substituting for , and applying the definition of norm yields, From a property of inner products and since is symmetric, Hence, Next we want to minimize as a function of . Taking its derivative with respect to yields, Setting and solving for gives Substituting for into gives, By definition of norm, Hence Multiplying and dividing the second term on the right hand side of the above equation by and applying a property of inner product yields, From the result of part (b), we have our desired result: