> <\body> <\itemize> If you are asked to compare several methods, don't just print their results. You need to discuss which method worked better--and how you judged quality. You should generally have some quantitative measure of quality--the relative error -\\|/\|\\|> is typically a good one if it is available.\ As you learn in the second problem, the residual -\\|> is a good measure of the error. If you include computer output, try to keep it concise. Norms (especially norms of errors) are much shorter and more meaningful than full vector output. In general, I'm not interested in intermediate results of your code. When you turn in results of computational exercises, include something that makes it credible that you actually did write code for the problem--include the code itself or a (reasonably short) printout of the results. Use your own best judgement to turn in that you think will convince me that you did the problem and did it correctly. Let <\equation*> U=>|>|>>||>|>>|||>>>>>. We would like to show that <\equation*> det U=u\u\u. For n>, define the matrix <\equation*> U\>|>|>>||>|>>|||>>>>>. Our proof will closely follow the definition on p. 146. We will proceed by induction on . If , then =U=(u)=det(U)>, so the claim is trivial. Suppose we know that )=u\u\u>. We would like to show <\equation*> det U=u\u\u. By definition, <\eqnarray*> >|>|(-1)*u*m,>>>> where we have (somewhat arbitrarily) chosen that our sum should go over the th row. > is the -minor of , as in the definition. Realize that <\eqnarray*> >||(-1)*u*m,>>|||(-1)*|\>*m+(-1)*u*m>>||||\>*udet(U)>>|||\u\u>>>> > This problem was to be done in finite-precision arithmetic (3 significant digits, in this case). Here, I emulate this by rounding to hundredths. If you look closely at the resulting matrix, you will find that there are elements on the order of > left throughout the lower-left half. This phenomenon occurs as well if you use double-precision arithmetic, although then the ``leftovers'' are on the order of machine precision (about >). <\with|par-par-sep|0> The matrix in the problem is called a . Depending on the size of , it has an exponentially big condition number, which means we should expect increasingly bad solutions. (Part a) and b) are treated together.) <\with|par-par-sep|0> \; (Note: in the output dump refers to the 2-norm \|=(a)>. refers to the relative error in per cent, i.e. \|\-\\|/\|\\|>.) It can be seen that partial pivoting yields a substantial decrease in the error of the final solution. Scaled partial pivoting seems conterproductive in our case--the values in our initial matrix are all of fairly comparable magnitude, so that improved pivoting does not help much. Also observe that the residual -\> remains roughly the same (namely, machine zero) for all cases, while the solution varies wildly. Here is the code corresponding to the above output: <\with|par-par-sep|0> <\strong> 4. Problem 20, p. 170 Here are the results for this problem: <\with|par-par-sep|0> Before we begin discussing this problem, note that the matrix is actually singular (). Gauss elimination in exact arithmetic would thus fail, but we are getting (bad) results. What is to be learned here is that you can't trust Gauss elimination to detect singular matrices. In particular, observe that our residual -\> is fairly small, so if we didn't know the exact solution, we would not suspect anything to be wrong. We observe that the partial pivoting methods fare significantly better than the non-pivoting ones, however scaled partial pivoting does not really have a huge impact. This stems from the fact that while partial pivoting favors clearly favors ``large'' rows, scaled partial pivoting does not particularly favor any of the rows in this matrix (their /maxj\n>\|a\|> rations are roughly the same)--thus choosing rows almost ``at random''. The code can be found on the solutions web page; it is mostly a repeat of the last problem. a) Suppose we find values > and > such that <\eqnarray*> >|>|>|>>>>>>|>>||>>>>>>|||>||>>>>.>>>> Then <\eqnarray*> u>||l=0\u=0,>>|u>||l\0\u=0,>>|u>||u\0,>>>> which is a contradiction. b) We need to find values > and > such that <\eqnarray*> >|>|>|>>>>>>|>>||>>>>>>|||>||>>>>|\>>>>>> Oddly enough, is already upper triangular so that if we put (the identity matrix) and , we've found an LU decomposition. <\equation*> |>||>>>>|>||>>>>=|>||>>>> is the other solution. a) We will try to find values > and > such that <\eqnarray*> ||>|>||>|>|>|>>>>>|>|>>||>|>>|||>>>>>>||||>|||>|||>>>>|\>>.>>>> By direct factoring (which I don't write out here): <\eqnarray*> ||>|||>|||>>>>||>|||>|||>>>>>||>>> b) Observe that <\equation*> ||>|||>|||>>>>||>|||>|||>>>>=||>|||>|||>>>>. Thus <\eqnarray*> ||>|||>|||>>>>||>|||>|||>>>>||>|||>|||>>>>>||>>> c) Finally, observe that <\equation*> ||>|||>|||>>>>||>|||>|||>>>>=||>|||>|||>>>>. Thus <\equation*> ||>|||>|||>>>>||>|||>|||>>>>=A. <\initial> <\collection>