CS3331: Numerical Methods
Quiz 3
May. 16, 1997

1.

(3%) Suppose that a root of f(x)=0 is located in an interval between x=0 and x=1024, and we are going to use the bisection method to find the root. If the error tolerance of the estimated root is 0.001, what is the smallest number of iteration we need to perform?

2.

(2%) What is the sufficient condition to insure the convergence of the successive substitution method x_n = g(x_n-1)?

3.

(5%) One systematic way of using the successive substitution method to find the zero of f(x)=0 is to have the iterative scheme $x_n = x_{n-1}-\alpha f(x_{n-1})$.

(a)

(2%) What is the sufficient condition to insure the convergence of the iterative scheme?

(b)

(3%) What is the $\alpha$ value for optimal convergence rate? Why? (Use hand drawing if necessary.)

4.

(7%) Let f(x) = x³/3+x²/2+x-1/2.

(a)

(2%) Without actually solving the equation, explain why there is a root of f(x) between x=0 and x=1.

(b)

(2%) Write down the Newton iteration formula.

(c)

(3%) To use the successive substitution method, we can have an iterative formula: $x_n = x_{n-1}-\alpha f(x_{n-1})$. What is the range for $\alpha$ such that the formula can converge to the root between x=0 and x=1?

5.

(5%) The following equations represent two ellipses:

$$\left\{ \begin{array} {rcl} (x-2)^2+(y-3+2x)^2 & = & 5\\ 2(x-3)^2+(y/3)^2 & = & 4 \end{array} \right.$$

We are going to find its solution via the Newton iteration.

(a)

(3%) What is the Jacobian matrix?

(b)

(2%) What is the iteration formula? (Just write down the formula; you don't need to expand or simplify it.)

6.

(8%) What transformations are necessary to make the following equations linear in terms of the undetermined coefficients $\alpha$, $\beta$, $\gamma$, and so on?

(a)

(2%) $y=\alpha e^{\beta x}$

(b)

(2%) $y=\frac{\textstyle 1}{\textstyle 1+\beta x^\alpha}$

(c)

(2%) $y=\frac{\textstyle 1} {\textstyle 1+ e^{\frac{\alpha x}{\beta + x}}}$

(d)

(2%) $y=\ln \alpha + x - \ln(\beta+e^x)$

7.

(6%)

(a)

(2%) What is the least-squares solution to ${\bf A}\mbox{\boldmath$\theta$}={\bf y}$?

(b)

(2%) What is the preferable one-line command for computing the least-squares solution to the above equation?

(c)

(2%) What error measure (or objective function) is minimized by the answers in (a) and (b)?