AERO20542代做、代写Python/Java编程

日期：2024-03-06 09:33

MECH20042/AERO20542 Numerical Methods and Computing

Laboratory exercise 1: Direct methods for the solution of

tridiagonal systems of linear equations

Solution of systems of linear equations is one of the most frequently encountered problems in

numerical modelling and simulation. Efficient numerical methods, both in terms of the execution time

and memory storage are essential to complete this task. Sparse systems of linear equations arise in

many applications, such as finite element or finite volume solution of differential equations. Sparse

linear systems have coefficient matrices that are sparse, i.e., a large proportion of the elements are

equal to zero. Banded matrices are a special class of sparse matrices in which the non-zero coefficients

are concentrated about the main diagonal.

Storing sparse matrices in computer memory as two-dimensional arrays is inefficient, as many zero

elements are kept needlessly in computer memory. Banded matrices can be stored by their diagonals,

where each diagonal is stored as a one-dimensional array (a vector). With this setup a tridiagonal

matrix 𝑇 of size 𝑛 × 𝑛

can be stored using three vectors as follows:

𝐴 = [𝑎11 𝑎22 ⋯ 𝑎𝑛𝑛]

𝑇 ∈ 𝑅

𝑛

,

𝐵 = [𝑎21 𝑎32 ⋯ 𝑎𝑛,𝑛−1]

𝑇 ∈ 𝑅

𝑛−1

,

𝐶 = [𝑎12 𝑎23 ⋯ 𝑎𝑛−1,𝑛]

𝑇 ∈ 𝑅

𝑛−1

.

The Gaussian elimination technique applied to a tridiagonal system 𝑇𝒙 = 𝒇 is particularly simple,

because only the non-zero elements in the sub-diagonal held in vector 𝐵 need to be eliminated. This

algorithm, known as the Thomas algorithm, proceeds as follows:

FORWARD ELIMINATION BACKSUBSTITUTION

𝑎𝑖𝑖 = 𝑎𝑖𝑖 −

𝑎𝑖,𝑖−1

𝑎𝑖−1,𝑖−1

𝑎𝑖−1,𝑖 𝑥𝑛 =

𝑓𝑛

𝑎𝑛𝑛

𝑓𝑖 = 𝑓𝑖 −

𝑎𝑖,𝑖−1

𝑎𝑖−1,𝑖−1

𝑓𝑖−1 𝑥𝑖 =

1

𝑎𝑖𝑖

(𝑓𝑖 − 𝑎𝑖,𝑖+1 𝑥𝑖+1)

𝑖 = 2, … , 𝑛 𝑖 = 𝑛 − 1, … ,1

TASK 1. Calculate the number of arithmetic operations that are required to solve a tridiagonal system

𝑇𝒙 = 𝒇 of size 𝑛 using the Thomas algorithm. Based on this result, determine the asymptotic

complexity of the Thomas algorithm, and compare it to the asymptotic complexity of the standard

Gaussian elimination.

TASK 2. Rewrite the Thomas algorithm in terms of the arrays 𝐴,𝐵, and 𝐶 introduced to store the matrix

𝑇 efficiently.

TASK 3. Implement the Thomas algorithm from TASK 2 as a Python function. The input parameters to

the function should be the coefficient matrix 𝑇 (stored as three arrays 𝐴,𝐵, and 𝐶) and the right-hand

side vector 𝒇. The output should be the solution vector 𝒙. The coefficient matrix and the right-hand

side should be defined in the main script and passed to the function that solves the system.

TASK 4. Test your code by solving the linear system of size 𝑛 = 10 with the values 𝐴 = 2, and 𝐵 = 𝐶 =

−1. Set the right-hand side to 𝒇 = 𝟏. To verify the correctness of your code, compare the solution

vector obtained from the Thomas algorithm to that obtained by applying the direct solver

numpy.linalg.solve(). For the latter, the coefficient matrix should be assembled.

TASK 5. Solve five linear systems 𝑇𝒙 = 𝒇 with 𝐴 = 2, 𝐵 = 𝐶 = −1 and 𝒇 = 𝟏 varying the problem size

𝑛 between 106

and 108

. Record the execution times in seconds for each case. To accomplish this task,

explore the Python function timer() from the package timeit (refer to the code for matrix

multiplication covered in lectures). Plot a graph where the obtained execution times are represented

as the function of the problem size 𝑛. What are your conclusions about the cost of the Thomas

algorithm?