4. Homework #4ΒΆ

For all programming assignments, please turn in your code along with your solution. Submissions should be made on Sakai.

Problem 1

Consider the following procedure for solving the nonlinear equation \(f(x)=0\):

  • Start with an initial guess \(x_0\).

  • For \(k=0,1,2,\ldots\) do the following:

    • Compute the value that standard Newton’s method would provide, and call it \(\hat x_{k+1}\), i.e.,

      \[\hat x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}\]

    • Compute the next approximation \(x_{k+1}\) by averaging \(x_k\) and \(\hat x_{k+1}\), i.e.,

      \[x_{k+1} = \frac{x_k + \hat x_{k+1}}{2}\]
  1. Show that if this method converges, it will converge to a solution of \(f(x)=0\).
  2. Show that this method converges under the same conditions as Newton’s method.
  3. Determine the order of convergence of this method.

Problem 2

For the equation

\[f(x) = x^2 - 3x + 2 = 0\]

each of the following functions yields an equivalent fixed-point problem:

\[\begin{split}g_1(x) & = & \enspace (x^2+2)/3 \\ g_2(x) & = & \enspace \sqrt{3x-2} \\ g_3(x) & = & \enspace 3 - 2/x \\ g_4(x) & = & \enspace (x^2 - 2)/(2x - 3)\end{split}\]
  1. Analyze the convergence properties of each of the corresponding fixed-point iteration schemes for the root \(x=2\) by considering \(\lvert g_i'(2) \rvert\).
  2. Confirm your analysis by implementing each of the schemes and verifying its convergence (or lack thereof) and approximate convergence rate.

Problem 3

Implement the bisection, Newton, and secant methods for solving nonlinear equations in one dimension, and test your implementations by finding at least one root for each of the following equations. What termination criterion should you use? What convergence rate is achieved in each case?

  1. \(x^3 - 2x - 5 = 0\).
  2. \(e^{-x} = x\).
  3. \(x \sin x = 1\).
  4. \(x^3 - 3x^2 + 3x - 1 = 0\).

Problem 4

Suppose you are using the Secant method to find a root \(x^\star\) of a nonlinear equation \(f(x) = 0\). Show that if at any iteration it happens to be the case that either \(x_k = x^\star\) or \(x_{k-1} = x^\star\) (but not both), then it will also be true that \(x_{k+1} = x^\star\).