Scientific Computing Language Homework 2
Problem 1 (10 pts). Let Ax = b Write x ̃ = x+δx be the computed estimate of x where x is perturbed by δx. Although we can not compute δx, we can estimate the residual, defined as
Show that
r = b − A ̃x.
∥δx∥ ≤ κ(A)∥r∥. ∥x∥ ∥b∥
Does small residual mean the error is also small?
Problem 2 (10 pts). Show that the multiplication of two n × n matrices takes ∼ 2n3 flops. Problem 3 (15 pts). Suppose that A ∈ Rn×n and that ∥A∥ < 1 in some induced matrix norm.
1. Show that I − A is nonsingular. (Show that (I − A)x = 0 for nonzero x implies that ∥A∥ ≥ 1, using the definition of an induced matrix norm.
2. Showthatlimm→∞Am =0. (WesaylimB→∞Bk =B∗ iflimB→∞∥Bk −B∗∥=0.)
3. Use the above result to show (I − A)−1 = ∞k=0 Ak.
Problem 4 (15 pts). Here are population figures for three countries over the same 30 years period.
Year United States China Germany 1980 227.225 984.736 78.298 1990 249.623 1148.364 79.380 2000 282.172 1263.638 82.184 2010 308.282 1330.141 81.644
1. Use cubic polynomial interpolation to estimate the population of China in 1992.
2. Use cubic polynomial interpolation to estimate the population of China in 1984.
3. Use cubic polynomial interpolation to make a plot of the German population from 1985 to 2000. Your plot should show a smooth curve and be well annotated.
Problem5(10pts). ConsiderthematrixA∈Rn×n,withentriesaij =1ifi=jorj=n,aij =−1 if i > j, zero otherwise. Show that A admits an LU decomposition, with |Lij| ≤ 1 and unn = 2n−1.
Problem 6 (15 pts). In Matlab, define
1 1012 0
11 1/3
A= 1 1 ,xˆ=2/3,b=Axˆ.
111
10 4/3 1
1. The format command can adjust output appearance in Matlab; enter format long in Matlab. Using lufact function and triangular substitutions, solve the linear system Ax = b and let Matlab print out the result. About how many (to the nearest integer) accurate digits are in the result? (The answer is much less than the default 16 of double precision)
2. Repeat part 1) with 1020 as the corner element. (The result is even less accurate).
Problem 7 (15 pts). In this problem you will explore the backslash and how it handles banded
matrices. To do this you will generate tridiagonal matrices using the following code:
1 2
1
A = triu( tril(rand(n),1), -1); A(:1:n+1:end) = a;
The result is n × n, with each entry on the sub- and super-diagonals chosen randomly from (0, 1) and each diagonal entry equaling a.
1. Write a script that solves 200 linear systems whose matrices are generated as above, with n = 1000 and a = 2. Record the total time used by the solution process A\b only, using the built-in cputime.
2. Repeat the experiment of 1), but add the command A=sparse(A); right after the two lines above. how does timing change?
3. Based on these observations, state a hypothesis on how backslash solves tridiagonal linear systems given in standard dense form and in sparse form.
Problem 8 (10 pts). Based on the lufact function, write a function
function [L, U] = luband(A, upper, lower)
that accepts upper and lower bandwidth values and computes LU factors in a way that avoids doing arithmetic using the locations that are known to stay zero.
2