Q1 part d, Q2 part C, Q3 and extra credit, Q2 part c do not need to use matlab. When submit, make sure submit pdf for the solution and the matlab code together. Prefer expert:
BALJITNumerical Linear Algebra with Applications S21 HW 2 Due Jan 30 1. The symmetric matrix A = 11 7 −47 11 4 −4 4 −10 , has independent eigenvectors x1 = (1, 1, 0) T , x2 = (−2, 2, 1)T , and x3 = (1,−1, 4)T . (a) What are the corresponding eigenvalues? (b) Using the starting vector y0 = (1, 1, 1) T , what eigenvalue will the power method converge to? (c) Using the power method, by hand, determine v0 and v1. (d) (MATLAB) Compute the dominant eigenvalue, and its associated eigenvector, using the algo- rithm in the table for the power method given in the lecture for Jan 19, except use the starting vector given in part (b). The value of the eigenvalue should be correct to 6, or more, significant digits. Your answer should include the value of k that the iteration stopped at, the resulting value of vk and the associated eigenvector yk+1 = zk/||zk||2. A copy of your code must be included. As a suggestion, use the Publish command (select the options: Output format=pdf, Code settings: include code=true, Evaluate code=true). Make sure that the output is clearly labeled. 2. Let A = ( 2 2 2 −1 ) . (a) Using orthogonal iteration with B0 = A, what are the k = 0 approximations for the eigenval- ues? (b) Find B1 and Q1 and the resulting approximations for the eigenvalues. (c) What matrix does orthogonal iteration converge to? 3. This problem concerns the n× n tridiagonal matrix shown below. It is symmetric and positive definite. Also, note that aii = i except that ann = πn. In this problem take n = 100. A = 1 1 1 2 1 1 3 1 . . . . . . . . . 1 n−1 1 1 πn . a) Use the power method to compute the largest eigenvalue. The value should be correct to eight significant digits, and in your write-up you should explain why it likely satisfies this condition. b) Use the power method to compute the smallest eigenvalue. The value should be correct to eight significant digits. Also, explain how you used the power method to answer this question. c) Is λ = 100 an eigenvalue for A? You should use the power method to answer this question. Explain what you did and how (or why) it can be used to answer the question. Note that it is not possible to prove decisively whether λ = 100 is, or is not, an eigenvalue using MATLAB, but it can be used to provide a compelling answer to this question (which you must provide). Not a hint (for problem 3): The MATLAB command eig(A) will compute all of the eigenvalues for A. Feel free to use this if you want to know what the answers are, but you can not use this command or anything you learn from it as an answer to the given questions. What to turn in for problem 3: Output : Make a pdf of the results from MATLAB (make sure to include comments, or labels, in the printout indicating the problem being answered). You do not need to include the code in your write-up. Extra Credit: What is the largest eigenvalue when n = 200,000? The value should be correct to eight significant digits. In your write-up explain what modifications you made to the code you used in part (a) to answer this question. Also, how many iteration steps does it take to determine the eigenvalue? Powermethod E A's AE J K use cu to find I Requirements a the matrix A is not defective 3 and it has a dominant e value independent Def Suppose that A has re vectors I I In with corresponding e values T Ta In Also assume the labeling is as follows 11,7711 711 317 3 1 Tn with this I is a dominant e value of A if given any other e value Ii with di I then tail Idi 1 Examples A is 4x4 D T 4 12 2 1 2 Ty 0 A is the dominant e value 2 1 4 12 4 13 2 Ty 0 11,1 7121 but I 12 no dominant e value 3 71 4 12 4 13 4 14 1 1 4 is a dominant e value for A 4 A 4 12 1 ti 13 1 i Ay I 11,1 1121 1131 1141 Tais a dominant e value 3 the starting rectory must contain a contribution of an e vector for the dominant e value The Fix picky randomly Example suppose A is 2 2 with e vectors I o must pick 5 El so y o By picking y randomly from of y El the probability y o is almost zero I Rate of Convergence let une approx of 1 at step k of the power method If A is symmetric then as f A 1 I Uh Uh I R I Ve i Vh al where y error reduction R É factor where di is the next largest tail value If A is not symmetric then usually D 15,1 Examples A is 3 3 symmetric 1 I 4 12 1 13 0 D It I 2 A 2 Foo 12 2 13 1 R C EC T 70.99990 VEY slow convergence Stopping Condition If top 10 the stopping condition is Is not Assuming vet I then for Vee close to It un is likely to be correct to p significant digits MATLAB Examples i A 3d 2 A 1 6 9 I 10 6 Tz E 10 6 R IF I 0.999992 3 A l I T A T F 4 A o's defective Observation works as expected Question can the power method be used to compute other e values for A Examnle A is 3 3 with e values 2 1 4 I b Y I r e values E dominant e value Fact I shifting If A has Éectors I Ia In with corresponding e values Ji Ta In then B A MI has e vectors I I xi with e values him Izu Tim Example A Iz o f y a e values IB A BI g I n X r e values so power method applied to B to compute 5 5 with e vector I the A has e value I th z with e vector I Example suppose A is 3 3 with e values 2 I 2 A I to Y E D e values no dominant e value shift B A I wya e values dominant e value Fact inverse If A is invertible so 1 0 is not an e value then A has e vectors I I In with e values I taz In Example A is 3 3 A I b y y is e values At I by is e values dominant e value for A 1 So the power method with A computes e value I with e vector I Then a I is e value for A with e vector I Complication need to compute A of use Lufactorization Combo Idea shifting inverse suppose we want to find the e value for A that is closest to u step 1 shift B A MI stenz power method applied to B to obtain I and e vectors e value for Ant f with e vector I This is called the inverse iteration method Introduction to Scientific Computing and Data Analysis Mark H. Holmes Introduction to Scientifi c Computing and Data Analysis Editorial Board T. J. Barth M. Griebel D. E. Keyes R. M. Nieminen D. Roose T. Schlick 13 Texts in Computational Science and Engineering 13 Editors Timothy J. Barth Michael Griebel David E. Keyes Risto M. Nieminen Dirk Roose Tamar Schlick More information about this series at http://www.springer.com/series/5151 http://www.springer.com/series/5151 Mark H. Holmes Introduction to Scientific Computing and Data Analysis 123 Mark H. Holmes Department of Mathematical Sciences Rensselaer Polytechnic Institute Troy, NY, USA ISSN 1611-0994 ISSN 2197-179X (electronic) Texts in Computational Science and Engineering ISBN 978-3-319-30254-6 ISBN 978-3-319-30256-0 (eBook) DOI 10.1007/978-3-319-30256-0 Library of Congress Control Number: 2016935931 Mathematics Subject Classification (2010): 65-01, 15-01, 49Mxx, 49Sxx, 65D05, 65D07, 65D25, 65D30, 65D32, 65Fxx, 65Hxx, 65K10, 65L05, 65L12, 65Zxx © Springer International Publishing Switzerland 2016 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper This Springer imprint is published by Springer Nature The registered company is Springer International Publishing AG Switzerland Preface The objective of this text is easy to state, and it is to investigate ways to use a computer to solve various mathematical problems. One of the challenges for those learning this material is that it involves a nonlinear combination of mathematical analysis and nitty-gritty computer programming. Texts vary considerably in how they balance these two aspects of the subject. You can see this in the brief history of the subject given in Figure 1 (which is an example of what is called an ngram plot). According to this plot, the earlier books concentrated more on the analysis (theory). In the early 1970s this changed, and there was more of an emphasis on methods (which generally means much less theory), and these continue to dominate the area today. However, the 1980s saw the advent of scientific computing books, which combine theory and programming, and you can see a subsequent decline in the other two types of books when this occurred. This text falls within this latter group. Year 1950 1960 1970 1980 1990 2000 2010 P er ce n ta g e 0 1 2 3 Numerical Methods Scientific Computing Numerical Analysis Figure 1 Historical record according to Google. The values are the number of in- stances that the expression appeared in a published book in the respective year, expressed as a percentage for that year, times 105 [Michel et al., 2011]. v vi Preface There are two important threads running through the text. One concerns understanding the mathematical problem that is being solved. As an exam- ple, when using Newton’s method to solve f(x) = 0, the usual statement is that it will work if you guess a starting value close to the solution. It is important to know how to determine good starting points and, perhaps even more importantly, whether the problem being solved even has a solution. Consequently, when deriving Newton’s method, and others like it, an effort is made to explain how to fairly easily answer these questions. The second theme is the importance in scientific computing of having a solid grasp of the theory underlying the methods being used. A computer has the unfortunate ability to produce answers even if the methods used to find the solution are completely wrong. Consequently, it is essential to have an understanding of how the method works and how the error in the computation depends on the method being used. Needless to say, it is also important to be able to code these methods and in the process be able to adapt them to the particular problem being solved. There is considerable room for interpretation on what this means. To explain, in terms of computing languages, the current favorites are MATLAB and Python. Using the commands they provide, a text such as this one becomes more of a user’s manual, reducing the entire book down to a few commands. For example, with MATLAB, this book (as well as most others in this area) can be replaced with the following commands: Chapter 1: eps Chapter 2: fzero(@f,x0) Chapter 3: A\b Chapter 4: eig(A) Chapter 5: polyfit(x,y,n) Chapter 6: integral(@f,a,b) Chapter 7: ode45(@f,tspan,y0) Chapter 8: fminsearch(@fun,x0) Chapter 9: svd(A) Certainly this statement qualifies as hyperbole, and, as an example, Chap- ters 4 and 5 should probably have two commands listed. The other extreme is to write all of the methods from scratch, something that was expected of students in the early days of computing. In the end, the level of coding de- pends on what the learning outcomes are for the course and the background and computing prerequisites required for the course. Many of the topics included are typical of what are found in an upper- division scientific computing course. There are also notable additions. This includes material related to data analysis, as well as variational methods and derivative-free minimization methods. Moreover, there are differences related to emphasis. An example here concerns the preeminent role matrix factorizations play in numerical linear algebra, and this is made evident in the development of the material. Preface vii 1950 1960 1970 1980 1990 2000 2010 2020 Year 0 5 10 15 N u m b er