MTH 373/573 Homework 2 Solved

Problem1: ForwardSubstitutiononSteroids                                       
Suppose we are given a linear system 𝐴𝑥 = 𝑏, we say we can solve for 𝑥 without inverting 𝐴 when we mean we can use Gaussian elimination (with or without partial or full pivoting as appropriate) to compute 𝑥. For example, we can solve for 𝑦 = 𝐴−1𝐵𝑥 by first computing 𝑧 = 𝐵𝑥 and then solving for 𝑦 using 𝐴𝑦 = 𝑧. In case of triangular linear systems, such solution would involve use of forward and back substitutions.

Using this background, suppose you are given 𝐿, 𝐾 ∈ ℝ𝑛×𝑛 which are both lower triangular matrices, and 𝐵 ∈ ℝ𝑛×𝑛 any general matrix. Then, specify an algorithm for computing 𝑋 ∈ ℝ𝑛×𝑛 so that

𝐿𝑋𝐾 = 𝐵.

Problem2: Gaussianeliminationandpartialpivoting                            
(a)    Write a function to implement Gaussian elimination with no pivoting as in algorithm 1. 

(b)    Write a function to implement Gaussian elimination with partial pivoting as in algorithm 2. 

(c)    Test your code. For each of the examples as stated below, report the various measurements as below in a table. Use relative measurements as necessary, and 2-norm for all appropriate norms and condition numbers. You can use functions available from NumPy or SciPy for these purposes.      

•    The condition number (np.linalg.cond),

•    the error from un-pivoted solve from your function in part (a),

•    the residual from un-pivoted solve from your function in part (a),

•    the error from partially-pivoted solve from your function in part (b),

•    the residual from partially-pivoted solve from your function in part (b),

•    the error from np.linalg.solve,

•    the residual from np.linalg.solve.

Report if any of the solves fail. You should try to write your code so that it prints the above table automatically without user interaction.

For each matrix below, write 2 or 3 sentences on your observations with regard to conditioning, necessity of pivoting, and reasons for your observed results.

Use the following matrices of sizes 𝑛 = 10, 20, 30, 40 to test your code:

1.    A random matrix of size 𝑛×𝑛 with entries uniformly sampled from [0, 1) (use np.random.randn).

2.    The Hilbert matrix given by:
                                                                    𝑎𝑖𝑗 = 𝑖 + 𝑗 − 1  (𝑖, 𝑗 = 1, … , 𝑛).

3.    The matrix given by

⎡ 1

⎢

⎢−1

𝐴𝑛 = ⎢⎢−1

⎢ ⋮ ⎢

⎣−1
1

−1

−1
1 −1
⋯

⋯

⋯

⋱

⋯
1⎤

1⎥⎥

1⎥

⎥

⋮⎥

⎥ 1⎦
𝑇

For each case, let 𝑥⋆ = [1      ⋯         1]         ∈ ℝ𝑛 be the vector of all 1s of size 𝑛. Now, compute 𝑏 as the matrix-vector product 𝐴 𝑥⋆ and solve the linear system 𝐴 𝑥 = 𝑏.

Problem3: ScaledLinearSystems                                               
A matrix 𝐴 = [𝑎𝑖𝑗]𝑛×𝑛 is said to row equilibrated if it is scaled so that max |𝑎𝑖𝑗| = 1, 1 ≤ 𝑖 ≤ 𝑛. In solving a system of equations 𝐴𝑥 = 𝑏, we can produce an equivalent system in which the matrix is row equilibrated by dividing the 𝑖th equation by max1≤𝑗≤𝑛 |𝑎𝑖𝑗|.

(a) Solve the system of equations:
 
 
⎡1

⎢2

⎢

⎣1
1

−1 2
2 × 109⎤ ⎡𝑥1⎤              ⎡1⎤

109 ⎥ ⎢⎢𝑥2⎥⎥ = ⎢⎢1⎥⎥

⎥

        0 ⎦ ⎣𝑥3⎦ ⎣1⎦
by using Gaussian elimination with partial pivoting and the function you wrote for it in Problem 2.

(b)    Solve the same problem but now changing the linear system into a row equilibrated one and using Gaussian elimination without partial pivoting. You can reuse the function you wrote in Problem 2. Are the answers the same? Why or why not?

(c)    State your reasoning for the why or why not part in 2 to 4 sentences.