Numerical Linear Alge
a 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 co
esponding 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-
ithm 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 co
ect to 6, or more,
significant digits. Your answer should include the value of k that the iteration stopped at, the
esulting 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 co
ect to eight
significant digits, and in your write-up you should explain why it likely satisfies this condition.
) Use the power method to compute the smallest eigenvalue. The value should be co
ect 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
e 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 you
write-up.
Extra Credit: What is the largest eigenvalue when n = 200,000? The value should be co
ect 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 co
esponding
e values T Ta In Also
assume the labeling is as follows
11, XXXXXXXXXXTn
with this I is a dominant
e value of A if given any othe
e value Ii with di I then
tail Idi 1
Examples A is 4x4
D T XXXXXXXXXX
2 Ty 0
A is the dominant e value
XXXXXXXXXXTy 0
11,1 7121 but I 12 no
dominant e value
XXXXXXXXXX1
1 4 is a dominant e value for A
4 A XXXXXXXXXXti 13 1 i Ay I
11, XXXXXXXXXX
Tais a dominant e value
3 the starting rectory must contain
a contribution of an e vector fo
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
e
or reduction
R É facto
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 XXXXXXXXXX
D It I
2 A 2 Foo XXXXXXXXXX
R C EC T
XXXXXXXXXX
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 co
ect
to p significant digits
MATLAB Examples
i A 3d
2 A 1 6 9
I 10
6
Tz E 10
6
R IF I XXXXXXXXXX
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 co
esponding
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 vecto
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 vecto
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 XXXXXXXXXXISSN 2197-179X (electronic)
Texts in Computational Science and Engineering
ISBN XXXXXXXXXXISBN XXXXXXXXXXeBook)
DOI XXXXXXXXXX/ XXXXXXXXXX
Li
ary of Congress Control Number: XXXXXXXXXX
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,
oadcasting, 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 o
the editors give a wa
anty, express or implied, with respect to the material contained herein or for any
e
ors or omissions that may have been made.
Printed on acid-free pape
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
ief 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 occu
ed. This text falls within this latter group.
Yea
XXXXXXXXXX XXXXXXXXXX
P
e
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 compute
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 e
or 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 cu
ent 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\
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 hype
ole, 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
elated to emphasis. An example here concerns the preeminent role matrix
factorizations play in numerical linear alge
a, and this is made evident in
the development of the material.
Preface vii
XXXXXXXXXX XXXXXXXXXX
Yea
0
5
10
15
N
u
m
e