m136_le1_reviewer.pdf

Math 136 Introduction to Numerical Analysis First Long Examination Reviewer University of the Philippines Baguio Second Semester, A.Y. 2023-2024 1. Write TRUE if the statement is always true. Ot...

Math 136 Introduction to Numerical Analysis First Long Examination Reviewer University of the Philippines Baguio Second Semester, A.Y. 2023-2024 1. Write TRUE if the statement is always true. Otherwise write FALSE. (a) Codes are algorithms written in a specific programming language. (b) Polynomials of degree n have exactly n real zeros. (c) Machine epsilon eps has the property that for any ϵ < eps, the numbers 1 and 1 + ϵ are the same in computer arithmetic. (d) Truncation errors are obtained when continuous models are replaced by discrete and finite processes for computability. (e) Given any base β and positive integer d, any real number can be approximated by a real number with a β-positional representation with d digits. (f) qk is always constant in the Secant Method. (g) All the roots of a polynomial whose coefficients are all 1 are on or within the circle centered at the origin with radius 1 in the complex plane. (h) All square matrices have LU factorization (i) The convergence of Newton’s method does not depend on the initial iterate. (j) Jacobi method uses the diagonal of the coefficient matrix as the iteration matrix in its update scheme. 2. Give concise statements (at most 3 sentences only) that answers the following: (a) Explain the difference between Absolute Errors and Relative Errors. (b) Explain why we sometimes prefer codes with reduced number of function evaluations. (c) Which is better, iterative methods or substitution methods? Explain your answer. (d) Suppose that A, B, C,.... , I are the zeros of f. At what zero of f will the bisection method converge to if we consider the interval [−5, 2]? How about [−4, 2]? If it does not converge, reason out why. A B C D E F G H I J −6 −5.5 −5 −4.5 −4 −3.5 −3 −2.5 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 2.5 3 f 3. (5 points) Given the following python code of the Horner method, determine the error/s in order to have a smooth implementation of the method. Write the line number of the wrong part and the correct code beside it. Explain your solution as needed.  1 import np a s numpy 2 def horner (p , z ) : 3 ”” 4 E v a l u a t i o n o f p ( a ) = a0 + a1 ∗x +... + an∗xˆn a t z 5 and l i n e a r f a c t o r i z a t i o n with r e m a i n d e r p 6 Arguments : 7 p ( array ) : [ a0 a1... an ] c o e f f i c i e n t s o f p o l y n o m i a l 8 z ( complex ) : complex number t o be e v a l u a t e d 9 Returns : 10 b [ 0 ] ( complex ) : v a l u e o f p ( z ) 11 b [1... n ] ( array ) : f a c t o r i z a t i o n of 12 p ( x ) = ( x−z ) ∗ b [ 1... n ] + p ( z ) 13 ””” 14 lenp = len (p) 15 b = np. z e r o s ( lenp , dtype=complex ) 16 b [ lenp ] = p [ lenp ] 17 f o r k i n r a n g e ( lenp −2 ,0 , −1): 18 b [ k ] = p [ k ] + b [ k +1]∗ z 19 return b [ 0 ] , b [ range (1 , lenp ) ] Line # Correct Code 4. State and prove the Fixed Point Theorem. 5. Let f ∈ C 2 (R) and x∗ be a simple root of f , i.e. f (x∗ ) = 0 and f ′ (x) ̸= 0. (a) Prove that there exists closed interval [a.b] such that the sequence {xk }k∈N generated by the Newton-Raphson method converges to the root x∗ for any x0 ∈ [a.b]. (b) Prove that the convergence rate is quadratic. 6. Show that the function f (x) = xex+2 + 1 has a root. Approximate the root using the Newton-Raphson Method with the initial iterate x0 = 1/2. 7. Consider the following system −a − b + 4c = 9 −a + 4b − c = −7 4a − b − c = 5. (a) Solve the system using substitution method. (b) Let the initial iterate be (a0 , b0 , c0 ) = (1, 0, 0) and use the Jacobi method to find the solution after 3 iterates, i.e. the value of (a3 , b3 , c3 ). Compute also for the absolute error. First Long Examination Scoring Written Part 1. TRUE or FALSE (10 points) 2. Explanations ( 5 points) 3. Python code ( 5 points) 4. Proving (15 points) 5. Scalar Root Finding ( 5 points) 6. Systems of Equations ( 10 points) First Long Examination Coverage Fundamental Concepts Algorithms Sources of Errors Machine Representation and Operations (Machine Epsilon, Cancellation Error) Scalar Root Finding Methods Bisection Method First Order Approx. (Chord, Secant, Regula-Falsi, Newton–Raphson, Steffensen) Fix Point Iterations Convergence of Root Finding Methods Zeros of Polynomials (Deflation, Newton–Horner) Linear and Nonlinear Systems Linear Systems (Triangular Systems, LU Factorization and Pivoting, Jacobi Method, Gauss–Seidel Method) Nonlinear Systems (Newton Method) jgbueno 11042024