1. Let a be non-negative real number. Then, for any positive x0, the sequence of iterates generated by the formula
(1)
√
converges to a.
√
Use this rule to write a routine to approximate 5. Use as your starting condition x0 = 5, kmax = 20 and tolerance ε = 1 × 10−12.
2. We often need to be able to approximate the definite integral
(2)
for some function f(x) over a given interval [a,b]. One approximation is the Trapezoidal rule, given by (3)
where xi = a + ih, for
Write an algorithm that takes as input a function f(x), and an interval [a,b] and returns an approximation to the integral of f(x).
Use your algorithm to find the value of the integral
(4)
What are the values of your approximation for n = 10 and n = 20?
3. Let P(x) = anxn + an−1xn−1 + an−2xn−2 + ... + a0 be an nth degree polynomial.
(a) How many additions and multiplications are required to evaluate P(x) for a given value of x? Treat each power as a repeated multiplication.
(b) Can you devise an algorithm that reduces the required number of arithmetic operations? Howmany multiplications and how many additions are required by your algorithm?
(c) (Math 565 only). Write a computer code that evaluates a polynomial, given a set of coefficients. Test your algorithm on the 5th degree polynomial p(x) = 3.1x5+πx4−x3+4.7x+4. Your algorithm should require a minimal number of operations. Create a plot of the polynomial over the interval [−2,2]. Explain why it is important to have an efficient method for polynomial evaluation.
