{"id":1327,"date":"2018-11-27T10:16:49","date_gmt":"2018-11-27T10:16:49","guid":{"rendered":"http:\/\/msp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=1327"},"modified":"2019-04-30T12:14:33","modified_gmt":"2019-04-30T12:14:33","slug":"indirect-methods-for-linear-equations","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/msp01\/chapter\/indirect-methods-for-linear-equations\/","title":{"rendered":"Indirect methods for linear equations"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\nTABLE OF CONTENTS<\/strong>\r\n

1. Introduction<\/p>\r\n

2. Vector Norms<\/p>\r\n

2.1 Distance between vectors in \u211dn<\/em><\/sup><\/p>\r\n

2.2 Convergent sequences<\/p>\r\n

3. Matrix norms and distances<\/p>\r\n

4. The Jacobi iterative method<\/p>\r\n

4.1 The matrix form<\/p>\r\n

5. The Gauss-Seidel method<\/p>\r\n

5.1 The matrix form<\/p>\r\n

6. Convergence of iterative techniques<\/p>\r\n

6.1 Criterion for convergence<\/p>\r\n\r\n<\/div>\r\n \r\n

\r\n\r\nLEARNING OBJECTIVES<\/strong>\r\n

1. Various vector norms are introduced. The associated notion of vector distance is also introduced.<\/p>\r\n

2. Idea of convergence is defined and limit of a sequence of vectors introduced.<\/p>\r\n

3. Next, matrix norms and distances.<\/p>\r\n

4. The Jacobi iterative method is described and also put in the matrix form.<\/p>\r\n

5. Next the Gauss-Seidel method is described. This is also put in the matrix form as well.<\/p>\r\n

6. Convergence of iterative techniques is discussed and simple criterion for convergence described.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n<\/div>\r\n
\r\n

Indirect methods for solution of linear Equations<\/strong><\/p>\r\n \r\n\r\n1. Introduction<\/strong><\/span>\r\n

In this unit we describe iterative techniques for solving linear systems. Jacobi and the Gauss-Seidel iterative methods are the two classic iterative methods in this class. Iterative techniques are seldom used for solving linear systems of small dimension since the time required for sufficient accuracy exceeds that required for direct techniques such as Gauss elimination. For large systems with a high percentage of 0 entries, however, these techniques are often much more efficient. Systems of this type arise frequently in circuit analysis and in the numerical solution of boundary-value problems and partial-differential equations.<\/p>\r\n \r\n\r\n2. Vector norms<\/strong><\/span>\r\n\r\n\"\"\r\n\r\nThe l<\/em>2<\/sub> norm is what we called the Euclidean norm<\/em> of the vector x<\/strong>. It is not difficult to show that the norms defined above do satisfy the properties required of a norm that we described in the unit on matrices.\r\n\r\n \r\n\r\nExample<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\n2.1 Distance between vectors in \u211dn<\/em><\/sup><\/span>\r\n

The distance between two vectors<\/em> is defined as the norm of the difference of the vectors. Thus<\/p>\r\n\"\"\r\n\r\n \r\n\r\nExample<\/span>\r\n\r\n\"\"\r\n\r\n2.2 Convergent sequence<\/span>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nTheorem-1<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\nProof<\/span>\r\n\r\n\"\"\r\n\r\nThe converse can be proved in a similar manner.\r\n\r\n \r\n\r\nExample<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\nTheorem-2<\/span>\r\n\r\nFor each\r\n\r\n\"\"\r\n\r\n \r\n\r\nProof<\/span>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n\"\"\r\n
\r\n\r\n \r\n\r\n3. Matrix norms and distances<\/strong><\/span>\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\nTheorem-3<\/span>\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\nTheorem-4<\/span><\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\nProof<\/span>\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\nExample<\/span>\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\nTheorem-5<\/span><\/span>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nProof of (ii)<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\nExample-1<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\nExample-<\/span>2<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\n4. The Jacobi iterative method<\/span><\/strong><\/span>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n\"\"\r\n\r\n \r\n\r\nExample<\/span>\r\n\r\nConsider the system of three equations\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\n4.1 The matrix form<\/span><\/span>\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nExample<\/span>\r\n\r\nThe system of equations\r\n\r\n\"\"\r\n\r\n \r\n\r\n5. The Gauss-Seidel Method<\/span><\/strong><\/span>\r\n\r\n\"\"\r\n\r\nThis modification is called the <\/span>Gauss-Seidel<\/em> iterative method.<\/span>\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\nExample<\/span>\r\n\r\nLet us look at the earlier example once again:\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\nFor more accuracy than this, we need to calculate <\/span>x<\/strong>(4)<\/sup>, <\/span>x<\/strong>(5)<\/sup>, \u2026 as well.<\/span>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n
\r\n\r\n \r\n\r\n5.1 The matrix form<\/span>\r\n

Let us now put the Gauss-Sidel method also in the matrix form. For this purpose we multiply equation (20) by a<\/em>ii<\/em><\/sub> and take all the (k<\/em> + 1)th iterate terms on the left hand side:<\/p>\r\n\"\"\r\n

Define the matrices D, L<\/strong> and U<\/strong> as we did for the Jacobi case. Then the matrix form of the Gauss-Sidel method is<\/p>\r\n\"\"\r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n6.\u00a0 Convergence of iterative techniques<\/strong><\/span>\r\n

We will now study certain general properties of the iterative techniques for the solution of linear systems, in particular the question of convergence of the iterative series. The question of convergence is crucial for all problems where iterative techniques are employed. There is always a possibility that a series of iterates diverges or converges so slowly that it is of no practical use.<\/p>\r\nFirst of all we define a convergent matrix<\/em>. An n<\/em> x n<\/em> matrix A<\/strong> is said to be convergent if\r\n\r\n\"\"\r\n\r\n \r\n\r\nTheorem-6<\/span>\r\n

For a convergent matrix the following statements are equivalent; that is each follows from the others:<\/p>\r\n\"\"\r\n\r\nNow we come to the general iteration method, equation (21).\r\n\r\n \r\n\r\nTheorem-7<\/span>\r\n

First of all we have the following result: If the spectral radius of T<\/strong> satisfies \u03c1<\/em>(T<\/strong>) < 1, then (I<\/strong> \u2013<\/strong> T<\/strong>)-1<\/sup> exists and satisfies the relation<\/p>\r\n\"\"\r\n\r\n \r\n\r\nProof<\/span>\r\n

If Tx<\/strong> = \u03bb<\/em>x<\/strong> then (I<\/em><\/strong> \u2013<\/strong> T<\/em><\/strong>)x<\/strong> = (1 \u2013 \u03bb)x<\/strong>. Thus if \u03bb<\/em> is an eigenvalue of T<\/strong>, then 1 \u2212 \u03bb<\/em> is an eigenvalue of\u00a0\u00a0\u00a0 I \u2212 T<\/strong>. But<\/p>\r\n

|\u03bb<\/em>| \u2264 \u03c1(T) <<\/em> 1,<\/p>\r\n

which implies that \u03bb<\/em> = 1 is not an eigenvalue of T<\/strong>, and 0 cannot be an eigenvalue of I<\/strong> \u2212<\/strong> T<\/strong>. Hence, (I<\/em><\/strong> \u2013<\/strong> T<\/em><\/strong>)-1<\/sup> exists.\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0QED<\/p>\r\n \r\n\r\nTheorem-8<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\nProof<\/span><\/span>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\nWe omit the proof of the converse of the theorem.\r\n\r\n \r\n\r\nTheorem-9<\/span>\r\n\r\n\"\"\r\n\r\n \r\n\r\nJacobi and Gauss-Seidel techniques<\/span>\r\n

Both Jacobi and Gauss-Seidel techniques can be written in the form [See equations (16),19, 21 and (22)]<\/p>\r\n\"\"\r\n\r\n\"\"\r\n\r\nOr\r\n

Ax = b<\/strong><\/p>\r\n

We can demonstrate the result for Gauss-Seidel also in the same fashion.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n6.1 Criterion for convergence<\/span>\r\n

What we need is an executable criterion for the convergence and the rapidity of convergence of the two techniques.<\/p>\r\n

To provide such a criterion, we first introduce a strictly diagonally dominant matrix<\/em>. An n<\/em> x n<\/em> matrix A<\/strong> is said to be strictly diagonally dominant if<\/p>\r\n\"\"\r\n

If the equality is also allowed in the above equation, then the matrix is said to be diagonally dominant<\/em>. Strict diagonal dominance implies that each diagonal element is so large that its magnitude is greater than the sum of magnitudes of all other elements in that row<\/em>.<\/p>\r\n\"\"\r\n\r\n \r\n\r\nTheorem-10<\/span>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n

<\/div>\r\n \r\n\r\nSUMMARY<\/strong>\r\n