CS323: Homework #1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS323: Homework #1
Due: Thursday, February 9th, 2023 by 11:59PM
Sum of all problems: 160%.
For the following problems, even if you do not answer a given question, you are still allowed to use its result in order to answer a subsequent question.
1. [20%] Each of the following examples describes a fixed point iteration and a nonlinear equation. In each case, assuming that the fixed point iteration will converge, show that the limit is a solution of the respective equation.
(a) The iteration xk+1 = and the equation ax2 + bx + c = 0. (b) The iteration xk+1 = 34(x)2kxk(+)a and the equation x2 _ a = 0.
2. [30%] Consider the following pairs, each containing one nonlinear equation and one iterative procedure:
(a) The equation ex = x + 2 and the iterative method
xk+1 = exk _ 2
(b) The equation x3 = x2 + 1 and the iterative method
xk
xk+1 =
For each case, examine if the given iterative procedure is an effective solution technique for the respective equation. In order for the method to be effective, it needs to (a) be guaranteed to converge and (b) converge to a solution of the given equation.
3. [30%] Use Newton’s method to generate an iterative process that converges to the following values:
(a) Create an iterative procedure that computes the cube root ^3a of a given number a. You are not allowed to use roots in the formula. [Hint: The cube root is the solution of x3 _ a = 0.]
(b) Create an iterative procedure that computes the natural logarithm log a of a given number a. You are not allowed to use logarithms in the formula (exponentials are ok).
(c) Create an iterative procedure that computes the arc-tangent arctan(x) of a given number x (remember, the arc-tangent of x is the angle whose tangent equals x). You are not allowed to use inverse trigono- metric functions in the formula (normal trigonometric functions such as sin, cos, tan, etc., are ok).
4. [40%] Consider the following procedure for solving the nonlinear equation f (x) = 0:
● Start with an initial guess x0 .
● For k = 0, 1, 2, . . . do the following:
– Compute the value that standard Newton’s method would pro- vide, and call it k+1, i.e.,
f (xk )
k+1 = xk _
– Compute the next approximation xk+1 by averaging xk and
k+1, i.e.,
xk + k+1
2
(a) [10%] Show that if this method converges, it will converge to a solu- tion of f (x) = 0.
(b) [15%] Show that this method converges under the same conditions as Newton’s method.
(c) [15%] Determine the order of convergence of this method.
5. [40%] Implement bisection, Newton, and secant methods for solving non- linear equations in one dimension, and test your implementations by find- ing at least one root for each of the following equations. What termination criterion should you use? What convergence rate is achieved in each case?
(a) [10%] x3 _ 2x _ 5 = 0.
(b) [10%] e-x = x.
(c) [10%] x sin x = 1.
(d) [10%] x3 _ 3x2 + 3x _ 1 = 0.
2023-01-30