Realizing an LU decomposition

For an LU decomposition of a given n x n matrix A, we seek a lower triangular matrix L and an upper triangular matrix U (both of order n x n) such that A = LU. The matrix U may be taken to be the upper triangular matrix resulting from Gauss elimination without partial pivoting, and the matrix L may be taken to be the lower triangular matrix which has diagonal elements 1 and which, for k <>, has as the (i, k) element the multiplier m_ik. This multiplier is calculated at the k-th stage of Gauss elimination and is required to transform the current value of a_ik to 0. In the notation of Step 11, these multipliers were given by m_ik = a_ik/a_kk, I = k+l, k+2,.. ,n.

An example will help clarify this. From Step 11, we recall that Gauss elimination, applied to the system

yielded the upper triangular matrix:

Also, we saw that in the first stage we calculated the multipliers rn₂₁ = a_2l/a₁₁ = 1 / 1= 1 and m_3l = a_3l/a₁₁ = 2/ 1 = 2, while in the second stage we calculated the multiplier m₃₂ = a₃₂/a₂₂ = -3/1 = -3. Thus

It is readily verified that LUequals the coefficient matrix of the original system:

. Another technique that may be used to find an LU decomposition of an n x n matrix is by direct decomposition. In order to illustrate this process, let it be rquired to find an LU decomposition for the 3 x 3 coefficient matrix of the system above. Then the required L and U are of the form

Note that the total number of unknowns in L and U is 12, whereas there are only 9 elements in the 3 x 3 coefficient matrix A. To ensure that L and U are unique, we need to impose 12 - 9 = 3 extra conditions on the elements of these two triangular matrices. (In the general n x n case, n extra conditions are required.) One common choice is to require all the diagonal elements of L to have the value 1; the resulting method is known as Doolittle's method. Another choice is to require all the diagonal elements of U to be 1; this is Crout's method. Since Doolittle's method will result in the same LU decomposition for A, given above, we shall use Crout's method to illustrate this direct decomposition procedure.

We then require that

Multiplication of L and U yields:

It is clear that this construction by Crout's method yields triangular matrices L and U for which A = LU.

Checkpoint

1. What constitutes an LU decomposition of a matrix A?
   
2. How is a decomposition A = LU used to solve a linear system Ax = b?
   
3. How may an LU decomposition be obtained by Gauss elimination?

Procedure

Suppose we have to solve a linear system Ax = b, and that we can express the coefficient matrix A in the form of the socalled LU decomposition A = LU.

Then we may solve the linear system by the following procedure:

Stage l: Write Ax = LUx = b.

Stage 2: Set y = Ux, so that Ax = Ly = b. Use forward substitution on Ly = b to find y₁, y₂, . . , y_n in that order, i.e., suppose the augmented matrix for the system Ly = b is:

Then forward substitution yields y₁ = b₁/l₁₁, and, subsequently,

Note that the value of y_i depends on the values y₁, y₂, . . , y_i-1, which have already been calculated.

Stage 3: Finally, use back-substitution on Ux = y to find x_n, . . . , x₁x in that order.

Later on we shall outline a general method for finding LU decompositions of square matrices. The following example shows this method in action, involving the matrix A = L₁U₁ above. If we wish to solve Ax = b for a number of different bs, then this method is more efficient than Gauss elimination. Once we have found an LU decomposition of A, we need only do forward and backward substitutions to solve the system for any b.

Example

We shall solve the system

Stage l: An LU decomposition of the system is

Stage 2: Set y = U₁x and then solve the system L₁y = b, i.e.,

Using forward substitution, we obtain:

Stage 3: Solve

Back-substitution now yields:

Thus the solution of Ax = b is:

which may be checked, using the original equations. We turn now to the problem of finding an LU decomposition of a given square matrix A.

We have shown in STEP 11 how to solve a linear system Ax = b by Gauss elimination, applied to the augmented matrix . In the preceding Step, we have extended the elimination process to calculate the inverse A^<-1 of the coefficient matrix A, assuming it exists.

Another general approach to solving Ax = b is known as the method of LU decomposition, which provides new insights into matrix algebra and has many theoretical and practical uses. Efficient computer algorithms for handling practical problems can be developed from it.

The symbols L and U denote lower triangular matrix and upper triangular matrices, respectively. Examples of lower triangular matrices are

Note that in such a matrix all elements above the leading diagonal are zero. Examples of upper triangular matrices are:

where now all elements below the leading diagonal are zero. The product of L₁ and U₁ is

Question 5.

As we have seen, chips carry away the majority of the heat generated during machining. If chips did not have this capacity, what suggestions would you make in order to be able to carry out machining process without excessive heat. Explain?

Solutions:

When the chips are formed they have long grain structures, traverse to the direction of cutting. However, as the chip rubs the surface of the workpiece, the grain structure on the lower surface bends to form a "long tail" due to secondary deformation and the heat build up. This lower surface then recrystallizes due to the grain structure and intense heat. This recrystallized area is highly undesirable since it is more difficult to have smaller, broken chips.

We can improve the chip breaking by

• increasing the brittleness of the chip material by the low temperature application of the cryogenic coolant;
• reducing the secondary deformation that occurs at the bottom surface of the chip which rubs on the tool face;
• reducing the long tail in the grain structure of the chips, which is a major cause of the difficulty in breaking ductile chips;
• avoiding the welding or recrystallizing of the bottom layer of the chip (to avoid the strong bonding of chip structure which adds to the difficulty in chip breaking) by the coldness and reduction of the secondary deformation;
• bending and curling the chip for breaking by the use of both a mechanical chip breaker and the pressure from the cryogenic fluid

Explanation:

The build-up edge formation is automatically prevented by injecting the super cold cryogenic fluid to the cutting tip area. This reduces the adhesion of the chip material to the tool tip which lowers the temperature in the cutting zone and prevents the welding phenomenon. Also, this invention can clean and remove the possible build-up edge with the cryogenic jet. Because the build-up edge is the main cause of poor surface quality, the method of the present invention also indirectly improves the finish of the machined surface. Therefore, it is an object of the present invention to provide a cutting tool which injects liquid nitrogen or other liquified gas as close as possible to the highest heat affected area of the cutting tool, not the workpiece, through a nozzle, between the chip and the tool face. This provides a fluid cushion which reduces the friction of the chip rubbing on the tool face, and reduces the cutting force involved, as well as the abrasive wear.

Question 4. Why does the temperature in cutting depends on the cutting speed, feed and depth of cut? Explain in term of the relevant process variable.

Temperature in cutting refers to the temperature at the tool/chip interface. It consists of the temperature rise in the body of the chip due to shear at the interfaces as the hot chip rubs on the tool faces, and the workpiece temperature. Those rises varies with cutting speed, in general, decreasing with an increasing in cutting speed.

Most of the mechanical energy expanded in metalcutting is transformed into heat. About 75%-80% of this heat is carried away by the chip; the remainder is divided between the workpiece and the tool.

An increase in speed or feed decreases the proportion of the heat transferred to the tool and workpiece. The relationship of cutting temperature to cutting speed is shown below:

where,
θf = tool/chip interface temperature
V = cutting speed
C = constant (dependent on tool/workpiece combination and cutting variables other than cutting speed)
n = exponent

An empirical equation of similar from relates cutting temperature to feed. It is seen that the increase in feed is less hazardous as far as temperature is concerned than a corresponding increase in speed. The depth-of-cut influences the cutting temperature in a limited manner.

If the depth-of-cut is more than twice the nose radius, a further increase in depth will have little effect on the cutting temperature. Basically, a depth of cut of 10 times of the feed rate creates a little temperature effect.