xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

考试代写-CMPUT 340

时间：2021-04-19

University of Alberta

Computing Science Department

CMPUT 340 - Winter 2021

Sample Final

Introduction to Numerical Methods (CMPUT 340)

1. (Heath 2018) Consider the nonlinear equation

f(x) = x2 − 2 = 0

a) With x0 = 1 as a starting point, what is the value of x1 if you use Newton’s method for solving

this problem?

b) With x0 = 1 and x1 = 2 as a starting points, what is the value of x2 if you use the secant method

for solving this problem?

2. (Heath 2018) Write out Newton’s iteration for solving each of the following nonlinear equations:

a) x3 − 2x− 5 = 0

b) e−x = x

c) x sin(x) = 1

3. (Heath 2018) On a computer with no functional unit for floating-point division, one might instead

use multiplication by the reciprocal of the divisor. Apply Newton’s method to produce an iterative

scheme for approximating the reciprocal of a number y > 0. Considering the intended application,

your formula should contain no divisions.

4. Consider a function f : Rn → R given by

f(x) =

1

2

xTAx− xT b+ c ,

where x and b are vectors, A is a matrix, and c is a constant. Explain in English why Newton’s method

is able to find the minimum of the equation above in a single step for any starting point x0.

5. Prove that any local minimum of a convex function f on a convex set S ⊆ Rn is a global minimum of

f on S.

6. Consider a procedure for finding the minimum of the function depicted in the image below in the

interval [a, b]. We will assume that the function is convex in the interval.

1

a) Given that f(x1) > f(x2), what is the smallest interval involving values a, x1, x2, b that will

contain the minimum of the function?

b) The bisection algorithm reduces the interval [a, b] using the procedure described in (a) to reduce

the bracket containing the minimum of the function. The algorithm’s efficiency clearly depends

on the choice of x1 and x2. Describe a method for choosing x1 and x2 and explain how this is

more efficient than using arbitrary values of x1 and x2.

7. (Heath 2018) Given the three data points (−1, 1), (0, 0), (1, 1), determine the interpolating degree two:

a) Using the monomial basis

b) Using the Lagrange basis

c) Using the Newton basis

Can you see that all three approaches give the same polynomial?

8. (Heath 2018) Express the following polynomial in the correct form for evaluation by Horner’s method

(the nested form we studied in class)

p(t) = 5t3 − 3t2 + 7t− 2

Why is the nested form more efficient than the exponential form written above?

9. Using the composite midpoint quadrature rule, compute the approximate value for the integral

∫ 1

0

x3dx,

using a mesh size (subinterval length) of h = 1 and also using h = 0.5. Compare the results.

10. Using the computational graph below compute the partial derivatives of the following function with

respect to x0, x1, w0, w1, b: g(w0, w1, b, x0, x1) = 11+exp(−(w0·x0+w1·x1+b)) .

x0

w0

x1

w1

b

∗

∗ + + ∗ − 1 exp +1 1/x g

2

−1

−3

−2

−3

−2

6 4 1 −1 0.367 1.367 0.731

2

学霸联盟

Computing Science Department

CMPUT 340 - Winter 2021

Sample Final

Introduction to Numerical Methods (CMPUT 340)

1. (Heath 2018) Consider the nonlinear equation

f(x) = x2 − 2 = 0

a) With x0 = 1 as a starting point, what is the value of x1 if you use Newton’s method for solving

this problem?

b) With x0 = 1 and x1 = 2 as a starting points, what is the value of x2 if you use the secant method

for solving this problem?

2. (Heath 2018) Write out Newton’s iteration for solving each of the following nonlinear equations:

a) x3 − 2x− 5 = 0

b) e−x = x

c) x sin(x) = 1

3. (Heath 2018) On a computer with no functional unit for floating-point division, one might instead

use multiplication by the reciprocal of the divisor. Apply Newton’s method to produce an iterative

scheme for approximating the reciprocal of a number y > 0. Considering the intended application,

your formula should contain no divisions.

4. Consider a function f : Rn → R given by

f(x) =

1

2

xTAx− xT b+ c ,

where x and b are vectors, A is a matrix, and c is a constant. Explain in English why Newton’s method

is able to find the minimum of the equation above in a single step for any starting point x0.

5. Prove that any local minimum of a convex function f on a convex set S ⊆ Rn is a global minimum of

f on S.

6. Consider a procedure for finding the minimum of the function depicted in the image below in the

interval [a, b]. We will assume that the function is convex in the interval.

1

a) Given that f(x1) > f(x2), what is the smallest interval involving values a, x1, x2, b that will

contain the minimum of the function?

b) The bisection algorithm reduces the interval [a, b] using the procedure described in (a) to reduce

the bracket containing the minimum of the function. The algorithm’s efficiency clearly depends

on the choice of x1 and x2. Describe a method for choosing x1 and x2 and explain how this is

more efficient than using arbitrary values of x1 and x2.

7. (Heath 2018) Given the three data points (−1, 1), (0, 0), (1, 1), determine the interpolating degree two:

a) Using the monomial basis

b) Using the Lagrange basis

c) Using the Newton basis

Can you see that all three approaches give the same polynomial?

8. (Heath 2018) Express the following polynomial in the correct form for evaluation by Horner’s method

(the nested form we studied in class)

p(t) = 5t3 − 3t2 + 7t− 2

Why is the nested form more efficient than the exponential form written above?

9. Using the composite midpoint quadrature rule, compute the approximate value for the integral

∫ 1

0

x3dx,

using a mesh size (subinterval length) of h = 1 and also using h = 0.5. Compare the results.

10. Using the computational graph below compute the partial derivatives of the following function with

respect to x0, x1, w0, w1, b: g(w0, w1, b, x0, x1) = 11+exp(−(w0·x0+w1·x1+b)) .

x0

w0

x1

w1

b

∗

∗ + + ∗ − 1 exp +1 1/x g

2

−1

−3

−2

−3

−2

6 4 1 −1 0.367 1.367 0.731

2

学霸联盟