Linear System 47
The Gauss-seidel method is given by
1
x1 n 1
7 x2n
2
n 1 1 n 1 n
x2 1 x1 x3
2
1
x3n 1
1 x2n 1
2
0 0 0
Given, X x1 , x2 , x30 0, 0, 0
1 1 0 1
x1 7 x2 7 0 3.5
2 2
1 1
x21 1 x11 x30 1 3.5 0 2.25
2 2
1 1 1 1
x3 1 x2 1 2.25 1.625
2 2
Hence option (b) is correct.
25. Consider the system of equations [D.U. 2017]
1 a x1 b1
a 1 x2 b2
where ‘a’ is a real constant. Then Gauss-seidal method for the solution of the above system converges for
(a) all values of a (b) a 1 (c) a 1 (d) a 2
Soln. Consider the system AX = B. We know that the gauss seidal method converges for AX = B if the matrix A is
diagonally dominated.
i.e. aii aij for each i
i j
we have 1> |a|
Hence option (b) is correct.
26. The total number of arithmetic operations required to find the solution of a system of n linear equation in n
unknowns by Gauss elimination method is [D.U. 2018]
2 3 1 2 5 1
(a) n n n (b) n3 n
3 2 6 6
2 3 3 2 7 1 3 1 2 5
(c) n n n (d) n n n
3 2 6 3 2 6
Soln. Article - Counting operation in Gaussian elimination.
Consider a system of n linear equation in n unknowns and the corresponding n × n coefficient matrix
a11 a12 .....a1n
a21 a22 ......a2 n
A
| | |
an1 an 2 ......ann
The n × 1, solution matrix X = [ x1 , x2 ......xn]T, and the n × 1 constant matrix B = [b1, b2 .....bn]T.
Numerical Analysis 48
consider AX = B
Then After Gaussian elimination, the system convert as
UX = G
u11 u12 .....u1n
u22 ......u 2 n
u
Where | is the coefficient matrix of the equivalent system,
.................unn
g1
g2
and g | be the n × 1 equivalent constant matrix.
gn
The following table states the operation count from going from A to U at each step as
Therefore
2 n n 1 2n 1
Total number of Addition/Subtraction n 1
6
2 n n 1 2n 1 n n 1 n n2 1
Total number of Multiplication/Divisions n 1 n 1
6 2 3
Now we count the Number of Addition/Subtraction and the Number of Multiplication/divisions in going from
b g , we have
n n 1
Total Number of Addition/Subtraction n 1
2
n n 1
Total Number of Multiplication/divisions n 1
2
Lastly, we count the Number of Addition/Subtraction and Multiplications/divisions for finding the solution
from the back substitution method, as
n n 1
Total Number of addition/subtraction n 1
2
n n 1
Total Number of Multiplication/division n
2
Therefore, the total number of operations to obtain the solution of a system of n linear equations in n variables
using Gaussian - elimination method is
n n 1 2n 1 n n 1 n n 1 n n 1 2n 5
Total Number of additions/subtraction
6 2 2 6
Total number of multiplication /divisions to obtain solution is
Linear System 49
n n2 1 n n 1 n n 1 n n2 3n 1
3 2 2 3
Therefore total number of Arithmetic operations are
n n 1 2n 5 n n2 3n 1
6 3
4n3 9n2 7n 2 3 3 2 7
n n n
6 3 2 6
2 3 3 2 7
Total number of operation are n n n
3 2 6
Hence option (c) is correct
1 4 3 11 0 0 1 u12 u13
27. If 2 7 9 21 22 0 0 1 u23 , then the value of a is [GATE-2008]
5 8 a 31 32 53 0 0 1
(a) –2 (b) –1 (c) 1 (d) 2
1 4 3 11 0 0 1 u12 u13 11 11 12u u
11 13
Soln. 2 7 9 21 22 0 0 1 u23 21 11 12 u 22 21u13 22 u 23
5 8 a 31 32 53 0 0 1 31 31u12 32 u
31 13 u
32 23 53
Comparing both sides, we have
11 1, 21 2, 31 5, u
11 12 4 implies u12 4
u
11 13 3 implies u13 3, u
21 12 22 7 implies 8 22 7 i.e. 22 1
21 13u 22 23u 9 implies 6 u23 9 i.e. u23 3
31 12u 32 8 implies 20 32 8 i.e. 32 12
Now, 31u13 32 u23 53 a implies 15 36 53 a i.e. a 2
Option (a) is correct
Numerical Analysis 50
4
Interpolation by Polynomials
Suppose that a function f x is not defined explicitely, but its value at some finite number of points
xi , i 1, 2,...., n is given. The interest is to find the value of f at some point x lying between x j and xk , for
some j, k = 1, 2,....,n. This can be obtained by first approximating f by a known function and then finding the
value of this approximate function at the point x. Such a process is called the interpolation.
Lagrange Interpolation:
The basic interpolation problem can be posed in one of two ways:
I. Given a set of nodes xi / i 0,1,....n and corresponding date values yi / i 0,1,....n . Find the polynomial
pn x of degree less than or equal to n, such that pn xi yi , i 0,1,...n
II. Given a set of nodes xi / i 0,1,...., n and a continuous function f x . Find the polynomial pn x of
degree less than or equal to n, such that pn xi f xi , i 0,1,....n
Note that in the first problem we are trying to fit a polynomial to the data, and in the second case, we are trying
to approximate a given function with the interpolating polynomial. Note that the first problem can be viewed as
a particular case of the second.
Theorem (Lagrange Interpolation Formula)
Let x0 , x1 ,....xn I a , b be n +1 distinct nodes and let f x be a continuous real- valued function defined
on I. Then, there exists a unique polynomial pn of degree n (called Lagrange Formula for interploting Polyno-
mial), given by
n n
x xi
pn x f xk lk x where lk x , k 0,..., n
k 0 i 0,i k xk xi
such that pn xi f xi , i 0,1,...., n
The function lk x is called the Lagrange Multiplier..
Newton Interpolation and Divided Differences
We have seen that in the Lagrange formula of interpolating polynomial for a function,if we decide toadd a point
to the set of nodes to increase the accuracy, we have to completely recompute all of the li x functions. In
other words, we cannot express Pn 1 in terms of pn, using Lagrange formula. An alternate form of the polynomail,
known as the Newton form, avoids this problem, and allows us to easily write Pn 1 in terms of Pn.
The idea behind the Newton formula of the interploting polynomial is to write Pn x in the form (called New-
ton form)
