这个作业是解决矩阵、泊松方程等相关问题的统计代写
CS 475/675 Spring 2020: Assignment 1
1.(10分)面向列的向后求解。考虑求解系统Ux = b,其中U是上三角形。解决该问题的一种方法是以下过程。首先,解析xn。
然后可以将其从等式1到n-1中删除,我们可以继续进行简化右侧已更新的系统。接下来我们计算xn−1并删除它是从等式1到n-2,等等。例如,如果将此方法应用于
8 7 3
0 4 2
0 0 6
x12倍3倍=51个12
(1)我们首先计算x3 = 2,然后求解简化的2×2系统:
</ s> </ s> </ s>8 70 4 x12倍
</ s> </ s> </ s>=</ s> </ s> </ s>5
1个</ s> </ s> </ s>− 2</ s> </ s> </ s>32</ s> </ s> </ s>(2)
对于矩阵U为n×n上位的一般情况,推导一种有效的算法三角矩阵(不一定是单位对角线)。用伪代码展示您的算法。算法的输入应为矩阵U和右侧b,并且输出应为解x。您的算法复杂度是多少?展示你的作品特别是所有O(np),p∈Z.
2.(10个标记)考虑一个具有上限和下限带宽等于q的n×n矩阵A。
假设您获得了由A的LU分解组成的L和U矩阵,即A = LU。推导一个有效的算法(即向前和向后求解)来求解Ax = b。
为您的算法提供精确的伪代码。您的算法的复杂度是多少n和q的项?领先订单项的系数是多少(假设q 1)?
3.(10分)假设给定一个n×n对称正定矩阵A及其胆固醇系数G,使得GGT =A。描述如何有效解决以下问题问题。 (请注意,您无需计算A或任何其他值的显式逆假设c和b是给您的已知向量。
(a)计算α= cT A−1b。
(b)求解矩阵方程Bx = b,其中B = A + A〜。矩阵A〜满足条件它的所有列都是零向量,除了第k列,其中A〜i,k = i,1≤i≤n。 (提示:考虑谢尔曼·莫里森公式。)1个
4.(5个标记)泊松方程的一些有限差分近似值∆φ = f生成一个包含当前点及其周围8个立即数的9点模具邻居。这产生了一组一般形式的线性方程:
θTi-1,j-1 +γTi,j-1 + µTi + 1,j-1 +ρTi-1,j +ηTi,j +δTi+ 1,j +νTi-1,j + 1 +αTi,j + 1 +βTi+1,j + 1 = fi,j对于i = 1,2,… m,j = 1,2,… m。设A为线性系统的矩阵。假设自然未知数的按行排序,绘制A的图片。描述A的稀疏结构并指出哪些系数(希腊字母)出现在哪些非零条目中。
5.(10分)考虑一个对称矩阵,其图形由下式给出:
一个乙CdFHJķ
图1:矩阵图
执行Cuthill-McKee(从节点A开始),反向执行Cuthill-McKee和最低程度在此矩阵上重新排序。对于最小度排序,请显示每个阶段的图形消除。应通过按字母顺序更早地选择节点来断开关系原始标签(如图1所示)。在每种情况下,请使用新标签。
6.(40个标记)在建模(稳态)热流中,温度T = T(x,y)满足泊松方程-∂2T∂x2-∂2T∂y2= f(x,y)
其中f(x,y)代表热源函数。
我们在m个活动网格的二维网格上的离散位置处近似T(x,y)每个维度中的点。令(i,j)网格点具有位置(xi,yj)其中xi = ih,yi = jh,h = 1 /(m +1)是网格间距,并且i,j∈[0,m +1]。如果让Ti,j≈T(xi,yj),然后
一组线性方程组的有限差分近似结果 1个H2
(4Ti,j-Ti-1,j-Ti + 1,j-Ti,j-1-Ti,j + 1)= fi,j。 (3)
我们将假设网格两侧的所有边界温度均为零:
T0,j = Ti,0 = Tm + 1,j = Ti,m + 1 = 0
对于所有i,j∈[0,m + 1]。我们要分析两种热源的热流,分别为: fi,j =
如果k(xi,yj)−(0.35,0.6)k≤0.1
如果k(xi,yj)−(0.8,0.25)k≤0.1
否则为0。
2 0 10 20 30
0 10 20 30
0 0.002 0.004 0.006 0.008 0.01 0.012
Figure 2: Example plot for three heat sources
An example of a final temperature distribution for a different set of three heat sources is shown in Figure 2.
Define a vector x such that xk = Ti,j ,
where k = (j − 1)m + i. Similarly, we define the vector b with bk = fi,j . Then we can write equation (3) in matrix form
Ax = b. (4)
The coefficient matrix A is sparse with size n × n, where n = m2.
(a) Create a MATLAB function [A,b] = Lap2D(m). The input is a positive integer m, the number of active grid points in each dimension. The outputs are the matrix A and the right-hand side b as in equation (4).
(b) Implement the following numerical methods: Gaussian elimination, Cholesky factorization, and Banded Gaussian elimination. Create the following MATLAB functions:
x=GaussElim(A,b)
x=Cholesky(A,b)
x=BandGE(A,b,p,q)
These MATLAB functions take as inputs the matrix A and right-hand side b and compute the solution x using the corresponding variant of Gaussian elimination. The parameters p and q indicate the lower and upper matrix bandwidth, respectively. (There is no need to implement pivoting or check for zero or small pivots.) You can check your code by visualizing the solution x. Use the following command:
>> mesh(reshape(x,m,m))
This will convert the solution vector x into a 2D array, and generate a 2D mesh plot of the result. Submit a 2D mesh plot of the solution for the case when m = 20.
(c) Create a MATLAB script, GETimes.m, that solves (4) using the three different variants of Gaussian elimination you wrote. In particular, set up the matrix A and right-hand 3 side b by calling the MATLAB function Lap2D. Then solve the equation by calling one of the MATLAB functions in part (b). Record the execution time using the MATLAB commands tic and toc. Construct a table of execution times for solving with each of the methods above. Try the grid sizes 8×8, 16×16, 24×24, 32×32. (Consider vectorizing the innermost loop of your implementations to keep solve times more manageable.) Compare and comment on the timing results for the three methods you implemented.
Submit to the LEARN Dropbox: Lap2D.m, GaussElim.m, Cholesky.m, BandGE.m, GETimes.m,a mesh plot of x, a table of CPU times, and your comments on the timing results.
7. [CS675 students only] ( 15 marks ) Consider using finite differences to discretize the three-dimensional version of the heat equation in question 6.
(a) Create a MATLAB function:
A = Lap3D(m)
The input is m, the number of active grid points in each dimension. The output is the sparse matrix A, whose size is n × n where now we have n = m3. You do not need to build b.
(b) Create another MATLAB function:
B = ReorderedLap3D(A,ordering method)
that takes your Laplacian matrix and produces a reordered version. The first input parameter is the Laplacian matrix A produced by Lap3D. The second input, ordering method,is a string that can be one of the following: ‘natural’, ‘rcm’, ‘min’, which correspond to the natural rowwise, reverse Cuthill-McKee (RCM), and minimum degree orderings,respectively. You will use MATLAB’s reordering functionality to generate reordered versions of the matrix A. For example, to construct the ordering vector for RCM and then apply it to the matrix, do the following:
>> p = symrcm(A);
>> B = A(p,p);
Then the matrix B is the reordering of A using the RCM ordering. The corresponding MATLAB command for the minimum degree ordering is symamd.
(c) Create a MATLAB script, CompareNNZ.m, that compares the number of nonzeros in the Cholesky factorization of A using different orderings. The program should call Lap3D to create a sparse matrix A, and then use ReorderLap3D to perform each of the reorderings. Then compute the Cholesky factor G using the MATLAB command chol.
Determine the number of nonzeros of G using the MATLAB command nnz. Construct a table of number of nonzeros in A and G for different ordering methods and grid sizes.
Use grid resolutions of m = 8, 16, 24, 32, 40. Comment on the number of nonzeros in different cases. In particular, how are the number of nonzeros affected by the ordering methods and grid dimensions? Which ordering method produces the fewest nonzeros in G? Produce a sparsity plot of G for each of the three ordering methods for the m = 24 case, using MATLAB’s spy command.
Submit to the LEARN Dropbox: Lap3D.m, ReorderLap3D.m, CompareNNZ.m, the three sparsity plots, a table of numbers of nonzeros, and your comments on the results.