Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 7: Problem 2

Consider the problem described in Example \(7.1\), where the boundary condition \(u(0, y)=0\) is replaced by $$ \frac{\partial u}{\partial x}(0, y)=0 $$ (Example 4.17 considers such a change in one variable, but here life is harder.) Correspondingly, we change the conditions \(u_{0, j}=0, j=1, \ldots, N\), into $$ 4 u_{0, j}-2 u_{1, j}-u_{0, j+1}-u_{0, j-1}=b_{0, j}, \quad 1 \leq j \leq N $$ where still \(u_{0,0}=u_{0, N+1}=0\). You don't need to know for the purposes of this exercise why these new linear relations make sense, only that \(N\) new unknowns and \(N\) new conditions have been introduced. (a) What is the vector of unknowns u now? What is \(\mathbf{b}\) ? What is the dimension of the system? (b) What does \(A\) look like? [Hint: This exercise may not be easy; do it for the case \(N=3\) first!]

Short Answer

Expert verified
**Answer:** The structure of the matrix A is a sparse 20 x 20 square matrix with coefficients from the given boundary equations placed in corresponding rows and columns. The dimensions of the vectors u and b are both (N+1)(N+2) = 20, where N is the number of unknowns in one dimension.

Step by step solution

01

Determine the vector of unknowns u

The vector of unknowns \(\mathbf{u}\) will have the \(u_{i,j}\) values for all \(i = 0,1, \ldots, N\) and \(j = 0,1, \ldots, N+1\). Since there is a total of \((N+1)(N+2)\) unknowns, the dimension of the vector \(\mathbf{u}\) is \((N+1)(N+2)\). For the case \(N=3\), there are \(20\) unknowns in the vector: \(u_{0,0}\), \(u_{0,1}\), \(u_{0,2}\), \(u_{0,3}\), \(u_{0,4}\), \(u_{1,0}\), ..., \(u_{3,4}\).
02

Determine the vector b

The vector \(\mathbf{b}\) contains the right-hand-side terms, given by the equation \(4 u_{0, j}-2 u_{1, j}-u_{0, j+1}-u_{0, j-1}=b_{0, j}, \quad 1 \leq j \leq N\). The dimension of the vector \(\mathbf{b}\) is equal to the number of linear equations, which is \((N+1)(N+2)\). For the case \(N=3\), there are \(20\) terms in the vector \(\mathbf{b}\): \(b_{0,0}\), \(b_{0,1}\), \(b_{0,2}\), \(b_{0,3}\), \(b_{0,4}\), \(b_{1,0}\), ..., \(b_{3,4}\).
03

Find the dimension of the system

The dimension of the system is equal to the number of unknowns, which is \((N+1)(N+2)\). For the case \(N=3\), the dimension of the system is \(20\).
04

Describe the matrix A

The matrix A will be a square matrix of size \((N+1)(N+2) \times (N+1)(N+2)\). Each row of the matrix will correspond to an equation, while each column will correspond to an unknown \(u_{i,j}\). Coefficients from the given boundary equation are placed in the corresponding rows and columns. For example, the coefficient for the term \(4u_{0,1}\) in the first equation will be placed in the entry corresponding to the row for the first equation and the column for the \(u_{0,1}\) unknown. You should notice that the matrix A is sparse, i.e., it contains a large number of zeroes. For the case \(N=3\), the matrix A will be of size \(20 \times 20\). It will have the following structure: [4,-2,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] [-2,4,-2,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0] [0,-2,4,-2,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0] [0,0,-2,4,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0] [-1,0,0,0,4,-2,0,0,-1,0,0,0,0,0,0,0,0,0,0,0] [0,-1,0,0,-2,4,-2,0,0,-1,0,0,0,0,0,0,0,0,0,0] [0,0,-1,0,0,-2,4,-2,0,0,-1,0,0,0,0,0,0,0,0,0] [0,0,0,-1,0,0,-2,4,0,0,0,-1,0,0,0,0,0,0,0,0] [0,0,0,0,-1,0,0,0,4,-2,0,0,-1,0,0,0,0,0,0,0] [0,0,0,0,0,-1,0,0,-2,4,-2,0,0,-1,0,0,0,0,0,0] [0,0,0,0,0,0,-1,0,0,-2,4,0,0,0,-1,0,0,0,0,0] [0,0,0,0,0,0,0,0,0,0,0,4,-2,0,0,-1,0,0,0,0] [0,0,0,0,0,0,0,0,-1,0,0,-2,4,-2,0,0,-1,0,0,0] [0,0,0,0,0,0,0,0,0,-1,0,0,-2,4,-2,0,0,-1,0,0] [0,0,0,0,0,0,0,0,0,0,-1,0,0,-2,4,-2,0,0,-1,0] [0,0,0,0,0,0,0,0,0,0,0,-1,-2,0,-2,4,0,0,0,-1,0] [0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,4,-2,0,0,0] [0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,-2,4,-2,0] [0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,-2,4,-2] [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-2,0,-2,4] Though this exercise is not easy, breaking it down into steps and focusing on the \(N=3\) case can help ensure a solid understanding of the problem.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Finite Difference Methods
Finite Difference Methods are a powerful tool for approximating solutions to differential equations by using discrete approximations. This approach is essential because exact solutions for partial differential equations (PDEs) are often challenging to find. Finite difference methods involve replacing the derivatives in equations with difference equations that approximate them at discrete points.
These points form a grid over the domain of the problem, and the grid can vary in density depending on the level of accuracy needed.
Numerical boundary conditions, such as those described in the exercise, are crucial because they influence the solution over the entire domain. By implementing such methods, we discretize a continuous problem to make it solvable with linear algebra techniques, which is less resource-intensive than solving components directly.
This conversion is especially beneficial for complex systems where intuition from exact methods isn't applicable.
Partial Differential Equations
Partial Differential Equations (PDEs) describe phenomena with more than one independent variable. They are fundamental in expressing laws of nature, from heat distribution to sound waves.
These equations involve partial derivatives and form the backbone for modeling dynamics in various fields such as physics and engineering.
In the exercise, the change in boundary conditions illustrates how different scenarios can lead to alterations in PDEs. When boundaries are shifted, it alters the behavior of the solution over the entire domain.
This requires adjusting equations to ensure conditions match real-world constraints across various instances. Consequently, the task involves ensuring the number of unknowns matches the number of boundary conditions to maintain system consistency.
The nature of PDEs means that solving them often requires sophisticated numerical techniques, given that analytical solutions may not be feasible or might not exist at all.
Sparse Matrix Representation
When solving large systems of equations derived from discretized domains in PDEs, matrices often become very large. However, these matrices can also be sparse, meaning they have numerous zero elements relative to non-zero elements.
Sparse matrix representation is a way to optimize storage and computational resources by focusing only on non-zero elements.
In the exercise scenario, representing the matrix 'A' as a sparse matrix means focusing computational efforts and memory on significant coefficients. This dramatically reduces the computational load, especially when solving large systems with potentially thousands of equations. The format reduces storage requirements and speeds up mathematical operations, which can be crucial for real-time applications or large-scale simulations.
Overall, understanding sparse matrix representation requires an appreciation of data structure optimization and the ability to exploit sparsity in linear systems to harness efficient algorithm performance.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Let \(A\) be a symmetric positive definite \(n \times n\) matrix with entries \(a_{i j}\) that are nonzero only if one of the following holds: \(i=1\), or \(i=n\), or \(j=1\), or \(j=n\), or \(i=j\). Otherwise, \(a_{i j}=0\). (a) Show that only \(5 n-6\) of the \(n^{2}\) elements of \(A\) are possibly nonzero. (b) Plot the zero-structure of \(A\). (In MATLAB you can invent such a matrix for \(n=20\), say, and use spy (A).) (c) Explain why for \(n=100,000\) using chol (see Section 5.5) to solve \(A \mathbf{x}=\mathbf{b}\) for a given right-hand-side vector would be problematic.

Let \(A\) be a general nonsymmetric nonsingular square matrix, and consider the following two alternatives. The first is applying GMRES to solve the linear system \(A \mathbf{x}=\mathbf{b} ;\) the second is applying CG to the normal equations $$ A^{T} A \mathbf{x}=A^{T} \mathbf{b} $$ We briefly discussed this in Section \(7.5\); the method we mentioned in that context was CGLS. (a) Suppose your matrix \(A\) is nearly orthogonal. Which of the two solvers is expected to converge faster? (b) Suppose your matrix is block diagonal relative to \(2 \times 2\) blocks, where the \(j\) th block is given by $$ \left(\begin{array}{cc} 1 & j-1 \\ 0 & 1 \end{array}\right) $$ with \(j=1, \ldots, n / 2\). Which of the two solvers is expected to converge faster? [Hint: Consider the eigenvalues and the singular values of the matrices.]

(a) Write a program for solving the linear least squares problems that arise throughout the iterations of the GMRES method, using Givens rotations, where the matrix is a nonsquare \((k+1) \times k\) upper Hessenberg matrix. Specifically, solve $$ \min _{\mathbf{z}}\left\|\rho e_{1}-H_{k+1, k} \mathbf{z}\right\| $$ Provide a detailed explanation of how this is done in your program, and state what \(Q\) and \(R\) in the associated QR factorization are. (b) Given \(H_{k+1, k}\), suppose we perform a step of the Arnoldi process. As a result, we now have a new upper Hessenberg matrix \(H_{k+2, k+1}\). Describe the relationship between the old and the new upper Hessenberg matrices and explain how this relationship can be used to solve the new least squares problem in an economical fashion. (c) The least squares problems throughout the iterations can be solved using a QR decomposition approach. Show that the upper triangular factor cannot be singular unless \(\mathbf{x}_{k}=\mathbf{x}\), the exact solution.

A skew-symmetric matrix is a matrix \(S\) that satisfies $$ s^{T}=-S $$ (a) Show that for any general matrix \(A\), the matrix \(\left(A-A^{T}\right) / 2\) is skew-symmetric. (This matrix is in fact referred to as the "skew- symmetric part" of \(A\).) (b) Show that the diagonal of a skew-symmetric matrix \(S\) must be zero component-wise. (c) Show that the eigenvalues of \(S\) must be purely imaginary. (d) If \(S\) is \(n \times n\) with \(n\) an odd number, then it is necessarily singular. Why? (e) Suppose that the skew-symmetric \(S\) is nonsingular and sparse. In the process of solving a linear system associated with \(S\), a procedure equivalent to Arnoldi or Lanczos is applied to form an orthogonal basis for the corresponding Krylov subspace. Suppose the resulting matrices satisfy the relation $$ S Q_{k}=Q_{k+1} U_{k+1, k} $$ where \(Q_{k}\) is an \(n \times k\) matrix whose orthonormal columns form the basis for the Krylov subspace, \(Q_{k+1}\) is the matrix of basis vectors containing also the \((k+1)\) st basis vector, and \(U_{k+1, k}\) is a \((k+1) \times k\) matrix. i. Determine the nonzero structure of \(U_{k+1, k} .\) Specifically, state whether it is tridiagonal or upper Hessenberg, and explain what can be said about the values along the main diagonal. ii. Preconditioners for systems with a dominant skew-symmetric part often deal with the possibility of singularity by solving a shifted skew-symmetric system, where instead of solving for \(S\) one solves for \(S+\beta_{k} I\) with \(\beta_{k}\) a scalar. Suppose we have the same right-hand-side, but we need to solve the system for several values of \(\beta_{k}\). Can the Arnoldi or Lanczos type procedure outlined above be applied once and for all and then be easily adapted? iii. Describe the main steps of a MINRES-like method for solving a skew- symmetric linear system.

The damped Jacobi (or under-relaxed Jacobi) method is briefly described in Sections \(7.2\) and \(7.6\). Consider the system \(A \mathbf{x}=\mathbf{b}\), and let \(D\) be the diagonal part of \(A\). (a) Write down the corresponding splitting in terms of \(D, A\), and \(\omega\). (b) Suppose \(A\) is again the same block tridiagonal matrix arising from discretization of the two-dimensional Poisson equation. i. Find the eigenvalues of the iteration matrix of the damped Jacobi scheme. ii. Find the values of \(\omega>0\) for which the scheme converges. iii. Determine whether there are values \(\omega \neq 1\) for which the performance is better than the performance of standard Jacobi, i.e., with \(\omega=1\).
See all solutions

Recommended explanations on Math Textbooks

Geometry

Read Explanation

Decision Maths

Read Explanation

Mechanics Maths

Read Explanation

Calculus

Read Explanation

Pure Maths

Read Explanation

Applied Mathematics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free