Constructive

Question 1

Give a description of the bisection algorithm

Answer 1

If f(a)f(b) < 0, we can use the bisection algorithm to find the root of f.
At each iteration, consider c = 1/2(a+b).
If c has the same sign as a, let a(k+1) = c(k) and b(k+1) = b(k), otherwise let a(k+1) = a(k) and b(k+1) = c(k).

Question 2

Give a description of a fixed point iteration.

Answer 2

If x = g(x), a fixed point iteration would be if we let x(k+1) = g(x(k)).

Question 3

Give an iterate for Newton’s method in one dimension

Answer 3

x(k+1) = x(k) - f(x(k))/f’(x(k)).

Question 4

Describe Horner’s method

Answer 4

If p(z) = a(n)z^n + a(n-1)z^(n-1) + … + a(0), if we set b(n) = a(n) and b(r) = b(r+1)σ + a(r) for all other r, then b(0) = p(σ).
If we let q(n-1)(z) = b(n)z^(n-1) + b(n-1)z^(n-2) + … + b(1), then p(z) = (z-σ)q(n-1)(z) + b(0)

Question 5

Give an iterate for Newton’s method in higher dimensions

Answer 5

x(k+1) = x(k) - J^(-1)(f(x_k))