辅导案例-PART 1
Programming Project PART 1 CS 323 - Numerical Analysis 1 Introduction This project will be divided in two parts, the first part (this hand- out) contains the first algorithms covered in class that you must implement in Matlab. The second part will be assigned after we have covered in class the remaining algorithms that you will need to implement. • For this project you will work individually. • You must turn in your own work. • All your programs should run. No partial credit will be given for programs that do not run. • You must use at least five test cases for each program. You must turn in the input and output of each one of your test cases. Please start working as soon as possible. 2 About the programs 2.1 Programming Language The programs must be written in Matlab (m files), and the in- put should be read from a file. Please refer to the following link: https://www.mathworks.com/help/matlab/ref/fscanf.html for information on how to read files in matlab. 2.2 Style All your programs must be correctly indented and must include comments (use % in matlab) describing the major parts of the al- gorithm. If you use any other variables that are not the usual ones described in the lecture notes, please explain in your comments the meaning of each one of those variables. 1 3 Algorithms The following is the list of all the algorithms that you must imple- ment: 1. Horner: Given the coefficients of a polynomial a0, a1, . . . , an, and a real number x0, find P (x0), P ′(x0), P ′′(x0), P (3)(x0), . . . , P (n)(x0) Sample input representing P (x) = 2+3x−x2+2x3, x0 = 3.5: 3 2 3 -1 2 3.5 the first number is the degree of the polynomial (n), the coef- ficients are in order a0, a1, . . . , an, the last number is x0. 2. Newton with Horner: Given the coefficients of a polynomial a0, a1, . . . , an, an initial guess x0 ∈ R, an error tolerance ǫ, and a maximum number of iterations N , find one root of the polynomial. Input format is the same as above, plus two more lines for ǫ and N Important: no credit will be given if the method does not use Horner. The output is just one number representing the solution within the desired error tolerance, or a message saying that the solu- tion was not found. 2 3. Cramer’s Rule: Given a matrix A representing a system of equations, and a vector b of independent terms, use Gaussian Elimination to find all the determinants needed to solve the system. The program must output the value of each of the n + 1 determinants as well as the solution x1, x2, . . . , xn. Sample input representing the system: 3 4 2 −1 3 −4 2 2 5 x1 x2 x3 = 5 2 −6 is: 3 3 4 2 -1 3 -4 2 2 5 5 2 -6 The expected output should be: determinant A = 41 determinant A1 = 215 determinant A2 = -53 determinant A3 = -114 x1 = 5.24390 x2 = -1.29268 x3 = -2.78049 3 4. Neville’s Method: Given a set of n+ 1 points (x0, y0), (x1, y1), . . . , (xn, yn) and x0 ∈ R use Neville’s Algorithm to find Pn(x0) where Pn(x) is the unique polynomial that goes through all of the given points. Sample input representing the points (−1, 1), (0, 0), (1, 1) and x0 = 0.5: 2 -1 1 0 0 1 1 0.5 where the first number is n, then the pairs xi, yi, and the last number is x0 The expected output should be: P(0.5) = 0.25 4