MATH-UA.0252 Numerical Analysis
Assignment 2
数值分析代写 1.Estimates for vector and matrix norms, [10pts](a)[4pts] For a vector v ∈ Rn , do the following defifinitions N : Rn → R defifined norms?
1.Estimates for vector and matrix norms, [10pts]
(a)[4pts] For a vector v ∈ Rn , do the following defifinitions N : Rn → R defifined norms? If yes, prove that they satisfy the axioms. If no, argue why (e.g., giving an example that shows that the axioms are not satisfified).
2.[Backward substitution implementation, 5pts] 数值分析代写
[3pts] Write a code for backward substitution to solve systems of the form Ux = b, i.e., write a function x = backward(A,b), which expects as inputs an upper triangular matrix U ∈ Rnxn , and a right hand side vector b ∈ Rn , which returns the solution vectox ∈ Rn . The function should fifind the size n from the vector b and also check if the matrix and the vector sizes are compatible before it starts to solve the system. Apply your program for the computation of for x ∈ R4 , with
[2pts] How do you know that your code is working correctly?
¹ This is sometimes referred to as the “ι0-norm”—which doesn’t necessarily mean that it’s a norm.
3.[LU factorization of tridiagonal matrix, 6pt]
Given is a tridiagonal matrix, i.e., a matrix with nonzero entries only in the diagonal, and the fifirst upper and lower subdiagonals:
derive iterative expressions for di , ei and fi (i.e., how to compute the value for i+ 1 from the values at i, and how to start for i = 1).
Hint: You could check your answer by implementing the formulas in code and checking that LU = A in Matlab for some specifific example.
4.[Inverse matrix computation, 8pts] 数值分析代写
Let us use the LU-decomposition to compute the inverse of a matrix².
(a) [2pts] Describe an algorithm that uses the LU-decomposition of an n × n matrix A for computing A-1 by solving n systems of equations (one for each unit vector).
(b)[2pts] Calculate the flfloating point operation count of this algorithm. It is OK to use estimates from class/worksheets but write them down so the grader knows what you are doing.
(c)[4pts] Improve the algorithm by taking advantage of the structure (i.e., the many zero entries) of the right-hand side. What is the new algorithm’s flfloating point operation count?
[Hint: Consider splitting the solution vector for the k-th equation from part (a) into two pieces, and solve for each piece separately, on paper or using forward/back substitution.]2 This also illustrates that computing a matrix inverse is signifificantly more expensive than solving a linear system. That is why to solve a linear system, you should never use the inverse matrix!
5.[Stability of the Gaussian elimination, 8pts] 数值分析代写
Consider the linear system
Ax = b, (1)
where A is an n×n matrix that has ones on the diagonal, minus ones below the diagonal, and ones in the last column, with all other entries zero. For example, when n = 5, we have
(a) [(extra credit) 3pts] Prove that A is invertible for any n, by induction. [Hint: Perform a column operation on A to eliminate the reduce it to a smaller matrix of size n − 1 and ask whether that smaller matrix is invertible under the induction hypothesis.]
(b)[3pts] Now consider the matrix A for some unspecifified (arbitrary) n. Perform Gaussian elimination on A to obtain the upper triangular matrix U appearing in the LU factorization A = LU. What is maxi ,j |ui ,j | as a function of n?
(c) [2pts] For large n, e.g., n = 2000, what problems can you envision if you try to solve (1) using Gaussian elimination on a computer? Explain. [Note: This is one rare example matrix for even Matlab will fail to solve a linear system correctly even though the matrix is well-conditioned, see discussion in Section 7.5 of Practice textbook.]
6.[Matrix square root, 6pts] 数值分析代写
Newton’s method for fifinding roots can be extended to matrix-valued functions as well. Here you will devise a Newton method (i.e., generalize the Babylonian method) to compute the square root of a matrix. If it exists, the square root of a real symmetric n×n matrix A is another real square symmetric matrix X such that
XTX = A (2)
Just like the square root of even a positive number is not unique, the matrix square is not unique (one can roughly think of having to choose n signs, as we will revisit in a future homework once we cover eigenvalue decompositions).
(a) [2pts]
In class/worksheet we used derivatives to obtain Newton’s method. Instead of computing derivatives of matrix-valued functions, however, it is useful to think of computing derivatives from a linearization of the function around a given value (this allows to generalize the notion of a derivative and makes it easier to compute in some cases). Set X = X + δX in (2) and keep only the terms that are linear in the ’perturbation” δX. Use this to write down an equation for δX.
(b) [2pts] 数值分析代写
The equation you obtained in part (a) can be solved explicitly for any n – can you explain why? It is OK if you assume a unique solution exists. Take n = 2 and write down the solution explicitly. [Hint: It is always a good idea to check by plugging in specifific numbers.]
(c) [2pts]
It would be nice to write down an explicit formula for the solution of the equation you got from part (a) for any n. Do this by assuming that the matrices X and δX commute, i.e., that
X (δX) = (δX) X. (3)
[Hint: Recall that X is symmetric.].Note: One can prove (3) holds at all iterations if the initial guess X0 commutes with A; if interested, look at the paper “Newton’s Method for the Matrix Square Root” by Nicholas Higham, freely available on the web.
其他代写：program代写 project代写 assignment代写 北美作业代写 homework代写 加拿大代写 python代写 report代写 paper代写 essay作业代写 作业代写 java代写 matlab代写 finance代写 英国代写
