当前位置:天才代写 > 作业代写,留学生作业代写-北美、澳洲、英国等靠谱代写 > 数值分析代写 Numerical Analysis代写

数值分析代写 Numerical Analysis代写

2021-09-09 16:47 星期四 所属: 作业代写,留学生作业代写-北美、澳洲、英国等靠谱代写 浏览:551

数值分析代写

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).

 

0

 

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 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

 

0

 

[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 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.]

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

 

0

 

(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 appearing in the LU factorization A = LU. What is max,j |u,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代写 英国代写

合作平台:essay代写 论文代写 写手招聘 英国留学生代写

 

天才代写-代写联系方式