Scribd Logo
Upload

Welcome to Scribd!

  • 81 views

    Midterm 2016 Corr

    Uploaded by

    antoine demeire
    The document is a summary of a midterm exam for an engineering course. It contains 14 multiple choice and free response questions on topics like Gaussian elimination, Newton's method, floating point arithmetic, and Taylor series approximations. Students were instructed to show their work, manage their time carefully, and answer all questions directly on the form.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Midterm 2016 Corr

    Uploaded by

    antoine demeire
    81 views4 pages
    The document is a summary of a midterm exam for an engineering course. It contains 14 multiple choice and free response questions on topics like Gaussian elimination, Newton's method, floating point arithmetic, and Taylor series approximations. Students were instructed to show their work, manage their time carefully, and answer all questions directly on the form.

    Original Description:

    MECH 309 Midterm F2016 Corr

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document is a summary of a midterm exam for an engineering course. It contains 14 multiple choice and free response questions on topics like Gaussian elimination, Newton's method, floating point arithmetic, and Taylor series approximations. Students were instructed to show their work, manage their time carefully, and answer all questions directly on the form.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    81 views4 pages

    Midterm 2016 Corr

    Uploaded by

    antoine demeire
    The document is a summary of a midterm exam for an engineering course. It contains 14 multiple choice and free response questions on topics like Gaussian elimination, Newton's method, floating point arithmetic, and Taylor series approximations. Students were instructed to show their work, manage their time carefully, and answer all questions directly on the form.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    MECH309 Midterm Exam February 25, 2016 11:35am-12:55pm

    Closed note, closed book exam. No calculator allowed.


    Read over all questions carefully. Manage your time wisely. Answer all questions directly on this form.

    Quiz (4 points per question)


    Question 1 You want to solve n equations in n unknowns and decide to use Newtons method. Every iteration in Newtons method requires
    solving a system of linear equations. In order to solve this system of linear equations, which strategy is best: Gaussian elimination or Jacobis
    method? Explain.
    Answer 1 Gaussian elimination as it works for a much wider class of linear systems than Jacobi. It might still fail though, if, at some point in
    Newtons iterations, the system of linear equations to be solved is singular.

    Question 2 The finite difference scheme approximates the derivative of a function as follows:

    f .x C h/ f .x/
    f 0 .x/ 
    h
    Knowing that h theoretically tends to 0, list possible issues that would emerge in floating-point arithmetics.
    Answer 2 Round-off errors emerge as follows:
    1. Loss of significance (fewer significant digits) due to the subtraction of similar numbers: f .x C h/  f .x/ when h small
    2. Dividing by a small number h. See Gaussian elimination for instance.
    Another source of error here is truncation error in the Taylor expansion with remainder of f .x C h/ where higher-order terms involving
    powers of h were ignored. See chapter 6 of the lecture notes. An optimal h, compromise between the contradictory truncation and round-off
    errors, can actually be found.

    Question 3 The matrix A of a system of linear equations Ax D b is given as follows:


     
    2 2
    AD
    1 2

    Does Jacobis iteration converge?


    Answer 3 Matrix A is not strictly diagonally dominant and a finer condition should be stated to answer the question. Let us have a look at the
    eigenvalues of T D D 1 .L C U/ with:
           
    2 0 0 0 0 2 0 1
    DD I LD I UD ) TD (1)
    0 2 1 0 0 0 1=2 0
    p
    The two eigenvalues of T are 1= 2 and .T/ < 1. Jacobis iteration converges.

    Question 4 Estimate the number of basic operations involved in calculating a polynomial of degree n at a point x:

    p.x/ D a0 C a1 x C : : : C an x n

    Compare with its nested version:

    p.x/ D .: : : ..an x C an 1 /x C an 2 /x C : : : C a1 /x C a0

    Answer 4 O.n2 / in the non-nested version versus O.n/ in the nested version.

    Question 5 Within the Gaussian elimination approach, you decide to implement a stopping criterion through a tolerance ". Which stopping
    criterion is a good choice?
    Answer 5 No stopping criteria in Gaussian elimination as the method converges in a finite number of operations.

    Question 6 Find the rate of convergence of the following sequence as n ! C1:

    cos.sin.1=n/ C 1/

    Answer 6 The sequence converges to the limit cos.1/ at a O.1=n/ rate.

    1
    Question 7 Circle the correct answer: Apply Newtons method to h.x/ D 8x 8x 3 . Does Newtons iteration converge using the given initial
    guess x1 D 0:5:
    A. Yes, the iterations converge to x D 1.
    B. Yes, although it does not converge to x D 1.
    C. No, Newtons method diverges using this guess.
    D. No, the iterations oscillate forever.
    E. More information is needed to answer this question.
    Answer 7 Answer B. [This question is ignored in the final grade unless you have the correct answer].

    Question 8 Assume a decimal (base 10) floating-point machine able to store no more than 5 digits with an exponent range of 15. What is
    the result of each of the following floating-point arithmetic operations?
    1. 1 C 10 7
    2. 1 C 104
    3. 1010 C 104
    4. 109 =10 7
    5. 10 9 =10 7
    Answer 8
    1. 1
    2. 10001
    3. 1010
    4. overflow
    5. 10 2

    56 55
    Question 9 How many digits does the number 10 9  10 have?
    Answer 9 2. Let us have a look at 0:1 9D 8:9. The other digits are leading 0 that are not considered as digits but stored in a power of 10
    instead.

    Question 10 True or false: If two real numbers are exactly representable as floating-point numbers, then the result of a real arithmetic
    operation on them will also be exactly representable as a floating-point number.
    Answer 10 False. See question 2.

    Question 11 Use the third-order Taylor polynomial about h D 0 to show that


    1
    sin h h C h3 D O.h5 / when h!0
    6
    Answer 11 Use Taylor expansion with remainder up to h5 of sinus and bound the last term.

    Question 12 For a given floating-point number system, describe in words the distribution of machine numbers along the real line.
    Answer 12 They are distributed logarithmically because of the powers of 10 (or 2 in a binary base) in their definition.

    Question 13 Consider the following system of two equations in two variables .x; y/:

    yx C x 3 D x
    (

    x2 C y 1D0
    Completely define the solution space.
    Answer 13 The first equation is the second equation multiplied by x. The solution space is thus defined by the second equation as x D 0 is
    not always a solution, ie f.x; y/ j y D 1 x 2 g.

    Question 14 Suppose we wish to compute the square root of a given positive number y. Provide the corresponding nonlinear equation to be
    solved.
    Answer 14 Solve in x the equation x 2 y D 0.

    Question 15 In a floating-point system, what quantity determines the maximum relative error in representing a given real number by a
    machine number?
    Answer 15 mach

    2
    Exercise 1 [10 points]
    Solve the linear system below by Gaussian elimination.

    x1 x2 C 2x3 D 8
    2x1 2x2 C 3x3 D 20
    x1 C x2 C x3 D 2

    Solution
    Very basic. Not solved.

    Exercise 2 [15 points]


    Assuming x 1, consider the expression:
    1 1
    1 x xC1
    1. For what range of values of x is it difficult to compute this expression accurately in floating-point arithmetic?
    2. Rearrange the terms so that, for the range of x in part 1., the computation is more accurate in floating-point arithmetic.

    Solution
    1. Error occurs when x is around 1, 1 and 0.
     When x is around 0, that is when x is very small in absolute value, 1=.1 x/ is similar to 1=.1 C x/, and subtraction of similar
    numbers is likely to give poor approximation.
     When x is around 1 or 1, two issues may occur. First, dividing by a very small number may cause Overflow. Second, subtracting
    a big number and a normal number may induce lost of accuracy.
    2. Simply rearrange the expression into 2x=.1 x 2 /: the only remaining issue is potential Overflow when x is around 1 or 1.

    Exercise 3 [15 points]


    A tri-diagonal band system is a system of linear equations where the matrix is of the form:
    2 3
    b1 c1 0 ::: 0
    6 :: :: 7
    6a2 b2
    6 c2 : : 77
    AD60
    6 : :: : :: : :: 7
    6 0 7 7
    6: :
    4 :: :: a
    7
    n 1 bn 1 cn 1 5
    0 ::: 0 an bn

    Assuming that matrix A is invertible and that no row interchange is needed, adapt the Gaussian elimination technique to this system of
    equations. Detail you reasoning and provide the algorithm (pseudo-code or Matlab language). [Skip the backward-substitution step]

    Solution
    The idea of this exercise was to simplify the Gaussian elimination procedure to the minimum number of required operations. The proposed
    matrix A is said to be sparse as it stores many zeros. Algorithmically, it is useless to compute operations involving zeros and the Gaussian
    elimination should thus be adapted accordingly. The algorithm simplifies as follows:
    1: Input: A such that det.A/ 0
    2: for j from 1 to n 1 do
    3: i j C1
    4: mult aij =ajj
    5: aij 0
    6: ai i ai i mult aj i
    7: end for
    Only one loop (counter j ) on the columns of A is needed. The usual i and k loops highly simplify here because of the structure of A.

    3
    Bonus [10 points]
    You are given the number 112.2 in base b D 3. Translate it into base b D 2. Using base b D 10 is strictly prohibited (Assume you do not
    know it).

    Solution
    As we did in class from the decimal base to the binary base, the idea in this exercise is to perform the needed operations in base 3. First, it was
    important to note that 2 is base 3 is 2. Then:
     Integer part:

    112=2 D 21 C 0
    21=2 D 10 C 1
    10=2 D 1 C 1

    that is 122jbD3 D 1110jbD2


     fractional part:

    0:2  2 D 1:1 D 0:1 C 1


    0:1  2 D 0:2 D 0:2 C 0
    0:2  2 D 1:1 D 0:1 C 1

    pattern which repeats itself indefinitely. Thus, 0:2jbD3 D 0:101jbD2

    Final answer is: 122:2jbD3 D 1110:101jbD2

    You might also like