gibson:teaching:fall-2012:iam961:hw3
====== Differences ====== This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
gibson:teaching:fall-2012:iam961:hw3 [2012/10/24 10:26] gibson |
gibson:teaching:fall-2012:iam961:hw3 [2012/10/24 11:08] (current) gibson |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| - | **1** Implement Classical Gram-Schmidt, Modified Gram-Schmidt, and Householder | + | **1:** Implement Classical Gram-Schmidt, Modified Gram-Schmidt, and Householder |
| algorithms for the QR decomposition of a square matrix ''A''. Your functions | algorithms for the QR decomposition of a square matrix ''A''. Your functions | ||
| should return the ''Q'' and ''R'' matrices like this (in Matlab syntax) | should return the ''Q'' and ''R'' matrices like this (in Matlab syntax) | ||
| Line 40: | Line 40: | ||
| - | **2** Investigate the behavior of your three QR algorithms as follows: | + | **2:** Investigate the behavior of your three QR algorithms as follows: |
| (Note: Performing the following operations with a smaller (say 10 x 10) | (Note: Performing the following operations with a smaller (say 10 x 10) | ||
| Line 83: | Line 83: | ||
| - | Now see how well the computed QR decomp does what it should! | + | Now see how well the computed QR decomp does what it should |
| + | by computing **five error measures**! | ||
| <code> | <code> | ||
| Line 103: | Line 104: | ||
| - | In particular, look at ''Qc* Qc'' to see exactly where it deviates from | + | And look at some 2d plots of ''Qc* Qc'' to see exactly where it deviates from |
| the identity | the identity | ||
| Line 128: | Line 129: | ||
| **Now, keeping ''A,x,b'' constant, run that same series of calculations using your | **Now, keeping ''A,x,b'' constant, run that same series of calculations using your | ||
| ''qr_cgs'', ''qr_mgs'', and ''qr_house'' codes for the QR decomposition.** | ''qr_cgs'', ''qr_mgs'', and ''qr_house'' codes for the QR decomposition.** | ||
| + | |||
| + | Use script files to automate the above calculations. Put the generation of | ||
| + | ''A,x,b'' in one script file (or maybe function) and the others in another script | ||
| + | so that you can rerun the whole series of calculations for different QR algorithms | ||
| + | just by changing ''qr_cgs'' to ''qr_mgs'' or ''qr_house''. | ||
| + | |||
| + | Run the script a few times for each algorithm. Note that the computed errors might | ||
| + | vary over one or two orders of magnitude based on the particular random ''A,x,b''. | ||
| + | Again, running the script a few times for each algorithm, record **the nearest usual | ||
| + | power of ten for each error**, and make a table of the 5 error measures for the 3 | ||
| + | algorithms. | ||
| Based on your results, how well do each of the three QR algorithms work? Make | Based on your results, how well do each of the three QR algorithms work? Make | ||
| - | some general observations based on the plots and the computed errors for the three cases. | + | some general observations based on the plots and the error table. Keep in mind that |
| - | Make a table of the 5 error measures for the 3 algorithms. Keep in mind that errors of | + | errors of order 10^-16 are superb, 10^-8 are ok, and 10^0 (one) are very bad, and that |
| - | order 10^-16 are very good, 10^-8 are ok, and 10^0 (one) are very bad, and that | + | |
| the order of magnitude (exponent of 10) is all that matters. | the order of magnitude (exponent of 10) is all that matters. | ||
| - | Hint: Use script files to automate the above calculations. Put the generation of | ||
| - | ''A,x,b'' in one script file (or maybe function) and the others in another script | ||
| - | so that you can rerun the whole series of calculations for different QR algorithms | ||
| - | just by changing ''qr_cgs'' to ''qr_mgs'' or ''qr_house''. Also, rerun each of the | ||
| - | **3** For the ambitious: Note that if you rerun the above commands repeatedly for | + | **3:** For the ambitious: To be more precise about the averaging over random ''A,x,b'', |
| - | different randomly constructed ''A,x,b'', you might get errors ranging over a couple | + | run the tests repeatedly and take an average of the errors. Put the entire sequence |
| - | different orders of magnitude. It's actually best to run the tests repeatedly and | + | of above commands (minus the plots) in a ''for'' loop over, say, 100 trials, and reduce |
| - | take an average of the errors. Put the entire sequence of above commands (minus the plots) in a | + | the dimension of the matrices to say ''m=30'' so they run faster. Then compute the //geometric mean// |
| - | ''for'' loop over, say, 100 trials, and reduce the dimension of the matrices to say | + | errors as follows |
| - | ''m=30'' so they run faster. Use a geometric mean rather than the arithmetic mean, i.e. | + | |
| <code> | <code> | ||
| Line 161: | Line 167: | ||
| Put the various calculated geometric-mean errors in a table and base your discussion | Put the various calculated geometric-mean errors in a table and base your discussion | ||
| of the behavior of the three algorithms on the geometic means rather than the | of the behavior of the three algorithms on the geometic means rather than the | ||
| - | particular-case answers of **3**. | + | estimated order-of-magnitude errors of **3**. |
| - | **4** For those seeking world domination: calculate the geometric-mean errors for | + | **4:** For those seeking world domination: calculate the geometric-mean errors for |
| - | each algorithm as a function of condition number, and produce plots for each error | + | each algorithm as a function of condition number, and produce log-log plots for each error |
| type with three lines, one each for CGS, MGS, and Householder, with condition number | type with three lines, one each for CGS, MGS, and Householder, with condition number | ||
| ranging from 1 to 10^16. | ranging from 1 to 10^16. | ||
| - | + | Turn in your codes, the error table, one inner-product matrix plot for each algorithm, | |
| + | and your discussion of the behavior of the three algorithms. | ||
gibson/teaching/fall-2012/iam961/hw3.1351099586.txt.gz · Last modified: 2012/10/24 10:26 by gibson
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
