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
x