Anhui University Semester 1, 2004-2005 Final Examination(Paper A) Model answer and referee criterion for Numerical analusis In question 1-6, please choose the correct answer (only one is correct) 1.(5 marks)Word” MATLAB” comes form A Mathematics Laboratory (B)Matrix Laboratory (C) Mathematica Laboratory (D) Maple Laboratory Answer. B) 2.(5 marks) The matrix 215 (a)a strictly diagonally dominant matrix; (B) not a strictly diagonally dominant matrix (C) a singular matrix; () a matrix whose determinant is equal to zero A (A) 3.(5 marks)The computational complexity of Gaussian elimination for solv- ing linear equation systems AX=B(A is N X N matrix)is A)O(N),(B) ),(C)O(N3),(D)O(N4) 4.(5 marks) Assume that f(a) is defined on [a, b, which contains equall spaced nodes Ck=co+hk. Additionally, assume that f"(a)is continuous a,b. If we use Lagrange interpolation polynomial PI E (A)O(1)(B)O(h)(C)O(h2)(D)O(h3) Answer.(C) 5.(5 marks) Degree 4 Chebyshev Polynomial T4( )is
Anhui University Semester 1, 2004-2005 Final Examination (Paper A) Model Answer and Referee Criterion for Numerical Analysis In question 1-6, please choose the correct answer (only one is correct) 1. (5 marks) Word ”MATLAB” comes form (A) Mathematics Laboratory (B) Matrix Laboratory (C) Mathematica Laboratory (D) Maple Laboratory Answer. (B) 2. (5 marks) The matrix 4 −1 1 4 −8 1 −2 1 5 is (A) a strictly diagonally dominant matrix; (B) not a strictly diagonally dominant matrix; (C) a singular matrix; (D) a matrix whose determinant is equal to zero. Answer. (A) 3. (5 marks) The computational complexity of Gaussian elimination for solving linear equation systems AX = B (A is N × N matrix) is (A) O(N), (B) O(N 2 ), (C) O(N 3 ), (D) O(N 4 ). Answer. (C) 4. (5 marks) Assume that f(x) is defined on [a, b], which contains equally spaced nodes xk = x0 + hk. Additionally, assume that f 00(x) is continuous on [a, b]. If we use Lagrange interpolation polynomial P1(x) = X 1 k=0 f(xk)L1,k(x) to approximate f(x), then the error E1(x) is (A) O(1) (B) O(h) (C) O(h 2 ) (D) O(h 3 ) Answer. (C) 5. (5 marks) Degree 4 Chebyshev Polynomial T4(x) is 1
a an odd function (B) an even function (C)not odd or even function,(D) both odd and even function Answer.(B) 6.(5 marks)Pade Approximation is a)A rational polynomial approximation b)A polynomial approximation (C) A triangular polynomial approximation (D) A linear function approximation Answer.(A) 7.(15 marks) Use the false position method to find the root of r sin()-1=0 that is located in the interval 0, 2(the function sin (a)is evaluated in radians) Solution. Starting with a0=0 and bo= 2, we have f(0)=-1 and f(2) 0.8186. so a root lies in the interval [ 0. 2 ImaI Using formula ∫(bn)(bn-an ∫(bn)-f(an) Imar 0.818 =1.0997andf(co)=-0.0200 The function changes sign on the interval [co, bo]=[1.0997, 2, so we squeeze from the left and set a1= co and b1= bo. The formula produces the next approximation: 08186(2-10997 0.8186-(-0.0200) =1.1212 f(c1)=0.0098 Next f(r) changes sign on [a1, c1=[1.0997, 1. 1212, and the next decision is to squeefrom the right and set a2= a1 and b2=C1. Hence we get c2=1. 1141 f(c2)=0.0000 15 marks 8.(15 marks) In the following linear equation systems 2x+y-5x=15
(A) an odd function, (B) an even function (C) not odd or even function, (D) both odd and even function Answer. (B) 6. (5 marks) Pad´e Approximation is (A) A rational polynomial approximation (B) A polynomial approximation (C) A triangular polynomial approximation (D) A linear function approximation Answer. (A) 7. (15 marks) Use the false position method to find the root of x sin(x)−1 = 0 that is located in the interval [0, 2] (the function sin(x) is evaluated in radians). Solution. Starting with a0 = 0 and b0 = 2, we have f(0) = −1 and f(2) = 0.8186, so a root lies in the interval [0, 2]. · · · 2 marks Using formula cn = bn − f(bn)(bn − an) f(bn) − f(an) , · · · 7 marks we get c0 = 2 − 0.8186(2 − 0) 0.8186 − (−1) = 1.0997 and f(c0) = −0.0200 The function changes sign on the interval [c0, b0] = [1.0997, 2], so we squeeze from the left and set a1 = c0 and b1 = b0. The formula produces the next approximation: c1 = 2 − 0.8186(2 − 1.0997) 0.8186 − (−0.0200) = 1.1212 and f(c1) = 0.0098. · · · 11 marks Next f(x) changes sign on [a1, c1] = [1.0997, 1.1212], and the next decision is to squeefrom the right and set a2 = a1 and b2 = c1. Hence we get c2 = 1.1141 and f(c2) = 0.0000 · · · 15 marks 8. (15 marks) In the following linear equation systems 4x − y + z = 7 4x − 8y + z = −21 −2x + y − 5z = 15, 2
Will Gauss-Seidel iteration converge to the solution? to find P& for k=1,2 start with Po=(1, 2, 2), and use Gauss-Seidel iteration Solution. The Gauss-Seidel iteration is 7+k 21+4xk+1+zk 15+2 5 7 marks Substitute yo=2 and z0=2 into the first equation of the systems above and 7+2-2 =1.75 4 Then substitute 1= 1.75 and 20= 2 into the second equation and get 21+4(1.75)+2 3.75 Finally, substitute 1=1.75 and y1=3.75 into the third equation to get 2.95. 5 Using the same reason, we get 3.96 2.98 Since the exact solution of the linear equation systems is P=(2, 4, 3),Gauss- eidel iteration Pk will converge to the solution 9.(15 marks) Consider y= f(r)= cos (a) over 0.0, 1.2]. Use the three nodes To=0.0, 1=0.6, and a2=1.2 to construct a quadratic interpolation polynomial P2(a) Solution. The quadratic Lagrange interpolation polynomial for f(a)is P(x)=∑L2(x) k=0 (x-x1)(x-x2) (x-x0)(x-x2) (x-x0)(x-x1) (x0-x1)(x0-x2)(x1-x0)(x1-x2)( 7 marks Us 0.0 0.6 1.2 and 0.0)=1, (0.6) 0.8253, and y2= cos(1. 2)=0.3623 in the formula above produces P2(x)=1.0 (x-0.6)(x-1.2) 00-06(00-12)+08253 (x-0.0)(x-1.2) (0.6-0.0)(0.6-1.2)
start with P0 = (1, 2, 2), and use Gauss-Seidel iteration to find Pk for k = 1, 2. Will Gauss-Seidel iteration converge to the solution? Solution. The Gauss-Seidel iteration is xk+1 = 7 + yk − zk 4 yk+1 = 21 + 4xk+1 + zk 8 zk+1 = 15 + 2xk+1 − yk+1 5 · · · 7 marks Substitute y0 = 2 and z0 = 2 into the first equation of the systems above and obtain x1 = 7 + 2 − 2 4 = 1.75. Then substitute x1 = 1.75 and z0 = 2 into the second equation and get y1 = 21 + 4(1.75) + 2 8 = 3.75. Finally, substitute x1 = 1.75 and y1 = 3.75 into the third equation to get z1 = 15 + 2(1.75) − 3.75 5 = 2.95. Using the same reason, we get x2 = 1.95, y2 = 3.96, and z2 = 2.98 · · · 13 marks Since the exact solution of the linear equation systems is P = (2, 4, 3), GaussSeidel iteration Pk will converge to the solution. · · · 15 marks 9. (15 marks) Consider y = f(x) = cos(x) over [0.0, 1.2]. Use the three nodes x0 = 0.0, x1 = 0.6, and x2 = 1.2 to construct a quadratic interpolation polynomial P2(x). Solution. The quadratic Lagrange interpolation polynomial for f(x) is P2(x) = X 2 k=0 ykL2,k(x) = y0 (x − x1)(x − x2) (x0 − x1)(x0 − x2) + y1 (x − x0)(x − x2) (x1 − x0)(x1 − x2) + y2 (x − x0)(x − x1) (x2 − x0)(x2 − x1) · · · 7 marks Using x0 = 0.0, x1 = 0.6, x2 = 1.2 and y0 = cos(0.0) = 1, y1 = cos(0.6) = 0.8253, and y2 = cos(1.2) = 0.3623 in the formula above produces P2(x) = 1.0 (x − 0.6)(x − 1.2) (0.0 − 0.6)(0.0 − 1.2) + 0.8253 (x − 0.0)(x − 1.2) (0.6 − 0.0)(0.6 − 1.2) 3
0.0)(x-0.6) +0.3623 12-0.0)(12-0.6) =1.388-0.6)(x-1.2)-2.2925(x-0.0)(x-1.2) +0.5032(x-0.0)(x-0.6 10.(15 marks)Consider f(r)=2+sin(2v ). Use the composite Simpson rule with 1l sample points to compute an approximation to the integral of ∫(x) taken over[1,6 1)/10=1/2. Using formula ple points, we must use S(b)=a(f)+f()+3a2)+3x 7 marks the computation is S(f,)=(f(1)+f(6)+(f(2)+∫(3)+f(4)+f(5) (f(。)+f()+f(言+f()+( (29092+1.0173) (23080+1.6830+1.2431+1.0287) +(26381+1.9793)+1.4353+1.1083+1.0002 3(39166+)+362630)+381613 0.6544+2.0876+5.4408=8.1830 15 11.(10 marks)Assume that g E Cla, b. If the range of the mapping y=g(a) satisfies y∈a,列 for all x∈a,b, then g has a fixed point in[a,b Proof. If g(a)= a or g(b)=b, the assertion is true. Otherwise, the values f(a)=r-g(a)has the property tlli(a, b) and g()E [a, b). The function of g(a) and g(b) must satisfy g(a)E f(a)=a-g(a)0. Now apply Zero Value Theorem to f(r), and conclude that there exists a number P with P E(a, b) so that f(P)=0. Therefore, P=g(P) and P is the desired fixed point of g(a) marks
+0.3623 (x − 0.0)(x − 0.6) (1.2 − 0.0)(1.2 − 0.6) = 1.3888(x − 0.6)(x − 1.2) − 2.2925(x − 0.0)(x − 1.2) +0.5032(x − 0.0)(x − 0.6). · · · 15 marks 10. (15 marks) Consider f(x) = 2 + sin(2√ x). Use the composite Simpson rule with 11 sample points to compute an approximation to the integral of f(x) taken over [1, 6]. Solution. To generate 11 sample points, we must use M = 5 and h = (6 − 1)/10 = 1/2. Using formula S(f, h) = h 3 (f(a) + f(b)) + 2h 3 M X−1 k=1 f(x2k) + 4h 3 X M k=1 f(x2k−1), · · · 7 marks the computation is S(f, 1 2 ) = 1 6 (f(1) + f(6)) + 1 3 (f(2) + f(3) + f(4) + f(5)) + 2 3 (f( 3 2 ) + f( 5 2 ) + f( 7 2 + f( 9 2 ) + (11 2 ) = 1 6 (2.9092 + 1.0173) + 1 3 (2.3080 + 1.6830 + 1.2431 + 1.0287) + 2 3 (2.6381 + 1.9793) + 1.4353 + 1.1083 + 1.0002) = 1 6 (3.9166+) + 1 3 (6.2630) + 2 3 (8.1613) = 0.6544 + 2.0876 + 5.4408 = 8.1830. · · · 15 marks 11. (10 marks) Assume that g ∈ C[a, b]. If the range of the mapping y = g(x) satisfies y ∈ [a, b] for all x ∈ [a, b], then g has a fixed point in [a, b]. Proof. If g(a) = a or g(b) = b, the assertion is true. Otherwise , the values of g(a) and g(b) must satisfy g(a) ∈ (a, b] and g(b) ∈ [a, b). The function f(x) = x − g(x) has the property that f(a) = a − g(a) 0. · · · 5 marks Now apply Zero Value Theorem to f(x), and conclude that there exists a number P with P ∈ (a, b) so that f(P) = 0. Therefore, P = g(P) and P is the desired fixed point of g(x). · · · 10 marks 4