提示: 欢迎访问OurACM平台。
Problem 1052 Partial Differential Equations

Accept: 1    Submit: 3
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

In engineering sciences, partial differential equations play an important and central role. For example, the temperature of a metal plate can be expressed as a partial differential equation if the temperature on the boundaries is known. This is called a boundary value problem.

Usually, it is not easy to solve these problems. Analytical solutions exist only in very special cases. But there are some more or less "good" numerical ways to solve boundary value problems.

We now will look at one method which works with finite difference approximations for the derivatives of a function. For this approach, we do not look at an analytical function u(x) but we are only interested in the values of u at a finite set of discrete points tex2html_wrap_inline118 . The distance between two adjacent points, tex2html_wrap_inline120 and tex2html_wrap_inline122 , is constant: tex2html_wrap_inline124 (cf. figure 1).

  figure26
Figure: u(x) at some discrete points tex2html_wrap_inline120

The finite difference approximation of a first derivative of the function u(x) is

equation33

The second derivative is approximated by

equation39

This approximation works with 2-dimensional functions u(x,y) as well. For simplicity we only work on square problems, i.e. (x, y) is element of tex2html_wrap_inline136 . Again, the area of the function is discretized in a similar way: tex2html_wrap_inline138 , for some integer tex2html_wrap_inline140 . We only look at the values of u(x,y) at the discrete points tex2html_wrap_inline144 . With this discretization, we have a function tex2html_wrap_inline146 as shown in figure 2:

  figure50
Figure: Function tex2html_wrap_inline146 in the discretization area

On the boundary, tex2html_wrap_inline150 is given by 4 known functions:

equation57

The points tex2html_wrap_inline152 cover the inner points of the discretization area, i.e. the area without the boundary. They are numbered from left to right and from top to bottom like English text.

What we now want to do is to solve the poisson-equation in the area tex2html_wrap_inline136 :

equation62

with the above boundary conditions. f(x,y) is a given 2-dimensional function. With equation (2) and the above discretization, the poisson-equation can be approximated at

equation66

where tex2html_wrap_inline158 is the function f(x,y), evaluated at the discrete points tex2html_wrap_inline162 .

Formula (5) can be written in a more readable form, depending on the position of the discrete points:

displaymath164

A similar equation, which we will use as an example below, is:

displaymath166

We call the tex2html_wrap_inline168 matrix on the left hand side v and the tex2html_wrap_inline168 matrix on the right hand side g.

Now, equation (6b) can be formulated in every point of the discrete area of figure 2:

equation92

and (7) is a linear equation system for the values of u(x,y) at the points tex2html_wrap_inline178 and tex2html_wrap_inline180 .

By rearranging and adding the terms on each line, the linear equation system can be formulated as:

equation101

where a is a tex2html_wrap_inline184 matrix and b is a vector with 4 elements. Vector z represents the unknown values of u(x,y) at the points tex2html_wrap_inline178 and tex2html_wrap_inline180 .

You are to write a program that creates the linear equation system (7) in the form (8) for any two matrices v and g (6). As input, the two matrices v and g and the functions tex2html_wrap_inline204 , and f are given. Also, a parameter n is given as the number of discretization intervals. Thus, tex2html_wrap_inline210 . As the result, your program should calculate the matrix a and the vector b. For this more general case, there are tex2html_wrap_inline216 inner points and a and b must be sized accordingly.

Input

The input file consists of m tests. The number m is given in the first line of the file. The first line of each test contains the number n which gives the number of discretizations intervals as defined above. You may assume that tex2html_wrap_inline228 . Then the tex2html_wrap_inline168 matrices v and g follow. The following four lines contain the functions tex2html_wrap_inline236 and tex2html_wrap_inline238 , each given as a vector of order n+1, containing the values for 0, h, 2h, ..., 1. Finally, the function f is given as a n+1 by n+1 matrix. Like the vectors before, it contains the values for tex2html_wrap_inline252 . Each row contains from left to right the function values for increasing x values while each column contains from top to bottom the function values for decreasing y values.

A vector occupies one line. Its values are given in ascending order, separated by a space. A n by n matrix occupies n lines. Its rows are given in ascending order as vectors, which occupy one line each. All values found in the input file are integer values.

Output

For each test found in the input file, your program should output the matrices a and b. Matrix a is a tex2html_wrap_inline270 matrix (the discretization area (cf. figure 2) contains tex2html_wrap_inline216 inner points, which are unknown). The vector b is of order tex2html_wrap_inline216 . They should be output in the same format as the vectors and matrices in the input file. Your output should only contain integer values. Note that the expression tex2html_wrap_inline278 yields an integer number and that all other calculations can also be done using integer numbers.

Sample Input

1 3 1 0 2 0 -4 0 3 0 4 0 5 0 6 0 7 0 8 0 3 4 5 6 0 1 2 3 3 2 1 0 6 5 4 3 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4

Sample Output

-36 0 0 36 0 -36 27 0 0 18 -36 0 9 0 0 -36 -35 -188 -189 -315

Submit  Back  Status  Discuss