CS/M 143M - SJSU



Matlab Assignments CS/M 143M

1. Least Squares

If A is an m by n rectangular matrix with m >= n and if c is a vector with m components then A c = y can not usually be solved exactly. Matlab can solve these equations approximately with the command c = A \ y. The solution c is called the “least squares” solution for reasons that we will describe later in the course. To illustrate an application involving this use of a rectangular matrix suppose that we wish to fit the three points (0,3), (2,5), and (4,6) with a straight line. Then as we described earlier we can let the line be described by c1` + c2 x, let c = [ c1 ; c2] (using Matlab notation for vectors), let y = the vector of y values.and let A be a Vandermonde matrix with components aij= xIj . To fit the line to the data we need to try to solve the equation A c = y.. In this example one can create A with the Matlab command A = [ 1 0;1 2;1 4] and y with y = [3 ; 5; 6]. Then c = A / y gives c = [3.1667; .75]. The commands

x=[0; 2; 4] % x isthe vector of x coordinates

plot(x,y,'o',x,A*c) % note that A*c generates points on the best fit line

xlabel('x')

ylabel('y')

title('given points (o) and least squares fit (line)')

will plot the given points and the line 3.1667 + .75 x. See the figure below.

For homework consider the points (0,0), (1,2), (2,3), (3,9), ( 4,17), (5,24), (6,37). (1) Use Matlab to find the least squares best fit with a line. Turn in A, y and c and a plot like the one above. Also (2) use Matlab to find the least square best fit with a quadratic. Turn in the same information.

2. Eigenvalues applied to Fibonacci numbers

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc. where the next number is the sum of the previous two numbers. If we let f0= 0, f1=1, f2=2, f3 = 3, f4 = 5, etc. then we can define the successive entries in the sequence by fn+1 = fn + fn-1. Now let us consider vectors xn = [ fn ; fn+1] ( I am using Matlab notation since the equation editor on my computer is not working right now – recall that the semicolon makes xn a column vector with two components: fn and fn-1). Therefore x0 = [0; 1], x1 = [ 1; 1], x2=[1 ; 2], x3 = [2; 3], etc. Since fn+1 = fn + fn-1 it is not hard to check that xn = [ fn ; fn+1] = [0 1 ; 1 1] [fn-1 ; fn] = A xn-1 where A = [ 0 1; 1 1]. You should check this with a few of the above x’s to get more comfortable with the equation. Since xn = A xn-1 we have x1 = A x0 , x2 = A x1, x3 = A x2 , etc. We can combine these equations to conclude that x2 = A2 x0, x3 = A3x0, etc. Therefore in general xn = Anxo. You might wish to check this by hand with n = 1 or n = 2.

An important application of eigenvalues is that they can be used to evaluate powers of matrices efficiently. We saw earlier that we can use eigenvectors and eigenvalues to write A = V D V-1 where D is a diagonal matrix with eigenvalues on the diagonal and V is the matrix whose columns are eigenvectors. In Matlab we can generate V and D with the one command [V,D] = eig(A). Also we discussed earlier that An = V Dn V-1. But Dn is easy to calculate -- a diagonal matrix raised to a power simply raises the diagonal entries to the power. Therefore we have a formula for calculating the n th Finonacci numbers: (1) let xn = V DnV-1 x0 (2) fn is the first component of the vector xn.

In Matlab this can be done with the commands:

n = 10 ; % or define n to be any other positive integer

x0 = [0;1] ;

A = [ 0 1; 1 1] ;

[V,D]=eig(A);

xn = V * D^n * inv(V) * x0 ;

fn = xn(1) ;

For homework:

1) Use Matlab and the above scheme to calculate the 50th Fibonacci number and the 100th Fibonacci number. Turn in the values you calculated.

2) When you do the above you will see that

V = 0.8507 0.5257 D = -.6180 0 inv(V) = .8507 -.5257

-0.5257 0.8507 0 1.6180 .5257 .8507

Write out the matrix formula xn = V * D^n * inv(V) * x0 by hand. Use it to derive an ordinary algebraic formula (that is one without any matrices) for fn. Recall that fn is the first component of xn.

3) (By hand) Use the formula A = V D V-1 to derive the formula An = V Dn V-1.

(4) Use Matlab and the above idea to find the 20th term in the sequence given by fn+1 = 3fn - fn-1, f0= 2, f1 = 1. (Hint: the first row of A can still be [0 1]. The second row will be different than above. Also x0will be different.) Turn in your A and f20.

Additional comment: Equations like fn+1 = fn + fn-1 are called difference equations. Eigenvalues are important tools in solving difference equations. Eigenvalues are also important for solving certain differential equations (although we don’t describe how here).

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download