numerical analysis with mathematica
Numerical Methods (Math 385/685) Homework 3 February 27, 2019 Due: Sunday, March 10th Problems: 1. Find the LU decomposition of the following matrices using Mathemat- ica’s inbuilt function. Write out the matrices, L, U and P . Verify your decomposition by showing that PA = LU . (a) 1. 1. 01 1. 3 0 1. −1 (b) 1. 2. 1 7 2 0. 1 4 1 0 2 5 1 2 3 11 (c) 1. 2. 31 1 1 9 7 9 2. The Mathematica function Eigensystem returns n+1 vectors when an nxn matrix is supplied. The entries of the first vector are the eigen- values of A. The remaining vectors are the corresponding eigenvectors. Apply Eigensystem to the matrices listed in problem 1. Recall that a matrix is singular if it has zero as an eigenvalue. Also when looking at computer output a number close to zero should be considered as zero. 1 (a) Which of the matrices in problem 1 are singular? (b) Which of the matrices in problem 1 are ill conditioned? 3. Let A = [ai,j] be an n× n matrix with real entries. Suppose that there is an m with ai,j = 0 for i ≥ m, j ≤ m and ai,i 6= 0 for 1 ≤ i < m. prove that a is singular. 4. prove that the inverse of a triangular matrix is a triangular matrix of the same type. (hint: the product of a matrix and its inverse should produce an identity matrix) 5. suppose that an object can be at anyone of n+1 equally spaced points x0, x1, x2, · · · , xn. when an object is at location xj it is equally likely to move to either xi−1 or xi+1 and cannot directly move to any other location. consider the probability pi that an object starting at location xi will reach the left end point x0 before reaching the right end point xn.clearly p0 = 1 and pn = 0. since the object can move to xi only from xi−1 or xi+1 and does so with probability 1/2, then the equation pi = 1 2 pi−1 + 1 2 pi+1 holds for each location i = 1, 2, · · · , n− 1 (a) set up a linear system ax = b for the problem. (b) execute linearsolve for the linear system to calculate the respec- tive probabilities for n = 10. (c) from your results from part (b), what is the probability that from x5 an object will reach x0 before x10 (d) repeat part (b) for n = 100, 1000, 10000, 100000. use the timing function to determine the required cpu time. plot cpu time against the matrix size. (e) comment on your results from part(d). graduate students 1. prove that given a normed linear space, v , d(u, v) =‖ u− v ‖ defines a metric for u, v ∈ v . 2 2. prove that for real or complex matrices ‖ a ‖‖ b ‖≥‖ ab ‖ . 3. complete the proof. if a is an n × n real symmetric matrix with orthonormal eigenvectors v1, v2, · · · vn then ‖ ak ‖=‖ a ‖k . 3 m.="" prove="" that="" a="" is="" singular.="" 4.="" prove="" that="" the="" inverse="" of="" a="" triangular="" matrix="" is="" a="" triangular="" matrix="" of="" the="" same="" type.="" (hint:="" the="" product="" of="" a="" matrix="" and="" its="" inverse="" should="" produce="" an="" identity="" matrix)="" 5.="" suppose="" that="" an="" object="" can="" be="" at="" anyone="" of="" n+1="" equally="" spaced="" points="" x0,="" x1,="" x2,="" ·="" ·="" ·="" ,="" xn.="" when="" an="" object="" is="" at="" location="" xj="" it="" is="" equally="" likely="" to="" move="" to="" either="" xi−1="" or="" xi+1="" and="" cannot="" directly="" move="" to="" any="" other="" location.="" consider="" the="" probability="" pi="" that="" an="" object="" starting="" at="" location="" xi="" will="" reach="" the="" left="" end="" point="" x0="" before="" reaching="" the="" right="" end="" point="" xn.clearly="" p0="1" and="" pn="0." since="" the="" object="" can="" move="" to="" xi="" only="" from="" xi−1="" or="" xi+1="" and="" does="" so="" with="" probability="" 1/2,="" then="" the="" equation="" pi="1" 2="" pi−1="" +="" 1="" 2="" pi+1="" holds="" for="" each="" location="" i="1," 2,="" ·="" ·="" ·="" ,="" n−="" 1="" (a)="" set="" up="" a="" linear="" system="" ax="b" for="" the="" problem.="" (b)="" execute="" linearsolve="" for="" the="" linear="" system="" to="" calculate="" the="" respec-="" tive="" probabilities="" for="" n="10." (c)="" from="" your="" results="" from="" part="" (b),="" what="" is="" the="" probability="" that="" from="" x5="" an="" object="" will="" reach="" x0="" before="" x10="" (d)="" repeat="" part="" (b)="" for="" n="100," 1000,="" 10000,="" 100000.="" use="" the="" timing="" function="" to="" determine="" the="" required="" cpu="" time.="" plot="" cpu="" time="" against="" the="" matrix="" size.="" (e)="" comment="" on="" your="" results="" from="" part(d).="" graduate="" students="" 1.="" prove="" that="" given="" a="" normed="" linear="" space,="" v="" ,="" d(u,="" v)="‖" u−="" v="" ‖="" defines="" a="" metric="" for="" u,="" v="" ∈="" v="" .="" 2="" 2.="" prove="" that="" for="" real="" or="" complex="" matrices="" ‖="" a="" ‖‖="" b="" ‖≥‖="" ab="" ‖="" .="" 3.="" complete="" the="" proof.="" if="" a="" is="" an="" n="" ×="" n="" real="" symmetric="" matrix="" with="" orthonormal="" eigenvectors="" v1,="" v2,="" ·="" ·="" ·="" vn="" then="" ‖="" ak="" ‖="‖" a="" ‖k="" .="">