Subject: Numerical Computing

Subject: Numerical Computing

Code: C-09/T-09 (June 2003)

1. (a) Let or ² = N.

We take Newton-Raphson method becomes

= Answer: A

(b)

= Answer: C

H = - D^-1 (L + U). From the given matrix A, we get

H =

Eigen values of H are

Since the spectral radius of H is >1, the method diverges. Answer: D

(d) We first construct the forward difference table from the given data. We have

x f(x)

1 -1

2 -1 0

3 1 2 2

4 5 4 2 0

Using Newton forward difference interpolation and the given data, we get for h = 1

= x² – 3x + 1 Answer: B

(e) For the Simpsons rule

we obtain h = 1/2, x₀ = 0, x₂ = 1, x₁ = 1/2 , f₀ = 1, f₁ = 4/5, f₂ = 1/2

I = [1 + 4 (4/5) + 1/2]/6 = 47/60 Answer: D

(f) We need the approximation f(x) = ax + b, where a and b are to be determined so that

minimum. We obtain the normal equations

We have

Substituting in the normal equations, we get

30a + 10b = 30, 10a + 4b = 8

Solving, we get a = 2, b = -3 Answer : A

(g) The truncation error associated with the given method is given by

The method will be of the highest order, if the coefficient of f(x) is zero.

We get a = 0. Answer: B

(h) Make the method exact for f(x) = 1 and x. We get

which is true

Answer: C

2. (a) We have We find that f(-2) = 9.2484, f (-1) = 1.3791,

f(0) = - 3 , f(1) = -2.6209, f(2) = 1.2484.

Hence, the smallest root in magnitude lies in the interval (- 1, 0).

Using the secant method , we get for

, which is correct to three decimal places.

(b) We have x = N ^¼. Take f(x) = x⁴ – N = 0. Let be the exact root. Therefore, ⁴ = N.

Substituting in the given formula, we get

Expanding in binomial series and simplifying, we get

For the method to be of highest order, we have

a + b + c = 1, a – 3b – 7c = 0, 6b + 28c = 0

Solving these equations, we get a = 21/32, b = 14/32, c = -3/32 and

Hence, the method is of third order.

3. (a) We have .

We obtain the Jacobian matrix

and

Using Newton’s method , we get

(b) We write the given coefficient matrix A as

A = LL^T where . We obtain

Comparing element by element, we get,

First row: ,

Second row: ,

Third row:

Hence, we obtain

Write the given system of equations A x = b as L L ^Tx = b

or L^T x = z, L z = b

From L z = b, that is

we obtain using forward substitution

From L^T x = z, that is

we obtain using back substitution

4. (a) We obtain from the augmented matrix

1 -3 2 3 4 -3 1 4.25

[A b] = 2 6 8 -1 R₁R₃ 2 6 8 -1 R₂ – R₁/2

4 -3 1 4.25 1 -3 2 3 R₃ – R₁/4

4 -3 1 17/4

0 15/2 15/2 -25/8 R₃+ 3R₂/10

0 -9/4 7/4 31/16

4 -3 1 17/4

0 15/2 15/2 -25/8

0 0 4 1

Using back substitution, we get

(b) We obtain from the augmented matrix

[A I] = 2 1 2 1 0 0

1 2 -1 0 1 0 R₂ – R₁/2

2 4 3 0 0 1 R₃ – R₁

2 1 2 1 0 0

0 3/2 -2 -1/2 1 0 R₁ – 2R₂/3

0 3 1 -1 0 1 R₃ – 2R₂

2 0 10/3 4/3 -2/3 0

0 3/2 -2 -1/2 1 0 R₁ – 2R₃/3

0 0 5 0 -2 1 R₂+ 2R₃/5

2 0 0 4/3 2/3 -2/3

0 3/2 0 -1/2 1/5 2/5

0 0 5 0 -2 1 R₁/2, 2R₂/3, R₃/5

1 0 0 2/3 1/3 -1/3

0 1 0 -1/3 2/15 4/15

0 0 1 0 -2/5 1/5

2/3 1/3 -1/3 10 5 -5

Hence, A^-1 = -1/3 2/15 4/15 = -5 2 4

0 -2/5 1/5 0 -6 3

5. (a) From the given system of equations, we obtain

We have . From the above equations, we obtain

After four iterations, we obtain the solution

The iteration matrix associated with the Gauss-Seidal method is given by

H = - (D + L)^-1 U . We have

4 0 0 0 -2 1

D + L = 1 2 0 , U = 0 0 1

3 -3 5 0 0 0

1/4 0 0

(D + L)^-1= -1/8 1/2 0 . We obtain

-9/40 3/10 1/5

1/4 0 0 0 -2 1 0 1/2 -1/4

H = - -1/8 1/2 0 0 0 1 = 0 -1/4 -3/8

-9/40 3/10 1/5 0 0 0 0 -9/20 -3/40

Characteristics equation of the matrix H is given by

The eigen values of H are 0, 0.2575,

Since spectral radius is the method converges.

Rate of convergence = v =

(Note that rate of convergence can also be written as v =

(b) The largest off diagonal element in magnitude in A is a₁₃ = 2. We obtain

Define S₁ = and

Now the largest off-diagonal element in magnitude in A₁ is a₁₂ = 2. We obtain

Define S₂ = and

Hence, the eigen values of A are 6, 2 and 0.

6. (a) We have

4 1 0 11 -4 1

A = 1 3 1 A^-1 = -4 16 -4

0 1 4 1 -4 11

and V₀ = [0.4, - 0.9, 0.4]^T

We have , and

( is largest element in magnitude in )

We obtain

11 -4 1 0.4 0.21

k = 0 : Y₁ = - 4 16 -4 -0.9 = -0.44

1 -4 11 0.4 0.21

m₁ = 0.44 and V₁= Y₁/m₁ = [0.4773, - 1, 0.4773]^T

11 -4 1 0.4773 0.2432

k = 1 : Y₂ = - 4 16 -4 -1 = -0.4955

1 -4 11 0.4773 0.2432

m₂ = 0.4955 and V₂= Y₂/m₂ = [0.4908, - 1, 0.4908]^T

11 -4 1 0.4908 0.2472

k = 2 : Y₃ = - 4 16 -4 -1 = -0.4982

1 -4 11 0.4908 0.2472

After three iterations, we obtain the ratios as

Therefore,

Hence, the smallest eigen value in magnitude of A is 2.

(b) From the given matrix, we obtain

Define S₁ = and

This is the required tri-diagonal form. We obtain the sturm sequence as

Eigen values are the roots of f₃ = 0. Hence, the eigen values are

Therefore, the smallest eigen value in magnitude is .

7. (a) The maximum error in linear interpolation is given by where

We choose h such that . We get h < 0.00272

Hence, the largest step size that can be used is h 0.0027.

(b) Let the polynomial be

From f(0) = 1, we get = 1; f(1) = 5, we get a₀ + a₁ + a₂ + a₃ = 5

we get a₂ = 2;

Solving the above equations, we get a₀ = - 2, a₁ = 4, a₂ = 2, a₃ = 1

and the polynomial is

8. (a) We have

(b) We have and Ñ = 1 – E^-1. We get

L.H.S. = + Ñ = E – 1 + 1 – E^-1 = E – E^-1

R.H.S. = L.H.S.

(c) Since the points are equispaced with h = 0.1, we can use Newton difference interpolation. We first construct the forward difference table. We have

x f(x) f(x) ² f(x) ³ f(x)

0.1 0.93

0.2 0.92 - 0.01

0.3 0.97 0.05 0.06

0.4 1.08 0.11 0.06 0

0.5 1.25 0.17 0.06 0

0.6 1.48 0.23 0.06 0

using the Newton forward difference interpolation and the given data, we obtain

9. (a) We need an approximation of the form y + a + (b/x). We determine a and b such that

minimum. We obtain the normal equations

From the given data, we obtain

Hence, we have the normal equations

5 a + 2.2833 b = 16.7, 2.2833 a + 1.4636 b = 8.925

Solving these equations, we obtain a = 1.9305 and b = 3.0863

(b) Using the given formula and the given data, we get for x = 0.4 and

Using the Richardson extrapolation scheme, we obtain the improved value of

as . We get

10. (a) The method is exact for f(x) = 1 and f(x) = x. Making the method exact for f(x) = x², we get

Writing x₁ = x₀ + h, we obtain

, which gives p = 1/12.

We write the integral as

Replacing each integral on the right side by the given formula, we get

which is the required composite rule.

(b) Using we change the limits of integration from [2, 3] to [-1, 1]. Hence, we get

Using Gauss two-point formula

we get

Using Gauss three-point formula

we get

11. (a) Taylor series second order method is given by

We have and h = 0.2. We get

and

(b) We have x₀ = 1, y₀ = 2, h = 0.2 and f(x, y) = (y + 2x) / (y + 3x).

Using the given method, we get for

Subject NUMERICAL COMPUTING

Code C-09 / T-09 (December 2003)

1. (a) Absolute error =

Relative error = Answer: A

(b) The rate of convergence of Newton-Raphson method is 2. Hence

Answer: A

, Hence, Answer: D

(d) The maximum error in linear interpolation is

where

We choose such that

Hence, largest value of h is 0.00075 Answer: D

(e) Jacobian matrix =

At the point (1, 1), we get, Jacobian matrix = Answer: B

(f) Since f is a polynomial of degree k, all the divided differences of order k are equal and divided differences of order greater than k are zeros. Answer: C

(g) Trapezoidal rule is exact for polynomials of degree upto one. Answer: C

(h) Mid-point rule is given by :

For we get

We calculate from the exact solution

We obtain

Hence, from the given formula, we get for h = 0.2,

Answer: B

2 (a) Substituting we obtain the characteristic equation

The roots of the characteristic equation are -1.1 and 0.9

The general solution is written as

Using the given conditions, we obtain

Solving, we get

Since one root of the characteristic equation is greater than 1 in magnitude, computation will not be stable.

(b) We have , we find the f (x) < 0 for all x < 0. We obtain

f(0) = -2 < 0 and f(1) = 3 – cos1 - 1 = 1.46 > 0.

Therefore, the smallest root in magnitude lies in (0, 1).

Using the Newton-Raphson method, we obtain

and

3. (a) Without pivoting

(A b) = 1 1 1 1

1 1 2 0 1-1/ 2-1/

Using back substitution, we get

With pivoting

(A b) = 1 1 1 1 2 1 1 2

1 1 2 1 1 0 1- 1-2

Using back substitution, we get

Results in both cases are same, since we are using exact arithmetic.

(b) The iteration matrix in the Jacobi method is given by We obtain from the given matrix A,

The eigen values of are obtained from

For convergence of Jacobi method, we have

. Hence,

4. (a) We obtain from the augmented matrix

4 1 1 5

2 5 -2 9

R₂ – R₁/2

2 3 6 13 R₃ – R₁/2

4 1 1 5

0 9/2 -5/2 13/2

0 5/2 11/2 21/2 R₃ – 5R₂/9

4 1 1 5

0 9/2 -5/2 13/2

0 0 62/9 62/9

Using back substitution, we get

(b) The Gauss-seidel iteration method in matrix form is given by

From the given system of equations, we have

4 0 0 0 0 2

= 0 5 0 = 0 0 2

5 4 10 , 0 0 0

We obtain

Now eigen values of are

Since the method converges. The rate of convergence is given by

Q5. (a) We have

Using Newton’s method :

we obtain

(b) We write

We obtain

Comparing element by element, we obtain

first row: = 2

= -1

second row: which is not possible.

Hence, we cannot use the Choleski method.

Note: For the use of Choleski method, the given coefficient matrix must be positive definite. The given matrix is not positive definite matrix since first leading minor = 2 > 0 and second leading minor =

Q6. (a) The largest off-diagonal element in magnitude in is a₁₃ = 2. We obtain

tan 2

Now define

and

Now, largest off diagonal element in is a₁₂ =2. We obtain

tan 2

Now define

and

which is the diagonal matrix. The eigen values of are 5, 1, -1.

The eigen vectors are obtained from

Hence, eigen vectors are

6. (b) We obtain using Given’s method and the given matrix

Define

and

which is the required tridiagonal form

From ,

we obtain the Strums sequence

f₀ = 1

The eigen values of are -1, -1 and 5. The largest eigen values in magnitude of is 5.

7. (a) We are given that We obtain

x 0 0.5 1

f(x) -1 1/6 8/9

We now construct the Newton’s forward difference table

x f(x) f ²f

0 -1

0.5 1/6 7/6

1 8/9 13/18 -4/9

Using Newton’s forward difference interpolation

we obtain for h = 1/2

Setting p(x) = 0, we obtain the solutions x = 2.7098 and x = 0.4152

(b) Let p(x) =

This polynomial interpolates the first four points in the given table. We determine a so that this polynomial interpolates at the last point also. We get

p(3) = 2 – 4 + 12 – 48 + 24a = 10, or a = 2

Hence, the required polynomial is

p(x) =

8. (a) We want an approximation of the form where a and b are constants to be determined such that

minimum

We obtain the normal equation

From the given data, we obtain

Hence, we obtain the normal equations

5a + 2.2833b = 65

2.2833a + 1.4636b = 31.5333

Solving these equations, we get a = 10.9918 and b = 4.3972.

(b) We have

Setting the coefficients of y^(r), r = 0, 1, 2, 3, equal tozero, we obtain

1 – a – b = 0, s - b = 0

Solving these equations, we get

9. (a) Let be the quantity which is to be obtained and denote the approximate value of obtained by using the given method with step length h/2^r, r = 0, 1, 2, ………. Thus we have

Eliminating c₁ from the above equations, we get

Eliminating c₂from the above equations, we get

Thus successive higher order results can be obtained from the formula

Now we evaluate the given integral

Using Simpson’s rule, we get

Using Romberg integration, we obtain

9. (b) The method is exact for f (x) = 1 and x. Making the method exact for f (x) = x², we get

Since x₁ = x₀ + h, we get

Simplifying, we obtain

The error of integration is given by :Error =

where,

Therefore error is written as :Error =

where .

Hence, Error = .

We can now write

Replacing each integral by the above integration formula, we get

which is the required composite rule.

10. (a)

Expanding each term in Taylor series about x₀ and collecting terms of various order derivatives we get

We choose , , such that

Solving the above system of equations ,we get

Hence, we obtain the differentiation method

The error term is given by

(b) We write , where f (x) = x (1 – x²) sin x

Using Gauss-Chebyshev two point method

, we get

Using Gauss-Chebyshev three point formula

, we get

11. (a) Euler’s method is given by :

We obtain for h = 0.2

i = 0 : x₀ = 0, y₀ = 1,

i = 1 : x₁ = 0.2, y₁ = 1,

i = 2 : x₂ = 0.4, y₂ = 0.92,

i = 3 : x₃ = 0.6, y₃ = 0.784576,

i = 4 : x₄ = 0.8, y₄ = 0.636842,

(b) Expanding in Taylor series about the point we get

Substituting in the given method, we get

We also have,

Comparing the coefficients of h and h² in (1) and (2), we get,

Solving these equations, we get

and is arbitrary.

Hence, we obtain the method

The truncation error is given by

Hence, the method is of second order for all values of c₂.

Subject: Numerical Computing

Code: C-09/T-09 (June 2004)

1. (a) For one application of Simpson’s rule, we require three nodal points. Since we have 2n +1, (odd) nodal points, the number of sub-intervals n must be even. Answer: A

(b) We have Integrating, we get Using the given condition, we obtain c = 0. Hence, . Answer: C

(d) Hence roots are x = 1, 1 and x = These roots form a complex pair. Answer: C

(e) Using Gerschgorin theorem, we find that

Hence, spectral radius < 1. Answer: D

(f) An n-point Gauss-Legendre method is exact for polynomials of degree upto 2n – 1. Hence, for n = 4, the method will produce exact results for polynomials of degree upto 7. Answer: D

(g) The error term of the method is given by

Hence, order of the method is 2. Answer: A

(h) We have

Hence, = E – 1. The result = E + 1 is wrong. Answer: B

2. (a) We obtain from the augmented matrix

1 1 2 1

(A b) = 2 1 -3 0 R₂ – 2R₁

-3 -1 8 A R₃ + 3R₁

1 1 2 1

0 -1 -7 -2 R₃ + 2R₂

0 2 14 A + 3

1 1 2 1

0 -1 -7 -2

0 0 0 A-1

For consistency of the system A = 1. For other values of A, the system is inconsistent.

(b). We obtain from the augmented matrix

1 1/2 1/3 1

(A b) = 1/2 1/3 1/4 0 R₂ –R₁/2

1/3 1/4 1/5 0 R₃ - R₁/3

1 1/2 1/3 1

0 1/12 1/12 -1/2 R₃ - R₂

0 1/12 4/45 -1/3

1 1/2 1/3 1

0 1/12 1/12 -1/2

0 0 1/180 1/6

Using back substitution, we obtain x₃ = 30, x₂ = -36, x₁ = 9.

3. Gauss-Legendre two-point method is written as

where , , , are to be determined. Making the method exact for

=1, x, x² and x³, we get

=1 : or (1)

=x : or = 0 (2)

=x² : or =2/3 (3)

=x³ : or = 0 (4)

From (2) and (4) we obtain on eliminating , (

Since (system becomes inconsistent).

we get x₀ = -x₁. From (3) we obtain ()=2/3 or =1/3

We obtain

Hence, the method becomes

To evaluate the given integral using this method, we first change the limits of integration from [-2, 2] to (-1, 1). Using the substitution x =2t, we obtain

4. (a) We have

Since Using the method of false position, we get

First iteration:

Since we get

Second iteration:

Since we get

Third iteration:

After three iterations, we obtain the root as 1.9767.

(b) Using Lagrange interpolation and the given data, we obtain

= 0.8455 x³ – 1.0603 x² + 1.9331 x

We obtain f (1.5) .

5 (a) We have

Using the classical fourth order Runge-Kutta method, we get

Now, x₁ = 1.1, y₁ = 2.633474. We get

(b) We first write the given method in the form

Substituting and we get

since Cancelling we get

where C₂ =

Therefore, we get =

Hence,

Therefore, the method has linear rate of convergence.

6. (a) We have

From the trapezoidal rule, we get

h = 1/2 : x₀ = 0, x₁ = 1/2, f₀ = 1, f₁ = 1.042915 and

h = 1/4 : x₀ = 0, x₁ = 1/4, x₂ = 1/2, f₀ = 1, f₁ = 1.010493, f₂ = 1.042915 and

h = 1/8 : x₀ = 0, x₁ = 1/8, x₂ = 2/8, x₃ =3/8, x₄ = 1/2, f₀ = 1, f₁ = 1.002609,

f₂ = 1.010493, f₃ = 1.023828, f₄ = 1.042915 and

Using Romberg integration

we obtain the following Romberg table:

h 0(h²), m=0 0(h⁴), m=1 0(h⁶), m = 2

1/2 0.510729

1/4 0.507988 0.507074

1/8 0.507298 0.507068 0.507068

Hence,

(b) (i) =

(ii) . =

7. (a) If is an eigen value of a matrix A, then 1/ is an eigen value of A^-1. Thus the smallest eigen value in magnitude of A is the largest eigen value in magnitude of A^-1. Thus, we use the power method on A^-1 to obtain its largest eigen value in magnitude. Then = 1/ is the smallest eigen value in magnitude of A.

We take an arbitrary vector V₀ (non-zero) and generate

Y_k₊₁ = A^-1 V_k

V_k₊₁ = Y_k₊₁/ m_k_+1, (where m_k₊₁ is the largest element in magnitude in Y_k₊₁)

Then

Since V₀ = [0, 0, 0]^T is zero vector, we cannot use V₀ to obtain .

Hence, in this case solution cannot be obtained. However, if take any other vector V₀ say V₀ = [1, 1, 1]^T_,solution can be found. (The question in the present form is wrong).

8. Let A be a given real symmetric matrix. The eigen values of A are real. There exists a real orthogonal matrix S such that S^-1 A S is a diagonal matrix D. The elements on the diagonal of D are the eigen values of A. This diagonalization is done by applying a sequence of orthogonal transformations, S₁, S₂, ….., S_n, …….. as follows:

Among the off diagonal elements, let be the largest element in magnitude.

We define

1 … 0 0 ….. 0

S = cos -sin ith row

sin cos

0 ... 0 ….. 1

kth column

Thus S is an identity matrix in which the elements in positions (i, i) , (i, k) , (k, i) and (k, k) are written as cos, - sin, sin and cos respectively. It can be verified that S in an orthogonal matrix

We consider the 2x2 matrix

cos -sin

S₁ = sin cos

Now obtain the matrix (since A is symmetric, a_ik = a_ki)

A₁ = = cos sin a_ii a_ik cos -sin

-sin cos a_ik a_kk sin cos

where,

We choose such that the matrix A₁ becomes the diagonal matrix.

Setting =0, we get

where is called the angle of rotation. To obtain the smallest rotation, we take Now, we find the largest off-diagonal element in A₁ and the procedure is repeated. After r such rotations, we obtain

where, S = ……S_r.

As tends to a diagonal matrix D having eigen values on its diagonal.

The columns of S give the eigen vectors corresponding to the elements on the diagonal of D in that order.

In the given matrix, the largest off-diagonal element in magnitude is either a₁₂ or a₂₃. We take this element as a₂₃ (since a₂₂ = a₃₃ and exact arithmetic can be performed). From , we get Now define

1 0 0 1 0 0

S₁ = 0 cos -sin = 0 1/ -1/

0 sin cos 0 1/ 1/

1 0 0 2 1 0 1 0 0

A₁ = 0 1/ 1/ 1 4 1 0 1/ -1/

0 -1/ 1/ 0 1 4 0 1/ 1/

1 0 0 2 1/ -1/ 2 1/ -1/

= 0 1/ 1/ 1 5/ -3/ 1/ 5 0

0 -1/ 1/ 0 5/ 3/ -1/ 0 3

Now, the largest off-diagonal element in magnitude in A₁ is a₁₂ (or a₁₃). We find

We obtain sin = -0.2184, cos = 0.9758. Now, define

cos -sin 0 0.9758 0.2184 0

S₂ = sin cos 0 = - 0.2184 9578 0

0 0 1 0 0 1

A₂ =

0.9758 -0.2184 0 2 1/ -1/ 0.9758 0.2184 0

= 0.2184 0.9758 0 1/ 5 0 -0.2184 0.9758 0

0 0 1 -1/ 0 3 0 0 1

0.9758 -0.2184 0 1.7971 1.1268 -1/

= 0.2184 0.9758 0 -0.4020 5.0334 0

0 0 1 -0.6900 -0.1544 3

1.8414 0.0002 -0.6900

= 0.0002 5.1577 -0.1544

-0.6900 -0.1544 3

Since A₂ is not a diagonal matrix, we need more iterations. If we neglect the off-diagonal elements, then eigen values after two iterations are obtained as

9. (a) We need an approximation of the form y = a + bx + cx². We determine a, b, c such that

minimum

We get the normal equations as

Hence, we obtain

From the given data, we obtain

Substituting these values in the normal equations, we get

6a + 21b + 91c = 3060

21a + 91b + 441c = 6450

91a + 441b + 2275c = 17950

We write these equations as

a + 3.5b + 15.66667c = 510

a + 4.333333b + 21c = 307.142857

a + 4.846154b + 25c = 197.252747

Subtracting, we obtain

0.833333b + 5.833333c = -202.857143

0.512821b + 4c = -109.890110

Solving these equations, we obtain

b = -498.434243, c = 36.429357 and a = 1702.007924

(b) We have Differentiating, we get , . Taylor’s series method of order four is given by

We have h= 0.1. We obtain

=0 : x₀ = 0, y₀ = 0,

=1 : x₁ = 0.1, y₁ = 0.099333,

10. (a) Taking the limit as and noting that

, where is the exact root. We get

(i) = , (ii) =

Hence, both the methods determine , where a is a positive real constant.

(i) =

= =

We obtain, Error constant = (1)

Hence, the method has second order convergence.

(ii) =

Simplifying, we obtain,

Error constant = (2)

Hence, the method has second order convergence. Comparing (1) and (2), we find that error in the first method is about one third of that in the second method. If we multiply the fist method by 3 and add to the second method, we obtain the method

or (3)

The error of this method is given by

= 3 (error in first method) + (error in second method)

Hence, the new method (3) has third order convergence.

11. (a)

Expanding each term in Taylor series about and simplifying, we get

Therefore, .

Let be the round-off errors in evaluating respectively. We obtain

. If

then We choose h such that

(b) l₁₁ 0 0

From A = LL^T where L = l₂₁ l₂₂ 0 _,we obtain

l₃₁ l₃₂ l₃₃

1 2 1 l₁₁ 0 0 l₁₁ l₂₁ l₃₁

2 5 0 = l₂₁ l₂₂ 0 0 l₂₂ l₃₂

1 0 13 l₃₁ l₃₂ l₃₃ 0 0 l₃₃

l₁₁l₂₁ l₁₁l₃₁

= l₁₁l₂₁ l₂₁l₃₁ + l₂₂l₃₂

l₁₁l₃₁ l₃₁l₂₁+l₃₂l₂₂

Comparing element by element, we get

First row:

Second row:

Third row:

Hence, we obtain

1 0 0

L = 2 1 0

1 -2 2

We write the given system of equations A x = b as

L L ^T x = b, or L^T x = z and L z = b

1 0 0 z₁ 0

From L z = b, that is, 2 1 0 z₂ = -3

1 -2 2 z₃ 14

We obtain using forward substitution

z₁ = 0, z₂ = -3, z₃ = [ 14 - z₁ + 2 z₂]/2 = 2

1 2 1 x 0

From L^T x = z , that is, 0 1 -2 y = -3

0 0 2 z 2

We obtain using back substitution z = 1, y = -3 + 2z = -1, x = - 2y – z =1

Subject NUMERICAL COMPUTING

Code C-09 / T-09 (December 2004)

1. (a) We are given

We obtain

Using the secant method, we obtain

First iteration : ,

Second iteration : Answer: B

(b) The characteristic equation of the iteration matrix is

The roots are = 0, 0, 1/2. Spectral radius is 1/2. Answer: C

x f(x) First d.d Second d.d Third d.d

-3 7

-1 1 -3

0 1 0 1

1 3 2 1 0

2 7 4 1 0

Using Newton’s divided difference interpolation formula

, we get

Hence, f (-2) = 3 Answer: B

(d) We write the truncation error as

Expanding each term in Taylor series about x_k and simplifying, we obtain

Hence, p = 4. Answer: D

(e) Make the method exact for f(x) = 1, x and x². We get

Hence, we get Answer: D

(f) Write the integral as

Using the Gauss-Chebyshev two-point method

we get

Answer: A

(g) We need the approximation We determine a and b such that

minimum. We obtain the normal equations

or (1)

or (2)

Solving (1) and (2), we get Answer: A

(h) Euler’s method when applied to the given problem gives

We have h =0.1. We obtain

, Answer: C

2. (a) Let be the exact root. Since is a root of multiplicity 3, we have

Writing in the given method, we get

or,

where Using binomial expansion, we obtain

= Setting the coefficient of to zero, we get

The error becomes .

The method has second order rate of convergence and the error constant is 1/12.

(b) We have . We obtain

3. (a) We have and

Using Newton’s method we obtain

(b) The iteration matrix associated with the Gauss-Jacobi iteration method is given by

The eigen values of are obtained from

We obtain

The eigen values of are -3, 2.8318, 0.1682

The spectral radius is . Hence, the method diverges.

4. (a) Let

Comparing element by element, we get

third column: ,

second column:

first column:

Hence, and =

Now, We obtain

(b) From the augmented matrix, we have

1 1 -1 2

2 3 5 -3 R₁ R₃, (pivoting)

3 2 -3 6

2 3 5 -3 R₂ – 2R₁/3

1 1 -1 2 R₃ – R₁/3

3 2 -3 6

0 5/3 7 -7

0 1/3 0 0 R₃ – R₂/5

3 2 -3 6

0 5/3 7 -7

0 0 -7/5 7/5

Using back substitution, we get

5. (a) The largest off-diagonal element in magnitude in

From

Define and

Now the largest off-diagonal element in magnitude of

From

Define and

Hence, the eigen values of are , and -3.

(b) We have

Starting with

;

After three iterations, we obtain the ratios

We take 2.4 (we need more iterations for more accurate results.)

Hence, the largest eigen value in magnitude of

The eigen value nearest to 3 of the matrix is

Since satisfies the equation more accurately, the nearest eigen value to 3 is 2.5833.

6. (a) We obtain from the given matrix

Therefore

Define and

= =

which is the required tri-diagonal form. Using Sturms sequence, we obtain

The characteristic equation of the given matrix is =

(b) From the given matrix, we write

4 1 1 1 0 0

1 4 -2 0 1 0 R₂ – R₁/4

3 2 -4 0 0 1 R₃ – 3R₁/4

4 1 1 0 0 0

0 15/4 -9/4 -1/4 1 0 R₁ – 4R₂/15

0 5/4 -19/4 -3/4 0 1 R₃ – R₂/3

4 0 8/5 16/15 -4/15 0

0 15/4 -9/4 -1/4 1 0 R₁ + 2R₃/5

0 0 -4 -2/3 -1/3 1 R₂ – 9R₃/16

4 0 0 4/5 -2/5 2/5

0 15/4 0 1/8 19/16 -9/16 R₁/4, 4R₂/15,

0 0 -4 -2/3 -1/3 1 -R₃/4

Hence,

7. (a) We need to determine a and b such that

We obtain the normal equations

or (1)

or (2)

Solving (1) and (2), we get

(b) Newton’s backward difference interpolation is given by

Substituting

We obtain

Now dx/ds = h and for

(1)

We now construct the backward difference table from the given data. We get for h = 1

x f(x)

1 1

2 3 2

3 7 4 2

4 13 6 2 0

5 21 8 2 0

Substituting in (1) for x_n= 5, we obtain

8. (a) Using Lagrange interpolation formula and the given data, we get

(b) we have

We shall now show by induction that

The result is true for n = 1. Assume that the result is true for n = k, that is

. Then for n = k + 1, we have

Hence, the result is true for any k.

9. (a) We can write

Hence, we can write the error term as

, where c_i_’s are independent of h.

Let denote the approximate value of obtained by using the given method with step length , r =0, 1, ………….

Thus we can write

Eliminating c₁ from the above equations, we obtain

Eliminating c₂ from the above equations, we get

Thus the successive higher order results can be obtained from the formula

Using the given formula and the given data, we obtain

We obtain the following Richardson’s table

h O(h) O(h²) O(h³)

4 31

2 13 -5

1 7 1 3

Hence, the best value of is 3.

(b). Truncation error of the given method is given by

Expanding each term in Taylor series about x_o and simplifying, we get

. Hence

If are round off errors in evaluating respectively,

then we get

Let . Then

We choose h such that

Differentiating with respect to h and equating it to zero, we get

10. (a) Make the method exact for We get

From the above equations, we obtain

= 2 , (,

Solving these equations, we get

It can be verified that the method produces exact results for

The error term is given by Error = where

Hence, Error =

(b). Using the Trapezoidal rule, we get

I =

Using Romberg integration

we obtain the following Romberg table

h o(h²) o(h⁴) o(h⁶)

1 0.666667

½ 0.619048 0.603175

¼ 0.608108 0.604461 0.604547

The improved value of I is I = 0.604547

11. (a) We have

Third order Taylor series method is given by

We have h = 0.2, x₀ =1, y₀ =1. We obtain

Now

(b). We have

Using the classical fourth order Runge-Kutta method, we get

Now, x₁ = 1.1, y₁ = 2.229705. we get